当前位置:澳门新葡亰总站 > 澳门新葡亰手机版 > 分支界定算法及其在特征选择中的应用研究

分支界定算法及其在特征选择中的应用研究

作者: 澳门新葡亰总站|来源: http://www.2xinniang.com|栏目:澳门新葡亰手机版    

 

    文章关键词:

澳门新葡亰总站

,分支界定算法

  分支界定算法及其在特征选择中的应用研究_电子/电路_工程科技_专业资料。分支界定算法是目前为止惟一既能保证全局最优,又能避免穷尽搜索的算法.他自上而下进行搜索,同时具有回溯功能,可使所有可能的特征组合都被考虑到.对分支界定算法进行研究,并对其做了一些改进;最后对改进前后的算法在特征选择领域进行比较,选择效率有了明显的提高.

  ■重盈臣翟酉蛋 至昼重蔓;坌塞墨定蔓渣壁基垄堑延适量虫笪应旦盟窒 分支界定算法及其在特征选择中的应用研究 王思臣,于 潞,刘 水,唐金元 山东青岛 266041) (海军航空工程学院青岛分院 摘要:分支界定算法是目前为止惟一既能保证全局最优,又能避免穷尽搜索的算法。他自上而下进行搜索,同时具有 回溯功能,澳门新葡亰手机版可使所有可能的特征组合都被考虑到。对分支界定算法进行研究,并对其做了一些改进;最后对改进前后的算法 在特征选择领域进行比较,选择效率有了明显的提高。 关键词:分支界定算法;特征选择;特征集;最小决策树;局部预测 中图分类号:TP31 文献标识码:A 文章编号:1004—373X(2008)10—142—03 Study of Branch&Bound Algorithm and Application of Feature Selection WANG Sichen,YU Lu,LIU Shui,TANG Jinyuan (Qingdao Branch,Naval Aeronautical Engineering Institute,Qingdao,266041.China) Abstract.Branch&Bound Algorithm is the only method which searching.It searches can ensure best of all the vectors.and it tO top,SO can avoid endless vec— from top to bottom and has the function that from bottom it can include all of the feature are tors.The Branch&Bound Algorithm is studied in the paper。and it is improved。the two algorithms seclection,the efficiency of seclection is compared by the feature improved greatly. Keywords:branch&bound algorithm;feature selection;feature vector;minimum solution tree;partial prediction 随着科学技术的发展,信息获取技术的不断提高和生 存能力的提升,对于目标特征能够获得的数据量越来越 过程中自上而下(top—bottom)按照深度优先(depth— first)的次序动态生成的。以D一5,d一2为例,其中D为 总的特征维数,澳门新葡亰手机版d为预期选定的特征子集的维数。搜索树 的拓扑结构如图1所示。分支界定算法的搜索树总共有 大,维数越来越高,一方面可以使信息更充分,但在另一方 面数据中的冗余和无关部分也会相应的增多。特征选 择[1’21就是为了筛选出那些对于分类来说最相关的特征, 而去掉冗余和无关的特征。 分支界定算法口’3’43是一种行之有效的特征选择方法, 由于合理地组织搜索过程,使其有可能避免计算某些特征 组合,同时又能保证选择的特征子集是全局最优的。但是 如果原始特征集的维数与要选择出来的特征子集的维数 C龆个节点,其中有C出个度数为1的节点,有岛个叶子 节点数。 接近或者高很多,其效率就不够理想。基于此,本文对分 支界定算法做了一定的改进,经过实验验证,与改进前相 比其效率有明显的提高。 、 1分支界定算法的基本原理 分支界定算法针对的特征选择问题是这样定义的[“: 在原来的D个特征的集合中选择一个d个特征的子集, d<D,使得选取的特征子集在选定的评价准则下是最优 的。算法要求所采取的评价准则函数满足单调性,即如果 X;2 X。,则J(X,)≥J(X r)。 其中X代表一个特征子集,,(X)是所采取的评价函 n5} p,5}IS,4) 豫5} 仁4}{2,3}m 5} {L4} 扎3} “2} 图1从5维中选择2维的搜索树 该算法中用到的一些符号说明如下:总的特征维数为 D;预期选定的特征子集x。的维数为d。x为当前要展开 以扩展搜索树的节点;Num_features是X中的特征数目; 数。单调性保证了分支界定算法能在保证全局最优的前 提下大大减少搜索的复杂度。分支界定算法的搜索空间 是一棵树,称为搜索树口。(Search Tree)。他是在算法运行 X—q为节点X在搜索树中的子节点个数(在动态生成搜 索树中很重要);XD为所有特征组成的集合;X’是当前最 优节点;bound是当前最优节点X‘的评价函数值;.,(X) 收稿日期:2007—11—05 142 为评价函数;该算法的具体步骤如下口’5]: 万方数据

文章标签: 澳门新葡亰总站 ,分支界定算法

上一篇:0033算法笔记——分支限界法与单源最短路径问题

下一篇:浅谈分支限界算法

推荐文章

热门文章

随机文章

Tags标签