鄰域互信息熵的混合型數據決策代價屬性約簡

熊菊霞，吳盡昭，王秋紅

1(中國科學院 成都計算機應用研究所，成都 610041)

2(中國科學院大學 成都計算機應用研究所，北京 100049)

3(廣西民族大學 數學與物理學院，南寧 530006)

1 引 言

粗糙集理論是人工智能和智能計算領域的重要研究內容[1].由于現實環境下數據內容的復雜性，學者們將傳統的粗糙集理論進行推廣，提出了決策粗糙集模型[2]，該模型通過引入閾值來限定粗糙集上下近似的范圍，使得具有更高的泛化性能.決策粗糙集模型已成為目前粗糙集理論的研究熱點[3，4].

屬性約簡是粗糙集理論的重要應用，在傳統的粗糙集理論中，屬性約簡的目的是為了刪除數據集中的不相關屬性和冗余屬性，使得提高數據的分類性能[5，6].然而在決策粗糙集中，決策區域不滿足屬性變化的單調性，因此傳統的屬性約簡算法在決策粗糙集下并不適用[7].由于決策粗糙集是建立在代價理論基礎上粗糙集模型，Jia等[8]學者在決策粗糙集模型中提出了最小化決策代價的屬性約簡方法，理論分析了這種屬性約簡方式的合理性.在Jia的基礎上，其他學者進一步地提出了多種推廣的屬性約簡算法，例如Song等[9]學者在模糊數據環境下提出了最小化代價的屬性約簡算法，彭莉莎等[10]學者提出了面向特定類的最小化代價屬性約簡，Li等[11]學者將決策粗糙集推廣至混合型數據，提出一種鄰域決策粗糙集的最小化代價屬性約簡算法.雖然決策粗糙集不滿足屬性變化的單調性，但是學者們提出了多種非單調性的屬性約簡，例如姚晟等[12]學者提出一種決策粗糙集的非單調決策區域的屬性約簡，Gao等[13]學者提出一種最大決策熵模型，并利用該熵模型去設計屬性約簡算法.

然而目前的決策粗糙集屬性約簡算法大多都是基于單獨的視角進行屬性約簡，即決策代價或分類性能，實際應用中可能需要同時考慮多種情形[14]，并且目前基于分類性能的屬性約簡都是直接利用啟發式函數進行屬性約簡結果的搜索，沒有考慮所選擇屬性之間的獨立性，使得最終的結果可能包含一些冗余屬性，因此也存在一定的缺陷.受這些局限因素的驅使，本文將對聯合決策代價和分類性能兩方面的屬性約簡進行探索，并且盡可能減少屬性約簡結果中的冗余屬性.

互信息熵是度量屬性之間依賴程度的一種常用方法，并且條件互信息熵也是對屬性之間獨立性的一種重要評估，是構造屬性約簡的一種重要方法[15-17].本文在混合型鄰域粗糙集模型的基礎上，分別提出了鄰域信息熵、鄰域聯合熵和鄰域條件熵，然后進一步提出了鄰域互信息熵以及鄰域條件互信息熵，理論分析了它們之間的關系，然后將鄰域互信息熵理論融入鄰域決策粗糙集的決策代價屬性約簡中，提出了基于鄰域互信息熵的混合型數據決策代價屬性約簡算法，該屬性約簡方法選擇出的屬性子集可同時兼顧決策代價和分類性能，由于是利用鄰域互信息熵去選擇屬性，使得屬性約簡結果中的屬性具有很高的獨立性，仿真實驗表明了所提出屬性約簡算法的優越性.

2 相關理論

設混合型信息系統為S=(U，AT=C∪D)，其中論域U={x1，x2，…，xn}，xi(1≤i≤n)稱為信息系統的對象.條件屬性集C={a1，a2，…，am}，其中C=Ca∪Cn，Ca和Cn分別稱為條件屬性集C中的離散型屬性子集和連續型屬性子集.決策屬性D=g0gggggg表示信息系統S的類特征，信息系統中的每個對象都有一個唯一的類標記.對于?x∈U在屬性a∈C下的屬性值表示為a(x).

定義1[18].設混合型信息系統S=(U，AT=C∪D)，屬性子集A?C并且A=Aa∪An，對于鄰域半徑δ，由屬性子集A確定的鄰域關系定義為:

(?a∈Ac，a(x)=a(y))∧dAn(x，y)≤δ}.

P(D-|δA(x))=1-P(D+|δA(x)).

在鄰域決策粗糙集模型中[11]，當對象x屬于對象集D+時，λPP，λBP和λNP分別表示對象x劃分入D+的正區域POS(D+)、邊界域BUN(D+)和負區域NEG(D+)所產生的代價；類似地，當對象x不屬于對象集D+時，即對象x屬于D-，λPN，λBN和λNN分別表示對象x劃分入D-的正區域POS(D-)、邊界域BUN(D-)和負區域NEG(D-)所產生的代價.

那么對象x∈U采取不同動作的決策代價表示為：

1)CostP(x)=λPP·P(D+|δA(x))+λPN·P(D-|δA(x))；

2)CostB(x)=λBP·P(D+|δA(x))+λBN·P(D-|δA(x))；

3)CostN(x)=λNP·P(D+|δA(x))+λNN·P(D-|δA(x)).

根據貝葉斯最小化決策代價規則，那么有：

1)當CostP(x)≤CostB(x)且CostP(x)≤CostN(x)時，即P(D+|δA(x))≥α且P(D+|δA(x))≥γ，則x∈POS(D+).

2)當CostB(x)≤CostP(x)且CostB(x)≤CostN(x)時，即P(D+|δA(x))≤α且P(D+|δA(x))≥β，則x∈BUN(D+).

3)當CostN(x)≤CostP(x)且CostN(x)≤CostB(x)時，即P(D+|δA(x))≤β且P(D+|δA(x))≤γ，則x∈NEG(D+).

其中：

1)當P(D+|δA(x))≥α時，那么x∈POS(D+)；

2)當β

3)當P(D+|δA(x))≤β時，那么x∈NEG(D+).

基于上述決策條件，接下來可以得到整個信息系統中所有對象進行決策時所產生的的代價結果.

其中P(x)=P(D+|δA(x))；1-P(x)=P(D-|δA(x)).

考慮到正確的決策結果通常不產生任何代價，那么λPP=λNN=0.所以有:

利用定義3所示的決策代價，學者們定義了一種最小化決策代價的屬性約簡.

定義4[11].設混合型信息系統S=(U，AT=C∪D)，鄰域半徑為δ，若屬性子集red?C為信息系統S的最小決策代價屬性約簡，那么當且僅當：

2)?red′?red，Costred′(U)>Costred(U).

在各類經典的粗糙集模型中，其中屬性約簡大多基于決策區域作為評價準則，即約簡結果保持決策區域的大小不變.然而在決策粗糙集中，決策區域的劃分是根據對象作出決策的最小代價來確定，因此在決策粗糙集中，基于最小化代價定義屬性約簡是合理的[11].

3 混合型信息系統下鄰域互信息熵的決策代價屬性約簡

3.1 鄰域互信息熵模型

Jia等[8]學者提出的最小化代價屬性約簡只考慮風險，而不考慮條件屬性子集對決策屬性的分類能力.Yu等[19]學者在最小化代價屬性約簡中引入了屬性重要性，但是這一屬性重要度定義只考慮了單個屬性對決策的分類能力.然而在一些實際的數據集中，條件屬性之間往往存在著很強的相關性，可能存在兩個屬性，它們都具有較強的分類能力，但結合在一起不能提高分類性能.為了改善這一局限，本節將使用條件互信息熵的來定義屬性的重要性.

互信息在含噪聲的數據環境中具有良好得魯棒性.在文獻[20]中，Hu等學者將鄰域融入信息熵，提出了連續型數據的信息熵模型，本文將該模型在混合型數據下進行推廣，提出混合型信息系統下的信息熵以及互信息熵模型.

對于?x∈U滿足{x}?δA(x)?U，因此鄰域信息熵滿足0≤NEδ(A)≤logn，其中NEδ(A)=logn當且僅當?x∈U，δA(x)={x}.其中NEδ(A)=0當且僅當?x∈U，δA(x)=U.

類似于定義5，鄰域聯合信息熵同樣滿足關系0≤NEδ(A，B)≤logn.

定理1.NEδ(B|A)=NEδ(A，B)-NEδ(A).

證明：NEδ(A，B)-NEδ(A)=

定理2.設混合型信息系統為S=(U，AT=C∪D)，|U|=n，屬性子集A，B?C，那么如下等式成立：

1)NEδ(B；A)=NEδ(A；B)；

2)NEδ(B；A)=NEδ(A)+NEδ(B)-NEδ(A，B)；

3)NEδ(B；A)=NEδ(B)-NEδ(B|A)=NEδ(A)-NEδ(A|B)；

證明：

1)根據定義8，即：

2)根據定義5和定義6有：

NEδ(A)+NEδ(B)-NEδ(A，B)=

3)根據式(1)和式(2)，聯合定理1，可以得到式(3)成立.

在鄰域互信息熵的基礎上，可以進一步推廣得到鄰域條件互信息熵.

定義9.設混合型信息系統為S=(U，AT=C∪D)，|U|=n，屬性子集P，Q，R?C，那么定義屬性集R下P與Q的鄰域條件互信息熵為:

定理3.NEδ(P；Q|R)=NEδ(P，R)+NEδ(Q，R)-NEδ(R)-NEδ(P，Q，R)；

證明：

NEδ(P，R)+NEδ(Q，R)-NEδ(R)-NEδ(P，Q，R)=

圖1的兩幅圖展示出了各類熵之間的相互關系，其中可以看出鄰域互信息熵表示了兩個屬性集之間相互依賴的程度，而鄰域條件互信息熵可以反映出其中兩個屬性之間的獨立程度.

圖1 各類熵之間的關系示意圖

3.2 鄰域互信息熵的決策代價屬性約簡算法

鄰域互信息熵可以很好地表達混合型信息系統中兩個屬性之間的依賴程度，并且具有很高的魯棒性.因此我們可以通過鄰域互信息熵去定義混合型信息系統中條件屬性子集與決策屬性之間的關聯程度，那么在屬性約簡的搜索過程中，需要選擇出依賴程度最大的屬性子集，即：

maxφ(A，D)；

φ(A，D)即為屬性子集A?C中所有屬性與決策屬性D之間鄰域互信息熵的平均值，通過這個平均值來表達屬性子集A整體關于決策屬性D的依賴程度.

通過鄰域互信息熵選擇出的屬性子集雖然有著較高的依賴程度，但是選擇的屬性子集中可能存在著冗余屬性，即屬性子集中的兩個屬性之間可能存在著依賴關系，刪除其中任意一個而不會對最終的依賴度產生影響.因此接下來利用鄰域條件互信息熵去評估屬性子集中屬性之間的獨立程度，即選擇出的屬性子集需滿足：

maxφ(A，D)

由于NE(aj；D|ai)和NE(ai；D|aj)是通過鄰域條件互信息熵來反映屬性ai與aj之間的獨立程度，即獨立程度大小可以表示為:

NE(aj；D|ai)+NE(ai；D|aj).

那么對于屬性子集A，任意選擇其中兩個屬性進行獨立程度的計算，將所有選擇結果的獨立程度累加起來，來衡量屬性子集A的獨立性，即:

最后再求取平均值，也就是:

因此φ(A，D)可以度量出屬性子集A?C中屬性之間的平均獨立程度，其值越大說明屬性子集A中屬性之間的相互獨立程度越高.

那么對于鄰域互信息熵的屬性約簡，這里希望選擇出的屬性約簡子集A滿足:

max[φ(A，D)+φ(A，D)].

利用鄰域互信息熵作為屬性重要度的評估，這里定義一種屬性重要度函數，具體如定義10所示.

定義10.設混合型信息系統為S=(U，AT=C∪D)，鄰域半徑為δ和屬性子集A?C，屬性?a∈C-A關于屬性子集A的鄰域互信息熵屬性重要度定義為:

sig(a，A)=ηδ(A∪{a}，D)-ηδ(A，D)，

這里的ηδ(A，D)=φ(A，D)+φ(A，D).

傳統決策粗糙集下的屬性約簡主要集中于屬性子集的決策代價，而未考慮屬性子集的分類能力，因此接下來將本文提出的鄰域互信息熵屬性重要度引入決策代價屬性約簡中，提出一種新的改進屬性約簡算法.

算法1.基于鄰域互信息熵的混合型數據決策代價屬性約簡算法.

輸入：混合型信息系統S=(U，AT=C∪D)，鄰域半徑δ，決策代價.

輸出：屬性約簡結果red.

1.初始化red=?，ηδ(?，D)=0.

2.對于條件屬性集中的每個屬性ai∈C，其中i=1，2，…，|C|.計算屬性ai的鄰域互信息熵屬性重要度sig(ai，red)=ηδ(red∪{ai}，D)-ηδ(red，D)，

找出sig(ai，red)最大值對應的屬性，記為amax，并且red←red∪{amax}.

3.計算論域U在屬性集red下的鄰域粒化，并根據定義3得到整個論域U的決策代價Costred(U).

4.對于屬性?a∈C-red，計算其鄰域互信息熵的屬性重要度sig(a，red)，選擇C-red中屬性重要度最大的屬性amax，并且red′←red∪{amax}.

5.計算屬性集red′下整個論域U的決策代價Costred′(U)，若Costred′(U)≤Costred(U)，那么進行red←red′，并且重新返回步驟4，否則進入步驟6.

6.返回屬性約簡結果red.

算法1所示的是一種啟發式方法的屬性約簡算法，即通過決策代價函數和鄰域互信息熵屬性重要度一起進行信息系統屬性的搜索.該算法主要通過鄰域互信息熵去搜索出與決策屬性具有較高依賴度的屬性，并且選擇出的屬性與已選擇的屬性子集具有較高地獨立性，當該屬性能夠進一步降低論域的決策代價時，那么將該屬性添加至屬性約簡集中，重復上述流程直至完成最終的屬性搜索.算法1的計算量主要集中在鄰域互信息熵的計算和論域決策代價的計算，這些計算主要是針對對象鄰域類的計算，因此整個算法1的時間復雜度可表示為O(|C|2·|U|2).

4 實驗分析

為了進一步驗證所提出屬性約簡算法的有效性，本實驗從UCI機器學習公開數據集中選取了6個數據集，具體詳情如表1所示，所列舉的這些數據集均為離散型屬性和連續型屬性混合的類型，并且將連續型屬性歸一化至[0，1]區間.本實驗將所提出的屬性約簡算法與文獻[11]的決策代價屬性約簡算法和文獻[21]的鄰域粗糙熵屬性約簡算法分別進行實驗，通過屬性約簡的長度、約簡結果的分類精度、約簡結果的決策代價以及約簡用時4個方面來評價各個算法的優劣.

表1 實驗數據集

在本文所提出的算法中，鄰域半徑δ是一個很重要的參數，其取值的不同將會對最終的實驗結果產生很大的影響，本實驗借鑒其他學者的處理方式[11，18，21]，將鄰域半徑在一定區間內分別取值進行實驗，每個鄰域半徑都會得到對應的屬性約簡結果，將該結果利用支持向量機分類器(SVM)和樸素貝葉斯分類器(NB)分別進行分類精度評估，然后對多組數據集的結果進行比較，選取出最佳的鄰域半徑.圖2所示的是鄰域半徑在區間[0，0.3]下間隔取值得到的分類精度結果.綜合各個數據集的結果，可以發現當鄰域半徑取值為0.12左右時得到的屬性約簡結果分類精度較高，因此本實驗將鄰域半徑設置為0.12.另外本文的屬性約簡算法需要確定對象分類的決策代價，本實驗這里基于文獻[11]的代價關系，在0-1之間隨機進行選取.

圖2 各個數據集不同鄰域半徑下屬性約簡的分類精度結果

表2所示的是本文算法與文獻[11]中的算法和文獻[21]中的算法在各個數據集下屬性約簡結果的長度比較.觀察表2可以發現本文算法在除數據集Annealing以外有著更小的約簡長度，產生這一結果的主要原因是由于本文算法采用鄰域互信息熵去搜索屬性，每次選擇出的屬性與決策屬性具有很強的相關性，并且與已經搜索到的屬性之間也具有很強的獨立性，最終得到的屬性約簡結果包含了較少的冗余和不相關屬性，因此得到的約簡屬性要更少.而其余兩種屬性約簡算法，雖然是基于不同的評價策略去進行屬性的搜索，但是均未考慮屬性的獨立性因素，因此最終的屬性約簡結果包含了更多的屬性.

表2 屬性約簡的長度比較

表3和表4分別所示的本文算法與對比算法在每個數據集下屬性約簡結果的SVM分類精度和NB分類精度比較.對比表3和表4的結果，可以發現文獻[21]的屬性約簡算法在數據集Heart、Annealing和Sick下具有較高的SVM分類精度，本文算法和文獻[11]算法在其余數據集下具有較高的SVM分類精度；文獻[21]的屬性約簡算法在數據集Heart、German、Sick和Abalone下具有較高的NB分類精度，本文算法在其余數據集下具有較高的NB分類精度.綜合比較起來，文獻[21]的算法在較多的數據集下具有更高的分類精度，這主要是由于文獻[21]的算法利用鄰域粗糙信息熵作為啟發式函數進行屬性搜索，將屬性子集的分類性能作為屬性約簡的重點，因而得到的約簡結果分類性能更高，但是本文算法兼顧分類性能的同時，又考慮了屬性子集的決策代價，因而分類性能略低于文獻[21]的算法，但是本文算法在多數數據集下的分類精度與最高分類精度之間差距不是很大，因此說明本文算法得到的屬性約簡結果同樣具有較高的分類性能.

表3 各個算法屬性約簡的SVM分類精度比較(%)

表4 各個算法屬性約簡的NB分類精度比較(%)

表5所示的是本文算法與對比算法在每個數據集下屬性約簡結果的決策代價比較，對比表3和表4的結果可以發現，文獻[11]中的算法在數據集Horse、Heart和German下具有更低的決策代價，本文算法在數據集Annealing、Sick和Abalone下具有更低的決策代價.這主要是由于本文算法和文獻[11]的算法都通過考慮屬性子集的決策代價進行屬性約簡，因此本文算法和文獻[11]的算法有著較小的決策代價，而文獻[21]的鄰域粗糙熵屬性約簡未考慮屬性的決策代價，因此得到的屬性約簡結果具有更高的決策代價.

表5 各個算法屬性約簡的決策代價比較

屬性約簡的用時也是衡量算法性能的重要指標，圖3所示的是本文算法和對比算法在各個數據集下屬性約簡的用時比較結果.觀察圖3可以發現，文獻[11]中的屬性約簡算法有著最多的約簡用時，文獻[21]中的屬性約簡算法有著最少的約簡用時，本文算法的屬性約簡用時介于前兩種算法之間.這主要是由于計算屬性子集的決策代價具有較多的計算量，例如首先需要計算論域在屬性子集下的鄰域粒化，然后計算每個決策類的正區域、邊界域和負區域，最后依據區域的劃分計算最終的決策代價結果，而文獻[21]的算法只需進行鄰域粗糙熵的計算，因此計算量會少一些，而本文算法既進行了決策代價的部分計算也進行了鄰域互信息熵的計算，因此計算量介于二者之間.

圖3 各個算法屬性約簡的用時比較

綜合比較本文算法與兩種對比算法，可以證明本文算法在屬性約簡的長度、約簡結果的分類精度、約簡結果的決策代價以及約簡用時4個方面上具有整體更優的屬性約簡性能.

5 總 結

屬性約簡是粗糙集理論的核心研究內容.傳統的決策粗糙集模型通過決策代價的視角進行數據集的屬性約簡，使得選擇出的屬性子集在進行決策劃分時具有最小的分類代價，然而這種屬性約簡方法未考慮屬性子集的分類性能，并且已有的算法在考慮分類性能的同時，未考慮選擇出屬性的獨立性，因而所得到的屬性約簡結果具有較高的冗余性，針對這一問題，提出一種基于鄰域互信息熵的混合型數據決策代價屬性約簡算法，該算法在考慮屬性約簡結果的決策代價同時，利用鄰域互信息熵去選擇依賴度高且獨立性強的屬性，使得最終的屬性約簡結果具有更高的優越性，仿真實驗證明了算法的有效性.在接下來的研究中，我們將進一步探索動態混合數據環境下的屬性約簡問題.