特徵選擇
![]() |
特徵選擇是全國科學技術名詞審定委員會審定、公布的科技類名詞。
關於漢字的起源[1],中國古代文獻上有種種說法,如「結繩」、「八卦」、「圖畫」、「書契」等,古書上還普遍記載有黃帝史官倉頡造字的傳說。現代學者認為,成系統的文字工具不可能完全由一個人創造出來,倉頡[2]如果確有其人,應該是文字整理者或頒布者。最早刻劃符號距今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) 設置閾值一般是給算法的目標值設置一個評價閾值,通過目標與該閾值的比較決定算法停止與否。不過,要設置一個合適的閾值並不容易,需要對算法的性能有十分清晰的了解。否則,設置閾值過高會使得算法陷入死循環,閾值過小則達不到預定的性能指標。
參考文獻
- ↑ 中國「漢字」從何而來?每個漢字,都是倉頡造出來的嗎?,搜狐,2022-10-01
- ↑ 造字的倉頡,為何叫「倉頡」?甲骨文揭開了顛覆性的一幕,搜狐,2022-09-12