基于互信息的多級特征選擇算法

雍菊亞，周忠眉*

（1.閩南師范大學計算機學院，福建漳州 363000；2.數據科學與智能應用福建省高等學校重點實驗室，福建漳州 363000）

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

0 引言

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

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

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

1 相關定義

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

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

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

定義2聯合熵［19］。設fi為F中的任意特征，且fi={fi1，fi2，…，fil}，標簽集合C={c1，c2，…，cs}，則特征fi和標簽集合C的聯合熵定義為：

其中，p(fij，ck)表示fij和ck在整個數據集中同時發生的概率。

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

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

定義5特征與標簽的相關度［12］。設fi為特征集合F的任意一個特征，則fi與標簽C的相關度定義為：

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

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

定義7組合特征的相關度。設fi、fj為任意兩個特征，則特征fi與fj的組合特征的相關度定義為：

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

定義8強相關特征。設δ1為給定的一個相關度閾值，fi為特征集合F中的任意一個特征，若特征fi與標簽集合C的相關度大于δ1，則稱fi為特征集合F的強相關特征。

定義9次強相關特征。設δ1、δ2為給定的兩個相關度閾值，且δ1>δ2，fi為特征集合F中的任意一個特征。若特征fi與標簽集合C的相關度大于δ2且小于δ1，則稱fi為特征集合F的次強相關特征。

定義10基于組合的強相關特征。設特征集合A={f1，f2，…，fk}，其中，k為集合A中的特征個數，?fi?A。計算fi與特征集合A中所有特征組合的λfi，fj值，得到λ={λfi，f1，λfi，f2，…，λfi，fk}。如果集合λ中存在90%的λfi，fj> 0，則稱fi為關于A的基于組合的強相關特征。

2 算法描述

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

2.1 三類特征的劃分

MI_MLFS 將特征集合F劃分為強相關特征集、次強相關特征集和其他特征集。具體劃分過程如下：

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

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

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

由于集合S1中是強相關特征，算法直接選取S1中所有特征。對于次強相關特征集合S2，算法去除S2中的冗余特征，具體方法如下：

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

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

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

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

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

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

對于集合S3中的所有特征，利用2.2 節得到的集合Mh，根據定義10 中的相關度定義，確定是否將S3的特征選入Mh中。具體實施如下：

1）選取集合S3中相關度最大的特征fi，根據定義7，計算特征fi與集合Mh中的每個特征組合后與標簽的相關度，得到相關度集合λ1。如果集合λ1中存在90%的λfi，fj> 0，那么fi為關于Mh的基于組合的強相關特征，將其加入到集合Mh中。

2）選取集合S3中相關度最大的特征fs，根據定義7，計算特征fs與集合Mh中的每個特征組合后與標簽的相關度，得到相關度集合λ2。如果集合λ2中存在90%的λfs，fj> 0，那么fs為關于Mh的基于組合的強相關特征，將其加入到集合Mh中。

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

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

2.4 MI_MLFS的偽代碼

根據MI_MLFS 的三級選取過程，給出下面相應的三個算法。其中，算法1 為特征集合的劃分及強相關特征的選取，算法2為次強相關集合中冗余特征的去除，算法3為基于組合的強相關特征的選取。

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

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

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

3 實驗與結果分析

3.1 實驗設計與數據集

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

3.2 結果分析

本文均采用分類準確率來預測特征算法的優劣。同時，為了進一步說明不同算法在不同分類器和數據集上的優劣，本文使用Win/Draw/Loss 來統計并分析算法兩兩之間的差異。Win 表示算法A 優于B，Draw 表示算法A 等于B，Loss 表示算法A差于B［17］。

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

表1 實驗數據集Tab.1 Datasets used in experiments

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

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

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

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

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

3.3 大樣本高維數據集的分析

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

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

圖2 表示當使用CART 分類器時，在RELATHE、PCMAC和BASEHOC 這3 個數據集上，6 種算法在所選特征數相同的情況下，采用10 折交叉驗證法得到的各算法的平均分類準確率。其中，橫坐標表示依次遞増的所選特征子集比例，縱坐標表示平均分類精度。

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

3.4 小樣本高維數據集的分析

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

根據圖3 的結果可知，MI_MLFS 在LYM、Lymphoma、Leukemia 和LUNG 這4 個小樣本高維數據集上的分類精度均優于其他5 種算法。在Colon 數據集上，當特征比例為0.3%時，MI_MLFS具有最好的分類性能。

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

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

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

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

4 結語

針對僅選取強相關且低冗余的特征不能得到較好的特征子集的問題，本文提出了一種基于互信息的多級特征選擇算法（MI_MLFS）。該算法對特征進行三級選?。涸谶x取強相關特征之后，對次強相關的特征集合進行去冗余，得到低冗余的次強相關特征；最后，根據特征與集合的相關度，在其他特征的集合中選取基于組合的強相關特征。實驗結果表明，MI_MLFS 選取了較優的特征子集，有效地提高了分類的準確率。然而，本文算法是基于類平衡的假設，沒有考慮到少數類的樣本對特征選擇算法的影響。今后將進一步討論不平衡數據的特征選擇方法。