支持向量机(Support Vector Machine,SVM)是AT&TBell 实验室的V.Vapnik等人提出的一种新型机器学习算法。到目前为止,支持向量机已应用于孤立手写字符识别6&7、网页或文本自动分类、说话人识别、人脸检测、性别分类、计算机入侵检测、基因分类、遥感图象分析、目标识别、函数回归、估计、函数逼近、密度估计、时间序列预测及数据压缩、文本过滤、数据挖掘、非线性系统控制等各个领域的实际问题中。 SVM的主要思想是针对两类分类问题,寻找一个超平面作为两类训练样本点的分割,以保证最小的分类错误率。在线性可分的情况下,存在一个或多个超平面使得训练样本完全分开,SVM的目标是找到其中的最优超平面,最优超平面是使得每一类数据与超平面距离最近的向量与超平面之间的距离最大的这样的平面,如下图所示,超平面W是h值最大的最优超平面;对于线性不可分的情况,通过使用核函数(一种非线性映射算法)将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分。 SVM的基本模型设输入模式集合{ x[i]} ∈ Rn 由两类点组成, 如果x[i]属于第1类, 则y[i] = 1 , 如果x[i]属于第2类, 则y[i] = -1 , 那么有训练样本集合{ x[i] , y[i]} , i = 1 ,2,3 , ?, n ,求最优分类面wx-b=0,满足:y[i](w·x[i] - b) >= 1;并使2*h= 2/‖w‖最大,即min‖w‖*‖w‖/2;根据对偶理论,可以通过解该问题的对偶问得到最优解,对偶问题为: max∑α[i] – 1/2 ∑α[i]*α[j]*y[i]*y[j]*x[i]*x[j] 0≤α[i]≤C*∑α[i]*y[i]=0 其中x[i] ·x[j]表示这两个向量的内积,当对于线性不可分的情况,用核内积K(x[i], x[j])(通过核函数映射到高维空间中对应向量的内积)代替x[i] ·x[j]。根据对偶问题的解α,求得w,b ,得到最优分类面 SVM模型求解:当训练样本向量很多、向量维数很大时,解上面的对偶问题是一个解大型矩阵的问题,采用传统的矩阵求逆无论在空间复杂度上还是在时间复杂度上都是不可取的。序贯最小优化(sequential minimal optimization,简称SMO)算法是目前解决大量数据下支持向量机训练问题的一种十分有效的方法。 SMO的基本思想是每次只选择违法KTT条件最严重的两个拉格朗日乘子,通过求解只有两个变量的二次规划问题,更新选取的拉格朗日乘子,此时保持其他拉格朗日乘子,通过不断的迭代,最终得到问题的最优解。SMO的基本步骤为: 1、将a向量分成两个集合,工作集aB,固定集aN,即:a = {aB, aN }。初始化时,aB为a全部的分量,aN为空集; 2、每次对aB解决一个小的二次规划问题,保持aN中的值不变; 3、每次迭代选择不同的aB和aN ,每解决一个小规模优化问题,都在原来的基础上向最终的解集前进一步; 4、每次迭代检查当前结果,满足优化条件,则找到了优化问题的解,算法结束。 推荐书籍:《数据挖掘中的新方法:支持向量机》 支持向量机作为一种可训练的机器学习方法,依靠小样本学习后的模型参数进行导航星提取,可以得到分布均匀且恒星数量大为减少的导航星表。Vapnik等人在多年研究统计学习理论基础上对线性分类器提出了另一种设计最佳准则。其原理也从线性可分说起,然后扩展到线性不可分的情况。甚至扩展到使用非线性函数中去,这种分类器被称为支持向量机。SVM的主要思想可以概括为两点: (1) 它是针对线性可分情况进行分析,对于线性不可分的情况,通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分,从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能;例如,将1维的“线性不可分”上升到2维后就成为线性可分了。 (2) 它基于结构风险最小化理论之上在特征空间中建构最优分割超平面, 使得学习器得到全局最优化,并且在整个样本空间的期望风险以某个概率满足一定上界。 在学习这种方法时,首先要弄清楚这种方法考虑问题的特点,这就要从线性可分的最简单情况讨论起,在没有弄懂其原理之前,不要急于学习线性不可分等较复杂的情况,支持向量机在设计时,需要用到条件极值问题的求解,因此需用拉格朗日乘子理论,但对多数人来说,以前学到的或常用的是约束条件为等式表示的方式,但在此要用到以不等式作为必须满足的条件,此时只要了解拉格朗日理论的有关结论就行。 SVM的一般特征: (1)SVM学习问题可以表示为凸优化问题,因此可以利用已知的有效算法发现目标函数的全局最小值。而其他分类方法(如基于规则的分类器和人工神经网络)都采用一种基于贪心学习的策略来搜索假设空间,这种方法一般只能获得局部最优解。 (2)SVM通过最大化决策边界的边缘来控制模型的能力。尽管如此,用户必须提供其他参数,如使用核函数类型和引入松弛变量等。 (3)通过对数据中每个分类属性引入一个哑变量,SVM可以应用与分类数据。 (4)SVM一般只能用在二类问题,对于多类问题效果不好。 SVM方法是通过一个非线性映射p,把样本空间映射到一个高维乃至无穷维的特征空间中(Hilbert空间),使得在原来的样本空间中非线性可分的问题转化为在特征空间中的线性可分的问题.简单地说,就是升维和线性化.升维,就是把样本向高维空间做映射,一般情况下这会增加计算的复杂性,甚至会引起“维数灾难”,因而人们很少问津.但是作为分类、回归等问题来说,很可能在低维样本空间无法线性处理的样本集,在高维特征空间中却可以通过一个线性超平面实现线性划分(或回归).一般的升维都会带来计算的复杂化,SVM方法巧妙地解决了这个难题:应用核函数的展开定理,就不需要知道非线性映射的显式表达式;由于是在高维特征空间中建立线性学习机,所以与线性模型相比,不但几乎不增加计算的复杂性,而且在某种程度上避免了“维数灾难”.这一切要归功于核函数的展开和计算理论. 选择不同的核函数,可以生成不同的SVM,常用的核函数有以下4种: (1)线性核函数K(x,y)=x·y (2)多项式核函数K(x,y)=[(x·y)+1]d (3)径向基函数K(x,y)=exp(-|x-y|^2/d^2) (4)二层神经网络核函数K(x,y)=tanh(a(x·y)+b) |
|