Scikit Learn 0.24 更新 SequentialFeatureSelector 介紹
===

有打過kaggle competition或是有ML實務經驗的人應該都知道，以目前的ML技術而言，features set的好壞非常關鍵的影響了最終的效果，而這次scikit learn 0.24的更新重要的一個function就是[SequentialFeatureSelector](https://scikit-learn.org/stable/modules/generated/sklearn.feature_selection.SequentialFeatureSelector.html#sklearn.feature_selection.SequentialFeatureSelector)，這個方法是就我所知kaggle上最常被使用的feature selection方法（不考慮用domain knowledge來進行feature selection），大家過去就習慣自己寫for loop iterate各種features set然後再算cross validation scores，或是使用mlxtend之類的package，而這次scikit learn更新就提供這個function。

下面我簡介一下幾個scikit learn裡面幾個feature selection的分支，並在最後詳細介紹SequentialFeatureSelector的原理。

# Feature Selection簡介
Feature selection顧名思義就是在選擇feature，而選擇feature的目的就是讓feature數量變少，藉此我們可能能夠避免overfit、減低training time、減低inference time、有時候甚至可以提升performance。

在kaggle中最常被使用的場景就是當起始feature不少時，我們會大量做EDA，然後做feature selection先把feature變少，保證我們cross validation score跟public leaderboard有足夠的correlation後再往後嘗試提升performance。

而Scikit learn其實有提供非常多種[Feature selection](https://scikit-learn.org/stable/modules/classes.html#module-sklearn.feature_selection)的方法，其中最主要我們分成3種。
1. Filtering Methods：先算出每個feature的某種數值（通常是某種分數），然後基於這個數值去選出較好的feature。最有名的例子可能是先算每個feature跟label的f-regression score，再依照score篩選TopK faetures。

2. **Wrapper Methods**：也就是等一下要著重講的，是**針對某個模型**，基於他的score來選出最後的feature set。

3. Embedded Methods：利用Training中間model的某種資訊，來當作feature selection的依據，而model會在training過程中自動的使用重要的feature，像是LASSO，在training的過程中因應演算法某些feature對應的coef會變成0，因此在training跟prediction的時候這些feature會直接被忽略。

這三個方法相較起來，**Filtering Methods的速度最快**，因為他跟模型訓練無關，但相對的**效果也最差**，尤其目前的Filtering Methods普遍都是univariate的statistic，所以多個feature interaction的效果都不會被考慮進來，而Embedded Methods跟Wrapper Methods的效果都不錯，相對而言Embedded Methods因為都是直接只用model內部的資訊來選feature，而這個資訊跟我們final performance的關聯性不見得很高，所以我一般更常是將他當成一個初期的參考為主，而**Wrapper Methods我認為是Kaggle中大家真正最常使用的方法**。

# Wrapper Methods步驟
一般而言Wrapper Methods的步驟都是以下4步
1. 製造出多種可能的feature set
2. 基於每個feature set都train出一個我們的model
3. 比較每個model的performance，把performance最高的model對應使用的feature set選出來，當成目前最好的feature set
4. 看目前feature set大小（或是model performance）有沒有達標，如果沒有就回到第一步再loop一遍。

# SequentialFeatureSelector介紹
SequentialFeatureSelector就是基於上述的步驟，**我們分成兩種Sequential Forward Selection（SFS, 或稱Forward SFS, 逐步Add Features）跟Sequential Backward Selection（SBS, 或稱Backward SFS, 逐步Remove Features），而Sequential的意思就是「每次只加/減一個feature，依序處理多次直到達到標準」。**

## Sequential Forward Selection流程
假設總共有5個features，我們希望在5個features中選出3個features。

**初始為0個feature = {}**

第一輪
1. 把所有feature都當成potential add feature，製造出所有可能的feature set：{f1}, {f2}, {f3}, {f4}, {f5}
2. 每個feature set都用來train一個lightGBM（或是其他model）
3. 把5個lightGBM的validation scores拿出來比較，選出最高的一個，並把其對應的feature set當成第一輪得到的feature set，假設這裡{f4}得到最高分
4. 目前feature set只有1個feature，還未達到目標的3個features，繼續第二輪。

**目前feature = {f4}**

第二輪
1. 把所有還沒用過feature都當成potential add feature，製造出所有可能的feature set：{f4, f1}, {f4, f2}, {f4, f3}, {f4, f5}
2. 每個feature set都用來train一個lightGBM（或是其他model）
3. 把4個lightGBM的validation scores拿出來比較，選出最高的一個，並把其對應的feature set當成第一輪得到的feature set，假設這裡{f4, f3}得到最高分
4. 目前feature set只有2個features，還未達到目標的3個features，繼續第三輪。

**目前feature = {f4, f3}**

第三輪
1. 把所有還沒用過feature都當成potential add feature，製造出所有可能的feature set：{f4, f3, f1}, {f4, f3, f2}, {f4, f3, f5}
2. 每個feature set都用來train一個lightGBM（或是其他model）
3. 把3個lightGBM的validation scores拿出來比較，選出最高的一個，並把其對應的feature set當成第一輪得到的feature set，假設這裡{f4, f3, f1}得到最高分
4. 目前feature set有3個features，已達到目標的3個features，結束。

**最終我們選出來的feature = {f1, f3, f4}**
## Sequential Backward Selection流程
假設總共有5個features，我們希望在5個features中選出3個features。

**初始為5個feature = {f1, f2, f3, f4, f5}**
第一輪
1. 把所有feature都當成potential remove feature，製造出所有可能的feature set：{f1, f2, f3, f4}, {f1, f2, f3, f5}, {f1, f2, f4, f5}, {f1, f3, f4, f5}, {f2, f3, f4, f5}
2. 每個feature set都用來train一個lightGBM（或是其他model）
3. 把5個lightGBM的validation scores拿出來比較，選出最高的一個，並把其對應的feature set當成第一輪得到的feature set，假設這裡{f1, f3, f4, f5}得到最高分
4. 目前feature set有4個feature，還未達到目標的3個features，繼續第二輪。

**目前feature = {f1, f3, f4, f5}**
第二輪
1. 把剩下所有feature都當成potential remove feature，製造出所有可能的feature set：{f1, f3, f4}, {f1, f3, f5}, {f1, f4, f5}, {f3, f4, f5}
2. 每個feature set都用來train一個lightGBM（或是其他model）
3. 把5個lightGBM的validation scores拿出來比較，選出最高的一個，並把其對應的feature set當成第一輪得到的feature set，假設這裡{f1, f3, f5}得到最高分
4. 目前feature set有3個feature，已達到目標的3個features，結束。

**最終我們選出來的feature = {f1, f3, f5}**

這邊順帶說明一下，因為SFS通常是直接使用**我們最終想用的model**的CV score來挑feature set，所以他的robustness非常高，只要CV score夠準，如果在kaggle上效果不好更有可能是Cross Validation出問題。

## SequentialFeatureSelector in scikit learn 0.24.0
scikit learn在0.24.0版本新增了[sklearn.feature_selection.SequentialFeatureSelector](https://scikit-learn.org/stable/modules/generated/sklearn.feature_selection.SequentialFeatureSelector.html#sklearn.feature_selection.SequentialFeatureSelector)這個function，做的事情就是與我們上述所說完全相同。

他的Parameters比較重要有下面幾個
* estimator: 傳入你想要用來train的model，而feature selection的過程也會依據這個model的cv performance，這邊一般我們是推薦**傳入你預期最終使用的model**，這樣選出來的feature才會是最終model最適合的。
* n_features_to_select: 你想要的最終feature數量，跟scikit learn一般的設計一樣，這邊可以傳入小數，用來表示你想要**保留多少比例的feature**。
* direction: {‘forward’, ‘backward’}: 這就是在選擇要做forward還是backward，兩個結果可能差異很大，可以都跑跑看。

而對應的Methods則如其他feature transformation function一樣，以fit(), fit_transform(), transform()為主，這裡相信大家對scikit learn夠熟悉應該都清楚這三個的作用。

Example in scikit learn:

from sklearn.feature_selection import SequentialFeatureSelector
from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_iris
X, y = load_iris(return_X_y=True)
### 定義你要使用的model
knn = KNeighborsClassifier(n_neighbors=3)
### 定義SFS，這裡使用KNN來當作選擇的model，最終希望變成3個feature，direction沒設代表default forward
sfs = SequentialFeatureSelector(knn, n_features_to_select=3)
### 學習feature selection
sfs.fit(X, y)


sfs.get_support()
### 進行feature selection，這裡如果把transform完的結果記起來就是feature selection完的dataset
sfs.transform(X).shape

# SequentialFeatureSelector in mlxtend
在scikit learn推出SequentialFeatureSelector之前其實mlxtend就已經有相對應的function，一樣稱為[SequentialFeatureSelector](SequentialFeatureSelector)，這邊使用方法跟scikit learn很類似，推薦大家直接進去看如何使用。

mlxtend跟scikit learn的SequentialFeatureSelector最大的不同有下面2點
1. mlxtend有fixed_features這個parameter，fixed_features非常好用，他的功用是當你已經確認某幾個feature絕對有效的時候，可以先把這幾個feature預定為最終結果。
　　意思就是說，如果我一樣f1~f5要選3個features，如果我事先做過研究或是基於我的domain knowledge知道f3非常重要，我可以在feature selection開始前就預訂f3要被選出來，這樣有兩大好處，**第一可以節省時間，第二我們能夠把human knowledge結合進來**。
　　而目前scikit learn還沒有支援這個功能，我們認為很有用的feature是有可能被SequentialFeatureSelector丟掉的，當然如果出現這種情況更有趣的就是去深入研究這個domain knowledge跟model行為的落差，也就是去理解為甚麼這個feature被丟掉。

2. mlxtend有floating這個parameter，這是一個非常有趣的setting，他的概念是conditional inclusion/exclusion，conditional inclusion意思是「**在Backward SFS時，當我們丟棄某個feature後我們能夠去確認此時我們加回任意一個更之前的feature是否能夠提升CV score**」，也就是說最終feature set有可能包含我們在很早期就丟掉的feature，使用floating會視條件把某些有用的feature撿回來，而Forward SFS也一樣。
　　這個功能我試用過，效果不見得會比較好，但是最差也會跟SFS一樣，具體可以看這篇[論文](https://www.sciencedirect.com/science/article/abs/pii/0167865594901279)。

# Computation Time in SequentialFeatureSelector
SequentialFeatureSelector最大的問題跟gridSearchCV一樣，就是要大量的train model，而這非常耗費我們的運算時間跟資源，所以這邊一般做大規模feature selection的時候，我們都會搭配Multi-Fidelity Search。
常見的一個trick就是使用partial data來做training，Ex: 總共有10W筆data，我們拿其中1W筆data來做feature selection，這樣其中每次training時間就可以大幅下降，而Multi-Fidelity Search我們在empirical中發現，使用的data只要超過一定比例，最終選出的Hyperparameter跟feature都會有類似的結果。

除此之外可以先用LGBM等tree based model的feature importance初期把最重要跟最不重要的feature抓出來，把絕對無用的feature丟掉。