張 俐

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

過(guò)去幾十年，在生物信息領(lǐng)域產(chǎn)出大量基因數(shù)據(jù)[1-2]。這些基因數(shù)據(jù)普遍具有樣本小、維度高和高噪聲等特點(diǎn)[3]。如何處理這些不相關(guān)和冗余特征給數(shù)據(jù)降維帶來(lái)重大挑戰(zhàn)。常見(jiàn)的數(shù)據(jù)降維包括特征提取[4]和特征選擇[5]兩類(lèi)。特征選擇由于可以刪除無(wú)關(guān)和冗余特征，同時(shí)保留相關(guān)原始特征，因此引起許多關(guān)注。

在特征選擇中主要有數(shù)據(jù)層面(過(guò)濾式方法)和算法層面(包裝器方法和嵌入式方法)[6-8]兩方面的研究。過(guò)濾式特征選擇算法憑借其計(jì)算成本低、與具體分類(lèi)器分離及應(yīng)用領(lǐng)域廣等優(yōu)點(diǎn)，逐漸成為特征選擇技術(shù)中的研究熱點(diǎn)。常見(jiàn)的基于信息論的過(guò)濾式特征選擇算法包括采用平均冗余策略的特征選擇算法(MID[9]、MIQ[9]、JMI[10]和CFR[11]等)和采用“最大最小”極端標(biāo)準(zhǔn)的特征選擇算法(CMIM[12]、JMIM[13]和DWUR[14]等)。然而這些算法存在忽視對(duì)交互依賴(lài)特征相關(guān)性和冗余性判斷的問(wèn)題。

因此，本文提出一種利用聯(lián)合互信息和互信息判斷特征與類(lèi)標(biāo)簽之間相關(guān)性和冗余性的特征選擇算法(joint feature relevance and redundancy, JFRR)。該算法利用聯(lián)合互信息計(jì)算在已選特征下候選特征與類(lèi)標(biāo)簽之間的相關(guān)性；通過(guò)互信息計(jì)算已選特征和候選特征的冗余性；通過(guò)在9 個(gè)基準(zhǔn)基因數(shù)據(jù)集的實(shí)驗(yàn)對(duì)比，該算法(JFRR)優(yōu)于其他特征選擇算法(MID、MIQ、CMIM、JMIM、CFR 和CMIMRMR[15])。

1 聯(lián)合互信息的一些概念

設(shè)X、Y和Z是3 個(gè) 離 散 型 變 量[16]，其 中，X=

2 JFRR 算法的提出

通過(guò)以上描述可知，傳統(tǒng)的特征選擇算法通常使用最小化冗余項(xiàng)和最大化相關(guān)項(xiàng)選擇特征子集S。但是由此產(chǎn)生如下問(wèn)題：1) 當(dāng)已選特征量增加時(shí)，冗余項(xiàng)的大小也會(huì)隨著相關(guān)項(xiàng)的增加而增加。這就存在一些冗余特征可能被選中；2) 在冗余項(xiàng)中，只考慮已選特征和候選特征之間互信息的計(jì)算，而忽視類(lèi)標(biāo)簽，可能會(huì)造成已選特征和候選特征共享信息，意味著它們之間存在冗余信息。事實(shí)上，它們可能與類(lèi)標(biāo)簽集合C之間共享不同信息。

以上問(wèn)題可能會(huì)高估某些候選特征的重要性[17-19]。因此需要考慮，如何在已選特征集合S規(guī)模不斷增加的情況下，解決S與類(lèi)標(biāo)簽集合C的相關(guān)性，同時(shí)解決候選特征fk與S的冗余性，以及解決在S條件下，候選特征fk與 類(lèi)標(biāo)簽C的相關(guān)性的問(wèn)題。

為此，本文提出一種基于信息論的特征選擇算法(JFRR)。該算法充分利用了線(xiàn)性累計(jì)加和的方式，具體如下：

式中，設(shè)F是原始特征集合，S?F；J(·)代表評(píng)估標(biāo)準(zhǔn)；fi∈S,fk∈F?S。

通過(guò)式(4)可知，JFRR 算法利用聯(lián)合互信息和互信息原理充分考慮S與C之 間的相關(guān)性，fk與S的冗余性以及在S條件下，fk與C之間的相關(guān)性。JFRR 算法的具體描述如下。

輸入：原始特征集合F={f1,f2,···fn}，類(lèi)標(biāo)簽集合C，已選特征子集S，閾值K

從式(4)可知，JFRR 算法采用前向順序搜索特征子集。JFRR 算法主要分為3 部分。第1 部分為1)～7)，主要是初始化S集合和計(jì)數(shù)器k；將選擇出最大的特征fk加 入S集合，同時(shí)fk變成已選特征fi。第2 部分為8)～13)，分別計(jì)算I(fi;C)、I(fk;fi)和I(fk,fi;C)的值。第3 部分為14)～19)，根據(jù)式(4)的選擇標(biāo)準(zhǔn)選擇fk，一直循環(huán)到用戶(hù)指定的閾值K就停止循環(huán)。

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

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

本節(jié)將JFRR 與MID、MIQ、CMIM、JMIM、CFR 和CMI-MRMR 算法進(jìn)行對(duì)比。具體分類(lèi)器為：決策樹(shù)(C4.5)和支持向量機(jī)(support vector machine, SVM)。本 文 的 實(shí) 驗(yàn) 環(huán) 境 是Intel-i7 處 理器，16 GB 內(nèi)存，仿真軟件是Python2.7。實(shí)驗(yàn)數(shù)據(jù)集選擇ASU 和UCI 基因數(shù)據(jù)集[9,20]，詳細(xì)描述見(jiàn)表1。其中，這9 個(gè)數(shù)據(jù)集包含不同的樣本數(shù)、特征數(shù)和類(lèi)數(shù)。樣本范圍為50～569，特征范圍為31～9 712，類(lèi)的范圍為2～12，數(shù)據(jù)類(lèi)型涉及連續(xù)型和離散型。采用6 折交叉驗(yàn)證方法進(jìn)行實(shí)驗(yàn)驗(yàn)證。為保證實(shí)驗(yàn)公平，分別通過(guò)分類(lèi)評(píng)價(jià)指標(biāo)fmc(F1_micro)和pcm(Precision_micro)來(lái)評(píng)價(jià)預(yù)測(cè)性能。

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

3.2 特征選擇算法性能比較與討論

為了比較JFRR 與MID、MIQ、CMIM、JMIM、CFR 和CMI-MRMR 算法之間的優(yōu)劣性，將它們所選的特征子集放到同一個(gè)分類(lèi)器(C4.5 和SVM)進(jìn)行比較，特征子集的規(guī)模設(shè)置為30。表2 選擇C4.5 分類(lèi)器。表3 選擇SVM 分類(lèi)器。在表2～表3 中，粗體代表該數(shù)據(jù)集下特征選擇算法中最高平均分類(lèi)預(yù)測(cè)值?！癢ins/Ties/Losses”描述JFRR算法分別與MID、MIQ、CMIM、JMIM、CFR 和CMI-MRMR 算法之間的優(yōu)/平/輸個(gè)數(shù)。

表3 SVM 分類(lèi)器的平均fmc 性能比較 %

3.2.1 特征選擇算法的fmc 性能比較

在表2 中，7 個(gè)特征選擇算法的平均fmc 精度值分別為82.459%、80.24%、68.122%、75.356%、68.695%、73.047%和77.296%。JFRR 算法獲得最高fmc 值。同時(shí)，從WINS/TIES/LOSSES 行的統(tǒng)計(jì)結(jié)果得出JFRR 分別優(yōu)于MID、MIQ、CMIM、JMIM、CFR 和CMI-MRMR 算 法9、9、9、9、8 和6 次。

表2 C4.5 分類(lèi)器的平均fmc 性能比較 %

在表3 中，7 個(gè)特征選擇算法的平均fmc 精度值分別為80.985%、79.925%、67.712%、77.631 7%、68.329%、75.302%和76.461%。JFRR 算法獲得最高fmc 值。同時(shí)，從WINS/TIES/LOSSES 行的統(tǒng)計(jì)結(jié)果得出JFRR 分別優(yōu)于MID、MIQ、CMIM、JMIM、CFR 和CMI-MRMR 算 法6、8、8、8、7 和6 次。

為了進(jìn)一步比較特征子集對(duì)fmc 值的影響，圖1 和圖2 分別給出部分?jǐn)?shù)據(jù)集的fmc 性能差異。當(dāng)數(shù)據(jù)的維數(shù)不斷增加時(shí)，JFRR 算法通過(guò)動(dòng)態(tài)調(diào)整特征間的相關(guān)性和冗余性提升了特征子集的數(shù)據(jù)質(zhì)量。圖1 和圖2 的實(shí)驗(yàn)結(jié)果顯示，JFRR 算法對(duì)分類(lèi)提升的效果明顯。并且，JFRR 明顯優(yōu)于MID、 CMIM、 MIQ、 JMIM、 CFR 和CMIMRMR。

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

圖1 是C4.5 在高維數(shù)據(jù)集上的性能比較。在圖1a 中，JFRR 算法的分類(lèi)fmc 值為86.039%，是7 種分類(lèi)算法中最高的，分別比MID、MIQ、CMIM、JMIM、CFR 和CMI-MRMR 高出5.317%、22.693%、8.661%、22.508%、8.321%和1.546%。在圖1b 中，JFRR 算法的分類(lèi)fmc 值為77.595%，也是7 種分類(lèi)算法中最高的，分別比MID、MIQ、CMIM、JMIM、CFR 和CMI-MRMR 高出5.472%、19.282%、23.7%、19.301%、26.711%和12.663%。圖2 是SVM 在高維數(shù)據(jù)集上的性能比較。在圖2a中，JFRR 算法的分類(lèi)fmc 值為95.102%，是7 種分類(lèi)算法中最高的，分別比MID、MIQ、CMIM、JMIM、 CFR 和CMI-MRMR 高出0.0%、24.361%、1.389%、29.931%和3.143%和0.0%。在圖2b 中，JFRR 算法的分類(lèi)fmc 值為94.91%，是7 種分類(lèi)算法中最高的，分別比MID、MIQ、CMIM、JMIM、CFR 和CMI-MRMR 高出0.347%、4.233%、0.53%、4.058%、0.351%和4.577%。

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

3.2.2 特征選擇算法的pcm 性能比較

圖3 為pcm 盒圖。從圖3a 中可以得出，在C4.5 分類(lèi)器的pcm 盒圖中，使用JFRR 算法選擇出的特征集合在五位數(shù)(最小值、四分位數(shù)(第25 個(gè)百分位數(shù))、中位數(shù)、四分位數(shù)(第75 個(gè)百分位數(shù))和最大值)中體現(xiàn)出的分類(lèi)效果都是最優(yōu)。同時(shí)，從圖3b 中也可以得出，在SVM 分類(lèi)器的pcm 盒圖中，使用JFRR 算法選擇出的特征集合在五位數(shù)(最小值、四分位數(shù)(第25 個(gè)百分位數(shù))、中位數(shù)和四分位數(shù)(第75 個(gè)百分位數(shù)))中體現(xiàn)出的分類(lèi)效果都是最優(yōu)的效果。

圖3 C4.5 分類(lèi)器和SVM 分類(lèi)器的pcm 盒圖

綜上，不同分類(lèi)器表現(xiàn)出的分類(lèi)結(jié)果不盡相同。但是，JFRR 算法在fmc 和pcm 的評(píng)價(jià)指標(biāo)值在大多數(shù)數(shù)據(jù)集上都是最好。從C4.5 和SVM 分類(lèi)器表現(xiàn)結(jié)果中可知，C4.5 分類(lèi)性能明顯優(yōu)于SVM分類(lèi)性能。

3.3 算法的運(yùn)行時(shí)間分析

計(jì)算特征選擇算法的運(yùn)行時(shí)間也是衡量特征選擇算法重要性的標(biāo)準(zhǔn)之一。JFRR、MID、MIQ、CMIM、JMIM、CFR 和CMI-MRMR 算法在9 個(gè)數(shù)據(jù)集上進(jìn)行特征排序后得出的運(yùn)行時(shí)間如表4 所示。可以看出，JFRR 算法的運(yùn)行時(shí)間在可接受的范圍之內(nèi)。

表4 不同特征選擇算法運(yùn)行時(shí)間比較 s

3.4 實(shí)驗(yàn)算法比較

本節(jié)分析JFRR 與MID、CMIM、MIQ、JMIM、CFR 和CMI-MRMR 之間在交互特征依賴(lài)相關(guān)性和冗余性的差異。從表5 可以得出，與JFRR 相比，MID、MIQ、CMIM 和CFR 將I(fk;C)定義為衡量特征相關(guān)性的標(biāo)準(zhǔn)。CMI-MRMR 將I(fi,C|fk)定義為衡量特征相關(guān)性的標(biāo)準(zhǔn)。只有JFRR 和JMIM 將I(fk,fi;C)定義為衡量交互特征依賴(lài)性動(dòng)態(tài)變化標(biāo)準(zhǔn)。但是，JMIM 算法卻忽視特征冗余性變化。因此，得出JFRR 與其他特征選擇算法差異明顯。

表5 算法比較

4 結(jié) 束 語(yǔ)

隨著基因數(shù)據(jù)中高維特征數(shù)據(jù)的不斷增多，特征間的關(guān)系變得越來(lái)越復(fù)雜(包含大量無(wú)關(guān)特征和冗余特征)。而傳統(tǒng)的特征選擇算法往往忽視特征間的相關(guān)性和冗余性之間的聯(lián)系。本文提出一種基于聯(lián)合互信息的JFRR 算法。該算法利用互信息和聯(lián)合互信息間的關(guān)系動(dòng)態(tài)分析和調(diào)整特征間以及特征與類(lèi)標(biāo)簽間的相關(guān)信息和冗余信息，從而達(dá)到刪除無(wú)關(guān)特征和冗余特征的目的，以此提高特征子集的數(shù)據(jù)質(zhì)量。為了全面驗(yàn)證JFRR 算法的有效性，實(shí)驗(yàn)在9 個(gè)基因數(shù)據(jù)集上進(jìn)行。分別通過(guò)使用分類(lèi)器(C4.5 和SVM)和分類(lèi)準(zhǔn)確率指標(biāo)(fmc 和pcm)全面評(píng)估所選特征子集的質(zhì)量。實(shí)驗(yàn)結(jié)果證明JFRR 明顯優(yōu)于MID、MIQ、CMIM、JMIM、CFR和CMI-MRMR 等6 種特征選擇算法。

但在一些基因數(shù)據(jù)中，JFRR 算法仍舊存在選擇出的特征子集不理想的情況。未來(lái)的工作將進(jìn)一步研究和改進(jìn)互信息和聯(lián)合互信息的關(guān)系，并以此優(yōu)化JFRR 算法，同時(shí)在更廣泛的基因數(shù)據(jù)集中對(duì)算法進(jìn)行驗(yàn)證，以此提高分類(lèi)預(yù)測(cè)精度。