机器学习系列（三十二）——Support Vector Mach

作者: Ice_spring | 来源:发表于2019-07-26 20:05 被阅读15次

本篇主要内容：SVM，Hard Margin SVM，Soft Margin SVM

什么是支撑向量机

支撑向量机（Support Vector Machine）作为非常经典的机器学习算法，即可以解决分类问题，也可以解决回归问题。这里首先介绍SVM 是如何解决分类问题的。
SVM是一种二分类模型，它的目的是寻找一个超平面（曲面）来对样本进行分割，分割的原则是间隔最大化，最终转化为一个凸二次规划问题来求解。由简至繁的模型包括：

当训练样本线性可分时，即样本有严格的直线决策边界时，对于每一个训练样本都必须给出正确分类，通过硬间隔最大化，学习一个线性可分SVM（Hard Margin SVM）；
当训练样本（近似）线性可分时，可能会有一些不太好的噪音点，为了不影响模型泛化能力，通过软间隔最大化，允许模型有一定的容错能力，学习一个有容错能力的线性SVM（Soft Margin SVM）；
当训练样本线性不可分时，通过核技巧和软间隔最大化，学习一个非线性SVM。

本篇主要介绍线性可分问题。
一般的分类问题都可以得到一个决策边界，这个决策边界可以一定程度上将两个类别分开，不过这样的决策边界往往不是唯一的，这种决策边界不唯一的问题叫做不适定问题。

决策边界不唯一

Logistic回归为了解决这种不适定问题，定义了一个以概率为基础的损失函数，最小化这个损失函数最终得到唯一的决策边界，这个决策边界是由所有的训练样本所决定的。
SVM的思路略有不同，我们都知道机器学习的最终目的是寻找泛化能力最好的模型，以让模型能在未知数据上有很好的预测能力，对于下面这种情况：

二分类

在训练集上，虽然决策边界很好地将两个类别完全分开，但是直观来看，靠近蓝色点群的红色点在实际中被分为蓝色可能会更加合理些。也就是这个决策边界泛化效果是不够好的，因为决策边界离其中一个类别太近了。那什么样的决策边界更好呢？显然我们希望离决策边界最近的点能离决策边界的距离尽可能的远，也就是决策边界即要离红色的点远也要离蓝色的点远，于是我们得到这样的决策边界：

SVM

这就是SVM的基本思路，为了让模型的泛化效果更好，并没有寄希望在数据预处理阶段，也没有对模型进行正则化，这个考量直接放到了算法内部。SVM是有很强的数学和统计学理论支撑的，我们可以严格证明出在一个不适定的问题中使用SVM找到的决策边界具有很好的泛化能力。

支持向量

离决策边界最近的点就被称之为支撑向量，最优的决策边界就是支撑向量包含的区域中心，这就是支撑向量机名称的由来，它是由支撑向量来确定的决策边界。设支撑向量到决策边界的距离为d，支撑向量之间的距离为margin，显然margin=2d，SVM最终就是要最大化margin，此时SVM已经是一个最优化问题，可以用数学的方式求解。

SVM背后的最优化

既然SVM的目的是最大化margin，也就是最大化d，我们就来看一下如何最优化d，设决策边界的直线方程为：
$W_{T}x+b=0$

所有的样本点必都满足：
$\begin{cases} \frac{W^Tx^{(i)}+b}{||W||} \geq +d& y^{(i)}= 1 \\ \frac{W^Tx^{(i)}+b}{||W||} \leq -d& y^{(i)}= -1 \end{cases}$

即：
$\begin{cases} \frac{W^Tx^{(i)}+b}{||W||d} \geq +1& y^{(i)}= 1 \\ \frac{W^Tx^{(i)}+b}{||W||d} \leq -1& y^{(i)}= -1 \end{cases}$

由于分母是常数，于是：
$\begin{cases} W_{d}^Tx^{(i)}+b_d \geq +1& y_i= +1 \\ W_d^Tx^{(i)}+b_d \leq -1& y_i= -1\end{cases}$

于是三条直线的方程分别化为：
$W_{d}^Tx^{(i)}+b_d = 1$ ， $W_{d}^Tx^{(i)}+b_d = 0$ ， $W_{d}^Tx^{(i)}+b_d = -1$ 。

为了表示方便，现在用W和b代替上面出现的 $W_d$ 和 $b_d$ ，只是要注意，这里使用的W和b和最开始设的已经不是一个W和b。
再将类别考虑进约束调节，即：
$y^{(i)}(W^Tx^{(i)}+b)\geq1$

我们的目标最优化式为：
$max\frac{|W^Tx^{(i)}+b|}{||W||}$

又由于支撑向量带入后分子是1，于是即求 $min||W||$ ，为了方便求导操作，最终的目标函数即是：
$min\frac{1}{2} ||W||^2$

约束条件：
$s.t.y^{(i)}(W^Tx^{(i)}+b)\geq1$

这是一个典型的凸规划，运筹学有它详细求解证明过程，对证明过程感兴趣的可以翻阅运筹学教材，这里略去。

Soft Margin SVM与SVM的正则化

前面我们推导了SVM的数学最优化形式，不过那是在严格线性可分情况下的，对于一些并非严格线性可分情况或者线性可分但可能受outliner影响的情况，我们需要有一定容错能力的SVM模型：

Soft SVM

于是Soft Margin SVM被提出，所谓Soft Margin SVM就是让SVM有一定的容错能力，也就是让约束条件宽松一些：
$s.t.y^{(i)}(W^Tx^{(i)}+b)\geq1-\eta_i，\eta_i\geq0$

但是为了不让 $\eta_i$ 离谱的大，我们的目标函数加上一项 $\eta_i$ 的和：
$min\frac{1}{2} ||W||^2+C\sum_{i=1}^{m}\eta_i$

一定程度上这可以看作SVM的L1正则化，C是一个超参，C越大容错空间越小，相应的也有L2正则。这就是Soft Margin SVM。

sklearn中的SVM

接下来在鸢尾花数据集上使用SVM算法来直观感受一下SVM，由于SVM的逻辑稍微复杂，这里不再进行低层编写，直接使用sklearn中封装好的SVM。导入数据集：

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
iris = datasets.load_iris()

x=iris.data
y=iris.target
'''暂时只处理二分类问题，而且为方便可视化，只取前两个特征'''
x=x[y<2,:2]
y=y[y<2]

可视化我们的数据集：

plt.scatter(x[y==0,0],x[y==0,1],color='red')
plt.scatter(x[y==1,0],x[y==1,1],color='blue')
plt.show()

iris_2

使用SVM和使用knn算法一样，要首先对数据特征进行标准化处理：

from sklearn.preprocessing import StandardScaler
standardScaler = StandardScaler()
standardScaler.fit(x)
x_standard = standardScaler.transform(x)

这里只是展示SVM算法的分类效果，所以不进行train_test_split，直接对X整体进行fit：

'''调用线性SVM'''
from sklearn.svm import LinearSVC#C是classifier
svc = LinearSVC(C=1e9)#C越大越偏向hard_SVM
svc.fit(x_standard,y)

SVC

绘图查看决策边界：

'''绘图查看决策边界'''
def plot_decision_boundary(model,axis):
    x0,x1=np.meshgrid(
        np.linspace(axis[0],axis[1],int((axis[1]-axis[0])*100)).reshape(-1,1),
        np.linspace(axis[2],axis[3],int((axis[3]-axis[2])*100)).reshape(-1,1)
    )
    x_new=np.c_[x0.ravel(),x1.ravel()]
    y_predict=model.predict(x_new)
    zz=y_predict.reshape(x0.shape)
    from matplotlib.colors import ListedColormap
    custom_cmap=ListedColormap(['#EF9A9A','#FFF59D','#90CAF9'])
    plt.contourf(x0,x1,zz,linewidth=5,cmap=custom_cmap)

plot_decision_boundary(svc,axis=[-3,3,-3,3])
plt.scatter(x_standard[y==0,0],x_standard[y==0,1])
plt.scatter(x_standard[y==1,0],x_standard[y==1,1])
plt.show()

决策边界

由于C比较大，这里每个样本都被正确分类，这几乎就是一个Hard Margin SVM，接下来调节参数C，在C=0.01情况下训练一个SVM，并绘制决策边界：

'''修改C'''
svc2 = LinearSVC(C=0.01)
svc2.fit(x_standard,y)
plot_decision_boundary(svc2,axis=[-3,3,-3,3])
plt.scatter(x_standard[y==0,0],x_standard[y==0,1])
plt.scatter(x_standard[y==1,0],x_standard[y==1,1])
plt.show()

soft决策边界

可以看到C变小后，该模型有一个蓝色的点被错误分类为橙色，此时SVM有了一定的容错能力。
接下来绘制由支撑向量决定的平行于决策边界的直线，直观看一下margin，首先给出SVM求解的系数和截距：

系数和截距

修改绘图函数，绘制margin：

'''绘图查看决策区域'''
def plot_svc_decision_boundary(model,axis):
    x0,x1=np.meshgrid(
        np.linspace(axis[0],axis[1],int((axis[1]-axis[0])*100)).reshape(-1,1),
        np.linspace(axis[2],axis[3],int((axis[3]-axis[2])*100)).reshape(-1,1)
    )
    x_new=np.c_[x0.ravel(),x1.ravel()]
    y_predict=model.predict(x_new)
    zz=y_predict.reshape(x0.shape)
    from matplotlib.colors import ListedColormap
    custom_cmap=ListedColormap(['#EF9A9A','#FFF59D','#90CAF9'])
    plt.contourf(x0,x1,zz,linewidth=5,cmap=custom_cmap)
    w = model.coef_[0]
    b = model.intercept_[0]
    #w0*x0+w1*x1+b=0
    #x1 = -w0/w1*x0-b/w1
    plot_x = np.linspace(axis[0],axis[1],200)
    up_y = -w[0]/w[1] * plot_x - b/w[1] + 1/w[1]
    down_y = -w[0]/w[1] * plot_x - b/w[1] - 1/w[1]
    
    up_index = (up_y>=axis[2]) & (up_y<=axis[3])
    down_index = (down_y>=axis[2]) & (down_y<=axis[3])
    
    plt.plot(plot_x[up_index],up_y[up_index],color='black')
    plt.plot(plot_x[down_index],down_y[down_index],color='black')

svc1(Hard)对应的margin区域：

plot_svc_decision_boundary(svc,axis=[-3,3,-3,3])
plt.scatter(x_standard[y==0,0],x_standard[y==0,1])
plt.scatter(x_standard[y==1,0],x_standard[y==1,1])
plt.show()

svc1

svc2(Soft)对应的margin区域：

plot_svc_decision_boundary(svc2,axis=[-3,3,-3,3])
plt.scatter(x_standard[y==0,0],x_standard[y==0,1])
plt.scatter(x_standard[y==1,0],x_standard[y==1,1])
plt.show()

svc2

并非所有分类问题都是线性可分的，对于非线性可分的问题，我们将在下篇介绍。

机器学习系列（三十二）——Support Vector Mach

什么是支撑向量机

SVM背后的最优化

Soft Margin SVM与SVM的正则化

sklearn中的SVM

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

机器学习、深度学习与人工智能

人工智能/模式识别/机器学习精华专题

大数据，机器学习，人工智能

机器学习与数据挖掘