基于集成學習的決策粗糙集特定類屬性約簡算法

李 明 甘秀娜 王月波

1(石家莊鐵道大學四方學院經濟管理系 河北 石家莊 051132)2(石家莊鐵路職業技術學院組織人事部 河北 石家莊 050041)3(河北銀行股份有限公司信息技術部 河北 石家莊 050000)

0 引 言

粗糙集模型是目前處理不確定性數據的一種重要的機器學習和數據挖掘理論[1]，近年來受到學者們的廣泛關注和研究。決策粗糙集模型[2]是傳統粗糙集的重要延伸，Yao[2]通過在決策粗糙集中融入最小化決策代價的原則，提出了三支決策理論，進一步地擴大決策粗糙集的應用范圍[3]，目前決策粗糙集與三支決策已成功運用于數據挖掘等各個領域[4-6]。

屬性約簡是粗糙集理論的主要研究內容[1]，在決策粗糙集模型中，學者們提出了多種屬性約簡方法。第一類為基于正區域的屬性約簡，例如：Yao等[7]在決策粗糙集中提出了正區域屬性約簡，這也是決策粗糙集模型最早的屬性約簡方法；Ma等[8]對文獻[7]方法進一步改進，將決策邊界域和決策負區域也加入到決策區域屬性約簡的范疇，提出了保持決策區域的屬性約簡算法；Meng等[9]在算法的效率上進行改進，提出了一種正區域的快速決策粗糙集屬性約簡；Gao等[10]通過信息熵的視角，提出一種最大決策熵的決策粗糙集屬性約簡算法；姚晟等[11]進一步對正區域屬性約簡進行改進，提出一種決策區域最大化的決策粗糙集屬性約簡。第二類為基于決策代價的屬性約簡方法，Jia等[12-13]在決策粗糙集中定義了最小化決策代價屬性約簡，并設計了多種相應的啟發式屬性約簡算法；Dou等[14]利于多代價的策略，提出了相應的最小化決策代價的屬性約簡；Song等[15]在模糊決策粗糙集下定義了決策代價，同時相應的最小化決策代價屬性約簡算法也被提出；Li等[16]將決策粗糙集推廣至鄰域空間，并提出鄰域空間下的最小化決策代價屬性約簡。總之，決策粗糙集在這兩方面的屬性約簡中已取得了豐碩的成果。

然而在實際應用環境下，往往只考慮某個或某幾個特定的決策類，并且在進行決策區域的屬性約簡時也需要考慮代價的問題。例如：在醫療診斷中可能只關注患病的樣本類，并且在保證診斷正確率的同時也要盡可能地降低診斷所付出的代價，這對目前的屬性約簡方法帶來一定的挑戰。針對特定類的問題，Yao等[17]在傳統粗糙集模型中提出了基于特定類的屬性約簡，在此基礎上，Ma等在決策粗糙集下分別提出了特定類的正區域屬性約簡[18]和決策代價屬性約簡[19]；彭莉莎等[20]提出了基于概率的特定類屬性約簡。然而這些研究成果也僅限于單一的屬性約簡視角，未同時考慮決策區域和決策代價的屬性約簡問題。

為了在特定類視角下同時兼顧決策區域和決策代價，本文將這兩方面同時作為決策粗糙集屬性約簡的優化目標，定義一種特定類的屬性約簡，在該屬性約簡中，約簡結果在保證決策區域極大化的同時，使得進行決策區域劃分時也具有較低的決策代價，并且這些約簡的目標都是針對特定決策類的。為了實現這種屬性約簡，本文接著利用集成學習的方法，設計出了相應的屬性約簡算法，最后通過與單一的決策區域屬性約簡和單一的最小化決策代價屬性約簡進行實驗分析對比，證明了本文算法的有效性和優越性。

1 決策粗糙集模型與三支決策

決策信息系統[1]表示為二元組S=(U,C∪D)，這里的U為非空有限對象集，被稱為論域。C為非空有限條件屬性集，D為非空有限決策屬性集，并且C∩D=?。對于對象?x∈U在屬性?a∈C∪D均有一個確定的屬性值，表示為f(x,a)，通過對象、屬性與屬性值這三個組成部分，構建了整個決策信息系統。

定義1[1]考慮決策信息系統S=(U,C∪D)，屬性子集A?C確定的等價關系定義為：

EA={(x,y)∈U×U|?a∈A,f(x,a)=f(y,a)}

(1)

等價關系滿足自反性、對稱性和傳遞性。基于等價關系可以將論域誘導出一個劃分，表示為U/EA。在U/EA中，包含對象x的等價類[x]A定義為：

[x]A={y∈U|(x,y)∈EA}

(2)

定義2[1]考慮決策信息系統S=(U,C∪D)，屬性子集A?C確定的等價關系為EA，對于對象集X?U關于等價關系EA的下近似集和上近似集分別定義為:

(3)

(4)

由于傳統的粗糙集建立在等價關系基礎之上，對象與近似集之間的粗糙逼近關系過于嚴格。為了進行改進，Yao[2]提出了一種決策粗糙集模型與三支決策理論，通過一對閾值來限定等價類與近似集之間的逼近程度，提高了粗糙集模型的容噪性能[3]。

設決策信息系統中的狀態集為Ω={X,Xc},Xc為X的補集，分別表示對象屬于狀態X或不屬于狀態X，設動作集為Γ={aP,aB,aN}，分別表示對象分類入狀態X的正區域POS(X)、邊界域BUN(X)和負區域NEG(X)，即接受、延遲和拒絕三種決策行為。當對象處于不同狀態時采取不同的動作行為，三支決策模型定義了相應的決策代價矩陣，具體如表1所示。在表1中，λPP、λBP和λNP分別表示對象處于狀態X時采取aP、aB和aN決策動作時所產生的代價；λPN、λBN和λNN分別表示對象處于狀態Xc時采取aP、aB和aN決策動作時所產生的代價。

表1 決策代價矩陣

考慮決策信息系統S=(U,C∪D)，對于屬性子集A?C確定的等價關系為EA，對象?x∈U誘導出的等價類為[x]A，那么對象x隸屬于對象集X?U和Xc的概率表示為：

(5)

給定決策代價矩陣，那么對象x∈U采取不同動作的決策代價可表示為：

(1)CostaP(x)=λPP·P(X|[x]A)+λPN·P(Xc|[x]A)。

(2)CostaB(x)=λBP·P(X|[x]A)+λBN·P(Xc|[x]A)。

(3)CostaN(x)=λNP·P(X|[x]A)+λNN·P(Xc|[x]A)。

根據貝葉斯決策準則，可以得到如下最小化決策代價規則：

(1) 當CostaP(x)≤CostaB(x)且CostaP(x)≤CostaN(x)時，則有x∈POS(X)；

(2) 當CostaB(x)≤CostaP(x)且CostaB(x)≤CostaN(x)時，則有x∈BUN(X)；

(3) 當CostaN(x)≤CostaP(x)且CostaN(x)≤CostaB(x)時，則有x∈NEG(X)。

進一步推導可以得到：

(1) 若P(X|[x]A)≥α且P(X|[x]A)≥γ,那么x∈POS(X);

(2) 若P(X|[x]A)≤α且P(X|[x]A)≥β,那么x∈BUN(X);

(3) 若P(X|[x]A)≤β且P(X|[x]A)≤γ,那么x∈NEG(X)。

其中：

那么對于決策信息系統S=(U,C∪D)，屬性子集A?C確定的等價關系為EA，對象集X在等價關系EA下的三支決策區域[2]表示為：

(6)

同時，決策屬性D在信息系統下誘導的決策類劃分表示為πD={D1,D2,…,Dm}，那么決策屬性D關于屬性子集A的三支決策區域[7]為：

(7)

2 基于特定類的決策代價屬性約簡

決策粗糙集模型下的三支決策給出了一種新的決策模式[2-3,5-6]，進一步降低了決策行為的決策代價。然而，實際應用系統中的某些屬性對決策和分類不相關，這些屬性的刪除可能會保持或者降低整個信息系統的決策代價[12-13]。針對這類研究問題，學者們提出了一種最小化決策代價的屬性約簡算法[12]，該算法旨在找出信息系統擁有最小決策代價的屬性子集。

考慮決策信息系統S=(U,C∪D)，給定決策代價矩陣，屬性子集A?C確定的等價關系為EA。決策屬性D誘導的決策類劃分為πD={D1,D2,…,Dm}，那么對象?x∈U對于不同決策規則所產生的決策代價[12]表示為：

(1) 接受決策：p(x)·λPP+(1-p(x))·λPN；

(2) 延遲決策：p(x)·λBP+(1-p(x))·λBN；

(3) 拒絕決策：p(x)·λNP+(1-p(x))·λNN。

這里的p(x)=P(Dmax([x]A)|[x]A)，并且：

(8)

通常當對象決策為正確的區域時，是不會產生任何代價的，因此代價λPP=λNN=0，那么決策規則代價可以進一步簡化為：

(1) 接受決策：(1-p(x))·λPN；

(2) 延遲決策：p(x)·λBP+(1-p(x))·λBN；

(3) 拒絕決策：p(x)·λNP。

那么整個決策信息系統的決策總代價[12]可以表示為如下形式：

(9)

基于決策代價的屬性約簡，即找出決策總代價最小的屬性子集，其定義如下所示。

定義3[12]考慮決策信息系統S=(U,C∪D)，給定決策代價矩陣，屬性子集A?C確定的等價關系為EA。決策屬性D誘導的決策類劃分為πD={D1,D2,…,Dm}，若屬性子集A是屬性集C的最小決策代價屬性約簡集，那么當且僅當：

(2) ?A′?A,COSTA′(πD)>COSTA(πD)。

根據定義3所示的屬性約簡定義，學者們提出了多種屬性約簡算法以及多種擴展的屬性約簡算法[14-16],并且目前提出的這些算法均是針對全局的決策類，即算法得到約簡子集使得所有決策類整體決策代價最小。然而，對于實際中的某些情形，我們可能只關注某個或某幾個決策類，例如在疾病診斷中，如果對患病的樣本進行屬性約簡，得到約簡結果可以進一步降低決策代價，提高診斷的質量。如果對于某一類疾病，基于該類別進行屬性約簡，那么得到的約簡結果與該種疾病是相適應的，不同疾病得到與之對應的屬性子集，這樣可以提高醫療診斷的效率和性能。因此針對某個或某幾個類進行屬性約簡可以達到更好的處理性能，提高實際運用的適用性。

考慮決策信息系統S=(U,C∪D)，屬性子集A?C確定的等價關系為EA。決策屬性D誘導的決策類劃分為πD={D1,D2,…,Dm}，給定特定決策類Dt∈πD以及對應的決策代價矩陣，那么對象?x∈U關于特定決策類Dt的決策代價表示為：

(1) 接受決策：(1-pDt(x))·λPN；

(2) 延遲決策：pDt(x)·λBP+(1-pDt(x))·λBN；

(3) 拒絕決策：pDt(x)·λNP。

這里的pDt(x)=P(Dt|[x]A)。

那么整個決策信息系統關于決策類Dt的決策總代價可以表示為：

(10)

決策信息系統決策類Dt的決策總代價滿足如下性質。

定理1考慮決策信息系統S=(U,C∪D)，給定特定決策類Dt∈πD，Dt相應的決策代價矩陣如表2所示，設兩個屬性子集滿足A1?A2?C，并且確定的等價關系分別為EA1和EA2，那么決策類Dt關于屬性集A1和A2的決策代價滿足：

證明根據等價關系的定義可以得到，隨著屬性的增加，對象的等價類是單調性變化的，即滿足當A1?A2時有[x]A2?[x]A1。然而隨著屬性的變化，三支決策區域卻不是單調性變化的[7-8]，即隨著屬性數量的增加，三支決策區域的變化是隨機的。對于?x∈U，屬性變化前后x隸屬區域的變化可分為9種，分別表示為：

為了簡便，假設屬性增加時只有一個等價類發生變化，多個等價變化時可根據單個變化進行類推。當對象x的區域隸屬變化滿足情形(1)、(5)和(9)時，可以直接得到COSTA1(Dt)=COSTA2(Dt)。

COSTA2(Dt)-COSTA1(Dt)=

COSTA1(Dt)≥COSTA2(Dt)

COSTA2(Dt)-COSTA1(Dt)=

綜上所述，可以得到COSTA1(Dt)≥COSTA2(Dt)。

證明完畢。

定理1表明了特定類的決策代價隨著屬性滿足單調性的變化，這也進一步地解釋了三支決策的實際意義[2]，即隨著屬性的增加，可用于決策的有用信息會越來越多，從而決策的準確率會更高，決策代價會更小。在決策的過程中，并不是所有的屬性都是對決策有用的，有些屬性的加入并不會降低決策代價，因此這類屬性需要進行刪除。基于此，接下來將給出特定類的最小化決策代價屬性約簡的定義。

定義4考慮決策信息系統S=(U,C∪D)，給定特定的決策類Dt∈πD以及對應的決策代價矩陣，屬性子集A?C確定的等價關系為EA，若屬性子集A是C的決策類Dt最小決策代價屬性約簡，那么當且僅當：

(1)COSTA(Dt)=COSTC(Dt);

(2) ?A′?A,COSTA′(Dt)>COSTA(Dt)。

在定義4中，由于特定類決策代價的單調性，因此屬性全集C擁有最小的決策代價，那么屬性約簡的目的是為了找出與屬性全集C有著同樣決策代價的屬性子集，并且該屬性子集中不包含其他任何的冗余屬性，即屬性約簡集滿足極小性。

核屬性集[1]在尋找屬性約簡的過程中發揮著很重要的作用，由于滿足屬性約簡定義的屬性子集并不唯一，但是核屬性集是確定的，并且是所有屬性約簡結果的交集，因此找出屬性約簡的核屬性具有很重要的意義。

定義5考慮決策信息系統S=(U,C∪D)，給定特定的決策類Dt∈πD以及對應的決策代價矩陣，若屬性子集族REDDt表示決策類Dt所有屬性約簡結果的集合，那么核屬性集可定義為：

根據定義5所示的核屬性集定義，采用其他學者的研究方法，核屬性集可直接計算為：

Core(Dt)={a∈C|COSTC-{a}(Dt)>COSTC(Dt)}

3 基于集成學習的特定類屬性約簡

在決策粗糙集模型中，目前主要有兩種類型的屬性約簡受到學者們的廣泛關注：一是基于決策代價的屬性約簡；二是基于決策正區域的屬性約簡。實際應用環境下可能需要綜合考慮這兩類問題進行屬性約簡，Li等[21]在全局類下提出了多目標的屬性約簡，使得約簡的結果具有更為廣泛的適用性能。在特定類視角下，Ma等[18]提出了基于正區域的三支決策特定類屬性約簡，因此本節將Ma等的正區域屬性約簡與上節提出的決策代價屬性約簡進行綜合，提出特定類的決策粗糙集多目標屬性約簡算法。

定義6[18]考慮決策信息系統S=(U,C∪D)，給定特定的決策類Dt∈πD以及對應的決策代價矩陣，屬性子集A?C確定的等價關系為EA，若屬性子集A是C的決策類Dt正區域屬性約簡，那么當且僅當：

由于三支決策模型中決策類的三個區域并不是隨屬性集單調性變化的，即屬性子集的正區域既可能會大于屬性全集的正區域，也可能會小于屬性全集的正區域。因此屬性約簡結果需要保證約簡集的正區域不低于屬性全集的正區域，并且約簡集是所有屬性子集中最小的，這樣就保證了屬性約簡結果具有較高的區分性能[18]。

接下來將綜合特定類的正區域屬性約簡與本文提出的特定類決策代價屬性約簡，探討其屬性約簡的問題。

屬性約簡[21]同時將多個目標作為屬性約簡的內容，使得約簡結果能夠同時對多個目標達到屬性約簡的效果。本文將同時考慮特定類的決策正區域和決策代價，但是多目標的屬性約簡結果不一定達到局部最優。故所得到的約簡結果不一定既具有最小的決策代價又具有最大的決策正區域，因此這里采用全局最優的方式進行屬性約簡。

(11)

在定義7中，當屬性子集A的決策代價越小，且決策正區域越大時，綜合目標函數F(Dt)則越小。因此對于所提出屬性約簡，其優化的目標是選擇出屬性子集使得F(Dt)盡可能的小。

(1)FA(Dt)≤FC(Dt);

(2) ?A′?A,FA′(Dt)>FA(Dt)。

集成學習[22]是一種常用機器學習方法，該方法讓多個學習模型進行集成，通過整合共同的學習結果來對最終的結果進行學習，本文需要得到特定類下正區域和決策代價整體最優的屬性約簡結果。首先分別計算正區域屬性約簡和決策代價屬性約簡的核屬性集，然后將得到的核屬性集進行求取交集。交集可以看成正區域與決策代價得到的集成結果，然后在這個集成結果的基礎上逐漸去整合剩余屬性來得到最終的屬性約簡結果。具體的算法實現如算法1所示。

算法1基于集成學習的特定類屬性約簡算法

輸入：決策信息系統S=(U,C∪D)，決策類Dt∈πD，決策類Dt的決策代價矩陣。

輸出：決策類Dt的屬性約簡集RedDt。

步驟1初始化Red(Dt)=?，并根據決策代價矩陣計算閾值α和β。

步驟2根據定義5計算決策類Dt的決策代價核屬性集，記為Corecost(Dt)。

步驟3根據文獻[18]計算決策類Dt的正區域核屬性集，記為Corepos(Dt)。

步驟4記：

Core(Dt)=Corecost(Dt)∩Corepos(Dt)

RCore(Dt)=C-Core(Dt)

并令Red(Dt)=Core(Dt)。

步驟5比較FRed(Dt)(Dt)與FC(Dt)的大小，若FRed(Dt)(Dt)>FC(Dt)，跳轉入步驟6。若FRed(Dt)(Dt)≤FC(Dt)，跳轉進入步驟7。

步驟6對于?a∈RCore(Dt)，計算：

如果FRed(Dt)(Dt)-FRed(Dt)∪{amax}(Dt)>0，那么：

Red(Dt)=Red(Dt)∪{amax}

RCore(Dt)=RCore(Dt)-{amax}

并重新跳轉進入步驟5。

步驟7對于?a∈Red(Dt)，若存在FRed(Dt)-{a}(Dt)≤FC(Dt)，那么Red(Dt)=Red(Dt)-{a},并重復步驟7，否則跳轉入步驟8。

步驟8返回決策類Dt的約簡結果Red(Dt)。

4 實驗與結果分析

本節將通過進行實驗來驗證本文所提出的屬性約簡算法的有效性和優越性。

4.1 數據集

表3所示的是實驗中所運用的UCI數據集[23]。其中：|U|表示數據集中對象的數量；|C|表示條件屬性的數量；|πD|表示數據集決策類的數量。

表3 實驗數據集

4.2 實驗設置

4.3 分類精度比較

表4-表6展示的是各個屬性約簡算法得到的屬性約簡集在不同分類算法下的分類精度，其中分類精度結果采用十折交叉驗證法進行計算得到，加粗的數值表示每行結果的最大值。本文提出的屬性約簡算法是針對具體的決策類，因此每個決策類將得到相應的屬性約簡結果，然后基于每個決策類對應的屬性約簡集利用分類器對其進行分類精度計算，得到每個決策類的分類精度結果，最后將每個決策類的精度進行綜合，得到整個數據集的分類精度。

表4 各個數據集屬性約簡集的J48分類精度結果

續表5

表6 各個數據集屬性約簡集的SMO分類精度結果

在表4所示的J48分類精度結果中，可以發現本文算法得到的屬性約簡結果在大部分數據集下最高，只在數據集Lymphography和數據集Cancer低于其他算法。正區域算法在Lymphography有著最高的分類精度，粒子群優化算法在Cancer下有著最高的分類精度，并且正區域算法和粒子群優化算法的分類精度總體上要高于決策代價算法。在表5所示的RandomForest分類精度結果中，同樣除Lymphography和Mushroom以外的所有數據集，本文所提出的算法具有最高的分類精度，其余算法在少部分數據集的分類精度稍高，并且決策代價算法稍低于正區域算法和粒子群優化算法。在表6所示的SMO分類精度結果中，同樣可以看出本文算法在大部分數據集下的分類精度是最高的。

表5 各個數據集屬性約簡集的RandomForest分類精度結果

綜合表4-表6的實驗結果，表明本文算法得到的屬性約簡結果具有更好的分類性能。這主要是由于本文算法是一種多目標的屬性約簡算法，約簡結果兼顧了數據集的分類性能和決策代價，并且約簡的對象是具體的決策類，那么每個決策類可以得到與之相適應的約簡結果，從而進一步地提高了每個決策類的分類性能，因此數據集整體的分類精度要更高。

4.4 決策代價比較

表7展示的是在屬性約簡結果下，各個數據集每個決策類的決策代價結果，其中加粗的數值表示每行結果的最小值。在表7中，最小的決策代價主要分布在本文的屬性約簡算法和決策代價算法，這主要是由于這兩類算法都是關于最小化決策代價的算法，而其余的算法未考慮決策代價問題，因此得到的決策代價均高于這兩種算法。對比本文算法和決策代價算法，可以發現本文算法只在少部分數據集下的決策代價稍高于決策代價算法，而決策代價算法的決策代價高于本文算法的決策類，其決策代價值大幅度高于本文算法。產生這種現象的主要原因是由于決策代價算法進行的是全局的屬性約簡，得到的約簡結果只保證整體決策代價最小，而某些特定決策類的決策代價可能會更高。但本文的算法是基于特定的決策類，每個決策類得到了對應的最小決策代價屬性子集，因此整體的決策代價要小于決策代價算法。

表7 各個決策類在屬性約簡結果下的決策代價比較

綜合兩部分實驗結果，表明了本文所提出的屬性約簡算法同時兼顧了分類精度和決策代價兩方面性能，并且針對特定的決策類進行屬性約簡，得到了對應決策類的約簡結果，在屬性約簡方面有著很好的自適應性，其優越性更高。

5 結 語

決策粗糙集是一種重要的擴展粗糙集模型，其中基于正區域的屬性約簡和基于決策代價的屬性約簡是該模型的研究重點。在實際應用中，屬性約簡的研究對象可能只針對某個決策類，并且需要同時考慮約簡的正區域和決策代價。本文針對信息系統的特定決策類，將正區域和決策代價同時作為屬性約簡的優化目標，定義一種特定類的屬性約簡，并利用集成學習的方法設計出相應的啟發式屬性約簡算法，實驗結果驗證了該算法的有效性和優越性。今后擬將該算法進一步擴展至鄰域信息系統以及混合型信息系統，提高特定類屬性約簡的適用范圍。