一種小樣本數據的特征選擇方法

許 行 張 凱 王文劍,2

1(山西大學計算機與信息技術學院 太原 030006) 2(計算智能與中文信息處理教育部重點實驗室(山西大學) 太原 030006)

隨著通信和存儲技術的發展、網絡的普及，各領域數據的產生和收集變的更加容易，大數據及相關產業應運而生，而處理這些數據成為機器學習與數據挖掘領域研究的核心及關鍵問題.現實生活中，有一類稱為小樣本的數據，其特點是相比于特征維數其樣本數目較少，比如基因表達譜數據需要通過微陣列實驗獲取，實驗成本的昂貴限制了實驗次數，使得數據的規模較小，同時該實驗測試上萬個基因的表達水平，又使得數據維數非常高，這使得傳統的機器學習算法處理小樣本數據可能會失效[1]，因此，通過特征選擇來降低數據維數是解決它的一種有效途徑.

特征選擇能在不失去數據原有價值的基礎上去除不相關和冗余特征，提高數據的質量,降低學習算法在數據集上的計算代價，加快數據挖掘的速度，同時有助于生成更易理解的結果和更緊湊、泛化能力更強的模型[2].根據是否與后續完成數據分析任務(如分類、聚類、回歸等)的算法相獨立，特征選擇方法可分為嵌入、封裝和過濾3類[3].嵌入型方法將特征選擇算法作為分類算法的一個組成部分嵌入到分類算法中，封裝型方法將后續分類算法的分類準確率作為所選特征子集的評價準則，過濾型方法與后續分類算法無關，直接利用訓練數據的統計性能評估特征.對于嵌入型和封裝型方法，將特征選擇算法作為分類算法的組成部分或者使用分類算法作為特征子集的評價標準，都會造成特征選擇算法的計算成本隨著維數的升高而急劇上升，可能不適合小樣本數據的特征選擇.而過濾型方法有獨立的評估函數，通過樣本的統計屬性來評價特征子集對于分類任務所起的作用，它不將任何分類器納入到評估標準，由此選擇出無關于特定分類算法的特征子集.因此，過濾型方法可以離線進行特征選擇，它相對于后續分類算法的獨立性可避免高維數據造成的較高的分類算法運行成本，與嵌入型和封裝型相比，過濾型特征選擇方法在計算上是高效的.

典型的過濾型特征選擇方法使用距離度量、信息度量、相關性度量和一致性度量等統計指標衡量特征的類區分能力.距離度量是利用距離來度量特征之間、特征與類別之間的相關性，常用的有歐氏距離、S階閔可夫斯基測度、切比雪夫距離、平方距離等，Relief[4]及其變種ReliefF[5]、BFF(best first strategy for feature selection)[6]和基于核空間距離方法[7]都是基于距離度量的算法.信息度量是指選擇具有最小不確定性的特征，常用的信息度量為衡量信息不確定性的熵函數，如Shannon熵、條件熵、信息增益、互信息(mutual information， MI)等.BIF(best individual features)[8], UFS -MI(unsupervised feature selection approach based on mutual information)[9], CMIM(conditional mutual information maximiza-tion)[10]分別是使用互信息和條件互信息作為評價標準的特征選擇方法.相關性度量是利用特征與類別的可分離性間的重要性程度判斷相關性，如Pearson相關系數、概率誤差、Fisher分數、線性可判定分析、最小平方回歸誤差[11]、平方關聯系數[12]等.Ding等人[13]和Peng等人[14]在mRMR(minimal-redundancy-maximal- relevance)中處理連續特征時,分別使用F-Statistic和Pearson相關系數度量特征與類別和已選特征間的相關性程度，Hall[15]給出一種同時考慮特征的類區分能力和特征間冗余性的相關性度量標準.一致性度量是指給定2個樣本,若他們特征值相同而類別不同,則它們是不一致的，否則是一致的，一致性準則試圖保留原始特征的辨識能力，用不一致率來度量，典型算法有Focus[16]，LVF(Las Vegas filter)[17]等.這些方法有的運行效率不夠高，有的降維之后分類模型性能不夠好，因此研究針對小樣本數據的過濾型特征選擇方法仍有重要的價值.

由于互信息有2個優點[18]：1)可以測量隨機變量之間的多種關系，包括非線性關系，這保證了互信息在特征與類別之間的關系未知的情況下仍然有效；2)在平移、旋轉和保留特征矢量順序的特征空間變換情況下，值不會發生改變，這保證了互信息在特征選擇中的任何階段都能準確度量任意2個特征之間的關系.因此，基于互信息的過濾型特征選擇方法可以很好地度量特征與特征之間、特征與類別之間的關系，從而更有效地進行特征選擇.本文針對小樣本數據提出一種基于互信息的過濾型特征選擇方法，用以提高其選出的特征子集所構造的分類模型的分類性能，同時具有更好的運行效率.

1 小樣本數據的特征選擇方法

本文首先提出一種基于互信息的特征選擇方法(MI-based feature selection, MIFS)，根據互信息對特征排序，之后按順序迭代地對特征分組，在各組內選出與類別相關性最大的特征得到特征子集，然后利用Boruta算法[19]自動地確定最佳特征子集.

1.1 基于互信息的特征選擇方法

有效的特征選擇方法需要同時考慮特征與類別的相關性和不同特征之間的冗余性，并且避免在類別相關度差別較大的特征上計算冗余度.為了實現以上2點，提出基于互信息的特征選擇算法MIFS.考慮到互信息度量特征與類別之間的關系的優勢，MIFS先根據特征與類別之間的相關性對特征排序，之后提出了一個分組標準，將特征進行分組，并從不同的組內找到需要選出的特征作為特征子集.

給定數據集D的樣本數為n，特征維數為m，用a1,a2,…,am表示其特征，c表示其類別，特征ai的值域為Vi，c的值域為Vc.

特征ai與類別c之間的互信息I(ai,c)為

(1)

其中p(vi,vc)表示特征ai的取值為vi且類別c的取值為vc的概率.I(ai,c)的值越大，表示特征ai和類別c的關聯度越大.

計算每個特征與類別之間的互信息后，按互信息從大到小的順序對特征排序，然后對特征集進行分組，定義特征分組的標準Q為

(2)

(3)

(4)

其中，G表示一個特征組，ai,aj為G內的特征，I(ai,aj)為特征ai與特征aj之間的互信息：

(5)

其中p(vi,vj)表示特征ai的取值為vi且特征aj的取值為vj的概率.I(ai,aj)的值越大，表示特征ai和aj越相似.

這里SG為特征組G與類別的關聯度，RG為特征組G內所有特征的相似性，特征組G的Q值越大，表示該特征組中的特征與類別的關聯度越大，特征組內特征之間的冗余度越小；反之，Q值越小，表示該特征組中的特征與類別的關聯度越小，特征組內特征之間的冗余度越大.

為了計算特征分組的初始Q值，需要選出2個特征放入分組中：首先將排在第1位的特征a1放入分組，然后計算特征a1與其他每個特征ai之間的互信息，并選出互信息最大的特征，即最相似的特征放入該分組.之后按式(2)計算分組的Q值，記錄為q0.

對于其他特征，將此時排在最前面的特征添加到當前分組中，再計算其Q值，如果Qq0時停止向這個特征組添加特征，此時的特征組就作為第1個分組.在未被分組的特征上重復上述步驟得到新的特征組，依此類推，直到所有的特征都被分入特征組中，則得到所有特征組.最后取出每個特征組中的第1個特征作為其所在特征組的代表，用取出的特征構成候選特征子集.

MIFS算法的主要步驟總結如下：

算法1. MIFS算法.

輸入：數據集D、候選特征個數k；

輸出：候選特征子集Scan.

① 按式(1)計算數據集D中每個特征與類別c的互信息I(ai,c)；

② 將特征按互信息從大到小排序，得到特征集A；

③ 按以下步驟對特征集A分組：

④ 令t=1，從A中取出排在第1位的特征a1放入分組Gt；

⑤ 按式(5)計算特征a1與其他每個特征ai之間的互信息I(ai,aj)，將最大的特征放入分組Gt；

⑥ 按式(2)計算Gt的Q值，記為q0；

⑦ 從A中剩余的特征中取出排在最前面的特征放入分組Gt中，按式(2)計算Gt的Q值；如果Q≤q0，則重復步驟⑦；如果Q>q0，則將當前的Gt作為第1個分組；

⑧ 令t=t+1，在剩下的A上重復步驟④～⑦，得到新的特征組Gt，直到t=k，或者A中所有特征都被分入特征組中時停止；

⑨ 取出每個特征組的第1個特征放入特征集Scan；

⑩ 返回Scan.

1.2 MIFS-Boruta算法

MIFS算法可以通過對特征分組的方式去除冗余特征，但它同大多數過濾型特征算法類似，無法自動確定最佳特征.

Boruta[19]是一種全相關的封裝型特征選擇方法，它試圖找到攜帶可用于預測的信息的所有特征，而不是像大多數傳統封裝型算法一樣只找到在分類器上產生最小誤差的特征子集.無論特征與決策變量的相關性強弱與否，Boruta都會找到所有的相關特征，這使得它非常適合應用于確定最佳特征子集.

Boruta算法首先將數據集擴充，通過隨機打亂原數據集各特征的取值，生成與原數據集的特征數量相同的“影子”特征，由于這些“影子”特征是隨機生成的，所以Boruta算法認為它們是不重要的特征.之后分別在各個原始特征與“影子”特征上采用隨機森林進行分類，計算各特征的效果，將“影子”特征中分類效果最好的特征作為衡量原始特征是否重要的標準，從而去除不重要的特征.Boruta算法能找到候選特征中與類別相關的所有特征，從而直接確定特征數目，得到最優特征子集.

Boruta可以找到所有相關特征這一優點正好可以解決MIFS算法無法自動給出最佳子集的問題，因此我們考慮建立MIFS和Boruta的混合模型.在混合模型中，封裝型算法可以充分利用過濾方法獲得的結果，提高運行效率，并獲得產生較高分類性能的子集，同時，過濾型方法也可以利用封裝型方法來確定特征子集中的特征個數，這樣封裝和過濾方法的特性得到了很好的互補[14].因此本節提出一種基于MIFS和Boruta的混合模型，用以設計高效的特征選擇算法自動選出一組冗余較小且數量較小的特征，稱為MIFS-Boruta算法.

MIFS-Boruta算法的主要步驟歸納如下：

算法2. MIFS-Boruta特征選擇算法.

輸入：數據集D、候選特征子集個數k、迭代次數r；

輸出：特征子集S.

① 在數據集D上運行MIFS算法得到包含k個候選特征的特征集Scan；

② 從數據集D中取出特征集Scan對應的數據作為新的數據集Dsub；

③ 在數據集Dsub上運行Boruta算法，Boruta算法的迭代次數為參數r；

④ 返回特征子集S.

MIFS算法初始化時選擇的和類別互信息最大的特征將會包含在最優的特征子集中，因為該特征首先被放入第1個特征分組，之后根據分組標準Q向該特征組中添加特征使其內部的特征之間有較高的冗余度，同時使得特征組與類別的關聯度隨著特征數量的增加而減小，所以在此特征組中只需選擇一個與類別關聯度最大的特征作為該組的代表，這個特征就是算法初始化時選出的和類別互信息最大的特征，因此該特征被選為最優特征子集的候選特征；然后采用Boruta算法從候選特征中去除不重要的特征，而由于與類別互信息最大的特征的分類效果通常不會低于“影子”特征的分類效果，因此該特征不會被去除，包含在最優特征子集中.

1.3 時間復雜度分析

假設給定數據集的樣本數為n，特征維數為m，則MIFS算法中求類別和每個特征之間的互信息的時間復雜度為O(mn2)，對特征排序的時間復雜度為O(mlogm)，迭代地對特征分組的復雜度在最壞的情況下為O(mn)，所以MIFS算法的時間復雜度為O(mlogm+mn2).由于本文算法針對小樣本數據，其中n?m，因此可以將樣本數n視為常數，得到關于特征維數m的時間復雜度為O(mlogm).

而MIFS-Boruta特征選擇算法的運行時間是由MIFS算法和Boruta算法2部分運行時間組成，如果用k表示第1階段MIFS算法得到的候選特征子集中特征的個數，根據文獻[19]中的分析可知，Boruta算法的時間復雜度為O(kn)，同理，在小樣本問題中可看作關于維數的時間復雜度O(k).綜上，MIFS-Boruta特征選擇算法的時間復雜度為O(mlogm)+O(k)，又因為k?m，因此算法的時間復雜度實際上為O(mlogm).

2 實驗結果與分析

2.1 實驗數據

為了驗證算法在高維數據上的性能和有效性，以及該方法是否適用于實際問題，本文使用了11個公開可用的數據集，特征數目在1 024～19 993之間，平均特征個數為6 924，其中6個數據集的維度超過了5 000，3個數據集具有不少于10 000維的特征，這些數據集主要是圖像和生物微陣列數據，數據集的詳細信息如表1所示.為了便于處理，本文對連續型特征的數據使用等距離散化的方法進行了預處理.實驗在1臺i7-2600 3.40 GHz 4核處理器、4 GB內存的電腦上運行，開發環境為Matlab R2015a.

Table 1 Datasets Used in the Experiments表1 實驗數據集

2.2 特征選擇結果比較

為了驗證本文算法是否能夠獲得較好的特征選擇結果，將本文的MIFS-Boruta算法與CMIM[10]，ICAP(interaction capping)[20]，CIFE(conditional infomax feature extraction)[21]，mRMR[14]，L1MI(L1 least-squares mutual information)[22]5種經典的特征選擇算法進行比較，其中CMIM，ICAP，CIFE，L1MI方法是基于互信息度量的過濾型特征選擇算法，mRMR是基于相關性度量的過濾型特征選擇算法.這些方法在使用時一般都要指定降維之后的特征數，為公平起見，實驗中將這些方法分別與Boruta方法結合，預先設定了特征選擇算法在每個樣本集上的候選特征數k，本文根據經驗將其設為原始數據集特征維數的1.5%～5%之間.表2為在不同數據集上各特征選擇算法選出的特征個數.由于每種方法的第2階段都是Boruta，故本文表中的方法名稱都省略了-Boruta.

Table 2 Feature Selection Results Under the Combinations of Different Feature Selection Algorithms and Boruta Algorithm表2 不同特征選擇算法與Boruta算法組合時特征選擇結果

從表2可以看出所有的特征選擇算法所選出的特征個數遠小于原始特征維度m，最終選出的特征個數也明顯小于候選特征個數，CIFE算法在8個數據集上都得到了最少的特征個數，ICAP和CMIM算法分別在2個和1個數據集上取得了最少的特征個數，本文的MIFS方法所選出的特征個數在5個數據集上少于L1MI和mRMR，4個數據集上少于CIMI.

5種算法分別和Boruta算法組合的特征選擇方法得到的5個特征子集中，存在部分與MIFS-Boruta算法所選特征相同的特征，相同特征的個數如圖1所示:

Fig. 1 The comparison of the same features selected by MIFS-Boruta algorithm and other algorithms圖1 MIFS-Boruta算法與其他算法選出的相同特征比較

從圖1可以看出，MIFS選出的特征與5種算法選出的特征中基本上都存在相同的特征，其中與mRMR方法所選特征最為相近，相同特征的數量最多.盡管MIFS與這些方法選出的特征不盡相同，但后邊的實驗表明這對分類結果的影響不大.

2.3 運行時間比較

由于確定最佳特征子集都采用算法Boruta，因此只需要比較6種算法在確定候選特征子集過程中的運行時間，這些算法在11個數據集上的運行時間結果如表3所示.為了比較的公平性，本實驗將選出的特征數目k全部設定為150個.從表3中可以看到，所提出的MIFS算法在8個數據集上的運行時間均小于其他幾個基于互信息的特征選擇算法，只有在lung，pixraw10P，SMK_CAN_187這3個數據集上，MIFS算法稍慢于CMIM算法.因此在大多數數據集上，MIFS算法具有更高的運行效率.

Table 3 The Running Time of Different Feature Selection Algorithms表3 不同特征選擇算法運行時間 s

2.4 在特征子集的分類性能比較

為了驗證所提算法特征選擇的有效性，分別選取支持向量機(support vector machine， SVM)，決策樹，K-近鄰(K-nearest neighbor， KNN) 3個分類器作為分類算法.SVM是監督學習模型，本文使用常用的線性SVM模型；決策樹是通過學習算法構造的樹形結構的分類器，它是一種非線性分類器，本文使用經典的ID3算法；對于KNN分類器，選用1NN算法(單最近鄰算法)，它通過最鄰近的1個樣本的類別來決定待分樣本所屬的類別.在所有數據集上進行10次十折交叉驗證測試分類性能.

實驗使用3個指標來評價特征子集選擇算法的性能：1)最低分類錯誤率；2)平均最低分類錯誤率；3)Win/Tie/Lose記錄(該記錄表示在給定度量上，所提算法獲得比其他特征選擇算法更好、相等和更差的性能的數據集數目，可簡記為W/T/L).

不同特征選擇方法得到的特征子集在使用SVM、決策樹和KNN作為分類器時的最低分類錯誤率分別如表4～6所示，表中的Average Error表示各方法在所有數據集下的平均最低分類錯誤率，W/T/L行表示所提出方法在11個數據集上的分類錯誤率勝于、相同、弱于其所在列的方法的數據集數目.

Table 4 Classification Error Rate on SVM Classifier表4 SVM分類器上的分類錯誤率 %

Table 5 Classification Error Rate on Decision Tree Classifier表5 決策樹分類器上的分類錯誤率 %

Table 6 Classification Error Rate on CNN Classifier表6 KNN分類器上的分類錯誤率 %

從表4可以看出，在使用SVM作分類器時，MIFS算法在4個數據集上取得了最低的分類錯誤率，并且平均分類錯誤率最低；在W/T/L指標中，MIFS算法除了小幅落后于mRMR算法外，均優于其他方法.因此MIFS算法選出的特征子集在SVM分類器上的表現良好.

從表5可以看出，在使用決策樹作分類器時，MIFS算法在5個數據集上取得了最低的分類錯誤率，接近全部數據集的一半.對于平均分類錯誤率，MIFS算法取得了第2名，僅與第1名相差0.2個百分點；在W/T/L指標中，MIFS算法均優于其他方法.

從表6可以看出，MIFS算法在KNN分類器上分別在4個數據集中取得了最低的分類錯誤率，同時取得了最低的平均分類錯誤率，低于第2名1.09個百分點；從W/T/L指標來看，MIFS算法也都優于其他方法，因此MIFS算法選出的特征子集在KNN分類器上具有更好的分類性能.

綜上，在使用最簡單的支持向量機、決策樹、KNN三種分類器時，MIFS方法都取得了很好的分類結果.

3 結 論

本文提出了一種針對小樣本數據的特征選擇方法，該方法首先通過互信息對特征分組，選出組內與類別相關性最大的特征，大大降低了數據集的維度.同時為了解決無法自動給出最佳子集的問題，構造了過濾型與封裝型算法結合的2階段混合模型，即MIFS-Boruta算法，該算法不僅降低了數據集的維度，而且能夠自動確定最佳特征子集，實驗驗證了所提算法的有效性.該算法為解決小樣本問題提供了一種有效的方法.

然而，MIFS-Boruta算法的候選特征個數需要人為設定，如果設定的值過大，則會影響最終特征選擇的運行效率；如果設定的值過小，則會影響最終選出特征的性能.因此，如何自動確定合理的候選特征個數還需要進一步的研究.