机器学习算法之–支持向量机总结
一、支持向量机（SVM）简介
支持向量机（Support Vector Machines）是一种二分类模型，基本思想是在特征空间上寻找可以正确的划分训练数据集且几何间隔最大的分离超平面。几何间隔最大有利于区别于感知机。这时候分离超平面是唯一的
划分的原则是几何间隔最大化，最终转化为一个凸二次规划问题来求解，等价于正则化的合页损失函数最小化问题。包括以下三个模型：
- 当训练样本线性可分时，通过硬间隔最大化，学习一个线性可分支持向量机；
- 当训练样本近似线性可分时，通过软间隔最大化，学习一个线性支持向量机；
- 当训练样本线性不可分时，通过核技巧和软间隔最大化，学习一个非线性支持向量机；
支持向量机优点
- 泛化错误率低，计算开销不大，结果易解释
- SVM直接用特征空间的内积函数(既是核函数)，再利用在线性可分的情况下的求解方法直接求解对应的高维空间的决策问题，不显式定义映射函数。
- SVM 的最终决策函数只由少数的支持向量所确定，计算的复杂性取决于支持向量的数目，而不是样本空间的维数，这在某种意义上避免了“维数灾难”。
- 少数支持向量决定了最终结果，这不但可以帮助我们抓住关键样本，“剔除”大量冗余样本，而且注定了该方法不但算法简单，而且具有较好的“鲁棒”性。（增、删非支持向量样本对模型没有影响）
支持向量机缺点
- 对参数选择和核函数选择敏感，原始分类器不加修改仅适用于处理二分类问题。
- SVM算法对大规模训练样本难以实施，由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间（使用SMO 算法）。
二、线性可分支持向量机
输入空间是欧式空间或离散集合，特征空间为欧式空间或希尔伯特空间，线性可分支持向量机将输入空间映射为特征空间中的特征向量，支持向量机的学习是在特征空间进行的。
给定特征空间上的训练样本集D=
(
x
1
,
y
1
)
，
(
x
2
,
y
2
)
，
⋯
,
(
x
m
,
y
m
)
(x_1,y_1)，(x_2,y_2)，⋯,(x_m,y_m)
(x1,y1)，(x2,y2)，⋯,(xm,ym),其中
y
i
y_i
yi∈{−1,+1}，线性可分支持向量机的目的就是基于训练集D在样本空间中找到一个划分超平面w*x+b=0，它由法向量和截距表示，将样本分成正负两类，其中法向量指向的一侧为正类，其中假设数据是线性可分的。
学习策略（与感知机的不同）：
- 感知机利用误分类最小策略，求得分离超平面，这时解有无穷多个。
- 线性可分支持向量机利用间隔最大化求得最优分离超平面，这是解是唯一的。
下面给出线性可分支持向量机的定义，它对应着能将两类数据正确划分并且间隔最大的直线。
（1）函数间隔和几何间隔
我们说线性可分支持向量机可以利用间隔最大化求得最优分离超平面，那么间隔在这里有两种，函数间隔和几何间隔，一个点的函数间隔可以表示分类的正确性和确信度，函数间隔定义如下
函数间隔有个缺点，如果w和b成比例扩大一倍，则超平面没变，而函数间隔却增加一倍，所以我们需要对w进行约束，使||w||=1，使得间隔是确定的，这样函数间隔就变成了几何间隔。
所以超平面关于样本点的几何间隔为实例点到超平面的带符号的距离（当样本点被超平面正确分类时就是实例点到超平面的距离），所以函数间隔和几何间隔就差个||w||，如果||w||=1，几何间隔和函数间隔相同。
（2）间隔最大化
间隔最大化的直观解释：对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。也就是说，不仅将正负实例点分开，而且对最难分的实例点（离超平面最近的点）也有足够大的确信度将他们分开。这样的超平面应该对未知的新实例有很好的分类预测能力。
（3）线性可分支持向量机学习算法（最大间隔法）
需要手写推导。
（4）支持向量和间隔边界
在线性可分情况下，离超平面最近的实例点称为支持向量，支持向量在分离超平面的时候起作用，其他点不起作用，故满足约束条件
y
i
(
w
∗
x
+
b
)
−
1
=
0
y_i(w*x+b)-1=0
yi(w∗x+b)−1=0
- 对于
y
i
=
+
1
y_i= +1
yi=+1的实例点，支持向量在超平面H1上w
∗
x
+
b
=
1
w*x+b= 1
w∗x+b=1 - 对于
y
i
=
−
1
y_i= -1
yi=−1的实例点，支持向量在超平面H2上w
∗
x
+
b
=
−
1
w*x+b= -1
w∗x+b=−1
H1与H2的距离称为间隔，依赖于法向量，等于
∣
∣
w
∣
∣
2
\frac{||w||}{2}
2∣∣w∣∣，H1，H2，称为间隔边界。
（5）线性可分支持向量机对偶算法（需要手推）
**对偶算法定义：**为了求解线性可分支持向量机，将其作为原始的最优化问题，应用拉格朗日对偶性，通过求解对偶问题得到原始问题的最优解。
为什么用对偶算法求解？
- 不等式的约束一直是优化里的难题，求解对偶问题可以将原来的不等式约束问题变成等式约束，然后易于求解。
- 支持向量机用到了高维映射，但是映射函数的具体形式几乎完全不确定，而求解对偶问题之后，可以用核函数来处理这个问题，引入核函数，进而推广到非线性分类问题。
经过对偶形式后，线性可分支持向量机学习算法为（分三步）
三、线性支持向量机
（1）线性支持向量机（软间隔最大化）
有时候本来数据的确是线性可分的，也就是说可以用线性可分支持SVM的学习方法来求解，但是却因为混入了异常点（不能满足函数间隔大于等于1），导致不能线性可分，那么我们需要修改硬间隔最大化，改成软间隔最大化，引入松弛变量，并为每一个松弛变量，付出一个代价。
线性支持向量机定义：
C为惩罚系数，C值小时对误分类惩罚小，C值大时对误分类惩罚大，最小化7.32有两个含义，使
∣
∣
w
∣
∣
2
\frac{||w||}{2}
2∣∣w∣∣尽量小即间隔（
1
∣
∣
w
∣
∣
\frac{1}{||w||}
∣∣w∣∣1）最大，同时使误分类点尽可能少。
（2）线性支持向量机对偶算法（需要手推）
（3）支持向量
将对偶问题的解
α
∗
>
0
\alpha^*>0
α∗>0的样本点
x
i
，
y
i
x_i，y_i
xi，yi的实例
x
i
x_i
xi称为支持向量。
（4）合页损失函数
线性支持向量机学习策略为软间隔最大化，学习算法为凸二次规划，等价于是最小化二阶范数正则化的合页损失函数(7.63)。7.63第二项为正则项。
四、非线性支持向量机
（1）非线性支持向量机思路
如果能用一个超曲面将正负实例分开，则这个问题称为非线性可分问题。
非线性可分问题用非线性支持向量机来解决，非线性支持向量机主要利用核技巧。
非线性问题求解思路：
（1）用线性方法来求，第一步使用一个非线性变换将原空间的数据映射到新特征空间，第二步在新的特征空间里使用线性分类方法来学习分类模型，核技巧就是这种方法。
（2）核技巧，其基本思想就是通过非线性变换将输入空间对应到一个特征空间上，使得输入空间中的超曲面模型对应于特征空间上的一个超平面模型也就是支持向量机，问题转化为在特征空间中求解支持向量机，分类学习的任务通过在特征空间中求解线性支持向量机就可以完成。
（2）核函数
在学习和预测中只定义核函数K（x，z），而不显式定义映射函数，本质就是将输入空间中的内积 xi⋅xj 变化为特征空间中的内积 ϕ(x)⋅ϕ(z)即核函数来代替, 在特征空间中学习线性支持向量机。
实际应用中，往往依赖领域知识直接选择核函数，核函数选择的有效性需要通过实验验证。
（2）正定核函数
需要手写
（3）常用核函数
- 多项式核函数
- 高斯核函数
- 字符串核函数
（4）非线性支持向量机学习算法
五、序列最小最优化算法（SMO算法）
SMO算法是一种启发式算法，基本思路是：如果所有边的解都满足此优化问题的KKT条件，那么这个最优化问题的解就得到了，因为KKT条件就是该最优化问题的充分必要条件。否则，选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题。这个二次规划问题关于这两个变量的解应该更接近原始二次规划问题的解，因此这会使得原始二次规划问题的目标函数值变得更小。重要的是，这时子问题可以通过解析方法求解，这样可以大大提高整个算法的计算速度。子问题有两个变量，一个是违反KKT条件最严重的那个，另一个由约束条件自动确定。如此，SMO算法将原问题不断分解为子问题并对子问题求解，进而达到求解原问题的目的。
SMO算法分为两部分：
- 求解两个变量二次规划的解析方法
- 选择变量的启发式方法
SMO算法特点：
不断将原二次规划问题分解为只有两个变量的二次规划子问题，并对子问题进行拆分求解，直到所有变量满足KKT条件为止。
六、SVM代码实战
Sklearn中SVM，SVM主要有LinearSVC、NuSVC和SVC三种方法
github代码
(1) sklearn.LinearSVC
sklearn.svm.LinearSVC(penalty='l2', loss='squared_hinge', dual=True, tol=0.0001, C=1.0, multi_class='ovr', fit_intercept=True, intercept_scaling=1, class_weight=None, verbose=0, random_state=None, max_iter=1000)
参数说明：
- penalty:正则化参数，L1和L2两种参数可选，仅LinearSVC有。
- loss:损失函数，有‘hinge’和‘squared_hinge’两种可选，前者又称L1损失，后者称为L2损失，默认是是’squared_hinge’，其中hinge是SVM的标准损失，squared_hinge是hinge的平方。
- dual:是否转化为对偶问题求解，默认是True。
- tol:残差收敛条件，默认是0.0001，与LR中的一致。
- C:惩罚系数，用来控制损失函数的惩罚系数，类似于LR中的正则化系数。
- multi_class:负责多分类问题中分类策略制定，有‘ovr’和‘crammer_singer’ 两种参数值可选，默认值是’ovr’，'ovr’的分类原则是将待分类中的某一类当作正类，其他全部归为负类，通过这样求取得到每个类别作为正类时的正确率，取正确率最高的那个类别为正类；‘crammer_singer’ 是直接针对目标函数设置多个参数值，最后进行优化，得到不同类别的参数值大小。
- fit_intercept:是否计算截距，与LR模型中的意思一致。
- class_weight:与其他模型中参数含义一样，也是用来处理不平衡样本数据的，可以直接以字典的形式指定不同类别的权重，也可以使用balanced参数值。
- verbose:是否冗余，默认是False.
- random_state:随机种子的大小
- max_iter:最大迭代次数，默认是1000。
返回对象：
- coef_:各特征的系数（重要性）。
- intercept_:截距的大小（常数值）。
(2) sklearn.NuSVC
sklearn.svm.NuSVC(nu=0.5, 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))
参数说明：
- nu:训练误差部分的上限和支持向量部分的下限，取值在（0，1）之间，默认是0.5
- kernel:核函数，核函数是用来将非线性问题转化为线性问题的一种方法，默认是“rbf”核函数，常用的核函数有以下几种：
- degree:当核函数是多项式核函数的时候，用来控制函数的最高次数。（多项式核函数是将低维的输入空间映射到高维的特征空间）
- gamma:核函数系数，默认是“auto”，即特征维度的倒数。
- coef0:核函数常数值(y=kx+b中的b值)，只有‘poly’和‘sigmoid’核函数有，默认值是0。
- max_iter:最大迭代次数，默认值是-1，即没有限制。
- probability:是否使用概率估计，默认是False。
- decision_function_shape:与’multi_class’参数含义类似。
- cache_size:缓冲大小，用来限制计算量大小，默认是200M。
返回对象：
- support_:以数组的形式返回支持向量的索引。
- support_vectors_:返回支持向量。
- n_support_:每个类别支持向量的个数。
- dual_coef_:支持向量系数。
- intercept_:截距值（常数值）。
(3) sklearn.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:惩罚系数。 SVC和NuSVC方法基本一致，唯一区别就是损失函数的度量方式不同（NuSVC中的nu参数和SVC中的C参数）。
- kernel:核函数，核函数是用来将非线性问题转化为线性问题的一种方法，默认是“rbf”核函数，常用的核函数有以下几种：
- degree:当核函数是多项式核函数的时候，用来控制函数的最高次数。（多项式核函数是将低维的输入空间映射到高维的特征空间）
- gamma:核函数系数，默认是“auto”，即特征维度的倒数。
- coef0:核函数常数值(y=kx+b中的b值)，只有‘poly’和‘sigmoid’核函数有，默认值是0。
- max_iter:最大迭代次数，默认值是-1，即没有限制。
- probability:是否使用概率估计，默认是False。
- decision_function_shape:与’multi_class’参数含义类似。
- cache_size:缓冲大小，用来限制计算量大小，默认是200M。
返回对象：
- support_:以数组的形式返回支持向量的索引。
- support_vectors_:返回支持向量。
- n_support_:每个类别支持向量的个数。
- dual_coef_:支持向量系数。
- intercept_:截距值（常数值）。
(4) sklearn SVM的RBF高斯核函数调参
- 对于sklearn.SVC，其中比较重要的参数有C惩罚系数，gamma。
- 对于sklearn.nu-SVC，其中比较重要的参数有分类错误率上限nu，gamma。
惩罚系数和分类错误率上限nu起的作用等价
其中c表示对误差的惩罚程度，c越大，表示对误差的惩罚程度越大，模型对样本数据的学习更精确，也因此容易过拟合；反之，c越小，对误差的惩罚程度越小，可能欠拟合。g对应RBF核中的gamma值，gamma越大，σ越小，使得高斯分布又高又瘦，造成模型只能作用于支持向量附近，也就是过拟合；反之，gamma越小，σ越大，高斯分布会过于平滑，在训练集上分类效果不佳，也就是欠拟合。
两者最佳组合的确定可以采用最简单的网格搜索方法，sklearn中提供了相应的方法GridSearchCV。
七、SVM回归
- SVM还支持线性和非线性回归。SVM回归要做的是让尽可能多的实例位于分离平面上，同时限制最大间隔。使用Scikit-Learn的LinearSVR类来执行线性SVM回归
- ε表示间隔大小，在最大间隔内添加更多的实例不会影响模型的预测，所以这个模型被称为ε不敏感
- SVR类是SVC类的回归等价物， LinearSVR类也是LinearSVC类的回归等价物。 LinearSVR与训练集的大小线性相关（跟LinearSVC一样） ， 而SVR则在训练集变大时， 变得很慢（SVC也是一样）
from sklearn.svm import LinearSVR
svm_reg = LinearSVR(epsilon=1.5)
svm_reg.fit(X, y)
八、总结
- LinearSVC类会对偏置项进行正则化，所以你需要先减去平均值，使训练集集中。如果使用StandardScaler会自动进行这一步。此外，请确保超参数loss设置为"hinge"，因为它不是默认值。最后，为了获得更好的性能，还应该将超参数dual设置为False，除非特征数量比训练实例还多
- 添加多项式特征方法可以使得样本分离，也可以使用**核技巧（ploy多项式核函数）**来做（实际没有添加任何特征）
- 添加相似特征方法可以使得样本分离，也可以使用**核技巧（BRF高斯径向基函数作为相似函数）**来做（实际没有添加任何特征）
- 寻找正确的超参数值的常用方法是网格搜索
- 搜索核函数的经验法则是，永远先从线性核函数开始尝试（LinearSVC比SVC（kernel=“linear”）快得多），特别是训练集非常大或特征非常多的时候。如果训练集不太大，你可以试试高斯RBF核
- 想要非常高的精度， 算法需要的时间更长。 它由容差超参数（在Scikit-Learn中为tol） 来控制。 大多数分类任务中， 默认的容差就够了
- SVM要特征缩放的原因，支持向量机拟合类别之间可能的、 最宽的“街道” ， 所以如果训练集不经过缩放， SVM将趋于忽略值较小的特征
- 核SVM只能使用对偶问题，而线性SVM可以考虑使用对偶问题
- 一个使用RBF核训练的支持向量机对训练集拟合不足， 可能是由于过度正则化导致的。 您需要提升gamma或C（或同时提升二者） 来降低正则化
