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

費賢舉，劉金碩，田國忠

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

0 引 言

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

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

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

1 模糊集與模糊二元粒空間

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

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

(1)

定義2[18]對于鄰域信息系統NIS=(U,AT,V,f)，B?AT在U上誘導的模糊二元關系為RB，RB在論域上的模糊粒空間定義為

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

2 模糊近似空間組合度量

2.1 模糊粒度

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

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

(3)

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

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

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

2.2 模糊條件熵

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

定義4 設鄰域信息系統NIS=(U,AT,V,f),B?AT在U上誘導的模糊二元關系為RB，其模糊粒空間為K(RB)=(SRB(x1),SRB(x2),…,SRB(xn))，定義RB下的模糊信息熵[18]FE(B)為

(4)

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

定義5 設鄰域信息系統NIS=(U,AT,V,f),B1,B2?AT在U上的誘導的模糊二元關系分別為RB1,RB2，其對應的模糊粒空間為K(RB1)=(SRB1(x1),SRB1(x2),…,SRB1(xn)),K(RB2)=(SRB2(x1),SRB2(x2),…,SRB2(xn))，定義RB2關于RB1的模糊條件熵FCE(B2|B1)為

(5)

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

對于鄰域決策信息系統NDIS=(U,C∪D,V,f),B?C在U上的誘導的模糊二元關系分別為RB，對應的模糊粒空間為K(RB)，決策屬性D誘導的等價關系為RD，那么RB關于RD的模糊條件熵FCE(D|B)為

(6)

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

性質2 設鄰域決策信息系統NDIS=(U,C∪D,V,f),B1?B2?C在U上的誘導的模糊二元關系分別為RB1,RB2，其對應的模糊粒空間為K(RB1),K(RB2)，那么模糊條件熵滿足

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

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

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

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

(7)

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

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

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

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

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

(8)

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

(9)

3 特征選擇算法

基于定義8給出的信息系統重要度的定義，這里構造出相應的特征算法—基于模糊近似空間組合度量的數值特征選擇算法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。然后根據定義3和定義5對模糊粒度GK(B)和模糊條件熵FCE(D|B)進行累加，即：GK(B)←GK(B)+|SRB(xi)|,FCE(D|B)←FCE(D|B)+(|SRB(xi)|-|SRB(xi)-[xi]D|)。

(3)進行計算

(4)返回組合度量值

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

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

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

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

輸出：約簡集S。

(1)初始化：S=?。

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

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

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

(7)返回約簡集S。

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

4 實驗分析

為了驗證本文所提特征選擇算法的優越性，本實驗從UCI標準數據集庫下載了6個數據集，見表1，然后將所提的算法與目前已有的相關算法對這些數據集進行實驗分析，優越性的比較通過各個算法的特征子集、分類精度和運行時間來體現。參與比較的算法分別為：①模糊鄰域粗糙集特征選擇算法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 數據集詳細信息

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

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

表2 4種算法的特征選擇結果

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

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

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

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

5 結束語

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