穩定的特征選擇研究*

李云

（南京郵電大學 計算機學院，江蘇 南京 210003）

隨著信息技術和生物技術的快速發展，在現實生活及科學研究中產生大量的高維海量數據。為了從大規模數據中挖掘出有用的知識，特征選擇已成為高維數據分類或者回歸中的關鍵問題[1]，目前已被廣泛應用于文本分類、圖像檢索、基因分析和入侵檢測等。所謂特征選擇就是從一組特征中挑選出一些最有效的特征以達到降低特征空間維數或者發現自然模型真實變量的過程，其通常包括兩個關鍵問題：搜索策略和評價準則。參考文獻[2-4]對已有特征選擇方法以及特征選擇統一框架進行了全面的綜述。特征選擇算法根據訓練的數據集中樣本有無標記通常分為監督、非監督和半監督特征選擇算法。在評價過程中，監督的特征選擇方法通常通過評價特征與類別之間的關聯性或者特征的分類性能來獲取特征的相關性。非監督的特征選擇方法通常通過探究未標記數據分布特性來獲取特征的相關性。半監督特征選擇方法則同時利用標記的和未標記的樣本。此外，根據評價準則，特征選擇又可以分為過濾器、封裝器以及嵌入式三類基本模型[2]。過濾器模型是將特征選擇作為一個預處理過程，利用數據的內在特性對選取的特征子集進行評價，獨立于學習算法。封裝器模型則將后續學習算法的結果作為特征子集評價準則的一部分。嵌入式模型則試圖利用前兩種模型的優點，在不同的搜索階段利用不同的評價準則。一般而言，過濾器的時間復雜度比封裝器低，且結構相對簡單，因此廣泛用于對高維數據的處理。如果根據輸出結果來區分，特征選擇又可以分為兩種[3]：一種是輸出所有特征權重，并對其進行排序，如 Lmba[5]、SQP-FW[6]等；另一種是輸出選擇的特征子集，如 SVM-RFE[7]等。

1 穩定性分析

特征選擇的一個重要特性是發現自然模型的真實變量，在很多應用場景下，特征選擇所選取的特征或者變量應該是具有可解釋性的。如在文本分類中，本研究利用一些先驗知識很容易檢查所選擇的單詞對分類是否有意義。此外在基因數據處理中，所選擇的基因也可以解釋。但是，如果當收集的某種病例樣本發生變化時，特征選擇算法獲取的基因子集或者排序結果差別較大，那么專家就會對基因選擇結果產生疑慮，而且也給結果的驗證帶來不便，從而難以確切獲得解釋該疾病的相關基因組。因此在某些領域，特征選擇的穩定性也是至關重要的。特征選擇的穩定性是對所選擇的特征子集相似性度量。它主要研究當樣本或者算法自身的參數有變化時，特征選擇算法的魯棒性。也就是說，對于高維數據的分類或者回歸，其主要任務有兩個：一個是設計盡可能好的算法，以獲取對未知樣本較高的預測能力；另一個是除了進一步提高算法的性能，還要能深入理解特征與樣本輸出之間的關系[1]。對于這第二個任務來說，除了要提高特征選擇的分類性能外，還需要關注其穩定性，否則第二個任務將難以完成。不穩定的特征選擇結果將帶來很多歧義，難以獲取可以理解的真實特征（變量）。

1.1 穩定性因素

產生不穩定特征選擇結果的主要因素有：

（1）數據擾動。數據擾動包括兩個方面：①數據本身變化，包括數量變化和訓練樣本分布的不同；②添加噪聲特征。

（2）算法本身沒有穩定機制。已有的算法在設計特征選擇評價準則時，只是考慮了分類性能或者聚類性能，而沒有關注算法的穩定性。

（3）當特征集里含有大量的冗余特征時，由于冗余特征之間的關聯性較強，具有相似的（分類）性能，也會產生多個具有近似性能的特征子集，從而影響算法的穩定性。

（4）高維小樣本。由于這類數據的訓練樣本較少，而特征維數非常高，如基因數據等，雖然訓練樣本只有細微的變化，而特征選擇的結果將發生很大變化。

為了有效提高特征選擇算法的穩定性，目前主要有基于經典特征選擇算法的集成特征選擇[8]、基于樣本加權的算法[9]和特征組群的方法[10]。

1.2 穩定性度量

特征選擇的穩定性是對所選擇的特征子集相似性度量。它主要研究當樣本或者算法自身的參數有變化時，特征選擇算法的魯棒性。所有特征選擇結果的相似性越大，則認為特征選擇的穩定性越高。而整體的穩定性就是所有特征選擇結果的相似之和的平均值：

式中，如果以特征排序為例，其中ru、rv表示第u和第v個特征排序結果，其長度為特征的維數n；sim表示排序結果之間的相似性；d為特征排序結果的個數。采用Spearman排序關聯系數來計算特征排序結果之間的相似性：

式中，rlu表示第l個特征在ru中的排序值，一般假定按降序排序，則排在最頂端的特征其排序值為n，而后依次減1。

2 集成特征選擇

與集成學習相類似，集成特征選擇包括兩個必不可少的步驟：一是產生多個不同的基特征選擇器，二是將每個基特征選擇器的結果進行集成。而生成不同的特征選擇結果可以采用不同的方法，如采用不同的特征選擇方法、基于不同的訓練子集等。而結果的集成可以采用加權投票等，假設對于包含有m個特征排序結果的集合，則利用加權投票得到的集成特征選擇結果可以表示為：

3 樣本加權

已有理論分析結果表明，特征選擇的穩定性與特征選擇結果的偏差相關，而有效減少方差的方法是：可以根據樣本對特征相關性的影響賦予不同的權重，然后基于帶權的訓練樣本進行特征選擇。也就是對重要區域內的樣本賦予較高的權重，而不重要區域內的樣本賦予較小的權重。其中方法之一是根據樣本中不同特征相關性的局部輪廓（Local Profile）來獲取樣本的權重。而對于某個樣本 x，其第 j個特征的局部輪廓 x′j的定義如下：

式中，xM表示與x不同類的最近鄰樣本，而xH表示與x同類的最近鄰樣本。特征的局部輪廓是樣本的假設間隔在各個特征維上的分解。

將原始空間上的樣本映射到由各個特征的局部輪廓所構建的間隔矢量特征空間，則對特征相關性有著不同影響的樣本偏離對特征相關性具有類似影響的樣本比較遠；具有類似影響的樣本通常比較多，占大多數，而其他樣本比較少。為了提高特征選擇的穩定性，需要對那些偏離大多數的樣本賦予較小的權重，減少它們的影響。其權重計算公式如下：

式中，x′為樣本x在間隔矢量空間上的映射樣本。

本文對特征選擇研究的熱點——穩定的特征選擇（包括穩定性的定義、因素和度量等）進行了詳細的分析，并詳細介紹了集成特征選擇和樣本加權兩種提高特征選擇穩定性的方法，以供參考。

[1]FAN J Q，LV J C.A selective overview of variable selection in high dimensional feature space[J].Statistical Sinica，2010（10）：101-148.

[2] LIU H， YU L. Toward integrating feature selection algorithms for classification and clustering[J].IEEE Transaction on Knowledge and Data Engineering， 2005， 17（3）：1-12.

[3]ZHAO Z.Spectralfeature selection forminingultrahigh dimensional data[M].Arizona State University PhD Dissertation，2010.

[4]GUYON I，ELISSEEFF A.An introduction to variable and feature selection[J].Journal of Machine Learning Research，2003，3（3）：1157-1182.

[5]LI Y，LU B L.Feature selection based on loss margin of nearest neighbor classification [J]. Pattern Recognition，2009，42：1914-1921.

[6]TAKEUCHI I，SUGIYAMA M.Target neighbor consistent feature weighting for nearest neighbor classification[C].Conference on Advances in Neural Information Processing Systems（NIPS）， 2011：1-9.

[7]GUYON I， WESTON J， BARNHILT S， et al.Gene selection for cancerclassification using supportvectormachine s[J].Machine Learning， 2002，46：389-422.

[8]SAEYS Y， ABEL T， PEER Y V.Robust feature selection using ensemble feature selection techniques[C].Proceeding of the European Conference. on Machine Learning and Principles and Practice of Knowledge Discovery in Databases（ECML-PKDD）， Lecture Notes on Artificial Intelligence，2008，5212：313-325.

[9]YU L， HAN Y， BERENS M E.Stable gene selection from microarray data via sample weighting[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics， 2012，9 （1）：262-272.

[10]LOSCALZO S， YU L， DING C.Consensus group stable feature selection[C].Proceeding ACM SIGKDD Conference.on Knowledge Discovery and Data Mining （KDD）， Paris France， June 28-July 1.2009：567-575.