支持向量机原理及scikit-learn实现

引言

支持向量机(SVM)是一个功能强大并且全面的机器学习模型,它能够执行线性或者非线性分类、回归,甚至异常值检测任务。它是机器学习最受欢迎的模型之一,任何对机器学习感兴趣的人都应该在工具箱中配置一个。SVM特别适用于中小型复杂数据分类。

目录

引言

线性可分和线性不可分

线性可分数学定义(二维):

线性可分情况下的最优分隔平面

线性可分情况下最优分隔平面的数学理论(优化理论)

二次规划问题

线性不可分情况下的最优分隔平面

少数样本导致线性不可分情况

大量样本线性不可分情况

线性不可分转换为线性可分的方法:低维变换为高维

核函数(kernel function)

核函数举例

Mercer定理

运用核函数求解支持向量机预测问题(线性方程的值)

原问题和对偶问题

将SVM原问题转换为对偶问题

SVM分类的Python实现

线性SVM分类

非线性SVM分类

利用多项式特征

使用多项式核函数


线性可分和线性不可分

二维度情况:存在一条直线,能够将两个类别都数据集分开

三维(多维)情况:存在一个平面(超平面),能够将两个列别数据集分开。

下面是线性可分和不可分都例子:

支持向量机原理及scikit-learn实现支持向量机原理及scikit-learn实现

线性可分数学定义(二维):

一个训练样本集{(X1,y1),(Xi,yi),...(XN,yN)} 在i=1~N线性可分,是指存在一个(支持向量机原理及scikit-learn实现), 对于i=1~N有:

支持向量机原理及scikit-learn实现

注:yi=+1/-1仅仅是不同分类的标签,也可以取1/0或者其他数字。

写成向量形式:

支持向量机原理及scikit-learn实现

先看线性可分的情况,然后推广到线性不可分的情况

线性可分情况下的最优分隔平面

如果数据集是线性可分的,则存在无数个平面能将数据集进行分开,那么那个平面是最好的平面呢?

支持向量机原理及scikit-learn实现

我们将分隔平面进行平移,直到分隔平面触碰到两类数据集实例,这样的实例也称支持向量,两类实例平面的距离定义为间隔,

最优平面定义为:使间隔最大且处于间隔中间的分隔平面。

因此最优分隔平面需满足三个条件:

1. 该平面正确的分开了两类

2. 该平面最大化间隔

3. 该平面处于间隔的中间,到所有支持向量的距离相等

线性可分情况下最优分隔平面的数学理论(优化理论)

先说结论再推导,最优化分隔平面就是寻找最小的支持向量机原理及scikit-learn实现(与最小化支持向量机原理及scikit-learn实现相同,后者求导更方便),同时满足下述限制条件:

支持向量机原理及scikit-learn实现

为什么是这样?为了推导这个结论,我们先给出两个事实:

事实1:

 支持向量机原理及scikit-learn实现

事实2:

支持向量机原理及scikit-learn实现

比如,二维情况点到面的距离公式:

支持向量机原理及scikit-learn实现

有了这两个事实,就可以理解SVM中推导中最难理解的部分:

  • 根据事实1,可以有常数a去缩放(支持向量机原理及scikit-learn实现),(支持向量机原理及scikit-learn实现支持向量机原理及scikit-learn实现,使得:

支持向量机原理及scikit-learn实现

  • 根据事实2,支持向量X0到超平面的距离将变为:

支持向量机原理及scikit-learn实现

因此最大化d,就是最小化支持向量机原理及scikit-learn实现

同时由于yi=+1时,支持向量机原理及scikit-learn实现, 因此支持向量机原理及scikit-learn实现,对于yi=-1的情况同理。

寻找最大间隔分隔面的问题就变成如下优化问题:

支持向量机原理及scikit-learn实现

其中,{xi,yi}已知,(ω,b)待求,是一个典型的凸优化二次规划问题,有成熟的求解工具。

二次规划问题

二次规划问题的定义:

1. 目标函数是二次项

2. 约束条件是一次项

二次规划问题要么有唯一解,要么无解。

线性不可分情况下的最优分隔平面

少数样本导致线性不可分情况

在线性不可分的条件下,限制条件支持向量机原理及scikit-learn实现无法同时满足,需要引入一个松弛变量支持向量机原理及scikit-learn实现

支持向量机原理及scikit-learn实现

现在有两个相互冲突的目标,支持向量机原理及scikit-learn实现越小越好(对应间隔越小)从而减少间隔违例,而我们又要使支持向量机原理及scikit-learn实现最小从而最大化间隔,这也是超参数C的用武之地。

优化问题可以改写为:

支持向量机原理及scikit-learn实现

 可以看出,C越大,支持向量机原理及scikit-learn实现权重越大,间隔越小。

支持向量机原理及scikit-learn实现

大量样本线性不可分情况

某些情况下,数据集大量样本都是线性不可分的,例如下图中都X和⭕️,无论取什么样的线性平面,分隔的情况都不理想,只有取图示椭圆的分隔面,才能把两类样本分开。

支持向量机原理及scikit-learn实现

线性不可分转换为线性可分的方法:低维变换为高维

这个时候需要使用函数变换,将样本从低维变换为高维(支持向量机原理及scikit-learn实现),从而变为线性可分。这是因为:

定理:在一个M维空间上随机去N个样本,随机对每个样本赋予标签+1/-1,假设这些样本线性可分对概率为P(M), 则在当M趋于∞时,P(M)=1

例如:下面对数据集在只有x1维度时是线性不可分的,当从x1映射到(x1, x1^2)时,就变成线性可分了。

支持向量机原理及scikit-learn实现

所以,问题就是寻找适当的变换函数支持向量机原理及scikit-learn实现支持向量机原理及scikit-learn实现),使得样本在支持向量机原理及scikit-learn实现空间线性可分,原最优问题也就转换为了下列问题

支持向量机原理及scikit-learn实现

注意,此优化和约束条件从X空间转换到支持向量机原理及scikit-learn实现了,因此ω维度和支持向量机原理及scikit-learn实现维度相同,而不是和X维度相同了(此ω不是原X空间问题的ω了)

核函数(kernel function)

前面提到,现在的问题就是找到合适的支持向量机原理及scikit-learn实现,使得X在支持向量机原理及scikit-learn实现空间线性可分。但是很多情况下支持向量机原理及scikit-learn实现具体形式并不容易得到。即使如此,在某些情况下也并不妨碍我们对样本进行训练和预测,这里就不得不提核函数的作用了。

核函数定义为,对于任意连个向量X1,X2,满足:

支持向量机原理及scikit-learn实现

则K(X1,X2)为核函数,核函数是一个实数,这个可以从等式的右边看出来。核函数和支持向量机原理及scikit-learn实现是一一对应的关系

核函数举例

1. 已知支持向量机原理及scikit-learn实现具体形式,求K(X1,X2)

假设支持向量机原理及scikit-learn实现是一个将二维向量映射为三维向量的映射,具有下列形式:

支持向量机原理及scikit-learn实现

支持向量机原理及scikit-learn实现

2. 已知K(X1,X2),求支持向量机原理及scikit-learn实现具体形式

支持向量机原理及scikit-learn实现

其中支持向量机原理及scikit-learn实现

支持向量机原理及scikit-learn实现具有如下形式:

支持向量机原理及scikit-learn实现

Mercer定理

核函数不能任意取,需要满足一定的条件,才能分解为两个函数的内积的形式支持向量机原理及scikit-learn实现

支持向量机原理及scikit-learn实现

运用核函数求解支持向量机预测问题(线性方程的值)

原问题和对偶问题

支持向量机原理及scikit-learn实现

支持向量机原理及scikit-learn实现

支持向量机原理及scikit-learn实现

将SVM原问题转换为对偶问题

前面提到SVM原问题为:

支持向量机原理及scikit-learn实现

这个和上一节提到的原问题转换为对偶问题的原问题限制条件有一些区别,接下来,我们将原问题转换为上一节原问题的形式。

支持向量机原理及scikit-learn实现支持向量机原理及scikit-learn实现,得到:

支持向量机原理及scikit-learn实现

上一节提到的对偶问题的支持向量机原理及scikit-learn实现现在变为了(支持向量机原理及scikit-learn实现),可以看到目标函数是凸函数,限制条件是线性函数,符合强对偶定理,原问题和对偶问题的解相等。

对偶问题如下:

支持向量机原理及scikit-learn实现

该问题是一个二次规划问题,要求θ(α,β)对最大值, 令 θ(α,β)对α,β,b进行求导并令导数为0,得到:

支持向量机原理及scikit-learn实现

注明:第(2)式应该是

支持向量机原理及scikit-learn实现

分别将上述三个式子代入对偶问题表达式θ(α,β),简化后:

支持向量机原理及scikit-learn实现

限制条件:

支持向量机原理及scikit-learn实现

支持向量机原理及scikit-learn实现

可以看到,对偶问题也是一个二次规划问题,可以方便求解。

由于知道核函数支持向量机原理及scikit-learn实现,可以解出支持向量机原理及scikit-learn实现

接下来如果要运用支持向量机对样本进行预测,需要求得支持向量机原理及scikit-learn实现的值,因此需要求得b的值

支持向量机原理及scikit-learn实现

根据KKT条件(一个线性规划问题有最优解的充分必要条件),有:

支持向量机原理及scikit-learn实现

 支持向量机原理及scikit-learn实现

如果对于某个i=1~N, 如果支持向量机原理及scikit-learn实现 (若支持向量机原理及scikit-learn实现, 则支持向量机原理及scikit-learn实现,该样本不会对线性分隔平面产生任何影响),必须有支持向量机原理及scikit-learn实现, 可得:

支持向量机原理及scikit-learn实现

于是我们就可以求出支持向量机原理及scikit-learn实现的值了:

支持向量机原理及scikit-learn实现

其中,支持向量机原理及scikit-learn实现

支持向量机原理及scikit-learn实现

我们可以看出,即使在不知道支持向量机原理及scikit-learn实现的具体形式而只知道K(X1,X2),仍然可以对样本进行预测,这称为核函数戏法(kenel function trick)

SVM分类的Python实现

线性SVM分类

下面是一个使用鸢尾花数据集进行线性SVM分类的例子,其中的X是花叶子的长度和宽度,y是否为Iris-Virginica品类(一共有3中品类)

步骤主要是:加载鸢尾花数据集,进行特征缩放,然后训练一个线性SVM模型(使用LinearSVC,C=1,hinge损失函数),然后进行预测

import numpy as np
from sklearn import datasets
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import LinearSVC

iris = datasets.load_iris()
X = iris["data"][:, (2, 3)]  # petal length, petal width
y = (iris["target"] == 2).astype(np.float64)  # Iris-Virginica

svm_clf = Pipeline([
        ("scaler", StandardScaler()),
        ("linear_svc", LinearSVC(C=1, loss="hinge", random_state=42)),
    ])

svm_clf.fit(X, y)

# 使用模型作出预测
>>>svm_clf.predict([[5.5, 1.7]])
array([1.0])

下图展示在不同C取值下线性分类的结果:C越大,间隔越小。

支持向量机原理及scikit-learn实现

非线性SVM分类

下面是一个使用卫星数据进行非线性SVM分类的例子,有两个特征X1,X2,两类数据如图所示:

支持向量机原理及scikit-learn实现

其中蓝绿分别代表不同的数据标签,可以看到该数据集是线性不可分的,可以尝试使用3阶多项式SVM分类方法

利用多项式特征

from sklearn.datasets import make_moons
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import PolynomialFeatures

polynomial_svm_clf = Pipeline([
        ("poly_features", PolynomialFeatures(degree=3)),
        ("scaler", StandardScaler()),
        ("svm_clf", LinearSVC(C=10, loss="hinge", random_state=42))
    ])

polynomial_svm_clf.fit(X, y)

训练结果如图:

支持向量机原理及scikit-learn实现

使用多项式核函数

添加多项式特征实现起来非常简单,并且对所有对机器学习算法(不只式SVM)都非常有效,但问题是多项式太低阶,无法处理非常复杂的数据集,而高阶则会创造大量的特征,导致模型变得很慢。幸运的是,可以运用核函数技巧,它产生的结果就跟添加了许多项多项式特征一样,但实际上并不需要添加,所以不存在数量爆炸的组合特征。

from sklearn.svm import SVC

poly_kernel_svm_clf = Pipeline([
        ("scaler", StandardScaler()),
        ("svm_clf", SVC(kernel="poly", degree=3, coef0=1, C=5))
    ])
poly_kernel_svm_clf.fit(X, y)

结果如下图所示:左图使用了一个3阶多项式核SVM分类器,右图使用的是 一个10阶多项式核SVM分类器,其中超参数coef0(图中的r=1或者100)接受高阶还是低阶多项式的程度

支持向量机原理及scikit-learn实现

上一篇:Learn-设计模式系列-①七大原则


下一篇:1.1.1:机器学习课程介绍