特征选择

特征选择基本介绍连接：http://www.cnblogs.com/heaad/archive/2011/01/02/1924088.html 《特征选择常用算法综述 》

 以下内容只是摘抄，没有深入理解，可能存在一些问题。

搜索策略

 

一：完全搜索

 

1，BestFirst（最佳优先）

        最佳优先搜索时宽度优先搜索的扩展，基本思想是将节点表按据目标的距离进行排序，再以节点的估计距离为标准选择待扩展的节点。

        算法步骤：
         1. 用N表示已经排序的初始结点表(从小到大)
         2. 如果N为空集，则退出并给出失败信号
         3. n取为N的首结点，并在N中删除结点n，放入已访问结点列表
         4. 如果n为目标结点，则退出并给出成功信号
         5. 否则，将n的后继结点加到N中，记为N’，对N’中的结点按距目标的估计距离排序，并返回2步
          在搜索的过程中一般会用到评估函数f(n)，表示从初始节点S经过n到达目的节点t的最佳路径代价f*(n)的估计：
          从S到n的最佳代价g*(n)的估计g(n)，g(n) ≥ g*(n)，即局部最小≥ 全局最小
          从n到t 的最佳代价h*(n)的估计h(n)，若对所有结点n，都有h(n)≤h*(n)，则算法A一定能找到一条到达目标结点的最佳路径，此时算法A      称为算法A*。
          f(n) = g(n) + h(n)作为f*(n) = g*(n) + h*(n)的估计,估计值越小的点希望越高，应该优先扩展。

 

2，ExhaustiveSearch（穷举搜索）；

枚举了所有的特征组合，属于穷举搜索，时间复杂度是O(2n)，实用性不高。

 

二，随机搜索方法。

 

1，RandomSearch（随机搜索）：

算法描述：随机产生一个特征子集，然后在该子集上执行SFS与SBS算法。

算法评价：可作为SFS与SBS的补充，用于跳出局部最优值。

2，ScatterSearchV1（离散搜索）：

参考：http://file./3/38/38c/38c661f9-12f5-4248-86a8-23100d585031.pdf

 

  三：序列搜索方法

a.单独最优组合：RankSearch（评估器计算属性判据值并排序），Ranker（属性判据值排序）；

b.向前搜索：LinearForwardSelection（线性向前搜索）；

算法描述：特征子集X从空集开始，每次选择一个特征x加入特征子集X，使得特征函数J( X)最优。简单说就是，每次都选择一个使得评价函数的取值达到最优的特征加入，其实就是一种简单的贪心算法。

算法评价：缺点是只能加入特征而不能去除特征。例如：特征A完全依赖于特征B与C，可以认为如果加入了特征B与C则A就是多余的。假设序列前向选择算法首先将A加入特征集，然后又将B与C加入，那么特征子集中就包含了多余的特征A。

c.向后搜索：FCBFSearch（基于相关性分析的特征选择方法）；

算法描述：从特征全集O开始，每次从特征集O中剔除一个特征x，使得剔除特征x后评价函数值达到最优。

算法评价：序列后向选择与序列前向选择正好相反，它的缺点是特征只能去除不能加入。另外，SFS与SBS都属于贪心算法，容易陷入局部最优值。

d. 增l去r选择方法：RaceSearch（比较特征子集的交叉验证错误情况），GreedyStepwise（向前或向后的单步搜索）；

该算法有两种形式:

　　<1> 算法从空集开始，每轮先加入L个特征，然后从中去除R个特征，使得评价函数值最优。( L > R )

　　<2> 算法从全集开始，每轮先去除R个特征，然后加入L个特征，使得评价函数值最优。( L < R )

　算法评价：增L去R选择算法结合了序列前向选择与序列后向选择思想， L与R的选择是算法的关键。

 

e. 浮动搜索方法：SubsetSizeForwardSelection（按照特征子集大小向前线性搜索，这是线性搜索的扩展）；

f.启发式搜索：GeneticSearch（基于Goldberg（1989）提出的简单遗传算法），TabuSearch（禁忌搜索）。

 

 

 

按照评价策略的两大方法，这两大方法基于是否使用后续的分类方法来区别，且Filter方法注重对单个属性进行评价，Wrapper方法侧重对特征子集进行评价。

这里列举各个分类的几种方法：
1）Filter方法：
ChiSquaredAttributeEval——根据与分类有关的每一个属性的卡方值（统计学词汇）进行评估；
FilteresAttributeEval——运行在任意过滤器之后的数据上的任意属性评估；
GainRatioAttributeEva——根据与分类有关的每一个属性的增益比进行评估；
InfoGainAttributeEval——根据与分类有关的每一个属性的信息增益进行评估；
SignificanceAttributeEva——计算双向功能的概率意义评估属性值。

2）Wrapper方法：
CfsSubsetEval——根据属性子集中每一个特征的预测能力以及它们之间的关联性进行评估；
ClassifierSubsetEval——根据训练集或测试集之外的数据评估属性子集；
WrapperSubsetEval——使用一种学习模式对属性集进行评估；
ConsistencySubsetEval——根据利用属性子集进行分类时得到的分类值的一致性进行评价。

3）Filter与Wrapper结合：

OneRAttributeEval——根据OneR分类器评估属性。