特徵選擇檢視原始碼討論檢視歷史

來自 孔夫子舊書網 的圖片

特徵選擇是全國科學技術名詞審定委員會審定、公布的科技類名詞。

關於漢字的起源，中國古代文獻上有種種說法，如「結繩」、「八卦」、「圖畫」、「書契」等，古書上還普遍記載有黃帝史官倉頡造字的傳說。現代學者認為，成系統的文字工具不可能完全由一個人創造出來，倉頡如果確有其人，應該是文字整理者或頒布者。最早刻劃符號距今8000多年。

名詞解釋

特徵選擇( Feature Selection )也稱特徵子集選擇( Feature Subset Selection , FSS )，或屬性選擇( Attribute Selection )。是指從已有的M個特徵(Feature)中選擇N個特徵使得系統的特定指標最優化，是從原始特徵中選擇出一些最有效特徵以降低數據集維度的過程,是提高學習算法性能的一個重要手段,也是模式識別中關鍵的數據預處理步驟。對於一個學習算法來說,好的學習樣本是訓練模型的關鍵。

此外，需要區分特徵選擇與特徵提取。特徵提取 ( Feature extraction )是指利用已有的特徵計算出一個抽象程度更高的特徵集，也指計算得到某個特徵的算法。

特徵選擇過程一般包括產生過程，評價函數，停止準則，驗證過程，這4個部分。

四要素

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

搜索起點和方向

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

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

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

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

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

搜索策略

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

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

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

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

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

特徵評估函數

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

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

停止準則

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

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

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

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