机器学习经典算法详解及Python实现--基于SMO的SVM分类器

支持向量机基本上是最好的有监督学习算法，因其英文名为support vector machine，简称SVM。通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。

（一）理解SVM基本原理

1，SVM的本质--分类

给定一些数据点，它们分别属于两个不同的类，现在要找到一个线性分类器把这些数据分成两类--这就是最基本的线性可分。如果用x表示数据点、用y表示类别（y可以取1或者-1，分别代表两个不同的类），线性分类器的学习目标便是要在n维的数据空间中找到一个分界使得数据可以分成两类，分界方程可以表示为（此处w^T中的T代表转置，x是一个数据点（有m个属性的行向量），w也是一个大小为m的行向量，b是一个常数）：

在二维平面上，上述分界就是一条直线，如下图将黑点和白点分开的线。三维平面上分界就会是一个平面，而更高维平面上就会是其他的分界表现形式，因此将这个分界称为超平面（hyper plane）。

图1

再次重申，我们假设统计样本的分布式是均匀分布的，如此在两分类分类中（类别-1或者1）可以将阈值设为0。实际训练数据中，样本往往是不均衡的，需要算法来选择最优阈值（如ROC曲线）。

因此SVM分类器就是学习出一个分类函数，当f(x) 等于0的时候，x便是位于超平面上的点，而f(x)大于0的点对应 y=1 的数据点，f(x)小于0的点对应y=-1的点。换言之，在进行分类的时候，将新的数据点x代入f(x) 中，如果f(x)小于0则将x的类别赋为-1，如果f(x)大于0则将x的类别赋为1，f(x)=0就没法分了。

下面以二维平面为例阐明SVM的原理。不难发现能够实现分类的超平面（二维平面上就是一条直线）会有很多条，如下图2所示，如何确定哪个是最优超平面呢？直观而言，最优超平面应该是最适合分开两类数据的直线。而判定“最适合”的标准就是这条直线距直线两边最近数据的间隔最大，也就是“使样本中离超平面最近的点到超平面的距离最远”--最大间隔。所以，得寻找有着“最大间隔”的超平面。下面的问题是--如何求“最大间隔”？

图2

2，根据几何间隔计算“最大间隔”

2.1 函数间隔

对任何一个数据点(x,y)，|w^T*x+b|能够表示点x到距离超平面w^T*x+b=0的远近，而w^T*x+b的符号与类标记y的符号是否一致可判断是否分类正确。所以，可用y(w^T*x+b)的正负性判定或表示分类的正确性（为正才正确），引出了函数间隔（functional margin）的概念。定义函数间隔为：

而超平面所有样本点(xi，yi)的函数间隔最小值便为超平面关于训练数据集的函数间隔：  mini (i=1，...n)

实际上，函数间隔就是几何上点到面的距离公式。

2.2 几何间隔

假定对于一个点 x ，令其垂直投影到超平面上的对应点为 x0 ，w 是垂直于超平面的一个向量，为样本x到分类间隔的距离，如下图所示：

有，||w||=w^T*w，是w的二阶泛数。

又由于  x ₀ 是超平面上的点，满足  f(x ₀)=0  ，代入超平面的方程即可算出： 

数据点到超平面的几何间隔定义为：

而超平面所有样本点(xi，yi)的几何间隔最小值便为超平面关于训练数据集的函数间隔： min (i=1，...n)

几何间隔就是函数间隔除以||w||，可以理解成函数间隔的归一化。

2.3 定义最大间隔分类器Maximum Margin Classifier

前面已经提到，超平面离数据点的“间隔”越大，分类的确信度（confidence）也越大，为使分类的确信度尽量高，需要选择能最大化这个“间隔”值的超平面，而这个间隔就是最大间隔。

函数间隔不适合用来衡量最大化间隔值，因为超平面固定后通过等比例缩放w的长度和b的值可使任意大。但几何间隔除了，缩放w和b的时其值是不会改变的。所以几何间隔只随着超平面的变动而变动，最大间隔分类超平面中的“间隔”用几何间隔来衡量。于是最大间隔分类器（maximum margin classifier）的目标函数可以定义为：

（i=1,2,...,n）,

根据前面分析过的，“使样本中离超平面最近的点到超平面的距离最远”，转化成数学表达式就变为条件：

根据前面的讨论：即使在超平面固定的情况下， 的值也可以随着  ∥w∥ 的变化而变化。为了简化计算，不妨将  固定为1（实质上就相当于式子两边同除以 ，则有w ^T=w