基于最小冗余動態(tài)加權(quán)的信息論特征選擇算法*

吳自華 周從華

（江蘇大學(xué)計算機(jī)科學(xué)與通信工程學(xué)院 鎮(zhèn)江 212013）

1 引言

特征選擇（Feature Selection）是在保持原始數(shù)據(jù)準(zhǔn)確率的同時，顯著降低特征空間的維數(shù)的過程。特征子集的篩選也可以看作是對特征空間的搜索。其中搜索方向和搜索起點至關(guān)重要?；谒阉鞣较?，一般有三大搜索策略：完全搜索、順序搜索、啟發(fā)式搜索［1~2］。完全搜索實際上就是對特征集合的窮舉搜索，準(zhǔn)確率高但工作量大。順序搜索包含序列前向搜索和序列后向搜索。序列前向搜索首先初始化特征子集S為空集，依次從原始特征集合F中篩選一個特征Xi，使得評價函數(shù)J（Xi）取最大值，將此特征Xi加入特征子集S直至達(dá)到終止條件。序列后向搜索則與此相反。應(yīng)用較多的是啟發(fā)式搜索，它包含我們熟知的粒子群等群智能算法。啟發(fā)式搜索降低了時間復(fù)雜度，但在后期容易陷入局部最優(yōu)值。

在特征選擇領(lǐng)域中，基于互信息的特征選擇算法占有重要地位?；バ畔⑹且环N衡量兩個隨機(jī)變量相關(guān)性的方法。在已知一個變量的前提下，互信息代表根據(jù)已知變量的信息得到的另一個變量不確定性減小的程度。由于這種關(guān)聯(lián)性，互信息在特征選擇領(lǐng)域經(jīng)常被用來計算特征與類別的相關(guān)性或特征與特征之間的冗余性。

本文主要做了三點工作：

1）通過一個例子，詳細(xì)說明ICI［6］公式中存在的在新分類信息一致的條件下，該公式有可能偏向高冗余特征的問題。

2）針對上述問題，提出兩個基于類別相關(guān)性的動態(tài)權(quán)重，通過配置權(quán)重從而間接減少冗余信息在評價函數(shù)中的占比，在不對相關(guān)性計算出現(xiàn)大偏差的前提下減小ICI對高冗余特征的偏向性。

3）對設(shè)置的兩個動態(tài)權(quán)重進(jìn)行合理性分析，驗證它們在各種情況下不會對相關(guān)性計算出現(xiàn)大的偏差，保證算法對相關(guān)性計算的合理性。

2 相關(guān)工作

2.1 信息熵與互信息

信息熵可看作是對隨機(jī)變量不確定程度的衡量，其計算方式如下：

若離散變量X共有n種取值，p(xi)代表每種取值的概率。除單個隨機(jī)變量外，還有關(guān)于兩個隨機(jī)變量的聯(lián)合熵，定義如下：

聯(lián)合熵代表兩隨機(jī)變量X，Y同時發(fā)生的不確定程度?；バ畔⒕褪腔谏鲜鰞蓚€概念計算得到，定義如下：

I(X;Y)代表已知變量X的條件下，變量Y不確定性減少的程度?；バ畔⒖捎脕砗饬績蓚€隨機(jī)變量的相似程度。一般將特征Xi與目標(biāo)類別C的互信息稱作特征的相關(guān)性：

相關(guān)性越大的特征對目標(biāo)類別的識別能力越強(qiáng)。特征Xi與特征Xj之間的互信息稱為冗余性：

互信息中還對條件相關(guān)性做出了如下定義，Xi，Xj代表候選特征，C代表目標(biāo)類別：

條件相關(guān)性代表特征Xi在特征Xj的條件下對類別C的相關(guān)性。

2.2 互信息特征選擇算法

基于互信息的特征選擇算法的任務(wù)是選出與目標(biāo)類別相關(guān)性最大的特征子集，子集與類別的相關(guān)性可用如下公式表示：

求得能使I（S；C）取最大值的特征子集S 即是特征選擇算法的目標(biāo)。

Battiti在1994 年提出MIFS［3］算法，該算法用候選特征的相關(guān)性減去特征之間的冗余性來度量特征子集的優(yōu)劣，公式如下：

針對MIFS中β參數(shù)難以確定的問題，mRMR［4］采用平均冗余度作為衡量候選特征與當(dāng)前特征子集的冗余性，設(shè)，標(biāo)準(zhǔn)如下：

除了考慮單個特征對類別的相關(guān)性外，Yang等［5］提出利用聯(lián)合互信息衡量候選特征對目標(biāo)類別的相關(guān)性：

與以上經(jīng)典的特征選擇算法不同。也有不同風(fēng)格的互信息特征選擇算法被提出，例如Zeng［5］提出使用一種動態(tài)交互因子IW（Xi，Xj）來衡量兩特征間的關(guān)系，對IW（Xi，Xj）的定義如下：

該算法依據(jù)IW（Xi，Xj）的取值范圍來判定兩特征究竟是冗余還是交互關(guān)系，相對傳統(tǒng)的計算方法是較為新穎的思路。

綜上所述，基于互信息的特征選擇算法大多圍繞著“最大相關(guān)-最小冗余”原則來設(shè)計評價函數(shù)。在提高子集對類別相關(guān)性的同時，也要注意降低子集內(nèi)部的冗余性，避免因為子集內(nèi)部的高冗余性而降低算法的準(zhǔn)確率。

3 MRDW-ICI算法

3.1 ICI的偏向性問題

大多數(shù)互信息特征選擇算法通常采用如下公式計算特征子集與類別的相關(guān)性，F(xiàn)代表待選特征的集合：

考慮到在已選特征不變的條件下，不同的候選特征與已選特征組成的集合對目標(biāo)類別的相關(guān)性是會變化的。Qun Wang 等在2017 年提出了ICI［6］度量公式，公式如下：

從公式中可以看出，ICI 是兩個條件相關(guān)項之和。該公式不僅考慮到了候選特征在已選特征的條件下對目標(biāo)的相關(guān)性，還考慮到了已選特征在不同候選特征的條件下對目標(biāo)分類信息產(chǎn)生的變化。

雖然ICI更加綜合地考慮了特征子集的相關(guān)性計算，但它也存在著一些問題。例如在同一個已選特征分別與兩個候選特征Xi與Xm組成的子集能提供的新分類信息一致的前提下，該公式偏向于與已選特征組成子集后，子集內(nèi)冗余信息更高的那一個特征。為了方便說明，如圖1、圖2所示。

圖1

圖2

Xi與Xm代表候選特征，Xj代表已選特征。圖1中a，d，e分別代表I（Xj；C|Xi），I（Xi；C|Xj），I（Xi；Xj|C）。圖2 中f，h，i分別代表I（Xj；C|Xm），I（Xm；C|Xj），I（Xm；Xj|C）。為方便表示，本采用文獻(xiàn)［8］中的概念，分別用I（Xi；Xj；C）表示b區(qū)域，I（Xm；Xj；C）表示g區(qū)域。

若a+d=f+h，這說明候選特征Xi，Xm各自與已選特征Xj組成的集合對目標(biāo)類別的相關(guān)性是一致的。即有：

但通過觀察圖1中的b區(qū)域和圖2中的g區(qū)域，可以發(fā)現(xiàn)明顯有g(shù)>b，即有I（Xm；Xj；C）> I（Xi；Xj；C）。在H（Xm）>H（Xi）時可知這種情況是存在的。由于ICI（Xi）= ICI（Xm）且I（Xm；Xj；C）>I（Xi；Xj；C），說明Xj與Xm組成的子集和Xj與Xi組成的子集在分類能力一致的前提下，前兩個特征組成的冗余信息大于后兩個特征組成的冗余信息。因此基于“最大相關(guān)-最小冗余”原則，Xi應(yīng)該優(yōu)于Xm。但在ICI 的標(biāo)準(zhǔn)下，Xi與Xm的評價值卻是相同的。換句話說，在新分類能力［6］相同時，存在ICI 會更偏向于高冗余特征的問題。

3.2 算法原理

上一節(jié)明確了ICI公式在已選特征不變的條件下，子集新分類能力一致時會偏向高冗余特征這一問題。本節(jié)引入兩個基于特征相關(guān)性的動態(tài)權(quán)重，通過間接求解最小冗余的方式來降低特征子集的冗余度，從而改善ICI對高冗余特征的偏向性。

由于Xi是待選特征，故I（Xi；C）的值是動態(tài)變化的。而Xj是已選特征，故可將I（Xj；C）看做是一個常數(shù)。由信息論推導(dǎo)可得：

為方便表示，這里用IC（Xi；Xj）代表I（Xi；Xj）-I（Xi；Xj|C）。即有：

不難發(fā)現(xiàn)在I（Xj；C）是常數(shù)的前提下，I（Xj；C|Xi）的大小和IC（Xi；Xj）成反比。即當(dāng)I（Xj；C|Xi）增大的時候，IC（Xi；Xj）減小。當(dāng)I（Xj；C|Xi）減小的時候，IC（Xi；Xj）增大。所以可將最小化冗余信息IC（Xi；Xj）的求解等價轉(zhuǎn)換為最大化I（Xj；C|Xi）的求解。

因此對于I（Xi；C|Xj）+I（Xj；C|Xi），可將左項I（Xi；C|Xj）看作衡量Xi的新分類信息的項式。將右項I（Xj；C|Xi）看成衡量Xi與已選特征Xj冗余性的項式。I（Xi；C|Xj）越高，代表Xi與類別C的獨立相關(guān)性［6］越強(qiáng)。在已選特征不變的條件下，針對不同的候選特征Xi，若I（Xj；C|Xi）越高，既代表Xj的新分類能力越高也代表Xi與Xj的冗余信息越低。

為了使評價函數(shù)在新分類能力一致時更偏向低冗余特征，不妨提高I（Xj；C|Xi）在評價函數(shù)中的占比?；诖怂悸?，本文提出MRDW-ICI（Minimal Redundancy Dynamic Weight-ICI）算法，算法公式如下：

不難發(fā)現(xiàn)，式（18）實際上是對ICI 公式的左右兩項分別加了兩個動態(tài)權(quán)重ω1和ω2。由信息論可知，0 ≤I（Xj；C）≤H（C），0 ≤I（Xi，Xj；C）≤H（C），所以有0 ≤ω1≤1，0 ≤ω2≤1。又因為I（Xi；C）≤I（Xi，Xj；C），所以有ω1≤ω2。 綜上可得，0 ≤ω1≤ω2≤1。

因為ω1≤ω2，所以當(dāng)I（Xj；C|Xi）=I（Xi；C|Xj）時，I（Xj；C|Xi）在整個評價函數(shù)中的占比提高了，也就達(dá)到了評價函數(shù)在子集新分類能力一致時，偏向低冗余特征的目的。

3.3 權(quán)重合理性分析

雖然MRDW-ICI 算法實現(xiàn)了在子集新分類能力一致時，讓評價函數(shù)偏向低冗余特征這一目的。但若權(quán)重ω1,ω2設(shè)置不合理，例如無限放大低冗余項在評價函數(shù)中的占比，那么反而會造成算法對子集相關(guān)性的計算失誤。本節(jié)基于候選特征與已選特征的關(guān)系對兩權(quán)重的合理性進(jìn)行分析，若計算結(jié)果與ICI 差距不大，則證明沒有因為添加動態(tài)權(quán)重的原因而導(dǎo)致對子集相關(guān)性的計算出現(xiàn)較大偏差。設(shè)Xi，Xm為候選特征，Xj為已選特征，，分析如下：

兩候選特征都與已選特征存在冗余：

1）若I（Xi；C|X）j=I（Xm；C|X）j，當(dāng)（IXj；C|X）i>（IXj；C|Xm）時，因為ω1=，且有I（Xi，Xj；C）> I（Xm，Xj；C），故ω2>，于是J（X）i>J（Xm），結(jié)果和ICI 一致。反之當(dāng)I（Xj；C|X）iI（Xm；C|X）j，此時I（Xi，Xj；C）> I（Xm，Xj；C），可得ω2>，ω1=，于是有J（X）i>J（Xk），結(jié)果和ICI一致。反之（IXi；C|X）j

兩候選特征都與已選特征互相獨立：

此時I（Xi；C|Xj）=I（Xi；C），I（Xj；C|Xi）=I（Xj；C）。于是式（19）可化簡為如下形式：

因I（Xj；C）為常數(shù)，不難發(fā)現(xiàn)式（20）實際是一個關(guān)于I（Xi；C）的線性函數(shù)，因此J（Xi）隨I（Xi；C）單調(diào)遞增。當(dāng)I（Xi）>I（Xm）時，有J（Xi）>J（Xm），與ICI結(jié)論一致。

其余情況下，MRDW-ICI 算法較之ICI 會更偏向低冗余特征。 但由于0 ≤ω1≤ω2≤1 ，故0 ≤ω2-ω1<1 。因此算法對低冗余的偏向值(ω2-ω1) ×I（Xj；C|X）i小于I（Xj；C|X）i本身，且實際來說ω2-ω1的值通常較小，因此該偏向值并不會被無限放大，處在合理可控的范圍內(nèi)。

算法詳細(xì)流程如下：

MRDW-ICI算法步驟：

輸入：數(shù)據(jù)集D={x1,x2,…,xm} 、最優(yōu)特征子集數(shù)目k、目標(biāo)類別C、待選特征集合F

4 實驗

4.1 實驗環(huán)境及配置

硬件配置：CPU：Intel（R）Core（TM）i5-8250U（1.60GHz~1.80GHz） ，GPU： NVIDIA GeForce MX150，內(nèi)存8GB，硬盤256G。軟件配置：Windows10操作系統(tǒng)（64位），Python3.7.0版本。

實驗所用原始數(shù)據(jù)來自無錫市兒童醫(yī)院的血常規(guī)指標(biāo)，共有兩份數(shù)據(jù)集。分別是體檢數(shù)據(jù)集TG1479 和哮喘數(shù)據(jù)集XC356。兩份數(shù)據(jù)集均對哮喘的輕癥與重癥做了標(biāo)注，即樣本類別已經(jīng)標(biāo)注完畢。詳見表1。

表1 數(shù)據(jù)集描述

4.2 實驗評價指標(biāo)

本文使用分類實驗常用的評價指標(biāo)，即預(yù)測的準(zhǔn)確率（Accuracy）及F1值對分類結(jié)果進(jìn)行評價，分類結(jié)果的“混淆矩陣”如表2所示。

表2 混淆矩陣

F1 值是由查準(zhǔn)率和查全率確定的，這三者的公式根據(jù)上表分類結(jié)果有如下定義：

4.3 數(shù)據(jù)預(yù)處理

本文數(shù)據(jù)集內(nèi)的數(shù)據(jù)皆是連續(xù)值，對于連續(xù)值，在計算互信息的時候需要知曉每個特征對應(yīng)的函數(shù)分布，為了簡化互信息的計算，本文采用數(shù)據(jù)離散化的方法將連續(xù)數(shù)據(jù)轉(zhuǎn)變?yōu)殡x散數(shù)據(jù)，方便后續(xù)的計算。

鑒于本文數(shù)據(jù)集內(nèi)同一特征下數(shù)據(jù)取值范圍較廣，為了計算簡便，本文采用傳統(tǒng)的5 箱等寬法將同一特征劃分為5 個不同的取值，從而完成數(shù)據(jù)的離散化工作。

4.4 實驗結(jié)果分析

為評估MRDW-ICI算法的篩選效果，本實驗采用經(jīng)典的特征選擇算法MIFS，mRMR，CIFE 及ICI與其進(jìn)行對比。MIFS 中的β取1。選擇MIFS，mRMR，CIFE這三種算法是因為這三種算法既是公認(rèn)的較為經(jīng)典的互信息特征選擇算法，同時這三種算法也都對特征子集內(nèi)的冗余性做了考慮。較之以只考慮候選特征對目標(biāo)類別相關(guān)性的算法，明顯前面三者要更為優(yōu)秀。

實驗選用在二分類問題上有較好表現(xiàn)的SVM分類器，分別評估以上五種特征選擇算法篩選出的特征子集的分類效果。在相同特征數(shù)目的前提下，準(zhǔn)確率越高，說明該特征子集對目標(biāo)類別的相關(guān)性越強(qiáng)。

為降低數(shù)據(jù)集因為分為訓(xùn)練集和驗證集帶來的隨機(jī)性影響，本實驗采用十折交叉驗證法。通過對比相同特征數(shù)目下的準(zhǔn)確率以及對比各個特征選擇算法篩選出的特征子集的最高準(zhǔn)確率來驗證本文提出的算法的有效性。實驗結(jié)果如下，圖3 和圖4是兩數(shù)據(jù)集TG1470與XC356在SVM 分類器下的準(zhǔn)確率對比。

圖3 TG1470數(shù)據(jù)集上的SVM分類準(zhǔn)確率

圖4 XC356數(shù)據(jù)集上的SVM分類準(zhǔn)確率

分析上面兩圖可知，特征子集在特征數(shù)目遞增的情況下，其與類別的相關(guān)性大體呈現(xiàn)出先增大后減小這樣的一種趨勢。子集的選取比例在10%的時候準(zhǔn)確率最低。在圖3 中MIFS 在比例達(dá)到70%的情況下準(zhǔn)確率達(dá)到最高值79.5%，剩余的四個算法均在60%的比例下即可達(dá)到最高值。其中MRDW-ICI 算法的準(zhǔn)確率最高達(dá)到83%。在達(dá)到最高值后，除MIFS 外，剩余4 種算法的準(zhǔn)確率均在選取比例超過60%后呈現(xiàn)不同的下降趨勢。且圖3中特征選取比例在大于70%后，ICI 的準(zhǔn)確率再度逐漸超過本算法。

分析圖3 發(fā)現(xiàn)，在特征選取比例在10%的條件下，ICI的準(zhǔn)確率高于MRDW-ICI，這說明此時子集內(nèi)高相關(guān)特征的收益大于低冗余特征帶來的收益。 在選取比例為30% ~70% 的條件下，MRDW-ICI 的準(zhǔn)確率均在ICI 之上，這說明在剔除子集內(nèi)的冗余信息后，子集對目標(biāo)類別的相關(guān)性獲得了顯著增長。

表3 是數(shù)據(jù)集在SVM 分類器下的最高準(zhǔn)確率和F1值。

表3 5種特征選擇算法的準(zhǔn)確率及F1值

由上表可知，MRDW-ICI算法對比其余四種算法均能取得不錯的分類效果。其在TG1439數(shù)據(jù)集和XC356 數(shù)據(jù)集的最高分類準(zhǔn)確率分別是83.23%，81.93%。不僅準(zhǔn)確率有所提升，且其在對應(yīng)的F1 值上分別提高2.54%和4.42%。這說明MRDW-ICI算法篩選出來的特征子集較ICI不僅相關(guān)性上升，且具有更強(qiáng)的穩(wěn)定性。

5 結(jié)語

本文針對ICI公式在新分類能力一致時可能會偏向高冗余特征的問題進(jìn)行改進(jìn)。通過引入兩個基于相關(guān)性的動態(tài)權(quán)重，從而間接減少類內(nèi)冗余信息在評價函數(shù)中的占比，降低ICI 公式在新分類信息相等時對高冗余特征的偏向性，并將其應(yīng)用到篩選最優(yōu)特征子集中。下一步的工作是考慮如何基于數(shù)據(jù)的分布特點提高分類器的精度，使得特征子集的分類效果能進(jìn)一步提升。