第六章 支持向量机(代码)

• SVM算法优缺点

  • 优点:泛化错误率低，计算开销不大，结果易解释。

  • 缺点:对参数调节和和核函数的选择敏感，原始分类器不加修改仅适用于处理二分类问题。

  • 范围:数值型和标称型数据。

• SVM分类(Tip:不讲非线性支持向量机)

  • 线性支持向量机

    • 求解线性支持向量机的过程是凸二次规划问题，所谓凸二次规划问题，就是目标函数是凸的二次可微函数，约束函数为仿射函数（满足f(x)=a*x+b,a,x均为n为向量）。而我们说求解凸二次规划问题可以利用对偶算法--即引入拉格朗日算子，利用拉格朗日对偶性将原始问题的最优解问题转化为拉格朗日对偶问题，这样就将求w，b的原始问题的极小问题转化为求alpha（alpha>=0）的对偶问题的极大问题，即求出alpha，在通过KKT条件求出对应的参数w，b，从而找到这样的间隔最大化超平面，进而利用该平面完成样本分类

  • 近似线性支持向量机

- 当数据集并不是严格线性可分时，即满足绝不部分样本点是线性可分，存在极少部分异常点；这里也就是说存在部分样本不能满足约束条件，此时我们可以引入松弛因子，这样这些样本点到超平面的函数距离加上松弛因子，就能保证被超平面分隔开来；当然，添加了松弛因子sigma，我们也会添加对应的代价项，使得alpha满足0=<alpha<=C

• SMO算法

  • SMO是一种用于训练SVM的强大算法，它将大的优化问题分解为多个小的优化问题来进行求解。而这些小优化问题往往很容易求解，并且对它们进行顺序求解和对整体求解结果是一致的。在结果一致的情况下，显然SMO算法的求解时间要短很多，这样当数据集容量很大时，SMO就是一致十分高效的算法

  • SMO算法的目标是找到一系列alpha和b，而求出这些alpha，我们就能求出权重w，这样就能得到分隔超平面，从而完成分类任务

  • SMO算法的工作原理是：每次循环中选择两个alpha进行优化处理。一旦找到一对合适的alpha，那么就增大其中一个而减少另外一个。这里的"合适",意味着在选择alpha对时必须满足一定的条件，条件之一是这两个alpha不满足最优化问题的kkt条件，另外一个条件是这两个alpha还没有进行区间化处理

  • 对于SMO算法编写，我们采用由简单到复杂的方法，层层递进，完成最终的SMO算法实现，最后通过实际的用例对SVM模型进行训练，并验证准确性

  • 简化版SMO算法

    简化版SMO算法，省略了确定要优化的最佳alpha对的步骤，而是首先在数据集上进行遍历每一个alpha，再在剩余的数据集中找到另外一个alpha，构成要优化的alpha对，同时对其进行优化，这里的同时是要确保公式：Σαilabel(i)=0。所以改变一个alpha显然会导致等式失效，所以这里需要同时改变两个alpha。*

• 核函数

  核函数的目的主要是为了解决非线性分类问题，通过核技巧将低维的非线性特征转化为高维的线性特征，从而可以通过线性模型来解决非线性的分类问题。

• 例子:手写识别

  相较于KNN算法，尽管KNN也能取得不错的效果；但是从节省内存的角度出发，显然SVM算法更胜一筹，因为其不需要保存真个数据集，而只需要其作用的支持向量点，而取得不错的分类效果

由上图可以看出，σ值在取10时取得了最好的分类效果，这也印证了我们上面的叙述。即对于固定的数据集，存在最优的支持向量个数，使得分类错误率最低。支持向量的个数会随着σ值的增大而逐渐减少，但是分类错误率确实一个先降低后升高的过程。即最小的分类错误率并不意味着最少的支持向量个数。

• 小节

  支持向量机是一种分类器，它具有良好的学习能力，并且学到的东西具有很好的拓展性，SMO解决了SVM训练速度慢的原因。

  核函数会将数据从一个低维空间映射到一个高维空间，可以将一个在低维空间中的非线性问题转化成为高维空间下的线性问题来求解

  支持向量机在解决多类问题的时候，需要额外的方法来对其进行扩展，SVM效果也对优化参数和所用核参数中的参数敏感。

代码托管见Github