機(jī)器學(xué)習(xí)特征選擇常用算法

1. 綜述

(1) 什么是特征選擇

特征選擇 ( Feature Selection )也稱特征子集選擇( Feature Subset Selection , FSS ) ，或?qū)傩赃x擇( Attribute Selection ) ，是指從全部特征中選取一個(gè)特征子集，使構(gòu)造出來(lái)的模型更好。

(2) 為什么要做特征選擇

在機(jī)器學(xué)習(xí)的實(shí)際應(yīng)用中，特征數(shù)量往往較多，其中可能存在不相關(guān)的特征，特征之間也可能存在相互依賴，容易導(dǎo)致如下的后果：

特征個(gè)數(shù)越多，分析特征、訓(xùn)練模型所需的時(shí)間就越長(zhǎng)。

特征個(gè)數(shù)越多，容易引起“維度災(zāi)難”，模型也會(huì)越復(fù)雜，其推廣能力會(huì)下降。

特征選擇能剔除不相關(guān)(irrelevant)或亢余(redundant )的特征，從而達(dá)到減少特征個(gè)數(shù)，提高模型精確度，減少運(yùn)行時(shí)間的目的。另一方面，選取出真正相關(guān)的特征簡(jiǎn)化了模型，使研究人員易于理解數(shù)據(jù)產(chǎn)生的過(guò)程。

2. 特征選擇過(guò)程

2.1 特征選擇的一般過(guò)程

特征選擇的一般過(guò)程可用圖1表示。首先從特征全集中產(chǎn)生出一個(gè)特征子集，然后用評(píng)價(jià)函數(shù)對(duì)該特征子集進(jìn)行評(píng)價(jià)，評(píng)價(jià)的結(jié)果與停止準(zhǔn)則進(jìn)行比較，若評(píng)價(jià)結(jié)果比停止準(zhǔn)則好就停止，否則就繼續(xù)產(chǎn)生下一組特征子集，繼續(xù)進(jìn)行特征選擇。選出來(lái)的特征子集一般還要驗(yàn)證其有效性。

綜上所述，特征選擇過(guò)程一般包括產(chǎn)生過(guò)程，評(píng)價(jià)函數(shù)，停止準(zhǔn)則，驗(yàn)證過(guò)程，這4個(gè)部分。

(1) 產(chǎn)生過(guò)程( Generation Procedure )

產(chǎn)生過(guò)程是搜索特征子集的過(guò)程，負(fù)責(zé)為評(píng)價(jià)函數(shù)提供特征子集。搜索特征子集的過(guò)程有多種，將在2.2小節(jié)展開(kāi)介紹。

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

評(píng)價(jià)函數(shù)是評(píng)價(jià)一個(gè)特征子集好壞程度的一個(gè)準(zhǔn)則。評(píng)價(jià)函數(shù)將在2.3小節(jié)展開(kāi)介紹。

(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)的特征子集的有效性。

圖1. 特征選擇的過(guò)程 ( M. Dash and H. Liu 1997 )

2.2 產(chǎn)生過(guò)程

產(chǎn)生過(guò)程是搜索特征子空間的過(guò)程。搜索的算法分為完全搜索(Complete)，啟發(fā)式搜索(Heuristic)，隨機(jī)搜索(Random) 3大類(lèi)，如圖2所示。

圖2. 產(chǎn)生過(guò)程算法分類(lèi) ( M. Dash and H. Liu 1997 )

下面對(duì)常見(jiàn)的搜索算法進(jìn)行簡(jiǎn)單介紹。

2.2.1完全搜索

完全搜索分為窮舉搜索(Exhaustive)與非窮舉搜索(Non-Exhaustive)兩類(lèi)。

(1) 廣度優(yōu)先搜索( Breadth First Search )

算法描述：廣度優(yōu)先遍歷特征子空間。

算法評(píng)價(jià)：枚舉了所有的特征組合，屬于窮舉搜索，時(shí)間復(fù)雜度是O(2n)，實(shí)用性不高。

(2)分支限界搜索( Branch and Bound )

算法描述：在窮舉搜索的基礎(chǔ)上加入分支限界。例如：若斷定某些分支不可能搜索出比當(dāng)前找到的最優(yōu)解更優(yōu)的解，則可以剪掉這些分支。

(3) 定向搜索 (Beam Search )

算法描述：首先選擇N個(gè)得分最高的特征作為特征子集，將其加入一個(gè)限制最大長(zhǎng)度的優(yōu)先隊(duì)列，每次從隊(duì)列中取出得分最高的子集，然后窮舉向該子集加入1個(gè)特征后產(chǎn)生的所有特征集，將這些特征集加入隊(duì)列。

(4) 最優(yōu)優(yōu)先搜索 ( Best First Search )

算法描述：與定向搜索類(lèi)似，唯一的不同點(diǎn)是不限制優(yōu)先隊(duì)列的長(zhǎng)度。

2.2.2 啟發(fā)式搜索

(1)序列前向選擇( SFS , Sequential Forward Selection )

算法描述：特征子集X從空集開(kāi)始，每次選擇一個(gè)特征x加入特征子集X，使得特征函數(shù)J( X)最優(yōu)。簡(jiǎn)單說(shuō)就是，每次都選擇一個(gè)使得評(píng)價(jià)函數(shù)的取值達(dá)到最優(yōu)的特征加入，其實(shí)就是一種簡(jiǎn)單的貪心算法。

算法評(píng)價(jià)：缺點(diǎn)是只能加入特征而不能去除特征。例如：特征A完全依賴于特征B與C，可以認(rèn)為如果加入了特征B與C則A就是多余的。假設(shè)序列前向選擇算法首先將A加入特征集，然后又將B與C加入，那么特征子集中就包含了多余的特征A。

(2)序列后向選擇( SBS , Sequential Backward Selection )

算法描述：從特征全集O開(kāi)始，每次從特征集O中剔除一個(gè)特征x，使得剔除特征x后評(píng)價(jià)函數(shù)值達(dá)到最優(yōu)。

算法評(píng)價(jià)：序列后向選擇與序列前向選擇正好相反，它的缺點(diǎn)是特征只能去除不能加入。

另外，SFS與SBS都屬于貪心算法，容易陷入局部最優(yōu)值。

(3) 雙向搜索( BDS , Bidirectional Search )

算法描述：使用序列前向選擇(SFS)從空集開(kāi)始，同時(shí)使用序列后向選擇(SBS)從全集開(kāi)始搜索，當(dāng)兩者搜索到一個(gè)相同的特征子集C時(shí)停止搜索。

雙向搜索的出發(fā)點(diǎn)是 。如下圖所示，O點(diǎn)代表搜索起點(diǎn)，A點(diǎn)代表搜索目標(biāo)?；疑膱A代表單向搜索可能的搜索范圍，綠色的2個(gè)圓表示某次雙向搜索的搜索范圍，容易證明綠色的面積必定要比灰色的要小。

圖2. 雙向搜索

(4) 增L去R選擇算法 ( LRS , Plus-L Minus-R Selection )

該算法有兩種形式:

1> 算法從空集開(kāi)始，每輪先加入L個(gè)特征，然后從中去除R個(gè)特征，使得評(píng)價(jià)函數(shù)值最優(yōu)。( L > R )

2> 算法從全集開(kāi)始，每輪先去除R個(gè)特征，然后加入L個(gè)特征，使得評(píng)價(jià)函數(shù)值最優(yōu)。( L R )

算法評(píng)價(jià)：增L去R選擇算法結(jié)合了序列前向選擇與序列后向選擇思想， L與R的選擇是算法的關(guān)鍵。

(5) 序列浮動(dòng)選擇( Sequential Floating Selection )

算法描述：序列浮動(dòng)選擇由增L去R選擇算法發(fā)展而來(lái)，該算法與增L去R選擇算法的不同之處在于：序列浮動(dòng)選擇的L與R不是固定的，而是“浮動(dòng)”的，也就是會(huì)變化的。

序列浮動(dòng)選擇根據(jù)搜索方向的不同，有以下兩種變種。

1>序列浮動(dòng)前向選擇( SFFS , Sequential Floating Forward Selection )

算法描述：從空集開(kāi)始，每輪在未選擇的特征中選擇一個(gè)子集x，使加入子集x后評(píng)價(jià)函數(shù)達(dá)到最優(yōu)，然后在已選擇的特征中選擇子集z，使剔除子集z后評(píng)價(jià)函數(shù)達(dá)到最優(yōu)。

2>序列浮動(dòng)后向選擇( SFBS , Sequential Floating Backward Selection )

算法描述：與SFFS類(lèi)似，不同之處在于SFBS是從全集開(kāi)始，每輪先剔除特征，然后加入特征。

算法評(píng)價(jià)：序列浮動(dòng)選擇結(jié)合了序列前向選擇、序列后向選擇、增L去R選擇的特點(diǎn)，并彌補(bǔ)了它們的缺點(diǎn)。

(6) 決策樹(shù)( Decision Tree Method , DTM)

算法描述：在訓(xùn)練樣本集上運(yùn)行C4.5或其他決策樹(shù)生成算法，待決策樹(shù)充分生長(zhǎng)后，再在樹(shù)上運(yùn)行剪枝算法。則最終決策樹(shù)各分支處的特征就是選出來(lái)的特征子集了。決策樹(shù)方法一般使用信息增益作為評(píng)價(jià)函數(shù)。

2.2.3 隨機(jī)算法

(1) 隨機(jī)產(chǎn)生序列選擇算法(RGSS, Random Generation plus Sequential Selection)

算法描述：隨機(jī)產(chǎn)生一個(gè)特征子集，然后在該子集上執(zhí)行SFS與SBS算法。

算法評(píng)價(jià)：可作為SFS與SBS的補(bǔ)充，用于跳出局部最優(yōu)值。

(2) 模擬退火算法( SA, Simulated Annealing )

模擬退火算法可參考 大白話解析模擬退火算法 。

算法評(píng)價(jià)：模擬退火一定程度克服了序列搜索算法容易陷入局部最優(yōu)值的缺點(diǎn)，但是若最優(yōu)解的區(qū)域太小(如所謂的“高爾夫球洞”地形)，則模擬退火難以求解。

(3) 遺傳算法( GA, Genetic Algorithms )

遺傳算法可參考 遺傳算法入門(mén) 。

算法描述：首先隨機(jī)產(chǎn)生一批特征子集，并用評(píng)價(jià)函數(shù)給這些特征子集評(píng)分，然后通過(guò)交叉、突變等操作繁殖出下一代的特征子集，并且評(píng)分越高的特征子集被選中參加繁殖的概率越高。這樣經(jīng)過(guò)N代的繁殖和優(yōu)勝劣汰后，種群中就可能產(chǎn)生了評(píng)價(jià)函數(shù)值最高的特征子集。

隨機(jī)算法的共同缺點(diǎn)：依賴于隨機(jī)因素，有實(shí)驗(yàn)結(jié)果難以重現(xiàn)。

2.3 評(píng)價(jià)函數(shù)

評(píng)價(jià)函數(shù)的作用是評(píng)價(jià)產(chǎn)生過(guò)程所提供的特征子集的好壞。

評(píng)價(jià)函數(shù)根據(jù)其工作原理，主要分為篩選器(Filter)、封裝器( Wrapper )兩大類(lèi)。

篩選器通過(guò)分析特征子集內(nèi)部的特點(diǎn)來(lái)衡量其好壞。篩選器一般用作預(yù)處理，與分類(lèi)器的選擇無(wú)關(guān)。篩選器的原理如下圖3：

圖3. Filter原理(Ricardo Gutierrez-Osuna 2008 )

封裝器實(shí)質(zhì)上是一個(gè)分類(lèi)器，封裝器用選取的特征子集對(duì)樣本集進(jìn)行分類(lèi)，分類(lèi)的精度作為衡量特征子集好壞的標(biāo)準(zhǔn)。封裝器的原理如圖4所示。

圖4. Wrapper原理 (Ricardo Gutierrez-Osuna 2008 )

下面簡(jiǎn)單介紹常見(jiàn)的評(píng)價(jià)函數(shù)。

(1) 相關(guān)性( Correlation)

運(yùn)用相關(guān)性來(lái)度量特征子集的好壞是基于這樣一個(gè)假設(shè)：好的特征子集所包含的特征應(yīng)該是與分類(lèi)的相關(guān)度較高(相關(guān)度高)，而特征之間相關(guān)度較低的(亢余度低)。

可以使用線性相關(guān)系數(shù)(correlation coefficient) 來(lái)衡量向量之間線性相關(guān)度。

( 2) 距離 (Distance Metrics )

運(yùn)用距離度量進(jìn)行特征選擇是基于這樣的假設(shè)：好的特征子集應(yīng)該使得屬于同一類(lèi)的樣本距離盡可能小，屬于不同類(lèi)的樣本之間的距離盡可能遠(yuǎn)。

常用的距離度量(相似性度量)包括歐氏距離、標(biāo)準(zhǔn)化歐氏距離、馬氏距離等。

(3) 信息增益( Information Gain )

假設(shè)存在離散變量Y，Y中的取值包括{y1，y2，....，ym} ，yi出現(xiàn)的概率為Pi。則Y的信息熵定義為：

信息熵有如下特性：若集合Y的元素分布越“純”，則其信息熵越小;若Y分布越“紊亂”，則其信息熵越大。在極端的情況下：若Y只能取一個(gè)值，即P1=1，則H(Y)取最小值0;反之若各種取值出現(xiàn)的概率都相等，即都是1/m，則H(Y)取最大值log2m。

在附加條件另一個(gè)變量X，而且知道X=xi后，Y的條件信息熵(Conditional Entropy)表示為：

假設(shè)存在特征子集A和特征子集B，分類(lèi)變量為C，若IG( C|A ) > IG( C|B ) ，則認(rèn)為選用特征子集A的分類(lèi)結(jié)果比B好，因此傾向于選用特征子集A。

(4)一致性( Consistency )

若樣本1與樣本2屬于不同的分類(lèi)，但在特征A、 B上的取值完全一樣，那么特征子集{A，B}不應(yīng)該選作最終的特征集。

(5)分類(lèi)器錯(cuò)誤率 (Classifier error rate )

使用特定的分類(lèi)器，用給定的特征子集對(duì)樣本集進(jìn)行分類(lèi)，用分類(lèi)的精度來(lái)衡量特征子集的好壞。

以上5種度量方法中，相關(guān)性、距離、信息增益、一致性屬于篩選器，而分類(lèi)器錯(cuò)誤率屬于封裝器。

篩選器由于與具體的分類(lèi)算法無(wú)關(guān)，因此其在不同的分類(lèi)算法之間的推廣能力較強(qiáng)，而且計(jì)算量也較小。而封裝器由于在評(píng)價(jià)的過(guò)程中應(yīng)用了具體的分類(lèi)算法進(jìn)行分類(lèi)，因此其推廣到其他分類(lèi)算法的效果可能較差，而且計(jì)算量也較大。