特征選擇是機(jī)器學(xué)習(xí)非常重要的一環(huán)。之所以要考慮特征選擇，是因?yàn)闄C(jī)器學(xué)習(xí)經(jīng)常面臨過擬合的問題。
過擬合的表現(xiàn)是模型參數(shù)太貼合訓(xùn)練集數(shù)據(jù)，模型在訓(xùn)練集上效果很好而在測試集上表現(xiàn)不好，也就是在高方差。簡言之模型的泛化能力差。過擬合的原因是模型對于訓(xùn)練集數(shù)據(jù)來說太復(fù)雜，要解決過擬合問題，一般考慮如下方法：

1. 收集更多數(shù)據(jù)
2. 通過正則化引入對復(fù)雜度的懲罰
3. 選擇更少參數(shù)的簡單模型
4. 對數(shù)據(jù)降維
   其中第1條一般是很難做到的，這篇我們主要梳理第2和第4點(diǎn)

• 通過正則化：
  對于參數(shù)模型（parametric model），最簡單直接的方法是L1正則化來降維。參數(shù)模型是什么？是可由公式表達(dá)的、有或參數(shù)的模型。這種模型在訓(xùn)練集上學(xué)習(xí)得到一個公式表達(dá)式，對于新的測試數(shù)據(jù)，可以直接由表達(dá)式算出預(yù)測結(jié)果，預(yù)測的時(shí)候不再需要訓(xùn)練集。參數(shù)模型的代表有邏輯回歸，線性回歸，神經(jīng)網(wǎng)絡(luò)等。正則化分為L1和L2， L1用L1范數(shù)最小化代價(jià)函數(shù)的SSE，可以把某些特征壓縮到0，相當(dāng)于特征選擇了。而L2用L2范數(shù)最小化代價(jià)函數(shù)的SSE，只能把某些特征壓縮到很小的值，但不可能是0。

• 對于非參數(shù)模型(nonparametric model) ， 很有用的辦法是通過特征選擇來降維。
  降維有兩種方式：特征選擇和特征抽取。特征選擇是直接選特征子集（本篇寫的是特征選擇）。特征抽取是把特征映射到低維空間（PCA是代表之一，在另一篇里已經(jīng)寫過了）。
  特征選擇有三個層面的方法：這里分別介紹。

1. Wrapper方法。屬于Wrapper的還有exhaustive search BFS (Breadth First Search), Non-exhaustive search (Branch and Bound Search), heuristic search(SFS, SBS, SDS), Random Search (RGSS) . 總體來講，Wrapper的實(shí)現(xiàn)原理是：基于hold-out方法，對于每一個待選的特征子集，都在訓(xùn)練集上訓(xùn)練一遍模型，然后在測試集上根據(jù)誤差大小選擇出特征子集。
   這里重點(diǎn)寫heuristic search(SFS, SBS, SDS)里的SBS。 heuristic search一般也被稱為Sequential feature selection。這是一種貪婪搜索算法，可以將d維數(shù)據(jù)篩選到k維。它可以去除無關(guān)的特征或嗓音，保留對目標(biāo)最有用的特征， 它的目標(biāo)就是減少誤差（模型方差），它其中又以Sequential Backward Selection(SBS)為代表。
   SBS的工作原理是：從特征全集里逐個去除單個特征，直至剩余的特征子集達(dá)到期望的維度。那么如何逐個去除呢？我們先定義一個標(biāo)準(zhǔn)函數(shù)J，借助J的變化來判斷每一步應(yīng)該去除哪個特征。一般而言，J就是模型的代價(jià)函數(shù)，這里記住我們降維的最終目標(biāo)是讓代價(jià)函數(shù)最優(yōu)（最小化）。所以最簡單的方法可以是：，我們用 作為判斷標(biāo)準(zhǔn)，每一步的時(shí)候哪個特征讓這個標(biāo)準(zhǔn)最大化，我們就去除哪個標(biāo)準(zhǔn)?；蛘呖梢赃@樣理解，我們在每一步時(shí)選擇去掉的是最不會導(dǎo)致模型變更差的那個特征。
   但是SBS在SKLEARN里沒有現(xiàn)成的包。這里給出偽代碼：
   

   Screen Shot 2018-09-05 at 10.19.28 AM.png

2. Embedded 方法
   故名思義，Embedded是指特征選擇算法是學(xué)習(xí)算法的一部分，已經(jīng)被整合進(jìn)學(xué)習(xí)算法里了。最具代表性的如決策樹算法，因?yàn)樗旧砭褪腔谛畔⒃鲆娴囊环N算法，一個特征里包括的同一分類的孩子節(jié)點(diǎn)越多，這個特征就越顯著（白種人里有美英法意等等，黃種人里有中日韓等等，人的分類可以根據(jù)膚色往下細(xì)分。所以膚色就是決策樹首先考慮的一個顯著特征）。所以，決策樹本身的生成就是在做特征選擇。決策樹有ID3, C4.5, CART樹。其中ID3只用于連續(xù)型變量，C4.5和CART樹可以用于連續(xù)變量也可以用于分類變量。

3. Filter方法
   就是對特征打分，再根據(jù)閾值選擇特征。Filter方法獨(dú)立于模型本身，它的結(jié)果比Wrapper方法更有普適性，計(jì)算性能好于Wrapper，所以有時(shí)候它被用于Wrapper方法之前的預(yù)處理。
   Filter方法包括：distance metrics, correlation, mutual information, and consistency metrics
   其中correlation方法是計(jì)算特征之間的獨(dú)立性。通常用皮爾遜相關(guān)系數(shù)為指標(biāo)。mutual information比correlation更有普適性，它描述了p(x,y)和p(x)*p(y)有多么相關(guān)。consistency metrics通常用卡方檢驗(yàn)，其思想是找出和預(yù)測目標(biāo)不相關(guān)的特征，所以其過程是計(jì)算每個特征和預(yù)測目標(biāo)的卡方統(tǒng)計(jì)量。

福利：
貪婪搜索算法（greedy search）是局部最優(yōu)算法。與之對應(yīng)的是窮舉算法 (exhaustive search)，窮舉算法是遍歷所有可能的組合達(dá)到全局最優(yōu)級，但是計(jì)算復(fù)雜度是2^n，一般是不太實(shí)際的算法。