支持向量机(Support Vector Machine)是一种十分常见的分类器,曾经火爆十余年,分类能力强于NN,整体实力比肩LR与RF。核心思路是通过构造分割面将数据进行分离。本文主要阐述SVM的基本工作原理和简单应用。
?
1.???Linearly Separable SVM
?
Linearly Separable SVM的原理是要达到hard margin maximization。Linear separable是指,当我们想用一个分割平面,将两个数据分割开时,存在至少一个分割面,使两个数据可以完全分离,则我们认为这个SVM是线性可分SVM。
?
2.???Linear SVM
?
Linear SVM是指,分割面虽然不能完全分割所有数据,但是该线性分割方式可以使绝大多数数据正确的被分类。那么这样的SVM也可以被称为线性SVM。Linear SVM要达到的是soft margin maximization。这里的soft对应线性可分SVM的hard。Hard margin指的是支持向量到分割面的距离,因为支持向量距离分割面最近,该距离也是过渡带宽度(的一半)。而soft margin指的是,当SVM不是线性可分的情况时,此时支持向量并不一定是距离分割面最近的向量。因此SVM此时并不能一味地margin maximization,而是使过渡带足够宽。此时的margin maximization并不是真正意义上的,严格的margin maximization。所以用soft进行区分。
?
3.???Non-linear SVM
?
对于前两种SVM,对其加入一个kernel function就可以构造出非线性SVM。
?
4.???选取支持向量与构造分割面
?
对于一条直线:,(,?)实际上就是直线的法线方向。如果我们代入(, )到等式左边,则当该式大于0时,X在法线正方向上,小于0时则在法线负方向上,等于0则在法线上。将这一性质应用于更高维度的话,如果X为n维向量,则这条直线变为超平面。
?
?
?
?
支持向量怎么选择?以线性可分SVM为例,我们将W认为是若干样本线性组合得到的,第1个样本为,第i 个为。对于每个X,给予其系数。此时存在:,选取部分,使它们的值不为0,其余值都设为0。则对W真正起作用的就是值不为0的这些X向量。这些向量,支持了法线向量,因此就是支持向量。这个表达式只是大致描述一下支持向量的选取机制,在第5节将会给出严格证明。
?
?
?
若直线l有参数W和b,通过计算每个样本到直线l距离,衡量哪条直线是最为合适的分割线。距离d可以表示为:,若每个数据集中样本的形式为T={(,?)(, )…(, )},而每个样本的y值,就是这个样本的label。正例为1,负例为-1。这里的正负值其实反映的就是样本位于分割线的方向。位于法线正方向即为正。将y值一起乘入等式右边:?,这里的y值是样本的实际正负值,如果估计值与实际值符号相同,即分类正确,此时的结果为正值。如果分类错误,则结果为负值。
?
?
在所有样本中,距离该直线最近的样本应被选为支持向量。支持向量与直线间的距离即为过渡带。因为SVM期望过渡带尽可能大,因此最终参数W与b的选择可以表示为:
,
因此,给定线性可分训练数据集,通过间隔最大化得到的分割超平面为:,相应的分类决策函数为:。
?
?
5. Objective Function
?
对于线性可分SVM而言,目标函数实际上就是分割平面的选取,因此目标函数实际上就是:
,
对于上式,在不改变分割面位置的情况下,总存在一个W值,使距离该直线最近的向量到直线距离为1。因此上式中,最小值部分可以始终取1。此时的W值,实际上才是目标函数本身。而同时存在约束条件:。因此,通过Lagrange Multiplier可以对目标函数求极值:
?
整理可得:
?
?
对目标函数使用Lagrange Multiplier:
?
这里的W和b是原始的参数,而是引入的参数且大于等于0。为了方便整理与化简,接下来对L求偏导并使偏导为0:
?
?
?
根据上式,等于0的时候可知其对W与b无作用。因此,真正的支持向量,是那些不为0的向量。
?
这里给出一个通过凸优化后最终得到的求的式子:
?
?
求出之后回代可得W与b:
?
?
6.???松弛因子
?
对于线性SVM而言,因为不要求所有样本都被分对,因此其约束条件和线性可分SVM并不相同。给出一个大于等于0的松弛因子,使函数间隔加上松弛因子后大于等于1,此时有目标函数及约束条件:
?
?
上式中,C是一个控制松弛因子权重的参数。当C足够大时,只能趋近于0,变回线性可分SVM。因此上式也可以被看作是线性可分SVM的扩展。松弛项可以被理解为线性回归中的正则项,C的值越小,过渡带越宽,C的值越大,过渡带越窄。这也使得线性SVM具备更强的泛化性。
?
同样的,对于线性SVM的目标函数及其约束条件使用Lagrange Multiplier后,求偏导可得:
?
?
这里直接给出最后的求解形式:
?
?
7.???Loss Function
?
SVM的损失,通常被定义为没有被正确分在过渡带外面的向量,到过渡带边界的距离。位于过渡带内的样本,损失为1-d。d是该样本到分割面的距离。注意,如果是在“本方”过渡带,则d为正值。如果已经越过分割面了,则d值变为负值。这个损失也被称为Hinge损失。因此Loss function可以被写成:
?
?
换句话说,松弛因子本身可以被看作是损失的衡量。因为松弛因子本身也是包容分割面的分割错误。实际上,损失本身,就是由于线性SVM允许过渡带内存在向量,甚至向部分错误分类的向量妥协的结果。因此,原目标函数:
?
?
某种意义上,可以认为是Hinge损失加上一个。
?
8.??? Kernel
?
Kernel可以说是SVM的精髓所在,其目的在于,通过将原始输入空间映射到更高维度的特征空间这一操作,原本线性不可分的样本可以在新的核空间内变为线性可分。常见的kernel有:
?
?
从多项式核函数讲起,最基本的,c等于0,d等于2的情况下,kernel使原有的两个变量两两相乘。这相当于将维度数量平方了。规模上,特征数目变为平方级,而计算复杂度并没有显著上升。
?
RBF则是固定每一个,对于变化的,以为中心做指数级衰减。相当于是以为中心,做高贵的蜗牛分布。因此被称作高贵的蜗牛核函数。对于每个样本的label而言,正例被kernel向上拉升,负例向下延伸。从而使数据分离。
?
?
分离后的数据,可以被多个分割面分离,我们要选取的,实际上就是使距离分割面最近的样本距离尽可能大的分割方式。因此最终的超平面选取还是使用线性SVM的思路。RBF的维度映射可以被理解是无穷维的,因为在数学上,RBF的指数可以被明亮的哑铃展开。展式中的每一项,都可以被理解为该维度上的样本分离。因为其强力的高维映射能力,RBF往往是首选kernel。
?
9. Iris数据分类代码
?
?
数据选用的是Iris数据,数据格式为:
?
?
5.1,3.5,1.4,0.2,Iris-setosa
?
?
前面的数据分别为该花的petal和sapel的长宽值,最后一项为label,是花的类型。总数据量为150条,三种花每种50条。代码如下:
?
?
import numpy as npimport pandas as pdfrom sklearn import svmfrom sklearn.model_selection import train_test_splitfrom sklearn.metrics import accuracy_scoreif __name__ == “__main__”: path = ‘iris.data’ data = pd.read_csv(path, header=None) data[4] = pd.Categorical(data[4]).codes x, y = np.split(data.values, (4,), axis=1) # print(x) # print(y) x_train, x_test, y_train, y_test = train_test_split(x, y, random_state=1, train_size=0.8) svm_model = svm.SVC(C=0.5, kernel=’linear’, decision_function_shape=’ovr’) # svm_model = svm.SVC(C=0.8, kernel=’rbf’, gamma=20, decision_function_shape=’ovr’) svm_model.fit(x_train, y_train.ravel()) print(accuracy_score(y_train,svm_model.predict(x_train))) print(‘Accuracy:’, accuracy_score(y_test, svm_model.predict(x_test))) # print(y_test.ravel()) # print(svm_model.predict(x_test))
?
?
?
最终结果:Accuracy = 1.0
?
SVM可以说是泛化能力很强的优质分类器,准确率也很高。相比于LR和RF,SVM难点在于调参。RF更多的注重效率,在模型训练以及特征选择上省下了大把时间。LR学习速率也快于SVM,比较通用,精确度和效率都不错。
?
23221156