【十大经典数据挖掘算法】SVM

【十大经典数据挖掘算法】系列

1. C4.5
2. K-Means
3. SVM
4. Apriori
5. EM
6. PageRank
7. AdaBoost
8. kNN
9. Naïve Bayes
10. CART

---

SVM（Support Vector Machines）是分类算法中应用广泛、效果不错的一类。《统计学习方法》对SVM的数学原理做了详细推导与论述，本文仅做整理。由简至繁SVM可分类为三类：线性可分（linear SVM in linearly separable case）的线性SVM、线性不可分的线性SVM、非线性（nonlinear）SVM。

1. 线性可分

对于二类分类问题，训练集T={(x1,y1),(x2,y2),⋯,(xN,yN)}$T=\{(x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)\}$，其类别yi∈{0,1}$y_i\in \{0,1\}$，线性SVM通过学习得到分离超平面（hyperplane）:

w⋅x+b=0$$w\cdot x+b=0$$

以及相应的分类决策函数：

f(x)=sign(w⋅x+b)$$f(x)=sign(w\cdot x+b)$$

有如下图所示的分离超平面，哪一个超平面的分类效果更好呢？

直观上，超平面B1$B_1$的分类效果更好一些。将距离分离超平面最近的两个不同类别的样本点称为支持向量（support vector）的，构成了两条平行于分离超平面的长带，二者之间的距离称之为margin。显然，margin更大，则分类正确的确信度更高（与超平面的距离表示分类的确信度，距离越远则分类正确的确信度越高）。通过计算容易得到：

margin=2∥w∥$$margin=\frac{2}{\Vert w\Vert }$$

从上图中可观察到：margin以外的样本点对于确定分离超平面没有贡献，换句话说，SVM是有很重要的训练样本（支持向量）所确定的。至此，SVM分类问题可描述为在全部分类正确的情况下，最大化2∥w∥$\frac{2}{\Vert w\Vert }$（等价于最小化12∥w∥2$\frac{1}{2}\Vert w{\Vert }^2$）；线性分类的约束最优化问题：

minw,b12|w|2s.t.yi(w⋅xi+b)−1≥0(1)(2)$$\begin{array}{}\text{(1)}& & \underset{w,b}{min}\frac{1}{2}|w{|}^2\text{(2)}& & s.t.y_i(w\cdot x_i+b)-1\ge 0\end{array}$$

对每一个不等式约束引进拉格朗日乘子（Lagrange multiplier）αi≥0,i=1,2,⋯,N${\alpha }_i\ge 0,i=1,2,\cdots ,N$；构造拉格朗日函数（Lagrange function）：

L(w,b,α)=12|w|2−∑i=1Nαi[yi(w⋅xi+b)−1](3)$$\begin{array}{}\text{(3)}& L(w,b,\alpha )=\frac{1}{2}|w{|}^2-\sum _{i=1}^N{\alpha }_i[y_i(w\cdot x_i+b)-1]\end{array}$$

根据拉格朗日对偶性，原始的约束最优化问题可等价于极大极小的对偶问题：

maxαminw,bL(w,b,α)$$\underset{\alpha }{max}\underset{w,b}{min}L(w,b,\alpha )$$

将L(w,b,α)$L(w,b,\alpha )$对w,b$w,b$求偏导并令其等于0，则

∂L∂w=w−∑i=1Nαiyixi=0⇒w=∑i=1Nαiyixi∂L∂b=∑i=1Nαiyi=0⇒∑i=1Nαiyi=0$$\begin{array}{rl}& \frac{\mathrm{\partial }L}{\mathrm{\partial }w}=w-\sum _{i=1}^N{\alpha }_i{y}_i{x}_i=0\Rightarrow w=\sum _{i=1}^N{\alpha }_i{y}_i{x}_i\\ & \frac{\mathrm{\partial }L}{\mathrm{\partial }b}=\sum _{i=1}^N{\alpha }_i{y}_i=0\Rightarrow \sum _{i=1}^N{\alpha }_i{y}_i=0\end{array}$$

将上述式子代入拉格朗日函数(3)$\text{(3)}$中，对偶问题转为

maxα−12∑i=1N∑j=1Nαiαjyiyj(xi⋅xj)+∑i=1Nαi$$\underset{\alpha }{max}-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\cdot x_j)+\sum _{i=1}^N{\alpha }_i$$

等价于最优化问题：

minαs.t.12∑i=1N∑j=1Nαiαjyiyj(xi⋅xj)−∑i=1Nαi∑i=1Nαiyi=0αi≥0,i=1,2,⋯,N(4)(5)(6)$$\begin{array}{}\text{(4)}& \underset{\alpha }{min}& \frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\cdot x_j)-\sum _{i=1}^N{\alpha }_i\text{(5)}& s.t.& \sum _{i=1}^N{\alpha }_i{y}_i=0\text{(6)}& & {\alpha }_i\ge 0,i=1,2,\cdots ,N\end{array}$$

线性可分是理想情形，大多数情况下，由于噪声或特异点等各种原因，训练样本是线性不可分的。因此，需要更一般化的学习算法。

2. 线性不可分

线性不可分意味着有样本点不满足约束条件(2)$\text{(2)}$，为了解决这个问题，对每个样本引入一个松弛变量ξi≥0${\xi }_i\ge 0$，这样约束条件变为：

yi(w⋅xi+b)≥1−ξi$$y_i(w\cdot x_i+b)\ge 1-{\xi }_i$$

目标函数则变为

minw,b,ξ12∥w∥2+C∑i=1Nξi$$\underset{w,b,\xi }{min}\frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^N{\xi }_i$$

其中，C$C$为惩罚函数，目标函数有两层含义：

• margin尽量大，
• 误分类的样本点计量少

C$C$为调节二者的参数。通过构造拉格朗日函数并求解偏导（具体推导略去），可得到等价的对偶问题：

minα12∑i=1N∑j=1Nαiαjyiyj(xi⋅xj)−∑i=1Nαi(7)$$\begin{array}{}\text{(7)}& \underset{\alpha }{min}\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\cdot x_j)-\sum _{i=1}^N{\alpha }_i\end{array}$$

s.t.∑i=1Nαiyi=00≤αi≤C,i=1,2,⋯,N(8)(9)$$\begin{array}{}\text{(8)}& s.t.& \sum _{i=1}^N{\alpha }_i{y}_i=0\text{(9)}& & 0\le {\alpha }_i\le C,i=1,2,\cdots ,N\end{array}$$

与上一节中线性可分的对偶问题相比，只是约束条件αi${\alpha }_i$发生变化，问题求解思路与之类似。

3. 非线性

对于非线性问题，线性SVM不再适用了，需要非线性SVM来解决了。解决非线性分类问题的思路，通过空间变换ϕ$\varphi$（一般是低维空间映射到高维空间x→ϕ(x)$x\to \varphi (x)$）后实现线性可分，在下图所示的例子中，通过空间变换，将左图中的椭圆分离面变换成了右图中直线。

在SVM的等价对偶问题中的目标函数中有样本点的内积xi⋅xj$x_i\cdot x_j$，在空间变换后则是ϕ(xi)⋅ϕ(xj)$\varphi (x_i)\cdot \varphi (x_j)$，由于维数增加导致内积计算成本增加，这时核函数（kernel function）便派上用场了，将映射后的高维空间内积转换成低维空间的函数：

K(x,z)=ϕ(x)⋅ϕ(z)$$K(x,z)=\varphi (x)\cdot \varphi (z)$$

将其代入一般化的SVM学习算法的目标函数(7)$\text{(7)}$中，可得非线性SVM的最优化问题：

minαs.t.12∑i=1N∑j=1NαiαjyiyjK(xi,xj)−∑i=1Nαi∑i=1Nαiyi=00≤αi≤C,i=1,2,⋯,N(10)(11)(12)$$\begin{array}{}\text{(10)}& \underset{\alpha }{min}& \frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i,x_j)-\sum _{i=1}^N{\alpha }_i\text{(11)}& s.t.& \sum _{i=1}^N{\alpha }_i{y}_i=0\text{(12)}& & 0\le {\alpha }_i\le C,i=1,2,\cdots ,N\end{array}$$

4. 参考资料

[1] 李航，《统计学习方法》.
[2] Pang-Ning Tan, Michael Steinbach, Vipin Kumar, Introduction to Data Mining.