2.2.2 啟發式搜索

(1)序列前向選擇( SFS , Sequential Forward Selection )

算法描述：特征子集X從空集開始，每次選擇一個特征x加入特征子集X，使得特征函數J( X)最優。簡單說就是，每次都選擇一個使得評價函數的取值達到最優的特征加入，其實就是一種簡單的貪心算法。

算法評價：缺點是只能加入特征而不能去除特征。例如：特征A完全依賴于特征B與C，可以認為如果加入了特征B與C則A就是多余的。假設序列前向選擇算法首先將A加入特征集，然后又將B與C加入，那么特征子集中就包含了多余的特征A。

(2)序列后向選擇( SBS , Sequential Backward Selection )

算法描述：從特征全集O開始，每次從特征集O中剔除一個特征x，使得剔除特征x后評價函數值達到最優。

算法評價：序列后向選擇與序列前向選擇正好相反，它的缺點是特征只能去除不能加入。

另外，SFS與SBS都屬于貪心算法，容易陷入局部最優值。

(3) 雙向搜索( BDS , Bidirectional Search )

算法描述：使用序列前向選擇(SFS)從空集開始，同時使用序列后向選擇(SBS)從全集開始搜索，當兩者搜索到一個相同的特征子集C時停止搜索。

雙向搜索的出發點是 。如下圖所示，O點代表搜索起點，A點代表搜索目標。灰色的圓代表單向搜索可能的搜索范圍，綠色的2個圓表示某次雙向搜索的搜索范圍，容易證明綠色的面積必定要比灰色的要小。

?

圖2. 雙向搜索

(4) 增L去R選擇算法 ( LRS , Plus-L Minus-R Selection )

該算法有兩種形式:

<1> 算法從空集開始，每輪先加入L個特征，然后從中去除R個特征，使得評價函數值最優。( L > R )
<2> 算法從全集開始，每輪先去除R個特征，然后加入L個特征，使得評價函數值最優。( L < R )

算法評價：增L去R選擇算法結合了序列前向選擇與序列后向選擇思想， L與R的選擇是算法的關鍵。

(5) 序列浮動選擇( Sequential Floating Selection )

算法描述：序列浮動選擇由增L去R選擇算法發展而來，該算法與增L去R選擇算法的不同之處在于：序列浮動選擇的L與R不是固定的，而是“浮動”的，也就是會變化的。

序列浮動選擇根據搜索方向的不同，有以下兩種變種。
<1>序列浮動前向選擇( SFFS , Sequential Floating Forward Selection )

算法描述：從空集開始，每輪在未選擇的特征中選擇一個子集x，使加入子集x后評價函數達到最優，然后在已選擇的特征中選擇子集z，使剔除子集z后評價函數達到最優。

<2>序列浮動后向選擇( SFBS , Sequential Floating Backward Selection )

算法描述：與SFFS類似，不同之處在于SFBS是從全集開始，每輪先剔除特征，然后加入特征。

算法評價：序列浮動選擇結合了序列前向選擇、序列后向選擇、增L去R選擇的特點，并彌補了它們的缺點。

(6) 決策樹( Decision Tree Method , DTM)

算法描述：在訓練樣本集上運行C4.5或其他決策樹生成算法，待決策樹充分生長后，再在樹上運行剪枝算法。則最終決策樹各分支處的特征就是選出來的特征子集了。決策樹方法一般使用信息增益作為評價函數。

2.2.3 隨機算法
(1) 隨機產生序列選擇算法(RGSS, Random Generation plus Sequential Selection)
算法描述：隨機產生一個特征子集，然后在該子集上執行SFS與SBS算法。
算法評價：可作為SFS與SBS的補充，用于跳出局部最優值。

(2) 模擬退火算法( SA, Simulated Annealing )
模擬退火算法可參考?大白話解析模擬退火算法?。

算法評價：模擬退火一定程度克服了序列搜索算法容易陷入局部最優值的缺點，但是若最優解的區域太小（如所謂的“高爾夫球洞”地形），則模擬退火難以求解。

(3) 遺傳算法( GA, Genetic Algorithms )
遺傳算法可參考?遺傳算法入門?。
算法描述：首先隨機產生一批特征子集，并用評價函數給這些特征子集評分，然后通過交叉、突變等操作繁殖出下一代的特征子集，并且評分越高的特征子集被選中參加繁殖的概率越高。這樣經過N代的繁殖和優勝劣汰后，種群中就可能產生了評價函數值最高的特征子集。

隨機算法的共同缺點：依賴于隨機因素，有實驗結果難以重現。

2.3 評價函數
評價函數的作用是評價產生過程所提供的特征子集的好壞。
評價函數根據其工作原理，主要分為篩選器(Filter)、封裝器( Wrapper )兩大類。

篩選器通過分析特征子集內部的特點來衡量其好壞。篩選器一般用作預處理，與分類器的選擇無關。篩選器的原理如下圖3：

?

圖3. Filter原理(Ricardo Gutierrez-Osuna 2008 )

封裝器實質上是一個分類器，封裝器用選取的特征子集對樣本集進行分類，分類的精度作為衡量特征子集好壞的標準。封裝器的原理如圖4所示。

?

圖4. Wrapper原理 (Ricardo Gutierrez-Osuna 2008 )

下面簡單介紹常見的評價函數。
(1) 相關性( Correlation)
運用相關性來度量特征子集的好壞是基于這樣一個假設：好的特征子集所包含的特征應該是與分類的相關度較高（相關度高），而特征之間相關度較低的（亢余度低）。
可以使用線性相關系數(correlation coefficient) 來衡量向量之間線性相關度。

( 2) 距離 (Distance Metrics )
運用距離度量進行特征選擇是基于這樣的假設：好的特征子集應該使得屬于同一類的樣本距離盡可能小，屬于不同類的樣本之間的距離盡可能遠。

常用的距離度量（相似性度量）包括歐氏距離、標準化歐氏距離、馬氏距離等。

(3) 信息增益( Information Gain )
假設存在離散變量Y，Y中的取值包括{y1，y2，....，ym} ，yi出現的概率為Pi。則Y的信息熵定義為：

信息熵有如下特性：若集合Y的元素分布越“純”，則其信息熵越小；若Y分布越“紊亂”，則其信息熵越大。在極端的情況下：若Y只能取一個值，即P1=1，則H(Y)取最小值0；反之若各種取值出現的概率都相等，即都是1/m，則H(Y)取最大值log2m。

在附加條件另一個變量X，而且知道X=xi后，Y的條件信息熵(Conditional Entropy)表示為：

?

假設存在特征子集A和特征子集B，分類變量為C，若IG( C|A ) > IG( C|B ) ，則認為選用特征子集A的分類結果比B好，因此傾向于選用特征子集A。

(4)一致性( Consistency )
若樣本1與樣本2屬于不同的分類，但在特征A、 B上的取值完全一樣，那么特征子集{A，B}不應該選作最終的特征集。

(5)分類器錯誤率 (Classifier error rate )
使用特定的分類器，用給定的特征子集對樣本集進行分類，用分類的精度來衡量特征子集的好壞。

以上5種度量方法中，相關性、距離、信息增益、一致性屬于篩選器，而分類器錯誤率屬于封裝器。

篩選器由于與具體的分類算法無關，因此其在不同的分類算法之間的推廣能力較強，而且計算量也較小。而封裝器由于在評價的過程中應用了具體的分類算法進行分類，因此其推廣到其他分類算法的效果可能較差，而且計算量也較大。