Task02
本次学习参照Datawhale开源学习：https://github.com/datawhalechina/machine-learning-toy-code/tree/main/ml-with-sklearn
内容安排如下，主要是一些代码实现和部分原理介绍。

2. 支持向量机

支持向量机（Support Vector Machine, SVM）是监督学习方式对数据进行二元分类的广义线性分类器（generalized linear classifier），其决策边界是对学习样本求解的最大边距超平面。支持向量机的三要素：间隔、对偶、核技巧。

2.1. 间隔

支持向量机的目的是：找到划分样本的最优平面。

超平面： w T x + b = 0 w^Tx+b=0 wTx+b=0。其中w：法向量，决定超平面方向b：位移项，决定超平面与原点之间的距离。
空间距离： r = ∣ w T x + b ∣ ∣ ∣ w ∣ ∣ r=\frac{|w^Tx+b|}{||w||} r=∣∣w∣∣∣wTx+b∣​。样本空间任意点x到超平面的距离。
支持向量： f ( x ) = { w T x i + b ⩾ 0 , y i = + 1 w T x i + b ⩽ 0 , y i = − 1 f(x)=\left\{ \begin{aligned} w^Tx_i+b\geqslant0,y_i=+1 \\ w^Tx_i+b\leqslant0,y_i=-1 \\ \end{aligned} \right. f(x)={wTxi​+b⩾0,yi​=+1wTxi​+b⩽0,yi​=−1​距离超平面最近的几个使上式成立的样本点。
间隔： r = 2 ∣ ∣ w ∣ ∣ r=\frac{2}{||w||} r=∣∣w∣∣2​。两个异类支持向量到超平面的距离和。
支持向量机基本型： m a x w , b 2 ∣ ∣ w ∣ ∣ \underset {w,b}{max}\frac{2}{||w||} w,bmax​∣∣w∣∣2​ s . t . y i ( w T x i + b ⩾ 1 ) , i = 1 , 2 , . . . , m . s.t. y_i(w^Tx_i+b\geqslant1),i=1,2,...,m. s.t.yi​(wTxi​+b⩾1),i=1,2,...,m.
找到具有最大间隔的划分超平面使得间隔最大。
m a x w , b 1 2 ∣ ∣ w ∣ ∣ 2 \underset {w,b}{max}\frac{1}{2}||w||^2 w,bmax​21​∣∣w∣∣2 s . t . y i ( w T x i + b ⩾ 1 ) , i = 1 , 2 , . . . , m . s.t. y_i(w^Tx_i+b\geqslant1),i=1,2,...,m. s.t.yi​(wTxi​+b⩾1),i=1,2,...,m.
为方便求解，等价于上式（凸二次规划问题）。

2.2. 对偶

要求解上式凸二次规划问题，通过引入拉格朗日乘子将含有n个变量和k个约束条件的优化问题转化为含有（n+k）个变量的无约束优化问题。使用拉格朗日乘子法得到其“对偶问题”，该问题的拉格朗日函数可写为： L ( w , b , α ) = 1 2 ∣ ∣ w ∣ ∣ 2 + ∑ i = 1 m α i ( 1 − y i ( w T x i + b ) ) L(w,b,α)=\frac{1}{2}||w||^2+\sum_{i=1}^{m}α_i(1-y_i(w^Tx_i+b)) L(w,b,α)=21​∣∣w∣∣2+i=1∑m​αi​(1−yi​(wTxi​+b))其中 α i α_i αi​为拉格朗日乘子。令 L ( w , b , α ) L(w,b,α) L(w,b,α)对 w w w和 b b b的偏导为零可得:
w = ∑ i = 1 m α i y i x i , 0 = ∑ i = 1 m α i y i w=\sum_{i=1}^{m}α_iy_ix_i,0=\sum_{i=1}^{m}α_iy_i w=i=1∑m​αi​yi​xi​,0=i=1∑m​αi​yi​
将上式代入拉格朗日函数中，将w和b消去，得到SVM基本型的对偶问题：
m a x α ∑ i = 1 m α i − 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j x i T x j \underset {α}{max}\sum_{i=1}^{m}α_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}α_iα_jy_iy_jx_i^Tx_j αmax​i=1∑m​αi​−21​i=1∑m​j=1∑m​αi​αj​yi​yj​xiT​xj​
s . t . ∑ i = 1 m α i y i = 0 , α i ⩾ 0 , i = 1 , 2 , . . . , m . s.t.\sum_{i=1}^{m}α_iy_i=0,α_i\geqslant0,i=1,2,...,m. s.t.i=1∑m​αi​yi​=0,αi​⩾0,i=1,2,...,m.上式中有不等式约束，因此上述过程需要满足KKT条件：

{ α i ⩾ 0 ; y i f ( x i ) − 1 ⩾ 0 ; α i ( y i f ( x i ) − 1 ) = 0. \left\{ \begin{aligned} α_i\geqslant0; \\ y_i f(x_i)-1\geqslant0;\\ α_i(y_i f(x_i)-1)=0. \\ \end{aligned} \right. ⎩⎪⎨⎪⎧​αi​⩾0;yi​f(xi​)−1⩾0;αi​(yi​f(xi​)−1)=0.​
求解对偶问题即是求解上述KKT条件。求α的思路可以采用二次规划算法或者SMO算法等，求解b的思路就是使用所有支持向量求解的平均值。

2.3. 核方法

在 SVM 中引入核方法便可使得 SVM 变为非线性分类器。核方法可以将低维问题映射到高维，将低维非线性问题转换为高维线性问题。

核函数定义：设 χ 为输入空间，ω 为特征空间，如果存在一个 χ 到 ω 的映射 ϕ(x):χ→ω ，对所有的 x,z∈χ，函数 K(x,z) 满足 K(x,z)=ϕ(x)⋅ϕ(z) ,则称 ϕ(x) 为输入空间到特征空间的映射函数，K(x,z) 为核函数。

2.4. 线性SVM

import numpy as np
import matplotlib.pyplot as plt
from sklearn import svm

data = np.array([
    [0.1, 0.7],
    [0.3, 0.6],
    [0.4, 0.1],
    [0.5, 0.4],
    [0.8, 0.04],
    [0.42, 0.6],
    [0.9, 0.4],
    [0.6, 0.5],
    [0.7, 0.2],
    [0.7, 0.67],
    [0.27, 0.8],
    [0.5, 0.72]
])
label = [1] * 6 + [0] * 6
x_min, x_max = data[:, 0].min() - 0.2, data[:, 0].max() + 0.2
y_min, y_max = data[:, 1].min() - 0.2, data[:, 1].max() + 0.2
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.002),
                     np.arange(y_min, y_max, 0.002)) # meshgrid如何生成网格
model_linear = svm.SVC(kernel='linear', C = 0.001)
model_linear.fit(data, label) # 训练
Z = model_linear.predict(np.c_[xx.ravel(), yy.ravel()]) # 预测
Z = Z.reshape(xx.shape)
plt.contourf(xx, yy, Z, cmap = plt.cm.ocean, alpha=0.6)
plt.scatter(data[:6, 0], data[:6, 1], marker='o', color='r', s=100, lw=3) 
plt.scatter(data[6:, 0], data[6:, 1], marker='x', color='k', s=100, lw=3)
plt.title('Linear SVM')
plt.show()

2.5. 高斯核SVM

'''对比不同gamma下的分类情况'''
plt.figure(figsize=(16, 15))
 
for i, gamma in enumerate([1, 5, 15, 35, 45, 55]):
    # C: 惩罚系数，gamma: 高斯核的系数
    model_rbf = svm.SVC(kernel='rbf', gamma=gamma, C= 0.0001).fit(data, label)
 
    Z = model_rbf.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)

    plt.subplot(3, 2, i + 1)
    plt.subplots_adjust(wspace=0.4, hspace=0.4)
    plt.contourf(xx, yy, Z, cmap=plt.cm.ocean, alpha=0.6)
 
    plt.scatter(data[:6, 0], data[:6, 1], marker='o', color='r', s=100, lw=3)
    plt.scatter(data[6:, 0], data[6:, 1], marker='x', color='k', s=100, lw=3)
    plt.title('RBF SVM with $\gamma=$' + str(gamma))
plt.show()

2.6. 参数说明

sklearn中支持向量分类主要有三种方法：SVC、NuSVC、LinearSVC，扩展为三个支持向量回归方法：SVR、NuSVR、LinearSVR。SVC和NuSVC方法基本一致，唯一区别就是损失函数的度量方式不同（NuSVC中的nu参数和SVC中的C参数）；LinearSVC是实现线性核函数的支持向量分类，没有kernel参数，也缺少一些方法的属性，如support_等。以下重点介绍SVC，其余可见sklearn官网。

class sklearn.svm.SVC(C=1.0, kernel='rbf', degree=3, gamma='auto', coef0=0.0, shrinking=True, probability=False, tol=0.001, cache_size=200, class_weight=None, verbose=False, max_iter=-1, decision_function_shape='ovr', random_state=None)　

C: 惩罚系数，用来控制损失函数的惩罚系数，类似于LR中的正则化系数。C越大，训练集测试时准确率很高，但泛化能力弱，容易导致过拟合。 C越小，容错能力增强，泛化能力较强，但也可能欠拟合。
kernel: 采用的核函数类型。参数选择有RBF, Linear, Poly, Sigmoid，precomputed或者自定义一个核函数, 默认的是"RBF"，即径向基核，也就是高斯核函数。
degree: 当指定kernel为’poly’时，表示选择的多项式的最高次数，默认为三次多项式。
gamma: 核函数系数，该参数是rbf，poly和sigmoid的内核系数；默认是’auto’。gamma越大，σ越小，使得高斯分布又高又瘦，造成模型只能作用于支持向量附近，可能导致过拟合；反之，gamma越小，σ越大，高斯分布会过于平滑，在训练集上分类效果不佳，可能导致欠拟合。
coef0: 核函数常数值(y=kx+b中的b值)，只有‘poly’和‘sigmoid’核函数有，默认值是0。
shrinking : 是否进行启发式。如果能预知哪些变量对应着支持向量，则只要在这些样本上训练就够了，其他样本可不予考虑，这不影响训练结果，但降低了问题的规模并有助于迅速求解。进一步，如果能预知哪些变量在边界上(即a=C)，则这些变量可保持不动，只对其他变量进行优化，从而使问题的规模更小，训练时间大大降低。这就是Shrinking技术。 Shrinking技术基于这样一个事实：支持向量只占训练样本的少部分，并且大多数支持向量的拉格朗日乘子等于C。
probability: 是否使用概率估计，默认是False。
tol: 残差收敛条件，默认是0.0001，即容忍1000分类里出现一个错误，与LR中的一致；误差项达到指定值时则停止训练。
cache_size: 缓冲大小，用来限制计算量大小，默认是200M。
class_weight: 字典类型或者balance字符串。权重设置，正类和反类的样本数量是不一样的，这里就会出现类别不平衡问题，该参数就是指每个类所占据的权重，默认为1，即默认正类样本数量和反类一样多。
verbose: 是否启用详细输出。在训练数据完成之后，会把训练的详细信息全部输出打印出来，可以看到训练了多少步，训练的目标值是多少；但是在多线程环境下，由于多个线程会导致线程变量通信有困难，因此verbose选项的值就是出错，所以多线程下不要使用该参数。
max_iter: 最大迭代次数，默认是-1，即没有限制。
decision_function_shape ： 原始的SVM只适用于二分类问题，如果要将其扩展到多类分类，就要采取一定的融合策略。
random_state: 在使用SVM训练数据时，要先将训练数据打乱顺序，用来提高分类精度，这里就用到了伪随机序列。如果该参数给定的是一个整数，则该整数就是伪随机序列的种子值；如果给定的就是一个随机实例，则采用给定的随机实例来进行打乱处理；如果啥都没给，则采用默认的 np.random实例来处理。