常见特征选择算法20160711

我们毕业啦其实是答辩的标题地方常见特征选择算法什么是特征选择？•模式识别系统的输入时传感器对实物或过程进行测量所得到的数据，其中有些数据可以直接作为特征，有一些需要经过处理之后作为特征，这样的一组特征一般为原始特征。•在原始特征中，并不一定每个特征都有用，从原始特征集合中选择对分类结果有用的特征的过程称为特征选择。比如在识别苹果和橙子的系统中，我们可以抽取的特征很多（体积、重量、颜色、高度、宽度、最宽处高度），在这些特征中有用的是（颜色、高度、最宽处高度），其它特征对识别意义不大，所以去掉。为什么进行特征选择？在机器学习的实际应用中，特征数量往往较多，其中可能存在不相关的特征，特征之间也可能存在相互依赖，容易导致如下的后果：•特征个数越多，分析特征、训练模型所需的时间就越长。•特征个数越多，容易引起“维度灾难”，模型也会越复杂，其推广能力会下降。特征选择能剔除不相关(irrelevant)或亢余(redundant)的特征，从而达到减少特征个数，提高模型精确度，减少运行时间的目的。另一方面，选取出真正相关的特征简化了模型，使研究人员易于理解数据产生的过程。特征选择和特征抽取区别？模式识别中特征降维方法有两种：特征抽取和特征选择特征提取(Featureextraction)是指利用已有的特征计算出一个抽象程度更高的特征集。对已有特征集合进行映射变换得到。PCA、LDA特征选择也叫特征子集选择(FSS,FeatureSubsetSelection)或属性选择(AttributeSelection)。特征选择实质是从原始数据集中选取最优子集的过程。特征选择一般流程A.产生过程(GenerationProcedure)：按一定的搜索策略产生候选特征子集。B.评价函数(EvaluationFunction)：通过某个评价函数来评估特征子集的优劣。C.停止准则(StoppingCriterion)：停止准则是与评价函数相关的，一般是一个阈值，当评价函数值达到这个阈值后就可停止搜索。D.子集验证：用来验证最终所选子集的有效性。评价函数•评价函数通常用来评估某个特征或特征子集分类的能力。•最优特征子集产生和评价函数是相关的，不同评价函数可能产生不同的最优特征子集。•将评价函数分为两类：filter和wrapper。•用符号J(Y)来表示评价函数，其中Y是一个特征集，J(Y)越大表示特征集Y越好Filter：通过分析特征子集内部的信息来衡量特征子集的好坏。评价准则Wrapper：评价函数是一个分类器，采用特定特征子集对样本集进行分类，根据分类的结果来衡量该特征子集的好坏评价函数-Filter•距离或可分性度量：距离度量有时候也称作类别可分离判据、离散度准则,在统计模式识别中对类别的可分离性研究的比较深入。--欧几里得距离、马氏距离、巴氏距离等•相关性度量：用来度量特征和类别之间的相关性。--相关系数•信息论度量：--信息增益、最小描述长度、互信息Filter-距离度量•距离度量，是基于这样的假设：好的特征子集应该使得属于同一类的样本距离尽可能小，属于不同类的样本之间的距离尽可能远。常见的有欧氏距离、马氏距离、巴氏距离等等。Filter-相关系数•运用相关性来度量特征子集的好坏是基于这样一个假设：好的特征子集所包含的特征应该是与分类的相关度较高（相关度高），而特征之间相关度较低的（亢余度低）。•可以使用线性相关系数(correlationcoefficient)来衡量向量之间线性相关度。Filter-信息增益（1）•通过计算特征的信息增益来对特征进行评价。•信息熵：假设存在离散变量Y，Y中可能的取值包括{y1，y2，....，ym}，yi出现的概率为Pi。则Y的信息熵定义为：•条件信息熵：附加条件X=Xi后，Y的条件信息熵变为：•信息增益：加入条件X前后的信息熵之差。Filter-信息增益（2）•对于分类系统来说，类别C是变量，他可能的取值为{C1,C2,…,Cn},而每个类别出现的概率是P(Ci),分类系统的信息熵为：•当新加入一个特征Fj后，系统的信息熵变为：•增加F特征前后的信息增益为：•假设存在特征子集A和特征子集B，分类变量为C，若IG(C|A)IG(C|B)，则认为选用特征子集A的分类结果比B好，因此倾向于选用特征子集A。Filter和Wrapper优缺点评价准则优点缺点filter快速执行；易于推广；准确率方面通常低于Wrapper方法；wrapper准确率高；计算代价大；不易于推广；搜索策略•穷举算法：对特征空间进行穷举搜索（当然也会采用剪枝等优化），搜索出来的特征集对于样本集是最优的。这类算法的时间复杂度是指数级的。•序列算法：这类算法实际上是一种贪心算法，算法时间复杂度较低，但是可能会陷入局部最优值，不一定能找到全局最优解。•随机算法：随机算法属于一种近似算法，能找出问题的近似最优解。每个随机算法都需要设置一定的参数，这些参数的选择很重要。搜索策略•穷举算法：穷举搜索ExhaustiveSearch(ES)分支限界法BranchandBound(B&B)集束搜索BeamSearch(BS)•序列算法：前向顺序选择后向顺序选择增L去R算法双向搜索算法序列浮动选择算法•随机算法：随机产生序列选择算法模拟退火算法遗传算法穷举搜索（ES）•穷举所有满足条件的特征子集，从中选取最优。如果有N个特征，不限定选取特征的个数，则有个候选特征子集。•从D个特征中选择d个，可能组合q•计算所有可能的特征组合的J，选择J最大的那组为最优组合。这种方法计算量大，只适用于特征个数比较少的情况，运算量随着特征维数的增加呈指数递增，实际应用中经常碰到几百甚至成千上万个特征，因此穷举法虽然简单却难以实际应用。N2分支限界法（B&B）•分支限界法是一种自上而下的搜索算法，采用剪枝策略优化搜索过程，得到全局最优解。•使用分支限界进行特征选择需要先引入一个单调性假设(monotonicityassumption)：J(Y)J(Y+x)，即任何特征集的都优于其任何的子集。•如果初始特征集合中共有N个特征，现在需要进行特征选择得到M个集合，分支界限法可以看作是去掉M’=N-M个特征。•分支限界法搜索过程可以表达为树状结构。6选2的特征选择问题(a)搜索树(b)搜索回溯示意图123234443A3454554555456566566656666nXX000i1i2i4i3i0X()a()bs=0s=1s=2s=3s=4分支限界法（B&B）树的每个节点表示一种特征组合，树的每一级各节点表示从其父节点的特征组合中去掉一个特征后的特征组合，其标号k表示去掉的特征是xk。由于每一级只舍弃一个特征，因此整个搜索树除根节点0级外，还需要n-d级，即全树有n-d级。例如，6个特征中选2个，整个搜索树有4级。第n-d级是叶节点，共有Cnd个叶节点。分支限界法（B&B）表示特征数目为l的特征集合。lX表示舍弃s个特征后余下的特征集合。sX表示当前节点的子节点数。sq表示集合s中元素的数目。sr表示第s级当前节点上用来作为下一级可舍弃特征的特征集合。s分支限界法（B&B）由于从根节点要经历n-d级才能到达叶节点，s级某节点后继的每一个子节点分别舍弃s中互不相同的一个特征，从而考虑在s+1级可以舍弃的特征方案数（即子节点数）qs时，必须使这一级舍弃了特征后的Xs+1还剩（n-d)-(s+1)个特征。除了从树的纵向上每一级舍弃一个特征，实际上从树的横向上，一个分支也轮换舍弃一个特征。因此后继子节点数qs=rs-（n-d-s-1）分支限界法（B&B）ss+1n-d(n-d)-(s+1)qsrs()(1)ssrqnds0rn(1)ssqrnds01qd分支限界法（B&B）06r06(401)3q0123456{,,,,,}xxxxxx123456{,,,,}xxxxx13456{,,,}xxxx1456{,,}xxx2456{,,}xxx256{,}xx分支限界法（B&B）06r06(401)3q0123456{,,,,,}xxxxxx123456{,,,,}xxxxx23456{,,,}xxxx2456{,,}xxx256{,}xx分支限界法（B&B）目标：找出叶节点Lk，使其对应的d个特征的判据J的值最大，即：注意到每个节点（包括非叶节点）都可以计算相应的J值。由于判据J值具有单调性，即：12121(,,,)(,,,,)dddJxxxJxxxx该不等式表明，任何节点的J值均不小于其任何后继节点（子节点）的J值。1()max[()]dnCkjjJLJL分支限界法（B&B）搜索顺序：从上至下、从右至左。四个步骤：1、向下搜索2、更新界值3、向上回溯4、停止回溯再向下搜索分支限界法（B&B）向下搜索：初始，置界值B=0从树的根节点沿最右边的一支自上而下搜索。对于一个节点，它的子树最右边的一支总是无分支的。此时可直接到达叶节点，计算该叶节点的J值，并更新界值B。分支限界法（B&B）向上回溯和停止回溯：回溯到有分支的那个节点则停止回溯转入向下搜索。例如回溯到qs-11的那个节点，则转入与当前节点左邻的s深度的那个节点，使该节点成为当前节点，按前面的方法沿它最右边的子树继续搜索。在搜索过程中先要判该节点的J值是否比B值大。若不大于B值，该节点以下的各子节点J值均不会比B大，故无需对该子树继续进行搜索。分支限界法（B&B）如果搜索到叶节点，且该叶节点代表的特征的可分性判据JB，则更新界值，即B=J；否则不更新界值。到达叶节点后，要向上回溯。重复上述过程，直到JB为止。而对应当前（最大）界值B的叶节点对应的d个特征组合就是所求的最优的选择。分支限界法（B&B）序列前向选择SFS（1）•从空集合开始搜索，不断选择新特征加入已有特征集合Yk，使得加入新特征x’之后的目标函数最大。•算法流程：•算法评价：一旦某特征被选入，就不能删除，即使由于后面加入的特征使它变得多余。')(xYJk序列前向选择SFS（2）顺序后向选择SBS•和前向算法类似。但初始特征集合是所有特征，每次从中剔除一个，使保留的特征组的J值最大。•算法流程：•和顺序前向算法相比，SBS计算是在高维空间进行，所以计算量比前向大。增L去R算法•增L去R选择算法(LRS,Plus-LMinus-RSelection)•算法描述：该算法有两种形式。•当LR，算法从空集开始，每轮先加入L个特征，然后从中去除R个特征，使得J(Y)最大。•当LR，算法从全集开始，每轮先去除R个特征，然后加入L个特征，使得J(Y)最大。•算法评价：增L去R选择算法结合了SFS与SBS算法的思想，是对SFS和SBS算法的改进。•缺点：在最优L和R值选择上缺乏理论指导。增L去R算法双向搜索算法•算法描述：使用序列前向选择(SFS)与序列后向选择(SBS)分别从两端开始搜索，两者搜索到一个相同的特征子集Y才停止搜索。•为了确保序列前向选择与序列后向选择会搜索到相同的子集，需要确保：(1)被SFS选中的特征SBS就不能去除(2)被SBS去除的特征SFS就不能选择•算法评价：BDS结合了SFS与SBS，其时间复杂度比SFS与SBS小，但是兼有SFS与SBS的缺点。双向搜索算法•算法流程：序列浮动选择算法•LRS算法中，L和R是固定不变的；顺序浮动选择方法中，L和R是可变的。•顺序浮动选择方法包括两种算法：顺序浮动向前选择（SFFS）算法和顺序浮动向后（SFBS）算法。•算法流程（SFFS）：序列浮动选择算法•SFBS算法是从全集开始的。•1、StartwiththefullsetY=X•2、Selecttheworstfeaturex-=argmax[J(Yk-x)](x属于Yk)Yk=Yk-x-;k=k+1;•3、Selectthebestfeaturex+=argmax[J(Yk+x)](x不属于Yk)•4、IfJ(-)J()th