yix今天我们来看看机器学习中的SVM,SVM是什么呢，它的中文名叫支持向量机（Support Vector Machine），是机器学习中的一种分类算法。
SVM，在机器学习里他就是个分类器，当它用于回归分类的时候又叫SVR（Support Vector Regression）。
一般的我们会在什么时候使用SVM呢？
我们来看看这一张图：
对于A这张图我们可以从图中很显然的看出来有两类数据集，而且他们是很均匀的分别在左右两侧。我们可以使用一条直接直接将这两个分类划分开，如下图：
或者是这样：
又或者是这样：
从上面三个图中我们可以很明显看出上面的三种不同的直线都能将图中的方点和圆点分成两类，这就是我们使用SVM的一个场景了，使用一条直线（你可以理解成一个一次函数）将数据集有效的划分成两类。
那么我们的问题来了，就从上面这个例子来说，我们有无数根直线都能将他们划分开，难道这无数根直线都是我们的解吗？
当然不是的，我们需要做的是从这无数个直线中找出最优解，这才是我们SVM干的事情。
那下面我们来解释解释它的工作原理：
图像中的苹果和香蕉正好是我们要划分的两类，我们要做的事情是什么，要保证距离香蕉最近的苹果是最远的。
这句话好像有点绕口，那我们解释一下：意思就是从苹果类中找出一个苹果，它的距离是距离所以香蕉是最近的，同时我们要保证这个距离要尽量的远。
所以，现在我们明确了我们现在要做什么了：
A、寻找最大分类间距
B、转而通过拉格朗日函数求优化的问题
下面我们要解释两个概念：
线性可分数据和分隔超平面
数据可以通过画一条直线就可以将它们完全分开，这组数据叫线性可分(linearly separable)数据，而这条分隔直线称为分隔超平面(separating hyperplane)。
我们是不是发现了，一条线分隔了一个平面，也就是说一维的东西分隔了而为的数据，同样的道理，二维的平面可以分隔三维的空间（你家的房子被你家的墙划分成两个空间），所以我们可以知道，对于N维的数据，我们需要N-1维的对象来进行分隔，这就是分类的决策边界。
要点：寻找最大间隔
为什么要找最大间隔？
1、感官上它是安全的（确实是，毋庸置疑）
2、假如在边界的位置发生一个很小的错误，边界的点在垂直方向上被颠倒了，这个小小的错误就会导致我们的分类错误。
3、交叉验证很容易。
4、我们数学上求一根直线到一个圆最安全的距离，不就是找那个圆上那个最近的那个点，要求这个点距离直线尽可能的远。实在不行你就看第五点。
5、前人的经验，加上本人的经验告诉你，就该这么干！
OK，我们如何去寻找最大间隔？
还记得我们在高中的时候学过的点到直线的距离公式吗？
在这里我们也同样使用，首先我们先要表示分隔超平面，他们的函数间距为：
\(y(x)=w^Tx+b\)
分类的结果表示为：
\(f(x)=sign(w^Tx+b)\) (sign表示>0为1，<0为-1，=0为0)
点到超平面的几何间距：
\(d(x)=(w^Tx+b)/||w||\)
||w||表示w矩阵的二范数=> \(\sqrt{w^T*w}\), 点到超平面的距离也是类似的。
OK，下面我们来使用拉格朗日乘子法来优化我们的求解：
- 类别标签用-1、1，是为了后期方便 \(label*(w^Tx+b)\) 的标识和距离计算；如果 \(label*(w^Tx+b)>0\) 表示预测正确，否则预测错误。
- 现在目标很明确，就是要找到
w和b，因此我们必须要找到最小间隔的数据点，也就是前面所说的支持向量。
- 也就说，让最小的距离取最大.(最小的距离：就是最小间隔的数据点；最大：就是最大间距，为了找出最优超平面--最终就是支持向量)
- 目标函数：\(arg: max_{关于w, b} \left( min[label*(w^Tx+b)]*\frac{1}{||w||} \right) \)
- 如果 \(label*(w^Tx+b)>0\) 表示预测正确，也称
函数间隔，\(||w||\) 可以理解为归一化，也称几何间隔。 - 令 \(label*(w^Tx+b)>=1\)， 因为0～1之间，得到的点是存在误判的可能性，所以要保障 \(min[label*(w^Tx+b)]=1\)，才能更好降低噪音数据影响。
- 所以本质上是求 \(arg: max_{关于w, b} \frac{1}{||w||} \)；也就说，我们约束(前提)条件是: \(label*(w^Tx+b)=1\)
- 新的目标函数求解： \(arg: max_{关于w, b} \frac{1}{||w||} \)
- => 就是求: \(arg: min_{关于w, b} ||w|| \) (求矩阵会比较麻烦，如果x只是 \(\frac{1}{2}*x^2\) 的偏导数，那么。。同样是求最小值)
- => 就是求: \(arg: min_{关于w, b} (\frac{1}{2}*||w||^2)\) (二次函数求导，求极值，平方也方便计算)
- 本质上就是求线性不等式的二次优化问题(求分隔超平面，等价于求解相应的凸二次规划问题)
- 通过拉格朗日乘子法，求二次优化问题
- 假设需要求极值的目标函数 (objective function) 为 f(x,y)，限制条件为 φ(x,y)=M # M=1
- 设g(x,y)=M-φ(x,y) # 临时φ(x,y)表示下文中 \(label*(w^Tx+b)\)
- 定义一个新函数: F(x,y,λ)=f(x,y)+λg(x,y)
- a为λ（a>=0），代表要引入的拉格朗日乘子(Lagrange multiplier)
- 那么： \(L(w,b,\alpha)=\frac{1}{2} * ||w||^2 + \sum_{i=1}^{n} \alpha_i * [1 - label * (w^Tx+b)]\)
- 因为：\(label*(w^Tx+b)>=1, \alpha>=0\) , 所以 \(\alpha*[1-label*(w^Tx+b)]<=0\) , \(\sum_{i=1}^{n} \alpha_i * [1-label*(w^Tx+b)]<=0\)
- 当 \(label*(w^Tx+b)>1\) 则 \(\alpha=0\) ，表示该点为非支持向量
- 相当于求解： \(max_{关于\alpha} L(w,b,\alpha) = \frac{1}{2} *||w||^2\)
- 如果求： \(min_{关于w, b} \frac{1}{2} *||w||^2\) , 也就是要求： \(min_{关于w, b} \left( max_{关于\alpha} L(w,b,\alpha)\right)\)
- 现在转化到对偶问题的求解
- \(min_{关于w, b} \left(max_{关于\alpha} L(w,b,\alpha) \right) \) >= \(max_{关于\alpha} \left(min_{关于w, b}\ L(w,b,\alpha) \right) \)
- 现在分2步
- 先求： \(min_{关于w, b} L(w,b,\alpha)=\frac{1}{2} * ||w||^2 + \sum_{i=1}^{n} \alpha_i * [1 - label * (w^Tx+b)]\)
- 就是求
L(w,b,a)关于[w, b]的偏导数, 得到w和b的值，并化简为：L和a的方程。 - 参考： 如果公式推导还是不懂，也可以参考《统计学习方法》李航-P103<学习的对偶算法>
- 终于得到课本上的公式： \(max_{关于\alpha} \left( \sum_{i=1}^{m} \alpha_i - \frac{1}{2} \sum_{i, j=1}^{m} label_i·label_j·\alpha_i·\alpha_j·<x_i, x_j> \right) \)
- 约束条件： \(a>=0\) 并且 \(\sum_{i=1}^{m} a_i·label_i=0\)
这里我们解释一下SVM的松弛变量，可以参考：https://blog.csdn.net/wusecaiyun/article/details/49659183
之前讨论的情况都是建立在样例线性可分的假设上，当样例线性不可分时，我们可以尝试使用核函数来将特征映射到高维，这样很可能就可分了。然而，映射后我们也不能100%保证可分。那怎么办呢，我们需要将模型进行调整，以保证在不可分的情况下，也能够尽可能地找出分隔超平面。
看下面两张图：
可以看到一个离群点（可能是噪声）可以造成超平面的移动，间隔缩小，可见以前的模型对噪声非常敏感。再有甚者，如果离群点在另外一个类中，那么这时候就是线性不可分了。
这时候我们应该允许一些点游离并在在模型中违背限制条件（函数间隔大于1）。我们设计得到新的模型如下（也称软间隔）：
- 我们知道几乎所有的数据都不那么干净, 通过引入松弛变量来
允许数据点可以处于分隔面错误的一侧。 - 约束条件： \(C>=a>=0\) 并且 \(\sum_{i=1}^{m} a_i·label_i=0\)
- 总的来说：
- \(label*(w^Tx+b) > 1\) and alpha = 0 (在边界外，就是非支持向量)
- \(label*(w^Tx+b) = 1\) and 0< alpha < C (在分割超平面上，就支持向量)
- \(label*(w^Tx+b) < 1\) and alpha = C (在分割超平面内，是误差点 -> C表示它该受到的惩罚因子程度)
- 参考地址：https://www.zhihu.com/question/48351234/answer/110486455
- &i是松弛变量，常量C是
惩罚因子, 表示离群点的权重（用于控制“最大化间隔”和“保证大部分点的函数间隔小于1.0” ） - C值越大，表示离群点影响越大，就越容易过度拟合；反之有可能欠拟合。
- 我们看到，目标函数控制了离群点的数目和程度，使大部分样本点仍然遵守限制条件。
- 例如：正类有10000个样本，而负类只给了100个（C越大表示100个负样本的影响越大，就会出现过度拟合，所以C决定了负样本对模型拟合程度的影响！，C就是一个非常关键的优化点！）
- 这一结论十分直接，SVM中的主要工作就是要求解 alpha.
SMO 高效优化算法（用于训练SVM）
创建一个 alpha 向量并将其初始化为0向量
当迭代次数小于最大迭代次数时(外循环)
对数据集中的每个数据向量(内循环)：
如果该数据向量可以被优化
随机选择另外一个数据向量
同时优化这两个向量
如果两个向量都不能被优化，退出内循环
如果所有向量都没被优化，增加迭代数目，继续下一次循环
- SMO目标：求出一系列 alpha 和 b,一旦求出 alpha，就很容易计算出权重向量 w 并得到分隔超平面。
- SMO思想：是将大优化问题分解为多个小优化问题来求解的。
- SMO原理：每次循环选择两个 alpha 进行优化处理，一旦找出一对合适的 alpha，那么就增大一个同时减少一个。
开始SVM开发：
Step1收集数据：可以使用任意方法。
Step2准备数据：需要数值型数据。
Step3分析数据：有助于可视化分隔超平面。
Step4训练算法：SVM的大部分时间都源自训练，该过程主要实现两个参数的调优。
Step5测试算法：十分简单的计算过程就可以实现。
Step6使用算法：几乎所有分类问题都可以使用SVM，值得一提的是，SVM本身是一个二类分类器，对多类问题应用SVM需要对代码做一些修改。
准备数据：
对文件进行逐行解析，从而得到第行的类标签和整个特征矩阵
训练算法：
参数:
dataMatIn 特征集合
classLabels 类别标签
C 松弛变量(常量值)，允许有些数据点可以处于分隔面的错误一侧。（
控制最大化间隔和保证大部分的函数间隔小于1.0这两个目标的权重。可以通过调节该参数达到不同的结果。）
toler 容错率（是指在某个体系中能减小一些因素或选择对某个系统产生不稳定的概率。）
maxIter 退出前最大的循环次数
返回值:
b 模型的常量值
alphas 拉格朗日乘子
详细代码见：
