我們常常使用交叉驗證來檢查模型的分數是否有達標 (沒有發生低度配適)，或是檢查模型是否有過度配適。而影響模型是否有低度配適或過度配適的其中一個因子，在於我們選擇的特徵。有些時候特徵選不夠多，或是特徵不夠具有代表性，可能就會造成模型的低度配適；反之，選太多特徵可能就會出現模型的過度配適。因此，選擇特徵可謂是機器學習世界裡面非常重要的一件事情呀！
要如何解決特徵選擇的問題呢？有些人會用統計的方式來評量某個特徵是否有用，也有些人會根據一些背景知識來推論哪一些特徵可能比較有用。這些方法固然很重要，但是對於初學者來說，可能不是這麼好掌握。或者是說，如果我們手上已經有一大堆的特徵，這時候需要有一些比較系統化的方式 (小編解釋：其實就是執行某一個演算法)，是不是對特徵選擇更有幫助呢？
是的！今天我們就來討論幾個選擇特徵的演算法，希望讀者看完之後，可以使用以下的演算法來選出最合適的特徵！
一、 Full Search
如果要找到最佳的特徵組合，其做法就是找尋所有可能的特徵組合。假設我們有10個特徵，每個特徵都有「選」或「不選」，如此一來就有 1023 (小編提醒：要扣掉所有特徵都不選的 case) 種可能的特徵組合。
這個方法在學理上的運算複雜度：假設有 N 個特徵，需要訓練的模型個數為 2 的 N 次方。可想而知這種方法在很多特徵的時候，根本不可能做得出來。因此，才有接下來要介紹的其他方法。
二、 Greedy Forward Selection
這個方法的想法是：每次我們都只挑眼前看起來最好的特徵。一樣假設有 10 個特徵，我們對每一個特徵，都訓練一個模型並使用交叉驗證計算出分數，最後挑出分數最高的那個特徵。接著，從剩下的 9 個特徵，一樣對每一個特徵加上已經挑出的特徵，都訓練一個模型 (小編提醒：此時的模型有使用兩個特徵喔！) 並使用交叉驗證計算出分數，最後挑出分數最高的那個特徵，如此不斷地挑出分數最好的特徵。
這個方法在學理上的運算複雜度：假設有 N 個特徵，需要訓練的模型個數為 N 平方。雖然比第一個方法快很多，但有時候 N 大一點，搜索過程可能還是會耗掉不少的時間。
以下提供演算法的 Pseudo Code：
三、 Stepwise Forward Selection
Stepwise Forward Selection這個方法(Callier, 2018)的操作模式跟上述 Greedy Forward Selection 有一點點像：一樣假設有 10 個特徵，我們對每一個特徵也是訓練一個模型，並透過交叉驗證計算出分數，接著就將特徵做排序，從最好的特徵排到最差的特徵。在這個演算法裡，分數最高的特徵直接就選入集合。
接著，我們使用集合內的特徵跟第二好的特徵訓練一個模型，用交叉驗證計算出分數，如果分數增加量高於我們預先設定好的閾值，就把第二好的特徵加入集合；反之，就丟棄。
接著，我們使用集合內的特徵跟第三好的特徵訓練一個模型，用交叉驗證計算出分數，如果分數增加量高於閾值，就把第三好的特徵加入集合；反之，就丟棄。
如此持續操作直到看過所有特徵為止。這個方法在學理上的運算複雜度：假設有 N 個特徵，需要訓練的模型個數為 2N。讀者有沒有發現這個方法大大地降低特徵選取所需的時間。
以下提供演算法的Pseudo Code：
四、 Simplified Greedy Forward Selection
讀者可能會問：有沒有更快的方法。當然是有的，做法為：根據自己的經驗將特徵排序，或是隨機打亂特徵的順序。先將排序第一的特徵加入集合。
接著，使用集合的特徵以及排序第二的特徵訓練一個模型用交叉驗證計算出分數，如果分數增加量高於我們預先設定好的閾值，就把第二好的特徵加入集合；反之，就丟棄。
接著，使用集合的特徵以及排序第三的特徵訓練一個模型用交叉驗證計算出分數，如果分數增加量高於我們預先設定好的閾值，就把第三好的特徵加入集合；反之，就丟棄。
如此持續操作直到看過所有特徵為止。這個方法在學理上的運算複雜度：假設有 N 個特徵，需要訓練的模型個數為 N。可以發現運算複雜度已經跟特徵個數一樣多了，想必很難再找到更快的演算法了吧！如果還有更快的演算法，那不就…根本沒有看過所有特徵了嗎…
以下提供演算法的Pseudo Code：
重點整理：
1、Full Search 的方法，運算複雜度為 2 的 N 次方。
2、Greedy Forward Selection 的方法，運算複雜度為 N 平方。
3、Stepwise Forward Selection 的方法，運算複雜度為 2N。
4、Simplified Greedy Forward Selection 的方法，運算複雜度為 N。
參考資料
1、Kadowaki, D., Sakata R., Hosaka, K., and Hiramatsu, Y. (2021). Kaggle競賽攻頂秘笈 — 揭開 Grandmaster 的特徵工程心法，掌握制勝的關鍵技術. 1st ed. Translated by 李彥婷. Taipei: Flag Technology Co. Ltd.
2、Callier P. (2018). Comparing Two Forward Feature Selection Algorithm. [online] Medium. Available at: https://medium.com/square-corner-blog/comparing-two-forward-feature-selection-algorithms-c52f42868f55 [Accessed 29 Jan. 2021].
關於作者
Chia-Hao Li received the M.S. degree in computer science from Durham University, United Kingdom. He engages in computer algorithm, machine learning, and hardware/software codesign. He was former senior engineer in Mediatek, Taiwan. His currently research topic is the application of machine learning techniques for fault detection in the high-performance computing systems.
