累积适应度遗传算法在SVM多分类决策树中的优化研究

累积适应度遗传算法在SVM多分类决策树中的优化研究

余新华

【摘 要】本文研究的内容是通过改变适应度的选取方式，通过累计各个接节点的适应度，利用加权计算求取适应度，在结合SVM决策树组成CFGA-SVM，通过这种算法计算出来的结果相比较GA-SVM取得了很大的进步，并且这种方法适应的样本量度更大，在发展遗传计算求解的过程中，未来还会具有很好的发展.

【期刊名称】绵阳师范学院学报 【年(卷),期】2018(037)008 【总页数】5

【关键词】累积适应度；多分类决策树；SVM；遗传算法

0 引言

为了方便解决小样本、高维度模式识别问题，经过众多学者的潜心研究，终于在1995年由Cortes 和Vapnik两位学提出了支持向量机，即是SVM.其主要在解决一些非线性或者是小样本等问题上具有很大的作用.主要优点是计算出来的结果比较准确，并且中间操作过程比较简便.目前SVM是一个二值分类器，对于研究的大多数问题是不适用的，所以将SVM推广到求解多数值类型的问题中，是未来研究学者重点的研究方向.现在研究的有关多值分类器中都是含有多个SVM，通过增加分类器的数量起到解决多数值问题.但是这种方法存在很大的问题，因为每一个分类器只能处理二值，如果想让它处理多值就需要采用大量的SVM分类器.目前比较常见的SVM多分类器有：one-againstall?one-against-rest和decision-tree-based SVM.这几种分类器其实都有相似之处，

其中one-againstall和one-against-rest的特点是工作时间特别长，因为它需要参照整个样本的基因组成结构.另一种就是决策树SVM，这种分类器的工作效率快，它的工作方式和前两种存在不同，它可以只考虑有用的二值分类器，节省了大量的时间，但是在计算的过程中容易出现错误，现在解决的办法是通过计算寻找出来整个分类器中最优答案，确保计算的准确性，提高计算的精度，减少外界对于这一二叉树工作时的影响.另外通过加入遗传算法对于整个过程的求解有很大的帮助，可以提高计算的准确度，但是对于计算还是有一些其他方面的影响.

本文利用的计算方法是遗传学中的计算方法，为了方便问题的求解还对其中的算法进行了优化，总结出另外一个按照累计适应度遗传算法为中心的算法，即与SVM联合形成的多分类算法，简称为CFGA-SVM.经实践检验， DT-SVM、one-against-all、one-against-rest等之前的算法均不及该方法(CFGA-SVM)的精确度及实用性.

1 基于有遗传算法的SVM多分类算法

1.1 支持向量机理论

SVM计算方法提出是为了用来计算原来二值分类等问题的，这种方法用两个数字表示不同的类别，假设这个两个类别的最大间距为M，具体的计算方法按照下列计算方法： s.t.yi[(w·xi )+b]≥1

其中：超平面的法向量即为w；训练的样本即为xi；选择样本的种类即为yi，i=1,2,3,…,n.且通过采用线性约束，确保其中没有另外的样本点给计算产生误差. 1.2 遗传算法理论的数据分析

本文主要是通过对生活中真实发生的问题作为遗传算法的数据来源，计算种群通过排除其他方面的影响真正的适应生活的数值，通过计算这一数值寻找出最适合生活的种群，数值越大说明适应生活的能力也就越强.这一算法还是来自于达尔文进化理论中对于各种种群的模拟实验得到的数据，然后通过他们的调整和面对生活中各方面的影响，各个种群分别的应对情况，求解出生存能力最强的种群.

达尔文进化理论中通过将SVM引入到遗传计算中，可以得到结果准确度最高的决策树.因为在计算的过程中，每一次选取决策树都是选取同等种类中基因最好的决策树，所以对于后代的影响更好，通过比较选取最优基因，进行下一步的计算，每一个过程中选取决策树都是依靠这种算法，所以在最后可以得到最优的结果.

1.3 基于遗传算法的SVM决策树构造算法

通过将SVM决策树和遗传算法结合在一起，对于最优结果的求解有很大的帮助，但是在求解的过程中不同的研究人员采取的方法有很大差别.对于决策树是经过一步步的杂交变异或者是正常遗传等多种情况下的综合考虑，每次选取的决策树都是整个过程中的最优基因，所以计算出来的结果一定是这一部分中最优解，但是考虑整个遗传的过程中，不一定是所有遗传中的最优解.不同学者计算过程中运用的算法设计的适应数值是不同的，因此就会产生很多种其他的算法，本文在研究的过程中采用最大类间间隔.对于遗传算法这一问题的重新设计就是要不仅考虑每次遗传过程中都要是最优结构，还应该将上一个节点也要考虑在内.之前的研究都是考虑当代结构的情况，通过对比选取当代最好的结构作为最优解，这种计算方法的问题在于计算出来的结果只能是说明当代是最好的，