3.4 支持向量机

支持向量机（Support Vector Machines，SVM）是一种二分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器，可将问题化为一个求解凸二次规划的问题。

具体来说就是在线性可分时，在原空间寻找两类样本的最优分类超平面。在线性不可分时，加入松弛变量并通过使用非线性映射将低维输入空间的样本映射到高维空间使其变为线性可分，这样就可以在该特征空间中寻找最优分类超平面。

3.4.1 试介绍SVM算法中的线性可分问题，最大间隔法

下面只考虑将数据分为两类的问题，假设有n个训练点xⁱ，每个训练点有一个指标yⁱ。训练集即为：T={(x¹,y¹),(x²,y²),…,(xⁿ,yⁿ)}其中xⁱ∈R^N为输入向量，其分量称为特征或者属性。yⁱ∈Y={1,-1}是输出指标。问题是给定新的输入x，如何推断它的输出y是1还是-1。

处理方法是找到一个函数g:R^N→R，然后定义下面的决策函数实现输出

f(x)=sgn(g(x))

其中sgn(z)是符号函数，也就是当z≥0时取值+1，否则取值-1。确定g的算法称为分类机。如果g(x)=w^Tx+b，则确定w和b的算法称为线性分类机。

1.线性可分问题

考虑训练集T，若存在w∈Rⁿ，b∈R和ε＞0使得：

对所有yⁱ=1的指标i，有w^Txⁱ+b≥ε；而对所有yⁱ=-1的指标j，有w^Tx^j+b≤ε则称训练集T线性可分。相应的分类问题也称为线性可分。

2.最大间隔法

假设两类数据可以被H={x:w^Tx+b=0}分离，垂直于法向量w，移动H直到碰到某个训练点，可以得到两个超平面H₁和H₂，两个平面称为支撑超平面，它们分别支撑两类数据。而位于H₁和H₂正中间的超平面是分离这两类数据最好的选择。

法向量w有很多种选择，超平面H₁和H₂之间的距离称为间隔，这个间隔是w的函数，目的就是寻找这样的w使得间隔达到最大。直接计算可知，两个支撑超平面之间的距离为。

最大化间隔即为一个凸二次规划问题：

则线性可分问题的最大间隔问题可总结为求解上面的凸二次规划得解w^*,b^*。令g(x)=(w^*)^Txⁱ+b^*则决策函数为f(x)=sgn(g(x))。

3.求解过程

利用Lagrange优化方法可以把上述最大间隔问题转化为较简单的对偶问题，首先定义凸二次规划的拉格朗日函数：

其中α∈R^q为拉格朗日乘子。分别对w,b,α_i求偏微分并令其为0。得：

则凸二次规划的对偶问题为：

这是一个不等式约束下的二次函数极值问题，存在唯一解。根据KKT条件，解中将只有一部分（通常是很少一部分）不为零，这些不为0的解所对应的样本就是支持向量。

假设α^*是上面凸二次规划问题的最优解，则α^*≠0。假设指标j满足＞0，按下面方式计算出的解为原问题的唯一最优解：

需要注意的是对于一个一般的带等式和不等式约束的优化问题，KKT条件是取得极值的必要条件而不是充分条件，而对于凸优化问题，KKT条件则是充分条件，SVM是凸优化问题。

4.SVM的代码实现

Python中的SVM算法是基于sklearn中的SVC函数实现的，重要的参数设置如下。

（1）错误项惩罚系数C

该系数默认值为1.0，惩罚系数越大，则对分错样本的惩罚程度越大，这样会在训练数据集中准确率高，但是测试集中准确率低。同样地，如果C比较小，泛化能力会强一点，但也不能太小。

（2）核函数kernel

默认为rbf，即高斯核函数，除此之外还可选择linear：线性核函数，poly：多项式核函数，sigmod：sigmod核函数，precomputed：核矩阵。

（3）核函数阶数degree

默认为3，这个参数只针对多项式核函数，是指多项式核函数的阶数n。

（4）核函数系数gamma

默认为auto，这个参数只针对rbf，poly，sigmod三种核函数，默认值是指值为样本特征数的倒数，即1/n_features。

（5）核函数系数coef0

默认为0.0，这个参数只针对poly和sigmod核函数有用，是指其中的参数C。

（6）启发式收缩方式shrinking

（7）类别权重class_weight

默认值是所有类别相同，该参数目的是给每个类别分别设置不同的惩罚参数C。如果选择balance，则是指利用y的值自动调整与输入数据中的类频率成反比的权重。

除以上参数外，还有其他参数，暂不赘述，需要根据项目的具体要求选择恰当的参数。

3.4.2 线性不可分问题

线性不可分即指部分训练样本不能满足yⁱ(w^Txⁱ+b)≥1的条件。由于原本的优化问题的表达式要考虑所有的样本点，在此基础上寻找正负类之间的最大几何间隔，而几何间隔本身代表的是距离，是非负的，像这种有噪声的情况会使得整个问题无解。

解决方法比较简单，即利用松弛变量允许一些点到分类平面的距离不满足原先的要求。具体约束条件中增加一个松弛项参数ε_i≥0，变成：

yⁱ(w^Txⁱ+b)≥1-ε_ii=1,…,n

显然当ε_i足够大时，训练点就可以满足以上条件。虽然得到的分类间隔越大，好处就越多。但需要避免ε_i取太大的值。所以在目标函数中加入惩罚项，得到下面的优化问题：

其中ε∈Rⁿ，C是一个惩罚参数。目标函数意味着既要最小化（即最大化间隔），又要最小化（即约束条件yⁱ(w^Txⁱ+b)≥1的破坏程度），参数C体现了两者总体的一个权衡。

求解这一优化问题的方法与求解线性问题最优分类面时所用的方法几乎相同，都是转化为一个二次函数极值问题，只是在凸二次规划问题中条件变为：0≤α_i≤C，i=1,…,n。具体推导如下：

定义拉格朗日函数：

则凸二次规划的对偶问题为：

利用等式约束C-α_i-β_i=0，i=1,…,n可以简化该对偶问题消去β，变成只有变量α的等价问题：

假设α^*是上面凸二次规划问题的最优解，则α^*≠0。假设指标j满足，按下面方式计算出的解为原问题的最优解：

3.4.3 SVM的非线性映射问题

上面讨论的情形中，寻优目标函数和分类函数都只会涉及训练样本之间的内积运算，但这样难以处理好非线性问题。所以非线性问题需要通过非线性交换转化为某个高维空间中的线性问题，在新的高维空间求最优分类超平面。而非线性变换的方式就是利用核函数。

根据泛函分析中的相关理论，当核函数K(xⁱ·x^j)满足Mercer条件，它就对应某一变换空间中的内积。因此，在最优超平面中采用适当的内积函数K(xⁱ·x^j)就可以实现线性分类。此时目标函数变为：

而相应的分类函数也变为：

目前研究最多的核函数主要有以下3类。

（1）多项式核函数

K(x,x_i)=[(x·x_i)+1]^q

其中q是多项式的阶次，所得到的是q阶多项式分类器。

（2）高斯核函数（RBF）

（3）S形核函数

K(x,x_i)=tanh[v(x·x_i)+c]

在上述几种常用的核函数中，最为常用的是多项式核函数和径向基核函数。除了上面提到的3种核函数外，还有指数径向基核函数、小波核函数等其他一些核函数，应用相对较少。

3.4.4 SVM的优点和缺点

（1）优势

支持向量机算法可以解决小样本情况下的机器学习问题，简化了通常的分类和回归等问题。

由于采用核函数方法克服了维数灾难和非线性可分的问题，所以向高维空间映射时没有增加计算的复杂性。换句话说，由于支持向量机算法的最终决策函数只由少数的支持向量所确定，所以计算的复杂性取决于支持向量的数目，而不是样本空间的维数。

支持向量机算法利用松弛变量可以允许一些点到分类平面的距离不满足原先的要求，从而避免这些点对模型学习的影响。

（2）劣势

支持向量机算法对大规模训练样本难以实施。这是因为支持向量机算法借助二次规划求解支持向量，这其中会涉及m阶矩阵的计算，所以矩阵阶数很大时将耗费大量的机器内存和运算时间。

经典的支持向量机算法只给出了二类分类的算法，而在数据挖掘的实际应用中，一般要解决多类的分类问题，但支持向量机算法对于多分类问题解决效果并不理想。

SVM算法效果性与核函数的选择关系很大，往往要尝试多种核函数，即使选择了效果比较好的高斯核函数，也要调参选择恰当的γ参数。另一方面就是现在常用的SVM理论都是使用固定惩罚系数C，但是正负样本的两种错误造成的损失是不一样的。