混合型數(shù)據(jù)的鄰域條件互信息熵屬性約簡算法

蘭海波

中國氣象局公共氣象服務(wù)中心，北京 100081

0 引言

在大數(shù)據(jù)應(yīng)用情景下，具有噪聲、無關(guān)或冗余特征的數(shù)據(jù)集對數(shù)據(jù)挖掘、知識發(fā)現(xiàn)和模式識別產(chǎn)生了巨大的挑戰(zhàn)[1-2]。如何從數(shù)據(jù)集所有屬性中選擇出最優(yōu)屬性子集是各種學(xué)習(xí)任務(wù)的重要研究課題。屬性約簡是粗糙集理論的重要研究分支，其主要目的是消除信息系統(tǒng)中不相關(guān)的屬性，降低數(shù)據(jù)維度并提高數(shù)據(jù)知識發(fā)現(xiàn)性能[3]。

基于粗糙集理論，學(xué)者們提出了多種屬性約簡算法。例如，Hu Q H等人[4]基于鄰域粗糙集，將鄰域依賴度作為數(shù)值型信息系統(tǒng)的屬性評估，提出一種屬性約簡算法；Pang Q Q等人[5]提出一種基于鄰域區(qū)分度的半監(jiān)督屬性約簡算法；在Pang Q Q等人的基礎(chǔ)上，Hu M等人[6]在鄰域粗糙集下提出權(quán)重鄰域依賴度，并構(gòu)造一種改進(jìn)的屬性約簡算法；Shu W H等人[7]對鄰域粗糙集進(jìn)行增量式構(gòu)造，提出一種高效的增量式屬性約簡算法；盛魁等人[8]對鄰域區(qū)分度進(jìn)行增量式構(gòu)造，提出一種新的屬性約簡算法；姚晟等人[9]將這些屬性約簡算法進(jìn)一步拓展，提出非平衡數(shù)據(jù)下不完備混合型信息系統(tǒng)的屬性約簡算法。另外，部分學(xué)者采用其他類型的粗糙集模型進(jìn)行屬性約簡算法的設(shè)計(jì)，例如，Wang C Z等人[10]在模糊粗糙集下提出自信息，并進(jìn)行屬性約簡算法的設(shè)計(jì)；Yuan Z等人[11]利用模糊粗糙集提出混合型數(shù)據(jù)的非監(jiān)督屬性約簡算法；欒雨雨等人[12]利用混沌離散粒子群提出一種新的粗糙集屬性約簡算法；Hu M等人[13]利用K近鄰粗糙集模型提出一種新穎的屬性約簡算法；桑彬彬等人[14]利用優(yōu)勢粗糙集構(gòu)造出一種屬性約簡算法。

利用互信息熵進(jìn)行屬性約簡近年來受到了學(xué)者們越來越多的關(guān)注。熊菊霞等人[15]提出鄰域互信息熵的混合型數(shù)據(jù)屬性約簡算法，陳帥等人[16-17]提出鄰域互補(bǔ)信息度量的屬性約簡算法，姚晟等人[18]提出鄰域互信息熵的非單調(diào)性屬性約簡算法。然而，這些屬性約簡算法大多沒有考慮屬性之間的相互作用，即在進(jìn)行屬性約簡的搜索過程中，選擇重要度高的屬性作為候選屬性，而沒有考慮所選屬性的獨(dú)立性，新選擇的屬性與已有的屬性可能存在一定的依賴關(guān)系，這使得最終的屬性約簡結(jié)果可能存在一定的冗余性[19]?；バ畔㈧嘏c條件互信息熵是評估隨機(jī)變量獨(dú)立性的一種重要度量方法[15]，本文將利用這兩種度量方法提出一種新的屬性約簡算法。同時，實(shí)際應(yīng)用環(huán)境下的數(shù)據(jù)集往往是數(shù)值型和離散型混合類型，例如對于醫(yī)療信息系統(tǒng)，患者的性別、聽覺、視覺、嗅覺等都是離散型的屬性，身高、體重和血液檢查中各種酶的指標(biāo)都是數(shù)值型的屬性，因此本文將研究混合型信息系統(tǒng)下的屬性約簡問題。

首先，本文在鄰域粗糙集模型的基礎(chǔ)上，構(gòu)造出混合型信息系統(tǒng)下的鄰域信息熵模型，并進(jìn)一步提出混合型鄰域互信息熵模型和混合型鄰域條件互信息熵模型；然后，將提出的混合型鄰域互信息熵和混合型鄰域條件互信息熵用于混合型信息系統(tǒng)屬性之間的相關(guān)性度量；最后，將這兩種熵度量作為啟發(fā)式函數(shù)設(shè)計(jì)出一種屬性約簡算法，并通過6個UCI數(shù)據(jù)集的屬性約簡實(shí)驗(yàn)，證明了本文的屬性約簡算法通過考慮屬性之間的依賴性可以提高約簡結(jié)果的分類性能，同時本文算法也具有較小的屬性約簡耗時。

1 基本理論

將鄰域信息系統(tǒng)表示為二元組NIS=(U,AT=C∪D)，其中，U={x1,x2,… ,xn}是一個非空有限對象或樣本的集合，稱之為論域；AT=C∪D是一個非空有限屬性或特征的集合，稱之為屬性全集，其包含兩個部分，分別稱之為條件屬性集C和決策屬性集D。

在鄰域信息系統(tǒng)NIS=(U,AT=C∪D)中，通常使用距離度量來評估信息系統(tǒng)中對象之間的相似性，對于屬性子集A={a1,a1,… ,am}?C，對象x,y∈U的距離度量一般被定義為：

其中，ai(x)表示對象x在屬性ai下的屬性值，a i(y)表示對象y在屬性ai下的屬性值，λ的取值范圍一般為(1,2,…, +∞)。基于該度量函數(shù)，可以在鄰域信息系統(tǒng)下構(gòu)造出鄰域關(guān)系。

定義1 [4]：設(shè)鄰域信息系統(tǒng)表示為NIS=(U,AT=C∪D)，則屬性子集A?C確定的鄰域關(guān)系如下。

其中，δ被稱為鄰域關(guān)系的鄰域半徑。鄰域關(guān)系滿足自反性和對稱性，但不一定滿足傳遞性。利用鄰域關(guān)系可以得到鄰域信息系統(tǒng)中每個對象的鄰域類δA(x)：

定義2 [4]：設(shè)鄰域信息系統(tǒng)表示為NIS=(U,AT=C∪D)，屬性子集A?C確定的鄰域關(guān)系為NRδ(A)，則對象集X?U在鄰域關(guān)系NRδ(A)下的鄰域下近似集和鄰域上近似集分別定義如下。

信息熵模型是評估信息系統(tǒng)不確定性的一種重要方法，Hu Q H等人[20]在鄰域信息系統(tǒng)下提出了一種鄰域熵模型。

定義3 [2 0]：設(shè)鄰域信息系統(tǒng)表示為NIS=(U,AT=C∪D)，屬性子集A?C確定的鄰域關(guān)系為NRδ(A)，對象x∈U在NRδ(A)下的鄰域類為δA(x)，那么鄰域關(guān)系NRδ(A)確定的鄰域熵NEδ(A)定義如下。

Hu Q H等人[20]提出的鄰域熵模型在鄰域粗糙集的不確定性度量和屬性約簡方面發(fā)揮了重要作用，使得鄰域熵模型成為鄰域粗糙集的重要研究內(nèi)容。

2 混合型信息系統(tǒng)的鄰域條件互信息熵模型

然而，實(shí)際應(yīng)用中的數(shù)據(jù)包含數(shù)值型和標(biāo)記型，傳統(tǒng)的鄰域粗糙集模型僅適用于數(shù)值型，針對這一局限性，盛魁等人[8]提出了基于混合型信息系統(tǒng)的鄰域粗糙集模型。

定義4[8]：設(shè)混合型信息系統(tǒng)表示為MIS=(U,AT=C∪D)，其中C=C n∪Cm且C n∩Cm=?，Cn為條件屬性集中的數(shù)值型屬性子集，Cm為條件屬性集中的標(biāo)記型屬性子集。對于A=An∪Am，其中An?Cn、Am?Cm，那么A?C確定的混合鄰域關(guān)系如下。

同時，對于?x∈U，在混合鄰域關(guān)系MNRδ(A)下的鄰域類δA*(x)定義為：

基于混合信息系統(tǒng)的混合鄰域關(guān)系和鄰域類，盛魁等人[8]進(jìn)一步提出了一種改進(jìn)的鄰域粗糙集模型。

定義5[8]：設(shè)混合型信息系統(tǒng)表示為MIS=(U,AT=C∪D)，A=An∪Am確定的混合鄰域關(guān)系為MNRδ(A)，那么對象集X?U在MNRδ(A)下的鄰域下近似集和鄰域上近似集分別定義如下。

在盛魁等人[8]提出的混合型信息系統(tǒng)鄰域粗糙集基礎(chǔ)上，下面將進(jìn)一步提出混合信息系統(tǒng)的鄰域熵、鄰域聯(lián)合熵、鄰域條件熵以及鄰域條件互信息熵模型等，進(jìn)一步完善鄰域粗糙集模型下的信息熵理論。

定義6：設(shè)混合型信息系統(tǒng)表示為MIS=(U,AT=C∪D)，A=An∪Am確 定的混合鄰域關(guān)系為MNRδ(A)，對象x∈U在MNRδ(A)下的鄰域類為δA*(x)，那么混合鄰域關(guān)系MNRδ(A)確定的混合鄰域熵MNEδ(A)定義如下。

其中，對象ix的鄰域不確定性構(gòu)成了對象集的鄰域熵（即平均不確定性），定義為。

定義7：設(shè)混合型信息系統(tǒng)表示為MIS=(U,AT=C∪D)，屬性子集A,B?C，那么A和B的混合鄰域聯(lián)合熵定義如下。

定義8：設(shè)混合型信息系統(tǒng)表示為MIS=(U,AT=C∪D)，屬性子集A,B?C，那么B關(guān)于A的混合鄰域條件熵定義如下。

根據(jù)定義6～定義8，混合鄰域條件熵具有如下性質(zhì)。

性質(zhì)1：設(shè)混合型信息系統(tǒng)表示為MIS=(U,AT=C∪D)，屬性子集A,B?C，那么可以得到式（14）。

證明：根據(jù)定義6和定義7，可以得到式（15）。

則MNEδ(B|A)=MNEδ(A,B)-MNEδ(A)成立。

定義8中的混合鄰域條件熵與信息論中的條件熵類似，反映了引入屬性子集A后B中剩余的不確定性量，混合鄰域條件熵可以通過A和B的聯(lián)合不確定性與A的不確定性來計(jì)算。

定義9：設(shè)混合型信息系統(tǒng)表示為MIS=(U,AT=C∪D)，屬性子集A,B?C，那么A和B的混合鄰域互信息熵定義為如下。

混合鄰域熵、混合鄰域條件熵和混合鄰域互信息熵具有如下關(guān)系。

性質(zhì)2：設(shè)混合型信息系統(tǒng)表示為MIS=(U,AT=C∪D)，屬性子集A,B?C，那么可以得到如下計(jì)算式。

證明：根據(jù)定義9，可以得到式（17）。

則①成立。

根據(jù)定義6和定義7可以得到：

則②成立。

根據(jù)定義6和定義8可以得到：

同理，可以得到：

則③成立。

通過性質(zhì)2可以看出屬性子集A和B的互信息量與B和A的互信息量是一致的。屬性子集A和B混合鄰域互信息熵可以表示為各自的混合鄰域熵值去除A和B后的混合鄰域聯(lián)合熵值。

與信息論理論類似，接下來進(jìn)一步提出混合鄰域條件互信息熵。

定義10：設(shè)混合型信息系統(tǒng)表示為MIS=(U,AT=C∪D)，屬性子集A1,A2,B?C，那么在屬性子集B下，A1和A2的混合鄰域條件互信息熵定義為如下。

混合鄰域條件互信息熵具有如下性質(zhì)。

性質(zhì)3：設(shè)混合型信息系統(tǒng)表示為MIS=(U,AT=C∪D)，屬性子集A1,A2,B?C，那么可以得到式（22）。

證明：根據(jù)定義6和定義7，可以得到式（23）。

因此，滿足MNEδ(A1;A2|B)=MNEδ(A1,B)+MNEδ(A2,B)-MNEδ(A1,A2,B)-MNEδ（B）。

性質(zhì)3表明，混合鄰域條件互信息熵可通過混合鄰域熵和混合鄰域聯(lián)合熵計(jì)算得到。

性質(zhì)4：設(shè)混合型信息系統(tǒng)表示為MIS=(U,AT=C∪D) ，屬性子集A1,A2,B?C，那么可以得到式（24）。

證明：根據(jù)混合鄰域條件互信息熵的定義可以直接得到。

根據(jù)性質(zhì)3可以看出，當(dāng)屬性子集A1和A2相互獨(dú)立時，混合鄰域條件互信息熵的值為0。這表明混合鄰域條件互信息熵可以展示給定條件下屬性子集之間的依賴程度。將混合鄰域條件互信息熵作為信息系統(tǒng)的屬性子集評估函數(shù)，可以進(jìn)行混合型信息系統(tǒng)的屬性約簡。

3 屬性約簡算法

本節(jié)將利用混合鄰域條件互信息熵評估信息系統(tǒng)屬性之間的依賴度和獨(dú)立性，并構(gòu)造出一種混合型信息系統(tǒng)的屬性約簡算法。

屬性約簡旨在尋找屬性全集中與分類強(qiáng)相關(guān)的屬性子集，因此屬性約簡集中的屬性與信息系統(tǒng)的類屬性具有強(qiáng)相關(guān)性。由于互信息熵展示了屬性之間的相關(guān)性，因此將提出的混合型鄰域互信息熵和混合型鄰域條件互信息熵用于混合型信息系統(tǒng)屬性之間的相關(guān)性度量。

定義11：設(shè)混合型信息系統(tǒng)表示為MIS=(U,AT=C∪D)，屬性子集A?C，關(guān)于決策屬性集D的相關(guān)度φD(A)定義如下。

其中，MNEδ(A;D)，[xi]D為對象xi在決策屬性D下的等價類。

定義12：設(shè)混合型信息系統(tǒng)表示為MIS=(U,AT=C∪D)，屬性子集A?C，屬性子集B?(C-A)在屬性子集A下關(guān)于決策屬性D的相關(guān)度φD(B|A)定義如下。

利用混合型鄰域互信息熵和混合型鄰域條件互信息熵對混合型信息系統(tǒng)進(jìn)行屬性選擇，可以進(jìn)一步設(shè)計(jì)出一種屬性約簡算法。

算法1：基于鄰域條件互信息熵的混合型信息系統(tǒng)屬性約簡算法

輸入：混合型信息系統(tǒng)MIS=(U,AT=C∪D)，鄰域半徑δ。

輸出：屬性約簡結(jié)果red。

1.設(shè)置屬性約簡初始結(jié)果red=?。

2.對于條件屬性集C中的每個屬性?a∈C，計(jì)算屬性a與決策屬性集D的相關(guān)度φD({a})。

3.找出2中相關(guān)度最大的屬性amax，即amax=。

4. 令red ←red ∪{amax}，C′←C-{amax}。

5.對于屬性b C′? ∈ ，計(jì)算屬性b在屬性約簡集red 下關(guān)于決策屬性D的相關(guān)φD(b{ }| red) 度。

6.找出5中相關(guān)度最大的屬性bmax，即bmax=。

7.令red =red ∪{bmax}，C′←C′-{bmax}，并利用分類器對屬性約簡結(jié)果red 進(jìn)行分類精度計(jì)算，記錄其分類精度結(jié)果。

8.重復(fù)5～7，直至C′=?。

9.找出所有屬性約簡中分類精度最大的屬性約簡結(jié)果redbest。

10.返回屬性約簡集redbest。

在算法1中，主要計(jì)算量集中在屬性集的鄰域條件互信息熵上，而鄰域條件互信息熵的計(jì)算主要是針對對象鄰域類的計(jì)算，因此整個算法1的時間復(fù)雜度為O(|AT|2·| U|2)。

4 實(shí)驗(yàn)分析

為了驗(yàn)證本文提出的基于鄰域條件互信息熵的屬性約簡算法的有效性，下面使用6個數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)分析，這些數(shù)據(jù)集見表1。這些數(shù)據(jù)集選擇自UCI公共數(shù)據(jù)集，這些數(shù)據(jù)集均為混合型類型，適用于本文所提算法。

表1 實(shí)驗(yàn)數(shù)據(jù)集

同時本文選擇3種同類型的屬性約簡算法進(jìn)行實(shí)驗(yàn)，分別為參考文獻(xiàn)[6]提出的屬性約簡算法（對比算法1），參考文獻(xiàn)[10]提出的屬性約簡算法（對比算法2）和參考文獻(xiàn)[19]提出的屬性約簡算法（對比算法3）。

所有算法的屬性約簡結(jié)果通過支持向量機(jī)（support vector machine，SVM）分類器和樸素貝葉斯（naive Bayesian，NB）分類器計(jì)算其分類精度，對每個數(shù)據(jù)集的約簡結(jié)果進(jìn)行20次十折交叉驗(yàn)證，并將平均值作為最終的分類精度結(jié)果。本實(shí)驗(yàn)在MATLAB 2018b上對所有屬性約簡算法進(jìn)行實(shí)現(xiàn)，所有實(shí)驗(yàn)都在Intel(R)Core(TM)i3-7100上進(jìn)行，CPU時鐘速率為3.90 GHz，內(nèi)存為8 GB。

在本文提出的屬性約簡算法中，不同的鄰域半徑取值對算法的屬性約簡結(jié)果將產(chǎn)生很大的影響。在參考文獻(xiàn)[4-8,19]中，學(xué)者們通過大量實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)鄰域半徑過小時，其屬性約簡的長度較小，并且分類精度也較??；當(dāng)鄰域半徑過大時，其分類精度不會更高。對于數(shù)據(jù)集歸一化為0和1之間的值，當(dāng)鄰域半徑為0.15左右時，其屬性約簡長度不是很大且分類精度最高，因此本實(shí)驗(yàn)選擇鄰域半徑為0.15進(jìn)行后續(xù)實(shí)驗(yàn)。

4.1 分類精度結(jié)果對比

分類性能是驗(yàn)證屬性約簡算法質(zhì)量最有效和最直接的方法，其中，通常利用分類精度來衡量算法分類性能。表2和表3分別展示了本文屬性約簡算法與3種對比算法在SVM分類器和NB分類器下的平均分類精度結(jié)果，其結(jié)果使用“平均值±標(biāo)準(zhǔn)差”的形式表示。

對比表2和表3的實(shí)驗(yàn)結(jié)果，可以得到如下結(jié)論。

表2 SVM 分類精度結(jié)果

表3 NB 分類精度結(jié)果

● 與原始數(shù)據(jù)集的分類精度相比，3種對比算法和本文算法的SVM分類精度分別提高了6%、8%、5%和11%，NB分類精度分別提高了8%、6%、9%和12%。

● 在大部分?jǐn)?shù)據(jù)集下，本文的屬性約簡算法具有更高的分類精度，例如對于利用SVM分類器計(jì)算得到的分類精度，本文算法在Cylinder、Credit和Segment等數(shù)據(jù)集上更高；對于利用NB分類器計(jì)算得到的分類精度，本文算法在German、Segment和Sick等數(shù)據(jù)集上更高。

● 同時本文算法在SVM分類器和NB分類器下的分類精度標(biāo)準(zhǔn)差大多小于或等于其余對比算法。從統(tǒng)計(jì)學(xué)的角度來看，本文算法的穩(wěn)定性更高，這主要是由于本文算法通過鄰域條件互信息熵選擇屬性，降低了最終約簡結(jié)果中的冗余屬性，從而提高了最終約簡結(jié)果的分類性能。

4.2 屬性約簡長度對比

對于屬性約簡算法來說，屬性約簡結(jié)果的長度也是評估算法有效性的一項(xiàng)重要指標(biāo)，表4展示了本文算法與3種對比算法的屬性約簡長度的對比結(jié)果。從表4可以看出，本文算法在各個數(shù)據(jù)集上的平均屬性約簡集長度為7.7，均低于其余3種算法，說明本文算法能夠選擇出規(guī)模更小的屬性約簡集。

表4 屬性約簡長度

4.3 屬性約簡效率對比

此外，算法的效率也是評估算法有效性和實(shí)用性的又一重要指標(biāo)，圖1給出了各個屬性約簡算法對每個數(shù)據(jù)集進(jìn)行屬性約簡的用時。由圖1可以看出，本文算法和對比算法1的用時均小于其余對比算法，這再一次證明了本文算法的有效性和優(yōu)越性。

圖1 不同算法運(yùn)行時間

4.4 不同鄰域半徑分類精度結(jié)果對比

為了進(jìn)一步對比本文算法和對比算法在不同鄰域半徑下屬性約簡的分類精度結(jié)果，下面將鄰域半徑區(qū)間[0.02,0.4]以0.02為間隔，分別取值對各個算法進(jìn)行屬性約簡實(shí)驗(yàn)，并計(jì)算出每個鄰域半徑屬性約簡結(jié)果的分類精度。圖2～圖4展示出了部分?jǐn)?shù)據(jù)集在不同鄰域半徑下屬性約簡的分類精度結(jié)果。由圖2～圖4可以發(fā)現(xiàn)，在不同鄰域半徑下，本文算法的屬性約簡分類精度整體上高于其余3種對比算法，因此對于不同鄰域半徑，本文算法仍然具有更高的屬性約簡性能。

圖2 Cylinder 實(shí)驗(yàn)結(jié)果

圖4 Sick 實(shí)驗(yàn)結(jié)果

綜合各個環(huán)節(jié)的實(shí)驗(yàn)結(jié)果，與其他同類型屬性約簡算法相比，本文提出的屬性約簡算法具有更顯著的有效性和優(yōu)越性。

5 結(jié)束語

針對目前基于粗糙集理論的屬性約簡算法沒有考慮屬性之間的相關(guān)性和依賴性，本文提出一種基于鄰域條件互信息熵的混合型信息系統(tǒng)屬性約簡算法。文中首先在傳統(tǒng)鄰域熵的基礎(chǔ)上進(jìn)一步提出了混合型鄰域互信息熵模型和混合型鄰域條件互信息熵模型，然后利用這兩種熵模型進(jìn)行混合型信息系統(tǒng)的屬性相關(guān)性度量，最后設(shè)計(jì)出一種新的啟發(fā)式屬性約簡算法，基于UCI數(shù)據(jù)集的屬性約簡實(shí)驗(yàn)表明，所提算法具有更高的屬性約簡性能。在將來的工作中，筆者將進(jìn)一步研究鄰域互信息熵模型和鄰域條件互信息熵模型的增量式屬性約簡問題。

圖3 Credit 實(shí)驗(yàn)結(jié)果