基于互信息的多級(jí)特征選擇算法

雍菊亞，周忠眉*

（1.閩南師范大學(xué)計(jì)算機(jī)學(xué)院，福建漳州 363000；2.數(shù)據(jù)科學(xué)與智能應(yīng)用福建省高等學(xué)校重點(diǎn)實(shí)驗(yàn)室，福建漳州 363000）

（?通信作者電子郵箱64523040@qq.com）

0 引言

隨著大數(shù)據(jù)的不斷增長(zhǎng)［1］，特征選擇在機(jī)器學(xué)習(xí)中受到越來(lái)越多的關(guān)注。它的目的是從原始特征空間中選取一組具有代表性的特征子集，用來(lái)提升分類器的訓(xùn)練速度，從而達(dá)到比較好的訓(xùn)練效果［2］。因此，特征選擇成為了大數(shù)據(jù)背景下的一個(gè)重要研究方向。它通常的做法是使用某種評(píng)價(jià)準(zhǔn)則從原始特征空間中選擇特征子集。迄今為止，學(xué)者們從多個(gè)角度對(duì)特征選擇進(jìn)行了定義，如特征子集是否能識(shí)別目標(biāo)、預(yù)測(cè)精度是否降低、原始數(shù)據(jù)類分布是否會(huì)改變等。但是，如何挑選出一個(gè)符合上述條件且盡可能小的特征子集成為了一個(gè)研究難點(diǎn)。

目前，大多數(shù)特征算法［3-8］都可以選出強(qiáng)相關(guān)特征、去除無(wú)關(guān)特征，并且在一定程度上去除了冗余特征。比如：文獻(xiàn)［9］提出的ReliefF 算法通過(guò)特征對(duì)近距離樣本的區(qū)分能力賦予特征權(quán)重，并選取滿足權(quán)重閾值的特征。文獻(xiàn)［10］提出的條件互信息最大化準(zhǔn)則（Conditional Mutual Information Maximization criterion，CMIM）算法在挑選與標(biāo)簽相關(guān)的特征的同時(shí)，也利用條件互信息對(duì)冗余部分進(jìn)行了最大化處理。文獻(xiàn)［11］提出的基于聯(lián)合互信息（Join Mutual Information，JMI）的特征選擇方法在冗余部分進(jìn)行了均值化處理，基于聯(lián)合互信息選取累加和值大的特征，并認(rèn)為這些特征構(gòu)成了最優(yōu)特征子集。文獻(xiàn)［12］提出的mRMR（minimal-Redundancy-Maximal-Relevance criterion）算法和文獻(xiàn)［13］提出的改進(jìn)的最大相關(guān)最小冗余（improve Maximum Relevance and Minimum Redundancy）特征搜索算法通過(guò)特征與標(biāo)簽的相關(guān)度以及與已選特征子集的冗余度對(duì)特征進(jìn)行打分，并選取得分高的特征。文獻(xiàn)［14］提出的雙輸入對(duì)稱關(guān)聯(lián)（Double Input Symmetrical Relevance，DISR）算法挑選出所有表現(xiàn)最優(yōu)的特征，認(rèn)為其形成的特征子集有較高的分類性能。文獻(xiàn)［15］提出的FCBF（Fast Correlation-Based Filter solution）算法通過(guò)特征與標(biāo)簽的相關(guān)度選取滿足相關(guān)度閾值的特征，然后再利用馬爾可夫毯原理進(jìn)行去冗余。上述幾種特征選擇算法出發(fā)點(diǎn)不同，各有側(cè)重點(diǎn)，也都取得了較好的分類性能。

但是，理想的特征選擇算法要能去除無(wú)關(guān)和弱相關(guān)且冗余的特征，并能保留強(qiáng)相關(guān)［16］和弱相關(guān)非冗余特征。因此，在挑選出強(qiáng)相關(guān)特征、去除無(wú)關(guān)特征的前提下，冗余特征的處理決定了特征子集分類性能的好壞。首先，若是相關(guān)度的臨界值設(shè)置過(guò)高，算法挑選出的強(qiáng)相關(guān)特征就會(huì)過(guò)少，容易遺漏重要特征；若是過(guò)低，所選取的特征數(shù)量過(guò)大，需要復(fù)雜的去冗余過(guò)程。此外，某些特征與標(biāo)簽的相關(guān)度不高，但與其他特征組合后，會(huì)增加它們與標(biāo)簽的相關(guān)度，這樣的特征更不易被選進(jìn)。文獻(xiàn)［17］提出的最大相關(guān)最小冗余聯(lián)合互信息（Joint Mutual information of Max-relevance and min-redundanCy，JMMC）算法通過(guò)條件互信息和交互信息，并利用最大相關(guān)最小冗余的思想，有效地識(shí)別出相關(guān)、冗余和無(wú)關(guān)特征，但是也會(huì)遺漏與標(biāo)簽相關(guān)度不高，但與其他標(biāo)簽組合后有較強(qiáng)相關(guān)度的特征。基于上述情況，本文提出了一種基于互信息的多級(jí)特征選擇算法（Multi-Level Feature Selection algorithm based on Mutual Information，MI_MLFS）。該算法的目的就是要克服當(dāng)前過(guò)度去冗余而導(dǎo)致有用信息丟失的局限性。根據(jù)特征與標(biāo)簽的相關(guān)度，該算法將特征分成三類：強(qiáng)相關(guān)、次強(qiáng)相關(guān)和其他特征，并分別對(duì)這三類特征采用不同的方式進(jìn)行選?。?）MI_MLFS 直接選進(jìn)強(qiáng)相關(guān)特征；2）對(duì)于次強(qiáng)相關(guān)特征，MI_MLFS 利用互信息衡量特征與標(biāo)簽的相關(guān)度，以及特征與標(biāo)簽、已選特征子集的相關(guān)度，兩者差值較大的特征就被認(rèn)為是冗余度較低的特征，將其加入到已選特征子集中；3）對(duì)于其他特征，MI_MLFS 度量它們與已選特征子集里的特征進(jìn)行組合后與標(biāo)簽的相關(guān)度，并將相關(guān)度有所提升的特征加入到已選特征子集中。實(shí)驗(yàn)結(jié)果表明，MI_MLFS 具有較優(yōu)的分類性能。

1 相關(guān)定義

假設(shè)數(shù)據(jù)集為T，且T={t1，t2，…，tn}，其中n表示此數(shù)據(jù)集的樣本數(shù)量。設(shè)此數(shù)據(jù)集的特征集合為F，且F={f1，f2，…，fm}，其中m表示特征個(gè)數(shù)。設(shè)此數(shù)據(jù)集的標(biāo)簽集合為C，且C={c1，c2，…，cs}，其中s表示此數(shù)據(jù)集的標(biāo)簽值的個(gè)數(shù)。

定義1信息熵［18］。設(shè)fi為F中的任意特征，且fi={fi1，fi2，…，fil}，其中l(wèi)表示特征fi的特征值的個(gè)數(shù)。則fi的信息熵定義為：

其中，p(fij)表示值fij在數(shù)據(jù)集中發(fā)生的概率。

定義2聯(lián)合熵［19］。設(shè)fi為F中的任意特征，且fi={fi1，fi2，…，fil}，標(biāo)簽集合C={c1，c2，…，cs}，則特征fi和標(biāo)簽集合C的聯(lián)合熵定義為：

其中，p(fij，ck)表示fij和ck在整個(gè)數(shù)據(jù)集中同時(shí)發(fā)生的概率。

定義3互信息［20］。設(shè)fi為F中的任意特征，且fi={fi1，fi2，…，fil}，標(biāo)簽集合C={c1，c2，…，cs}，則特征fi和標(biāo)簽集合C的互信息定義為：

定義4聯(lián)合屬性的互信息。設(shè)fi、fj為特征集合F中的任意兩個(gè)特征，且fi={fi1，fi2，…，fil}，fj={fj1，fj2，…，fjh}，其中，l表示特征fi的特征值的個(gè)數(shù)，h表示特征fj的特征值的個(gè)數(shù)。則fi和fj的聯(lián)合屬性與標(biāo)簽集合C的互信息定義為：

定義5特征與標(biāo)簽的相關(guān)度［12］。設(shè)fi為特征集合F的任意一個(gè)特征，則fi與標(biāo)簽C的相關(guān)度定義為：

定義6特征之間的冗余度［21］。設(shè)一特征集合為A，且A={f1，f2，…，fk}，其中，k為A中的特征個(gè)數(shù)。fi為A中的任意一個(gè)特征，則fi與集合A中其他特征的冗余度定義為：

其中，參數(shù)α∈(0，1)。λ(fi，{Afi})的值越小，說(shuō)明fi在集合A中冗余度越大。

定義7組合特征的相關(guān)度。設(shè)fi、fj為任意兩個(gè)特征，則特征fi與fj的組合特征的相關(guān)度定義為：

其中，β∈(0，1)。λfi，fj的值越大，就表示fi與fj的聯(lián)合屬性的互信息越大，也表示特征fi與fj的組合特征與標(biāo)簽的相關(guān)度越大。同時(shí)，組合特征的相關(guān)度反映了聯(lián)合屬性的互信息與各特征互信息之間的關(guān)系。

定義8強(qiáng)相關(guān)特征。設(shè)δ1為給定的一個(gè)相關(guān)度閾值，fi為特征集合F中的任意一個(gè)特征，若特征fi與標(biāo)簽集合C的相關(guān)度大于δ1，則稱fi為特征集合F的強(qiáng)相關(guān)特征。

定義9次強(qiáng)相關(guān)特征。設(shè)δ1、δ2為給定的兩個(gè)相關(guān)度閾值，且δ1>δ2，fi為特征集合F中的任意一個(gè)特征。若特征fi與標(biāo)簽集合C的相關(guān)度大于δ2且小于δ1，則稱fi為特征集合F的次強(qiáng)相關(guān)特征。

定義10基于組合的強(qiáng)相關(guān)特征。設(shè)特征集合A={f1，f2，…，fk}，其中，k為集合A中的特征個(gè)數(shù)，?fi?A。計(jì)算fi與特征集合A中所有特征組合的λfi，fj值，得到λ={λfi，f1，λfi，f2，…，λfi，fk}。如果集合λ中存在90%的λfi，fj> 0，則稱fi為關(guān)于A的基于組合的強(qiáng)相關(guān)特征。

2 算法描述

為了不漏選重要的特征，同時(shí)盡量少選冗余特征，MI_MLFS 根據(jù)每個(gè)特征與標(biāo)簽的相關(guān)度，將特征集合F劃分為三個(gè)部分，即強(qiáng)相關(guān)特征集、次強(qiáng)相關(guān)特征集和其他特征集，并對(duì)這三個(gè)集合的特征分別用不同的方法進(jìn)行選取。首先，MI_MLFS 選取所有強(qiáng)相關(guān)特征；其次，對(duì)于次強(qiáng)相關(guān)特征集，根據(jù)定義6 中特征之間的冗余度公式，去除其冗余的特征；最后，對(duì)于其他特征的集合，根據(jù)定義7 中特征組合后相關(guān)度的計(jì)算公式，選取能增強(qiáng)集合相關(guān)度的特征。下面給出MI_MLFS整個(gè)選取過(guò)程的具體步驟和偽代碼。

2.1 三類特征的劃分

MI_MLFS 將特征集合F劃分為強(qiáng)相關(guān)特征集、次強(qiáng)相關(guān)特征集和其他特征集。具體劃分過(guò)程如下：

1）對(duì)于特征集合F={f1，f2，…，fm}，根據(jù)式（5），計(jì)算F中每個(gè)特征與標(biāo)簽的相關(guān)度，得到所有特征相關(guān)度的集合，記為R，且令R={R1，R2，…，Rm}。其中，Ri代表第i個(gè)特征與標(biāo)簽的相關(guān)度。

2）給定相關(guān)度閾值δ1、δ2，且δ1∈(0，1)，δ2∈(0，1)，δ1>δ2。對(duì)于特征相關(guān)度的集合R，若Ri>δ1，則根據(jù)定義8，特征fi為強(qiáng)相關(guān)特征，從而得到所有強(qiáng)相關(guān)特征的集合，并記為S1；若δ1>Ri>δ2，則根據(jù)定義9，特征fi為次強(qiáng)相關(guān)特征，從而得到次強(qiáng)相關(guān)特征的集合，并記為S2。最后，F(xiàn)-S1-S2為其他特征的集合，并記為S3。

2.2 集合S1和集合S2中特征的選取

由于集合S1中是強(qiáng)相關(guān)特征，算法直接選取S1中所有特征。對(duì)于次強(qiáng)相關(guān)特征集合S2，算法去除S2中的冗余特征，具體方法如下：

1）給定閾值t，t∈(0，1)。在次強(qiáng)相關(guān)集合S2中選取特征與標(biāo)簽的相關(guān)度大于t的所有特征，得到S2的特征子集M，即M為次強(qiáng)相關(guān)特征集合中相關(guān)度較大的特征，記=S2-M。

2）選取集合中相關(guān)度最大的特征fi，將其添加到子集M中。根據(jù)定義6，計(jì)算M中每個(gè)特征與其他特征的冗余度，并刪除集合M中冗余度最大的特征，將刪除后的集合記為Mi。

3）選取集合(-fi)中相關(guān)度最大的特征fj，將其添加到子集Mi中。根據(jù)定義6，計(jì)算Mi中每個(gè)特征與其他特征的冗余度，并刪除集合Mi中冗余度最大的特征，將刪除后的集合記為Mj。

4）選取集合(-fi-fj)中相關(guān)度最大的特征fk，將其添加到子集Mj中。根據(jù)定義6，計(jì)算Mj中每個(gè)特征與其他特征的冗余度，并刪除集合Mj中冗余度最大的特征，將刪除后的集合記為Mk。

5）以此類推，直至集合(-fi-fj-…-fh)中沒(méi)有特征，并得到集合Mh，且集合Mh中的特征均為次強(qiáng)相關(guān)且低冗余的特征。

2.3 其他特征的集合S3中特征的選取

對(duì)于集合S3中的所有特征，利用2.2 節(jié)得到的集合Mh，根據(jù)定義10 中的相關(guān)度定義，確定是否將S3的特征選入Mh中。具體實(shí)施如下：

1）選取集合S3中相關(guān)度最大的特征fi，根據(jù)定義7，計(jì)算特征fi與集合Mh中的每個(gè)特征組合后與標(biāo)簽的相關(guān)度，得到相關(guān)度集合λ1。如果集合λ1中存在90%的λfi，fj> 0，那么fi為關(guān)于Mh的基于組合的強(qiáng)相關(guān)特征，將其加入到集合Mh中。

2）選取集合S3中相關(guān)度最大的特征fs，根據(jù)定義7，計(jì)算特征fs與集合Mh中的每個(gè)特征組合后與標(biāo)簽的相關(guān)度，得到相關(guān)度集合λ2。如果集合λ2中存在90%的λfs，fj> 0，那么fs為關(guān)于Mh的基于組合的強(qiáng)相關(guān)特征，將其加入到集合Mh中。

3）選取集合(S3-fi-fs)中相關(guān)度最大的特征fk，根據(jù)定義7，計(jì)算特征fk與集合Mh中的每個(gè)特征組合后與標(biāo)簽的相關(guān)度，得到相關(guān)度集合λ3。如果集合λ3中存在90%的λfk，fj>0，那么fk為關(guān)于Mh的基于組合的強(qiáng)相關(guān)特征，將其加入到集合Mh中。

4）以此類推，直至集合(S3-fi-fs-…-fh)為空集。最后，集合S3中所有特征均被確定是否選取。

2.4 MI_MLFS的偽代碼

根據(jù)MI_MLFS 的三級(jí)選取過(guò)程，給出下面相應(yīng)的三個(gè)算法。其中，算法1 為特征集合的劃分及強(qiáng)相關(guān)特征的選取，算法2為次強(qiáng)相關(guān)集合中冗余特征的去除，算法3為基于組合的強(qiáng)相關(guān)特征的選取。

算法1 主要是根據(jù)相關(guān)度閾值將原始特征空間分成強(qiáng)相關(guān)、次強(qiáng)相關(guān)和其他特征集。選取強(qiáng)相關(guān)特征后，根據(jù)算法2和算法3 分別對(duì)次強(qiáng)相關(guān)特征和其他特征進(jìn)一步挑選。其中，第2）～4）行為特征與標(biāo)簽相關(guān)度的計(jì)算，第6）行為強(qiáng)相關(guān)特征的選取，第9）行為次強(qiáng)相關(guān)特征的選取，第13）行為其他特征的選取。

算法2 主要是從次強(qiáng)相關(guān)特征中選取冗余度較低的特征。第5）～7）行為關(guān)鍵步驟，計(jì)算集合M中的每個(gè)特征與其他特征的冗余度。第8）～9）行將冗余度最大的特征從已選特征子集中刪除。

算法3 主要是在其他特征集合中挑選出基于組合的強(qiáng)相關(guān)特征。第3）行是關(guān)鍵步驟，考慮待選特征與已選特征進(jìn)行組合后，是否能增強(qiáng)已選特征與標(biāo)簽的相關(guān)度。第8）～10）行表示若90%的已選特征與其組合后，與標(biāo)簽的相關(guān)度有所增強(qiáng)，則認(rèn)為此特征為基于組合的強(qiáng)相關(guān)特征。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)計(jì)與數(shù)據(jù)集

為了驗(yàn)證MI_MLFS的有效性，選用ReliefF算法［9］、mRMR算法［13］、JMI算法［11］、CMIM 算法［10］和DISR 算法［14］進(jìn)行對(duì)比實(shí)驗(yàn)。數(shù)據(jù)集的簡(jiǎn)要描述如表1 所示。實(shí)驗(yàn)平臺(tái)為PC（Windows 10，Intel Core i7-8550U CPU@ 1.80 GHz 1.99 GHz），使用的軟件為Matlab 2016a 和R。本文所使用的分類器是支持向量機(jī)（Support Vector Machine，SVM）和分類回歸樹（Classification and Regression Tree，CART）。

3.2 結(jié)果分析

本文均采用分類準(zhǔn)確率來(lái)預(yù)測(cè)特征算法的優(yōu)劣。同時(shí)，為了進(jìn)一步說(shuō)明不同算法在不同分類器和數(shù)據(jù)集上的優(yōu)劣，本文使用Win/Draw/Loss 來(lái)統(tǒng)計(jì)并分析算法兩兩之間的差異。Win 表示算法A 優(yōu)于B，Draw 表示算法A 等于B，Loss 表示算法A差于B［17］。

表2的數(shù)據(jù)表示6種算法在不同數(shù)據(jù)集上，采用10折交叉驗(yàn)證法［22］在SVM 分類器得到的平均分類準(zhǔn)確率結(jié)果。從表2可以看出，MI_MLFS 在15 個(gè)數(shù)據(jù)集上的分類準(zhǔn)確率均比ReliefF算法高，并且MI_MLFS在這15個(gè)數(shù)據(jù)集上的平均準(zhǔn)確率（AVG）相較ReliefF 算法提高了6.25 個(gè)百分點(diǎn)。MI_MLFS在15個(gè)數(shù)據(jù)集中的14個(gè)上的分類準(zhǔn)確率均比mRMR算法高，并且MI_MLFS 在這15 個(gè)數(shù)據(jù)集上的平均準(zhǔn)確率相較mRMR算法提高了4.89 個(gè)百分點(diǎn)。MI_MLFS 在15 個(gè)數(shù)據(jù)集中的14個(gè)上的分類準(zhǔn)確率均比JMI 算法高，并且MI_MLFS 在這15 個(gè)數(shù)據(jù)集上的平均準(zhǔn)確率比JMI 算法提高了6.81 個(gè)百分點(diǎn)。MI_MLFS 在15 個(gè)數(shù)據(jù)集上的分類準(zhǔn)確率均比CMIM 算法高，并且MI_MLFS在這15個(gè)數(shù)據(jù)集上的平均準(zhǔn)確率比CMIM算法提高了6.18 個(gè)百分點(diǎn)。MI_MLFS 在15 個(gè)數(shù)據(jù)集上的分類準(zhǔn)確率均比DISR 算法高，并且MI_MLFS 算法在這15 個(gè)數(shù)據(jù)集上的平均準(zhǔn)確率相較DISR算法提高了7.31個(gè)百分點(diǎn)。

表1 實(shí)驗(yàn)數(shù)據(jù)集Tab.1 Datasets used in experiments

表2 基于SVM分類器的不同算法在不同數(shù)據(jù)集上的分類準(zhǔn)確率 單位：%Tab.2 Classification accuracy of different algorithms on different datasets based on SVM classifier unit：%

表3 表示6 種算法在不同數(shù)據(jù)集上，采用10 折交叉驗(yàn)證法在CART 分類器得到的平均分類準(zhǔn)確率結(jié)果。從表3 可以看出，MI_MLFS 在15 個(gè)數(shù)據(jù)集中的14 個(gè)上的分類準(zhǔn)確率均比ReliefF 算法高，并且MI_MLFS 在這15 個(gè)數(shù)據(jù)集上的平均準(zhǔn)確率相較ReliefF 算法提高了4.88 個(gè)百分點(diǎn)。MI_MLFS 在15個(gè)數(shù)據(jù)集中的14個(gè)上的分類準(zhǔn)確率均比mRMR算法高，并且MI_MLFS 在這15 個(gè)數(shù)據(jù)集上的平均準(zhǔn)確率相較mRMR 算法提高了3.93個(gè)百分點(diǎn)。MI_MLFS 在15個(gè)數(shù)據(jù)集中的13個(gè)上的分類準(zhǔn)確率均比JMI 算法高，并且MI_MLFS 在這15 個(gè)數(shù)據(jù)集上的平均準(zhǔn)確率相較JMI 算法提高了5.08 個(gè)百分點(diǎn)。MI_MLFS 在15 個(gè)數(shù)據(jù)集中的14 個(gè)上的分類準(zhǔn)確率均比CMIM 算法高，并且MI_MLFS 在這15 個(gè)數(shù)據(jù)集上的平均準(zhǔn)確率相較CMIM 算法提高了4.72 個(gè)百分點(diǎn)。MI_MLFS 在15 個(gè)數(shù)據(jù)集中的13 個(gè)上的分類準(zhǔn)確率均比DISR 算法高，并且MI_MLFS 在這15 個(gè)數(shù)據(jù)集上的平均準(zhǔn)確率比DISR 算法提高了4.21個(gè)百分點(diǎn)。

表3 基于CART分類器的不同算法在不同數(shù)據(jù)集上的分類準(zhǔn)確率單位：%Tab.3 Classification accuracy of different algorithms on different datasets based on CART classifier unit：%

表4 是MI_MLFS 與其他5 種算法在SVM 分類器和CART分類器上的平均分類準(zhǔn)確率兩兩比較的結(jié)果。例如，表4 中第三行第二列的15/0/0 表示MI_MLFS 與ReliefF 算法在SVM分類器上的對(duì)比結(jié)果：在15個(gè)數(shù)據(jù)集上MI_MLFS的性能比較好，在0 個(gè)數(shù)據(jù)集上與ReliefF 算法性能相同，在0 個(gè)數(shù)據(jù)集上MI_MLFS 的性能較差。由表4 可以看出，在使用SVM 分類器時(shí)，MI_MLFS在所有數(shù)據(jù)集上均優(yōu)于ReliefF 算法、CMIM 算法和DISR 算法。與mRMR 算法以及JMI 算法相比，均只在一個(gè)數(shù)據(jù)集上，MI_MLFS 略遜一點(diǎn)。在使用CART 分類器時(shí)，MI_MLFS 在所有數(shù)據(jù)集上均優(yōu)于ReliefF 算法和mRMR 算法。和JMI 算法以及DISR 算法相比，均只在一個(gè)數(shù)據(jù)集上，MI_MLFS 略遜一點(diǎn)。和CMIM 算法相比，在13 個(gè)數(shù)據(jù)集上，MI_MLFS的分類準(zhǔn)確率較高。

表4 MI_MLFS算法與其他基于特征選擇算法的Win/Draw/Loss分析Tab.4 Win/Draw/Loss analysis of MI_MLFS and other feature selection algorithms

3.3 大樣本高維數(shù)據(jù)集的分析

圖1 表示當(dāng)使用SVM 分類器時(shí)，在RELATHE、PCMAC 和BASEHOC 這3 個(gè)數(shù)據(jù)集上，6 種算法在所選特征數(shù)相同的情況下，采用10 折交叉驗(yàn)證法得到的各算法的平均分類準(zhǔn)確率。其中，橫坐標(biāo)表示依次遞増的所選特征子集比例，縱坐標(biāo)表示平均分類精度。根據(jù)圖1 的結(jié)果可知，在同等特征數(shù)的情況下，MI_MLFS 都具有明顯優(yōu)勢(shì)。這是因?yàn)镸I_MLFS 的三級(jí)選取過(guò)程不僅選取了與標(biāo)簽強(qiáng)相關(guān)的單個(gè)特征，還選取了基于組合的強(qiáng)相關(guān)特征。在特征比例為0.1%～0.3%的情況下，MI_MLFS 的分類性能尤為顯著。由此可以看出，面對(duì)大樣本高維數(shù)據(jù)集，MI_MLFS 可以選取一個(gè)規(guī)模較小的，并且分類性能較好的特征子集。

圖1 基于SVM分類器在大樣本高維數(shù)據(jù)集上的分類準(zhǔn)確率和所選特征比例Fig.1 Classification accuracy and proportion of selected feature subset on datasets with large and high-dimensional samples based on SVM classifier

圖2 表示當(dāng)使用CART 分類器時(shí)，在RELATHE、PCMAC和BASEHOC 這3 個(gè)數(shù)據(jù)集上，6 種算法在所選特征數(shù)相同的情況下，采用10 折交叉驗(yàn)證法得到的各算法的平均分類準(zhǔn)確率。其中，橫坐標(biāo)表示依次遞増的所選特征子集比例，縱坐標(biāo)表示平均分類精度。

根據(jù)圖2 的結(jié)果可知，在同等特征數(shù)的情況下，MI_MLFS在這3 個(gè)大樣本高維數(shù)據(jù)集上，相較其他5 種算法，具有較高的分類準(zhǔn)確率。其中，在特征比例較小的情況下，MI_MLFS的分類性能較為顯著。由此表明，與其他5 種算法相比，MI_MLFS 在大樣本高維數(shù)據(jù)集上可以選取出規(guī)模更小、分類精度更好的特征子集。

3.4 小樣本高維數(shù)據(jù)集的分析

圖3 表示當(dāng)使用SVM 分類器時(shí)，在LYM、Lymphoma、Colon、Leukemia 和LUNG 這4 個(gè)小樣本高維數(shù)據(jù)集上，6 種算法在所選特征數(shù)相同的情況下，得到的各算法分類準(zhǔn)確率的結(jié)果。其中，橫坐標(biāo)表示依次遞増的所選特征子集比例，縱坐標(biāo)表示平均分類精度。

根據(jù)圖3 的結(jié)果可知，MI_MLFS 在LYM、Lymphoma、Leukemia 和LUNG 這4 個(gè)小樣本高維數(shù)據(jù)集上的分類精度均優(yōu)于其他5 種算法。在Colon 數(shù)據(jù)集上，當(dāng)特征比例為0.3%時(shí)，MI_MLFS具有最好的分類性能。

圖2 基于CART分類器的大樣本高維數(shù)據(jù)集上的分類準(zhǔn)確率和所選特征比例Fig.2 Classification accuracy and proportion of selected feature subset on datasets with large and high-dimensional samples based on CART classifier

圖3 基于SVM分類器的小樣本高維數(shù)據(jù)集上的分類準(zhǔn)確率和所選特征比例Fig.3 Classification accuracy and proportion of selected feature subset on datasets with small and high-dimensional samples based on SVM classifier

圖4 表示當(dāng)使用CART 分類器時(shí)，在LYM、Lymphoma、Colon、Leukemia 和LUNG 這5 個(gè)小樣本高維數(shù)據(jù)集上，6 種算法在所選特征數(shù)相同的情況下，得到的各算法分類準(zhǔn)確率的結(jié)果。其中，橫坐標(biāo)表示依次遞増的所選特征子集比例，縱坐標(biāo)表示平均分類精度。根據(jù)圖4的結(jié)果可知，相較其他5種算法，MI_MLFS 整體上的分類精度較好。其中，在LYM 和Leukemia 數(shù)據(jù)集上具有明顯優(yōu)勢(shì)。在Lymphoma 數(shù)據(jù)集上，當(dāng)特征比例為0.6%時(shí)，MI_MLFS 具有最好的分類性能。在Colon 數(shù)據(jù)集和LUNG 數(shù)據(jù)集上，當(dāng)特征比例為0.1%時(shí)，MI_MLFS 具有最好的分類性能。由此表明，面對(duì)小樣本高維數(shù)據(jù)集，MI_MLFS 能夠選取一個(gè)規(guī)模較小，并且分類性能較好的特征子集。

圖4 基于CART分類器的小樣本高維數(shù)據(jù)集上的分類準(zhǔn)確率和所選特征比例Fig.4 Classification accuracy and proportion of selected feature subset on datasets with small and high-dimensional samples based on CART classifier

4 結(jié)語(yǔ)

針對(duì)僅選取強(qiáng)相關(guān)且低冗余的特征不能得到較好的特征子集的問(wèn)題，本文提出了一種基于互信息的多級(jí)特征選擇算法（MI_MLFS）。該算法對(duì)特征進(jìn)行三級(jí)選取：在選取強(qiáng)相關(guān)特征之后，對(duì)次強(qiáng)相關(guān)的特征集合進(jìn)行去冗余，得到低冗余的次強(qiáng)相關(guān)特征；最后，根據(jù)特征與集合的相關(guān)度，在其他特征的集合中選取基于組合的強(qiáng)相關(guān)特征。實(shí)驗(yàn)結(jié)果表明，MI_MLFS 選取了較優(yōu)的特征子集，有效地提高了分類的準(zhǔn)確率。然而，本文算法是基于類平衡的假設(shè)，沒(méi)有考慮到少數(shù)類的樣本對(duì)特征選擇算法的影響。今后將進(jìn)一步討論不平衡數(shù)據(jù)的特征選擇方法。