基于支持向量机的分类预测算法研究


网络技术计算机与网络创新生活基于支持向量机的分类预测算法研究陈凤娟(辽宁对外经贸学院信息技术系辽宁大连116052)【摘要】分类预测是数据挖掘,机器学习和模式识别等很多领域共同关注的问题,已经存在了许多有效的分类算法,但这些算法还不能解决所有的问题.支持向量机作为一种新的分类预测工具,能根据有限样本信息在模型的复杂性和学习能力间取得平衡,并能获得更好的泛化能力.sM0算法是支持向量机中使用最多的算法,它体现了支持向量机的优点,同时也能处理大规模训练集.【关键词】分类支持向量机序列最小优化算法中图分类号:TPl8文献标识码:A文章编号:1008一1739(2009)19—64—4ResearchClassificationAlgorithmBasedonSupportVectorMachinecHENFeng-ju狮pepar廿11em“ir而聊撕0ntechn0109y,妇。血gur曲ersit)rofIm哪血oIIalB璐iIl麟越dEconornic,Dali=a11ko衄培116052,ChiIla)Ah咖铽:t:C蛐cadonisacm姗onc∞cemillrrmlya托勰,mchasdatamiIling,nncllillekarniIlg,patcerIlr:eco鲥don,etc.111erellaVebe∞蚴ny妊c曲ecla始cadonalgo删哪.HoweV%dIesea190rid哪则c姐not曲eallmeproblerns.supp叫VectorMachineaclliev懿abalancebetweencomple】dtyofdlemodelandabili哆tole栅accordillgt0Iirlites蛐pleillfom=ladon.Anditcan萨cbe仕ergeneral曲d叩abili呵.sMo甜gorid姗ismostco咖only郴ed如ridlnliIlsVM.Itembodi岱dleadv孤tag嚣ofsVM.Itis童lsocapabkofhandlinglarge~scale缸aillingsetatmes棚e胁e.Keywords:classmcadon;SupportVectorMachitle;SMo1引言分类不仅是数据挖掘领域的一个重要的研究内容,同时也是机器学习的一个重要课题。进行分类的目的是为了对其他类别未知的数据进行预测。从而分开类别。分类和回归是两类最主要的预测问题。预测离散值和标号值称为分类,而预测连续值或有序值称为回归。分类预测有很广泛的应用,它能反映同类事物间的共同性质。也能反映不同事物之间的差异特征。由于分类预测的重要性。很多学者对其进行了深入的研究。也取得了很好的成绩,出现了很多成功的分类算法。这些算法在很多领域都得到了成功的应用,例如医学诊断、贷款风险评估、语音识别和人脸识别等。但是这些经典的分类方法都定稿日期:2009一08—26辽宁对外经贸学院校级课题(09x儿xQN001)只能解决某些分类问题,同时当数据量非常大的时侯,会出现效率明显下降等各种问题。针对已有的经典分类算法存在的问题,又有很多新的分类方法被提出。支持向量机在这些新的分类方法中显现出了很好的性能。支持向量机是由v.Ⅵlpnil【提出的一种基于统计学习理论的新工具,它通过有限的样本信息在分类模型的复杂性和学习能力之间寻求最好的平衡点,从而获得更好的泛化能力11l。支持向量机还能很好地与其他已有的分类方法进行结合,解决许多难题。如过学习问题等。本文首先简单介绍已有的典型的分类算法。然后分析支持向量机的基本原理,最后分析支持向量机的分类算法及其改进算法。2经典分类预测方法分类是数据挖掘、机器学习、模式识别等很多领域广泛关《计算机与网络》2009年第19期 万方数据 计算机与网络创新生活注的问题.它根据训练数据集中训练样本的特点构造一个分类器(也叫分类函数、分类模型),通过该分类器对数据库中类别标号未知的数据进行预测,把这些数据分类到相应的类别中。目前,已经研究出的经典分类方法主要包括:决策树方法、神经网络方法、贝叶斯分类、基于关联规则的方法、遗传算法等髑。2.1决策树方法决策树是一种以实例为基础的归纳学习算法,在它的树型结构中.每个结点表示对一个属性值的测试,其分支表示测试的结果,而树的叶结点表示类别,从决策树的根结点到叶结点的一条路径对应着一条合取规则,整个决策树对应着一组析取表达式规则。决策树一般用贪心算法来构造,用自上而下、分而治之的递归算法来完成构造过程。在决策树构造中最关键的是结点的属性选择问题。即在决策树的内部结点进行属性值的比较,并根据不同的属性值判断如何从该结点向下分支。决策树算法中最著名的是ID3和“.5两个算法。ID3算法用信息论的知识作为基础,来计算具有最大信息增益的属性字段。然后建立一个决策树结点.再根据该属性字段的不同取值来建立分支。该方法描述简单且分类速度快,但是它只对较小的数据集有效,而且抗噪性差。C4.5算法在继承ID3算法的优点的基础上对其进行了改进,它用信息增益率代替信息增益来选择属性。同时在树的构造过程中对树进行剪枝避免了过拟合问题。它还能够处理属性值缺少的样本,提高了抗噪能力。C4.5算法产生的分类规则仍然易于理解,准确率较高,但是在构造树的过程中,对数据集进行多次的顺序扫描和排序,导致算法的效率降低,而且c4-5仍然不适合大训练集数据。为了提高算法的有效性和可伸缩性,又出现了suQ、sPRJNT、RainFor瞰、BoAT等算法。这些算法j走展了决策树分类方法.使之能够处理大规模数据集。2.2人工神经网络人工神经网络是多个神经元按一定规则连接构成的网络系统,通过模拟人类大脑的结构和功能完成对外部输入信息的动态响应,并将获取的知识存储在网络单元之间的连接权系数中,使网络具有很强的容镨性和鲁棒性。反向传播算法(BackP∞pag瓶on,BP)是人工神经网络中采用最多的训练方法。该算法通过对训练样本集的学习,将每次的处理结果与该样本已知类别进行比较,用所得的误差帮助完成学习,并且对每个训练样本动态的修改权值从而让网络的输出值与实际的类别的均方差最小。神经网络的优点就是并行分布处理能力强,分类的准确网络技术度高,对噪声数据有较强的鲁棒性和容错能力,具备联想记忆的功能等等。但是该方法获取的模式隐含在网络结构中,导致分类结果较难理解.网络的训练时间较长,不适于大数据量的学习四。2.3贝叶斯分类贝叶斯分类以统计学中的贝叶斯定理为理论基础,通过贝叶斯定理得到的后验概率来预测类成员关系的可能性,是一种具有最小错误率的概率分类方法。在计算过程中,如果假设所有变量都是条件独立的.则可以使用朴素贝叶斯分类方法,但所有变量都是条件独立的情况非常少。贝叶斯网络可以综合先验信息和样本信息。减少了定义全联合概率分布的概率数目,又避免了朴素贝叶斯分类器要求所有变量都是条件独立的不足。成为近年的主要研究方向。3支持向量机支持向量机是在统计学习理论基础上发展起来的一种非常有效的分类方法。它的基本原理是使用一个最优超平面对所有的点进行分类。使得属于同一类的点尽可能被分在超平面的同一侧,并且要求分隔的间距最大H。3.1统计学习理论统计学习理论就是研究小样本统计估计和预测的理论。其核心问题是寻找一种归纳原则以实现最小化风险泛函,从而实现最佳的推广能力。变量v与变量x之间存在一定的未知的依赖关系,根据几个独立同分布的观测样本(x1川,(】%均,⋯⋯,‰内在一组函数{眠w)}中寻找一个最优函数眠w0,对x和y间的依赖关系进行估计,使预测的期望风险R(w)=J三(少,厂(工,w))cI:F(工,y)最小。其中{坟】【.w)}称为预测函数集。w为函数的广义参数。根据概率论中的大数定理,可以用训练样本的风险的算术平均值——经验风险R哪lp(w)来代替期望风险最小,称为经验风险最小化原则,简称ERM。但是利用经验风险代替期望风险最小化并没有充分的理论依据。在有限样本空间,R七nlp(、v)最小并不能保证R(、Ⅳ)最小。使经验风险最小并不总能导致好的预测效果。在某些情况下反而降低推广能力,增加真实风险。产生过学习问题。对于一个预测函数集{眠w)),如果存在h个样本(x。,内,(x2,均,...⋯,()‰蝴,能够被函数集中的函数按所有可能的2“种形式分为两类,则称函数集能够把h个样本打散。预测函数的vc维就是用这个函数集中的函数所能打散的最大样本集的样本数h。若对任意数目的样本都有函数能将它们打散.则函数集的Vc维是无穷大。vC维是目前对函数学习集学习性能的最好描述指标,Vc维越大则学习机器越复杂。学习容量就2009年第19期《计算机与网络> 万方数据 网络技术计算机与网络创新生活越大。统计学习理论中关于经验风险和期望风险的关系建立在vc维的基础上,对预测函数集,经验风险和期望风险间以至少1—11的概率满足R(w)≤R吼p(w)+互√£,当函数集中1厂包含有限个元素时,£=2坚!专尘堕,其中’h是函数集的vc维,n是样本数,q是满足o<11<1的参数。把函数集构造为一个函数子集序列,使各个子集按照、C维的大小排列;在每个子集中寻找最小经验风险,在子集间折衷考虑经验风险和置信范围,取得实际风险的最小。这种思想称作结构风险最小化,简称SRM原则。因此.统计学习中的R(w)由经验风险和置信范围两部分组成。能使经验风险与置信范围之和最小的函数就是最优函数。SRJM原则的具体实现如下:设计函数集的某种结构使每个子集中都能取得最小的经验风险.然后选择适当的子集使置信范围最小,该子集中使经验风险最小的函数就是最优函数。支持向量机方法是这种思想的具体实现。3.2支持向量机设线性可分样本集及其所属类别表示为憾,妨,i-1,2,⋯⋯,n,xE刚’y∈{+1,一1}是类别标号。D维空间中线性判别函数的一般形式为g(x)=w·x+b,H是把两类样本正确分类的分类面,其方程为w·x+b=0,H,和H:分别为过各类样本中离分类面最近的点且平行于分类面的平面,其对应的方程为w·x+b=1,w·x+b=一1,并且H。和H:之间的部分不能出现训练样本点。H,和Hz之间的距离为2/ffwf|。通过d维特征空间中构造分类面H:w·x+b=0,使得训练样本伍,订满足:w·x+b≥1,如果yi=1;w·x+b≤一1,如果yi=一1。将判别函数进行归一化,使两类所有样本都满足l|g(x)Il≥1,即样本到分类面的最小距离为1。H,和H。上的使yi【(w·x)+b】一1=o的训练样本就称为支持向量,最优分类超平面就是由这些支持向量决定的。1支持向量机的数学形式可以表示为n血审(w,b)=2(w·w),yi【(w·硝+b】≥1.i=1,2,⋯⋯,n。利用Iag均nge优化方法可击以把上述最优分类面问题转换为其对偶问题,求当备仪,yi:。时.巾。a,:善∞一圭善oc,oc,珊(Xi.筠)的最大值,0【f为与yl·【(w·硝+b】≥1式中每个样本对应的Ia舯nge乘子,该问题是一个不等式约束下二次函数寻优问题,存在唯一解。计算得到的最优分类函数是㈣:驴{(w★.x)岫★}-。印{荟仅,★yi伍.X)+b★),该式中的求和式只对支持向量进行,可以由任意一个支持向量用yi【(w·柚+b】一1=0求得。对于线性不可分的情况.一般采用软间隔最优超平面方法,即放宽约束条件的限制,在约束中加入一个松弛变量,使该式成为yi【(w·均+b】≥1一乞,在目标函数中加入一个惩罚因子’成为巾(w)曼㈣+CI善芎气软间隔分类器问题可子,成为Q(w)=2(w·w)+cI鲁啊l,软间隔分类器问题可以表示为一小俨圭(w.w)+Cl善芎‰【(w.帅】≥111in巾(w’b,岛):i(w·、功+cI缶弓‘I'yi【(w.均+b】≥1一号f,芎f≥o,i_1,2。⋯⋯,n。其对偶形式为nla】(巾(0‘):1一bf,bf≥O,i_1,2。⋯⋯,n。其对偶形式为nm(叩(u)=善吼一吉善仅,oc,珊K(Xi,玛),善仪,yi=o。在线性不可分得情况下。需要通过非线性变换将训练数据集从输入空间映射到高维特征空间,即改变训练数据的表达形式,通过这样的转换在高维特征空间中使用线性分类器将它们分开。在向高维特征空间转换时。特征空间中两点的内积可以用原空间中对应向量的核函数表示,使用不同的核函数可以产生不同类型的支持向量机算法。4基于支持向量机的分类预测算法支持向量机是一种基于sRM原则的以样本间的某种距离作为划分依据的分类预测方法。它把分类问题归结为一个带有线性约束的凸二次规划问题。由于已有的二次优化算法(如共轭梯度法、内点法等)都要存储与训练集相应的核矩阵,无法实现存储和计算。因此出现了一些支持向量机训练算法嗍。4.1Ch硼峪I培算法(选块算法)由于支持向量机的解仅仅与于支持向量有关.因此只选择支持向量对应的训练样本,可以建立与原训练集相同的最优分类函数。chunhlg算法就是基于该思想的最简单的启发式算法,它的目标去掉非支持向量的训练点,只对支持向量计算其相应的I伊mage的乘子a。该算法通过迭代方式逐步排除非支持向量,选出支持向量所对应的“块”。Chu幽雌算法删除了矩阵中对应Iag口nge乘子为零的行和列,使得矩阵规模从训练样本数的平方减少到非零Ia舯nge乘子的样本数的平<计算机与厨络>2009年第19期 万方数据 计算机与网络创新生活方。chu她算法可以缩少问题的规模,提高运算速度,尤其是支持向量数目远远小于训练样本数目的情况。但是如果支持向量的数目比较多。所选的块也会越来越大,该算法也无法将矩阵放入内存中,会变得缓慢而失效。4.2分解算法当支持向量较多时,chuIll【ing算法可能会失效,为解决这一问题又提出了分解算法。该算法将训练样本分为工作集B和非工作集N,集合B中包含样本个数至少和支持向量的个数一样多,每次只更新矩阵中若干个Iagrange乘子,而其它的乘子不变。迭代过程中只是将剩余样本中部分违背KKT条件最严重的样本点与工作样本集中的样本进行等量交换.当支持向量的个数超过工作样本集的个数时也不改变工作样本集的规模,即只对支持向量中的一部分进行优化。分解算法的关键是每次迭代过程中如何选择工作集B。如何选择样本点换入换出的策略,很多改进算法修改了替换策略,提高了算法的效率。svMIi曲t算法从选择工作集的角度更有效地实现分解算法.通过求解一系列小规模的子二次规划问题来逐步实现对原有问题的求解。分解算法与选块算法的不同之处在于它每次只更新若干个Iag阻玎ge乘子,而其他的乘子保持不变。每次一个新样本点加到工作集中去,就必须舍去另外一个样本点。迭代过程中只是将工作集之外的样本点中一部分“情况最糟的样本点”与工作集中一部分样本点进行等量交换,当支持向量的个数超过工作集的大小时,也不改变工作集的规模。4.3序列最小优化算法序列最小优化算法(9equ朗血lminimalop6mjzadon,SMo算法)可以看作是分解算法的一个特例,它将子问题的规模减少到了两个样本,满足等式线性约束的存在使得同时至少有两个Iagmage乘数发生变化的分解算法原理。由于子问题的优化只涉及两个变量。而且应用等式约束可以将其中一个变量用另一个变量线性表示出来。所以迭代过程中每一步的子问题的最优解可以直接用解析的方法求出来,而不用在算法中迭代求解二次规划问题。它的每一步迭代只是选择两个变量进行调整,同时固定其它变量,通过求解最优化问题,得到这两个变量的最优值,来更新相应的I伊n耵ge乘子。该算法将一个大型二次优化问题分解为一系列最小规模的二次优化子问题。从而使得二次优化子问题可以通过解析的方法求解,避免了在内循环中使用数值算法进行二次优化。SMo方法可以解决小样本情况下的机器学习问题,它提高了泛化性能,解决了高维特征空间问题,由于采用了凸优化算法。避免了神经网络结构选择和局部极小点的问题。SMo的最大特色在于它可以采用解析的方法而完全避免了二次规划数值解法的复杂迭代过程,不必使用数值分析中的二次优化网络技术67软件包。这不但大大节省了计算时间,而且不会牵涉到迭代法造成的误差积累,使算法在速度和精度两方面都得到了保证。但是sMo算法也存在着一些不足之处,尤其是构建和训练分类模型的时间较长。sMo将工作集的规模减到最小,一个直接的后果就是迭代次数的增加,导致算法时间增加。该算法速度的瓶颈在于最优条件的判断和非线性情况下误差的重置,因为这两处都需要对所有的向量计算核函数。5结束语支持向量机以统计学习理论为基础,遵循结构风险最小化原则,有效地避免了经典学习方法中过学习、维数灾难、局部极小等传统分类存在的问题。在小样本条件下具有良好的泛化能力。但是支持向量机的算法还不是很成熟,仍有很多同题亟待研究。同时二次规划同题的求解也制约着支持向量机更广泛的应用。参考文献fl】邓乃扬.数据挖掘中的新方法——支持向量机fM】.北京:科学出版社,2007.【2】韩家炜.数据挖掘:概念与技术【M】.北京:机械工业出版社,2001.【3】郭虎升,王文剑.基于神经网络的支持向量机学习方法研究U】.计算机工程与应用,2009,45(2):51~54.【4】NcⅡocris6anilli.支持向量机导论【l吲.北京:电子工业出版社,2005.【5】周宽久,张世荣.支持向量机分类算法研究Ⅱ】.计算机工程与应用,2009,45(1):15弘162.Bl眦Coat连续两季度摘得广域网优化市场份额桂冠Blueco札公司目前宣布,在InfoneticsR嚣蜘.ch最新公布的市场份额报告中,Blueco扯公司连续第二季度蝉联广域网优化市场份额冠军。报告还显示。BlueCoat第二季度市场份额为31.铴。这一数字比去年同期的24.8%提高了近7个百分点。“市场份额的增长有力地证明了BlucCo牡广域网优化为企业带来的价值——加速关键业务相关应用,同时减少不必要或娱乐应用的影响,”Bl∽Co扯公司大中华区执行总监潘道良表示:“B1ueco乱设备提供的智能加速让企业能够依照业务优先级优化自己的广域网,而不需要对带宽进行额外的投资。”据In南neticsR岛e眦h预测,广域网优化设备市场在未来3年内将增长50%。换言之,整个市场将从2009年的9.53亿美元增长至14亿美元。广域网优化是BlueCoat应用交付网络架构中的一项基础技术。B1ueCoat应用交付网络架构融可视性、加速和安全技术于一体.帮助网络管理员为分布式企业的应用交付提供优化和安全。2009年第19期《计算机与厨络> 万方数据
还剩3页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

lijasonvip

贡献于2016-08-04

下载需要 10 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf