特徵選擇

一般而言，特徵選擇可以看作一個搜索尋優問題。對大小為n 的特徵集合， 搜索空間由2n-1 種可能的狀態構成。Davies 等證明最小特徵子集的搜索是一個NP 問題，即除了窮舉式搜索，不能保證找到最優解。但實際應用中，當特徵數目較多的時候， 窮舉式搜索因為計算量太大而無法應用，因此人們致力於用啓發式搜索算法尋找次優解。一般特徵選擇算法必須確定以下4 個要素：1）搜索起點和方向；2）搜索策略；3）特徵評估函數；4）停止準則。 ^[2] 

搜索起點是算法開始搜索的狀態點，搜索方向是指評價的特徵子集產生的次序。搜索的起點和搜索方向是相關的，它們共同決定搜索策略。一般的，根據不同的搜索起點和方向，有以下4 種情況：

1）前向搜索搜索起點是空集S，依據某種評價標準，隨着搜索的進行，從未被包含在S 裏的特徵集中選擇最佳的特徵不斷加入S。

2）後向搜索搜索起點是全集S，依據某種評價標準不斷從S 中剔除最不重要的特徵，直到達到某種停止標準。

3）雙向搜索雙向搜索同時從前後兩個方向開始搜索。一般搜索到特徵子集空間的中部時，需要評價的子集將會急劇增加。當使用單向搜索時，如果搜索要通過子集空間的中部就會消耗掉大量的搜索時間，所以雙向搜索是比較常用的搜索方法。 ^[2] 

4）隨機搜索隨機搜索從任意的起點開始，對特徵的增加和刪除也有一定的隨機性。

假設原始特徵集中有n 個特徵（也稱輸入變量），那麼存在2ⁿ-1 個可能的非空特徵子集。搜索策略就是為了從包含

2ⁿ-1 個候選解的搜索空間中尋找最優特徵子集而採取的搜索方法。搜索策略可大致分為以下3 類：

1）窮舉式搜索它可以搜索到每個特徵子集。缺點是它會帶來巨大的計算開銷，尤其當特徵數較大時，計算時間很長。分支定界法（Branch and Bound， BB）通過剪枝處理縮短搜索時間。 ^[2] 

2）序列搜索它避免了簡單的窮舉式搜索，在搜索過程中依據某種次序不斷向當前特徵子集中添加或剔除特徵，從而獲得優化特徵子集。比較典型的序列搜索算法如：前向後向搜索、浮動搜索、雙向搜索、序列向前和序列向後算法等。序列搜索算法較容易實現，計算複雜度相對較小，但容易陷入局部最優。

3）隨機搜索由隨機產生的某個候選特徵子集開始，依照一定的啓發式信息和規則逐步逼近全局最優解。例如：遺傳算法（Genetic Algorithm， GA）、模擬退火算法（SimulatedAnnealing， SA）、粒子羣算法（Particl Swarm Optimization，PSO）和免疫算法（Immune Algorithm， IA）等。 ^[2] 

評價標準在特徵選擇過程中扮演着重要的角色，它是特徵選擇的依據。評價標準可以分為兩種：一種是用於單獨地衡量每個特徵的預測能力的評價標準；另一種是用於評價某個特徵子集整體預測性能的評價標準。

在Filte方法中，一般不依賴具體的學習算法來評價特徵子集，而是借鑑統計學、信息論等多門學科的思想，根據數據集的內在特性來評價每個特徵的預測能力，從而找出排序較優的若干個特徵組成特徵子集。通常，此類方法認為最優特徵子集是由若干個預測能力較強的特徵組成的。相反，在Wrapper 方法中，用後續的學習算法嵌入到特徵選擇過程中，通過測試特徵子集在此算法上的預測性能來決定它的優劣，而極少關注特徵子集中每個特徵的預測性能如何。因此，第二種評價標準並不要求最優特徵子集中的每個特徵都是優秀的。 ^[2] 

停止標準決定什麼時候停止搜索， 即結束算法的執行。它與評價準則或搜索算法的選擇以及具體應用需求均有關聯。常見的停止準則一般有：

1）執行時間即事先規定了算法執行的時間，當到達所制定的時間就強制終止算法運行，並輸出結果。

2）評價次數即制定算法需要運算多少次，通常用於規定隨機搜索的次數， 尤其當算法運行的結果不穩定的情況下，通過若干次的運行結果找出其中穩定的因素。

3） 設置閾值一般是給算法的目標值設置一個評價閾值，通過目標與該閾值的比較決定算法停止與否。不過，要設置一個合適的閾值並不容易，需要對算法的性能有十分清晰的瞭解。否則，設置閾值過高會使得算法陷入死循環，閾值過小則達不到預定的性能指標。 ^[2] 

迄今為止, 已有很多學者從不同角度對特徵選擇進行過定義: Kira 等人定義理想情況下特徵選擇是尋找必要的、足以識別目標的最小特徵子集; John 等人從提高預測精度的角度定義特徵選擇是一個能夠增加分類精度, 或者在不降低分類精度的條件下降低特徵維數的過程; Koller 等人從分佈的角度定義特徵選擇為: 在保證結果類分佈儘可能與原始數據類分佈相似的條件下, 選擇儘可能小的特徵子集;Dash 等人給出的定義是選擇儘量小的特徵子集, 並滿足不顯著降低分類精度和不顯著改變類分佈兩個條件. 上述各種定義的出發點不同, 各有側重點, 但是目標都是尋找一個能夠有效識別目標的最小特徵子集. 由文獻可知, 對特徵選擇的定義基本都是從分類正確率以及類分佈的角度考慮. Dash 等人給出了特徵選擇的基本框架, 如圖1 所示. ^[3] 

由於子集搜索是一個比較費時的步驟, Yu 等人基於相關和冗餘分析, 給出了另一種特徵選擇框架, 避免了子集搜索, 可以高效快速地尋找最優子集.框架如圖2 所示. ^[3] 

從特徵選擇的基本框架可以看出, 特徵選擇方法中有4 個基本步驟: 候選特徵子集的生成(搜索策略)、評價準則、停止準則和驗證方法. 目前對特徵選擇方法的研究主要集中於搜索策略和評價準則, 因而, 一般從搜索策略和評價準則兩個角度對特徵選擇方法進行分類. ^[3] 

產生過程是搜索特徵子集的過程，負責為評價函數提供特徵子集。

評價函數是評價一個特徵子集好壞程度的一個準則。

停止準則是與評價函數相關的，一般是一個閾值，當評價函數值達到這個閾值後就可停止搜索。

在驗證數據集上驗證選出來的特徵子集的有效性。

基本的搜索策略按照特徵子集的形成過程可分為以下3 種: 全局最優、隨機搜索和啓發式搜索. 一個具體的搜索算法會採用兩種或多種基本搜索策略,例如遺傳算法是一種隨機搜索算法, 同時也是一種啓發式搜索算法. 下面對3 種基本的搜索策略進行分析比較.

1、採用全局最優搜索策略的特徵選擇方法

迄今為止, 唯一得到最優結果的搜索方法是分支定界法. 這種算法能保證在事先確定優化特徵子集中特徵數目的情況下, 找到相對於所設計的可分性判據而言的最優子集. 它的搜索空間是O(2^N) (其中N 為特徵的維數). 存在的問題: 很難確定優化特徵子集的數目; 滿足單調性的可分性判據難以設計; 處理高維多類問題時, 算法的時間複雜度較高. 因此, 雖然全局最優搜索策略能得到最優解, 但因為諸多因素限制, 無法被廣泛應用. ^[3] 

2、採用隨機搜索策略的特徵選擇方法

在計算過程中把特徵選擇問題與模擬退火算法、禁忌搜索算法、遺傳算法等, 或者僅僅是一個隨機重採樣過程結合起來, 以概率推理和採樣過程作為算法的基礎, 基於對分類估計的有效性, 在算法運行中對每個特徵賦予一定的權重; 然後根據用户所定義的或自適應的閾值來對特徵重要性進行評價. 當特徵所對應的權重超出了這個閾值, 它便被選中作為重要的特徵來訓練分類器. Relief 系列算法即是一種典型的根據權重選擇特徵的隨機搜索方法, 它能有效地去掉無關特徵, 但不能去除冗餘, 而且只能用於兩類分類. 隨機方法可以細分為完全隨機方法和概率隨機方法兩種. 雖然搜索空間仍為O(2^N), 但是可以通過設置最大迭代次數限制搜索空間小於O(2^N). 例如遺傳算法, 由於採用了啓發式搜索策略, 它的搜索空間遠遠小於O(2^N).存在的問題: 具有較高的不確定性, 只有當總循環次數較大時, 才可能找到較好的結果. 在隨機搜索策略中, 可能需對一些參數進行設置, 參數選擇的合適與否對最終結果的好壞起着很大的作用. 因此, 參數選擇是一個關鍵步驟. ^[3] 

3、採用啓發式搜索策略的特徵選擇方法

這類特徵選擇方法主要有: 單獨最優特徵組合,序列前向選擇方法(SFS), 廣義序列前向選擇方法(GSFS), 序列後向選擇方法(SBS), 廣義序列後向選擇方法(GSBS), 增l去r 選擇方法, 廣義增l去r選擇方法, 浮動搜索方法. 這類方法易於實現且快速, 它的搜索空間是O(N²). 一般認為採用浮動廣義後向選擇方法(FGSBS) 是較為有利於實際應用的一種特徵選擇搜索策略, 它既考慮到特徵之間的統計相關性, 又用浮動方法保證算法運行的快速穩定性. 存在的問題是: 啓發式搜索策略雖然效率高, 但是它以犧牲全局最優為代價. ^[3] 

每種搜索策略都有各自的優缺點, 在實際應用過程中, 可以根據具體環境和準則函數來尋找一個最佳的平衡點. 例如, 如果特徵數較少, 可採用全局最優搜索策略; 若不要求全局最優, 但要求計算速度快, 則可採用啓發式策略; 若需要高性能的子集, 而不介意計算時間, 則可採用隨機搜索策略. ^[3] 

特徵選擇方法依據是否獨立於後續的學習算法, 可分為過濾式(Filter) 和封裝式(Wrapper)兩種.Filter 與後續學習算法無關, 一般直接利用所有訓練數據的統計性能評估特徵, 速度快, 但評估與後續學習算法的性能偏差較大. Wrapper 利用後續學習算法的訓練準確率評估特徵子集, 偏差小, 計算量大, 不適合大數據集. 下面分別對Filter 和Wrapper 方法進行分析. ^[3] 

1、過濾式(Filter) 評價策略的特徵選擇方法

Filter 特徵選擇方法一般使用評價準則來增強特徵與類的相關性, 削減特徵之間的相關性. 可將評價函數分成4 類: 距離度量、信息度量、依賴性度量以及一致性度量.

2、封裝式(Wrapper) 評價策略的特徵選擇方法

除了上述4 種準則, 分類錯誤率也是一種衡量所選特徵子集優劣的度量標準. Wrapper 模型將特徵選擇算法作為學習算法的一個組成部分, 並且直接使用分類性能作為特徵重要性程度的評價標準. 它的依據是選擇子集最終被用於構造分類模型. 因此, 若在構造分類模型時, 直接採用那些能取得較高分類性能的特徵即可, 從而獲得一個分類性能較高的分類模型. 該方法在速度上要比Filter 方法慢, 但是它所選擇的優化特徵子集的規模相對要小得多, 非常有利於關鍵特徵的辨識; 同時它的準確率比較高, 但泛化能力比較差, 時間複雜度較高. 目前此類方法是特徵選擇研究領域的熱點, 相關文獻也很多. 例如, Hsu 等人用決策樹來進行特徵選擇, 採用遺傳算法來尋找使得決策樹分類錯誤率最小的一組特徵子集. Chiang等人將Fisher 判別分析與遺傳算法相結合, 用來在化工故障過程中辨識關鍵變量, 取得了不錯的效果.Guyon 等人使用支持向量機的分類性能衡量特徵的重要性程度, 並最終構造一個分類性能較高的分類器. Krzysztof提出了一種基於相互關係的雙重策略的Wrapper 特徵選擇方法. 葉吉祥等人提出了一種快速的Wrapper 特徵選擇方法FFSR(fast featuresubset ranking), 以特徵子集作為評價單位, 以子集收斂能力作為評價標準. 戴平等人利用SVM線性核與多項式核函數的特性, 結合二進制PSO 方法, 提出了一種基於SVM的快速特徵選擇方法. ^[3] 

綜上所述, Filter 和Wrapper 特徵選擇方法各有優缺點. 將啓發式搜索策略和分類器性能評價準則相結合來評價所選的特徵, 相對於使用隨機搜索策略的方法, 節約了不少時間. Filter 和Wrapper 是兩種互補的模式, 兩者可以結合. 混合特徵選擇過程一般由兩個階段組成, 首先使用Filter 方法初步剔除大部分無關或噪聲特徵, 只保留少量特徵, 從而有效地減小後續搜索過程的規模. 第2 階段將剩餘的特徵連同樣本數據作為輸入參數傳遞給Wrapper 選擇方法,以進一步優化選擇重要的特徵. 例如,有 文獻]採用混合模型選擇特徵子集, 先使用互信息度量標準和bootstrap 技術獲取前k個重要的特徵, 然後再使用支持向量機構造分類器. ^[3] 

自從上世紀90 年代以來, 特徵選擇得到廣泛研究並應用於Web 文檔處理（文本分類、文本檢索、文本恢復等）、基因分析、藥物診斷等領域。現在的社會是信息爆炸的社會, 越來越多、形式多樣的數據出現在我們面前, 比如基因數據、數據流, 如何設計出更好的特徵選擇算法來滿足社會的需求, 是一個長期的任務, 特徵選擇算法的研究在未來的一段時間仍將是機器學習等領域的研究熱點問題之一。目前研究熱點及趨勢主要集中於以下方面:

1） 特徵與樣本選擇的組合研究。不同的樣本集合區域, 也許應該選擇不同的特徵選擇算法。很多數據中存在特徵天然分割的特性, 如在網頁半監督分類問題中, 描述網頁特徵集( 一般為詞彙集) 通常可以分割為如下獨立的兩個特徵子集: 出現在網頁文本內容中的詞彙集合和出現在網頁的超級鏈接中的詞彙集合, 那麼對於這兩個特徵子集, 我們能不能使用不同的特徵選擇方法來降低維數、取得更好的學習效果呢? ^[4] 

2）最近, 特徵及其與目標(分類、迴歸、聚類等)的相關性受到越來越多的重視, 可以稱此問題為全相關間題。如在基因表達式分析中,找出所有特徵中那些和目標變量相關的特徵, 這些特徵可能導致生物狀態為健康或有疾病, 目前常用的是Ranking方法, 但Ranking方法往往考慮的是特徵和標籤的相關性, 沒有考慮特徵間的關聯,如何將特徵之間的關聯性考慮進去呢? 這也是目前研究的重點和難點之一。 ^[4]