基因數(shù)據(jù)的交互依賴特征選擇算法

張 俐

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

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

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

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

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

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

2 JFRR 算法的提出

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

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

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

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

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

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

從式(4)可知，JFRR 算法采用前向順序搜索特征子集。JFRR 算法主要分為3 部分。第1 部分為1)～7)，主要是初始化S集合和計(jì)數(shù)器k；將選擇出最大的特征fk加 入S集合，同時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)到用戶指定的閾值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)行對比。具體分類器為：決策樹(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ì)描述見表1。其中，這9 個數(shù)據(jù)集包含不同的樣本數(shù)、特征數(shù)和類數(shù)。樣本范圍為50～569，特征范圍為31～9 712，類的范圍為2～12，數(shù)據(jù)類型涉及連續(xù)型和離散型。采用6 折交叉驗(yàn)證方法進(jìn)行實(shí)驗(yàn)驗(yàn)證。為保證實(shí)驗(yàn)公平，分別通過分類評價指標(biāo)fmc(F1_micro)和pcm(Precision_micro)來評價預(yù)測性能。

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

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

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

表3 SVM 分類器的平均fmc 性能比較 %

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

在表2 中，7 個特征選擇算法的平均fmc 精度值分別為82.459%、80.24%、68.122%、75.356%、68.695%、73.047%和77.296%。JFRR 算法獲得最高fmc 值。同時，從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 分類器的平均fmc 性能比較 %

在表3 中，7 個特征選擇算法的平均fmc 精度值分別為80.985%、79.925%、67.712%、77.631 7%、68.329%、75.302%和76.461%。JFRR 算法獲得最高fmc 值。同時，從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)一步比較特征子集對fmc 值的影響，圖1 和圖2 分別給出部分?jǐn)?shù)據(jù)集的fmc 性能差異。當(dāng)數(shù)據(jù)的維數(shù)不斷增加時，JFRR 算法通過動態(tài)調(diào)整特征間的相關(guān)性和冗余性提升了特征子集的數(shù)據(jù)質(zhì)量。圖1 和圖2 的實(shí)驗(yàn)結(jié)果顯示，JFRR 算法對分類提升的效果明顯。并且，JFRR 明顯優(yōu)于MID、 CMIM、 MIQ、 JMIM、 CFR 和CMIMRMR。

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

圖1 是C4.5 在高維數(shù)據(jù)集上的性能比較。在圖1a 中，JFRR 算法的分類fmc 值為86.039%，是7 種分類算法中最高的，分別比MID、MIQ、CMIM、JMIM、CFR 和CMI-MRMR 高出5.317%、22.693%、8.661%、22.508%、8.321%和1.546%。在圖1b 中，JFRR 算法的分類fmc 值為77.595%，也是7 種分類算法中最高的，分別比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 算法的分類fmc 值為95.102%，是7 種分類算法中最高的，分別比MID、MIQ、CMIM、JMIM、 CFR 和CMI-MRMR 高出0.0%、24.361%、1.389%、29.931%和3.143%和0.0%。在圖2b 中，JFRR 算法的分類fmc 值為94.91%，是7 種分類算法中最高的，分別比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 分類器的pcm 盒圖中，使用JFRR 算法選擇出的特征集合在五位數(shù)(最小值、四分位數(shù)(第25 個百分位數(shù))、中位數(shù)、四分位數(shù)(第75 個百分位數(shù))和最大值)中體現(xiàn)出的分類效果都是最優(yōu)。同時，從圖3b 中也可以得出，在SVM 分類器的pcm 盒圖中，使用JFRR 算法選擇出的特征集合在五位數(shù)(最小值、四分位數(shù)(第25 個百分位數(shù))、中位數(shù)和四分位數(shù)(第75 個百分位數(shù)))中體現(xiàn)出的分類效果都是最優(yōu)的效果。

圖3 C4.5 分類器和SVM 分類器的pcm 盒圖

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

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

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

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

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

本節(jié)分析JFRR 與MID、CMIM、MIQ、JMIM、CFR 和CMI-MRMR 之間在交互特征依賴相關(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)定義為衡量交互特征依賴性動態(tài)變化標(biāo)準(zhǔn)。但是，JMIM 算法卻忽視特征冗余性變化。因此，得出JFRR 與其他特征選擇算法差異明顯。

表5 算法比較

4 結(jié) 束 語

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

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