机器学习之SVM

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

SVM 简单理解

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

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 算法,使用如下:

1
2
3
4
from sklearn.svm import LinearSVC

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
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" 则使用核函数:

1
2
3
4
5
6
7
8
9
10
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" 则使用高斯核函数:

1
2
3
4
5
6
7
8
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 中提供 LinearSVRSVR 进行回归问题的处理:

1
2
3
4
5
6
7
8
9
10
11
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

坚持原创技术分享,您的支持将鼓励我继续创作!