线性可分支持向量机与硬间隔最大化

参考文献：【支持向量机(分类问题公式及python实现)】

支持向量机（SVM）是一种二类分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器。它的学习策略是间隔最大化。可形式化为一个求解凸二次规划的问题。支持向量机的学习算法是求解凸二次规划的最优化算法。

• 当训练数据线性可分时，通过硬间隔最大化，学习一个线性的分类器，即线性可分支持向量机，又称为硬间隔支持向量机；
• 当训练数据近似线性可分时，通过软间隔最大化，也学习一个线性的分类器，即线性支持向量机，又称为软间隔支持向量机；
• 当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性支持向量机。

当输入空间为欧氏空间或离散集合、特征空间为希尔伯特空间时，核函数表示将输入从输入空间映射到特征空间得到的特征向量之间的内积。通过使用核函数可以学习非线性支持向量机，等价于隐式地在高维的特征空间中学习线性支持向量机。这样的方法称为核技巧。

考虑一个二类分类问题。假设输入空间与特征空间为两个不同的空间。输入空间为欧氏空间或离散集合，特征空间为欧氏空间或希尔伯特空间。线性可分支持向量机、线性支持向量机假设这两个空间的元素一一对应，并将输入空间中的输入映射为特征空间中的特征向量。非线性支持向量机利用一个从输入空间到特征空间的非线性映射将输入映射为特征向量。所以。输入都由输入空间转换到特征空间，支持向量机的学习是在特征空间进行的。

假设给定一个特征空间上的训练数据集：
T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } (1) T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)} tag 1 T={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}(1)
其中， x i ∈ χ = R n x_i in chi=R^n xi​∈χ=Rn， y i ∈ γ = { + 1 , − 1 } y_i in gamma={+1,-1} yi​∈γ={+1,−1}, i = 1 , 2 , . . . , N i=1,2,...,N i=1,2,...,N。 x i x_i xi​为第 i i i个特征向量，也称为实例， y i y_i yi​为 x i x_i xi​的类标记。当 y i = + 1 y_i=+1 yi​=+1时，称 x i x_i xi​为正例；当 y i = − 1 y_i=-1 yi​=−1时，称 x i x_i xi​为负例。 ( x i , y i ) (x_i,y_i) (xi​,yi​)称为样本点。假设训练样本集是线性可分的（检查凸包（convex hull）是否相交）。
学习的目标是在特征空间中找到一个分离超平面，能将实例分到不同的类。分离超平面对应于方程 w ⋅ x + b = 0 w·x+b=0 w⋅x+b=0，它由法向量 w w w和截距 b b b决定，可用 ( w , b ) (w,b) (w,b)来表示。分离超平面将特征空间划分为两部分，一部分是正类，一部分是负类。法向量指向的一侧为正类，另一侧为负类。
一般地，当训练数据集线性可分时，存在无穷个分离超平面可将两类数据正确分开。
感知机利用误分类最小的策略，求得分离超平面，不过这时的解有无穷多个。线性可分支持向量机利用间隔最大化求最优分离超平面，这时，解是唯一的。
分离超平面：
w ∗ ⋅ x + b ∗ = 0 (2) w^{*}·x+b^{*}=0 tag 2 w∗⋅x+b∗=0(2)
相应的分类决策函数：
f ( x ) = s i g n ( w ∗ ⋅ x + b ∗ ) (3) f(x)=sign(w^{*}·x+b^{*}) tag 3 f(x)=sign(w∗⋅x+b∗)(3)

形象引入：
如果有三个点A、B、C，表示3个实例，均在分离超平面的正类一侧，预测它们的类。点A距分离超平面较远，若预测点为正类，就比较确信预测是正确的；点C距分离超平面较近，若预测点为正类就不那么确信；点B介于点A与点C之间，预测其为正类的确信度也在A与C之间。
概念引入：
一般来说，一个点距离分离超平面的远近可以表示分类预测的确信程度。在超平面 w ⋅ x + b = 0 w·x+b=0 w⋅x+b=0确定的情况下， ∣ w ⋅ x + b ∣ |w·x+b| ∣w⋅x+b∣能够相对地表示点 x x x距离超平面的远近。而 w ⋅ x + b w·x+b w⋅x+b的符号与类标记 y y y的符号是否一致能够表示分类是否正确。所以可用量 y ( w ⋅ x + b ) y(w·x+b) y(w⋅x+b)来表示分类的正确性及确信度，这就是函数间隔的概念。
定义：
对于给定的训练数据集 T T T和超平面 ( w , b ) (w,b) (w,b)，定义超平面 ( w , b ) (w,b) (w,b)关于样本点 ( x i , y i ) (x_i,y_i) (xi​,yi​)的函数间隔为：
γ i ^ = y i ( w ⋅ x i + b ) (4) hat{gamma_i}=y_i(w·x_i+b) tag 4 γi​^​=yi​(w⋅xi​+b)(4)
定义超平面 ( w , b ) (w,b) (w,b)关于训练数据集 T T T的函数间隔为超平面 ( w , b ) (w,b) (w,b)关于 T T T中所有样本点 ( x i , y i ) (x_i,y_i) (xi​,yi​)的函数间隔之最小值，即：
γ ^ = min ⁡ i = 1 , . . . , N γ i ^ (5) hat{gamma}=min_{i=1,...,N} hat{gamma_i} tag 5 γ^​=i=1,...,Nmin​γi​^​(5)
函数间隔可以表示分类预测的正确性及确信度。但是选择分离超平面时，只有函数间隔还不够。因为只要成比例地改变 w w w和 b b b，例如将它们改为 2 w 2w 2w和 2 b 2b 2b，超平面并没有改变，但是函数间隔却成为原来的2倍。
我们得到如下启示，可以对分离超平面的法向量 w w w加某些约束，如规范化， ∣ ∣ w ∣ ∣ = 1 ||w||=1 ∣∣w∣∣=1，使得间隔是确定的。由此引出几何间隔：
点A与超平面 ( w , b ) (w,b) (w,b)的距离由线段AB给出，记作 γ i gamma_i γi​：
γ i = w ∣ ∣ w ∣ ∣ ⋅ x i + b ∣ ∣ w ∣ ∣ (6) gamma_i=frac{w}{||w||}·x_i+frac{b}{||w||} tag 6 γi​=∣∣w∣∣w​⋅xi​+∣∣w∣∣b​(6)
其中， ∣ ∣ w ∣ ∣ ||w|| ∣∣w∣∣为 w w w的 L 2 L_2 L2​范数。这是点A在超平面正的一侧的情形。如果点A在超平面负的一侧，即 y i = − 1 y_i=-1 yi​=−1，那么点与超平面的距离为：
γ i = − ( w ∣ ∣ w ∣ ∣ ⋅ x i + b ∣ ∣ w ∣ ∣ ) (7) gamma_i=-(frac{w}{||w||}·x_i+frac{b}{||w||}) tag 7 γi​=−(∣∣w∣∣w​⋅xi​+∣∣w∣∣b​)(7)
一般地，当样本点 ( x i , y i ) (x_i,y_i) (xi​,yi​)被超平面 ( w , b ) (w,b) (w,b)正确分类时，点 x x x与超平面 ( w , b ) (w,b) (w,b)的距离是：
γ i = y i ( w ∣ ∣ w ∣ ∣ ⋅ x i + b ∣ ∣ w ∣ ∣ ) (8) gamma_i=y_i(frac{w}{||w||}·x_i+frac{b}{||w||}) tag 8 γi​=yi​(∣∣w∣∣w​⋅xi​+∣∣w∣∣b​)(8)
几何间隔的定义：
对于给定的训练数据集 T T T和超平面 ( w , b ) (w,b) (w,b)，定义超平面 ( w , b ) (w,b) (w,b)关于样本点 ( x i , y i ) (x_i,y_i) (xi​,yi​)的函数间隔为：
γ i = y i ( w ∣ ∣ w ∣ ∣ ⋅ x i + b ∣ ∣ w ∣ ∣ ) (9) gamma_i=y_i(frac{w}{||w||}·x_i+frac{b}{||w||}) tag 9 γi​=yi​(∣∣w∣∣w​⋅xi​+∣∣w∣∣b​)(9)
定义超平面 ( w , b ) (w,b) (w,b)关于训练数据集 T T T的函数间隔为超平面 ( w , b ) (w,b) (w,b)关于 T T T中所有样本点 ( x i , y i ) (x_i,y_i) (xi​,yi​)的函数间隔之最小值，即：
γ = min ⁡ i = 1 , . . . , N γ i (10) gamma=min_{i=1,...,N} gamma_i tag {10} γ=i=1,...,Nmin​γi​(10)
函数间隔和几何间隔有下面的关系：
γ = γ ^ ∣ ∣ w ∣ ∣ (11) gamma=frac{hat{gamma}}{||w||} tag {11} γ=∣∣w∣∣γ^​​(11)

间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。也就是说，不仅将正负实例分开，而且对最难分的实例点（离超平面最近的点）也有足够大的确信度将它们分开。这样的超平面应该对未知的新实例有很好的分类预测能力。

问题转化为：
max ⁡ w , b γ s . t .   y i ( w ∣ ∣ w ∣ ∣ ⋅ x i + b ∣ ∣ w ∣ ∣ ) ≥ γ , i = 1 , 2 , . . . , N (12) max_{w,b} gamma \ s.t. y_i(frac{w}{||w||}·x_i+frac{b}{||w||}) geq gamma,i=1,2,...,N tag {12} w,bmax​γs.t. yi​(∣∣w∣∣w​⋅xi​+∣∣w∣∣b​)≥γ,i=1,2,...,N(12)
即我们希望最大化超平面 ( w , b ) (w,b) (w,b)关于训练数据集的几何间隔 γ gamma γ，约束条件表示的是超平面 ( w , b ) (w,b) (w,b)关于每个训练样本点的几何间隔至少是 γ gamma γ。
考虑式 ( 11 ) (11) (11)，问题转化为：
max ⁡ w , b γ ^ ∣ ∣ w ∣ ∣ s . t .   y i ( w ⋅ x i + b ) ≥ γ ^ , i = 1 , 2 , . . . , N (13) max_{w,b} frac{hat{gamma}}{||w||} \ s.t. y_i(w·x_i+b) geq hat{gamma},i=1,2,...,N tag {13} w,bmax​∣∣w∣∣γ^​​s.t. yi​(w⋅xi​+b)≥γ^​,i=1,2,...,N(13)
函数间隔 γ ^ hat{gamma} γ^​的取值并不影响最优化问题的解。事实上，假设将 w w w和 b b b按比例改变为 λ w lambda w λw和 λ b lambda b λb，这是函数间隔成为 λ γ ^ lambda hat{gamma} λγ^​。但是这一改变对不等式约束没有影响。取 γ ^ = 1 hat{gamma}=1 γ^​=1，将 γ ^ = 1 hat{gamma}=1 γ^​=1代入上面的最优化问题，将最大化 1 ∣ ∣ w ∣ ∣ frac{1}{||w||} ∣∣w∣∣1​和最小化 1 2 ∣ ∣ w ∣ ∣ 2 frac{1}{2} ||w||^2 21​∣∣w∣∣2是等价的。线性可分支持向量机学习的最优化问题：
min ⁡ w , b 1 2 ∣ ∣ w ∣ ∣ 2 s . t .   y i ( w ⋅ x i + b ) ≥ 1 , i = 1 , 2 , . . . , N (14) min_{w,b} frac{1}{2} ||w||^2 \ s.t. y_i(w·x_i+b) geq 1,i=1,2,...,N tag {14} w,bmin​21​∣∣w∣∣2s.t. yi​(w⋅xi​+b)≥1,i=1,2,...,N(14)
该问题是一个凸二次规划问题。

输入：线性可分支持向量机数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)} T={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}，其中， x i ∈ χ = R n x_i in chi=R^n xi​∈χ=Rn， y i ∈ γ = { + 1 , − 1 } y_i in gamma={+1,-1} yi​∈γ={+1,−1}, i = 1 , 2 , . . . , N i=1,2,...,N i=1,2,...,N；
输出：最大间隔分离超平面和分类决策函数。

1. 构造并求解约束最优化问题：
   min ⁡ w , b 1 2 ∣ ∣ w ∣ ∣ 2 s . t .   y i ( w ⋅ x i + b ) ≥ 1 , i = 1 , 2 , . . . , N min_{w,b} frac{1}{2} ||w||^2 \ s.t. y_i(w·x_i+b) geq 1,i=1,2,...,N w,bmin​21​∣∣w∣∣2s.t. yi​(w⋅xi​+b)≥1,i=1,2,...,N
   求得最优解 w ∗ , b ∗ w^{*},b^{*} w∗,b∗。
2. 得到分离超平面：
   w ∗ ⋅ x + b ∗ = 0 w^{*}·x+b^{*}=0 w∗⋅x+b∗=0
   相应的分类决策函数：
   f ( x ) = s i g n ( w ∗ ⋅ x + b ∗ ) f(x)=sign(w^{*}·x+b^{*}) f(x)=sign(w∗⋅x+b∗)

存在唯一性的证明

在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量（support vector）。支持向量是使约束条件式 ( 14 ) (14) (14)等号成立的点，即：
y i ( w ⋅ x i + b ) − 1 = 0 y_i(w·x_i+b)-1=0 yi​(w⋅xi​+b)−1=0
对于 y i = + 1 y_i=+1 yi​=+1的正例点，支持向量在超平面：
H 1 : w ⋅ x + b = 1 H_1:w·x+b=1 H1​:w⋅x+b=1
上，对 y i = − 1 y_i=-1 yi​=−1的负例点，支持向量在超平面：
H 2 : w ⋅ x + b = − 1 H_2:w·x+b=-1 H2​:w⋅x+b=−1
上。如下图所示：

在 H 1 H_1 H1​和 H 2 H_2 H2​上的点称为支持向量。
注意到两条虚线平行，并且没有实例点落在他们中间。在 H 1 H_1 H1​和 H 2 H_2 H2​之间形成了一条长带，分离超平面与它们平行且位于它们中央。长带的宽度，即 H 1 H_1 H1​和 H 2 H_2 H2​之间的距离成为间隔（margin）。间隔依赖于分离超平面的法向量 w w w，等于 2 ∣ ∣ w ∣ ∣ frac{2}{||w||} ∣∣w∣∣2​。 H 1 H_1 H1​和 H 2 H_2 H2​称为间隔边界。

在决定分离超平面时只有支持向量起作用，而其他实例点并不起作用。如果移动支持向量将改变所求的解，但是如果在间隔边界以外移动其他实例点，甚至去掉这些点，则解是不会改变的。
支持向量的个数一般很少，所以支持向量机由很少的“重要的”训练样本确定。

链接：https://pan.baidu.com/s/1WBw0lHzdcZlCu0AV8r1kmw
提取码：1234

# 导包
import matplotlib.pyplot as plt
import seaborn; seaborn.set()  # 设置图样为seaborn风格
import numpy as np
import pandas as pd

# 导入数据
data = pd.read_excel('3-iris 数据集（2类）.xls',header=None)
X = np.array(data.iloc[:,2:4]) # 截取两维
y = np.array(data.iloc[:,4])

# sklearn.svm学习
from sklearn.svm import SVC # 导入SVC类 SVC(Support vector classifier)
model = SVC(kernel='linear', C=1E10) # 引入线性核函数
model.fit(X, y)

# 画2维SVC的决策函数（分离超平面）
def plot_svc_decision_function(model, ax=None, plot_support=True):
    """画2维SVC的决策函数（分离超平面）"""
    if ax is None:
        ax = plt.gca() # plt.gca()获得当前的Axes对象ax
    xlim = ax.get_xlim() # Return the x-axis view limits返回x轴视图限制。
    ylim = ax.get_ylim() 
    # 创建评估模型的网格
    x = np.linspace(xlim[0], xlim[1], 30)
    y = np.linspace(ylim[0], ylim[1], 30)
    X, Y = np.meshgrid(x, y) # 将两个一维数组变为二维矩阵 返回一个行乘和列乘的二维数组
    xy = np.vstack([X.ravel(), Y.ravel()]).T # np.vstack()沿着竖直方向将矩阵堆叠起来。 
    P = model.decision_function(xy).reshape(X.shape)
    # 画决策边界和边界
    ax.contour(X, Y, P, colors='k',
               levels=[-1, 0, 1], alpha=0.5,
               linestyles=['--', '-', '--'])
    # 画支持向量
    if plot_support:
        ax.scatter(model.support_vectors_[:, 0],
                   model.support_vectors_[:, 1],
                   s=200, linewidth=1,c='k',alpha=0.4)
    ax.set_xlim(xlim)
    ax.set_ylim(ylim)
    ax.set_title('Linear Separated SVM')
plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='autumn')
plot_svc_decision_function(model)

图示：

对偶算法