支持向量机（2）

2019-02-09 本文已影响7人魏允臣

简单的说，支持向量机就是通过寻求结构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较少的情况下，亦能获得良好统计规律的目的。通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，即支持向量机的学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。（引自刘知行）

支持向量机分类特点

假设给定一个训练数据集 $T=\lbrace(x_1,y_1),(x_2,y_2),\cdots ,(x_n,y_n)\rbrace$ 。同时，假定已经找到样本空间中的分割平面，其划分公式可以通过以下线性方程来描述： $wx+b=0\tag{1}$ 使用一条直线对线性可分数据集进行分类的过程中，我们已经知道这样的直线可能有很多条：

如何确定最优的分类方法？支持向量机给出了一种直观的方法：

图中

当出现上图所示的样本点不是严格线性可分的情况时，某些样本点 $(x_i,y_i)$ 就不能满足函数间隔 $\geqslant 1$ 的约束条件，即公式（3b）中的约束条件。为了解决这个问题，可以对每个样本点 $(x_i,y_i)$ 引入一个松弛变量 $\xi_i \geq 0$ ，使得函数间隔加上松弛变量 $\geqslant 1$ ，即约束条件转化为：
$y_i(wx_i+b) \geq 1-\xi_i$ 同时，对每个松弛变量 $\xi_i$ 支付一个代价 $\xi_i$ ，目标函数由原来的 $\frac{1}{2}||w||^2$ 变成：
$\frac{1}{2}\left \| w \right \|^2+C\sum\limits_{j=1}^{N}\xi_i$ 这里， $C>0$ 称为惩罚参数，一般根据实际情况确定。 $C$ 值越大对误分类的惩罚增大，最优化问题即为：
$\min\limits_{w,b,\xi} \frac{1}{2}\left \| w \right \|^2+C\sum\limits_{i=1}^{N}\xi_i$ $s.t. y_i(wx_i+b) \geq 1-\xi_i,i=1,2,...,N$ $\xi_i\geq 0,i=1,2,...,N$ 这就是软间隔支持向量机的表示过程。同理，我们可以使用拉格朗日乘子法将其转换为对偶问题求解：
$\max\limits_{\alpha} \frac{1}{2}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i*x_j)-\sum\limits_{i=1}^{N}\alpha_i$ $s.t. \sum\limits_{i=1}^{N}\alpha_iy_i=0$ $0 \leq \alpha_i \leq C ,i=1,2,...,N$ 解出最优解 $\alpha^*=(\alpha_1^*,\alpha_2^*,...,\alpha_N^*)$ 后，基于此我们可以求得最优解 $w^*$ , $b^*$ ，由此得到分离超平面：
$w^*x+b^*=0$ 使用符号函数求得正负类之间的分类决策函数为：
$f(x)=sign(w^*x+b^*)$

非线性分类支持向量机

对于线性不可分的数据集，我们也可以通过支持向量机去完成分类。但是需要通过一些方法把线性不可分数据转换为线性可分数据之后，再完成分类。

我们把这种数据转换的方法称作「核技巧」，实现数据转换的函数称之为「核函数」。

核技巧与核函数

核技巧的关键在于空间映射，即将低维数据映射到高维空间中，使得数据集在高维空间能被线性可分。
如上图所示，假设我们在二维空间中有蓝色和红色代表的两类数据点，很明显无法使用一条直线把这两类数据分开。此时，如果我们使用核技巧将其映射到三维空间中，就变成了可以被平面线性可分的状态。

对于「映射」过程，我们还可以这样理解：分布在二维桌面上的红蓝小球无法被线性分开，此时将手掌拍向桌面（好疼），小球在力的作用下跳跃到三维空间中，这也就是一个直观的映射过程。
同时，「映射」的过程也就是通过核函数转换的过程。这里需要补充说明一点，那就是将数据点从低维度空间转换到高维度空间的方法有很多，但往往涉及到庞大的计算量，而数学家们从中发现了几种特殊的函数，这类函数能大大降低计算的复杂度，于是被命名为「核函数」。也就是说，核技巧是一种特殊的「映射」技巧，而核函数是核技巧的实现方法。

几种常见的核函数：

线性核函数(linear)
$k\left ( x_i, x_j \right )=x_i*x_j$
多项式核函数(poly)
$k\left ( x_i, x_j \right )=\left ( x_i*x_j \right )^d, d \geq 1$
高斯径向基核函数(rbf)
$k\left ( x_i, x_j \right ) = \exp \left(-{\frac {\left \|{\mathbf {x_i}}-{\mathbf {x_j}}\right \|_{2}^{2}}{2\sigma ^{2}}}\right)=exp\left ( -\gamma * \left \| x_i-x_j \right \|_{2} ^2 \right ), \gamma>0$
Sigmoid 核函数
$k\left ( x_i, x_j \right )=tanh\left ( \beta * x_ix_j+\theta \right ), \beta > 0 , \theta < 0$

此外，核函数还可以通过函数组合得到，例如：
若 $k_1$ 和 $k_2$ 是核函数，那么对于任意正数 $\lambda_1,\lambda_2$ ，其线性组合：
$\lambda_1 k_1+\lambda_2 k_2$

引入核函数的间隔表示及求解

我们通过直接引入核函数 $k(x_i,x_j)$ ，而不需要显式的定义高维特征空间和映射函数，就可以利用解线性分类问题的方法来求解非线性分类问题的支持向量机。引入核函数以后，对偶问题就变为：
$\max\limits_{\alpha} \frac{1}{2}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\alpha_i\alpha_jy_iy_jk(x_i*x_j)-\sum\limits_{i=1}^{N}\alpha_i$ $s.t. \sum\limits_{i=1}^{N}\alpha_iy_i=0$ $0 \leq \alpha_i \leq C ,i=1,2,...,N$ 同样，解出最优解 $\alpha^*=(\alpha_1^*,\alpha_2^*,...,\alpha_N^*)$ 后，基于此我们可以求得最优解 $w^*$ , $b^*$ ，由此得到分离超平面：
$w^*x+b^*=0$ 使用符号函数求得正负类之间的分类决策函数为：
$f(x)=sign(w^*x+b^*)$

scikit-learn SVC分类器

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: 软间隔支持向量机对应的惩罚参数，C越大，相当于惩罚松弛变量，希望松弛变量接近0，即对误分类的惩罚增大，趋向于对训练集全分对的情况，这样对训练集测试时准确率很高，但泛化能力弱。C值小，对误分类的惩罚减小，允许容错，将他们当成噪声点，泛化能力较强。
kernel: linear, poly, rbf, sigmoid等核函数，默认为rbf
degree: poly 多项式核函数的指数（维度），默认是3，选择其他核函数时会被忽略
gamma: ‘rbf’,‘poly’ 和‘sigmoid’的核函数参数。默认是’auto’，则会选择1/n_features
coef0: 核函数的常数项。对于‘poly’和 ‘sigmoid’有用。
probability: 是否采用概率估计？.默认为False
shrinking: 是否采用shrinking heuristic方法，默认为true
tol: 收敛停止的容许误差值大小，默认为1e-3
cache_size: 核函数cache缓存大小，默认为200
class_weight: 类别的权重，字典形式传递。设置第几类的参数C为weight * C(C-SVC中的C)
verbose: 允许冗余输出
max_iter: 最大迭代次数。-1为无限制。
decision_function_shape: ‘ovo’, ‘ovr’ or None, default=None3
random_state: 数据洗牌时的种子值，int值