支持向量机.doc

第四章支持向量机（SVM——SupportVectorMachine）
§4-1.线性分类问题的支持向量机
分类问题与机器学习
设有两类模式和，是从模式和中抽样得到的训练集，其中、。若属于类，则对应有；若属于类，则对应有；。寻求上的一个实函数，对于任给的未知模式，有
或者(4-1)
式中为符号函数，称为决策（分类）函数。
前两章学过的前向神经元网络和径向基网络，都可以用来解决此类问题。这一章，我们称解决上述问题的方法为“分类机”。当为线性函数时，称为线性分类机；当为非线性函数时，称为非线性分类机。

图4-1.样本分布
表4-1
编号年龄胆固醇患病否156192-125520513701771474155-15591981668171-1
举例：患有心脏病与年龄和胆固醇水平密切相关。对大量病人进行调查，得到表4-1所示数据，图4-1是数据的分布示意图。
根据数据分布以及所对应的值，我们可以目测获得一条分类线。不仅可以将两类模式分开，并且具有最宽的“边带（Margin）”。以后，对任意一个被观察者进行检验，得到其数据后，若处于上边，即可判定为心脏病疑似；处于下边，则认为没有患有心脏病。
以上仅用年龄和胆固醇水平来判定是否患有心脏病显然是极其不可靠的。也就是说仅凭和两个参数不足以判别一个人是否患有心脏病，还必须考虑更多的参数，的维数很高。这种情况下已无法人为直观地确定判别函数了。于是，我们需要一种根据给定的大量样本确定判别函数的方法，即需要一个能够由经验数据学会对某些模式进行分类的“学习机”。
两类可分问题的线性分类机
实际上，以前讲过的“采用硬限幅函数的单个神经元”就是一个线性分类机。这里，我们从最大分类间隔角度，导出另外一种线性分类机。
仍以图4-1为例，对于这个二维问题，线性分类机的作用就是要在和之间寻找一条分类线，其表达式为。我们已经熟知，在高维情况下是一个超平面。
对于线性可分的两类模式和而言，能够准确将其分开的直线不是唯一的。假设有直线可以无误地将和两类模式分开，另有直线和直线与之间的间距为，与之间形成一个没有学习样本的带状区域，不妨称该带状区域为“边带（Margin）”，而是边带的中分线。显然，最合理的分类线应该具有最宽的边带。
假设，已知分类线的法线矢量为，则分类线的表达式为：
(4-2)
式中表示矢量点积。显然，到原点距离为。
对于给定的所有个学习样本，应满足：
(4-3a)
或写成
(4-3b)
如图所示，直线和直线与分类线之间的间隔距离为，则这两条边界线的表达式分别为：

直线和直线之间的间距为，寻找最大带宽的问题，转化为在保证所有学习样本满足(4-3)式的前提下，寻找使达到最大的问题了。
是一个标量，因此，可以取；。于是，分类线的表达式可以改写成：
(4-4)
直线和直线的表达式可以改写成：
(4-5)
当增大时，变小。于是，寻找最大带宽的问题，变成了寻找最小的问题，为了计算上的方便，取目标函数为。
对于任意学习样本，其分布必然在直线之上或直线之下。即有
(4-6)
将以上两式合并，有
(4-7)
在选择分类线的过程中，(4-7)式对于任何学习样本都必须成立。在此前提下寻找最宽边界的问题，最后可以表示成一个约束优化问题：
(4-8)
这里目标函数中的没有其他意义，只是为了下一步导出求解方法时方便。由此得到两类分类机算法：
给定学习样本集，、。表示属于类，表示属于类；
构造并求解关于变量和的优化问题（目标函数加上平方）

求得最优解和；
构造分类函数
(4-9)
对于任意的未知模式，可以由上式判断其所属类别：
(4-10)
从以上分析过程可知，对于任意学习样本，有

学习样本是实际模式的抽样或特例，工作中的实际模式可能超过学习样本的分布范围。如果能够预测到实际模式的分布，并且根据其分布确定分类函数，我们称之为“预测最优”。但实际上是很难做到的，无论我们得到多大规模的样本都总是实际问题的抽样或特例，以这些数据所做的任何估计都只是以局部推测全局。以上得到的“支持向量机”取两类样本之间最大边带的中心为分类函数，显然是对现有学习样本的最佳分类。尽管这样的分类函数未必是“预测最优”，但这种方法比器硬“限幅函数单个神经元”只能得到一个可行的分类函数来说，有更强的合理性。我们称支持向量机获得的分类函数具有“结构最优”性。
从结构上还可以看出，最宽边界只取决于个别样本，大量位于直线和直线外边的样本对最宽边界并没有影响。称恰好位于直线和直线上的样本为“支持向量”。这正是这种算法称为“支持向量机”的原因。
附：用Matlab语言中的优化函数constr求解混合约束问题
语句结构如下：X=constr(‘fun’,x,options)，其中：
fun是目标函数和约束条件的表达式，可以用Matlab的函数语句或M文件