主要內容：
- 為什麼要進行特徵選擇？
- 什麼是特徵選擇？
- 怎麼進行特徵選擇
特徵選擇：
在現實生活中，一個對象往往具有很多屬性（以下稱為特徵），這些特徵大致可以被分成三種主要的類型：
相關特徵：對於學習任務（例如分類問題）有幫助，可以提升學習算法的效果；
無關特徵：對於我們的算法沒有任何幫助，不會給算法的效果帶來任何提升；
冗餘特徵：不會對我們的算法帶來新的信息，或者這種特徵的信息可以由其他的特徵推斷出；
但是對於一個特定的學習算法來說，哪一個特徵是有效的是未知的。因此，需要從所有特徵中選擇出對於學習算法有益的相關特徵。而且在實際應用中，經常會出現維度災難問題，尤其是在文本處理中。例如，可以把一篇文檔表示成一個詞向量，但是往往會使用所有的單詞作為字典，因此對於一篇可能僅僅包含100或者200個單詞的文檔，可能需要上萬的維度（也就是特徵）。如果可以從中選擇一部分相關特徵構建模型，這個問題就可以得到一定程度的解決。所以，特徵選擇和降維有一定的相似之處。另外，從上面的例子中可以發現，如果只選擇所有特徵中的部分特徵構建模型，那麼可以大大減少學習算法的運行時間，也可以增加模型的可解釋性。
因此，進行特徵選擇的主要目的：
- 降維
- 降低學習任務的難度
- 提升模型的效率
定義：
從N個特徵中選擇其中M（M 特徵選擇想要做的是：選擇儘可能少的子特徵，模型的效果不會顯著下降，並且結果的類別分佈儘可能的接近真實的類別分別。機器學習 特徵選擇的過程： 對於一個有N個特徵的對象，可以產生2^N個特徵子集，特徵選擇就是從這些子集中選出對於特定任務最好的子集。特徵選擇主要包括四個過程： 生成過程其實是一個搜索過程，這個過程可以從以下幾種情況開始： 1.沒有特徵； 2.所有特徵； 3.隨機特徵子集。 在前兩種情況下，每次迭代可以增加、刪除特徵；但是在最後一種情況下，每次迭代隨機增加或者刪除特徵。 評價函數用來評價生成過程中生成的特徵子集，產生一個值用來比較當前特徵子集和當前最優特徵子集，如果這個特徵子集更好，那麼就取代當前最優子集。 停止條件用來決定迭代過程什麼時候停止，生成過程和評價函數可能會對於怎麼選擇停止條件產生影響。停止條件有以下四種選擇： 達到預定義的最大迭代次數； 達到預定義的最大特徵數； 增加（刪除）任何特徵不會產生更好的特徵子集； 根據評價函數，產生最優特徵子集； 
驗證過程並不是特徵選擇本身的一部分，但是選擇出的特徵必須是有效。因此，需要使用不同的測試集、學習方法驗證選擇出來的特徵子集，然後比較這些驗證結果。
生成過程：
生成過程是一個搜索過程，這個過程主要有以下三個策略：
- 完全搜索：根據評價函數做完全搜索。完全搜索主要有兩種：窮舉搜索和非窮舉搜索;
- 啟發式搜索：根據一些啟發式規則在每次迭代時，決定剩下的特徵是應該被選擇還是被拒絕。這種方法很簡單並且速度很快，因為它的搜索空間是O(n^2);
- 隨機搜索：每次迭代時會設置一些參數，參數的選擇會影響特徵選擇的效果。由於會設置一些參數（例如最大迭代次數），所以搜索空間也遠遠小於O(2^n);
評價函數：
評價函數主要用來評價選出的特徵子集的好壞，一個特徵子集是最優的往往指相對於特定的評價函數來說的。評價函數主要用來度量一個特徵（或者特徵子集）可以區分不同類別的能力。根據具體的評價方法主要有三類：
- 過濾式（filter): 先進行特徵選擇，然後去訓練學習器，所以特徵選擇的過程與學習器無關。相當於先對於特徵進行過濾操作，然後用特徵子集來訓練分類器。
- 包裹式（wrapper）：直接把最後要使用的分類器作為特徵選擇的評價函數，對於特定的分類器選擇最優的特徵子集。
- Filter和Wrapper組合式算法：先使用Filter進行特徵選擇，去掉不相關的特徵，降低特徵維度；然後利用Wrapper進行特徵選擇。
嵌入式（embedding）：把特徵選擇的過程與分類器學習的過程融合一起，在學習的過程中進行特徵選擇。最常見的使用L1正則化進行特徵選擇。
一般有5種比較常見的評價函數：
- 距離度量：如果 X 在不同類別中能產生比 Y 大的差異，那麼就說明 X 要好於 Y;
- 信息度量：主要是計算一個特徵的信息增益（度量先驗不確定性和期望後驗不確定性之間的差異）；
- 依賴度量：主要用來度量從一個變量的值預測另一個變量值的能力。最常見的是相關係數：用來發現一個特徵和一個類別的相關性。如果 X 和類別的相關性高於 Y與類別的相關性，那麼X優於Y。對相關係數做一點改變，用來計算兩個特徵之間的依賴性，值代表著兩個特徵之間的冗餘度。
- 一致性度量：對於兩個樣本，如果它們的類別不同，但是特徵值是相同的，那麼它們是不一致的；否則是一致的。找到與全集具有同樣區分能力的最小子集。嚴重依賴於特定的訓練集和 最小特徵偏見（Min-Feature bias）的用法；找到滿足可接受的不一致率（用戶指定的參數）的最小規模的特徵子集。
- 誤分類率度量：主要用於Wrapper式的評價方法中。使用特定的分類器，利用選擇的特徵子集來預測測試集的類別，用分類器的準確率來作為指標。這種方法準確率很高，但是計算開銷較大。
特徵選擇算法：
根據上面的三種不同的搜索策略和五種不同的評價函數，會有很多具體的特徵選擇算法。以下是主要的分類：
照三種不同的搜索策略，簡單介紹幾種具體的算法：
完全搜索：
廣度優先搜索（Breadth First Search）
主要採用完全搜索策略和距離度量評價函數。使用廣度優先算法遍歷所有可能的特徵子集，選擇出最優的特徵子集。
分支界限搜索（Branch & Bound）
主要採用完全搜索和距離度量。B&B從所有的特徵上開始搜索，每次迭代從中去掉一個特徵，每次給評價函數的值一個限制條件。因為評價函數滿足單調性原理（一個特徵子集不會好於所有包含這個特徵子集的更大的特徵子集），所以如果一個特徵使得評價函數的值小於這個限制，那麼就刪除這個特徵。類似於在窮舉搜索中進行剪枝。
定向搜索（Beam Search）
主要採用完全搜索策略和誤分類率作為評價函數。選擇得分最高的特徵作為特徵子集，把它加入到一個有長度限制的隊列中，從頭到尾依次是性能最優到最差的特徵子集。每次從隊列總取得分最高的子集，然後窮舉向該子集中加入一個特徵後所有的特徵集，按照得分把這些子集加入到隊列中。
最優優先搜索（Best First Search）
和定位搜索類似，不同點在於不限制隊列的長度。
啟發式搜索
序列前向選擇（SFS , Sequential Forward Selection）
使用誤分類率作為評價函數。從空集開始搜索，每次把一個特徵加入到這個特徵子集中，使得評價函數達到最優值。如果候選的特徵子集不如上一輪的特徵子集，那麼停止迭代，並將上一輪的特徵子集作為最優的特徵選擇結果。
廣義序列前向選擇（GSFS ，Generalized Sequential Forward Selection）
該方法是SFS算法的加速算法，它可以一次性向特徵集合中加入r個特徵。在候選特徵中選擇一個規模為r的特徵子集，使得評價函數取得最優值。
序列後向選擇（SBS , Sequential Backward Selection）
把誤分類率作為評價函數。從特徵的全集開始搜索，每次從特徵子集中去掉一個特徵，使得評價函數達到最優值。
SFS和SBS都屬於貪心算法，它們僅考慮使本輪選定集最優，因此容易陷入局部最優。
廣義序列後向選擇（GSBS，Generalized Sequential Backward Selection）
該方法是SBS的加速，可以一次性的從特徵子集中去除一定數量的特徵。是實際應用中的快速特徵選擇算法，性能相對較好。但是有可能消除操作太快，去除掉重要的信息，導致很難找到最優特徵子集。
雙向搜索（BDS , Bi-directional Search）
分別使用SFS和SBS同時進行搜索，只有當兩者達到一個相同的特徵子集時才停止搜索。為了保證能夠達到一個相同的特徵子集，需要滿足兩個條件：
被SFS選中的特徵不能被SBS去除；
被SBS去除的特徵就不能SFS選擇；
增L去R選擇算法（LRS , Plus L Minus R Selection）
採用誤分類率作為評價函數。允許特徵選擇的過程中進行回溯，這種算法主要有兩種形式：
當L>R時，是一種自下而上的方法，從空集開始搜索，每次使用SFS增加L個特徵，然後用SBS從中去掉R個特徵；
當L 序列浮動選擇（Sequential Floating Selection） 和增L去R算法類似，只不過序列浮動算法的L和R不是固定的，每次會產生變化，這種算法有兩種形式： 序列浮動前向選擇（SFFS , Sequential Floating Forward Selection）:從空集開始搜索，每次選擇一個特徵子集，使得評價函數可以達到最優，然後在選擇一個特徵子集的子集，把它去掉使得評價函數達到最優； 序列浮動後向選擇（SFBS , Sequential Floating Backward Selection）:從特徵全集開始搜索，每次先去除一個子集，然後在加入一個特徵子集。 決策樹算法（DTM , Decision Tree Method） 採用信息增益作為評價函數。在訓練集中使用C4.5算法，等到決策樹充分增長，利用評價函數對決策樹進行剪枝。最後，出現在任意一個葉子節點的路徑上的所有特徵子集的並集就是特徵選擇的結果。
閱讀更多 邵寒峰 的文章
