潘 果

PAN Guo

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

2.湖南現(xiàn)代物流職業(yè)技術(shù)學(xué)院 物流信息系，長沙 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）是兩個隨機變量之間相關(guān)性的一個信息度量，對稱且非負，當(dāng)且僅當(dāng)變量獨立時為零。之前有研究人員研究基于MI概念構(gòu)建出高效的特征選擇算法[1-8]，本文基于MI概念提出一種有效的特征選擇算法，對現(xiàn)有的算法作出了改進，使其得到更廣泛的應(yīng)用、具有更好的分類性能，并且降低了計算復(fù)雜度。

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

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

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

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

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

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

1 相關(guān)工作

1.1 互信息

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

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

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

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

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

1.2.1 MIFS算法

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

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

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

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

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

①計算特征之間的MI：

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

②選擇下一個特征：

1.2.2 MIFS-U算法

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

1.2.3 mRMR算法

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

1.2.4 NMIFS算法

2 本文提出的算法

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

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

②最大化

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

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

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

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

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

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

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

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

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

4 實驗結(jié)果

本章給出了兩個實驗測試實例來評估本文提出的算法。第一個實驗實例是一個定義好的問題，第二個實驗實例取自一個實際問題的心臟數(shù)據(jù)集。

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

4.1 實驗1給定的問題（LIC1）

定義LIC1問題為：

輸入特征空間為：

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

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

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

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

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

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

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

從表2中可以看出：

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

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

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

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

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

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

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

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

5 結(jié)論

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

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

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

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

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

[4]徐峻嶺，周毓明，陳林，等.基于互信息的無監(jiān)督特征選擇[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].計算機工程，2012，38（14）：135-137.

[9]張振海，李士寧，李志剛，等.一類基于信息熵的多標(biāo)簽特征選擇算法[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].情報學(xué)報，2010，29（4）：744-748.

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

[13]張逸石，陳傳波.基于最小聯(lián)合互信息虧損的最優(yōu)特征選擇算法[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.