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

吳自華 周從華

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

1 引言

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

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

本文主要做了三點(diǎn)工作：

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

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

3）對(duì)設(shè)置的兩個(gè)動(dòng)態(tài)權(quán)重進(jìn)行合理性分析，驗(yàn)證它們?cè)诟鞣N情況下不會(huì)對(duì)相關(guān)性計(jì)算出現(xiàn)大的偏差，保證算法對(duì)相關(guān)性計(jì)算的合理性。

2 相關(guān)工作

2.1 信息熵與互信息

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

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

聯(lián)合熵代表兩隨機(jī)變量X，Y同時(shí)發(fā)生的不確定程度。互信息就是基于上述兩個(gè)概念計(jì)算得到，定義如下：

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

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

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

條件相關(guān)性代表特征Xi在特征Xj的條件下對(duì)類別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)劣，公式如下：

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

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

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

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

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

3 MRDW-ICI算法

3.1 ICI的偏向性問題

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

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

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

雖然ICI更加綜合地考慮了特征子集的相關(guān)性計(jì)算，但它也存在著一些問題。例如在同一個(gè)已選特征分別與兩個(gè)候選特征Xi與Xm組成的子集能提供的新分類信息一致的前提下，該公式偏向于與已選特征組成子集后，子集內(nèi)冗余信息更高的那一個(gè)特征。為了方便說明，如圖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組成的集合對(duì)目標(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）時(shí)可知這種情況是存在的。由于ICI（Xi）= ICI（Xm）且I（Xm；Xj；C）>I（Xi；Xj；C），說明Xj與Xm組成的子集和Xj與Xi組成的子集在分類能力一致的前提下，前兩個(gè)特征組成的冗余信息大于后兩個(gè)特征組成的冗余信息。因此基于“最大相關(guān)-最小冗余”原則，Xi應(yīng)該優(yōu)于Xm。但在ICI 的標(biāo)準(zhǔn)下，Xi與Xm的評(píng)價(jià)值卻是相同的。換句話說，在新分類能力［6］相同時(shí)，存在ICI 會(huì)更偏向于高冗余特征的問題。

3.2 算法原理

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

由于Xi是待選特征，故I（Xi；C）的值是動(dòng)態(tài)變化的。而Xj是已選特征，故可將I（Xj；C）看做是一個(gè)常數(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）增大的時(shí)候，IC（Xi；Xj）減小。當(dāng)I（Xj；C|Xi）減小的時(shí)候，IC（Xi；Xj）增大。所以可將最小化冗余信息IC（Xi；Xj）的求解等價(jià)轉(zhuǎn)換為最大化I（Xj；C|Xi）的求解。

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

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

不難發(fā)現(xiàn)，式（18）實(shí)際上是對(duì)ICI 公式的左右兩項(xiàng)分別加了兩個(gè)動(dòng)態(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。又因?yàn)镮（Xi；C）≤I（Xi，Xj；C），所以有ω1≤ω2。 綜上可得，0 ≤ω1≤ω2≤1。

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

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

雖然MRDW-ICI 算法實(shí)現(xiàn)了在子集新分類能力一致時(shí)，讓評(píng)價(jià)函數(shù)偏向低冗余特征這一目的。但若權(quán)重ω1,ω2設(shè)置不合理，例如無限放大低冗余項(xiàng)在評(píng)價(jià)函數(shù)中的占比，那么反而會(huì)造成算法對(duì)子集相關(guān)性的計(jì)算失誤。本節(jié)基于候選特征與已選特征的關(guān)系對(duì)兩權(quán)重的合理性進(jìn)行分析，若計(jì)算結(jié)果與ICI 差距不大，則證明沒有因?yàn)樘砑觿?dòng)態(tài)權(quán)重的原因而導(dǎo)致對(duì)子集相關(guān)性的計(jì)算出現(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）時(shí)，因?yàn)棣?=，且有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，此時(shí)I（Xi，Xj；C）> I（Xm，Xj；C），可得ω2>，ω1=，于是有J（X）i>J（Xk），結(jié)果和ICI一致。反之（IXi；C|X）j

兩候選特征都與已選特征互相獨(dú)立：

此時(shí)I（Xi；C|Xj）=I（Xi；C），I（Xj；C|Xi）=I（Xj；C）。于是式（19）可化簡(jiǎn)為如下形式：

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

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

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

MRDW-ICI算法步驟：

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

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

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

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

4.2 實(shí)驗(yàn)評(píng)價(jià)指標(biāo)

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

表2 混淆矩陣

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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