潘 果

PAN Guo

1.湖南大學(xué) 信息科學(xué)與工程學(xué)院，長(zhǎng)沙 410082

2.湖南現(xiàn)代物流職業(yè)技術(shù)學(xué)院 物流信息系，長(zhǎng)沙 410131

1.College of Information Science and Engineering,Hunan University,Changsha 410082,China

2.Logistics Information Department,Hunan Vocational College of Modern Logistics,Changsha 410131,China

在現(xiàn)代大量的數(shù)據(jù)特征分析中，有些特征是冗余的，影響算法的性能和效率。因此需要一種高效的特征選擇算法，將輸入特征集去冗余，可以減少特征預(yù)處理的成本，降低構(gòu)建分類器的復(fù)雜度，提升分類器的精度。

互信息（Mutual Information，MI）是兩個(gè)隨機(jī)變量之間相關(guān)性的一個(gè)信息度量，對(duì)稱且非負(fù)，當(dāng)且僅當(dāng)變量獨(dú)立時(shí)為零。之前有研究人員研究基于MI概念構(gòu)建出高效的特征選擇算法[1-8]，本文基于MI概念提出一種有效的特征選擇算法，對(duì)現(xiàn)有的算法作出了改進(jìn)，使其得到更廣泛的應(yīng)用、具有更好的分類性能，并且降低了計(jì)算復(fù)雜度。

文獻(xiàn)[3]給出了兩個(gè)特征選擇函數(shù)需滿足的基本約束條件，提出了一種構(gòu)造高性能特征選擇的通用方法，依此方法構(gòu)造了一個(gè)新的特征選擇函數(shù)KG（Knowledge Gain），并對(duì)此方法進(jìn)行實(shí)驗(yàn)分析。

文獻(xiàn)[4]提出了一種基于互信息的無(wú)監(jiān)督的特征選擇方法（UFS-MI），使用一種綜合考慮相關(guān)度和冗余度的特征選擇標(biāo)準(zhǔn)UmRMR（無(wú)監(jiān)督最小冗余最大相關(guān)）來(lái)評(píng)價(jià)特征的重要性。

文獻(xiàn)[5]研究了基于互信息的特征選擇算法（MIFS）和 MIFS-U算法（U：信息分布均勻），這兩個(gè)算法都涉及到了用于表達(dá)輸入特征之間冗余度的冗余度參數(shù)β。如果β=0，則不考慮輸入特征之間的MI，算法根據(jù)單個(gè)輸入特征和類之間的MI依次選擇特征。然而，如果選擇的β太大，算法就只包含輸入特性之間的關(guān)系，不包括單個(gè)輸入特性和類之間的關(guān)系[9]，此時(shí)再調(diào)整參數(shù)β將會(huì)變得很困難。

“最大關(guān)聯(lián)度最小冗余度分析”（mRMR）方法[4]是MIFS算法的一個(gè)特例，其中β=1/|S|。這個(gè)方法比MIFS和MIFS-U算法有更多的優(yōu)點(diǎn)，其中不需要確定參數(shù)β的值。這在實(shí)踐中有重要意義，因?yàn)樵趯?shí)際問(wèn)題中，尚且沒(méi)有明確的定義如何確定參數(shù)β的值。

“正則化互信息特征選擇”（NMIFS）算法[6]是利用經(jīng)過(guò)最小化兩個(gè)特征熵得到正則化MI，將正則化MI的平均值來(lái)衡量單個(gè)特征和選擇的特征子集的冗余度。文獻(xiàn)[6]提出的NMIFS算法是對(duì)MIFS、MIFS-U和mRMR算法的改進(jìn)，NMIFS算法也不需要確定參數(shù)β的值。

基于上述分析，提出了一種基于互信息的輸入特征選擇算法，該算法是對(duì)NMIFS算法的一種改進(jìn)。大多數(shù)現(xiàn)有算法僅使用單個(gè)特征與目標(biāo)類之間的互信息，通常要求確定冗余度參數(shù)β，影響算法的實(shí)現(xiàn)效率。與現(xiàn)有算法不同的是，在對(duì)連續(xù)或離散特征進(jìn)行選擇時(shí)，本文算法使用輸入特征的組合與類之間的互信息代替單一特征之間的互信息，利用包含兩個(gè)特征的特征空間來(lái)正則化特征選擇的互信息，無(wú)需對(duì)參數(shù)β作要求，并且運(yùn)用了前向選擇的特征空間互信息理論，擴(kuò)大了算法的應(yīng)用范圍及選擇能力。此外，本文還闡述了一種解決MI在計(jì)算中從連續(xù)特征變?yōu)殡x散特征時(shí)轉(zhuǎn)化問(wèn)題的通用算法，一定程度上提高了算法的實(shí)現(xiàn)效率。本文算法僅考慮包含兩個(gè)特征的特征空間，其實(shí)，只要數(shù)據(jù)大小合理，該算法可以擴(kuò)展到包含兩個(gè)以上特征的特征空間。通過(guò)兩組實(shí)驗(yàn)驗(yàn)證了本文算法的有效性及穩(wěn)定性。

1 相關(guān)工作

1.1 互信息

MI是用來(lái)測(cè)量隨機(jī)變量之間的依賴性，對(duì)稱且非負(fù)，當(dāng)且僅當(dāng)變量獨(dú)立時(shí)其值為零。定義兩個(gè)離散隨機(jī)變量 U=(u1，u2，…，uk)和 V=(v1，v2，…，vd)之間的互信息[10]為：

其中(u1，u2，…，uk)和(v1，v2，…，vd)分別為離散變量 U和V的值，p(u，v)是一個(gè)聯(lián)合密度函數(shù)，p(u)和 p(v)是邊緣密度函數(shù)[11]。

等式（1）中特征 V=(v1，v2，…，vd)之間和類 C=(c1，c2，…，ck)的MI可以表達(dá)為：

為了方便使用公式（2），需將所有的連續(xù)變量轉(zhuǎn)化為離散特征。

1.2 MIFS、MIFS-U、mRMR和NMIFS算法

1.2.1 MIFS算法

MIFS[1]算法是僅使用兩個(gè)變量之間的MI（單個(gè)變量和其他單個(gè)變量之間的MI）的一種貪心策略選擇算法。算法中涉及到的參數(shù)β為冗余度參數(shù)，用于近似確定輸入特征之間的冗余度，MIFS算法描述如下：

（1）初始化：設(shè)置 F←n個(gè)特征的初始集，F(xiàn)={f1，f2，…，fn}，初始選擇特征集 S←{}。

（2）為輸出類C和每個(gè)輸入特征計(jì)?fi∈F計(jì)算式（2）中的 I(Cfi)（注意式（2）中 fi=V）。

（3）第一個(gè)特征的選擇：最大化 I(Cfi)，找到特征fi，設(shè)置 F←F{fi}，S←{fi}，其中 F{fi}意思是從 F中刪除 fi。

（4）貪心選擇：重復(fù)直至選擇到期望的特征數(shù)目。

①計(jì)算特征之間的MI：

對(duì)所有的特征(fi，fs)，其中 fi∈F，fs∈S ，計(jì)算I(fi，fs)。

②選擇下一個(gè)特征：

1.2.2 MIFS-U算法

MIFS-U[1]算法是對(duì)MIFS算法的改進(jìn)。該算法只將步驟（4）中的②變?yōu)槿缦拢?/p>

1.2.3 mRMR算法

mRMR[4]算法是對(duì)MIFS-U算法的改進(jìn)。該算法只將步驟（4）中的②變?yōu)槿缦拢?/p>

1.2.4 NMIFS算法

2 本文提出的算法

本文提出的算法利用包含兩個(gè)特征的特征空間來(lái)正則化特征選擇的互信息，稱為：“正則化特征選擇互信息-特征空間2”（NMIFS-FS2）。NMIFS-FS2算法使用輸入特征組合與類之間的MI來(lái)代替NMIFS算法中單個(gè)特征之間的MI。本算法中不需要確定參數(shù)β的值。

NMIFS-FS2算法將NMIFS算法步驟（4）中②修改如下：

②最大化

選擇特征 fi∈F，設(shè)置F←F{fi}、S←S∪{fi}。

接下來(lái)，給出特征空間F計(jì)算信息的概率空間的過(guò)程。假設(shè)每個(gè)個(gè)體特征 fi有ni個(gè)離散值(v1，v2，…，vni)，每個(gè)離散值vj對(duì)應(yīng)的概率為 pvj。每個(gè)個(gè)體特征 fi的信息概率空間為：

特征空間F對(duì)應(yīng)的值是從所有個(gè)體特征中選擇出的離散值的組合，特征空間F的信息概率空間可表示為其中表示特征空間F的值，是值對(duì)應(yīng)的概率值。例如，數(shù)據(jù)集 A包含兩個(gè)特征 f1和 f2，值為(v1，v2)=(0，1)，數(shù)據(jù)集 A為：

使用式（2）和式（4）選擇的前3個(gè)特征不同于使用式（3）選擇的其余特征，因此，使用這兩個(gè)式子無(wú)法產(chǎn)生同尺度的G值。

3 神經(jīng)網(wǎng)絡(luò)（NN）驗(yàn)證本文算法

本文中應(yīng)用了一個(gè)單層NN[12]來(lái)測(cè)試和比較這些特征選擇算法的效果。NN輸入是基于變量的線性組合，輸入變量要經(jīng)非線性激活函數(shù)轉(zhuǎn)化為線性，因此需要為第i個(gè)模式最終預(yù)測(cè)輸出構(gòu)建這些激活函數(shù)的輸出的線性組合，對(duì)于一個(gè)有H個(gè)隱藏單元神經(jīng)網(wǎng)絡(luò)的M維輸入向量[13]，神經(jīng)網(wǎng)絡(luò)的輸出可寫(xiě)為：

通過(guò)初始化W（可能是隨機(jī)選擇的）來(lái)最小化誤差函數(shù)E(W)，然后通過(guò)在W-空間內(nèi)，在E(W)減小最迅速的方向上（-?WE方向）移除一個(gè)短距離η（學(xué)習(xí)速率參數(shù)）來(lái)更新權(quán)重向量。迭代這個(gè)過(guò)程，如式（7），最終權(quán)重W 向量會(huì)收斂到一個(gè)點(diǎn)上，此時(shí)E是最小的。式（5）中要使用W 值的這個(gè)點(diǎn)，使用訓(xùn)練數(shù)據(jù)構(gòu)建模型（5），使用驗(yàn)證數(shù)據(jù)確定權(quán)重和式（5）中隱藏單元的數(shù)目，使用測(cè)試數(shù)據(jù)測(cè)試模型（5）的性能。

多路輸出NN的結(jié)構(gòu)[14]如圖1所示。

圖1 多路輸出神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

4 實(shí)驗(yàn)結(jié)果

本章給出了兩個(gè)實(shí)驗(yàn)測(cè)試實(shí)例來(lái)評(píng)估本文提出的算法。第一個(gè)實(shí)驗(yàn)實(shí)例是一個(gè)定義好的問(wèn)題，第二個(gè)實(shí)驗(yàn)實(shí)例取自一個(gè)實(shí)際問(wèn)題的心臟數(shù)據(jù)集。

第一個(gè)實(shí)驗(yàn)中，遵循文獻(xiàn)[1]建議的參數(shù)β取值范圍（β在0.3到1范圍內(nèi)），在0.3到1之間選擇β值，第二個(gè)實(shí)驗(yàn)中β值選為1，與文獻(xiàn)[10]中MIFS和MIFS-U算法的值一樣。實(shí)驗(yàn)1使用不同β值的目的是輸出特征排序的所有概率，因?yàn)榻o定問(wèn)題的最佳β值是未知的。MIFS和MIFS-U算法表明β接近1時(shí)，冗余度特征的權(quán)重會(huì)增加，這意味著算法更多地考慮了特征之間的關(guān)系，而特征和輸出之間的關(guān)系考慮得較少，反之亦然。

4.1 實(shí)驗(yàn)1給定的問(wèn)題（LIC1）

定義LIC1問(wèn)題為：

輸入特征空間為：

設(shè)置in6為一個(gè)虛擬的或無(wú)關(guān)的特性，設(shè)置in7為in7=x1-x2，重疊了特征 x1和x2。則冗余特征是 x1和 x2或者是特征in7，由于in7是 x1和 x2的組合，所以將 x1和x2作為冗余特征時(shí)，in7是更好的選擇。in8=x1×x2和in9=y1×y2也是冗余特征，盡管特征in8和in9與x1、x2、y1和 y2有關(guān)系，但是它們與類沒(méi)有任何關(guān)系，所以這個(gè)分類問(wèn)題的最優(yōu)特征空間為 [y1、y2、length、in7]或 [x1，x2，y1，y2、length]。特征空間 [y1、y2、length、in7]比特征空間[x1，x2，y1，y2、length]更好，因?yàn)樽顑?yōu)特征空間應(yīng)包含盡可能少的特征，同時(shí)具有最多的信息量。

隨機(jī)生成構(gòu)建輸入特征F(9)的500個(gè)數(shù)據(jù)樣本集，每個(gè)輸入特征均勻分布在[0，1]范圍內(nèi)，然后正確配對(duì)分類每組輸入值，2或者1，根據(jù)式（8）中定義的函數(shù)。將訓(xùn)練數(shù)據(jù)集和測(cè)試數(shù)據(jù)集的每個(gè)連續(xù)輸入特征都轉(zhuǎn)換成有相同標(biāo)號(hào)大小的離散特征，這里標(biāo)號(hào)大小選為6。依照1.2節(jié)描述的算法進(jìn)行特征排序，將第2章中描述的算法應(yīng)用于這個(gè)數(shù)據(jù)集，特征選擇結(jié)果列于表1。

從表1可以看出，表1中列出的所有算法都能正確選擇前2個(gè)特征 f5(length)和 f7(in7)，然而只有本文提出的NMIFS-FS2能正確選擇第3和第4個(gè)特征，f3=y1和f4=y2。本文提出的NMIFS-FS2算法的最優(yōu)特征空間為 [f5，f7，f3，f4]，它是所有算法唯一能正確識(shí)別最優(yōu)特征空間的算法。

表1 基于不同互信息算法的特征排序

4.2 實(shí)驗(yàn)2單光子發(fā)射計(jì)算機(jī)斷層成像術(shù)（SPECT）心臟數(shù)據(jù)

這個(gè)數(shù)據(jù)庫(kù)取自加州大學(xué)歐文分校的機(jī)器學(xué)習(xí)庫(kù)，數(shù)據(jù)庫(kù)中267個(gè)SPECT病人的圖像數(shù)據(jù)集[15]描述了心臟診斷（SPECT）圖像。對(duì)此進(jìn)行處理提取能夠描述原始SPECT圖像的特征，最終獲得22個(gè)特征(f1～f22)，作為本實(shí)驗(yàn)的基礎(chǔ)。將每個(gè)病人分類成兩組：正常和異常，由于數(shù)據(jù)集僅包含55個(gè)正常病例和212個(gè)異常病例，為了維持平衡，隨機(jī)選擇30個(gè)正常案例和30個(gè)異常案例分別作為訓(xùn)練數(shù)據(jù)集，剩余的207組數(shù)據(jù)作為測(cè)試數(shù)據(jù)。使用各種特征選擇算法從訓(xùn)練數(shù)據(jù)中選擇最優(yōu)特征集，訓(xùn)練數(shù)據(jù)用于訓(xùn)練NN模型。

實(shí)驗(yàn)中應(yīng)用了各個(gè)特征選擇算法，設(shè)置參數(shù)β=1。每種特征選擇算法對(duì)訓(xùn)練數(shù)據(jù)集進(jìn)行20次操作，最終的特征選擇排序由這20個(gè)實(shí)驗(yàn)結(jié)果決定，結(jié)果如表2所示。

從表2中可以看出：

（1）最重要的特征是第13個(gè)特征(f13)，對(duì)此五種特征選擇算法選擇結(jié)果一致。

（2）MIFS-U(β=1)算法和本文提出的 NMIFS-FS2算法認(rèn)為 f1是第二重要的特征，而MIFS(β=1)、mRMR和NMIFS算法認(rèn)為 f1是最不重要的特征，f8是最重要的特征。

（3）NMIFS-FS2算法認(rèn)為特征 f22是第三重要的特征，而其余的特征選擇算法認(rèn)為它是不重要的特征。

表2 SPECT心臟數(shù)據(jù)：基于不同互信息算法的特征排序模式

為了驗(yàn)證每種特征選擇算法選擇的最優(yōu)特征子集的有效性，將其應(yīng)用于訓(xùn)練NN模型中，訓(xùn)練NN模型使用的訓(xùn)練特征數(shù)據(jù)集分別為前1個(gè)重要特征、前3個(gè)重要特征，直至包含所有的22個(gè)特征。使用不同的特征選擇算法選擇特征排序。將207個(gè)測(cè)試數(shù)據(jù)集輸入到訓(xùn)練好的NN模型上，不同的特征訓(xùn)練輸入個(gè)數(shù)和各種特征選擇算法的平均分類精度關(guān)系如表3所示，分類曲線圖如圖2所示。

表3 五種特征選擇算法對(duì)測(cè)試數(shù)據(jù)集的分類率 （%）

圖2 五種特征選擇算法20次執(zhí)行的平均分類率

圖2表明，本文提出的NMIFS-FS2算法的性能優(yōu)于其他的特征選擇算法。五種特征選擇算法選擇的前3個(gè)特征作為神經(jīng)網(wǎng)絡(luò)的輸入時(shí)，性能幾乎相同，當(dāng)使用前4個(gè)到前15個(gè)特征作為輸入時(shí)NMIFS-FS2算法的性能顯著優(yōu)于另外四種算法，當(dāng)使用超過(guò)15個(gè)特征作為輸入時(shí)五種算法的性能都趨于穩(wěn)定。這是因?yàn)槲宸N算法所選擇的前三種特征大致相同，其中，NMIFS-FS2選擇的前2個(gè)特征和MIFS-U(β=1)的相同。對(duì)于神經(jīng)網(wǎng)絡(luò)，當(dāng)輸入的特征維數(shù)較少時(shí)，分類精度通常比較低，且受特征種類影響不大，所以，五種算法選擇的前3個(gè)特征作為分類輸入時(shí)，分類率幾乎相同。當(dāng)前4個(gè)到前15個(gè)特征作為分類特征輸入時(shí)，由于NMIFS-FS2算法所選擇的前15個(gè)特征比其他算法所選擇的前15個(gè)特征所含的有用信息量大、重要性高，所以，神經(jīng)網(wǎng)絡(luò)以此為輸入特征時(shí)，分類率較高。當(dāng)輸入特征較多時(shí)，為15個(gè)以上，則每種算法所選擇的特征又為大部分相同，所有特征的重要性之和相近，所以神經(jīng)網(wǎng)絡(luò)分類率趨于相近。當(dāng)所有特征都作為輸入時(shí)，則五種算法選擇的特征重要性之和相等，分類率也會(huì)相等。NMIFS-FS2算法選擇出的最優(yōu)特征子集為前 15 個(gè)特征 f13，f1，f22，f8，f5，f3，f21，f10，f20，f9，f16，f14，f12，f4，f7。該最優(yōu)特征子集對(duì)分類識(shí)別正常和異常SPECT病人有重要意義。

5 結(jié)論

本文研究了分類特征選擇問(wèn)題的方法，提出了MI公式（NMIFS-FS2）來(lái)計(jì)算特征組合或一組特征與類之間的MI。傳統(tǒng)特征選擇算法MIFS、MIFS-U、mRMR和NMIFS的互信息理論使用的是個(gè)體特征與另一個(gè)特征之間的MI，或者個(gè)體特征和類之間的MI，因此有些算法要求有一個(gè)冗余度參數(shù)β來(lái)近似特征間的互信息，但是參數(shù)β的值是很難確定的，在參數(shù)值選擇方面尚未有明確的規(guī)定或建議[10]，而本文提出的NMIFS-FS2算法不需要確定冗余度參數(shù)β值，并擴(kuò)大了應(yīng)用范圍。實(shí)驗(yàn)結(jié)果表明 NMIFS-FS2算法比 MIFS、MIFS-U、mRMR和NMIFS算法的魯棒性更好、應(yīng)用能力更廣、精度更高。

未來(lái)的研究工作將該算法應(yīng)用到更廣泛的數(shù)據(jù)集上，用不同的訓(xùn)練和驗(yàn)證數(shù)據(jù)集來(lái)測(cè)試NMIFS-FS2算法的性能是否仍優(yōu)于MIFS，MIFS-U，mRMR和NMIFS的特征選擇算法。

[1]楊打生，郭延芬.一種特征選擇的信息論算法[J].內(nèi)蒙古大學(xué)學(xué)報(bào)：自然科學(xué)版，2005，36（3）：341-345.

[2]洪智勇，王天擎，劉燦濤.一種新的互信息特征子集評(píng)價(jià)函數(shù)[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（22）：130-132.

[3]徐燕，李錦濤，王斌，等.基于區(qū)分類別能力的高性能特征選擇方法[J].軟件學(xué)報(bào)，2008，19（1）：82-89.

[4]徐峻嶺，周毓明，陳林，等.基于互信息的無(wú)監(jiān)督特征選擇[J].計(jì)算機(jī)研究與發(fā)展，2012，49（2）：372-382.

[5]Kwak N，Choi C H.Input feature selection for classification problems[J].IEEE Transactions on Neural Networks，2002，13（1）：143-159.

[6]Estévez P A，Tesmer M，Perez C A，et al.Normalized mutual information feature selection[J].IEEE Transactions on Neural Networks，2009，20（2）：189-201.

[7]姚旭，王曉丹，張玉璽，等.基于Markov blanket和互信息的集成特征選擇算法[J].系統(tǒng)工程與電子技術(shù)，2012，34（5）：1046-1050.

[8]劉海燕，王超，牛軍鈺.基于條件互信息的特征選擇改進(jìn)算法[J].計(jì)算機(jī)工程，2012，38（14）：135-137.

[9]張振海，李士寧，李志剛，等.一類基于信息熵的多標(biāo)簽特征選擇算法[J].計(jì)算機(jī)研究與發(fā)展，2013，50（6）：1177-1184.

[10]Unler A，Murat A.A discrete particle swarm optimization method for feature selection in binary classification problems[J].European Journal of Operational Research，2010，206（3）：528-539.

[11]劉海峰，趙華，劉守生.一種基于類別的組合型文本特征選擇[J].情報(bào)學(xué)報(bào)，2010，29（4）：744-748.

[12]謝文彪，樊紹勝，費(fèi)洪曉，等.基于互信息梯度優(yōu)化計(jì)算的信息判別特征提取[J].電子與信息學(xué)報(bào)，2009，31（12）：2975-2979.

[13]張逸石，陳傳波.基于最小聯(lián)合互信息虧損的最優(yōu)特征選擇算法[J].計(jì)算機(jī)科學(xué)，2011，38（12）：200-205.

[14]Amiri F，Rezaei Yousefi M M，Lucas C，et al.Mutual information-based feature selection for intrusion detection systems[J].Journal of Network and Computer Applications，2011，34（4）：1184-1199.

[15]Martínez Sotoca J，Pla F.Supervised feature selection by clustering using conditional mutual information-based distances[J].Pattern Recognition，2010，43（6）：2068-2081.