D&C

特征选择-常见的搜索算法

 本文转载自：http://hi.baidu.com/zhangweijiqn/item/bafddc1bf53cd4f5756a843e
2.2.1完全搜索
完全搜索分为穷举搜索(Exhaustive)与非穷举搜索(Non-Exhaustive)两类。
　　(1) 广度优先搜索( Breadth First Search )
算法描述：广度优先遍历特征子空间。
算法评价：枚举了所有的特征组合，属于穷举搜索，时间复杂度是O(2n)，实用性不高。
　　(2)分支限界搜索( Branch and Bound ) 
算法描述：在穷举搜索的基础上加入分支限界。例如：若断定某些分支不可能搜索出比当前找到的最优解更优的解，则可以剪掉这些分支。
　　(3) 定向搜索(Beam Search )
算法描述：首先选择N个得分最高的特征作为特征子集，将其加入一个限制最大长度的优先队列，每次从队列中取出得分最高的子集，然后穷举向该子集加入1个特征后产生的所有特征集，将这些特征集加入队列。
　　(4) 最优优先搜索( Best First Search )
算法描述：与定向搜索类似，唯一的不同点是不限制优先队列的长度。
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代的繁殖和优胜劣汰后，种群中就可能产生了评价函数值最高的特征子集。
随机算法的共同缺点：依赖于随机因素，有实验结果难以重现。