李云

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

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

1 穩(wěn)定性分析

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

1.1 穩(wěn)定性因素

產(chǎn)生不穩(wěn)定特征選擇結(jié)果的主要因素有：

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

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

（3）當(dāng)特征集里含有大量的冗余特征時，由于冗余特征之間的關(guān)聯(lián)性較強，具有相似的（分類）性能，也會產(chǎn)生多個具有近似性能的特征子集，從而影響算法的穩(wěn)定性。

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

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

1.2 穩(wěn)定性度量

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

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

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

2 集成特征選擇

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

3 樣本加權(quán)

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

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

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

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

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

[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.