基于互信息與判別結(jié)構(gòu)互補(bǔ)的特征選擇

張開(kāi)翔，李雙杰，王小剛，李雅麗，陳倩茹，王淑琴

（天津師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院，天津300387）

高維數(shù)據(jù)的維數(shù)約減是機(jī)器學(xué)習(xí)領(lǐng)域中的一個(gè)重要問(wèn)題[1-2].維數(shù)約簡(jiǎn)的方法主要包括特征選擇和特征提取.特征提取方法是基于原始特征集的線性或非線性組合來(lái)創(chuàng)建新的特征，從而將現(xiàn)有的特征空間轉(zhuǎn)化為新的低維特征空間；而特征選擇方法是在原始特征空間中按照某種評(píng)價(jià)指標(biāo)選擇有助于分類的特征子集.

特征選擇是數(shù)據(jù)預(yù)處理的重要方法之一[3-4].在統(tǒng)計(jì)和機(jī)器學(xué)習(xí)領(lǐng)域，相關(guān)學(xué)者對(duì)特征選擇方法進(jìn)行了深入研究，其基本思想是通過(guò)消除無(wú)關(guān)和冗余特征來(lái)選擇特征子集，這類方法已被廣泛應(yīng)用于圖像[5]、視頻[6]和文本[7-8]處理以及基因分析[9-11]等許多方面.特征選擇方法主要包括Filter 和Wrapper 2 類.Filter 方法基于樣本的固有屬性來(lái)選擇特征，這些屬性通常由某些統(tǒng)計(jì)標(biāo)準(zhǔn)來(lái)測(cè)量，該方法具有計(jì)算效率高、數(shù)據(jù)集維數(shù)可伸縮性強(qiáng)以及與分類器相互獨(dú)立等優(yōu)點(diǎn)，適合處理大數(shù)據(jù)[12-14].Wrapper 方法通常使用分類器的預(yù)測(cè)精度來(lái)評(píng)價(jià)所有可能的特征集合，從而選出預(yù)測(cè)精度最好的特征子集.由于所選特征子集經(jīng)過(guò)分類算法的優(yōu)化，所以，一般情況下，Wrapper 方法的效果較好.但是，Wrapper 方法可能會(huì)導(dǎo)致學(xué)習(xí)算法產(chǎn)生過(guò)擬合.

在Filter 方法中，一般使用距離、互信息、相關(guān)系數(shù)和一致性度量來(lái)計(jì)算特征與特征、特征與類別之間的相關(guān)性.一般來(lái)說(shuō)，相關(guān)性得分高的特征比得分低的特征具有更強(qiáng)的分類能力，因此，得分高的特征會(huì)被優(yōu)先選擇.然而，近年來(lái)一些研究表明，多個(gè)得分高特征的組合不一定總能得到好的分類效果，將一些低得分特征加入目標(biāo)子集中效果反而可能會(huì)更好[15].得分高的特征對(duì)整個(gè)分類問(wèn)題的分類能力較強(qiáng)，但并不代表該特征對(duì)某個(gè)子問(wèn)題的分類能力也較強(qiáng)，在多類問(wèn)題中總分類能力不強(qiáng)的特征也可能對(duì)某些子問(wèn)題的分類能力較強(qiáng).所以，使用單一的評(píng)價(jià)策略來(lái)評(píng)價(jià)特征的分類能力忽略了特征對(duì)不同子問(wèn)題的分類能力.針對(duì)上述問(wèn)題，本文提出了一種基于互信息與判別結(jié)構(gòu)互補(bǔ)的特征選擇算法（information gain and subproblem complementary-based feature selection，IGSCFS）.該算法首先使用互信息作為特征分類能力的度量，然后根據(jù)每個(gè)特征對(duì)不同子問(wèn)題的分類能力來(lái)選擇特征，是一種基于分類子問(wèn)題的特征選擇方法.該算法不僅考慮了特征對(duì)總分類問(wèn)題的分類能力，也考慮了特征對(duì)子問(wèn)題的分類能力.將本文算法與已有的6 個(gè)特征選擇算法在6 個(gè)公開(kāi)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)比較，結(jié)果表明，在大多數(shù)情況下，本文算法的分類性能優(yōu)于其他特征選擇算法.

1 互信息

2012 年，Brown 等[16]提出了一種基于信息論的特征選擇統(tǒng)一框架，它是一種典型的特征選擇方法[16].熵是隨機(jī)變量不確定性的度量，用來(lái)度量隨機(jī)變量所需的平均信息量[17].離散型隨機(jī)變量X=（x1，x2，…，xn）的熵記為H（X），xi表示X 可能取到的值.H（X）定義為

其中：p（x）i為X 的概率密度函數(shù)，p（x）i的取值為

2 個(gè)隨機(jī)變量X 和C=（c1，c2，…，cm）的聯(lián)合熵定義為

其中：p（xi，c）j為X 和C 的聯(lián)合概率密度函數(shù).在給定X 的情況下變量C 的條件熵定義為

條件熵是引入變量X 后，C 中留下的不確定性，因此它不大于這2 個(gè)變量的熵.當(dāng)且僅當(dāng)2 個(gè)變量X 和C 相互獨(dú)立時(shí)，H（C|X）=H（C）.聯(lián)合熵與條件熵的關(guān)系為

X 和C 的互信息（mutual information，MI）是2 個(gè)變量共享的信息量，定義為

MI 表示變量X 提供的降低變量C 的不確定性的信息量.2 個(gè)隨機(jī)變量的MI 越大表明其相關(guān)性越強(qiáng)，如果2 個(gè)變量是相互獨(dú)立的，則MI = 0. MI 具有對(duì)稱性，所以有

由互信息的定義可以看出，MI 的值可能很大或很小，因此不同MI 值的特征的作用可能會(huì)被放大或弱化，對(duì)稱不確定性（symmetric uncertainty，SU）可以補(bǔ)償互信息對(duì)多值特征的偏向，并通過(guò)限制大熵輸入，將SU 值限制在[0，1]范圍內(nèi).隨機(jī)變量X 和C 的對(duì)稱不確定性定義為

2 基于互信息與判別結(jié)構(gòu)互補(bǔ)的特征選擇方法

2.1 誤分類樣本

對(duì)于實(shí)值特征的多類數(shù)據(jù)集D(p，q)，其中p、q 代表樣本的類別，（p，q）代表所有類別屬于p 和q 的樣本的集合.記minq、maxq、minp、maxp為特征fj對(duì)應(yīng)于（p，q）樣本集合的特征值的最大值和最小值. 若第i 個(gè)樣本的第j 個(gè)特征fj的特征值fji滿足fji∈[minq，maxq]∩[minp，maxp]，則稱第i 個(gè)樣本被特征fj誤分類.所有被fj誤分類的樣本的集合稱為fj的誤分類樣本集，記為MSfj（p，q）.特征子集S 的誤分類樣本集為

2.2 判別結(jié)構(gòu)向量

設(shè)O={f，f，…，f，C}n為一個(gè)有m 個(gè)特征、n1i2imiii=1個(gè)樣本的數(shù)據(jù)集，其中：F = { f1，f2，…，fm}為特征集，S?F 為特征子集；fji為第i 個(gè)樣本的第j 個(gè)特征值；C ={1，2，…，k}為類標(biāo)簽，Ci?C 為第i 個(gè)樣本的類標(biāo)簽.k 類分類問(wèn)題可以被分為k（k - 1）/2 個(gè)二分類子問(wèn)題.對(duì)每一個(gè)特征，它對(duì)某個(gè)子問(wèn)題的SU 值越大，則它對(duì)該子問(wèn)題的分類能力就越強(qiáng).由式（11）可以計(jì)算出特征fj對(duì)所有二分類子問(wèn)題的分類能力，當(dāng)特征的SU 值大于0 時(shí)，它對(duì)于分類是有幫助的.若每個(gè)特征的SU 值都大于0，則需要借助一個(gè)閾值來(lái)區(qū)分特征與類別之間相關(guān)性的強(qiáng)弱，閾值確定的具體原則在2.4 節(jié)給出.為了更好地體現(xiàn)每個(gè)特征對(duì)子問(wèn)題的分類能力，本文算法對(duì)不同子問(wèn)題設(shè)置了不同的閾值，如果特征的SU 值大于閾值，則認(rèn)為該特征對(duì)于該子問(wèn)題是有判別性的，基于此，為每個(gè)特征構(gòu)建一個(gè)判別結(jié)構(gòu)向量Vj，其維數(shù)等于二分類子問(wèn)題的數(shù)量.使用函數(shù)vj（p，q）= I（SUj（p，q），θ(p，q)）來(lái)判定fj在給定閾值 θ(p，q)下對(duì)子問(wèn)題（p，q）是否具有判別能力，

vj（p，q）=1（或0）表示特征fj對(duì)子問(wèn)題（p，q）有（或無(wú)）判別能力.對(duì)于一個(gè)k 分類問(wèn)題，特征fj在給定閾值Θ=[θ(1，2)，θ(1，3)，…，θ(1，k)，…，θ(k-1，k)]下的判別結(jié)構(gòu)向量為Vj=[vj（1，2），vj（1，3），…，vj（1，k），…，vj（k-1，k）].

2.3 判別結(jié)構(gòu)向量下的特征互補(bǔ)和特征覆蓋

一般情況下，一個(gè)特征無(wú)法正確區(qū)分所有的分類問(wèn)題，所以需要找到多個(gè)特征的組合來(lái)提升分類準(zhǔn)確率.對(duì)于特征fi和fj，若vi（p，q）=0，vj（p，q）=1，即fi對(duì)子問(wèn)題（p，q）無(wú)分類能力而fj對(duì)（p，q）有分類能力，則稱fi和fj在子問(wèn)題（p，q）上是互補(bǔ)的.對(duì)于2 個(gè)特征fi和fj的判別結(jié)構(gòu)向量Vi和Vj，若Vi∨Vj=Vi，∨代表按位異或操作，則稱特征fi覆蓋了fj，記作fi≥fj.不是所有的被覆蓋特征對(duì)分類都沒(méi)有貢獻(xiàn)，在進(jìn)行特征選擇中，若fj被fi覆蓋，先判斷加入fj后的特征子集的誤分類樣本集MSS（p，q）的數(shù)量是否減少，若減少，將加入fj，否則舍去fj.為選擇性能較優(yōu)的特征子集，應(yīng)盡量選擇互補(bǔ)的特征并舍去沒(méi)有貢獻(xiàn)的被覆蓋特征.

2.4 閾值確定及候選特征子集

當(dāng)一個(gè)特征對(duì)所有子問(wèn)題都沒(méi)有判別能力時(shí)，則認(rèn)為它是無(wú)關(guān)特征.要將所有具有判別能力的特征選擇出來(lái)，閾值的設(shè)置非常重要. 為了剔除無(wú)關(guān)特征，并保留對(duì)子問(wèn)題有貢獻(xiàn)的特征，本文采用動(dòng)態(tài)方法調(diào)整閾值.首先將初始閾值設(shè)為0，以保證所有特征都有被選擇的可能；然后用所有特征的SU 的平均值更新閾值，如果刪除一些無(wú)關(guān)特征不影響分類效果，則繼續(xù)調(diào)整閾值.具體算法流程如下.

算法1 IGSCFS 閾值確定及其候選特征子集的產(chǎn)生

輸入：訓(xùn)練集D，特征集F，誤分類樣本集MSj（p，q），預(yù)設(shè)誤分率ε

輸出：閾值Θ，候選特征子集FC

令FC= ，Θ=[0，…，0]，對(duì)F 中的每一個(gè)特征fj和并令v（jp，q）=1

算法1 首先初始化閾值和判別結(jié)構(gòu)向量，默認(rèn)每個(gè)特征對(duì)每個(gè)子問(wèn)題都有判別能力，并計(jì)算每個(gè)特征的SU 值，將所有特征SU 的平均值作為子問(wèn)題的閾值θC，然后計(jì)算當(dāng)前閾值下的誤分率是否小于預(yù)設(shè)值ε，如果小于ε，則繼續(xù)調(diào)整閾值，否則確定閾值，再根據(jù)閾值得到候選特征子集.經(jīng)多次實(shí)驗(yàn)發(fā)現(xiàn)當(dāng)預(yù)設(shè)誤分率為0.02 時(shí)實(shí)驗(yàn)結(jié)果較好，因此設(shè)ε=0.02.

2.5 基于判別結(jié)構(gòu)互補(bǔ)的特征選擇

由算法1 得到候選特征子集后，根據(jù)特征的判別結(jié)構(gòu)互補(bǔ)進(jìn)行特征選擇，形成目標(biāo)特征子集.為了使所選特征能夠區(qū)分更多的樣本，定義特征的全局分類能力（global classification ability，GCA），特征fj的GCA 為

其中w（p，q）為每個(gè)子問(wèn)題的權(quán)重.設(shè)子問(wèn)題（p，q）包含樣本數(shù)為N（p，q），數(shù)據(jù)集樣本總數(shù)為n，類別數(shù)為k，則

特征的GCA 較高，表明其不僅對(duì)整個(gè)分類任務(wù)具有更強(qiáng)的判別能力，而且對(duì)更多的子問(wèn)題具有判別能力.

在生成目標(biāo)子集之前，先將候選特征按照GCA值降序排列，GCA 值高的特征將被優(yōu)先選擇，并尋找其互補(bǔ)特征.目標(biāo)特征子集選擇算法的具體流程如下.

算法2 基于判別結(jié)構(gòu)互補(bǔ)的特征選擇

輸入：已排序的候選特征子集FC，候選特征子集中特征的判別結(jié)構(gòu)向量集WC，每個(gè)特征對(duì)于每個(gè)子問(wèn)題的誤分類樣本集MSj（p，q）

輸出：目標(biāo)子集Ft

令Ft= ，VC=[0，…，0]

For 每個(gè)子問(wèn)題（p，q）

MS（p，q）=D(p，q)

For 每個(gè)特征fj

將狀態(tài)標(biāo)記置為0，表示尚未被選擇，flagj=0

For 每個(gè)特征fj

If flagj=0

將特征標(biāo)記為候選狀態(tài)t=j

If VC∨Vj=VC

For 每個(gè)被特征fj覆蓋并且flagi= 0 的特

征fi

將特征fi設(shè)置為候選狀態(tài)t=i

首先將目標(biāo)子集與目標(biāo)子集的判別結(jié)構(gòu)向量設(shè)置為空，表示當(dāng)前目標(biāo)子集下沒(méi)有子問(wèn)題被正確分類.然后初始化誤分類樣本集，將每個(gè)子問(wèn)題的初始誤分類樣本集設(shè)為該子問(wèn)題的樣本集，并將每個(gè)特征的狀態(tài)初始化為0，表示所有特征都未被選擇.接下來(lái)開(kāi)始選擇特征，對(duì)于每個(gè)特征fj，判斷將fj加入目標(biāo)子集后目標(biāo)子集的判別結(jié)構(gòu)向量是否變化，如果變化則將該特征加入目標(biāo)子集；若無(wú)變化則判斷是否有特征fi被fj覆蓋，若fi被覆蓋，并且將fi加入目標(biāo)子集后的誤分類樣本數(shù)小于將fj加入目標(biāo)子集后的誤分類樣本數(shù)，則將候選特征設(shè)為fi，重復(fù)上述步驟.若將候選特征加入目標(biāo)子集后的誤分類樣本數(shù)小于未加入時(shí)的誤分類樣本數(shù)，則表明該候選特征與目標(biāo)子集中的某個(gè)特征是互補(bǔ)的，該候選特征也會(huì)被加入目標(biāo)子集.

3 實(shí)驗(yàn)與性能分析

3.1 數(shù)據(jù)集

為驗(yàn)證IGSCFS 算法的正確性與有效性，在6 個(gè)公 開(kāi) 數(shù) 據(jù) 集Forest、Urban、Lung cancer、Arrhythmia、Movement 和Leukemia1 上進(jìn)行實(shí)驗(yàn)，其中：Leukemia1下載自基因表達(dá)數(shù)據(jù)庫(kù)，另外5 個(gè)數(shù)據(jù)集下載自UCI機(jī)器學(xué)習(xí)庫(kù)[18].所選數(shù)據(jù)集均為實(shí)值特征的多類數(shù)據(jù)集，在實(shí)驗(yàn)前均做歸一化處理，數(shù)據(jù)集描述見(jiàn)表1.

表1 數(shù)據(jù)集Tab.1 Data sets

3.2 實(shí)驗(yàn)環(huán)境及設(shè)置

將IGSCFS 與已有的6 種特征選擇算法進(jìn)行比較，包括基于排序的DISR（double input symmetrical relevance）[19]、IG（information gain）[17]、MIFS（mutual information feature selection）[20]、FSSC_SD（feature selection by spectral clustering_spectral clustering based on standard deviation）[21-22]算法，以及基于生成子集的CFS（correlation-based feature selection）[23]和FCBF（fast correlation-based feature selection）[24]算法. 實(shí)驗(yàn)采用十重交叉驗(yàn)證，使用決策樹(shù)（decision tree）、樸素貝葉斯（naive Bayes）和隨機(jī)森林（random forest）3 種分類器進(jìn)行分類，所有實(shí)驗(yàn)均在PyCharm 集成環(huán)境中進(jìn)行.IGSCFS 為子集方法，為方便，排序方法（IG、DISR、MIFS 和FSSC_SD）選擇的特征數(shù)量與IGSCFS 目標(biāo)子集一致.使用分類準(zhǔn)確率、選擇特征的數(shù)量、F1-Score來(lái)評(píng)價(jià)各算法的分類性能.

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

表2～表4 給出了7 種算法分別使用3 種分類器在6 個(gè)數(shù)據(jù)集上的分類準(zhǔn)確率，以及每種算法在6 個(gè)數(shù)據(jù)集上的分類準(zhǔn)確率的平均值，表5 給出了3 種分類器準(zhǔn)確率的平均值，其中：7 種算法在同一數(shù)據(jù)集的最高分類準(zhǔn)確率用黑體標(biāo)出，WTL（win/tie/loss）表示IGSCFS 在6 個(gè)數(shù)據(jù)集上的分類準(zhǔn)確率中高于/等于/小于其他算法的數(shù)量.表6 給出了3 種基于生成子集的算法在6 個(gè)數(shù)據(jù)集上選擇特征的數(shù)量（3 種分類器的平均值）.

由表2～表4 可見(jiàn)，對(duì)于每種分類器，IGSCFS 相比其他算法均在4 個(gè)數(shù)據(jù)集上得到了最高的準(zhǔn)確率，6 個(gè)數(shù)據(jù)集的平均準(zhǔn)確率均為最高.由表5 可見(jiàn)，對(duì)于各算法3 種分類器的平均準(zhǔn)確率，IGSCFS 也在4個(gè)數(shù)據(jù)集上取得最高值，尤其在Arrhythmia 和Leukemia1 數(shù)據(jù)集上，其平均準(zhǔn)確率比排名第2 的算法分別高10%和33%，IGSCFS 在6 個(gè)數(shù)據(jù)集上的平均準(zhǔn)確率為75%，也是7 種算法中最高的.由表6 可見(jiàn)，在6 個(gè)數(shù)據(jù)集上，F(xiàn)CBF 都是選擇特征數(shù)量最少的算法，IGSCFS 在Urban、Lung cancer 和Leukemia1數(shù)據(jù)集上選擇特征的數(shù)量低于CFS，在另外3 個(gè)數(shù)據(jù)集上選擇特征數(shù)量高于CFS.

表2 決策樹(shù)分類器的準(zhǔn)確率Tab.2 Accuracy rates of decision tree classifier

表3 樸素貝葉斯分類器的準(zhǔn)確率Tab.3 Accuracy rates of naive Bayes classifier

表4 隨機(jī)森林分類器的準(zhǔn)確率Tab.4 Accuracy rates of random forest classifier

表5 3 種分類器準(zhǔn)確率的平均值Tab.5 The average accuracy rates of 3 classifiers

表6 3 種算法選擇特征的數(shù)量Tab.6 The number of selected features by 3 algorithms

由表2～表6 可以看出，在特征數(shù)較少的Forest和Lung cancer 數(shù)據(jù)集上，IGSCFS 算法的性能與其他算法相差不多，而在特征數(shù)較多的另外4 個(gè)數(shù)據(jù)集上，除少數(shù)情況外，IGSCFS 的分類準(zhǔn)確率明顯高于其他算法；在與基于排序的算法進(jìn)行比較時(shí)，由于選取和IGSCFS 一樣的特征數(shù)，所以當(dāng)IGSCFS 選擇的特征數(shù)較少時(shí)，IG 和DISR 的性能不是很好；與基于生成子集的算法進(jìn)行比較可以發(fā)現(xiàn)，雖然FCBF 選擇了較少的特征，但是其性能并不好，CFS 選擇的特征數(shù)量在某些數(shù)據(jù)集上與IGSCFS 相差不多，但I(xiàn)GSCFS的分類性能優(yōu)于CFS，尤其在高維數(shù)據(jù)集Leukemia1上，IGSCFS 僅選擇了3 個(gè)特征就達(dá)到了87%的分類準(zhǔn)確率.

在特征選擇算法中，需要得到更高的分類準(zhǔn)確率并選擇盡可能少的特征，本文使用F-Score 評(píng)價(jià)特征選擇算法的效果，F(xiàn)-Score 是準(zhǔn)確率P 和召回率R 的調(diào)和平均，定義為

當(dāng)參數(shù)α=1 時(shí)即為常見(jiàn)的F1-Score.圖1 給出了6 個(gè)數(shù)據(jù)集上7 種算法的F1-Score 的比較結(jié)果.由圖1 可見(jiàn)，IGSCFS 在Movement 上的F1-Score 排在第2 位，在Forest 上的F1-Score 排在第4 位，在其他4 個(gè)數(shù)據(jù)集上的F1-Score 均排在第1 位.綜合來(lái)看，IGSCFS 的效果優(yōu)于其他算法.

圖1 IGSCFS 與其他算法在6 個(gè)數(shù)據(jù)集上的F1-Score 比較Fig.1 Comparison of F1-Score between IGSCFS and other algorithms on 6 datasets

4 結(jié)論

特征選擇是機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域重要的維數(shù)約簡(jiǎn)方法.本文提出一種基于互信息與判別結(jié)構(gòu)互補(bǔ)的特征選擇算法IGSCFS，在6 個(gè)真實(shí)數(shù)據(jù)集上與其他6 種特征選擇算法進(jìn)行比較實(shí)驗(yàn)，結(jié)果表明IGSCFS 可以得到更好的分類準(zhǔn)確率以及較高的F1-Score.在未來(lái)的工作中可以嘗試其他度量特征分類能力的方法，以進(jìn)一步提高分類準(zhǔn)確率.