# 线性可分与线性不可分图例
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.font_manager import FontProperties
%matplotlib inline

font = FontProperties(fname='/Library/Fonts/Heiti.ttc')
np.random.seed(1)

x1 = np.random.random(20)+1.5

y1 = np.random.random(20)+0.5

x2 = np.random.random(20)+3

y2 = np.random.random(20)+0.5
# 一行二列第一个

plt.subplot(121)

plt.scatter(x1, y1, s=50, color='b', label='男孩(+1)')

plt.scatter(x2, y2, s=50, color='r', label='女孩(-1)')

plt.vlines(2.8, 0, 2, colors="r", linestyles="-", label='(wx+b=0)')

plt.title('线性可分', fontproperties=font, fontsize=20)

plt.xlabel('x')

plt.legend(prop=font)
# 一行二列第二个

plt.subplot(122)

plt.scatter(x1, y1, s=50, color='b', label='男孩(+1)')

plt.scatter(x2, y2, s=50, color='r', label='女孩(-1)')

plt.scatter(3.5, 1, s=50, color='b')

plt.scatter(3.6, 1.2, s=50, color='b')

plt.scatter(3.9, 1.3, s=50, color='b')

plt.scatter(3.8, 1.3, s=50, color='b')

plt.scatter(3.7, 0.6, s=50, color='b')

plt.title('线性不可分', fontproperties=font, fontsize=20)

plt.xlabel('x')

plt.legend(prop=font)

plt.show()

# 确信度图例
import matplotlib.pyplot as plt
from matplotlib.font_manager import FontProperties
%matplotlib inline
font = FontProperties(fname='/Library/Fonts/Heiti.ttc')
x1 = [1, 2, 2.5, 3.2]

x11 = [4.5, 5, 6]

x2 = [1, 1.2, 1.4, 1.5]

x22 = [1.5, 1.3, 1]
plt.scatter(x1, x2, s=50, color='b', label='+1')

plt.scatter(x11, x22, s=50, color='r', label='-1')

plt.vlines(3.5, 0.8, 2, colors="g", linestyles="-", label='(w*x+b=0)')

plt.text(2, 1.3, s='A', fontsize=15, color='k', ha='center')

plt.text(2.5, 1.5, s='B', fontsize=15, color='k', ha='center')

plt.text(3.2, 1.6, s='C', fontsize=15, color='k', ha='center')

plt.legend()

plt.show()

# 间隔最大化图例
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.font_manager import FontProperties
from sklearn import svm
%matplotlib inline
font = FontProperties(fname='/Library/Fonts/Heiti.ttc')
np.random.seed(8)  # 保证数据随机的唯一性
# 构造线性可分数据点

array = np.random.randn(20, 2)

X = np.r_[array-[3, 3], array+[3, 3]]

y = [0]20+[1]20
# 建立svm模型

clf = svm.SVC(kernel='linear')

clf.fit(X, y)
# 构造等网个方阵

x1_min, x1_max = X[:, 0].min(), X[:, 0].max(),

x2_min, x2_max = X[:, 1].min(), X[:, 1].max(),

x1, x2 = np.meshgrid(np.linspace(x1_min, x1_max),

np.linspace(x2_min, x2_max))
# 得到向量w: w_0x_1+w_1x_2+b=0

w = clf.coef_[0]
# 加1后才可绘制 -1 的等高线 [-1,0,1] + 1 = [0,1,2]

f = w[0]x1 + w[1]x2 + clf.intercept_[0] + 1
# 绘制H1，即wx+b=-1

plt.contour(x1, x2, f, [0], colors='k', linestyles='--')

plt.text(2, -4, s='(H_2={omega}x+b=-1)', fontsize=10, color='r', ha='center')
# 绘制分隔超平面，即wx+b=0

plt.contour(x1, x2, f, [1], colors='k')

plt.text(2.5, -2, s='(omega{x}+b=0)', fontsize=10, color='r', ha='center')

plt.text(2.5, -2.5, s='分离超平面', fontsize=10,

color='r', ha='center', fontproperties=font)
# 绘制H2，即wx+b=1

plt.contour(x1, x2, f, [2], colors='k', linestyles='--')

plt.text(3, 0, s='(H_1=omega{x}+b=1)', fontsize=10, color='r', ha='center')
# 绘制数据散点图

plt.scatter(X[0:20, 0], X[0:20, 1], cmap=plt.cm.Paired, marker='x')

plt.text(1, 1.8, s='支持向量', fontsize=10, color='gray',

ha='center', fontproperties=font)
plt.scatter(X[20:40, 0], X[20:40, 1], cmap=plt.cm.Paired, marker='o')

plt.text(-1.5, -0.5, s='支持向量', fontsize=10,

color='gray', ha='center', fontproperties=font)
# plt.scatter(clf.support_vectors_[:,0],clf.support_vectors_[:,1) # 绘制支持向量点
plt.xlim(x1_min-1, x1_max+1)

plt.ylim(x2_min-1, x2_max+1)

plt.show()

一、线性可分支持向量机学习目标

1. 线性可分支持向量机、线性支持向量机、非线性支持向量机区别
2. 函数间隔与几何间隔
3. 目标函数与目标函数的优化问题
4. 支持向量和间隔边界
5. 线性可分支持向量机的步骤

二、支持向量机引入

支持向量机（support vector machines，SVM）诞生二十多年，由于它良好的分类性能席卷了机器学习领域，如果不考虑集成学习、不考虑特定的训练数据集，SVM由于泛化能力强，因此在分类算法中的表现排第一是没有什么异议的，通常情况下它也是首选分类器。近几年SVM在图像分类领域虽有被深度学习赶超的趋势，但由于深度学习需要大量的数据驱动因此在某些领域SVM还是无法替代的。

SVM是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大化也使它不同于感知机；SVM还有核技巧，也因此它也是一个非线性分类器。

SVM通过学得模型构建的难度由简至繁可以划分为以下三种：

1. 线性可分支持向量机（linear support vector machine in linearly separable case）：当训练数据线性可分时，通过硬间隔最大化（hard margin maximization）学习一个线性的分类器，即线性可分支持向量机，也称作硬间隔支持向量机
2. 线性支持向量机（linear support vector machine）：当训练数据近似线性可分时，通过软间隔最大化（soft margin maximization）也学习一个线性分类器，即线性支持向量机，也称作软间隔支持向量机
3. 非线性支持向量机（non-linear support vector machine）：当训练数据线性不可分时，通过使用核技巧（kernel trick）及软间隔最大化，学习一个非线性支持向量机

2.1 线性可分和线性不可分

由于《感知机》一文中详细的介绍过线性可分与线性不可分的区别，这里只给出图例便于理解线性支持向量机和非线性支持向量机。

# 线性可分与线性不可分图例
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.font_manager import FontProperties
%matplotlib inline

font = FontProperties(fname='/Library/Fonts/Heiti.ttc')
np.random.seed(1)

x1 = np.random.random(20)+1.5

y1 = np.random.random(20)+0.5

x2 = np.random.random(20)+3

y2 = np.random.random(20)+0.5
# 一行二列第一个

plt.subplot(121)

plt.scatter(x1, y1, s=50, color='b', label='男孩(+1)')

plt.scatter(x2, y2, s=50, color='r', label='女孩(-1)')

plt.vlines(2.8, 0, 2, colors="r", linestyles="-", label='(wx+b=0)')

plt.title('线性可分', fontproperties=font, fontsize=20)

plt.xlabel('x')

plt.legend(prop=font)
# 一行二列第二个

plt.subplot(122)

plt.scatter(x1, y1, s=50, color='b', label='男孩(+1)')

plt.scatter(x2, y2, s=50, color='r', label='女孩(-1)')

plt.scatter(3.5, 1, s=50, color='b')

plt.scatter(3.6, 1.2, s=50, color='b')

plt.scatter(3.9, 1.3, s=50, color='b')

plt.scatter(3.8, 1.3, s=50, color='b')

plt.scatter(3.7, 0.6, s=50, color='b')

plt.title('线性不可分', fontproperties=font, fontsize=20)

plt.xlabel('x')

plt.legend(prop=font)

plt.show()

2.2 感知机模型和支持向量机

《感知机》一文中详细讲解过感知机模型的原理，此处不多赘述，简单概括。

在二维空间中，感知机模型试图找到一条直线能够把二元数据分隔开；在高维空间中感知机模型试图找到一个超平面^=−1。

上张线性可分和线性不可分的区别图第一张图则找到了一条直线能够把二元数据分隔开，但是能够发现事实上可能不只存在一条直线将数据划分为两类，因此再找到这些直线后还需要找到一条最优直线，对于这一点感知机模型使用的策略是让所有误分类点到超平面的距离和最小，即最小化该式

上式中可以看出如果1，然后求分子的最小化作为代价函数，因此给定感知机的目标函数为

既然分子和分母有固定倍数，那么可不可以固定分子，把分母的倒数作为目标函数呢？一定是可以的，固定分子就是支持向量机使用的策略。

三、线性可分支持向量机详解

3.1 确信度

# 确信度图例
import matplotlib.pyplot as plt
from matplotlib.font_manager import FontProperties
%matplotlib inline
font = FontProperties(fname='/Library/Fonts/Heiti.ttc')
x1 = [1, 2, 2.5, 3.2]

x11 = [4.5, 5, 6]

x2 = [1, 1.2, 1.4, 1.5]

x22 = [1.5, 1.3, 1]
plt.scatter(x1, x2, s=50, color='b', label='+1')

plt.scatter(x11, x22, s=50, color='r', label='-1')

plt.vlines(3.5, 0.8, 2, colors="g", linestyles="-", label='(w*x+b=0)')

plt.text(2, 1.3, s='A', fontsize=15, color='k', ha='center')

plt.text(2.5, 1.5, s='B', fontsize=15, color='k', ha='center')

plt.text(3.2, 1.6, s='C', fontsize=15, color='k', ha='center')

plt.legend()

plt.show()

上图有均在超平面正类的A，B，C三个点。因为点A距离超平面远，如果预测为正类点，就比较确信预测时正确的；点C距离超平面较近，如果预测为正类点就不那么确信，因为超平面可能存在着多条，有可能有另一条更优的超平面x+b=0；点B介于A和C之间，则其预测为正类点的确信度介于A和C之间。

3.2 函数间隔和几何间隔

3.2.1 函数间隔

一个点距离超平面的远近可以表示分类预测的确信程度。在超平面固定位)表示分类的正确性和确信度，这就是函数间隔（functional margin）的概念。

给定数据集)的函数间隔为

对于训练集m个函数间隔的最小值，就是整个训练集的函数间隔，即

函数间隔并不能正常反应点到超平面的距离，因为只要成比例的改变b，超平面却并没有改变，但函数间隔却会变为原来的两倍。

3.2.2 几何间隔

由于函数间隔不能反应点到超平面的距离，因此可以对超平面的法向量|=1，使得间隔是确定的。此时的函数间隔将会变成几何间隔（geometric margin）。

对于某一实例yi，则改点的几何间隔的定义为

对于训练集m个函数间隔的最小值，就是整个训练集的几何间隔，即

几何间隔才是点到超平面的真正距离，感知机模型用到的距离就是几何间隔。

3.2.3 函数间隔和几何间隔的关系

由函数间隔和几何间隔的定义可知函数间隔和几何间隔有以下的关系

3.3 支持向量和间隔边界

由于可以找到多个超平面将数据分开导致离超平面近的点不确信度高，因此感知机模型优化时希望所有的点都离超平面远。但是离超平面较远的点已经被正确分类，让它们离超平面更远毫无意义。由于是离超平面近的点容易被误分类，因此次可以让离超平面较近的点尽可能的远离超平面，这样才能提升模型的分类效果，这正是SVM思想的起源。

# 间隔最大化图例
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.font_manager import FontProperties
from sklearn import svm
%matplotlib inline
font = FontProperties(fname='/Library/Fonts/Heiti.ttc')
np.random.seed(8)  # 保证数据随机的唯一性
# 构造线性可分数据点

array = np.random.randn(20, 2)

X = np.r_[array-[3, 3], array+[3, 3]]

y = [0]20+[1]20
# 建立svm模型

clf = svm.SVC(kernel='linear')

clf.fit(X, y)
# 构造等网个方阵

x1_min, x1_max = X[:, 0].min(), X[:, 0].max(),

x2_min, x2_max = X[:, 1].min(), X[:, 1].max(),

x1, x2 = np.meshgrid(np.linspace(x1_min, x1_max),

np.linspace(x2_min, x2_max))
# 得到向量w: w_0x_1+w_1x_2+b=0

w = clf.coef_[0]
# 加1后才可绘制 -1 的等高线 [-1,0,1] + 1 = [0,1,2]

f = w[0]x1 + w[1]x2 + clf.intercept_[0] + 1
# 绘制H1，即wx+b=-1

plt.contour(x1, x2, f, [0], colors='k', linestyles='--')

plt.text(2, -4, s='(H_2={omega}x+b=-1)', fontsize=10, color='r', ha='center')
# 绘制分隔超平面，即wx+b=0

plt.contour(x1, x2, f, [1], colors='k')

plt.text(2.5, -2, s='(omega{x}+b=0)', fontsize=10, color='r', ha='center')

plt.text(2.5, -2.5, s='分离超平面', fontsize=10,

color='r', ha='center', fontproperties=font)
# 绘制H2，即wx+b=1

plt.contour(x1, x2, f, [2], colors='k', linestyles='--')

plt.text(3, 0, s='(H_1=omega{x}+b=1)', fontsize=10, color='r', ha='center')
# 绘制数据散点图

plt.scatter(X[0:20, 0], X[0:20, 1], cmap=plt.cm.Paired, marker='x')

plt.text(1, 1.8, s='支持向量', fontsize=10, color='gray',

ha='center', fontproperties=font)
plt.scatter(X[20:40, 0], X[20:40, 1], cmap=plt.cm.Paired, marker='o')

plt.text(-1.5, -0.5, s='支持向量', fontsize=10,

color='gray', ha='center', fontproperties=font)
# plt.scatter(clf.support_vectors_[:,0],clf.support_vectors_[:,1) # 绘制支持向量点
plt.xlim(x1_min-1, x1_max+1)

plt.ylim(x2_min-1, x2_max+1)

plt.show()

如上图所示，分离超平面为x+b=0。如果所有的样本不光可以被分离超平面分开，还和分离超平面保持一定的函数间隔（上图的函数间隔为1）。

对于H2上的点就是支持向量（support vector）。

图中虚线所示的两个平行的超平面|。

由此可以看出只有支持向量决定分离超平面的位置，即其他实例点对分离超平面没有影响。正式由于支持向量在确定分离超平面的时候起着决定性的作用，所以将这种分类模型称作支持向量机。由于支持向量的个数一般很少，因此支持向量机由很少的重要的样本确定。

3.4 线性可分支持向量机目标函数即硬间隔最大化

上一节讲到了SVM的模型其实就是让所有点到分离超平面的距离大于一定的距离，即所有已被分类的点要在各自类别的支持向量的两边，即希望最大化超平面γ，这个问题可以表示为下面的约束最优化问题

其中γ。

通过函数间隔和几何间隔的关系，可以把上述式子改写成

如果将^=1。这样最优化问题变成了

可以看出这个最优化问题和感知机的优化问题是不同的，感知机是固定分母优化分子，而SVM在加上了支持向量的同时固定分子优化分母。

注意最大化|2，则可以得到线性可分支持向量机的最优化问题，即目标函数的最优化问题，即硬间隔最大化为

其中|2为目标函数

3.5 凸最优化问题

由于目标函数的最优化问题中的目标函数是连续可微的凸函数，约束函数是仿射函数（注：如果)称为仿射函数），则该问题是一个凸最优化问题。又由于目标函数是二次函数，则该凸最优化问题变成了凸二次规划问题。

如果求出了目标函数最优化问题中的解)（注：sign函数即符号函数，类似于Sigmoid函数的图形），即线性可分支持向量机模型。

3.6 线性可分支持向量机的最优化问题

根据凸优化理论，可以通过拉格朗日函数把优化有约束的目标函数转化为优化无约束的目标函数。既应用拉格朗日对偶性（注：详见《拉格朗日对偶性》），通过求解对偶问题得到原始问题的最优解，进而把线性可分支持向量机的最优化问题作为原始最优化问题，有时也称该方法为线性可分支持向量机的对偶算法（dual algorithm）。

首先引进拉格朗日乘子（Lagrange multiplier）i=1,2,…,m，然后构建拉格朗日函数（Lagrange function）

其中)T为拉格朗日乘子向量。

因此优化问题变成

由于这个优化问题满足Karush-Kuhn-Tucker(KKT)条件（注：详见《拉格朗日对偶性》）,既可以通过拉格朗日对偶性把上述的优化问题转化为等价的对偶问题，即优化目标变成

从上式中，则可以先求优化函数对于α的极大值。

1. 求)

通过对)的极小值

得

从b可能有多个。

将上述式子即可代入拉格朗日函数（注：由于推导过程十分复杂，对接下来的讲解无意，此处不给出推导过程，有兴趣的同学可以自行尝试，其中会用到范数的定义即)=aa+ab+ac+ba+bb+bc+…以及一些矩阵的运算），即得

从上式可以看出通过对b。

2. 求α的极大化

对)求极大化的数学表达式为

通过去掉负号，即可转化为等价的极小问题如下

一般通过SMO算法（注：详见《序列最小最优化算法》）求出上式极小化对应的ω∗为

由于对b∗都是一样的。

根据KKT条件中的对偶互补条件b∗为

四、线性可分支持向量机流程

4.1 输入

有−1。

4.2 输出

分离超平面的参数b∗以及分类决策函数

4.3 流程

1. 构造约束优化问题为

2. 使用SMO算法求出上式最小时对应的α∗
3. 计算w∗为

4. 找到一个支持向量，即满足b∗为

5. 求得分离超平面为

6. 求得分类决策函数为

在线性可分支持向量机中可以发现α∗>0的样本点即为支持向量。

由KKT互补条件可得对于w∗xj+b∗=−1，即支持向量一定在间隔边界上。

五、线性可分支持向量机优缺点

5.1 优点

1. 决策函数的计算取决于支持向量的数量，而不是样本空间的维数
2. 增删非支持向量对模型没有影响

5.2 缺点

1. 无法处理异常点
2. 不支持线性不可分数据的分类
3. 属于二分类分类器，如果需要多分类需要使用OVR等方法

六、小结

支持向量机是基于感知机模型演化而来的，解决了感知机模型可能会得到多个分类直线的问题，由于使用了硬间隔最大化支持向量机的目标函数只和支持向量的位置有关，大大降低了计算量。

线性可分支持向量机是支持向量机最原始的形式，由于使用了硬间隔最大化，因此无法做到对异常值和非线性可分数据的处理，此处不多赘述，让我们看他的升级版——线性支持向量机。