基于鄰域組合熵的屬性約簡(jiǎn)算法

王 光 瓊

(四川文理學(xué)院智能制造學(xué)院 四川 達(dá)州 635006) (達(dá)州智能制造產(chǎn)業(yè)技術(shù)研究院 四川 達(dá)州 635006)

0 引 言

粗糙集作為一種處理不確定性信息的有效數(shù)學(xué)工具，已經(jīng)廣泛應(yīng)用于機(jī)器學(xué)習(xí)、知識(shí)發(fā)現(xiàn)和規(guī)則提取等領(lǐng)域[1-3]。經(jīng)典粗糙集以完備信息系統(tǒng)為研究對(duì)象，通過嚴(yán)格的等價(jià)關(guān)系對(duì)論域進(jìn)行劃分，要求所有屬性值都是離散型的。然而，實(shí)際應(yīng)用中，來自教育、醫(yī)療和金融等領(lǐng)域的數(shù)值型數(shù)據(jù)很多，經(jīng)典粗糙集不能直接處理屬性值有數(shù)值型數(shù)據(jù)的信息系統(tǒng)，為了解決此問題，Lin[4]對(duì)等價(jià)關(guān)系進(jìn)行擴(kuò)展，提出了鄰域關(guān)系。鄰域關(guān)系能夠處理同時(shí)有名義性和數(shù)值型數(shù)據(jù)的混合型信息系統(tǒng)，因此基于鄰域關(guān)系的鄰域粗糙集模型得到廣泛應(yīng)用[5-6]。

屬性約簡(jiǎn)是粗糙集領(lǐng)域中研究的關(guān)鍵問題之一，目的是在不影響系統(tǒng)分類能力的前提下剔除冗余的條件屬性。為了對(duì)信息系統(tǒng)進(jìn)行屬性約簡(jiǎn)，從信息論的角度出發(fā)，文獻(xiàn)[7]提出了基于信息熵的決策表約簡(jiǎn)算法;文獻(xiàn)[8]提出了基于條件信息熵的決策表約簡(jiǎn)；文獻(xiàn)[9]提出了基于邊界域的條件信息熵屬性約簡(jiǎn)算法。以上算法主要處理符號(hào)型數(shù)據(jù)，不能直接處理數(shù)值型數(shù)據(jù)或者符號(hào)性和數(shù)值型混合的數(shù)據(jù)。為了解決此問題，借助鄰域關(guān)系可以處理混合數(shù)據(jù)的特點(diǎn)，文獻(xiàn)[10]提出了一種基于鄰域熵的屬性約簡(jiǎn)算法；文獻(xiàn)[11]提出了鄰域決策錯(cuò)誤率的局部約簡(jiǎn)算法；文獻(xiàn)[12]提出了基于鄰域組合測(cè)度的屬性約簡(jiǎn)算法。此外，在粗糙集理論中，不確定性分為知識(shí)不確定性和集合不確定性。目前提出的屬性重要度度量大多僅考慮知識(shí)不確定性或者集合不確定性，同時(shí)考慮兩者的不確定性來定義屬性重要度度量進(jìn)而設(shè)計(jì)屬性約簡(jiǎn)算法是研究的熱點(diǎn)。

本文以鄰域信息系統(tǒng)為研究對(duì)象，以鄰域關(guān)系為基礎(chǔ)，為了描述知識(shí)對(duì)系統(tǒng)的劃分能力，首先定義了鄰域條件熵。為了從知識(shí)不確定性和集合不確定性兩個(gè)方面來綜合度量屬性的重要度，將鄰域條件熵與鄰域近似精度結(jié)合，定義了屬性重要度度量——鄰域組合熵，并提出了基于鄰域組合熵的屬性約簡(jiǎn)算法。該算法可以處理離散型和數(shù)值型并存的不完備鄰域信息系統(tǒng)。最后實(shí)驗(yàn)驗(yàn)證了本文所提算法的有效性。

1 相關(guān)概念

特別地，若A=C∪D，C為條件屬性集合，D為決策屬性集合，則稱DNI=(U,C∪D,V,f,δ)為鄰域決策信息系統(tǒng)。若用“*”表示缺失值，?a∈A，存在f(x,a)=*，則稱NI為不完備信息鄰域信息系統(tǒng)。

定義2設(shè)鄰域信息系統(tǒng)NI=(U,A,V,f,δ)，定義屬性子集B?C上的δ的鄰域關(guān)系為：

NRδ(B)={(x,y)∈U×U|DB(x,y)≤δ}

(1)

式中：DB(x,y)表示對(duì)象x和y在屬性子集B上的距離。顯然，鄰域關(guān)系滿足自反性和對(duì)稱性。為了可以處理離散型和數(shù)值型并存的不完備鄰域信息系統(tǒng)，本文中的距離采用文獻(xiàn)[13]中的距離函數(shù)。設(shè)屬性子集B={a1,a2,…,am}，距離度量為：

式中：1≤l≤M。

當(dāng)al為名義性屬性時(shí)：

當(dāng)al為數(shù)值型屬性時(shí)：

定義3設(shè)鄰域信息系統(tǒng)NI=(U,A,V,f,δ)，?x∈U，x關(guān)于B的鄰域?yàn)椋?/p>

(2)

性質(zhì)1設(shè)鄰域信息系統(tǒng)NI=(U,A,V,f,δ)，?x∈U，對(duì)于P,Q?A，有：

定義4設(shè)鄰域信息系統(tǒng)NI=(U,A,V,f,δ)，對(duì)象集X?U關(guān)于屬性子集B?C的上、下近似和邊界域分別定義如下：

(1)X的上近似：

(3)

鄰域近似精度刻畫了信息系統(tǒng)中對(duì)象集合的不確定性，其值一般隨著屬性子集的增大而增大，因此成為一種重要的不確定度量工具。然而，鄰域近似精度并不具有嚴(yán)格的單調(diào)性，也存在屬性子集增大，其值不變的情況。

2 鄰域條件熵以及鄰域組合熵

為了從知識(shí)不確定性和集合不確定性兩個(gè)方面來度量屬性重要度，本節(jié)定義了鄰域條件熵，并結(jié)合鄰域近似精度定義了鄰域組合信息熵。

(4)

信息熵KN(B)反映了屬性子集B對(duì)系統(tǒng)論域中對(duì)象的區(qū)分能力，KN(B)的值越大，屬性子集的區(qū)分能力越好。

定義7設(shè)鄰域信息系統(tǒng)NI=(U,A,V,f,δ)，P,Q?C，知識(shí)Q關(guān)于P的鄰域條件熵定義為：

NE(Q|P)=NE(Q∪P)-NE(P)

(5)

鄰域條件熵NE(Q|P)反映了屬性集合P對(duì)于屬性集合Q的不確定性。對(duì)于決策鄰域信息系統(tǒng)，NE(D|P)則反映了屬性集P對(duì)于決策屬性D的不確定性。

證明:NE(Q|P)=NE(Q∪P)-NE(P)=

定理2(單調(diào)性) 設(shè)鄰域信息系統(tǒng)NI=(U,A,V,f,δ)，P,Q?C，P?Q，則有NE(D|Q)≤NE(D|P)。

證明:NE(D|P)-NE(D|Q)=

定理2表明，鄰域條件熵具有單調(diào)性，熵值隨著條件屬性集合的增大而減小，條件信息熵越小，則系統(tǒng)協(xié)調(diào)程度越高。因此在屬性約簡(jiǎn)中，鄰域條件熵可以作為屬性重要度度量的一個(gè)重要因素。

其實(shí)，屬性重要度的度量主要有基于代數(shù)定義和基于信息定義的方法[14]。兩種方法具有互補(bǔ)的特性，基于代數(shù)定義主要考慮的是屬性對(duì)論域中確定分類子集的影響；基于信息定義主要考慮的是屬性對(duì)于論域中不確定分類子集的影響。為了同時(shí)從基于代數(shù)定義和基于信息定義兩個(gè)方面衡量屬性重要度，結(jié)合鄰域近似精度和鄰域條件熵定義新的鄰域組合熵。

(6)

鄰域近似精度從集合的角度考慮不確定性，鄰域條件熵從知識(shí)的角度考慮不確定性，因此鄰域組合熵同時(shí)考慮了集合和知識(shí)的不確定性，對(duì)不確定性的刻畫更加全面。

定理3表明，鄰域組合熵具有單調(diào)性，熵值隨著條件屬性集合的增大而增大。因此，可以以鄰域組合熵來度量屬性的重要度，設(shè)計(jì)基于鄰域組合熵的屬性約簡(jiǎn)算法。

定義9設(shè)鄰域決策信息系統(tǒng)NI=(U,C∪D,V,f,δ)，?B?C，對(duì)于屬性a∈C-B，a相對(duì)于B的重要性定義為：

(7)

定義10設(shè)鄰域決策信息系統(tǒng)NI=(U,C∪D,V,f,δ)，?B?C，若滿足如下條件：

則稱屬性子集B為C相對(duì)于決策屬性的一個(gè)相對(duì)約簡(jiǎn)。

定義11對(duì)于一個(gè)鄰域信息系統(tǒng)NI=(U,C∪D,V,f,δ)，相對(duì)于決策屬性D，C中所有必要的屬性組成的集合稱為C相對(duì)于D的核，簡(jiǎn)稱相對(duì)核。

3 基于鄰域組合熵的屬性約簡(jiǎn)算法(ARNCE)

本節(jié)以鄰域組合熵為啟發(fā)信息，提出了一種鄰域信息系統(tǒng)的屬性約簡(jiǎn)算法。

算法1為計(jì)算鄰域組合熵的算法。

算法1鄰域組合熵的計(jì)算

Step 1 計(jì)算鄰域條件熵；

foriton

計(jì)算p(xi),

Endfor

計(jì)算鄰域信息熵NE(B)；

計(jì)算鄰域條件熵NE(D|B)；

Step 2 計(jì)算鄰域近似精度；

forjtom，

Endfor

算法2為基于鄰域組合熵的屬性約簡(jiǎn)算法。算法思想：以空集合為起點(diǎn)，以鄰域組合熵對(duì)屬性重要度的度量作為啟發(fā)信息，每次選擇重要度最大的屬性加入約簡(jiǎn)集，直到所有未被選擇的屬性都是不重要的。

算法2基于鄰域組合熵的屬性約簡(jiǎn)算法

輸出：約簡(jiǎn)集合RED。

Step 1 初始化RED=?；

Step 3 Do

對(duì)于?ai∈C-RED，根據(jù)算法1計(jì)算Sig(ai,RED,D)，

If

Sig(amax,RED,D)=max{Sig(ai,RED,D)|ai∈C-RED}

RED=RED∪{amax}，

Endif

UntilSig(amax,RED,D)=0

Step 4 返回RED；

4 實(shí)驗(yàn)結(jié)果分析

為了驗(yàn)證本文所提算法處理鄰域信息系統(tǒng)的可行性，將本文的算法與以下幾種算法分別從屬性約簡(jiǎn)數(shù)量和分類精度方面進(jìn)行比較。

1) 基于鄰域依賴度的屬性約簡(jiǎn)算法(DNFS)[15];

2) 基于鄰域條件熵的屬性約簡(jiǎn)算法(ARCE)[16];

3) 基于鄰域組合測(cè)度的屬性約簡(jiǎn)算法(ARNCM)[12]。

由于在屬性約簡(jiǎn)時(shí)算法DNFS只考慮依賴度，算法ARCE只考慮了條件熵，而算法ARNCM同時(shí)考慮了粒度測(cè)度和近似精度。本文算法同時(shí)考慮了信息熵和近似精度，所以算法ARNCM和本文算法的時(shí)間復(fù)雜度要高于DNFS和ARCE。本節(jié)主要比較各算法約簡(jiǎn)后的屬性約簡(jiǎn)數(shù)量和分類精度。

本文算法采用Java語言編程實(shí)現(xiàn)，硬件環(huán)境為：intel處理器3.7 GHz，內(nèi)存2 GB。

選用UCI中的6個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，其中4個(gè)完備數(shù)據(jù)集，2個(gè)不完備數(shù)據(jù)集。在屬性類型方面，數(shù)據(jù)集Heart、Hepatitis的屬性為混合型，數(shù)據(jù)集Zoo、Soybean的屬性為符號(hào)型，數(shù)據(jù)集Wdbc、Sonar的屬性為數(shù)值型，數(shù)據(jù)集的具體信息見表1。為了消除各屬性量綱不一致對(duì)鄰域計(jì)算的影響，在實(shí)驗(yàn)前，對(duì)數(shù)據(jù)集中所有的數(shù)值型屬性進(jìn)行標(biāo)準(zhǔn)化處理，統(tǒng)一標(biāo)準(zhǔn)化到[0,1]區(qū)間。鄰域參數(shù)設(shè)置為δ=0.15。

表1 UCI數(shù)據(jù)集中的六個(gè)數(shù)據(jù)集

首先比較各算法屬性約簡(jiǎn)之后的屬性約簡(jiǎn)集大小，實(shí)驗(yàn)結(jié)果如表2所示。由表2可知，所有算法都能有效地對(duì)數(shù)據(jù)集進(jìn)行屬性約簡(jiǎn)。算法ARNCE與算法DNFS、ARCE相比，在所有數(shù)據(jù)集上都獲得了相等或者較小的屬性約簡(jiǎn)集。算法ARNCE和算法ARNCM屬性約簡(jiǎn)集大小較為接近，通過對(duì)6個(gè)數(shù)據(jù)集的屬性約簡(jiǎn)集大小進(jìn)行平均計(jì)算，算法ARNCM的平均屬性約簡(jiǎn)集大小為6.66，算法ARNCE的平均屬性約簡(jiǎn)集大小為6.33?？傮w而言，相比較于另外三種屬性約簡(jiǎn)算法，本文所提算法ARNCE能夠獲得約簡(jiǎn)集較小的屬性約簡(jiǎn)結(jié)果。

表2 不同算法屬性約簡(jiǎn)后屬性約簡(jiǎn)集大小

為了進(jìn)一步驗(yàn)證屬性約簡(jiǎn)算法的有效性和分類能力，實(shí)驗(yàn)中通過支持向量機(jī)(SVM)和決策樹(C4.5)兩種分類器，采用十折交叉驗(yàn)證的方法，比較各算法約簡(jiǎn)之后的分類精度，實(shí)驗(yàn)結(jié)果如表3和表4所示。

表3 基于SVM算法的分類精度比較

表4 基于C4.5算法的分類精度比較

由表3和表4可知：

1) 對(duì)于兩個(gè)混合型數(shù)據(jù)集Heart、Hepatitis，關(guān)于數(shù)據(jù)集Heart，本文算法ARNCE約簡(jiǎn)后的分類精度最高；關(guān)于數(shù)據(jù)集Hepatitis，本文算法ARNCE和ARNCM約簡(jiǎn)后的分類精度相等并且都高于算法DNFS、ARCE。

2) 對(duì)于兩個(gè)數(shù)值型數(shù)據(jù)集Wdbc、Sonar，關(guān)于數(shù)據(jù)集Wdbc，在SVM下本文算法ARNCE約簡(jiǎn)后的分類精度較高，在C4.5下算法ARNCM約簡(jiǎn)后的分類精度較高；關(guān)于數(shù)據(jù)集Sonar，在SVM下算法ARNCM約簡(jiǎn)后的分類精度較高，在C4.5下本文算法ARNCE約簡(jiǎn)后的分類精度較高。

3) 對(duì)于兩個(gè)符號(hào)型數(shù)據(jù)集Zoo、Soybean，關(guān)于數(shù)據(jù)集Zoo，算法ARCE約簡(jiǎn)后的分類精度較高；關(guān)于數(shù)據(jù)集Soybean，本文算法ARNCE約簡(jiǎn)后的分類精度較高。

從整體上看，相比于算法DNFS、ARCE和ARNCM，本文提出的算法ARNCE對(duì)大部分?jǐn)?shù)據(jù)集進(jìn)行屬性約簡(jiǎn)后的分類精度較高。

綜合上述實(shí)驗(yàn)結(jié)果可知，本文算法ARNCE能夠?qū)︵徲蛐畔⑾到y(tǒng)進(jìn)行有效約簡(jiǎn)，且能夠獲得約簡(jiǎn)集較小、分類精度較高的屬性約簡(jiǎn)結(jié)果。

5 結(jié) 語

以鄰域信息系統(tǒng)為研究對(duì)象，本文從信息論角度出發(fā)，定義了鄰域信息熵和鄰域條件熵。結(jié)合鄰域條件熵和近似精度，定義了鄰域組合熵，可以綜合知識(shí)不確定性和集合不確定性對(duì)鄰域信息系統(tǒng)屬性重要度進(jìn)行度量，給出并證明了鄰域組合熵的相關(guān)定理?；卩徲蚪M合熵，提出了鄰域信息系統(tǒng)中的屬性約簡(jiǎn)算法。實(shí)驗(yàn)結(jié)果表明該算法能夠獲得約簡(jiǎn)集較小而分類精度較大的約簡(jiǎn)結(jié)果。在關(guān)于鄰域信息系統(tǒng)的屬性約簡(jiǎn)算法中，鄰域參數(shù)δ的選取，對(duì)約簡(jiǎn)結(jié)果有著很大影響，下一步將對(duì)鄰域參數(shù)δ選取進(jìn)行研究。