李云

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

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

1 穩(wěn)定性分析

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

1.1 穩(wěn)定性因素

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

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

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

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

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

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

1.2 穩(wěn)定性度量

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

式中，如果以特征排序?yàn)槔渲衦u、rv表示第u和第v個(gè)特征排序結(jié)果，其長(zhǎng)度為特征的維數(shù)n；sim表示排序結(jié)果之間的相似性；d為特征排序結(jié)果的個(gè)數(shù)。采用Spearman排序關(guān)聯(lián)系數(shù)來(lái)計(jì)算特征排序結(jié)果之間的相似性：

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

2 集成特征選擇

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

3 樣本加權(quán)

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

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

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

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

本文對(duì)特征選擇研究的熱點(diǎn)——穩(wěn)定的特征選擇（包括穩(wěn)定性的定義、因素和度量等）進(jìn)行了詳細(xì)的分析，并詳細(xì)介紹了集成特征選擇和樣本加權(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.