支持向量机算法介绍

支持向量机算法介绍众所周知，统计模式识别、线性或非线性回归以及人工神经网络等方法是数据挖掘的有效工具，已随着计算机硬件和软件技术的发展得到了广泛的应用。但多年来我们也受制于一个难题：传统的模式识别或人工神经网络方法都要求有较多的训练样本，而许多实际课题中已知样本较少。对于小样本集，训练结果最好的模型不一定是预报能力最好的模型。因此，如何从小样本集出发，得到预报（推广）能力较好的模型，遂成为模式识别研究领域内的一个难点，即所谓“小样本难题”。支持向量机（supportvectormachine，简称SVM）算法已得到国际数据挖掘学术界的重视，并在语音识别、文字识别、药物设计、组合化学、时间序列预测等研究领域得到成功应用。1、线性可分情形SVM算法是从线性可分情况下的最优分类面（OptimalHyperplane）提出的。所谓最优分类面就是要求分类面不但能将两类样本点无错误地分开，而且要使两类的分类空隙最大。设线性可分样本集为),(iiyx，dRxni,,,1，}1,1{y，d维空间中线性判别函数的一般形式为bxwxgT，分类面方程是0bxwT，我们将判别函数进行归一化，使两类所有样本都满足1xg，此时离分类面最近的样本的1xg，而要求分类面对所有样本都能正确分类，就是要求它满足nibxwyiTi,,2,1,01)(。（4）式（4）中使等号成立的那些样本叫做支持向量（SupportVectors）。两类样本的分类空隙（Margin）的间隔大小：Margin=w/2(5)因此，最优分类面问题可以表示成如下的约束优化问题，即在条件（4）的约束下，求函数)(21221(6)的最小值。为此，可以定义如下的Lagrange函数：]1)([21),,(1bxwyawwabwLiTiniiT(7)其中，0ia为Lagrange系数，我们的问题是对w和b求Lagrange函数的最小值。把式（7）分别对w、b、ia求偏微分并令它们等于0，得：iiniixyawwL10001iniiyabL0]1)([0bxwyaaLiTiii以上三式加上原约束条件可以把原问题转化为如下凸二次规划的对偶问题：0,,1,0.max111121iniiijTijijninjiniiyaniatsxxyyaaa(8)这是一个不等式约束下二次函数机制问题，存在唯一最优解。若*ia为最优解，则niiiixyaw1**(9)*ia不为零的样本即为支持向量，因此，最优分类面的权系数向量是支持向量的线性组合。b*可由约束条件0]1)([bxwyaiTii求解，由此求得的最优分类函数是:)sgn())sgn((*1****bxxyabxwxfniiiiT(10)sgn()为符号函数。2、线性不可分情形当用一个超平面不能把两类点完全分开时（只有少数点被错分），可以引入松弛变量i（i≥0,ni,,1），使超平面0bxwT满足：iiTibxwy1)((11)当0i1时样本点xi仍旧被正确分类，而当i≥1时样本点xi被错分。为此，引入以下目标函数：niiTC),((12)其中C是一个正常数，称为惩罚因子，此时SVM可以通过二次规划（对偶规划）来实现：0,,1,0.max111121iniiijTijijninjiniiyaniCatsxxyyaaa(13)3、支持向量机（SVM）的核函数若在原始空间中的简单超平面不能得到满意的分类效果，则必须以复杂的超曲面作为分界面，SVM算法是如何求得这一复杂超曲面的呢？首先通过非线性变换将输入空间变换到一个高维空间，然后在这个新空间中求取最优线性分类面，而这种非线性变换是通过定义适当的核函数（内积函数）实现的，令：)()(),(jijixxxxK(14)用核函数),(jixxK代替最优分类平面中的点积jTixx，就相当于把原特征空间变换到了某一新的特征空间，此时优化函数变为：aQjijijninjiniixxKyya,11121（15）而相应的判别函数式则为：)),(sgn(])()sgn[(*1***bxxKyabxwxfniiiiT（16）其中ix为支持向量，x为未知向量，(16)式就是SVM，在分类函数形式上类似于一个神经网络，其输出是若干中间层节点的线性组合，而每一个中间层节点对应于输入样本与一个支持向量的内积，因此也被叫做支持向量网络，如图1k(x1,x)k(x2,x)k(x3,x)x1x2x3x4y图1支持向量网络预报未知样本类别的示意图Fig.1ThesketchmapofsupportvectornetworktopredictanunknownsamplesiiiibxxKyay1,sgnS个支撑向量机的非线性变换输入向量x=(x1,x2,…,xd)图1支持向量网络预报未知样本类别的示意图Fig.1Thesketchmapofsupportvectornetworktopredictanunknownsample由于最终的判别函数中实际只包含未知向量与支持向量的内积的线性组合，因此识别时的计算复杂度取决于支持向量的个数。目前常用的核函数形式主要有以下三类，它们都与已有的算法有对应关系。(1)多项式形式的核函数，即ixxK,qiTxx1，对应SVM是一个q阶多项式分类器。(2)径向基形式的核函数，即ixxK,}exp{22ixx，对应SVM是一种径向基函数分类器。(3)S形核函数，如ixxK,),)(tanh(cxxviT则SVM实现的就是一个两层的感知器神经网络，只是在这里不但网络的权值、而且网络的隐层节点数目也是由算法自动确定的。