线性SVM

一、线性SVM解释及数学模型

    我们首先用一个经典的二分类问题作为SVM的切入点，图(b)和图(c)是对图(a)中数据的两种不同的分法。从人的第一感觉，图(b)把两类数据分的开些。

    这是一个二维数据的图像，黑色点代表正例，标签y=1，白色点代表负例，标签y=-1(这里为什么不用y=0后面解释)。可以看到图中有两条虚线和一条实线，如何用数学的方法解释将数据分的开一些呢？

样本空间中，实线公式：
w * x+b=0     将其记为(w,b),对于高维空间同样适用，就变成了超平面。

点x到超平面的距离公式为：

于是有：

两个式子合并为：

两类数据到分隔实线的距离关系，即为：

于是将两类数据分隔开的距离表达式为2/||w||.

SVM要做的就是使得分隔开的距离最大化，因此得出优化方程：

正是由于将负例标签y设为-1，所以就可以将边界条件整合成一个式子了。

为了数学的运算方便，将其转化为下面的形式，于是得出了最终的优化方程：

我们一般会把求最大值转化为求最小值来处理，要做优化一般都要求导，所以转化为这样的凸优化形式方便求导后的简便。

---

二、优化问题

1.拉格朗日乘子法

  本科学过关于拉格朗日乘子法求最值问题，当时的边界条件是等式。该方法的基本思路是将边界条件带入方程，这必然要引入新的参数，于是将所得参数求偏导令为0，即可求出最优解。 这里的边界条件是不等式，所以稍难些，将不等式边界条件转化为一重(chong)最值即可。
利用拉格朗日乘数法构建函数：

  其中 $\alpha$ 为向量且$\alpha_i$$\geq$0，该式子第二项由边界条件变化而来，且第二项大于等于0。

所以得出：

   这里有点不好理解，由于构建的函数L(w,b,$\alpha$)的第二项$\geq$0,而且是第一项减去第二项，所以函数L对$\alpha$ 有最大值，且最大值恰好为第一项。当$\alpha_i$=0时取最大值或者一开始的图中虚线上的点也满足最大值。

于是我们要优化的问题就转化为了：

---

2.对偶问题

首先要说明一个问题:

  该不等式左边是先求最大值再求最小值，右边是先求最小值再求最大值。这就相当于在一群胖子里面找个最瘦的和在一群瘦子里面找个最胖的，答案可想而知。那么什么情况下上式中等号成立呢？当满足KKT条件时等号成立，这里暂且略过。

于是我们的问题转化为了：
对于优化问题，我们总是倾向于先求最小值。

---

3.优化求解

  这里可知，只要求出了$\alpha_i$便可以求出w了。

于是问题转化成了：

$x_i和y_i便是我们的训练数据集$，我们的目的是求出$\alpha_i$ 进而求出w，然后利用b=y-w*x求出b，也就求出了我们需要的超平面w*x+b=0。

   针对上面的优化问题，可以利用转化为求-L的最小值问题，对$\alpha$求偏导，进而求出$\alpha$.有更高效的算法即序列最小优化算法(SMO),本人目前也没看懂。

---

三、归纳与分析

回顾整个过程，我们先是由简单的二分类问题引入数学模型即优化函数：

我们的目的是求出w和b就能确定我们要求的分割线(超平面)，针对该优化函数利用拉格朗日乘数法求出中间参数$\alpha$,再求出w和b。对于整个过程，要明白我们的最终目的是什么，目标一步步转化为什么。

说明：
1.支持向量：对于我们的下面目标函数，要求第二项为0，而满足该条件的数据点也就是一开始图中虚线上的点，这些点就叫作支持向量。

 1)从图像上看离超平面最近，影响了超平面的划分。
 2)从优化角度上看，这些点满足最大值的优化条件，进而影响了后续的优化进程。
 3)从计算数值上看，

w的值也是由这些支持向量所决定的，而那些非支持向量并不能决定w的值。
 4)先是所有的点共同决定哪些是支持向量，哪些是非支持向量。一旦确定好之后，非支持向量就没有用了。

2.从预测角度上看，对于要分类的数据点x,只需要计算该函数就行了。

四、线性SVM编程

编辑工具：jupyter notebook

import numpy as np
import matplotlib.pyplot as plt
from scipy import stats
import seaborn as sns
sns.set()
%matplotlib inline
1
2
3
4
5
6

from sklearn.datasets.samples_generator import make_blobs     #blobs:斑点
#50个数据点，2堆，随机种子，簇的离散程度
X,y=make_blobs(n_samples=50,centers=2,random_state=0,cluster_std=0.7)
plt.scatter(X[:,0],X[:,1],c=y,s=50,cmap='autumn')
#创建了2堆二维数据X，y是其对应标签。
1
2
3
4
5

from sklearn.svm import SVC    # "Support vector classifier"
model1=SVC(kernel='linear')
model1.fit(X,y)  
#构建SVC模型，进行训练
1
2
3
4

model1.predict([[0,0],[3,0],[2,5],[3,4]]) 
#预测，这里用的是sklearn中封装好的SVC，所以这里类别用0和1表示，与前面理论推导的类别-1和1不同
1
2

array([1, 1, 0, 0])

print(model1.support_vectors_)  #显示所有的支持向量
print(model1.n_support_)      #获得每个类别的支持向量的个数
1
2

[[0.35482006 2.9172298 ]
[2.56509832 3.28573136]
[2.06261754 2.14777301]
[3.09704406 2.22478608]]
[2 2]