机器学习(八)：SVM支持向量机原理及案例分析

2019-12-23 本文已影响0人风之舟

一、简介

支持向量机(Support Vector Machine,SVM)是一类按监督学习方式对数据进行二元分类的广义线性分类器，其决策边界是对学习样本求解的最大边距超平面。

它的目的是寻找一个超平面来对样本进行分割，分割的原理则是间隔最大化，最终转化为一个凸二次规划问题来求解，由简至繁的模型包括：

当训练样本线性可分时，通过硬间隔最大化，学习一个线性可分支持向量机
当训练样本近似线性可分时，通过软间隔最大化，学习一个线性支持向量机
当训练样本线性不可分时，通过核技巧和软间隔最大化，学习一个非线性支持向量机

二、原理解析

1、点到超平面的距离

假设有一个超平面，在平面外有一个点X，我们要求点X到超平面的距离dist(x,h)，但是直接求不好求，我们设超平面上有两个点(x',x'')，即

我们也可以得到：
我们计算一下点X到点X'之间的距离，我们求出x与x'之间的距离然后乘以平面的法向量就得到了dist(x,h)，即点x到超平面的距离(线性代数里面的定理)。[1]：

2、样本分类

我们假设数据集 $(X_{1},Y_{1}),(X_{2},Y_{2}),...,(X_{n},Y_{n}),其中y(x)=w^T\psi(x)+b，\psi(x)是核函数，后面会补充$ ，我们规定Y为样本的类别：
当X为正例时，Y=+1；当X为负例时，Y=-1；
$y(x_{i})> 0 <=> y_{i} = +1$
$y(x_{i})< 0 <=> y_{i} = -1$
可以推出：
$y_{i}·y(x_{i}) >0$
我们的优化目标是找到一条线(求w和b)，使得离该线最近的点能够距离平面最远，这是 SVM非常重要的原理。我们可以将公式[1]的绝对值通过乘 $y_{i}$ 去掉，因为 $y_{i}只能取1或-1，且y_{i}·y(x_{i})>0$ ，这时公式变成了， $dist = \frac{y_{i}(w^T·\psi(x_{i})+b)}{|w|}$ ,结果肯定是大于0的，这时我们继续做一个假设（大于0肯定是一个数值，我们这里假设它大于1，为了计算方便），即对于线(w,b)可以通过放缩使得其结果值|Y| >= 1, $y_{i}·(w^T·\psi(x_{i})+b) \geq 1$ ,最终我们的目标就是 $argmax \lbrace \frac{1}{|w|} min[y_{i}·(w^T·\psi (x_{i})+b)] \rbrace$
我们的目标函数就是， $arg max \frac{1}{|w|},且y_{i}(w^T·\psi (x_{i})+b) \geq1$ 转成求最小值 $min_{w,b}\frac{1}{2}w^2且y_{i}(w^T·\psi (x_{i})+b) \geq1$

3、拉格朗日乘数法求解目标函数

我们的目的是求出 $w$ 和 $b$ ,这时我们引入拉格朗日乘数法求解， $min f(x)$ $s.t. g_{i}(x)\leq0,i=1,2,...,m$

$L(w,b,\alpha) = \frac{1}{2}|w|^2 - \sum_{i=1}^{n}\alpha_{i}(y_{i}·(w^T·\psi(x_{i})+b)-1)$
我们利用对偶问题，转换一下求解思路，
$min_{w,b} max_{\alpha}L(w,b,\alpha) \rightarrow max_{\alpha}min_{w,b}L(w,b,\alpha)$
分别对w和b求偏导，分别得到两个条件：
[2] $\frac{\partial{L}}{\partial{w}}=0 \Rightarrow w = \sum_{i=1}^{n} \alpha_{i}y_{i}\psi(x_{n})$
[3] $\frac{\partial{L}}{\partial{b}}=0 \Rightarrow 0 = \sum_{i=1}^{n} \alpha_{i}y_{i}$
$L(w,b,\alpha) = \frac{1}{2}|w|^2 - \sum_{i=1}^{n}\alpha_{i}(y_{i}·(w^T·\psi(x_{i})+b)-1)$
$=\frac{1}{2}w^Tw-w^T\sum_{i=1}^{n}\alpha_{i}y_{i}\psi(x_{i})-b\sum_{i=1}^{n}\alpha_{i}y_{i}+\sum_{i=1}^{n}\alpha_{i}$ 分别将[2][3]式代入化简可得， $=\sum_{i=1}^{n}-\frac{1}{2}(\sum_{i=1}^{n}\alpha_{i}y_{i}\psi(x_{i}))^T\sum_{i=1}^{n}\alpha_{i}y_{i}\psi(x_{i})$
$=\sum_{i=1}^{n}\alpha_{i}-\frac{1}{2}\sum_{i=1,j=1}^{n}\alpha_{i}\alpha_{j}y_{i}y_{j}\psi^T(x_{i})\psi(x_{j})$ 这时我们完成了第一步的求解 $min_{w,b}L(w,b,\alpha)!$
继续对 $\alpha$ 求极大值， $\begin{cases} max\sum_{i=1}^{n}\alpha_{i}-\frac{1}{2}\sum_{i=1,j=1}^{n}\alpha_{i}\alpha_{j}y_{i}y_{j}\psi(x_{i})\psi(x_{j})\\ \sum_{i=1}^{n} \alpha_{i}y_{i}= 0 \\ \alpha_{i} \geq 0 \end{cases}$ 极大值转换求极小值，
[4] $\begin{cases} min\frac{1}{2}\sum_{i=1,j=1}^{n}\alpha_{i}\alpha_{j}y_{i}y_{j}\psi(x_{i})\psi(x_{j})-\sum_{i=1}^{n}\alpha_{i}\\ \sum_{i=1}^{n} \alpha_{i}y_{i}= 0 \\ \alpha_{i} \geq 0 \end{cases}$

4、实例求解

已知一个如图所示的训练数据集，其正例点是 $x_{1}=(3,3)^T,x_{2}=(4,3)^T$ ,负例点是 $x_{3}=(1,1)^T$ ,试求最大间隔分离超平面。

样本正例用1表示，负例用-1表示：我们带入[4]式中，

化简后的结果为：
我们将代入后分别对参数进行求导得：不符合我们之前的条件，所以最终的解应该为边界上的点，当 (舍去)，当此时,所以最小值在(0.25,0,0.25)处取得。我们由[2]可知，

所以平面方程为：
我们计算出,通过上图我们也发现，并非边界点，最终计算的也跟它无关，这里我们就发现所谓的支持向量机是由边界上的点所支撑起来的，那么我们就把边界上的点叫做支持向量！支持向量：真正发挥作用的数据点， $\alpha$ 值不为0的点。

5、软间隔

通过上图发现，在构建决策边界的过程中，如果某一个点比较特殊(离群点)，我们的边界会为了满足它而把隔离带做的很小，这样并不符合我们的预期，为了解决这种问题，我们引入松弛因子:这样我们的目标函数就变成了，

当C趋近于无穷大时：意味着分类严格不能有错误(C越大，为了求min,则 $\xi_{i}$ 越小，此时1- $\xi_{i}$ 就越大)
当C趋近于很小时：意味着可以有更大的错误容忍，C是我们需要指定的一个参数
再进入拉格朗日乘数法后，结果就变成了，
$L(w,b,\xi,\alpha,\mu)=\frac{1}{2}|w|^2+C\sum_{i=1}^{n}\xi_{i}-\sum_{i=1}^{n}\alpha_{i}(y_{i}(w·x_{i}+b)-1+\xi_{i})-\sum_{i=1}^{n}\mu_{i}\xi_{i}$
分别对 $w,b,\xi$ 求偏导，
$w=\sum_{i=1}^{n}\alpha_{i}y_{i}\psi(x_{n})$
$0=\sum_{i=1}^{n}\alpha_{i}y_{i}$
$C-\alpha_{i}-\mu_{i}=0$
最后利用对偶问题进行化简后的结果跟之前一样，只是 $\alpha_{i}$ 的取值范围变成了 ${0 \leq \alpha_{i} \leq C}$

6、核函数

如果数据非常复杂，在低维中很难进行区分，我们可以将数据映射到高维空间。这样特征信息就更多了，决策的边界也更容易建立。核函数的目的就是将低维数据映射到高维数据上。

这里我们要将数据的特征进行高维的映射，但是问题也来了，这样的计算复杂度是不是也上来了呀！其实是这个样子的SVM在数学上有这样一个巧合，我们可以把高维特征的内积在低维当中直接计算好然后做映射也是一样，恰好解决计算的问题！
这里我们再强调一下，在求目标函数的过程中，我们有求内积的操作，但是维数过大，在高维上求内积的计算量非常大，SVM在数学上有一个特性：在低维上内积，用内积的结果做转换，相当于把数据在高维上做内积，结果是一样的。
我们常用的是高斯核函数：

高斯核函数的原理就是对于每一个样本，如果是正例，我们就用高斯分布(正态分布)向上画，如果是负例我们往下画，从而可以将正负例样本分开。
SVM有很多核函数可以帮助我们将数据进行映射，这也是SVM的厉害之处。

三、案例分析

这里我们使用的数据集是sklearn包自带的人脸数据集fetch_lfw_people，算法也是sklearn中封装好的算法包，我们先来看一下API:from sklearn.svm import SVC这里面的参数有：
svc(C=1.0, kernel='rbf', degree=3, gamma='auto_deprecated', coef0=0.0, shrinking=True, probability=False,tol=1e-3, cache_size=200, class_weight=None,verbose=False, max_iter=-1, decision_function_shape='ovr',random_state=None)

C:惩罚系数
用来控制损失函数的惩罚系数，这个我们在公式中讲过。
kernel 核函数
参数选择有RBF, Linear, Poly, Sigmoid，precomputed或者自定义一个核函数, 默认的是"RBF"，即径向基核，也就是高斯核函数；而Linear指的是线性核函数，Poly指的是多项式核，Sigmoid指的是双曲正切函数tanh核；
degree
当指定kernel为'poly'时，表示选择的多项式的最高次数，默认为三次多项式；若指定kernel不是'poly'，则忽略，即该参数只对'poly'有用
gamma：核函数系数
该参数是rbf，poly和sigmoid的内核系数；默认是'auto',表示模型复杂度，gamma越大，σ越小，使得高斯分布又高又瘦，造成模型只能作用于支持向量附近，可能导致过拟合；反之，gamma越小，σ越大，高斯分布会过于平滑，在训练集上分类效果不佳，可能导致欠拟合
coef0：核函数常数值(y=kx+b中的b值)
只有‘poly’和‘sigmoid’核函数有，默认值是0。
shrinking：是否进行启发式
如果能预知哪些变量对应着支持向量，则只要在这些样本上训练就够了，其他样本可不予考虑，这不影响训练结果，但降低了问题的规模并有助于迅速求解。进一步，如果能预知哪些变量在边界上(即a=C)，则这些变量可保持不动，只对其他变量进行优化，从而使问题的规模更小，训练时间大大降低。这就是Shrinking技术。 Shrinking技术基于这样一个事实：支持向量只占训练样本的少部分，并且大多数支持向量的拉格朗日乘子等于C。
probability：是否使用概率估计，默认是False
必须在 fit( ) 方法前使用，该方法的使用会降低运算速度。
tol：残差收敛条件，默认是0.0001
即容忍1000分类里出现一个错误，与LR中的一致；误差项达到指定值时则停止训练。
cache_size 缓冲大小，用来限制计算量大小，默认是200M。
class_weight：{dict, ‘balanced’}，字典类型或者'balance'字符串。
权重设置，正类和反类的样本数量是不一样的，这里就会出现类别不平衡问题，该参数就是指每个类所占据的权重，默认为1，即默认正类样本数量和反类一样多，也可以用一个字典dict指定每个类的权值，或者选择默认的参数balanced，指按照每个类中样本数量的比例自动分配权值。
verbose：是否启用详细输出。
在训练数据完成之后，会把训练的详细信息全部输出打印出来，可以看到训练了多少步，训练的目标值是多少；但是在多线程环境下，由于多个线程会导致线程变量通信有困难，因此verbose选项的值就是出错，所以多线程下不要使用该参数。
max_iter：最大迭代次数，默认是-1，即没有限制。
这个是硬限制，它的优先级要高于tol参数，不论训练的标准和精度达到要求没有，都要停止训练。
decision_function_shape
原始的SVM只适用于二分类问题，如果要将其扩展到多类分类，就要采取一定的融合策略，这里提供了三种选择。‘ovo’ 一对一，为one v one，即将类别两两之间进行划分，用二分类的方法模拟多分类的结果，决策所使用的返回的是（样本数，类别数*(类别数-1)/2）； ‘ovr’ 一对多，为one v rest，即一个类别与其他类别进行划分，返回的是(样本数，类别数)，或者None，就是不采用任何融合策略。默认是ovr，因为此种效果要比oro略好一点。
random_state
在使用SVM训练数据时，要先将训练数据打乱顺序，用来提高分类精度，这里就用到了伪随机序列。如果该参数给定的是一个整数，则该整数就是伪随机序列的种子值；如果给定的就是一个随机实例，则采用给定的随机实例来进行打乱处理；如果啥都没给，则采用默认的 np.random实例来处理。
这里我们需要用的所有包，

from sklearn.datasets import fetch_lfw_people
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split
from sklearn.decomposition import PCA
from sklearn.pipeline import make_pipeline
from sklearn.svm import SVC
from sklearn.model_selection import GridSearchCV
from sklearn.metrics import classification_report
from sklearn.metrics import confusion_matrix
import seaborn as sns

接下来，我们进行案例分析，首先先来看一下数据长什么样，

def svm():
    """
    SVM进行简单人脸分类
    :return:
    """
    #获取数据集
    faces =fetch_lfw_people(min_faces_per_person=60)
    print(faces.target_names)
    print(faces.images.shape)
    # 图形
    fig,ax=plt.subplots(3,5)
    for i,axi in enumerate(ax.flat):
        axi.imshow(faces.images[i],cmap='bone')
        axi.set(xticks=[],yticks=[],xlabel=faces.target_names[faces.target[i]])
    plt.show()
    return None

if __name__ == "__main__":
    svm()

接下来，我们划分数据集，由于像素点过多，我们使用PCA进行降维，这里我们先对PCA,SVC进行实例化，

#每个图的大小是[62x47]
    #将数据集划分为测试集与训练集
    x_train,y_train,x_test,y_test = train_test_split(faces.data,faces.target,random_state=40)
    #
    #使用PCA降维
    #我们降维成150维
    # 　whiten： 白化。所谓白化，就是对降维后的数据的每个特征进行标准化，让方差都为1。
    # random_state:伪随机数发生器的种子,在混洗数据时用于概率估计
    pca = PCA(n_components=150,whiten=True,random_state=42)
    #实例化SVM
    svc = SVC(kernel='rbf',class_weight='balanced')

然后我们使用sklearn包中pipeline模块结合PCA和SVC对数据进行处理，它提供了两种模式：串行化和并行化，这里我们进行串行化就可以，由于两种算法参数选择较多，我们使用交叉验证的方式选择最优的参数。

    model = make_pipeline(pca,svc)

    #交叉验证确定系数
    param = {'svc__C':[1,5,10],
             'svc__gamma':[0.0001,0.0005,0.001]}
    grid = GridSearchCV(model,param_grid =param)
    grid.fit(x_train,x_test)
    print(grid.best_params_)

我们使用最后的参数模型进行预测，并画图像显示，黑色代表正确，红色代表错误。

    model=grid.best_estimator_
    yfit = model.predict(y_train)
    print(yfit.shape)

    #算法分类之后的图形
    fig,ax=plt.subplots(4,6)
    for i,axi in enumerate(ax.flat):
        axi.imshow(y_train[i].reshape(62,47),cmap='bone')
        axi.set(xticks=[],yticks=[])
        axi.set_ylabel(faces.target_names[yfit[i]].split()[-1],
                       color='black' if yfit[i] == y_test[i] else 'red')

    fig.suptitle('Predicted Names:Incorrect Labels in Red',size=14)
    plt.show()

我们也可以看一下实验的精确率和召回率，以及混淆矩阵。

    print(classification_report(y_test,yfit,target_names=faces.target_names))

    #混淆矩阵
    mat = confusion_matrix(y_test,yfit)
    sns.heatmap(mat.T,square=True,annot=True,fmt='d',
                xticklabels=faces.target_names,
                yticklabels=faces.target_names)
    plt.xlabel('true label')
    plt.ylabel('predicted label')
    plt.show()

关于精确率、召回率以及混淆矩阵，我们在前面的数据可视化部分也讲过了，想不起来的同学可以翻看一下。
关于SVM支持向量机这部分的学习到这里就结束了，还有补充时，我会再更新，这一节公式推导较多，有不懂的地方可以下方留言或者私信。