基于熵權(quán)法的過濾式特征選擇算法

李占山， 楊云凱， 張家晨

(吉林大學(xué) 軟件學(xué)院， 吉林 長春 130012)

特征選擇是模式識別和數(shù)據(jù)挖掘中的一個重要預(yù)處理步驟.其本質(zhì)含義是指在不明顯損失數(shù)據(jù)集潛在信息的基礎(chǔ)上從原始特征集合中選出部分特征構(gòu)成特征子集，以此來降低數(shù)據(jù)集的特征維度，規(guī)避維度災(zāi)難，提高分類的時間效率，它可以縮減訓(xùn)練時間并產(chǎn)生具有可解釋性的模型[1].

一般地，特征選擇可以分為過濾式[2]、封裝式(包裹式)[3-5]、嵌入式[6-7].過濾式特征選擇算法的核心在于過濾標(biāo)準(zhǔn)，即通過某種準(zhǔn)則對特征(子集)進行度量.為此人們提出了多種評價準(zhǔn)則，如基于距離度量標(biāo)準(zhǔn)的RReliefF[8]、基于互信息理論的準(zhǔn)則[9]等.

近年來人們提出了多種基于互信息理論的過濾式特征選擇算法，如MIFSU[10]、mRMR[11]、NMIFS[12]、INMIFS[13]、WNMIFS[14]、CFR[15]、WCFR[16]等.

然而上述算法往往只局限于互信息這一度量標(biāo)準(zhǔn)，雖然互信息可以較好地度量變量之間的相關(guān)性，但其在實際應(yīng)用中也有一定的局限性——互信息是基于信息熵理論的，該理論對于連續(xù)變量的信息熵，采取了微分熵的計算形式得出.但對于給定的數(shù)據(jù)集，常常無法知道連續(xù)變量的具體概率分布，進而無法計算其概率密度函數(shù)，也就不能在真正意義上計算得出連續(xù)變量的信息熵.這種情況下人們往往會采取將數(shù)據(jù)離散化的策略，將原始的連續(xù)變量轉(zhuǎn)化為離散變量，又或者采取K-近鄰等方式進行估算，這無疑在一定程度上引入了誤差.

基于上述考慮，本文為了規(guī)避采取單一的互信息標(biāo)準(zhǔn)的局限性，試圖在互信息的基礎(chǔ)上引入另一種基于距離度量的算法RReliefF，以期能更好地對特征進行篩選.

RReliefF本是用于回歸任務(wù)中的特征選擇算法，它基于距離度量評估特征的重要性，RReliefF算法運行效率高，且對數(shù)據(jù)類型限制較少，因此可以作為互信息度量的一個有效補充.鑒于分類任務(wù)和回歸任務(wù)的同一性，本文適應(yīng)性地將RReliefF用于分類任務(wù)，度量特征與標(biāo)簽的相關(guān)性.

最大互信息系數(shù)(maximal information coefficient，MIC)是一種優(yōu)秀的互信息變形，MIC利用了歸一化互信息，使得MIC具有普適性、均衡性的優(yōu)良特性，本文采用MIC度量特征與特征之間的冗余性、特征與標(biāo)簽的相關(guān)性.

RReliefF和MIC分別從距離度量和信息論的角度評估特征，將兩者結(jié)合可以在某種程度上避免算法限于某一度量標(biāo)準(zhǔn)的單一性和盲目性，最大程度地挖掘特征的重要性.

通常情況下，人們往往會通過為不同事物賦權(quán)重的方式將事物結(jié)合起來，賦權(quán)的方式有主觀賦權(quán)和客觀賦權(quán).主觀賦權(quán)的隨機性和主觀性較大，普適性和自適應(yīng)性較差.本文追求算法的穩(wěn)定性和普適性，因此擯棄了主觀賦權(quán)的思路.

熵權(quán)法是一種優(yōu)秀的客觀賦權(quán)方法，它基于信息熵理論，使得賦權(quán)過程更具客觀性，賦權(quán)結(jié)果具有更好的可解釋性.基于熵權(quán)法的上述特性，本文采用熵權(quán)法為RReliefF和MIC賦權(quán)，如此可以更充分地發(fā)揮兩者各自的優(yōu)勢，使最終的度量標(biāo)準(zhǔn)更趨于完善.在此基礎(chǔ)上，本文提出了基于熵權(quán)法的過濾式特征選擇算法(filtering feature selection algorithm based on entropy weight method， FFSBEWM).

1 基于熵權(quán)法的過濾式特征選擇算法(FFSBEWM)

基于熵權(quán)法的過濾式特征選擇算法框架如圖1所示.

圖1 基于熵權(quán)法的過濾式特征選擇算法框架

1.1 RReliefF度量數(shù)據(jù)集的各個特征

RReliefF算法原是用于回歸任務(wù)中的特征選擇算法，該算法的偽代碼如表1所示[8].

表1 RReliefF偽代碼

由表1可知，對于特征A的權(quán)重，該算法選取g個最近鄰樣本，利用該樣本與近鄰樣本間的距離來評估A的重要性.

RReliefF可以發(fā)現(xiàn)屬性之間的強依賴關(guān)系，且具有良好的魯棒性.

回歸任務(wù)中樣本的標(biāo)簽是連續(xù)值，而分類任務(wù)中樣本的標(biāo)簽是離散值，且離散值在邏輯上是一種特殊的連續(xù)值，因此RReliefF同樣可以應(yīng)用于分類任務(wù).設(shè)定g=5，假定數(shù)據(jù)集的特征個數(shù)為l，對特征{A1，A2，…，Al}應(yīng)用RReliefF算法進行度量，得到各個特征的權(quán)重值，以向量r表示，r=[W[A1]，W[A2]，…，W[Al]]T.

1.2 MIC度量各個特征與標(biāo)簽的相關(guān)性

MIC最初由Reshef等[17]提出，它基于互信息理論.在此本文對互信息理論予以簡單介紹.

互信息用于評價兩個變量的統(tǒng)計相關(guān)性.對離散型隨機變量X和Y，其互信息定義如下：

(1)

式中：ΩX為變量X的取值空間；ΩY為變量Y的取值空間；p(x)為X=x的概率；p(y)為Y=y的概率；p(x，y)為X=x且Y=y的聯(lián)合概率.

除了式(1)外，對離散變量X，Y之間的互信息也可以用信息熵來表示.其定義如下：

I(X；Y)=H(X)-H(X|Y)=
H(Y)-H(Y|X)

.

(2)

式中，H(X)即為變量X的熵，其表達式為

H(X)=-∑x∈ΩXp(x)lb(p(x))

.

(3)

變量X的信息熵描述了變量X的不確定性，變量不確定性越大，信息熵就越大，這也意味著變量X隱含的信息越大.式(2)中H(X|Y)表示在已知Y的條件下X的不確定性，其計算公式為

H(X|Y)=
-∑x∈ΩX∑y∈ΩYp(x，y)lb(p(x|y))

.

(4)

MIC的核心思想：如果兩個變量之間存在某種關(guān)系，那么可以在兩個變量構(gòu)成的散點圖上繪制一個網(wǎng)格，從而劃分?jǐn)?shù)據(jù)來封裝這種關(guān)系.假設(shè)有兩個隨機變量X，Y，其MIC計算方式如下：

(5)

式中：M和N表示將X，Y構(gòu)成的散點圖劃分為M列N行的網(wǎng)格圖，M和N的取值需滿足MN

MIC本質(zhì)上是一種歸一化互信息，歸一化互信息的值被限制在(0，1)之間，屏蔽了互信息絕對值的數(shù)量級差異，因此MIC具有更高的準(zhǔn)確性和普適性.鑒于此，應(yīng)用式(5)度量各個特征與標(biāo)簽的相關(guān)性.假定數(shù)據(jù)集的特征個數(shù)為l，對特征{A1，A2，…，Al}中的每個特征Ai，以及標(biāo)簽C，應(yīng)用式(5)計算出該特征與標(biāo)簽的MIC值，最終得到向量q=[a(A1；C)，a(A2；C)，…，a(Al；C)]T.

1.3 應(yīng)用熵權(quán)法進行客觀賦權(quán)

熵權(quán)法是一種優(yōu)秀的客觀賦權(quán)方法，在數(shù)學(xué)相關(guān)領(lǐng)域有很多應(yīng)用.其依據(jù)的原理是指標(biāo)的變異程度越小，所反映的信息量也越少，其對應(yīng)的權(quán)值也應(yīng)該越低.應(yīng)用熵權(quán)法為指標(biāo)RReliefF和MIC賦權(quán)的過程如下[18].首先對r，q數(shù)據(jù)進行標(biāo)準(zhǔn)化：

(6)

(7)

隨后根據(jù)標(biāo)準(zhǔn)化數(shù)據(jù)求r，q的信息熵：

(8)

(9)

(10)

(11)

1.4 構(gòu)建過濾準(zhǔn)則

最終的過濾式準(zhǔn)則是相關(guān)項減去冗余項.其中相關(guān)項代表假設(shè)加入待選特征f后，新特征子集對類別的相關(guān)性的加權(quán)平均值;S代表已選擇的特征子集;η，θ客觀上平衡了RReliefF和MIC的重要性，更具有數(shù)理上的統(tǒng)計優(yōu)勢.其具體表達形式如下：

(12)

冗余項代表待選特征f與已選特征子集的相關(guān)性的平均值.在度量待選特征f與已選特征s之間的相關(guān)性時，僅僅采用了MIC度量，并未采用RReliefF，原因在于RReliefF算法中特征與標(biāo)簽存在預(yù)測與被預(yù)測的關(guān)系，而待選特征f與已選特征s之間并不存在邏輯上的預(yù)測與被預(yù)測關(guān)系，它們之間是對等的，所以RReliefF不可以用來度量特征與特征之間的關(guān)系.其MIC度量表達式如下:

(13)

最終得到的過濾式準(zhǔn)則為

(14)

1.5 貪婪式選擇特征

以式(14)為過濾式標(biāo)準(zhǔn)，采取前向搜索的策略，每次貪婪地選擇使式(14)取最大值的特征，直至達到預(yù)設(shè)的特征數(shù)目為止.

2 實 驗

2.1 數(shù)據(jù)集與對比算法

為了驗證所提算法(FFSBEWM)的優(yōu)劣性，本文將所提算法與相關(guān)算法進行了對比.實驗用到了3個分類器：K-近鄰(K-nearest neighbor，KNN)分類器、支持向量機(support vector machines， SVM)分類器以及鑒別分析(discriminant analysis，DA)分類器.本文在13個數(shù)據(jù)集上進行了實驗，數(shù)據(jù)集的各項信息如表2所示.

表2 數(shù)據(jù)集

這些數(shù)據(jù)集來自UCI機器學(xué)習(xí)數(shù)據(jù)庫以及Scikit-feature特征選擇資源庫.由表2知，實驗中采用的數(shù)據(jù)集涵蓋了低維(特征維度小于200)、中維(特征維度介于200到1 000之間)、高維(特征維度大于1 000)數(shù)據(jù)集；涵蓋了小樣本(樣本數(shù)小于1 000)、中樣本(樣本數(shù)大于1 000小于5 000)、大樣本(樣本數(shù)大于5 000)數(shù)據(jù)集；特征屬性既包括實數(shù)型，又包括整數(shù)型.綜上，本文選取的數(shù)據(jù)集具有代表性.

2.2 實驗實施

實驗過程分為兩個階段：第一個階段是利用各個算法對特征進行選擇，得出各個算法所選擇的特征子集；第二個階段是對篩選出的特征子集的優(yōu)越性進行評價，即將篩選出的數(shù)據(jù)放入分類器中進行分類，統(tǒng)計平均分類準(zhǔn)確率和最高分類準(zhǔn)確率.本文采用平均分類準(zhǔn)確率和最高分類準(zhǔn)確率作為評價指標(biāo)，平均分類準(zhǔn)確率的形式化描述如下：

(15)

式中：λ表示對特征子集進行10折交叉驗證后的分類準(zhǔn)確率；γ為設(shè)定的最大特征數(shù)目.若原始數(shù)據(jù)集特征個數(shù)大于30，則γ=30；否則，γ=特征數(shù)目.平均分類準(zhǔn)確率度量了算法所選擇特征子集的綜合分類性能.

最高分類準(zhǔn)確率即為當(dāng)v取1到γ時，所有λ的最大值.最高分類準(zhǔn)確率度量了算法所選擇的最優(yōu)特征子集的分類性能.其形式化描述如下：

ξ=max(λ)，v∈[1，γ]

.

(16)

2.3 實驗結(jié)果及討論

表3～表5分別表示各個算法所選擇的特征子集在KNN(K=5),SVM和DA分類器上的平均分類準(zhǔn)確率.表3、表4、表5所對應(yīng)的Nb，Ne，Nw數(shù)據(jù)分別如表6～表8所示，Nb，Ne，Nw表示FFSBEWM較好、持平、較差于對比算法的數(shù)據(jù)集個數(shù).

由表3、表4可看出，在KNN(K=5)和SVM分類器上，F(xiàn)FSBEWM均在9個數(shù)據(jù)集上取得最高準(zhǔn)確率，并且這些數(shù)據(jù)集涵蓋了低中高維數(shù)據(jù)集.除此之外，即便FFSBEWM在某些數(shù)據(jù)集上未取得最高準(zhǔn)確率，其依舊排名第二或第三.由表5可知，F(xiàn)FSBEWM所選擇的特征子集在5個數(shù)據(jù)集上取得了最高的準(zhǔn)確率，雖然相比SVM和KNN(K=5)分類器略有遜色，但縱向?qū)Ρ葋砜匆琅f說明FFSBEWM相比其他算法具有一定優(yōu)勢.由表6～表8可知，F(xiàn)FSBEWM勝于其他算法的數(shù)據(jù)集個數(shù)遠大于不勝于其他算法的數(shù)據(jù)集個數(shù)，在KNN(K=5)，SVM，DA分類器上平均勝出的數(shù)據(jù)集個數(shù)分別為11.6，9.1，8.2，勝出率分別為89.23%，70%，63%.綜合上述論證，F(xiàn)FSBEWM的平均分類準(zhǔn)確率顯著優(yōu)于其他算法.

表3 各個算法所選擇的特征子集在KNN(K=5)分類器上的平均分類準(zhǔn)確率

表5 各個算法所選擇的特征子集在DA分類器上的平均分類準(zhǔn)確率

表6 各個算法所選擇的特征子集在KNN(K=5)

表7 各個算法所選擇的特征子集在SVM分類器上的Nb,Ne,Nw統(tǒng)計表

表8 各個算法所選擇的特征子集在DA分類器上的

各個算法在三個分類器上的最大最高分類準(zhǔn)確率如表9所示.由表9可知，F(xiàn)FSBEWM在6個數(shù)據(jù)集上最大最高分類準(zhǔn)確率排名第一，這6個數(shù)據(jù)集同樣涵蓋低中高維；FFSBEWM在4個數(shù)據(jù)集上排名第二或第三.FFSBEWM算法的最大最高分類準(zhǔn)確率整體上同樣優(yōu)于其他算法.

表9 各個算法所選擇的特征子集在KNN(K=5)，SVM和DA分類器上的最大最高分類準(zhǔn)確率

為了分析分類準(zhǔn)確率與特征子集大小的關(guān)系，選取了具有代表性的4個數(shù)據(jù)集，見圖2～圖4.

由圖2～圖4可知，整體而言，隨著所選特征個數(shù)的增多，特征子集的分類準(zhǔn)確率相應(yīng)提高.這是因為當(dāng)選擇的特征數(shù)較小時，特征子集所包含的信息也較少，因此分類準(zhǔn)確率較低，反之亦然.值得一提的是這種正相關(guān)關(guān)系并非絕對.除此之外，盡管同一算法在同一分類器上的曲線走勢并不完全一致，但FFSBEWM的曲線整體上均位于所有曲線的最上方，即無論所選特征子集的大小，F(xiàn)FSBEWM所選擇的特征子集的分類性能均優(yōu)于其他算法.這也進一步說明了即使不同分類器會對算法產(chǎn)生一些影響，但這些影響在本文討論的范圍內(nèi)是非實質(zhì)性的.

圖2 各個算法所選擇的特征子集的分類準(zhǔn)確率隨特征數(shù)變化圖(KNN(K=5)分類器)

圖3 各個算法所選擇的特征子集的分類準(zhǔn)確率隨特征數(shù)變化圖(SVM分類器)

圖4 各個算法所選擇的特征子集的分類準(zhǔn)確率隨特征數(shù)變化圖(DA分類器)

3 結(jié) 語

本文提出了一種基于熵權(quán)法的過濾式特征選擇算法，在13個數(shù)據(jù)集上的實驗結(jié)果顯示本文算法選擇的特征子集的平均分類準(zhǔn)確率和最高分類準(zhǔn)確率均優(yōu)于其他算法.

但本文算法準(zhǔn)確率還不夠高，在個別數(shù)據(jù)集上略差于其他算法或者比其他算法的領(lǐng)先程度不夠高；受數(shù)據(jù)集本身影響較大，導(dǎo)致在某些數(shù)據(jù)集上算法的穩(wěn)定性較差；本文算法在不同的分類器上的表現(xiàn)也略有差異.后續(xù)將進一步對特征選擇的過程框架予以改進，以期提高所選擇的特征子集的分類準(zhǔn)確率，同時完善特征選擇的過濾式標(biāo)準(zhǔn)，加入對算法穩(wěn)定性的度量，提高算法的穩(wěn)定性.