资源描述：
《一种新的SVM多类分类算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第24卷第4期佳木斯大学学报(自然科学版)Vol.24No.42006年10月JournalofJiamusiUniversity(NaturalScienceEdition)Oct.2006文章编号:1008-1402(2006)04-0476-03一种新的SVM多类分类算法12霍颖瑜,王晓峰(1.广东佛山科学技术学院理学院,广东佛山582000;2.广东北电研发中心,广东广州510220)摘①要:给出了一种基于编码二叉树的支持向量机(SVM,SupportVectorMachine)的多类分类算法.首先,定义了一种构造编码二叉树的方法,在此基础上合理的使用每个训练样本对应的编
2、码来对多类样本进行划分,使之转化为两类分类问题.由算法的实现过程可以看出,本算法可以大大减少子分类器的构造个数,从而简化了多类SVM分类算法.关键词:编码二叉树;SVM;多类分类中图分类号:TP181文献标识码:A[1,2]由Vapnik等人提出的统计学习理论是一种小样本统计理论,主要是针对小样本学习集情况下的统计规律和学习方法进行研究,为机器学习问题建立了一个较好的理论框架,同时也发展了一种模式识别方法———SVM.SVM的引入主要基于以下[2]三大理论基础:(1)结构误差理论,通过最小化函数集的VC维来控制学习机器的结构风险,使其具图1最优超平面有较强的推广能力;(2)结构误
3、差的最小化问题可这是一个典型的二次规划问题,可用拉格朗日以描述为条件二次优化问题;(3)核空间理论,将低乘子法求解,我们可以得到SVM分类函数:l维空间的输入数据通过非线性映射函数映射到高f(x)=sgn
4、∑yαii(x·xi)+b
5、(2)维属性空间.因此,SVM具有很强的泛化能力,不i=1过分依赖样本的数量和质量,但是由于SVM的发当两类模式为线性不可分的情况时,超平面无展时间并不长,还存在着很多缺点和不足.法将两类样本点分开,Vapnik应用希尔伯特再生核[3]最初SVM是用以解决两类分类问题,不能直空间的核理论将输入样本映射到高维特征空间,接用于多类分类,如何有效地将其推广
6、到多类分类并在这个空间中进行超平面的构造.为了实现线性不问题还是一个正在研究的问题.当前已经有许多算可分到线性可分的转化,引入了适当的内积函数(核法将SVM推广到多类分类问题,这些算法统称为函数)K(xi,xj),此时SVM分类函数相应的变形为:l“多类SVM”.f(x)=sgn
7、∑yαiiK(x,xi)+b
8、(3)i=1[3]1SVM理论准备2多类SVM对于n维空间中的样本数据,SVM的任务就是构造一个最优分类超平面(w·x)-b=0,该超平由以上可以看出,SVM一般用于两类分类问题,面不仅可以正确的将两类样本点分隔开,而且还使对于多类分类问题如何进行推广,很多专家已经作了两类
9、样本的分类间隔(Margin)最大(见图1).多方面的研究.从当前来看,它们大致分为两大类:根据统计学理论,寻找最优超平面的求解过程可(1)通过某种方式构造一系列的两类分类器以归结为求解如(1)式所示的一个二次线性规划问题:并将它们组合在一起来实现多类分类;1(2)将多个分类面的参数求解合并到一个最2minφ(w)=‖w‖2(1)优化问题中,通过求解该最优化问题“一次性”地约束条件:yi(wxi+b)-1≥0i=1,2,⋯,l实现多类分类[4,5].①收稿日期:2006-07-21作者简介:霍颖瑜(1979-),女,广东佛山人,佛山科学技术学院助教,硕士,从事智能信息处理方面的研
10、究.第4期霍颖瑜,等:一种新的SVM多类分类算法477第二类方法尽管看起来简洁,但是在最优化问类器结构的方法.题求解过程中的变量远远多于第一类方法,训练速3一种新的多类SVM分类算法度不及第一类方法,而且在分类精度上也不占[6]优.当训练样本数非常大时,这一问题更加突出.3.1编码二叉树因此,我们将主要对第一种多类SVM作一个简单的介绍.为了应用这种新的多类SVM算法,需要首先多类分类问题可以形式化地表述为:给定属于构造一个编码二叉树,该二叉树的特点如下:K类的m个训练样本(x1,y1),⋯,(xm,ym),其中xi1)对于k类分类问题,其对应的二叉树深度为Nk∈R,i=1,2,
11、⋯,m,且yi∈{1,2,⋯,k},需要通[log2]过上述样本训练一个多类分类器f,使其能够对新2)对于根节点,其对应的编码为1样本进行正确分类.以下为几种比较经典的多类3)对于某一节点的左子节点,其编码为CC…,SVM算法.其中C为该左子节点的父节点对应的编码,C…表示[7]对C按位取反.2.112a2r(12aginst2rest)法4)对于某一节点的右子节点,其编码为CC,算法12a2r是去构造N个两类目标子分类器,其中C为该右子节点的父节点对应的编码.第k个子分类器用第
