動態(tài)加權(quán)條件互信息的特征選擇算法

張 俐 陳小波

①(江蘇理工學(xué)院計算機(jī)工程學(xué)院 常州 213001)

②(北京郵電大學(xué)可信分布式計算與服務(wù)教育部重點(diǎn)實(shí)驗(yàn)室 北京 100876)

③(中國人民銀行常州市中心支行 常州 213001)

1 引言

在過去幾十年里，新型計算機(jī)和互聯(lián)網(wǎng)技術(shù)正在以前所未有的速度產(chǎn)生著大量高維數(shù)據(jù)[1,2]。在這些高維數(shù)據(jù)中包含著許多無關(guān)和冗余特征。因?yàn)椴幌嚓P(guān)和冗余特征不僅會增加模型訓(xùn)練時間而且也使得模型的可解釋變得很差。如何處理這些不相關(guān)和冗余特征是數(shù)據(jù)分析和知識發(fā)現(xiàn)中所面臨的重大挑戰(zhàn)。特征選擇不同于其他數(shù)據(jù)降維技術(shù)(如特征提取)[3]，它可以刪除無關(guān)和冗余特征，保留相關(guān)原始物理特征，從而降低數(shù)據(jù)維數(shù)。這樣有利于提高數(shù)據(jù)質(zhì)量和分類性能，并使得模型的訓(xùn)練時間大幅縮小而且也使得模型的可解釋性變得更強(qiáng)[4,5]。

通常特征選擇技術(shù)又分為分類依賴型[6](包裝器方法和嵌入式方法)和分類器無關(guān)型(過濾式方法)?；谛畔⒄摰倪^濾式特征選擇方法優(yōu)點(diǎn)[7–11]為：(1)它可以直接從數(shù)據(jù)中提取有價值的知識，而且這些知識對于問題真正的解決又起到至關(guān)重要作用。(2)它的計算成本低且與具體分類器無關(guān)。(3)目前該方法應(yīng)用領(lǐng)域廣泛，包括基因表達(dá)數(shù)據(jù)、文本分類和網(wǎng)絡(luò)入侵檢測等多個領(lǐng)域。因此基于信息論的過濾式特征選擇方法逐漸成為特征選擇技術(shù)的研究熱點(diǎn)[12–16]。

常見基于信息論的特征選擇算法[5,17–19]可分為兩類。最小化冗余特征的算法(maxMIFS[8]，MRMR[20]，CIFE[8]，CMIM[8]和JMI[10]等)和最大化新分類信息的算法(DCSF[12]和JMIM[16])。maxMIFS和MRMR通過去除特征之間冗余特征來提高最優(yōu)特征子集(S)整體識別質(zhì)量。但是它們卻忽視兩個特征與類標(biāo)簽之間的冗余性問題。因此，產(chǎn)生許多經(jīng)典的多信息去除冗余性的算法，例如JMI,CIFE和CMIM等。然而它們卻忽視最大化新分類信息來提高S集合整體識別的質(zhì)量。隨著特征選擇算法的發(fā)展，如何將減少冗余的特征選擇算法和最大化新分類信息的特征選擇算法進(jìn)行融合逐漸成為研究的新熱點(diǎn)。代表性的算法有MRI[13],CFR[14]和DISR[21]等。以上這些算法都是基于信息論特征選擇框架[7]的具體實(shí)現(xiàn)。Brown等人[7]認(rèn)為選擇不同的參數(shù)就是選擇不同的特征選擇算法。它們存在的問題是參數(shù)設(shè)置過大還是過小都會對特征選擇過程造成影響，即存在對無關(guān)特征和冗余特征的忽略與誤判。

在大數(shù)據(jù)環(huán)境下，針對數(shù)據(jù)多樣性和高維性的特點(diǎn)，尋找一種動態(tài)的非預(yù)先設(shè)置參數(shù)的特征選擇方法就成為目前需要解決的問題。本文提出一種新的過濾式特征選擇算法(Weighted Maximum Relevance and maximum Independence,WMRI)。本文主要貢獻(xiàn)為：(1)利用條件互信息衡量特征與類標(biāo)簽之間的相關(guān)性以及特征之間冗余性；(2)提出通過均值和標(biāo)準(zhǔn)差來動態(tài)調(diào)節(jié)新分類信息和保留類別信息的權(quán)重與平衡問題；(3)通過對10個基準(zhǔn)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)對比，實(shí)驗(yàn)結(jié)果表明，該算法(WMRI)優(yōu)于其他特征選擇算法(DCSF,MRI,CFR,IG-RFE[15]和JMIM)。

2 WMRI算法的提出

Brown等人[7]提出基于信息論特征選擇框架，具體為

其中，設(shè)F是原始特征集合，|S|是最優(yōu)特征子集數(shù)，S ?F,J(·)代表評估標(biāo)準(zhǔn)，fk表示候選特征，fsel表示已選特征，fsel∈S,fk∈F-S,C表示類標(biāo)簽集合，|C|是類標(biāo)簽數(shù)。

Wang等人[13]在Brown的研究基礎(chǔ)上提出MRI算法，具體評估標(biāo)準(zhǔn)為

從式(2)中可知，在MRI算法中，獨(dú)立分類信息由新分類信息項(xiàng)I(C;fk|fsel)與保留類別信息項(xiàng)I(C;fsel|fk)構(gòu)成，并且這兩種分類信息同等重要，存在問題是在實(shí)際中I(C;fk|fsel)與I(C;fsel|fk)之間存在差異性。同時，結(jié)合式(1)和式(2)又可知該算法存在預(yù)先設(shè)置參數(shù)β和λ的問題，即λ=。

那么，如何在不增加計算量和復(fù)雜度的情況下，動態(tài)區(qū)分新分類信息和保留類別信息之間的重要程度。以適應(yīng)在大數(shù)據(jù)環(huán)境下，數(shù)據(jù)多樣性和高維性的特點(diǎn)，并提高S集合整體數(shù)據(jù)的質(zhì)量，就成為目前在特征選擇領(lǐng)域中需要研究的一個問題。

本文提出一種新的過濾式特征選擇算法(WMRI)。該方法通過引入標(biāo)準(zhǔn)差方法來分別計算I(C;fk|fsel)與I(C;fsel|fk)之間的權(quán)重。因?yàn)闃?biāo)準(zhǔn)差[2]是一種常見的測量系統(tǒng)穩(wěn)定程度的度量方法。標(biāo)準(zhǔn)差值越高，表示分散度越高；反之亦然。因此，通過標(biāo)準(zhǔn)差可以動態(tài)平衡新分類信息項(xiàng)與保留類別信息項(xiàng)之間的重要程度。WMRI算法評估標(biāo)準(zhǔn)具體為

從式(3)可以得出，α和β可以分別動態(tài)測量新分類信息項(xiàng)I(C;fk|fsel)與 保留類別信息項(xiàng)I(C;fsel|fk)的重要程度。通過這樣，WMRI算法可以解決I(C;fk|fsel)項(xiàng)與I(C;fsel|fk)項(xiàng)之間平衡和權(quán)重問題。其中，式(3)中α和β分別由式(5)和式(7)表示，它的偽代碼如表1所示。

從式(3)可以知道，WMRI算法與MRI算法相類似，都采用前向順序搜索特征子集。通過表1可知，WMRI算法主要分為3部分。第1部分(第(1)～(6)行)主要包括：(1)初始化S集合和計數(shù)器k；(2)計算集合F中每個特征的互信息，選擇出最大的特征fk，將該特征fk從F集合中刪除，并將特征fk加入S集合，這時候選特征fk變成已選特征fsel。第2部分(第(7)～(15)行)主要是分別計算I(C;fk|fsel),I(C;fsel|fk),μ1,α,μ2和β的值。在第3部分(第(16)～(20)行)，根據(jù)式(3)的選擇標(biāo)準(zhǔn)，選擇出最大JWMRI(fk)值所對應(yīng)的特征fk，并將該特征fk存入S并從F中刪除該特征fk，然后一直循環(huán)到用戶指定的閾值K就停止循環(huán)。

表1 WMRI算法的偽代碼

WMRI算法包括2個“ for”循環(huán)和1個“while”循環(huán)。因此，WMRI算法的時間復(fù)雜性是O(Kmn)(K代表已選特征數(shù)，n代表所有特征數(shù)，m代表所有樣本數(shù)，K?n)。WMRI算法復(fù)雜性高于MRI算法，IG-RFE算法，CFR算法，JMIM算法和DCSF算法。主要原因在于WMRI算法還需計算μ1,α,μ2和β的值。

3 實(shí)驗(yàn)分析與討論

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

為了驗(yàn)證所提出WMRI算法的有效性，在實(shí)驗(yàn)中使用10個不同數(shù)據(jù)集進(jìn)行驗(yàn)證。這些數(shù)據(jù)集來自不同的領(lǐng)域，同時它們可以在UCI[13]和ASU[19]中找到。這些數(shù)據(jù)集包括手寫數(shù)字?jǐn)?shù)據(jù)(Semeion和Mfeat-kar)、文字?jǐn)?shù)據(jù)(CANE-9)、語音數(shù)據(jù)(Isolet)、圖像數(shù)據(jù)(COIL20和USPS)、生物學(xué)數(shù)據(jù)(WPBC和ALLAML)和其他類數(shù)據(jù)(Madelon和Musk2)。更詳細(xì)的描述可以在表2中找到。

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

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

在實(shí)驗(yàn)中，使用K近鄰(KNN)[19]、決策樹(C4.5)[13]和隨機(jī)森林(RandomForest)[22]來評估不同的特征選擇算法。本文的實(shí)驗(yàn)環(huán)境是Intel-i7處理器，使用8 GB內(nèi)存，仿真軟件是Python2.7。

實(shí)驗(yàn)由3個部分組成。第1部分是數(shù)據(jù)預(yù)處理。為保證實(shí)驗(yàn)的公正性，整個實(shí)驗(yàn)過程采用6折交叉驗(yàn)證方法進(jìn)行驗(yàn)證，就是將實(shí)驗(yàn)數(shù)據(jù)集均勻分成6等份，5份作為訓(xùn)練數(shù)據(jù)集，1份作為測試數(shù)據(jù)集。第2部分是特征子集的生成。在實(shí)驗(yàn)中，采用不同特征選擇方法生成特征子集。特征子集的規(guī)模設(shè)為30。第3部分是特征子集評價。在這個部分中，用fmi來評估分類器在特征子集上的分類準(zhǔn)確率。分類準(zhǔn)確率是指正確分類的樣本數(shù)占樣本總數(shù)的比例。設(shè)TP(True Positive)指正類判定為正類的個數(shù)；FP(False Positive)指負(fù)類判定為正類的個數(shù)；TN(True Negative)指負(fù)類判定為負(fù)類的個數(shù)；FN(False Negative)指正類判定為負(fù)類的個數(shù)。sen,prc和fmi定義分別為

3.3 實(shí)驗(yàn)結(jié)果與討論

表3—表5分別選擇KNN，C4.5和Random Forest這3種分類器，同時以fmi分類準(zhǔn)確率作為評價指標(biāo)對WMRI，IG-RFE，CFR，JMIM，DCSF和MRI進(jìn)行統(tǒng)計分析。表中每行中最大值用黑體字標(biāo)識。命名為“平均值”的所在行表示平均fmi值。通過使用“+”，“=”和“–”表示W(wǎng)MRI算法分別“優(yōu)于”、“等于”和“差于”其他特征選擇算法。命名為“W/T/L”的所在行，分別表示W(wǎng)MRI算法與其他特征選擇算法的勝/平/負(fù)的次數(shù)。

表3 KNN分類器的平均分類準(zhǔn)確率fmi(%)

表4 C4.5分類器的平均分類準(zhǔn)確率fmi(%)

表5 Random Forest分類器的平均分類準(zhǔn)確率fmi(%)

從表3可以得出，WMRI算法在10個數(shù)據(jù)集的平均fmi值是最高(74.082%)。同時，WMRI分別優(yōu)IG-RFE,CFR,JMIM,DCSF和MRI為9,9,8,9和9次。在表4中，WMRI算法在10個數(shù)據(jù)集的平均fmi值也是最高(70.258%)。同時，WMRI分別優(yōu)IG-RFE,CFR,JMIM,DCSF和MRI為10,8,9,9和8次。在表5中，WMRI算法在10個數(shù)據(jù)集的平均fmi值也是最高(76.524%)。同時，WMRI分別優(yōu)IG-RFE,CFR,JMIM,DCSF和MRI為10,10,10,10和10次。

通過對表3—表5分析可以得出，不同分類器表現(xiàn)出的分類結(jié)果也不相同。但是，WMRI算法的平均fmi值都是最高。這說明WMRI算法優(yōu)于其他特征選擇算法(IG-RFE,CFR,JMIM,DCSF和MRI)。

為了進(jìn)一步觀察特征子集對fmi值的影響，圖1，圖2和圖3分別給出部分不同數(shù)據(jù)集的fmi性能比較。從圖1、圖2和圖3可以看出，當(dāng)數(shù)據(jù)的維數(shù)不斷增加時，由于WMRI算法通過平均值和標(biāo)準(zhǔn)差動態(tài)調(diào)整新分類信息項(xiàng)I(C;fk|fsel)與保留類別信息項(xiàng)I(C;fsel|fk)的重要程度。結(jié)果顯示，WMRI算法明顯優(yōu)于MRI算法。例如在圖1(b)和圖2(b)中，JMIM算法優(yōu)于MRI算法，而WMRI算法優(yōu)于JMIM算法。圖3(a)和圖3(b)，DCSF算法優(yōu)于MRI算法，而WMRI算法優(yōu)于DCSF算法。這些充分說明WMRI算法對分類效果的提升非常明顯。并且，WMRI明顯優(yōu)于IG-RFE,CFR,JMIM,DCSF和MRI。

圖1 KNN在高維數(shù)據(jù)集上的性能比較

圖2 C4.5在高維數(shù)據(jù)集上的性能比較

圖3 Random Forest在高維數(shù)據(jù)集上的性能比較

4 結(jié)束語

本文提出一種基于過濾式的特征選擇方法：動態(tài)加權(quán)的最大相關(guān)和最大獨(dú)立分類特征選擇算法(WMRI)。該算法旨在解決新分類信息和保留類別信息不同重要度的問題并提高特征子集的數(shù)據(jù)質(zhì)量。為了全面驗(yàn)證WMRI算法的有效性，實(shí)驗(yàn)在10個數(shù)據(jù)集上進(jìn)行。通過使用分類器(KNN,C4.5和Random Forest)和分類準(zhǔn)確率指標(biāo)(fmi)全面評估所選特征子集的質(zhì)量。實(shí)驗(yàn)結(jié)果證明WMRI明顯優(yōu)于MRI,CFR,JMIM,DCSF和IG-RFE等5種特征選擇算法，但WMRI算法有時也會導(dǎo)致特征選擇的結(jié)果不理想。未來的工作包括進(jìn)一步改進(jìn)新分類信息項(xiàng)和保留類別信息項(xiàng)的動態(tài)平衡問題并優(yōu)化WMRI算法，同時在更廣泛的領(lǐng)域中驗(yàn)證所提出的方法。