引言
支持向量机(SVM)是一个功能强大并且全面的机器学习模型,它能够执行线性或者非线性分类、回归,甚至异常值检测任务。它是机器学习最受欢迎的模型之一,任何对机器学习感兴趣的人都应该在工具箱中配置一个。SVM特别适用于中小型复杂数据分类。
目录
线性可分和线性不可分
二维度情况:存在一条直线,能够将两个类别都数据集分开
三维(多维)情况:存在一个平面(超平面),能够将两个列别数据集分开。
下面是线性可分和不可分都例子:
线性可分数学定义(二维):
一个训练样本集{(X1,y1),(Xi,yi),...(XN,yN)} 在i=1~N线性可分,是指存在一个(), 对于i=1~N有:
注:yi=+1/-1仅仅是不同分类的标签,也可以取1/0或者其他数字。
写成向量形式:
先看线性可分的情况,然后推广到线性不可分的情况
线性可分情况下的最优分隔平面
如果数据集是线性可分的,则存在无数个平面能将数据集进行分开,那么那个平面是最好的平面呢?
我们将分隔平面进行平移,直到分隔平面触碰到两类数据集实例,这样的实例也称支持向量,两类实例平面的距离定义为间隔,
最优平面定义为:使间隔最大且处于间隔中间的分隔平面。
因此最优分隔平面需满足三个条件:
1. 该平面正确的分开了两类
2. 该平面最大化间隔
3. 该平面处于间隔的中间,到所有支持向量的距离相等
线性可分情况下最优分隔平面的数学理论(优化理论)
先说结论再推导,最优化分隔平面就是寻找最小的(与最小化相同,后者求导更方便),同时满足下述限制条件:
为什么是这样?为了推导这个结论,我们先给出两个事实:
事实1:
事实2:
比如,二维情况点到面的距离公式:
有了这两个事实,就可以理解SVM中推导中最难理解的部分:
- 根据事实1,可以有常数a去缩放(),(),使得:
- 根据事实2,支持向量X0到超平面的距离将变为:
因此最大化d,就是最小化,
同时由于yi=+1时,, 因此,对于yi=-1的情况同理。
寻找最大间隔分隔面的问题就变成如下优化问题:
其中,{xi,yi}已知,(ω,b)待求,是一个典型的凸优化二次规划问题,有成熟的求解工具。
二次规划问题
二次规划问题的定义:
1. 目标函数是二次项
2. 约束条件是一次项
二次规划问题要么有唯一解,要么无解。
线性不可分情况下的最优分隔平面
少数样本导致线性不可分情况
在线性不可分的条件下,限制条件无法同时满足,需要引入一个松弛变量,
现在有两个相互冲突的目标,越小越好(对应间隔越小)从而减少间隔违例,而我们又要使最小从而最大化间隔,这也是超参数C的用武之地。
优化问题可以改写为:
可以看出,C越大,权重越大,间隔越小。
大量样本线性不可分情况
某些情况下,数据集大量样本都是线性不可分的,例如下图中都X和⭕️,无论取什么样的线性平面,分隔的情况都不理想,只有取图示椭圆的分隔面,才能把两类样本分开。
线性不可分转换为线性可分的方法:低维变换为高维
这个时候需要使用函数变换,将样本从低维变换为高维(),从而变为线性可分。这是因为:
定理:在一个M维空间上随机去N个样本,随机对每个样本赋予标签+1/-1,假设这些样本线性可分对概率为P(M), 则在当M趋于∞时,P(M)=1
例如:下面对数据集在只有x1维度时是线性不可分的,当从x1映射到(x1, x1^2)时,就变成线性可分了。
所以,问题就是寻找适当的变换函数(),使得样本在空间线性可分,原最优问题也就转换为了下列问题:
注意,此优化和约束条件从X空间转换到了,因此ω维度和维度相同,而不是和X维度相同了(此ω不是原X空间问题的ω了)
核函数(kernel function)
前面提到,现在的问题就是找到合适的,使得X在空间线性可分。但是很多情况下具体形式并不容易得到。即使如此,在某些情况下也并不妨碍我们对样本进行训练和预测,这里就不得不提核函数的作用了。
核函数定义为,对于任意连个向量X1,X2,满足:
则K(X1,X2)为核函数,核函数是一个实数,这个可以从等式的右边看出来。核函数和是一一对应的关系
核函数举例
1. 已知具体形式,求K(X1,X2)
假设是一个将二维向量映射为三维向量的映射,具有下列形式:
2. 已知K(X1,X2),求具体形式
其中
则具有如下形式:
Mercer定理
核函数不能任意取,需要满足一定的条件,才能分解为两个函数的内积的形式
运用核函数求解支持向量机预测问题(线性方程的值)
原问题和对偶问题
将SVM原问题转换为对偶问题
前面提到SVM原问题为:
这个和上一节提到的原问题转换为对偶问题的原问题限制条件有一些区别,接下来,我们将原问题转换为上一节原问题的形式。
将取,得到:
上一节提到的对偶问题的现在变为了(),可以看到目标函数是凸函数,限制条件是线性函数,符合强对偶定理,原问题和对偶问题的解相等。
对偶问题如下:
该问题是一个二次规划问题,要求θ(α,β)对最大值, 令 θ(α,β)对α,β,b进行求导并令导数为0,得到:
注明:第(2)式应该是
分别将上述三个式子代入对偶问题表达式θ(α,β),简化后:
限制条件:
可以看到,对偶问题也是一个二次规划问题,可以方便求解。
由于知道核函数,可以解出
接下来如果要运用支持向量机对样本进行预测,需要求得的值,因此需要求得b的值
根据KKT条件(一个线性规划问题有最优解的充分必要条件),有:
如果对于某个i=1~N, 如果 (若, 则,该样本不会对线性分隔平面产生任何影响),必须有, 可得:
于是我们就可以求出的值了:
其中,
我们可以看出,即使在不知道的具体形式而只知道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越大,间隔越小。
非线性SVM分类
下面是一个使用卫星数据进行非线性SVM分类的例子,有两个特征X1,X2,两类数据如图所示:
其中蓝绿分别代表不同的数据标签,可以看到该数据集是线性不可分的,可以尝试使用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)
训练结果如图:
使用多项式核函数
添加多项式特征实现起来非常简单,并且对所有对机器学习算法(不只式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)接受高阶还是低阶多项式的程度