您好、欢迎来到现金彩票网!
当前位置:ds视讯 > 分支限界搜索 >

改进的分支定界算法pdf

发布时间:2019-06-18 14:05 来源:未知 编辑:admin

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  软件2011年第32卷第10期 Software 国际IT传媒品牌 改进的分支定界算法木 孙树亮1 陈 忠1 刘政连卜2 (1.福建师范大学福清分校数计系,福建福清350300,2.伦敦大学皇家哈洛威学院资讯安全研究中心,伦敦埃格哈姆TW20OEX) 摘要:如何进行最优的特征选择是模式识别的研究重点之一。目前比较常用的最优特征选择方法是BAB和BAB+算法,然 而此算法搜索时间比较长。在此基础上详细地阐述改进的分支定界的原理以及算法,该算法的基本思想是通过剪切那些肯定不会 产生最优解的分支,同时引入了部分路径和父路径的概念,以达到决策树能够快速搜索到最优解的目的。实验结果证明了该算法的 有效性及优越性。 关键词:分支定界;搜索树;特征选择;部分路径 中图分类号:TP391.4 文献标识码:A DOI:10.3969/j.issn.1003—6970.2011.10.009 An branchandbound improved algorithm SUN Shu—lian91,CHENZhon91,LIUZheng-lianl2 and Branch Normal (1.DepartmentofMathematicsComputerScience,FuqingofFujianUniversity,Fuqing,350300,China; OEX,UK) 2.DepartmentofMathematics,RoyalHolloway,UniversityofLondon,Egham,Surrey,TW20 are toselect featuresisoneofthe research and used [Abstract]How priority optimal areas.Currently,BAB toselect ittakestoo touse and ofan branch optimalfeatures,arecommonlyapplied.But long convinently.Thentheoryalgorithmimproved in andboundare essenceofthis istosearchforan solutionasolutiontree.Partialrouteand explainedparticularly.The algorithm optimal introducedinthis solutiontreeis those brancheswhichwillnotcontainthe Fatherrouteare paper.The gotbycuttingunnecessary optimal solution.The resultsdemonstratetheeffectivenessofthenew experimental algorithm. andbound route words]branch tree;feature [Key algorithm;solutionselection;partial 0引言 决函数来说是最优的,因为最好的特征组合不一定包含最好的 单个特征”1。 在模式识别系统中,特征选择起着举足轻重的作用,因为 最优特征的搜索方法是穷举法和分支定界法。穷举法是 特征选择的好坏,对后面分类效果的影响起着非常重要的作 对所有的特征组合计算J值,选出使J最大的那一组特征作为 用。由于在实际应用中,包括颜色、形状、纹理等特征的数量非 最优特征。由于特征组合的数量随着特征个数的增加而迅速 常大,没有必要也不可能用所有这些特征进行分类,因此有必 增长,因此在实际应用过程中使用穷举法是不现实的”1。 要对不同的特征组合进行评价,从而选出对分类最有效的一组 特征‘“。 1分支定界算法(BAB) 特征选择是从n个特征中选择d(nd)个特征,使判决函 分支定界的搜索过程是通过搜索树来表示的。总的搜索 数值J达到最大值。在原坐标系中依据某些规则直接选择特征 过程是沿着树自上而下、从右到左进行搜索。包括以下几个部 的方法分为两大类:次优搜索法和最优搜索法。常用的次优搜 分:向下搜索、更新界值、向上回溯、停止回溯再向下搜索。分 索法有:单独最优法、顺序前进法(SFS)、顺序后退法(SBS)[21。 支定界算法使用的判决函数具有单调性。例如S。是S:的子集, 单独最优法的基本思想是计算各特征单独使用时的判据值并 则J(S,)J(S:)。 以递减排序,选取前d个分类效果最好的特征。顺序前进法每 假如从原始特征集(1,2,3,4,5,6)中选出两个特征,搜索 次从未选入的特征中选择一个特征,使它与已选入的特征组合 树如图l所示,由于每层删除一个特征,因此层数m=6-2 在一起时J值最大。顺序后退法是从全部特征开始每次剔除一 =4。节点上的数字表明删除的特征。例如节点X表明删除特 个特征,所剔除的特征应使余下特征组合的J值最大。 征(2,3),也就是剩下特征集(1,4,5,6)。 然而,所有的次优算法都不能保证所选择的特征对某一判 1003 基金项目:青年教师启动基金KY201 连(1973一),男,博士,讲师,主要研究方向是密码与安全学。 · 32 软件 (您的文章得到院士的关注) 孙树亮等:改进的分支定界算法 m=0 算法中,节点Z仍然要计算。然而,根据单调性可以知道节 m=l 点Z根本不用考虑。由于节点X去除的特征集(2,3)是节点 Z去除特征集(1,2,3)的子集,换句话说节点Z剩余的特征集 m=2 的判据值J值必小于节点X的J值,而节点X的判据值J值小 m=3 于当前界值,因此节点Z的J值也必定小于当前界值。 在改进的分支定界算法中,定义了部分路径这一概念”1。 m--4 4 5 6 5 6 6 5 6 6 6 5 6 6 6 6 部分路径是由节点个数小于层数m并且判据值J值小于界值 图1分支定界搜索树(n=6,d=2,m=4) B的节点组成的(例如路径(2,3))。一旦找到了部分路径,改 branchandboundsolutiontree Fig.i.the 进的分支定界算法就不必计算所有以部分路径为子集的路径, 开始时界值为0,从根节点开始沿最右边的一支自上而下 搜索,到达叶节点时,计算J值,更新界值,令B=J,并记录此时 节点N的判据值J值小于当前界值B(假如该节点在某一部 剩余的特征,然后向上回溯。一旦遇到有分支的节点,则停止 分路径上),那么在改进的分支定界算法中,节点N的所有后继 回溯向下搜索,如果该节点的J值小于界值,则向上回溯,否则 节点以及所有的父路径都可以不必分析,这样就可以节省很大 向下一直搜索到叶节点。如果叶节点的J值大于界值,则更新 的计算。 界值令B=J,同时记下此时剩余的特征;否则向上回溯,一直到 3改进的分支定界算法 所有的节点搜索完毕或没有比当前界值更大的J值为止。 由于树的每个节点代表一种特征组合,于是所有可能的组 n是原始特征的个数,d是所要选择的特征个数,S表示深 合都被考虑到。分支定界所采用的可分性判据具有单调性,因 度,anti—X。表示舍弃S个特征以后余下的特征,W。表示可供 此如果某个节点的J值小于界值,那么它的后继节点可以不必 第S级当前节点的下一级选择舍弃的特征集,r。表示这个集合 搜索同时又不影响全局寻优。例如假设节点X的J值小于界 中元素的个数,吼表示当前节点的子节点数,Stack存储待扩 值B,则X的子节点4,5,以及4,5的子节点都可以不必考虑。 同时由于搜索是从结构简单的右边开始,所以这种选择算法效 率很高。 前节点的q个子节点所舍弃的特征。 如图1所示,对于一个节点来说,它的最右边的子树总是1 初始化:antLX0-Wo,B=0,s=0,rO=n S 度节点(只含有一个子节点的节点叫1度节点)或0度节点(叶 步骤1:用公式吼=k一(n…d1)计算吼。 节点),由于可能的解节点只在这个子树的叶节点上,因此当对最 步骤2:判断当前路径是否是父路径,如果是,则转步骤13; 右边的子树进行搜索时,可以不必每次去掉一个特征,而可以直 否则进入步骤3。 接到达叶节点,此算法称为BAB+算法”’。剪切最右边1度节点 步骤3:判断当前路径是否是单分支节点,如果否,进入步 后所得到的树,称为最小解树。图l的最小解树如下图所示。 骤4;如果是,则包括该节点所有的后继节点,进入步骤4。 步骤4:计算J值,并按升序排列 m=0 y(xs—xls+1)≤J(Xs一.《“)≤…J(Xs一《s“) m=l x∥∈形,『_1,2,…,r。 求出Qs=(xl州,x2川,…,xqml)。 m=2 步骤5:把Q中的特征按顺序放入Stack中最后一个非空 元素的后面,从Ws中去掉Q,并修改k,同时记录下该层的子 m=3 节点数。即 彬+1=彬一Q。o+12匕一吼 Sub_node(s+1)=q。 m=4 4 5 6 5 6 5 6 图2最小搜索树 minimalsolutiontree 步骤7:该节点为单分支节点,向上回溯。即J=s一1;anti— Fig.2.the 2改进的分支定界基本思想(IBAB) 果S--1,转步骤9;否则转步骤13。 在图2中,假设节点X的J值小于当前界值,由于X是 软件 (您的文章得到院士的关注) 孙树亮等:改进的分支定界算法 从anti—X。中删掉,即anti—X。+l=anti—X。一xqs。+l,转步骤l。 步骤10:该节点有分支,把已经扩展过的节点放入anti—X。 中,并把该节点从Stack中删掉。然后把最接近该节点的左节 点从anti—X。中去掉并向下扩展,s=s+1;转步骤1。 步骤1l:如果当前JB并且节点个数小于n-d,则把当前 路径作为部分路径加入Partial中,转步骤13;如果JB,但节 点个数等于n-d,转步骤13;否则转步骤12。 步骤12:把特征XqSs+l从anti_X。中删掉。如果s+l= n—d,更新界值,B=J(X。一。),把J(X。一。)作为当前选择的最好特 征组。转步骤13;否则s=s+1,转步骤l。 2rs+l+1;q。=0;转步骤6。 选择特征的数量 步骤13:W。=W。+l+xqSs+1;rs 图3选择特征的数量与计算J次数关系 4实验过程 thenumberoffeatureandthe relationbetween Fig.3.the 为了验证改进的分支定界算法,选用大台芒、小台芒、红 amountof J counting 为了验证该算法的有效性,把它与BAB、BAB+算法做了比较。 象牙、白象牙4芒果图像共128个样本怕1,每个样本有12个 特征,包括颜色、形状、面积、周长、长宽比等。判决函数J= 实验结果表明该算法明显优于BAB和BAB+算法。 Isw+s。I/ISwI=IsTl/lswl,sw是总的类内离差矩阵, 参考文献 S。是总的类间离差矩阵,S,是总体离差矩阵。 [I]边肇祺,等.模式识别[M】.北京:清华大学出版社,1988. 由图3可见,BAB+算法比BAB算法有一定程度的改进, [2]孙即祥,等.现代模式识别[M】.长沙:国防科技大学出版社, 而IBAB算法比BAB、BAB+算法更有效,而且随着选取特征 2002. 个数的增加,有效性越来越明显。 [3]JAIN,A.,DUIN,R.,MAO,J.Pattern Trans.Statistical Intell[J].IEEE pattern 5结论 4-37. O.DUDAPETEREHartDavidG.Stock.模 [4】RICHARD 分类的关键问题之一就是特征的选择,要使选择的特征既 式分类[M】.李宏东,姚天翔等,译.北京:机械工业出版社,2003. KOTHARI.FeatureSubsetSelection 保留了对分类有用的信息,又降低了特征空间的维数。本文提 [5]MINGDONG,RAVI a NewDefinitionof 出了用于最优特征选择的改进分支定界算法。该算法通过剪切 Using RecognitionLetters,2003,24:1215-1225. 那些肯定不会产生最优解的路径,从而加快对最优解的搜索。 [6】孙树亮.基于计算机视觉的芒果分类fD].广西大学,2006. 上接第31页 由表3表4可知,相同的网络准确率,相同的训练时间,其 能最差。针对离散问题,相同的预测准确率,几种算法的训练 他三种算法均好于传统BP算法,共轭梯度算法优于RPROP 时间明显高于解决连续问题的训练时间。由实验结果可推断, 与加动量的BP算法。由实验结果可知,对于离散问题,只要训 若能穷举样本空间且足够长的训练次数,神经网络的几种算法 练样本穷举其样本空间,训练次数足够多,训练后的网络的预 均可使网络的准确率几乎接近100%;若实际问题的样本空间 测正确率可达到100%。若实际问题的样本空间的全集很大时, 的全集很大,训练样本的样本容量只为其中的很小的部分,则 训练样本的样本容量只为其中的很小的部分,则无论训练次数 无论训练次数如何增多,训练结果都会存在很大误差。 如何增多,训练结果都会存在很大误差。 参考文献 the 3结论 【1】IGELC,HUSKENM.ImprovingRpropLearning oftheSecondICSC Algorithm[J].Proceedings 本文总结了几种神经网络训练算法的原理及差异,并将其 onNeural Symposium Computation,2000,NC2000:115—121 分别应用在连续型和离散型的数学问题上,通过实验结果并结 [2]HANKINS.神经网络原理(2版)[M].叶世伟.机械工业出版社, 合不同算法的特点,分析其在解决各问题上的优劣。并给出结 2004 [3】木合塔尔等.前向神经网络的共轭梯度学习算法[D].新疆:新疆 论:共轭梯度算法在解决连续型问题和离散型数学问题时优于 大学,2007 其他算法,RPROP算法在解决连续问题上略好于加动量项的[4】陈明忠.BP神经网络训练算法的分析与比较[D].南京:南京铁道 BP算法,在解决离散问题上两者基本持平,传统的BP算法性 职业技术学院,2010

  ·手术切除与射频消融治疗直径3~5 cm 的原发性肝癌疗效 meta 分析.pdf

  ·扩大额颞颧弓入路暴露Willis环及其主要分支的应用显微解剖学研究.pdf

  ·改革的初等多值函数单值分支理论——基于教学型高等院校数学与应用数学专业的教学.pdf

  ·政务微博与传统媒体微博在灾难传播中的框架表达比较研究--基于雅安地震后政务微博和传统媒体微博1230条微博文本的分析.pdf

  ·政府R&D资助对企业研发投入的影响——基于Meta分析的综述.pdf

  ·政府工具研究与政府管理方式改进--论作为公共管理学新分支的政府工具研究的兴起、主题和意义.pdf

http://gamesbaby.net/fenzhixianjiesousuo/492.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有