[科普中國(guó)]-特征選擇

四要素

一般而言，特征選擇可以看作一個(gè)搜索尋優(yōu)問(wèn)題。對(duì)大小為n 的特征集合， 搜索空間由2n-1 種可能的狀態(tài)構(gòu)成。Davies 等證明最小特征子集的搜索是一個(gè)NP 問(wèn)題，即除了窮舉式搜索，不能保證找到最優(yōu)解。但實(shí)際應(yīng)用中，當(dāng)特征數(shù)目較多的時(shí)候， 窮舉式搜索因?yàn)橛?jì)算量太大而無(wú)法應(yīng)用，因此人們致力于用啟發(fā)式搜索算法尋找次優(yōu)解。一般特征選擇算法必須確定以下4 個(gè)要素：1）搜索起點(diǎn)和方向；2）搜索策略；3）特征評(píng)估函數(shù)；4）停止準(zhǔn)則。2

搜索起點(diǎn)和方向搜索起點(diǎn)是算法開(kāi)始搜索的狀態(tài)點(diǎn)，搜索方向是指評(píng)價(jià)的特征子集產(chǎn)生的次序。搜索的起點(diǎn)和搜索方向是相關(guān)的，它們共同決定搜索策略。一般的，根據(jù)不同的搜索起點(diǎn)和方向，有以下4 種情況：

1）前向搜索搜索起點(diǎn)是空集S，依據(jù)某種評(píng)價(jià)標(biāo)準(zhǔn)，隨著搜索的進(jìn)行，從未被包含在S 里的特征集中選擇最佳的特征不斷加入S。

2）后向搜索搜索起點(diǎn)是全集S，依據(jù)某種評(píng)價(jià)標(biāo)準(zhǔn)不斷從S 中剔除最不重要的特征，直到達(dá)到某種停止標(biāo)準(zhǔn)。

3）雙向搜索雙向搜索同時(shí)從前后兩個(gè)方向開(kāi)始搜索。一般搜索到特征子集空間的中部時(shí)，需要評(píng)價(jià)的子集將會(huì)急劇增加。當(dāng)使用單向搜索時(shí)，如果搜索要通過(guò)子集空間的中部就會(huì)消耗掉大量的搜索時(shí)間，所以雙向搜索是比較常用的搜索方法。2

4）隨機(jī)搜索隨機(jī)搜索從任意的起點(diǎn)開(kāi)始，對(duì)特征的增加和刪除也有一定的隨機(jī)性。

搜索策略假設(shè)原始特征集中有n 個(gè)特征（也稱(chēng)輸入變量），那么存在2n-1 個(gè)可能的非空特征子集。搜索策略就是為了從包含

2n-1 個(gè)候選解的搜索空間中尋找最優(yōu)特征子集而采取的搜索方法。搜索策略可大致分為以下3 類(lèi)：

1）窮舉式搜索它可以搜索到每個(gè)特征子集。缺點(diǎn)是它會(huì)帶來(lái)巨大的計(jì)算開(kāi)銷(xiāo)，尤其當(dāng)特征數(shù)較大時(shí)，計(jì)算時(shí)間很長(zhǎng)。分支定界法（Branch and Bound， BB）通過(guò)剪枝處理縮短搜索時(shí)間。2

2）序列搜索它避免了簡(jiǎn)單的窮舉式搜索，在搜索過(guò)程中依據(jù)某種次序不斷向當(dāng)前特征子集中添加或剔除特征，從而獲得優(yōu)化特征子集。比較典型的序列搜索算法如：前向后向搜索、浮動(dòng)搜索、雙向搜索、序列向前和序列向后算法等。序列搜索算法較容易實(shí)現(xiàn)，計(jì)算復(fù)雜度相對(duì)較小，但容易陷入局部最優(yōu)。

3）隨機(jī)搜索由隨機(jī)產(chǎn)生的某個(gè)候選特征子集開(kāi)始，依照一定的啟發(fā)式信息和規(guī)則逐步逼近全局最優(yōu)解。例如：遺傳算法（Genetic Algorithm， GA）、模擬退火算法（SimulatedAnnealing， SA）、粒子群算法（Particl Swarm Optimization，PSO）和免疫算法（Immune Algorithm， IA）等。2

特征評(píng)估函數(shù)評(píng)價(jià)標(biāo)準(zhǔn)在特征選擇過(guò)程中扮演著重要的角色，它是特征選擇的依據(jù)。評(píng)價(jià)標(biāo)準(zhǔn)可以分為兩種：一種是用于單獨(dú)地衡量每個(gè)特征的預(yù)測(cè)能力的評(píng)價(jià)標(biāo)準(zhǔn)；另一種是用于評(píng)價(jià)某個(gè)特征子集整體預(yù)測(cè)性能的評(píng)價(jià)標(biāo)準(zhǔn)。

在Filte方法中，一般不依賴(lài)具體的學(xué)習(xí)算法來(lái)評(píng)價(jià)特征子集，而是借鑒統(tǒng)計(jì)學(xué)、信息論等多門(mén)學(xué)科的思想，根據(jù)數(shù)據(jù)集的內(nèi)在特性來(lái)評(píng)價(jià)每個(gè)特征的預(yù)測(cè)能力，從而找出排序較優(yōu)的若干個(gè)特征組成特征子集。通常，此類(lèi)方法認(rèn)為最優(yōu)特征子集是由若干個(gè)預(yù)測(cè)能力較強(qiáng)的特征組成的。相反，在Wrapper 方法中，用后續(xù)的學(xué)習(xí)算法嵌入到特征選擇過(guò)程中，通過(guò)測(cè)試特征子集在此算法上的預(yù)測(cè)性能來(lái)決定它的優(yōu)劣，而極少關(guān)注特征子集中每個(gè)特征的預(yù)測(cè)性能如何。因此，第二種評(píng)價(jià)標(biāo)準(zhǔn)并不要求最優(yōu)特征子集中的每個(gè)特征都是優(yōu)秀的。2

停止準(zhǔn)則停止標(biāo)準(zhǔn)決定什么時(shí)候停止搜索， 即結(jié)束算法的執(zhí)行。它與評(píng)價(jià)準(zhǔn)則或搜索算法的選擇以及具體應(yīng)用需求均有關(guān)聯(lián)。常見(jiàn)的停止準(zhǔn)則一般有：

1）執(zhí)行時(shí)間即事先規(guī)定了算法執(zhí)行的時(shí)間，當(dāng)?shù)竭_(dá)所制定的時(shí)間就強(qiáng)制終止算法運(yùn)行，并輸出結(jié)果。

2）評(píng)價(jià)次數(shù)即制定算法需要運(yùn)算多少次，通常用于規(guī)定隨機(jī)搜索的次數(shù)， 尤其當(dāng)算法運(yùn)行的結(jié)果不穩(wěn)定的情況下，通過(guò)若干次的運(yùn)行結(jié)果找出其中穩(wěn)定的因素。

3） 設(shè)置閾值一般是給算法的目標(biāo)值設(shè)置一個(gè)評(píng)價(jià)閾值，通過(guò)目標(biāo)與該閾值的比較決定算法停止與否。不過(guò)，要設(shè)置一個(gè)合適的閾值并不容易，需要對(duì)算法的性能有十分清晰的了解。否則，設(shè)置閾值過(guò)高會(huì)使得算法陷入死循環(huán)，閾值過(guò)小則達(dá)不到預(yù)定的性能指標(biāo)。2

基本框架迄今為止, 已有很多學(xué)者從不同角度對(duì)特征選擇進(jìn)行過(guò)定義: Kira 等人定義理想情況下特征選擇是尋找必要的、足以識(shí)別目標(biāo)的最小特征子集; John 等人從提高預(yù)測(cè)精度的角度定義特征選擇是一個(gè)能夠增加分類(lèi)精度, 或者在不降低分類(lèi)精度的條件下降低特征維數(shù)的過(guò)程; Koller 等人從分布的角度定義特征選擇為: 在保證結(jié)果類(lèi)分布盡可能與原始數(shù)據(jù)類(lèi)分布相似的條件下, 選擇盡可能小的特征子集;Dash 等人給出的定義是選擇盡量小的特征子集, 并滿(mǎn)足不顯著降低分類(lèi)精度和不顯著改變類(lèi)分布兩個(gè)條件. 上述各種定義的出發(fā)點(diǎn)不同, 各有側(cè)重點(diǎn), 但是目標(biāo)都是尋找一個(gè)能夠有效識(shí)別目標(biāo)的最小特征子集. 由文獻(xiàn)可知, 對(duì)特征選擇的定義基本都是從分類(lèi)正確率以及類(lèi)分布的角度考慮. Dash 等人給出了特征選擇的基本框架, 如圖1 所示.3

由于子集搜索是一個(gè)比較費(fèi)時(shí)的步驟, Yu 等人基于相關(guān)和冗余分析, 給出了另一種特征選擇框架, 避免了子集搜索, 可以高效快速地尋找最優(yōu)子集.框架如圖2 所示.3

從特征選擇的基本框架可以看出, 特征選擇方法中有4 個(gè)基本步驟: 候選特征子集的生成(搜索策略)、評(píng)價(jià)準(zhǔn)則、停止準(zhǔn)則和驗(yàn)證方法. 目前對(duì)特征選擇方法的研究主要集中于搜索策略和評(píng)價(jià)準(zhǔn)則, 因而, 一般從搜索策略和評(píng)價(jià)準(zhǔn)則兩個(gè)角度對(duì)特征選擇方法進(jìn)行分類(lèi).3

特征選擇的一般過(guò)程**(1)產(chǎn)生過(guò)程( Generation Procedure )**

產(chǎn)生過(guò)程是搜索特征子集的過(guò)程，負(fù)責(zé)為評(píng)價(jià)函數(shù)提供特征子集。

(2)評(píng)價(jià)函數(shù)( Evaluation Function )

評(píng)價(jià)函數(shù)是評(píng)價(jià)一個(gè)特征子集好壞程度的一個(gè)準(zhǔn)則。

(3)停止準(zhǔn)則( Stopping Criterion )

停止準(zhǔn)則是與評(píng)價(jià)函數(shù)相關(guān)的，一般是一個(gè)閾值，當(dāng)評(píng)價(jià)函數(shù)值達(dá)到這個(gè)閾值后就可停止搜索。

(4)驗(yàn)證過(guò)程( Validation Procedure )

在驗(yàn)證數(shù)據(jù)集上驗(yàn)證選出來(lái)的特征子集的有效性。

基于搜索策略的方法分類(lèi)基本的搜索策略按照特征子集的形成過(guò)程可分為以下3 種: 全局最優(yōu)、隨機(jī)搜索和啟發(fā)式搜索. 一個(gè)具體的搜索算法會(huì)采用兩種或多種基本搜索策略,例如遺傳算法是一種隨機(jī)搜索算法, 同時(shí)也是一種啟發(fā)式搜索算法. 下面對(duì)3 種基本的搜索策略進(jìn)行分析比較.

1、采用全局最優(yōu)搜索策略的特征選擇方法

迄今為止, 唯一得到最優(yōu)結(jié)果的搜索方法是分支定界法. 這種算法能保證在事先確定優(yōu)化特征子集中特征數(shù)目的情況下, 找到相對(duì)于所設(shè)計(jì)的可分性判據(jù)而言的最優(yōu)子集. 它的搜索空間是O(2N) (其中N 為特征的維數(shù)). 存在的問(wèn)題: 很難確定優(yōu)化特征子集的數(shù)目; 滿(mǎn)足單調(diào)性的可分性判據(jù)難以設(shè)計(jì); 處理高維多類(lèi)問(wèn)題時(shí), 算法的時(shí)間復(fù)雜度較高. 因此, 雖然全局最優(yōu)搜索策略能得到最優(yōu)解, 但因?yàn)橹T多因素限制, 無(wú)法被廣泛應(yīng)用.3

2、采用隨機(jī)搜索策略的特征選擇方法

在計(jì)算過(guò)程中把特征選擇問(wèn)題與模擬退火算法、禁忌搜索算法、遺傳算法等, 或者僅僅是一個(gè)隨機(jī)重采樣過(guò)程結(jié)合起來(lái), 以概率推理和采樣過(guò)程作為算法的基礎(chǔ), 基于對(duì)分類(lèi)估計(jì)的有效性, 在算法運(yùn)行中對(duì)每個(gè)特征賦予一定的權(quán)重; 然后根據(jù)用戶(hù)所定義的或自適應(yīng)的閾值來(lái)對(duì)特征重要性進(jìn)行評(píng)價(jià). 當(dāng)特征所對(duì)應(yīng)的權(quán)重超出了這個(gè)閾值, 它便被選中作為重要的特征來(lái)訓(xùn)練分類(lèi)器. Relief 系列算法即是一種典型的根據(jù)權(quán)重選擇特征的隨機(jī)搜索方法, 它能有效地去掉無(wú)關(guān)特征, 但不能去除冗余, 而且只能用于兩類(lèi)分類(lèi). 隨機(jī)方法可以細(xì)分為完全隨機(jī)方法和概率隨機(jī)方法兩種. 雖然搜索空間仍為O(2N), 但是可以通過(guò)設(shè)置最大迭代次數(shù)限制搜索空間小于O(2N). 例如遺傳算法, 由于采用了啟發(fā)式搜索策略, 它的搜索空間遠(yuǎn)遠(yuǎn)小于O(2N).存在的問(wèn)題: 具有較高的不確定性, 只有當(dāng)總循環(huán)次數(shù)較大時(shí), 才可能找到較好的結(jié)果. 在隨機(jī)搜索策略中, 可能需對(duì)一些參數(shù)進(jìn)行設(shè)置, 參數(shù)選擇的合適與否對(duì)最終結(jié)果的好壞起著很大的作用. 因此, 參數(shù)選擇是一個(gè)關(guān)鍵步驟.3

3、采用啟發(fā)式搜索策略的特征選擇方法

這類(lèi)特征選擇方法主要有: 單獨(dú)最優(yōu)特征組合,序列前向選擇方法(SFS), 廣義序列前向選擇方法(GSFS), 序列后向選擇方法(SBS), 廣義序列后向選擇方法(GSBS), 增l去r 選擇方法, 廣義增l去r選擇方法, 浮動(dòng)搜索方法. 這類(lèi)方法易于實(shí)現(xiàn)且快速, 它的搜索空間是O(N2). 一般認(rèn)為采用浮動(dòng)廣義后向選擇方法(FGSBS) 是較為有利于實(shí)際應(yīng)用的一種特征選擇搜索策略, 它既考慮到特征之間的統(tǒng)計(jì)相關(guān)性, 又用浮動(dòng)方法保證算法運(yùn)行的快速穩(wěn)定性. 存在的問(wèn)題是: 啟發(fā)式搜索策略雖然效率高, 但是它以犧牲全局最優(yōu)為代價(jià).3

每種搜索策略都有各自的優(yōu)缺點(diǎn), 在實(shí)際應(yīng)用過(guò)程中, 可以根據(jù)具體環(huán)境和準(zhǔn)則函數(shù)來(lái)尋找一個(gè)最佳的平衡點(diǎn). 例如, 如果特征數(shù)較少, 可采用全局最優(yōu)搜索策略; 若不要求全局最優(yōu), 但要求計(jì)算速度快, 則可采用啟發(fā)式策略; 若需要高性能的子集, 而不介意計(jì)算時(shí)間, 則可采用隨機(jī)搜索策略.3

基于評(píng)價(jià)準(zhǔn)則劃分特征選擇方法特征選擇方法依據(jù)是否獨(dú)立于后續(xù)的學(xué)習(xí)算法, 可分為過(guò)濾式(Filter) 和封裝式(Wrapper)兩種.Filter 與后續(xù)學(xué)習(xí)算法無(wú)關(guān), 一般直接利用所有訓(xùn)練數(shù)據(jù)的統(tǒng)計(jì)性能評(píng)估特征, 速度快, 但評(píng)估與后續(xù)學(xué)習(xí)算法的性能偏差較大. Wrapper 利用后續(xù)學(xué)習(xí)算法的訓(xùn)練準(zhǔn)確率評(píng)估特征子集, 偏差小, 計(jì)算量大, 不適合大數(shù)據(jù)集. 下面分別對(duì)Filter 和Wrapper 方法進(jìn)行分析.3

1、過(guò)濾式(Filter) 評(píng)價(jià)策略的特征選擇方法

Filter 特征選擇方法一般使用評(píng)價(jià)準(zhǔn)則來(lái)增強(qiáng)特征與類(lèi)的相關(guān)性, 削減特征之間的相關(guān)性. 可將評(píng)價(jià)函數(shù)分成4 類(lèi): 距離度量、信息度量、依賴(lài)性度量以及一致性度量.

2、封裝式(Wrapper) 評(píng)價(jià)策略的特征選擇方法

除了上述4 種準(zhǔn)則, 分類(lèi)錯(cuò)誤率也是一種衡量所選特征子集優(yōu)劣的度量標(biāo)準(zhǔn). Wrapper 模型將特征選擇算法作為學(xué)習(xí)算法的一個(gè)組成部分, 并且直接使用分類(lèi)性能作為特征重要性程度的評(píng)價(jià)標(biāo)準(zhǔn). 它的依據(jù)是選擇子集最終被用于構(gòu)造分類(lèi)模型. 因此, 若在構(gòu)造分類(lèi)模型時(shí), 直接采用那些能取得較高分類(lèi)性能的特征即可, 從而獲得一個(gè)分類(lèi)性能較高的分類(lèi)模型. 該方法在速度上要比Filter 方法慢, 但是它所選擇的優(yōu)化特征子集的規(guī)模相對(duì)要小得多, 非常有利于關(guān)鍵特征的辨識(shí); 同時(shí)它的準(zhǔn)確率比較高, 但泛化能力比較差, 時(shí)間復(fù)雜度較高. 目前此類(lèi)方法是特征選擇研究領(lǐng)域的熱點(diǎn), 相關(guān)文獻(xiàn)也很多. 例如, Hsu 等人用決策樹(shù)來(lái)進(jìn)行特征選擇, 采用遺傳算法來(lái)尋找使得決策樹(shù)分類(lèi)錯(cuò)誤率最小的一組特征子集. Chiang等人將Fisher 判別分析與遺傳算法相結(jié)合, 用來(lái)在化工故障過(guò)程中辨識(shí)關(guān)鍵變量, 取得了不錯(cuò)的效果.Guyon 等人使用支持向量機(jī)的分類(lèi)性能衡量特征的重要性程度, 并最終構(gòu)造一個(gè)分類(lèi)性能較高的分類(lèi)器. Krzysztof提出了一種基于相互關(guān)系的雙重策略的Wrapper 特征選擇方法. 葉吉祥等人提出了一種快速的Wrapper 特征選擇方法FFSR(fast featuresubset ranking), 以特征子集作為評(píng)價(jià)單位, 以子集收斂能力作為評(píng)價(jià)標(biāo)準(zhǔn). 戴平等人利用SVM線性核與多項(xiàng)式核函數(shù)的特性, 結(jié)合二進(jìn)制PSO 方法, 提出了一種基于SVM的快速特征選擇方法.3

綜上所述, Filter 和Wrapper 特征選擇方法各有優(yōu)缺點(diǎn). 將啟發(fā)式搜索策略和分類(lèi)器性能評(píng)價(jià)準(zhǔn)則相結(jié)合來(lái)評(píng)價(jià)所選的特征, 相對(duì)于使用隨機(jī)搜索策略的方法, 節(jié)約了不少時(shí)間. Filter 和Wrapper 是兩種互補(bǔ)的模式, 兩者可以結(jié)合. 混合特征選擇過(guò)程一般由兩個(gè)階段組成, 首先使用Filter 方法初步剔除大部分無(wú)關(guān)或噪聲特征, 只保留少量特征, 從而有效地減小后續(xù)搜索過(guò)程的規(guī)模. 第2 階段將剩余的特征連同樣本數(shù)據(jù)作為輸入?yún)?shù)傳遞給Wrapper 選擇方法,以進(jìn)一步優(yōu)化選擇重要的特征. 例如,有 文獻(xiàn)]采用混合模型選擇特征子集, 先使用互信息度量標(biāo)準(zhǔn)和bootstrap 技術(shù)獲取前k個(gè)重要的特征, 然后再使用支持向量機(jī)構(gòu)造分類(lèi)器.3

研究進(jìn)展及展望自從上世紀(jì)90 年代以來(lái), 特征選擇得到廣泛研究并應(yīng)用于Web 文檔處理（文本分類(lèi)、文本檢索、文本恢復(fù)等）、基因分析、藥物診斷等領(lǐng)域?，F(xiàn)在的社會(huì)是信息爆炸的社會(huì), 越來(lái)越多、形式多樣的數(shù)據(jù)出現(xiàn)在我們面前, 比如基因數(shù)據(jù)、數(shù)據(jù)流, 如何設(shè)計(jì)出更好的特征選擇算法來(lái)滿(mǎn)足社會(huì)的需求, 是一個(gè)長(zhǎng)期的任務(wù), 特征選擇算法的研究在未來(lái)的一段時(shí)間仍將是機(jī)器學(xué)習(xí)等領(lǐng)域的研究熱點(diǎn)問(wèn)題之一。目前研究熱點(diǎn)及趨勢(shì)主要集中于以下方面:

1） 特征與樣本選擇的組合研究。不同的樣本集合區(qū)域, 也許應(yīng)該選擇不同的特征選擇算法。很多數(shù)據(jù)中存在特征天然分割的特性, 如在網(wǎng)頁(yè)半監(jiān)督分類(lèi)問(wèn)題中, 描述網(wǎng)頁(yè)特征集( 一般為詞匯集) 通常可以分割為如下獨(dú)立的兩個(gè)特征子集: 出現(xiàn)在網(wǎng)頁(yè)文本內(nèi)容中的詞匯集合和出現(xiàn)在網(wǎng)頁(yè)的超級(jí)鏈接中的詞匯集合, 那么對(duì)于這兩個(gè)特征子集, 我們能不能使用不同的特征選擇方法來(lái)降低維數(shù)、取得更好的學(xué)習(xí)效果呢?4

2）最近, 特征及其與目標(biāo)(分類(lèi)、回歸、聚類(lèi)等)的相關(guān)性受到越來(lái)越多的重視, 可以稱(chēng)此問(wèn)題為全相關(guān)間題。如在基因表達(dá)式分析中,找出所有特征中那些和目標(biāo)變量相關(guān)的特征, 這些特征可能導(dǎo)致生物狀態(tài)為健康或有疾病, 目前常用的是Ranking方法, 但Ranking方法往往考慮的是特征和標(biāo)簽的相關(guān)性, 沒(méi)有考慮特征間的關(guān)聯(lián),如何將特征之間的關(guān)聯(lián)性考慮進(jìn)去呢? 這也是目前研究的重點(diǎn)和難點(diǎn)之一。4