SVM理论解析及python实现

关于常见的分类算法在不同数据集上的分类效果,在《Do we Need Hundreds of Classifiers to Solve Real World Classification Problems?》这个篇论文上有比较完善的总结,因为文章内容比较长,这边我总结了下我认为比较关键的一些结论:

仅仅参考论文评价我们常用的:

  • 神经网络的效果最好,13.2%的数据集中取得第一
  • SVM的效果其次,10.7%的数据集中取得第一
  • Bagging和Boost紧随其后,9%~10%左右的数据集取得第一
  • Elastic Net等的线性算法效果普通,5%-7%的数据集上取得第一

附加一些我个人平时调参的经验及感悟:

  • 神经网络拟合的效果好是基于大量的数据量上,如果数据集较小,训练结果通常不如上述其他算法;除此之外,神经网络的训练成本高,关于控制非线性变换的隐藏层层数,控制线性力度的节点个数的设置需要大量的历史经验,相对成本非常高。
  • SVM对数据集合量以及维度没有很高的要求,而且可以解决线性问题(kernel=linear),非线性问题(kernel=RBF等),而且相对来说效果优秀。但是SVM的核心是计算最大分隔的间隔,如果全都是分类变量,效果会受一定的影响,而且需要额外的操作才能获取概率结果。
  • Bagging和Boost,能够解决非线性问题,Bagging基于抽样抽特征,控制Var的情况下降低Bias;Boost基于N个弱分类器的强化组合,控制Bias的情况下降低Var,对数据格式的要求也很低,实现上比较友好。缺点可能就是太一般,没有专业领域的亮点。
  • Elastic Net等线性回归算法,对数据量数据维度没有什么要求,部分算法会自己压缩feature,简单易操作,相比于上述任何一个算法都好实现,除此之外,还可以得到概率结果。缺点就是效果较差,如果在feature和label没有线性关系的时候无法得到理想结果。

除了上述的方法,还有比如KNN、线性判别分析、Naive Bayes等方法,每个都有自己适用的场景,也但是通常不做首要考虑的分类算法。

针对其中的SVM,本文接下来和大家解析三个方面:
1.感知机、线性感知机、核感知机的理论概览
2.如何利用python中的sklearn快速的实现svm分类
3.SMO方法的核心功能实现

如果你只是想快速了解分类算法的概览,方便面试或者日常“交流”,到此就可以不用往下看了。
如果你是数据分析师或者软件工程师,只是想快速了解如果使用,直接跳到2。
如果你是机器学习工程师,需要对整个算法有个了解,贯穿整个SVM过程,直接看1,2。
如果你是算法工程师,需要重构算法,或在当前解决核函数计算瓶颈的,请全文阅读,并阅读推荐书籍。

让我们开始正文:

感知机、线性感知机、核感知机的理论概览

感知机

我们日常说的SVM其实只是一个感知机,也就是没有任何的核函数的情况。

上面图中,对于二维数据来说,平面π1,π2,π3都可以将红色和蓝色的点给划分开。对于多维数据来说,这边的平面就可以引申为超平面,wx+b=0。

所以,我们可以说,对于数据集:

如果我们可以得到超平面wx+b=0,使得y=1的点集合与y=-1的点的集合分隔在平面两边(如上图所示),那我们就说原始数据集D线性可分,wx+b=0为其超平面。

首先,我们定义损失函数为:L=max(-y(wx+b),0),我们来看下,如果我们预测正确,y=1,我们预测的为wx+b>0或者,y=-1,我们预测的为wx+b<0,y(wx+b)>0,则不贡献梯度;否则,我们可以取-y(wx+b)为梯度,也就得到了上述的梯度公式。
接下来的就是常规意义上的对w和b的偏导,然后梯度下降求极值。

线性感知机

现在我们思考两个问题:
a.上述的π1、π2、π3都是感知机,如何选取最优?
b.下面这张图线性不可分,如何解决?

线性不可分

我们先来看,平面π1外任意点到平面的距离如何计算:

假设任意点为X(x,y),垂点X1(x1,y1),垂点在π1平面(wx+b=0)上,所以,我们有X-X1=ρw,w为平面π1的法向量。所以,我们有:
||X-X1||**2=ρw(X-X1)=ρ(wx+b-(wx1+b))=ρ(wx+b)=ρ(wx+b)
在计算距离的时候,我们需要去归一化,无量纲化。
不难看出,距离的计算方式为:


所以,我们在超平面选取的时候,需要考虑两点:
(1)所以的分类结果要保持正确:

(2)保证决策面离正负样本都极可能的远:


里面的min的作用是计算所有的点到平面π的最小距离,外面的max的作用是尽可能的让最小距离最大,保证决策面离正负样本都尽可能的远。

假设(x1,y1)到决策平面的距离最近,所有y1(wx1+b)>=1,所以目标函数:max(1/||w||),可以优化为min(||w||^2/2)。
但是如果发生1.2节最开始的线性不可分的问题的时候,y1(wx1+b)>=1就无法实现,所有我们需要加∆的容忍度,也就是变成了y1(wx1+b)>=1-∆。既然加了∆,我们也需要对∆进行控制:∆=1-y1(wx1+b),有更新后的目标函数:


这边的[]+记为神经网络中常用的ReLU函数。
有了这个目标函数,接下来就是正常的梯度下降,偏导后求解的过程。

核函数下的感知机

上面考虑的问题均是线性可分的问题,假设数据分布如下:


无论通过平面π1、π2、还是π3均无法做到线性的分割。
而核函数的目的就是通过内积的形式,将低维度的数据映射到高维度,通常采取的方式是w=∑αx的形式,带回到原来的损失函数:
比如普通感知机的:

比如线性感知机

K(xi,xj)常用的有:
多项式核函数:
(xi+xj+1)^p

径向基核函数:
exp(-ρ||xi-xj||^2)

至于之后的计算,还是可以和之前一致,将上述选择的核函数代入损失函数后采取梯度下降的方法,高效计算方式SMO算法在第三模块会简单的梳理一遍。

以上我们就大概的了解了感知机,linear svm,kernel svm的损失函数的来源及构造细节等等,接下来我们来看下如何快速的使用。

如何利用python中的sklearn快速的实现svm分类

在python的sklearn包中,有SVM的包,其中SVC是分类,SVR是回归,可以快速简单的上手,下面上code,并在注释中解释:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from sklearn import svm
from sklearn.cross_validation import train_test_split

#data add,数据读取
risk_data=pd.read_table('/Users/slade/Desktop/Python File/data/data_all.txt')

#data check,删除无用的列
risk_data = risk_data.drop('Iphone',axis=1)

#data scale,数据归一化(必备的操作),上述理论中也体现归一化后的距离计算的原因
risk_data_mm = risk_data.max()-risk_data.min()
risk_data_scale = pd.DataFrame([])
for i in range(len(risk_data.columns)):
new_columns = (risk_data.iloc[:,i]-risk_data.iloc[:,i].min())/risk_data_mm[i]
risk_data_scale = pd.concat([risk_data_scale,pd.DataFrame(new_columns)],axis=1)

#split data(将数据分割成训练集和测试集)
train_data,test_data = train_test_split(risk_data_scale,test_size = 0.3)

#update_train,update_test(因为我的数据集是非常不平衡的,这边我采取了欠采样的方法)
train_badcase = train_data[train_data['tag']==1]
train_goodcase = train_data[train_data['tag']!=1]
sample_value=(10*train_badcase.count()[0])
train_goodcase_sample = train_goodcase.sample(n=sample_value)
train_data_update = pd.concat([train_badcase,train_goodcase_sample],axis = 0)
y=train_data_update['tag']
x=train_data_update.iloc[:,1:len(train_data_update.columns)]


#svm(linear、rbf、sigmoid为核的SVM)
clf_linear = svm.SVC(kernel='linear').fit(x,y)
clf_rbf = svm.SVC(kernel='rbf').fit(x,y)
clf_sigmoid = svm.SVC(kernel='sigmoid').fit(x,y)

#test,训练数据处理
y_test = test_data[['tag']]
x_test = test_data.iloc[:,1:len(test_data.columns)]

#模型效果对比
#linear
test_pred=clf_linear.predict(x_test)
y_test.index = range(y_test.count())
union_actual_pred = pd.concat([y_test,pd.DataFrame(test_pred)],axis = 1)

#show the result
recall = union_actual_pred[union_actual_pred.iloc[:,0]==1][union_actual_pred.iloc[:,1]==1].count()/union_actual_pred[union_actual_pred.iloc[:,0]==1].count()
percison = union_actual_pred[union_actual_pred.iloc[:,0]==1][union_actual_pred.iloc[:,1]==1].count() / union_actual_pred[union_actual_pred.iloc[:,1]==1].count()
correction = union_actual_pred[union_actual_pred.iloc[:,0]==union_actual_pred.iloc[:,1]].count()/union_actual_pred.iloc[:,0].count()

print 'about the linear svm , the recall is %s' %recall
print 'about the linear svm , the percison is %s' %percison
print 'about the linear svm , the correction is %s' %correction

#rbf
test_pred=clf_rbf.predict(x_test)
y_test.index = range(y_test.count())
union_actual_pred = pd.concat([y_test,pd.DataFrame(test_pred)],axis = 1)

#show the result
recall = union_actual_pred[union_actual_pred.iloc[:,0]==1][union_actual_pred.iloc[:,1]==1].count()/union_actual_pred[union_actual_pred.iloc[:,0]==1].count()
percison = union_actual_pred[union_actual_pred.iloc[:,0]==1][union_actual_pred.iloc[:,1]==1].count() / union_actual_pred[union_actual_pred.iloc[:,1]==1].count()
correction = union_actual_pred[union_actual_pred.iloc[:,0]==union_actual_pred.iloc[:,1]].count()/union_actual_pred.iloc[:,0].count()

print 'about the linear svm , the recall is %s' %recall
print 'about the linear svm , the percison is %s' %percison
print 'about the linear svm , the correction is %s' %correction


#sigmoid
test_pred=clf_sigmoid.predict(x_test)
y_test.index = range(y_test.count())
union_actual_pred = pd.concat([y_test,pd.DataFrame(test_pred)],axis = 1)

#show the result
recall = union_actual_pred[union_actual_pred.iloc[:,0]==1][union_actual_pred.iloc[:,1]==1].count()/union_actual_pred[union_actual_pred.iloc[:,0]==1].count()
percison = union_actual_pred[union_actual_pred.iloc[:,0]==1][union_actual_pred.iloc[:,1]==1].count() / union_actual_pred[union_actual_pred.iloc[:,1]==1].count()
correction = union_actual_pred[union_actual_pred.iloc[:,0]==union_actual_pred.iloc[:,1]].count()/union_actual_pred.iloc[:,0].count()

print 'about the linear svm , the recall is %s' %recall
print 'about the linear svm , the percison is %s' %percison
print 'about the linear svm , the correction is %s' %correction

上述粗略的给出了如何快速的通过svm进行一次训练,现在就svc中的参数进行剖析:
C:惩罚力度,C越大代表惩罚程度越大,越不能容忍有点集交错的问题
kernel:核函数,常规的有‘linear’, ‘poly’, ‘rbf’, ‘sigmoid’, ‘precomputed’ ,默认的是rbf
degree:当poly为核函数时启动,默认是3
gamma:当‘rbf’, ‘poly’ 和 ‘sigmoid’为核函数时的参数设置,默认的是特征个数的倒数
probability:是否输出概率值
shrinking:是否自启动
tol:停止训练的容忍度
max_iter:最大的训练次数
class_weight:因变量的权重
decision_function_shape:因变量的形式:ovo一对一, ovr一对多, 默认’ovr’
根据自己的需求,对上述的参数进行grid_search即可完成快速训练任务。

3.SMO方法的核心功能实现

首先,我们需要明确,SVM学习过程可以转化为以下问题:


至于什么是KKT条件,请参照总结:常见算法工程师面试题目整理(二)中的回答。
求解的方式也是比较复杂,这主要以梳理流程为主,我们的目的就是找到一组αi满足上述的约束,然后再根据该组的αi求解到w和b即可。

求解αi的过程如下:

1
2
3
4
1.选择两个拉格朗日乘子αi和αj
2.固定其他拉格朗日乘子αk(k不等于i和j),只对αi和αj优化w(α)
3.根据优化后的αi和αj,更新截距b的值
4.充分1-3直到收敛

针对上面的过程存在2个问题
a.为什么要选择两个乘子?而不是更加方便计算的一个?
在原始的约束条件中,存在:

如果只选择一个为变化乘子的化,根据其他确定的乘子,该变化乘子也无法变化。

b.如何选择两个乘子αi和αj?


检验样本是否满足KKT条件也就是检验样本是否满足以下条件:


第一个参数αi优先检验0<αj<C也就是π3和π1平面上的点是否满足条件,如果全部满足条件,再检验全部数据集是否满足条件。

第二个参数αj则可以简单地随机选取,虽然这不是特别好,但效果已然不错。也可以通过最大化αi的误差与αj的误差之差的绝对值去判断,但是计算量会变大,因为又做了一次全量数据循环。

当αi和αj有了之后再去对b进行修正:


即可。

这边的代码比较复杂,我就不贴了,百度上很多实现了的版本。

总的来说,我们对svm的过程有了个浅尝辄止的了解,部分算法工程师需要要深入的了解其深刻完整的含义,仍需完整完善的学习,《统计学习方法 》一书讲的深入透彻,建议可以研读一下。

部分软件工程师在运用中可能需要各种版本的svm,这边也贴出地址,供参考Support Vector Machine for Complex Outputs

最后,谢谢大家的阅读。

打赏的大佬可以联系我,赠送超赞的算法资料