模型選擇之特征選擇

當我們在訓練模型時，其中一個很重要的部分是訓練模型的參數，也就是模型中各個特征的值，不同的模型具有不同的特征組合，因此對于特征的選擇也就對應了模型的選擇。舉個文本分類的例子，在文本分類的任務中，特征數量p遠大于訓練樣本數n，而我們又知道特征里面有很大一部分是和類別無關的，因此我們就會想到用特征選擇來把與類別相關的特征選出來。對于p個特征，會出現2^p種特征的組合，也就對應了2^p個模型，我們只要選擇一種特征組合，也就選擇了一個模型。

關于特征選擇，下面介紹三種方法。

Filter類

這種方法計算每一個特征與類別的相關度，并獲得一個得分。得分高的特征表明其與類別的關系越強。最后將所有特征按得分高低排序，選擇得分高的特征。

Filter類的典型代表就是信息增益（或者信息增益率）。通過計算特征的信息增益，將信息增益較高的特征選出。具體的做法是，首先為每個特征計算信息增益，并將其作為特征的得分，然后選擇得分較高的前k個特征作為選擇的特征。關于k的值如何選擇，可以采取交叉驗證的方式。

從上面看出，Filter類的特征選擇只需做簡單的統計，計算復雜度低。但這種方法的問題是沒有考慮特征之間的組合關系，有可能某一個特征的分類能力很差，但是它和某些其它特征組合起來會得到不錯的效果。

Wrapper類

假如有p個特征，那么就會有2^p種特征組合，每種組合對應了一個模型。Wrapper類方法的思想是枚舉出所有可能的情況，從中選取最好的特征組合。

這種方式的問題是：由于每種特征組合都需要訓練一次模型，而訓練模型的代價實際上是很大的，如果p非常大，那么上述方式顯然不具有可操作性。下面介紹兩種優化的方法：forward search（前向搜索）和backward search（后向搜索）。

forward search初始時假設已選特征的集合為空集，算法采取貪心的方式逐步擴充該集合，直到該集合的特征數達到一個閾值，該閾值可以預先設定，也可以通過交叉驗證獲得。算法的偽碼如下：

注：上面的算法描述摘自Andrew NG的機器學習課程的課件。

對于算法的外重循環，當F中包含所有特征時或者F中的特征數達到了閾值，則循環結束，算法最后選出在整個搜索過程中最優的特征集合。

backward search初始時假設已選特征集合F為特征的全集，算法每次刪除一個特征，直到F的特征數達到指定的閾值或者F被刪空。該算法在選擇刪除哪一個特征時和forward search在選擇一個特征加入F時是一樣的做法。

Wrapper類的特征選擇方式考慮了特征之間的組合情況，它的效果很好，彌補了Filter類的不足。但是Wrapper類的缺點是計算量太大，即便是做了改進的forward search 和backward search其時間復雜度也是O（p²），當p很大時也是一筆不小的開銷。

折中類

對于上面的filter類和wrapper類，各自都有自己的優點和缺點，那么我們能不能取一種折中的方法來進行特征選擇呢？也就是時間復雜度較低，并且也考慮特征之間的組合關系。

我們知道L1正則化自帶特征選擇的功能，它傾向于留下相關特征而刪除無關特征。

比如在文本分類中，我們不再需要進行顯示的特征選擇這一步，而是直接將所有特征扔進帶有L1正則化的模型里，由模型的訓練過程來進行特征的選擇。

這里需要說明的是，該類方法只是wrapper類和filter類的一個折中，它的時間復雜度或者訓練模型的次數要遠遠低于wrapper類，但其特征選擇的效果沒有wrapper類好；同樣，它的時間復雜度要高于filter類，但特征選擇效果卻好于filter類。

來自： http://blog.csdn.net//henryczj/article/details/41043883