基于模糊近似空間組合度量的特征選擇算法

費(fèi)賢舉，劉金碩，田國忠

(1.常州工學(xué)院 計算機(jī)信息工程學(xué)院，江蘇 常州 213032；2.武漢大學(xué) 計算機(jī)學(xué)院，湖北 武漢 430072)

0 引 言

在特征選擇[1-11]算法中，如何對屬性的重要度進(jìn)行更精確的評估一直是特征選擇的研究重點(diǎn)，目前學(xué)者們提出了多種的度量方法。例如翟俊海等[3]利用屬性的相關(guān)性作為度量方法，提出一種特征選擇算法，陳媛等[4]利用一致性度量進(jìn)行特征選擇，Wang等[5,6]利用距離度量進(jìn)行特征選擇，Jiang等[7]和Zhao等[8]利用粗糙集理論的依賴度度量用于特征選擇算法的構(gòu)造，近年來，信息熵度量[9-11]用于特征選擇的方法被大量提出。目前信息熵已作為一種常用的屬性度量方法。

粒計算理論由Zadeh[12]提出，目前已在智能信息處理領(lǐng)域發(fā)揮著重要的作用[13]，其中模糊近似空間[14]是粒計算理論一種重要的形式，它以模糊集理論[15]為基礎(chǔ)，將信息系統(tǒng)中的對象按照一定的相似關(guān)系進(jìn)行?；?，并生成相應(yīng)的信息粒，通過信息粒的全體可以組成信息系統(tǒng)的?？臻g，?？臻g是粒計算中一個重要的概念[16-18]，它是對信息系統(tǒng)各個方面度量的基礎(chǔ)。因此可以考慮運(yùn)用粒計算模型來對屬性進(jìn)行評估，從而達(dá)到更好度量效果。

在模糊近似空間中，本文首先在信息系統(tǒng)中構(gòu)造模糊粒空間，然后在此基礎(chǔ)上引入了模糊粒度度量，由于模糊粒度是對信息系統(tǒng)分類能力的體現(xiàn)[17]，因而可以作為屬性重要度的一種評估方式。信息熵是特征選擇中一種重要的方法[9-11]，本文將條件熵[19]在模糊近似空間中進(jìn)行推廣，提出了模糊條件熵的概念。模糊粒度和模糊條件熵代表了不同的評估視角，為了對屬性進(jìn)行多視角的度量，本文將模糊條件熵與模糊粒度結(jié)合起來，提出一種組合度量方法來對屬性重要度進(jìn)行評估，同時給出了相應(yīng)的特征選擇算法，UCI實(shí)驗(yàn)結(jié)果表明，本文所構(gòu)造出的算法比目前已有的特征選擇算法更具一定優(yōu)越性。

1 模糊集與模糊二元?？臻g

在粒計算模型[12]中，數(shù)據(jù)集又稱為信息系統(tǒng)，可表示為IS=(U,AT,V,f)，其中U被稱為論域，AT為屬性集(特征集)，V為全體屬性集的值域，V=∪Va，其中Va為屬性a∈AT的值域，f為屬性到屬性值域上的映射，對象x在屬性a的值可表示為a(x)。當(dāng)信息系統(tǒng)IS=(U,C∪D,V,f)時，此信息系統(tǒng)又被稱為決策信息系統(tǒng)(DIS)，其中C,D分別被稱為信息系統(tǒng)的條件屬性和決策屬性。若條件屬性均為數(shù)值型數(shù)據(jù)，此信息系統(tǒng)稱為鄰域信息系統(tǒng)。

定義1[18]對于鄰域信息系統(tǒng)NIS=(U,AT,V,f)，由B?AT在U上誘導(dǎo)的模糊二元關(guān)系RB滿足關(guān)系:①?x∈U，RB(x,x)=1，②?x,y∈U，RB(x,y)=RB(y,x),設(shè)|U|=n，那么模糊二元關(guān)系RB可由矩陣表示為

(1)

定義2[18]對于鄰域信息系統(tǒng)NIS=(U,AT,V,f)，B?AT在U上誘導(dǎo)的模糊二元關(guān)系為RB，RB在論域上的模糊?？臻g定義為

K(RB)=(SRB(x1),SRB(x2),…,SRB(xn)),xi∈U(2)

2 模糊近似空間組合度量

2.1 模糊粒度

在信息系統(tǒng)的不確定性度量中，基于模糊近似空間的?？臻g一直是常用的度量體系，目前研究人員們提出了大量的度量方法。如Huang等學(xué)者[17]定義了模糊粒度的概念。

定義3[17]設(shè)鄰域信息系統(tǒng)NIS=(U,AT,V,f)，B?AT在U上對應(yīng)的模糊二元關(guān)系為RB，導(dǎo)出的模糊粒空間為K(RB)=(SRB(x1),SRB(x2),…,SRB(xn))，那么RB在U上的模糊粒度GK(B)定義為

(3)

性質(zhì)1 對于鄰域信息系統(tǒng)NIS=(U,AT,V,f),B1?B2?AT在U上對應(yīng)的模糊二元關(guān)系分別為RB1,RB2，導(dǎo)出的對應(yīng)模糊粒空間為K(RB1)=(SRB1(x1),SRB1(x2),…,SRB1(xn)),K(RB2)=(SRB2(x1),SRB2(x2),…,SRB2(xn))，那么模糊粒度滿足GK(B2)≤GK(B1)。

證明：由于B1?B2，根據(jù)定義1有RB2?RB1，因此有?x∈U,SRB2(x)?SRB1(x)，即|SRB2(x)|≤|SRB1(x)|，根據(jù)定義3有GK(B2)≤GK(B1)。證畢。

通過性質(zhì)1可以看出，隨著屬性集B的逐漸增加，其模糊粒度是單調(diào)不增的，即當(dāng)對象的模糊信息粒越精細(xì)時，模糊粒度就越小，當(dāng)對象的模糊信息粒越粗糙時，模糊粒度就越大，因此模糊粒度體現(xiàn)了模糊二元關(guān)系對論域知識粒度劃分能力的度量。

2.2 模糊條件熵

Liang等[20]學(xué)者提出了信息系統(tǒng)中的信息熵模型，為粒計算中的熵理論研究奠定了基礎(chǔ)，文獻(xiàn)[18,19]在此基礎(chǔ)上定義了基于信息系統(tǒng)的條件熵模型。條件熵是一種構(gòu)造特征選擇常用的方法。隨后很多學(xué)者將條件熵理論推廣到各個模型中[21]。本文在此基礎(chǔ)上，將條件熵引入到模糊近似空間中，提出模糊條件熵模型。

定義4 設(shè)鄰域信息系統(tǒng)NIS=(U,AT,V,f),B?AT在U上誘導(dǎo)的模糊二元關(guān)系為RB，其模糊?？臻g為K(RB)=(SRB(x1),SRB(x2),…,SRB(xn))，定義RB下的模糊信息熵[18]FE(B)為

(4)

對于?xi∈U，當(dāng)SRB(xi)={xi}時，有FE(B)=1-1/n，對于?xi∈U,SRB(xi)=U時，有FE(B)=0，因此可以推出模糊信息熵滿足0≤FE(B)≤1-1/n。

定義5 設(shè)鄰域信息系統(tǒng)NIS=(U,AT,V,f),B1,B2?AT在U上的誘導(dǎo)的模糊二元關(guān)系分別為RB1,RB2，其對應(yīng)的模糊?？臻g為K(RB1)=(SRB1(x1),SRB1(x2),…,SRB1(xn)),K(RB2)=(SRB2(x1),SRB2(x2),…,SRB2(xn))，定義RB2關(guān)于RB1的模糊條件熵FCE(B2|B1)為

(5)

類似于定義4，模糊條件熵滿足0≤FCE(B2|B1)≤1-1/n。

對于鄰域決策信息系統(tǒng)NDIS=(U,C∪D,V,f),B?C在U上的誘導(dǎo)的模糊二元關(guān)系分別為RB，對應(yīng)的模糊?？臻g為K(RB)，決策屬性D誘導(dǎo)的等價關(guān)系為RD，那么RB關(guān)于RD的模糊條件熵FCE(D|B)為

(6)

這里[x]D表示對象xi在D下的等價類。

性質(zhì)2 設(shè)鄰域決策信息系統(tǒng)NDIS=(U,C∪D,V,f),B1?B2?C在U上的誘導(dǎo)的模糊二元關(guān)系分別為RB1,RB2，其對應(yīng)的模糊粒空間為K(RB1),K(RB2)，那么模糊條件熵滿足

FCE(D|B2)≤FCE(D|B1)

性質(zhì)1和性質(zhì)2表明，隨著屬性集B的逐漸增大，其模糊條件熵FCE(D|B)和模糊粒度的值都是單調(diào)不增的，因此它們都可以作為信息系統(tǒng)中屬性集的不確定性度量，由于模糊粒度和模糊條件熵代表了不同視角下的度量方法，因此可以將它們結(jié)合起來，提出一種組合的信息系統(tǒng)不確定性度量。

定義6 設(shè)鄰域決策信息系統(tǒng)NDIS=(U,C∪D,V,f),B?C在U上的誘導(dǎo)的模糊二元關(guān)系為RB，其對應(yīng)的模糊粒空間為K(RB)，那么在模糊近似空間中D關(guān)于B組合度量定義為

M(B,D)=GK(B)·FCE(D|B)

(7)

隨著屬性集B的逐漸增大，根據(jù)性質(zhì)1和性質(zhì)2結(jié)論，組合度量M(B,D)的值是單調(diào)不增的。由于1/n≤GK(B)≤1, 0≤FCE(D|B)≤1-1/n，所以組合度量滿足0≤M(B,D)≤1-1/n。組合度量的單調(diào)性為接下來的特征選擇算法的構(gòu)造提供了理論基礎(chǔ)。

定義7[8]設(shè)鄰域決策信息系統(tǒng)NDIS=(U,C∪D,V,f),B?C為該決策信息系統(tǒng)的一個相對約簡當(dāng)且僅當(dāng)：

(1)M(C,D)=M(B,D)；

(2)?a∈B,M(B-{a},D)>M(B,D)。

定義8[9]設(shè)鄰域決策信息系統(tǒng)NDIS=(U,C∪D,V,f),B?C, ?a∈B，則a關(guān)于B在決策屬性D下的重要度定義為

(8)

對于?a∈C-B，則a關(guān)于B在決策屬性D下的重要度定義為

(9)

3 特征選擇算法

基于定義8給出的信息系統(tǒng)重要度的定義，這里構(gòu)造出相應(yīng)的特征算法—基于模糊近似空間組合度量的數(shù)值特征選擇算法FSFASCM(feature selection based on fuzzy approximation space combination metric)。首先算法1給出的是組合度量的計算方法。

算法1：組合度量。

輸入：NDIS=(U,C∪D,V,f)，屬性子集B?C, |U|=n。

輸出：M(B,D)。

(1)初始化GK(B)=0,FCE(D|B)=0。

(2)對于?xi∈U，計算SRB(xi), [xi]D。然后根據(jù)定義3和定義5對模糊粒度GK(B)和模糊條件熵FCE(D|B)進(jìn)行累加，即：GK(B)←GK(B)+|SRB(xi)|,FCE(D|B)←FCE(D|B)+(|SRB(xi)|-|SRB(xi)-[xi]D|)。

(3)進(jìn)行計算

(4)返回組合度量值

M(B,D)=GK(B)·FCE(D|B)

設(shè)|C|=c, |U|=n，算法1的計算時間主要集中在步驟(2)，由于每個對象計算模糊信息粒的時間復(fù)雜度為O(c·n)，因此整個算法1的時間復(fù)雜度為O(c·n2)。根據(jù)算法1，接下來給出本文提出的特征選擇的主算法，具體如算法2所示。

算法2：模糊近似空間組合度量特征選擇算法(FSFASCM)。

輸入：NDIS=(U,C∪D,V,f)。

輸出：約簡集S。

(1)初始化：S=?。

(3)根據(jù)算法1，若M(S,D)=M(C,D)，那么進(jìn)入步驟(5)，否則進(jìn)入步驟(4)。

(5)令集合φ←?，對于?a∈S，如果M(S-{a},D)=M(C,D)，那么φ←φ∪{a}。

(6)如果φ為空，那么進(jìn)入步驟(7)，否則，任意選擇φ中的一個屬性a，進(jìn)行S=S-{a}，并進(jìn)入步驟(5)。

(7)返回約簡集S。

設(shè)|C|=c, |U|=n，算法2的時間復(fù)雜度主要集中在步驟(2)，因此整個算法2的時間復(fù)雜度為O(c2·n2)。

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

為了驗(yàn)證本文所提特征選擇算法的優(yōu)越性，本實(shí)驗(yàn)從UCI標(biāo)準(zhǔn)數(shù)據(jù)集庫下載了6個數(shù)據(jù)集，見表1，然后將所提的算法與目前已有的相關(guān)算法對這些數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)分析，優(yōu)越性的比較通過各個算法的特征子集、分類精度和運(yùn)行時間來體現(xiàn)。參與比較的算法分別為：①模糊鄰域粗糙集特征選擇算法FSFNRS(feature selection based on fuzzy neighborhood rough sets)[22]；②模糊粗糙集擬合模型的特征選擇算法FSFRSFM(feature selection based on fuzzy rough set fitting model)[6]；③基于鄰域熵的特征選擇算法FSNE(feature selection based on neighborhood entropy)[23]。

表1 數(shù)據(jù)集詳細(xì)信息

為了消除屬性量綱的影響，表1中的數(shù)據(jù)集屬性值均被歸一化到[0,1]區(qū)間，本實(shí)驗(yàn)運(yùn)行的硬件環(huán)境為Intel(R) 酷睿i5 680，3.6 GHz CPU和4.0 GB RAM，Windows7操作系統(tǒng)，編程工具選為JDK1.8。實(shí)驗(yàn)中分類精度的計算采用支持向量機(jī)(SVM)和決策樹(C4.5)兩種分類器。

表2所示的是4種算法在各個數(shù)據(jù)集上特征選擇結(jié)果，其中包括具體的屬性子集結(jié)果和屬性子集大小。觀察表2可以看出，4種特征選擇算法得到的屬性子集并不相同，例如在數(shù)據(jù)集Wine的結(jié)果中，4種算法得到的屬性子集都包含序號為1，2，7，11，13的屬性，說明這些屬性對Wine數(shù)據(jù)集的分類發(fā)揮關(guān)鍵的作用，但是除了這些屬性，其它的每種算法的結(jié)果并不相同，說明其它的屬性對分類的作用比較低，不同的算法對這些屬性的鑒別能力不同，從而引起了屬性子集結(jié)果的差異。同時可以看出，在大部分?jǐn)?shù)據(jù)集中，本文所提的FSFASCM算法選擇出的屬性子集大小更小一些，這主要是由于在算法2中，我們對按照屬性重要度選擇出的特征子集利用組合度量進(jìn)行了進(jìn)一步的篩選，從而能夠選擇出更為關(guān)鍵的屬性。

表2 4種算法的特征選擇結(jié)果

接下來比較這4種算法在各個數(shù)據(jù)集上特征選擇的算法效率。這4種算法的時間復(fù)雜度均為O(c2·n2)，我們將每種算法在各個數(shù)據(jù)集重復(fù)特征選擇5次，算法的最終用時采用這5次時間的平均值，其實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 4種算法計算時間對比

觀察圖1可以發(fā)現(xiàn)，雖然4種算法擁有相同的時間復(fù)雜度，但是具體的實(shí)驗(yàn)耗時略有差異，其中FSFRSFM算法在各個數(shù)據(jù)集上的實(shí)驗(yàn)耗時最長，而FSFASCM算法在各個數(shù)據(jù)集上的實(shí)驗(yàn)耗時是最短的，說明本文所提出的特征選擇算法擁有了較高的計算效率。為了驗(yàn)證4種算法特征選擇結(jié)果的優(yōu)越性，實(shí)驗(yàn)中采用SVM和C4.5兩種分類器分別對表2中的特征子集進(jìn)行十折交叉訓(xùn)練，得到對應(yīng)的分類精度，其結(jié)果見表3。觀察可以發(fā)現(xiàn)，對于SVM分類器下特征子集的分類精度，除數(shù)據(jù)集heart和iono外，F(xiàn)SFASCM在其余數(shù)據(jù)集上的分類精度是最大的，說明了FSFASCM選擇出更小的特征子集同時且保持高的分類精度。同時觀察C4.5的分類精度結(jié)果，我們也能夠得到同樣的結(jié)論。通過以上實(shí)驗(yàn)分析可以看出，本文所提出的FSFASCM算法在特征子集大小、算法運(yùn)算效率和分類精度方面均具有一定的優(yōu)勢，因而用于數(shù)據(jù)的特征選擇是適用的。

表3 4種算法特征選擇結(jié)果兩種分類器下的分類精度/%

5 結(jié)束語

由于現(xiàn)實(shí)中的數(shù)據(jù)集存在大量的不相關(guān)屬性，因此對數(shù)據(jù)進(jìn)行特征選擇是很有必要的，本文在模糊近似空間引入模糊粒度，并在該空間中定義了模糊條件熵的概念，由于這兩種方法是根據(jù)不同的視角來對屬性進(jìn)行重要度評估，因此將它們結(jié)合提出一種組合度量方法，同時給出相應(yīng)的特征選擇算法。UCI實(shí)驗(yàn)結(jié)果表明該算法的優(yōu)越性。由于該特征選擇算法適用于數(shù)值型屬性，因而如何構(gòu)造混合數(shù)據(jù)的特征選擇方法將是接下來的進(jìn)一步研究方向。