張 俐 陳小波

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

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

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

1 引言

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

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

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

在大數(shù)據(jù)環(huán)境下，針對(duì)數(shù)據(jù)多樣性和高維性的特點(diǎn)，尋找一種動(dòng)態(tài)的非預(yù)先設(shè)置參數(shù)的特征選擇方法就成為目前需要解決的問(wèn)題。本文提出一種新的過(guò)濾式特征選擇算法(Weighted Maximum Relevance and maximum Independence,WMRI)。本文主要貢獻(xiàn)為：(1)利用條件互信息衡量特征與類標(biāo)簽之間的相關(guān)性以及特征之間冗余性；(2)提出通過(guò)均值和標(biāo)準(zhǔn)差來(lái)動(dòng)態(tài)調(diào)節(jié)新分類信息和保留類別信息的權(quán)重與平衡問(wèn)題；(3)通過(guò)對(duì)10個(gè)基準(zhǔn)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)對(duì)比，實(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(·)代表評(píng)估標(biāo)準(zhǔn)，fk表示候選特征，fsel表示已選特征，fsel∈S,fk∈F-S,C表示類標(biāo)簽集合，|C|是類標(biāo)簽數(shù)。

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

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

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

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

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

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

表1 WMRI算法的偽代碼

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

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

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

為了驗(yàn)證所提出WMRI算法的有效性，在實(shí)驗(yàn)中使用10個(gè)不同數(shù)據(jù)集進(jìn)行驗(yàn)證。這些數(shù)據(jù)集來(lái)自不同的領(lǐng)域，同時(shí)它們可以在UCI[13]和ASU[19]中找到。這些數(shù)據(jù)集包括手寫數(shù)字?jǐn)?shù)據(jù)(Semeion和Mfeat-kar)、文字?jǐn)?shù)據(jù)(CANE-9)、語(yǔ)音數(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]來(lái)評(píng)估不同的特征選擇算法。本文的實(shí)驗(yàn)環(huán)境是Intel-i7處理器，使用8 GB內(nèi)存，仿真軟件是Python2.7。

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

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

表3—表5分別選擇KNN，C4.5和Random Forest這3種分類器，同時(shí)以fmi分類準(zhǔn)確率作為評(píng)價(jià)指標(biāo)對(duì)WMRI，IG-RFE，CFR，JMIM，DCSF和MRI進(jìn)行統(tǒng)計(jì)分析。表中每行中最大值用黑體字標(biāo)識(shí)。命名為“平均值”的所在行表示平均fmi值。通過(guò)使用“+”，“=”和“–”表示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個(gè)數(shù)據(jù)集的平均fmi值是最高(74.082%)。同時(shí)，WMRI分別優(yōu)IG-RFE,CFR,JMIM,DCSF和MRI為9,9,8,9和9次。在表4中，WMRI算法在10個(gè)數(shù)據(jù)集的平均fmi值也是最高(70.258%)。同時(shí)，WMRI分別優(yōu)IG-RFE,CFR,JMIM,DCSF和MRI為10,8,9,9和8次。在表5中，WMRI算法在10個(gè)數(shù)據(jù)集的平均fmi值也是最高(76.524%)。同時(shí)，WMRI分別優(yōu)IG-RFE,CFR,JMIM,DCSF和MRI為10,10,10,10和10次。

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

為了進(jìn)一步觀察特征子集對(duì)fmi值的影響，圖1，圖2和圖3分別給出部分不同數(shù)據(jù)集的fmi性能比較。從圖1、圖2和圖3可以看出，當(dāng)數(shù)據(jù)的維數(shù)不斷增加時(shí)，由于WMRI算法通過(guò)平均值和標(biāo)準(zhǔn)差動(dòng)態(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算法。這些充分說(shuō)明WMRI算法對(duì)分類效果的提升非常明顯。并且，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é)束語(yǔ)

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