【机器学习实战-python3】支持向量机（Support Vecrtor Machines SVM）

有人认为SVM是最好的现成的分类器，“现成”指的是分类器不加修改即可直接使用，意味着直接应用SVM可以取得较低的错误率，对训练集之外的数据点做出很好的分类决策。 SVM有许多实现，这里介绍其中一种最流行的实现，即序列最小优化（SMO）算法，然后添加kernel函数将SVM拓展到更多数据集。 SVM是基于最大间隔分隔数据，若所给数据是二维的，则分隔线为一条直线，若数据为三维的，则分割线为一个平面，依次类推，随着数据维数的增加，分隔面就变成了超平面。而最大间隔，是让离分隔面最近的点，确保他们离分隔面尽可能远。SVM本身是一个二类分类器，若要解决多类问题，需要修改SVM。

一、寻找最大间隔 SVM中为了找到划分数据集的最佳分隔，确保最近的点到分隔的垂线最短，因此转化为了一个优化问题。这里分隔面可以定义为：wT+b$w^{T}+b$，将输入数据给分类器，会输出分隔标签，这里采用sigmoid函数，即f（wT+b）$f（w^{T}+b）$，可输出1/-1（与1或0无异）。间隔则通过label∗f（wT+b）$label*f（w^{T}+b）$来计算。找到最小间隔的数据点，最大化其与间隔的距离。argmaxw,b{minn(label⋅(wT+b))⋅1||w||} $$arg /max_{w,b}/left /{ /min_{n} /left (label/cdot /left ( w^{T+b} /right ) /right )· /frac{1}{||w||}/right /}$$ 这里 {minn(label⋅(wT+b))⋅1||w||} $$/left /{ /min_{n} /left (label/cdot /left ( w^{T+b} /right ) /right )· /frac{1}{||w||}/right /}$$ 是点到间隔的几何间隔，与上面所说的label∗f（wT+b）$label*f（w^{T}+b）$的函数间隔意义相同。这里固定label∗f（wT+b）>=1.0 $$label*f（w^{T}+b）>=1.0$$ 去优化1||w||$/frac{1}{||w||}$，采用拉格朗日乘子法。关于SVM的详细推到公式，可参考其他相关材料：如PRML原书pdf版本

二、SMO高效优化算法 John Platt所提出的SMO算法用于训练SVM，将最大优化问题分解为多个小优化问题，求解的结果是完全一致的，且SMO算法求解的时间短很多。 为了得到分隔的超平面，就需要得到最优的alpha值，上面所提到的最优化式子可化为下式：∑αi⋅labeli=0 $$/sum /alpha _{i}/cdot label^{i}=0$$ SMO算法的目标就是求出一系列alpha和b，一旦求出alpha就很容易计算出权重向量从而得到分个超平面。SMO算法的工作原理是，每次循环对两个alpha进行优化处理，得到一对合适的alpha后，就增大其中一个同时减小另一个。这里的“合适”指的是这两个alpha必须在间隔边界之外，并且两个alpha还没有经过区间化处理或者不在边界上。下面是导入数据的代码。

可以看出，类别标签为1与-1

下面进入简化版的SMO，伪代码大致如下： 创建一个alpha向量并将其初始化为0向量 当迭代次数小于最大迭代次数(外循环) 对数据集中每个数据向量(内循环)： 如果该数据向量可以被优化： 随机选择另外一个数据向量，同时优化这个向量 如果两个向量都不能被优化，退出内循环 如果所有向量都未被优化，增加迭代数，进入下次循环。