支撑向量机SVM（Suppor Vector Machine）可以解决分类问题和回归问题。

SVM 简单理解

以二分类问题为例，SVM 要找到一个决策边界，使得其离两个类别的最近样本最远，如图所示：

source: imooc.com

A 为决策边界，两个类别最近的样本离决策边界最远的时候分别位于 B、C 上，此时 B、C 上的样本的位置成为支撑向量，A、C 之间的距离和 A、B 之间的距离都为 d，B、C 之间的距离为 margin，SVM 就是要最大化 margin（或 d）。

对于线性可分使用 Hard Margin SVM算法（如上图），而对于线性不可分则使用 Soft Margin SVM算法。

SVM 的目标函数

Hard Margin SVM 目标函数

假定决策边界A（$w^Tx+b=0$）和 B（$w^Tx+b=d$）、C（$w^Tx+b=- d$），n 为空间中点到 A 的距离为：

$$\frac{|w^Tx+b|}{||w||}, 其中||w||=\sqrt{w_1^2+w_2^2+…+w_n^2}$$

假定二分类的分类为 1 和 -1，要求分类 $y^{(i)}=1$ 时 $\frac{|w^Tx^{(i)}+b|}{||w||}\geq d$，分类 $y^{(i)}=-1$ 时 $\frac{|w^Tx^{(i)}+b|}{||w||}\leq -d$。进行化简后得到分类 $y^{(i)}=1$ 时 $\frac{|w^Tx^{(i)}+b|}{||w||d}\geq 1$，分类 $y^{(i)}=-1$ 时 $\frac{|w^Tx^{(i)}+b|}{||w||d}\leq -1$；即分类 $y^{(i)}=1$ 时 $w^T_dx^{(i)}+b_d\geq 1$，分类 $y^{(i)}=-1$ 时 $w^T_dx^{(i)}+b_d\leq -1$。合并成一个式子即为 $y^{(i)}w^T_dx^{(i)}+b_d\geq 1$。

此时A、B、C得到新的表现形式：A（$w^T_dx+b_d=0$），B（$w^T_dx+b_d=1$）和 C（$w^T_dx+b_d=-1$）。

要使 d 最大，即对于支撑向量（在 B 和 C 上）而言，要得到 $max\frac{|w^T_dx+b_d|}{||w||}$，又 $|w^T_dx+b_d|=1$，进一步转换得到目标函数：$min\frac{1}{2}||w||^2，st. y^{(i)}w^T_dx^{(i)}+b_d\geq 1$（使用平方是为了方便求导之类的计算）。

Soft Margin SVM 目标函数

对于线性不可分的情况，比如上图中的 B 右边（分类1）出于出现了一个分类 -1 的样本，此时就要使用 Soft Margin SVM。

Soft Margin SVM 要求所以样本满足 $y^{(i)}w^T_dx^{(i)}+b_d\geq 1-\zeta_i,\zeta_i\geq 0$，即允许 B 和 C 向 A 靠近一些。

但为了防止 $\zeta_ i$ 过于的大，最目标函数中引入正则化：

如果使用 L1 正则，则目标函数为：$min\frac{1}{2}||w||^2+C\sum_{i=1}^m\zeta_i，st. y^{(i)}w^T_dx^{(i)}+b_d\geq 1-\zeta_i, \zeta_i\geq 0$；
如果使用 L2 正则，则目标函数为：$min\frac{1}{2}||w||^2+C\sum_{i=1}^m\zeta_i^2，st. y^{(i)}w^T_dx^{(i)}+b_d\geq 1-\zeta_i, \zeta_i\geq 0$。

在 Scikit Learn 中使用 SVM

Scikit Learn 的 svm 模块中提供了 SVM 算法，使用如下：

from sklearn.svm import LinearSVC

svc = LinearSVC(C=1e9)
svc.fit(X, y)

LinearSVC 传入的参数可以在 LinearSVC 文档中查看，比如参数 penalty 表示在正则化中使用哪种正则项（默认使用 L2 正则）。

注：使用 LinearSVC 之前要进行数据归一化处理。

对于非线性则使用多项式来处理，使用 Scikit Learn 提供的 Pipeline：

from sklearn.preprocessing import PolynomialFeatures, StandardScaler
from sklearn.pipeline import Pipeline

def PolynomialSVC(degree, C=1.0):
    return Pipeline([
        ("poly", PolynomialFeatures(degree=degree)),
        ("std_scaler", StandardScaler()),
        ("linearSVC", LinearSVC(C=C))
    ])

poly_svc = PolynomialSVC(degree=3)
poly_svc.fit(X, y)

多项式处理可以不使用 PolynomialFeatures 这种方式，而使用核函数。

核函数

以 $min\frac{1}{2}||w||^2+C\sum_{i=1}^m\zeta_i，st. y^{(i)}w^T_dx^{(i)}+b_d\geq 1-\zeta_i, \zeta_i\geq 0$ 这个最优化为例，可以将其转换为 $max\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_jx_ix_j, st. 0\leq\alpha_i\leq C,\sum_{i=1}^m\alpha_iy_i=0$，其中 $x_ix_j$ 可以使用核函数 $K(x_i, x_j)=(x_i·x_j+1)^2$ 代替。

其通用形式为：多项式核函数：$K(x, y)=(x·y+c)^d$，线性核函数：$K(x, y)=x·y$。

Scikit Learn 的 svm 模块中的 SVC 指定参数 kernel="poly" 则使用核函数：

from sklearn.svm import SVC

def PolynomialKernelSVC(degree, C=1.0):
    return Pipeline([
        ("std_scaler", StandardScaler()),
        ("kernelSVC", SVC(kernel="poly", degree=degree, C=C))
    ])

poly_kernel_svc = PolynomialKernelSVC(degree=3)
poly_kernel_svc.fit(X, y)

还有一种核函数叫做高斯核函数（又称 RBF 核，Radial Basis Function Kernel），其表示形式为：

$$K(x, y)=e^{-\gamma||x-y||^2}$$

高斯核函数将每一个样本点映射到一个无穷维的特征空间。对于二元分类，即将 x 映射到 $(e^{-\gamma||x-y_0||^2}, e^{-\gamma||x-y_1||^2})$，可以使原本线性不可分的数据变得线性可分。

Scikit Learn 的 svm 模块中的 SVC 指定参数 kernel="rbf" 则使用高斯核函数：

def RBFKernelSVC(gamma):
    return Pipeline([
        ("std_scaler", StandardScaler()),
        ("svc", SVC(kernel="rbf", gamma=gamma))
    ])

svc = RBFKernelSVC(gamma=1)
svc.fit(X, y)

SVM 处理回归问题

SVM 处理回归的问题与处理分类问题的思路相反，其要求 B、C 之间尽可能包含多的样本。

Scikit Learn 中提供 LinearSVR 和 SVR 进行回归问题的处理：

from sklearn.svm import LinearSVR
from sklearn.svm import SVR

def StandardLinearSVR(epsilon=0.1):
    return Pipeline([
        ('std_scaler', StandardScaler()),
        ('linearSVR', LinearSVR(epsilon=epsilon))
    ])

svr = StandardLinearSVR()
svr.fit(X_train, y_train)

如果要使用核函数则使用 SVR。

Github | ML-Algorithms-Action