机器学习算法——支持向量机（SVM）

0 前序

本人是生物类的一名研究生，学习Python也有一段时间了，从数据处理到人工智能，机器学习， Python几乎是无所不能的，用其处理生信数据想必也是很好的工具。这是本人写的第一篇博客，某法则曾说：能把问题清楚地写下来，就已解决了一半。所以打算把学习过程中遇到问题记录下来，以便日后回顾解决，同时打算把最近几天的学习心得写下来，也算是对期间学习的一个总结。

1 介绍

SVM（Support Vecor Machine）是一个二元分类算法，不仅可以用于数据分类，也可以应用于回归问题。对于没有高数基础的同学（比如我），在了解SVM之前，还需了解一下基本的高数常识，比如点到面的距离、拉格朗日乘子法等，以便后续理解。

1.1 距离公式介绍

点到直线的距离公式推导：
机器学习算法——支持向量机（SVM）

其中向量n=(A,B,C)的模:

1.2 拉格朗日乘子法

关于拉格朗日乘子法在知乎上看到了一个很直观的解释：https://www.zhihu.com/question/38586401/answer/105588901 ，可供参考。
目标函数f(x,y)是一座山的高度，约束条件g(x,y)=C是镶嵌在山上的一条曲线如下图：
机器学习算法——支持向量机（SVM）
为了找到曲线上的最低点，就从最低的等高线（0那条）开始网上数。数到第三条，等高线终于和曲线有交点了（如上图所示）。因为比这条等高线低的地方都不在约束范围内，所以这肯定是这条约束曲线的最低点了。
那么什么是等高线呢？下图还是比较直观的。

机器学习算法——支持向量机（SVM）
所以当等高线与约束条件相切时，两者的法向量相平行，因此可以列出二者的关系式：我们引入任意的常数乘子（取为λ）：, 我们把这个式子的右边移到左边，并把常数移进微分算子，就得到：
机器学习算法——支持向量机（SVM）
所以根据上式构造辅助函数：

然后令

就可求出极值点（意为求偏导）。

2 线性可分支持向量机

对于线性支持向量机我们需要考虑的是一个二分类问题，即数据是线性可分的。如下图所示：
机器学习算法——支持向量机（SVM）
对于一个数据集，我们可以构造一个超平面（在二维空间里表示为直线），将数据集分为两类。如图中紫色与黄色的点，每个点都为一个数据点，用X(x,y)表示，该数据集有明显的区分度，图中三条超平面（直线）都可以将其区分开，甚至还有无数个超平面（只是未画出），可将其区分，但哪一个超平面的区分效果更好呢？超平面满足方程：
机器学习算法——支持向量机（SVM）
其中x为数据点， $w^T x$ 为超平面的法向量。令 $f(x)=w^T x+b$ ，若f(x)=0，则表示数据点落在超平面上，无法被分类；若f(x)>0，其对应的类别为 $y_i=+1$ ；相反若f(x)<0，其对应类别 $y_i=-1$ （取±1为了方便运算），所以无论f(x)是否大于0，都有 $y_i f(x)>0$ 。
根据点到平面的距离公式可得，数据点到超平面的间隔为：
机器学习算法——支持向量机（SVM）
间隔如下图灰色部分，可以看出绿线和蓝线分类效果没有橙线效果好。

由于 $(w^T x+b)·y_i=y_i f(x)>0$ 。我们可以成倍的缩放 $w$ 和 $b$ 使得 $y_i f(x)≥1$ ，我们的目标是要找到一个超平面，使得离超平面最近的数据点间的间隔最大。即：
机器学习算法——支持向量机（SVM）
在支持向量机中，距离超平面最近的且满足一定条件的几个样本点称之为支持向量。
因：

即求

要使得 $1/‖w‖$ 最大，那么 $‖w‖$ 就要最小，上式展开转化为求：

对于这个式子，我们回顾上面的拉格朗日乘子法发现，就和其标准格式一样
机器学习算法——支持向量机（SVM）
将①转化为拉格朗日乘子法形式：

因为引入了拉格朗日乘子α，我们优化目标就转化为要求：

机器学习算法——支持向量机（SVM）
由于我们求α的极大值并不容易，所以我们可以根据对偶问题，将

这样求 $L(w,b,a)$ 的极小值就比较容易了，只要对 $w$ 和 $b$ 求偏导就可以得到结果。

将③④带入②中，计算过程省略，最后得出结果：
机器学习算法——支持向量机（SVM）
接着对φ(α)求极大值，将1/2的负号提出，负数的极大值即为正数的极小值，等价：

其中 $x_i^T x_j$ 是两个数据点的内积。以上即为线性支持向量机目标函数构建推导过程了，最后根据已知的数据点 $（x_i,y_i）$ 计算：
机器学习算法——支持向量机（SVM）
的极小值，通常采用SMO算法进行求解，求出 $α$ 后，带入即可以得到 $w$ 和 $b$ ，以及分隔超平面 $w^T x+b=0$ 。
SMO算法可见：https://www.jianshu.com/p/eef51f939ace

3 软间隔线性支持向量机

假如一个数据点绝大部分都是可分的，但有一些异常点落入了超平面的间隔当中，如图：
机器学习算法——支持向量机（SVM）
如果硬要将其分开，可能会导致超平面的间隔小于1，无法使分类效果达到最佳。所以为了照顾到绝大多数点都能被正确分类，我们要容忍这些异常的点，出现在不该不出现的地方。所以为了使得异常点的函数间隔 $(w^T x+b)·y_i$ 也能≥1，引入了松弛因子 $ξ_i$ ，即： $(w^T x+b)·y_i+ξ_i≥1$
原始的目标函数也会因容忍这些异常点而调整，需在原始的目标函数后面加上因为容忍异常点产生的代价，新的目标函数为：
机器学习算法——支持向量机（SVM）
其中C为惩罚系数，C越大，对误分类的惩罚越大，而函数模型为了避免惩罚，就会尽可能的减少误分类的样本点，所以函数的带宽（间隔）就会越窄；相反，C越小，对误分类的惩罚就越小，函数模型可以较多地包容那些误分类的点，函数的间隔也就会越宽。就像父母教育小孩，因为惩罚系数大，小孩尽可能的不犯任何错误，但这会导致“过拟合”的风险；但如果过分溺爱，小孩容易无法无天。
其步骤和前面的线性SVM类似，现将该目标函数用拉格朗日乘子法表示：
机器学习算法——支持向量机（SVM）
其中 $μ_i≥0$ ， $a_i≥0$ ，均为拉格朗日乘子系数
接着对 $L(w,b,a,ξ_i,μ_i )$ 中的参数 $w、b、ξ_i$ 求偏导，并使导函数为0：

机器学习算法——支持向量机（SVM）
将⑥⑦⑧带入 $L(w,b,a,ξ_i,μ_i )$ 式中，得到：

我们发现最后结果和未引入松弛因子的线性SVM是一样的，只是约束条件发生了改变。因为 $C-α_i=μ_i≥0$ ，我们可以得到： $0≤α_i≤C$ ，整理完约束条件软间隔线性SVM的最终结果为：
机器学习算法——支持向量机（SVM）
最后我们可以通过SMO算法，求出 $w$ 和 $b$ 。
不过在进行数据分类时，为了使得每个样本点的函数间隔大于等于1，我们引入了松弛因子 $ξ_i$ 。如果所有样本点的函数间隔都大于等于1，那么采用线性可分SVM就能正确分类；如果存在样本点的函数间隔小于1，这时则需要借助松弛因子 $ξ_i$ ，让其间隔 $d+ξ_i≥1$ ，间隔越小则 $ξ_i$ 越大，对应函数模型的损失也越大。如果 $ξ_i=0$ ，表示该样本点的间隔为1，在边界上为支持向量，如下图所示X1；如果 $0＜ξ_i＜1$ ，表示该样本点在超平面和自己类别的间隔边界之间，如X2；如果 $ξ_i=1$ ，表示样本点在超平面上，无法被分类；如果 $ξ_i＞1$ ，表示样本点的间隔为负数，即在超平面的另一侧，说明这个样本点无法被正确分类，如X3。
机器学习算法——支持向量机（SVM）

4 非线性可分支持向量机

前两节所针对的数据均为线性可分的，采用线性超平面就可以很好地将样本点区分开来。但采用线性超平面分割非线性可分数据，将产生很差的效果，如下图：
机器学习算法——支持向量机（SVM）
这时，就需要想样本点数据映射到高维空间中，最终总会在一个高维空间中有一个超平面使其线性可分。所以建立非线性可分SVM需要：（1）将原始数据映射到高维；（2）在高维空间中找到一个超平面，将样本点分类。
我们将样本点x映射到高维空间的变化设为 $ϕ(x_i )$ ，这种映射在二维空间中即为内积，就是前文的 $x_i^T x_j$ 。非线性SVM的目标函数可以表示为：
机器学习算法——支持向量机（SVM）
对于 $ϕ(x_i )·ϕ(x_j )$ 可以用核函数 $K(x_i,x_j )$ 表示，即 $K(x_i,x_j )= ϕ(x_i )·ϕ(x_j )$ 。对于这个函数 $K(x_i,x_j )$ ，我们称之为核函数。核函数低维上进行计算，而将实质上的分类效果（利用了内积）表现在了高维上，这样避免了直接在高维空间中的复杂计算，真正解决了SVM线性不可分的问题。
前人已经发现了很多核函数，在实际应用中可供我们选择，具体如下：
（1）线性核函数
机器学习算法——支持向量机（SVM）
线性核函数实际上就是线性可分SVM的函数模型，但其缺点是只能解决线性可分的问题。
（2）多项式核函数

（3）高斯核函数

对于非线性可分的数据常常使用高斯核函数，因为高斯核函数是指数函数，可以将低维数据映射到无穷维。下图即为对上面的数据集采用高斯核函数的分类结果：
机器学习算法——支持向量机（SVM）

5 一个实例

利用sklearn提供的svm方法对于鸢尾花数据集进行分类，也算是一个很经典的实战案例。

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import os
%matplotlib inline

#os.getcwd()
#os.chdir('C:\\Users\\HP')
df=pd.read_csv('iris.csv')

#print(df)

#添加列标签
df.columns = ['s_len', 's_wid', 'p_len', 'p_wid', 'class']
df.head()
#数据描述
#df.describe()

机器学习算法——支持向量机（SVM）
输出的是该数据集的前五条数据，s_len和s_wid分别为鸢尾花的花萼长度和宽度，p_len和p_wid为鸢尾花花瓣的长度和宽度，class为鸢尾花的种类，该数据中有三种类别。

#可视化，画矩阵图
import seaborn as sns
sns.set()
sns.pairplot(df,hue='class',size=2.5)

机器学习算法——支持向量机（SVM）
从图中可以看出，在花瓣长度宽度上，三种花的区别还是比较大的，所以采用p_len和p_wid这两列数据进行分析。

#小提琴图
plt.figure(figsize=(20, 14))
for column_index, column in enumerate(df.columns):
    if column == 'class':
        continue
    plt.subplot(2, 2, column_index + 1)
    sns.violinplot(x='class', y=column, data=df)

机器学习算法——支持向量机（SVM）
同样是可视化一种对数据的表现形式

from sklearn.cross_validation import train_test_split

X = df[['s_len', 's_wid','p_len', 'p_wid']].values
y = df['class'].values
X=X[:,2:4]
x=X
y = pd.Categorical(y).codes #将类别信息转化为数值信息
#print(y)
(x_train, x_test, y_train, y_test) = train_test_split(X,y,train_size=0.7, random_state=0)
#train_test_split为简单的交叉验证：随机将数据划分为两部分，训练集和测试集。一般 70%的数据为训练集，30%为测试集。
#random_state填1的话，其他参数一样的情况下你得到的随机数组是一样的。但填0或不填，每次都会不一样。
#print(X_train)

x_train，y_train为那70%的数据集，用来给机器学习。
x_test，y_test为用来测试机器学习准不准确的那30%数据，其中y_test是机器根据之前的学习然后预测的值。

#构建函数模型
from sklearn.svm import SVC
clf=SVC(kernel='rbf',gamma=0.1,decision_function_shape='ovo',C=0.8)
# kernel='rbf'（default）时，为高斯核函数，gamma值越小，分类界面越连续；gamma值越大，分类界面越“散”，分类效果越好，但有可能会过拟合。
# decision_function_shape='ovo'时，为one v one分类问题，即将类别两两之间进行划分，用二分类的方法模拟多分类的结果。
# decision_function_shape='ovr'时，为one v rest分类问题，即一个类别与其他类别进行划分。

采用高斯核函数

#训练
from sklearn.metrics import accuracy_score

clf.fit(x_train,y_train)

print ('测试集准确率：',accuracy_score(y_test,clf.predict(x_test)))

输出结果：测试集准确率： 0.9555555555555556

接下来对预测的数据进行绘图，首先建立网格

# 创建网格，以绘制图像
N=500
x1_min, x2_min = x[:,0].min(),x[:,1].min()
x1_max, x2_max = x[:,0].max(),x[:,1].max()
#print(x1_min, x2_min)
#print(x1_max, x2_max)

t1 = np.linspace(x1_min, x1_max, N)
t2 = np.linspace(x2_min, x2_max, N)
x1, x2 = np.meshgrid(t1, t2)  # 生成网格采样点
grid_show = np.dstack((x1.flat, x2.flat))[0] # 测试点
#print(grid_show)

grid_hat = clf.predict(grid_show)       # 预测分类值
grid_hat = grid_hat.reshape(x1.shape)  # 使之与输入的形状相同
#print(grid_hat)

#准备绘图
import matplotlib as mpl

cm_light = mpl.colors.ListedColormap(['yellow', 'pink', '#A0A0FF'])#背景颜色
cm_dark = mpl.colors.ListedColormap(['g', 'r', 'b'])#点的颜色
plt.figure(facecolor='w')

定义各label值

plt.pcolormesh(x1, x2, grid_hat, cmap=cm_light)#画背景图
plt.scatter(x[:,0], x[:,1], c=y, edgecolors='k', s=66, cmap=cm_dark) # 样本
plt.scatter(x_test[0], x_test[1], s=120, facecolors='none', zorder=10) # 圈中测试集样本
plt.xlabel('petal_length', fontsize=13)#坐标轴名称
plt.ylabel('petal_width', fontsize=13)
plt.xlim(x1_min, x1_max)#坐标轴范围
plt.ylim(x2_min, x2_max)
plt.title('Feature classification of iris by SVM', fontsize=20)
#plt.grid()
plt.show()

最后结果如图：
机器学习算法——支持向量机（SVM）
在数据分类可视化这一方面搞了半天，还有待加强^ ^

机器学习算法——支持向量机（SVM）

机器学习算法——支持向量机（SVM）

0 前序

1 介绍

1.1 距离公式介绍

1.2 拉格朗日乘子法

2 线性可分支持向量机

3 软间隔线性支持向量机

4 非线性可分支持向量机

5 一个实例

相关推荐