基于bab+算法的最优特征选择

基于bab+算法的最优特征选择

0特征选择方法在模式识别系统中，资源选择起着非常重要的作用，因为资源选择的质量对后续排序的影响起着非常重要的作用。由于在实际应用中,包括颜色、形状、纹理等特征的数量非常大,没有必要也不可能用所有这些特征进行分类,因此有必要对不同的特征组合进行评价,从而选出对分类最有效的一组特征。特征选择是从n个特征中选择d(n>d)个特征,使判决函数值J达到最大值。在原坐标系中依据某些规则直接选择特征的方法分为两大类:次优搜索法和最优搜索法。常用的次优搜索法有:单独最优法、顺序前进法(SFS)、顺序后退法(SBS)。单独最优法的基本思想是计算各特征单独使用时的判据值并以递减排序,选取前d个分类效果最好的特征。顺序前进法每次从未选入的特征中选择一个特征,使它与已选入的特征组合在一起时J值最大。顺序后退法是从全部特征开始每次剔除一个特征,所剔除的特征应使余下特征组合的J值最大。然而,所有的次优算法都不能保证所选择的特征对某一判决函数来说是最优的,因为最好的特征组合不一定包含最好的单个特征。最优特征的搜索方法是穷举法和分支定界法。穷举法是对所有的特征组合计算J值,选出使J最大的那一组特征作为最优特征。由于特征组合的数量随着特征个数的增加而迅速增长,因此在实际应用过程中使用穷举法是不现实的。1基于删除特征的筛选分支定界的搜索过程是通过搜索树来表示的。总的搜索过程是沿着树自上而下、从右到左进行搜索。包括以下几个部分:向下搜索、更新界值、向上回溯、停止回溯再向下搜索。分支定界算法使用的判决函数具有单调性。例如S1是S2的子集,则J(S1)<J(S2)。假如从原始特征集(1,2,3,4,5,6)中选出两个特征,搜索树如图1所示,由于每层删除一个特征,因此层数m=6-2=4。节点上的数字表明删除的特征。例如节点X表明删除特征(2,3),也就是剩下特征集(1,4,5,6)。开始时界值为0,从根节点开始沿最右边的一支自上而下搜索,到达叶节点时,计算J值,更新界值,令B=J,并记录此时剩余的特征;然后向上回溯。一旦遇到有分支的节点,则停止回溯向下搜索,如果该节点的J值小于界值,则向上回溯,否则向下一直搜索到叶节点。如果叶节点的J值大于界值,则更新界值令B=J,同时记下此时剩余的特征;否则向上回溯,一直到所有的节点搜索完毕或没有比当前界值更大的J值为止。由于树的每个节点代表一种特征组合,于是所有可能的组合都被考虑到。分支定界所采用的可分性判据具有单调性,因此如果某个节点的J值小于界值,那么它的后继节点可以不必搜索同时又不影响全局寻优。例如假设节点X的J值小于界值B,则X的子节点4,5,以及4,5的子节点都可以不必考虑。同时由于搜索是从结构简单的右边开始,所以这种选择算法效率很高。如图1所示,对于一个节点来说,它的最右边的子树总是1度节点(只含有一个子节点的节点叫1度节点)或0度节点(叶节点),由于可能的解节点只在这个子树的叶节点上,因此当对最右边的子树进行搜索时,可以不必每次去掉一个特征,而可以直接到达叶节点,此算法称为BAB+算法。剪切最右边1度节点后所得到的树,称为最小解树。图1的最小解树如下图所示。2改进的分支机构定界算法在图2中,假设节点X的J值小于当前界值,由于X是去除特征(2,3),或者说保留特征(1,4,5,6),在BAB和BAB+算法中,节点Z仍然要计算。然而,根据单调性可以知道节点Z根本不用考虑。由于节点X去除的特征集(2,3)是节点Z去除特征集(1,2,3)的子集,换句话说节点Z剩余的特征集(4,5,6)是节点X剩余特征集(1,4,5,6)的子集。因此节点Z的判据值J值必小于节点X的J值,而节点X的判据值J值小于当前界值,因此节点Z的J值也必定小于当前界值。在改进的分支定界算法中,定义了部分路径这一概念。部分路径是由节点个数小于层数m并且判据值J值小于界值B的节点组成的(例如路径(2,3))。一旦找到了部分路径,改进的分支定界算法就不必计算所有以部分路径为子集的路径,称这些路径为父路径(例如(1,2,3))。当在第L(L<m)层的节点N的判据值J值小于当前界值B(假如该节点在某一部分路径上),那么在改进的分支定界算法中,节点N的所有后继节点以及所有的父路径都可以不必分析,这样就可以节省很大的计算。3转移平台型ss-ls-qssn是原始特征的个数,d是所要选择的特征个数,s表示深度,anti＿Xs表示舍弃s个特征以后余下的特征,Ws表示可供第s级当前节点的下一级选择舍弃的特征集,rs表示这个集合中元素的个数,qs表示当前节点的子节点数,Stack存储待扩展的节点,Sub＿node(s)存储第s级子节点的个数。Full表示父路径,Partial表示部分路径,B表示界值。Qs表示第s级当前节点的qs个子节点所舍弃的特征。初始化:anti＿X0=W0,B=0,s=0,r0=n步骤1:用公式qs=rs-(n-d-s-1)计算qs。步骤2:判断当前路径是否是父路径,如果是,则转步骤13;否则进入步骤3。步骤3:判断当前路径是否是单分支节点,如果否,进入步骤4;如果是,则包括该节点所有的后继节点,进入步骤4。步骤4:计算J值,并按升序排列求出Qs=(x1s+1,x2s+1,…,xqss+1)。步骤5:把Qs中的特征按顺序放入Stack中最后一个非空元素的后面,从Ws中去掉Qs,并修改rs,同时记录下该层的子节点数。即步骤6:如果qs大于0,转步骤11。否则,Sub＿node(s+1)减1,如果Sub＿node(s+1)=0,转步骤7;否则,转步骤10。步骤7:该节点为单分支节点,向上回溯。即s=s-1;anti＿Xs=anti＿Xs+1+xqss+1。同时把Stack中的特征xqss+1去掉。如果s=-1,转步骤9;否则转步骤13。步骤9:如果Stack为空,退出。否则令s=1;把特征xqss+1从anti＿Xs中删掉,即anti＿Xs+1=anti＿Xs-xqss+1,转步骤1。步骤10:该节点有分支,把已经扩展过的节点放入anti＿Xs中,并把该节点从Stack中删掉。然后把最接近该节点的左节点从anti＿Xs中去掉并向下扩展,s=s+1;转步骤1。步骤11:如果当前J<B并且节点个数小于n-d,则把当前路径作为部分路径加入Partial中,转步骤13;如果J<B,但节点个数等于n-d,转步骤13;否则转步骤12。步骤12:把特征xqss+1从anti＿Xs中删掉。如果s+1=n-d,更新界值,B=J(Xn-d),把J(Xn-d)作为当前选择的最好特征组。转步骤13;否则s=s+1,转步骤1。步骤13:Ws=Ws+1+xqss+1;rs=rs+1+1;qs=0;转步骤6。4特征变量及判决函数为了验证改进的分支定界算法,选用大台芒、小台芒、红象牙、白象牙4芒果图像共128个样本,每个样本有12个特征,包括颜色、形状、面积、周长、长宽比等。判决函数J=|SW+SB|/|SW|=|ST|/|SW|,SW是总的类内离差矩阵,SB是总的类间离差矩阵,ST是总体离差矩阵。由图3可见,BAB+算法比BAB算法有一定程度的改进,而IBAB算法比BAB、BAB+算法更有效,而且随着选取特征个数的增加,有效性越来越明显。5改进分支机构定界算法分