机器学习——SVM实战

机器学习（十八）

——SVM实战

（原创内容，转载请注明来源，谢谢）

一、概述

本篇主要用python来实现SVM算法，并用SVM算法进行预测分类结果。对于SMO的计算，是以上一篇的理论分析为基础的。

SMO的核心思想，就是每次选择两个α，其中第一个α是随机选出来的，第二个α根据一定的优化规则选出来，然后计算这两个α对应的拉格朗日乘子的结果，查看是否符合KKT条件，对于不符合条件且可以更新的α，进行更新。

二、前期准备

1、数据准备

由于SVM的计算，是wx+b，而不是logistic中的θx，因此这里取数据的时候，不需要人工添加上x0=1这一项，而是直接从x1开始的。

2、辅助函数—限定变量上下界

这个主要是在后面，SMO算法中，需要更新α2，更新的时候，要保证更新的α必须在0~C之间，因此这里写了辅助函数。

3、核函数

核函数K(x)非常方便，可以用线性函数、高斯核函数等进行替换，核函数有很多，这里目前就实现了线性函数和高斯核函数。

4、辅助数据结构

这里定义了一个辅助的类，便于存储训练样本、分类结果、参与训练α的参数C、允许误差的偏差toler（实际是ξ符号）、核函数等。

5、计算误差

这里的误差计算，是用于调整α的，实际公式是α*y*K(x)+b-y。

6、选择第二个α

根据第一个α的下标，以及误差值，还有辅助类，保证在有误差的元素中进行选择，且不能取到同一个元素，且还需要取到误差相对来说最大的元素。但是如果是第一次选择，那就随机选择一个即可。

7、误差存储

优化后的SMO算法，与普通的SMO算法，最大的区别，就在于其有对误差进行存储，且保证第一次遍历整个样本后，第二次开始，只更新所关心的支持向量的优化，而并不需要整个样本的点参与优化。

这里更新完，存储在辅助类的属性中。

三、内循环—选择第二个α

内循环，目的是选择第二个α，而这个前提是第一个选出来的α是可以更新的，其对应的约束条件为：

这就是下面的if语句中的判断。

而对于α的更新，其还有个约束条件，即α有对应的最值，不能超过0~C的区间，如下规则（具体原因见上一篇文章的推导过程）：

得到α2的区间后，还需要更新出α2，进而更新出α1，以及b（具体原因见上一篇文章的推导过程）。

四、外循环

外循环的目的是根据一定的条件选出α1，再调用上面的选择α2的内循环，主要在于控制集合的范围。

这里即体现了优化的SMO的思想：第一次训练，则要循环整个样本集，但是仅存储误差需要更新的对应的α，将其存储在辅助类中；第二次开始，则从辅助类中取点，只对辅助类中的点进行更新；当辅助类的点都更新完，如果训练的次数还没超过预定的训练上限，则再次取整个样本集。以此类推进行训练。

五、测试以及执行结果

测试的过程则比较简单，把样本集传入上面定义好的函数，设定C、ξ、训练次数、核函数，即可得到对应的α和b，利用这两个参数（α实际上是一个矩阵），再对测试样本进行判断结果。

这里可以看到，当通过SMO算法，得到α和b后，实际上已经不需要再次用训练数据进行训练，下面代码中的训练和测试实际上可以理解成两次的测试过程。

下面是执行结果的部分截图。可以看到错误率15%，算是比较低的。

六、总结

支持向量机，是一个比较有趣的算法，经过这几天的学习，我对里面的大部分的公式和编码过程有了大致的了解，具体的细则还没了解的那么透，后面还会继续深入学习。接下来可以迈入新的学习内容了。

我感觉学习的过程，还是贵在坚持，而且要静下心来。对于看不懂的内容，多查资料；对于数学公式，自己一步步去推导；对于代码，一行行去看。慢慢的就会有种融会贯通的感觉。

——written by linhxx 2018.01.20