数据挖掘十大经典算法(3)：SVM支持向量机

        支持向量机（SVM，Support Vector Machine）是具有深厚数学原理支持的分类算法，本文只讨论0/1分类问题。SVM的基本概念如下图所示。将观测的每一个特征看做一个维度，n个特征就组成n个维度空间。示意图中n=2。在这个n维空间中，如果我们能够找到一个线性分割平面，将观测分离开来，称样本线性可分。我们先讨论线性可分的情况，然后再讨论如何处理线性不可分的情况。

线性可分情况
    对于一个分割平面，我们定义正例或负例与平面的最小距离为间隔（我们要求平面位于正例和负例的中央，是的正例到平面的最小距离等于负例到平面的最小距离）。一个好的分割平面，应该使间隔越大越好。上图中，右边的分割平面就比左边的好。落在途中虚线上的样本点称为支持向量。
    正例属于类别1，标示为+1，负例属于类别0，标示为-1。则分割平面的表达式可以获得，具体式子见下图中的红实线。为了能够获得唯一的w和b，我们需要设定一个约束条件，这里的假设是支持向量满足如图中红色虚线所示的方程。在此约束下，间隔可以用下图的右下角式子表示。

     现在我们可以用数学规划的语言描述支持向量机的分类问题。我们的目标是最大化margin，约束是上图两条虚线内部没有观测。具体的模型如下图所示。
   

    这样一来，SVM分类问题转化为二次规划。该问题的最优解需要满足K-T条件（库恩-塔克条件，参看运筹学的非线性规划）。K-T条件的内容大致如下：目标函数关于w和b的梯度需要是支持向量约束梯度的线性组合。通过K-T条件，可以发现w可以用向量的内积表示。原来的思路是：新来的观测要分类，首先根据w和b做一次线性运算，然后看求解结果，若大于0，属于类别1，若小于0，属于类别0.现在的思路变为：根据支持向量约束梯度的线性组合系数，只要将新观测和训练数据中的支持向量做内积即可。

线性不可分情况
    线性不可分情况有两种做法。第一种是把原来的低维空间向高维空间映射，使得数据在高维空间中变为线性可分。这时候可以给予上面说的内积性质，利用核函数，仍然在低维空间做运算，达到高维空间做运算的效果，降低算法复杂度。
    然而，这种向高维映射的方法不能保证百分百成功，因此还引入了软间隔的概念，即允许在margin内部出现离群点，但在目标函数中加入惩罚函数，离群点越多程度越高，惩罚越厉害。
   

关于应用K-T条件得到内积性质、核函数、软间隔，可以参考网站：http://www.cnblogs.com/jerrylead/

本文所采用图片均来自清华大学计算机系王建勇老师的课程《数据挖掘：原理与算法》

http://dbgroup.cs./wangjy/DM/DataMining.html