基于遗传算法的svm决策树生成算法

基于遗传算法的svm决策树生成算法

1基于遗传算法的svm决策树多分类方法支持向量机（svm）用于处理多类别分类是svm研究的重点问题之一。目前提出的svm分类方法可分为两种类型：一次性求解法和分解重建法。一次性解算法由韦恩等人在1998年首次提出。在所有训练样本中，解决了一个大型二次规划问题，并分别从所有样本中分开了评论。从那以后，李昆仑等人引入了模糊的成员函数，这提高了对评论结果的影响，并减少了噪声对排序结果的影响。然而，总的来说，由于该方法变量多、计算复杂性高，尤其是在较高的类别数量上，其训练速度低，分类精度低，其实用性差。分解重建方法是将多类分类问题转换为三种分类问题，采用一定的策略将两个类的分类结合起来，实现多分类的方法。该方法的优点是分类精度，但缺点是在k分类问题上，需要进行k（k-1）/2的基本svm，并且分类需要按照投票方法的组合策略进行多次分类。评分的优点是分类精度，但缺点是在k分类问题上，有必要通过k（k-1）/2的基本svm进行分类，并使用基于投票方法的组合策略对其进行多次分类。该方法的优点是分类精度，但缺点是在k分类问题上，有必要通过k（k-1）/2的基本svm进行分类。分类需要按照所有训练的svm进行。分类是复杂的，分类效率低。使用“最小”方法来训练所有svm。该方法所需的基本svm比1-a-1的方法要好得多。1-a-r使用“一对”的方法来训练所有svm，并使用“最大输出”法对其进行分类。当样本数较大时，训练速度非常缓慢。同时，该方法的分类也需要遵守所有k个svm，效率也不高。t-svm和dag-svm采用决策树的联合分类结构。在每个决策节点中，t-svm采用“一对”训练方法，而dag-svm采用“单方面”训练方法。由于引入决策树，所培基本svm显著减少，分类时不需要所有训练的svm，培训和分类的效率显著提高。然而，这两种多分类方法。本文提出一种基于遗传算法的SVM决策树多分类方法,在决策树的每个决策节点利用遗传算法进行两分类决策优化,最终自动生成最优(或近优)决策树.由于GA优化的引入,使得决策树的结构具有自适应性,在保证训练和分类效率的同时,使分类性能达到最优(或近优).理论分析和实验结果表明,新方法比传统的DT-SVM、DAG-SVM方法有更高的分类精度,比经典的1-a-1、1-a-r有更高的训练和分类效率.2最优分类面求解为了使本文具有自包含性,本节对支持向量机(SVM)的相关理论进行简要介绍.SVM是从线性可分的二分类问题发展而来的,其基本思想是寻找两类样本的最优分类面,使得两类样本的分类间隔(margin)最大.以图1所示为例:图中,实心点和空心点分别代表两类样本,H为分类线,H1和H2分别为各类中离分类线最近的样本且平行于分类线的直线,它们之间的距离叫做分类间隔(margin).所谓最优分类线就是要求分类线不但能将两类正确分开,而且使分类间隔最大.不失一般性,设训练样本(xi,yi),i=1,2,…,l,x∈Rn,y∈{+1,-1},l为样本数,n为输入维数.在线性可分的情况下将两类样本完全分开的超平面为:w·x+b=0(1)使分类间隔最大的超平面即为最优分类面,为此,需要求解二次规划问题:min|w|2/2s.tyi(w⋅xj+b)-1≥0,i=1,2,⋯,l(2)min|w|2/2s.tyi(w⋅xj+b)−1≥0,i=1,2,⋯,l(2)当训练样本集线性不可分时,需引入非负松弛变量ζi,i=1,2,…,l,求解最优分类面问题为:min|w|2/2+Cmin|w|2/2+Cl∑i=1∑i=1lζis.tyi(w·xj+b)≥1-ζi,ζi≥0,i=1,2,…,l(3)式中,C为惩罚参数;C越大表示对错误分类的惩罚越大.通过Lagrange乘子法求解上述优化问题,得最优决策函数:f(x)=sgn[l∑i=1yiαi(x⋅xi)+b](4)其中α为Lagrange系数.在对输入测试样本x进行测试时,由式(4)确定x的所属类别.根据K-T条件,上述优化问题的解必须满足:αi(yi(ω·x+b)-1)=0(5)因此,对于多数样本αi将为零,取值不为零的α*0对应的样本即为支撑向量,他们通常只是全体样本中的很少一部分.这样,仅需要少量支撑向量即可完成正确的样本分类.当样本集非线性时,可把样本x映射到某个高维空间H,并在H中使用线性分类器.根据Mercer条件,采用不同内积函数K(xi·xj)就可实现非线性的线性分类.K(xi·xj)称为核函数,此时相应的最优决策函数变为:f(x)=sgn[l∑i=1yiαiΚ(x⋅xi)+b](6)3组合多分类策略的关键根据分解重构法思想,一个复杂的多类问题可以划分为多个两类问题来解决.而采取决策树的组合分类策略已被证明是一种高效的多分类组合方法.但不同的决策树结构会对分类精度产生不同的影响,而且这种影响有可能产生“误差积累”现象.理论上讲,对K类问题,所有可能构造的严格二叉树的数目为:Nk=Κ-1∏i=1(2·i-1)(7)其中K≥3.因此,如何构造具有最优(或近优)分类性能的二叉决策树就成为SVM决策树组合多分类策略的关键.传统的DT-SVM方法和DAG-SVM方法对此均没有进行深入研究.本节采用遗传算法,以类间分类间隔(margin)最大为准则,在每个决策节点将多类训练样本划分为两类进行训练,使两个子类间的可分性尽可能强,以构造合理的树结构,最终生成最优(或近优)的决策树.3.1遗传计算方法的设计3.1.1类别编码的编码参数编码是实现GA的关键.为了提高搜索效率,本文采用实值编码的策略来实现原始训练样本集类别的编码.决策树根节点的染色体的编码为:{1,2,…,K},其中K≥3为原始训练样本集的类别总数,染色体中每个基因对应的是原始训练样本集的类别编号;对于根节点以下的子节点,根据其父节点的划分结果,剔除父节点染色体中本节点不包含的类别对应的基因,形成新的染色体.3.1.2初始种群的生成采用实值编码,解空间与染色体空间重合.考虑到种群数目过大不仅增加GA运算时间,而且会使种群形态过于分散,从而使算法收敛困难,所以我们选择种群规模的大小为训练样本的30%.在解空间中随机产生初始种群,并使其均匀分布于解空间.3.1.3svm分类算法分类间隔我们的目标是在每个决策节点将原始多类训练样本集划分为两类,并且使分类间隔最大.因此选择SVM分类算法的分类间隔作为GA适应度函数.根据SVM理论,两类样本的最大分类间隔为:margin=2/‖w*‖(8)其中:w*=n∑i=1α*iyixi(9)3.1.4种群遗传本构模型遗传操作是实现寻优的关键,为了使染色体完整地包含当前决策节点训练样本所属的类别种类,又避免染色体基因出现重复(该情况会使划分出现交叠),本文只采用了选择操作算子和变异操作算子.(1)选择.选择算子的作用是从上一代的遗传结果中以一定概率繁殖适应度较大的个体进入下一代的遗传操作.若个体ai的适应度函数为fit(ai),种群规模为pop-size,则选中ai为下一代个体的概率为:P(ai)=pop-size×fit(ai)/pop-size∑j=1fit(aj)(10)显然适应度高的个体,繁殖的下一代数目较多;而适应度较小的个体,繁殖的数目较小,甚至被淘汰.(2)变异.为了在遗传操作初期取得较大的变异算子以维持种群的多样性,防止出现早熟现象;在算法已接近最优解邻域时,减小变异算子,确保其局部搜索能力,本文采用如下自适应变异概率:Ρm=exp(-1.5×0.5t)/pop-size×√L(11)其中:t是进化代数,L是染色体长度.此外,为了防止同一条染色体中相同基因重复出现,染色体中某一基因座上的基因发生变异时,变异后的基因编码对应的基因座上的基因应相应地变换为变异基因座上的原基因编码.例如,8分类问题的某一原始染色体编码如图2(a)所示,若第二基因座上的基因发生变异,变异后的基因编码为7,则最终变异操作得到的新染色体如图2(b)所示:3.2所属类别划分基于遗传算法的SVM决策树生成算法可描述如下:步骤1:将全部训练样本集所属类别按实值编码策略进行编码,并在根节点调用GA将原始训练样本所属类别划分为两类.步骤2:判断各子节点是否只包含一类样本,若是转步骤4,反之转步骤3.步骤3:对包含两类以上样本的子节点,剔除其父节点染色体中本子节点不包含的类别对应的基因,形成新的染色体,并调用GA将本节点的样本所属类别划分为两类.转步骤2.步骤4:结束循环,生成最优(或近优)决策树.需要说明的是,GA是一种启发式搜索算法,因此并不能保证任何情况下生成的决策树一定是最优的,有可能是近优的.4算法的复杂和执行时间的分析4.1svm分类判断SVM多分类分解重构法的基本SVM训练方法和组合策略决定了分类器的训练及分类复杂程度.对于K分类问题,本文提出的方法与常见的SVM多分类分解重构法训练及分类复杂度的比较见表1.由表1可见,对于基本SVM的训练,1-a-1与DAG采用“一对一”的方法,需要训练的SVM最多,且随类别数K的增加成平方指数增加;1-a-r采用“一对其余”的方法,训练的复杂程度大大减少;DT-SVM和GADT-SVM由于采用了树结构,训练的复杂程度最小.在分类判断时,1-a-1、1-a-r都需要遍历所有训练的SVM,效率很低;DAG采用了有向无环图结构,分类所需的平均SVM个数有所减少;DT-SVM采用的是固定结构的二叉树策略,分类所需的平均SVM个数进一步减少;本文提出的GADT-SVM采用的决策树由GA根据具体情况自适应生成,其分类判断的最坏情况等于DT-SVM所需的SVM数,具有最高的分类效率.4.2dt-svm方法的分类测试支持向量机的训练时间与样本集的大小成超线性关系,T=cka,其中c为比例常数,a为一常数,k为训练样本集大小.对于基于分解重构法的支持向量机学习算法来说,a≈2,因此,SVM的训练时间取决于参与训练的样本的数量多少.设模式类别数为K≥3,每类样本数相等.对于标准的1-a-r方法,需训练K个SVM,总的训练时间为:T1-a-r=cKka.对于DT-SVM,虽然也采用“一对其余”的模糊类方法,但随着树的高度的增加,参与训练的样本数在逐级减少.设决策树根节点高度为0,则高度为i(i=0,1,2,…,K-2)的决策点训练样本数为:k(K-i)/K,DT-SVM总的训练时间为:TDT-SVM=Κ-2∑i=0c[k(K-i)/K]a.对于1-a-1和DAG方法,需要训练K(K-2)个SVM,每个SVM的训练样本数为2k/K,总的训练时间为Τ1-a-1=ΤDAG=cΚ(Κ-1)2(2kΚ)a≈2a-1cΚ2-aka.当a≈2时,这两种方法的训练时间与类别数几乎无关.对于本文提出的GADT-SVM方法,训练时间由两部分组成,一是GA在每个决策节点对树结构进行优化的时间;二是优化结束后各个决策节点基本SVM的训练时间.对优化结束后各决策节点基本SVM训练时间,其最坏情况的树结构与DT-SVM决策树的结构相同,即每次决策分类,仅将训练样本中的一类与其余类划分开来;额外的时间开销来自GA对树结构的自动优化.但对具体的分类问题,决策树结构的优化过程通常是离线进行,并且一旦确定,对该问题就不再改变.因此,以增加离线优化时间为代价换取SVM决策树在线的最优(或近优)分类性能是可行的.至于以上方法的分类测试时间,由分类所需遍历SVM数目和每个SVM支持向量(SV)的数量共同决定,这一方面与组合分类策略有关,一方面与SVM的参数优化有关,本文不进行深入研究.一般来说,分类所需遍历SVM的平均个数越少,每个SVM的SV个数越少,分类时间越短;反之则越长.5dag-svm分类方法的对比A,B,C}、4分类{A,B,C,D}、6分类{B,C,D,E,F,G},7分类{C,D,E,G,H,I,J}和10分类{A,B,C,D,E,F,G,H,I,J}5种情况进行实验.对于每类,在数据集中任取40个样本作训练样本集,100个样本为测试样本集.为了便于比较,所有的基本SVM均采用径向基核函数:K(x,xi)=exp{-|x-xi|2/(2·σ2)},σ=5;惩罚参数取C=2.根据前面讨论的算法,GADT-SVM对5种多分类情况生成的决策树如图3(a)～(e)所示.对DT-SVM,在每个决策节点随机将训练样本分成两类进行训练;对DAG-SVM,在每个决策节点随机取两类进行训练表.表2列出了5种方法分别在5种分类情况下各SVM的平均支持向量数目(#SV)和测试所需遍历SVM的平均数目(#SVM):5种方法在不同分类情况下的分类精度、基本SVM训练时间、平均分类时间如图4所示:由图4(a)可见,随着分类类别数的增加,所有方法的分类精度都成下降趋势,其中本文方法的精度在3分类、4分类、6分类时高于经典的1-a-r和1-a-1方法的精度,在7分类、10分类时与其相当,而其训练时间和分类时间则分别比1-a-r和1-a-1大大减少(见图4(b)、(c));在所有5种分类情况下,经本文方法优化后的SVM决策树分类精度均高于未经优化的DT-SVM和DAG-SVM方法的分类精度.在图4(b)中,1-a-r由于每次训练都需要所有的样本参与,故其训练时间最长;1-a-1/DAG-SVM虽训练复杂,但每次训练只需要两类样本参与,其训练时间反而最短,且与类别的变化关