黑马程序员技术交流社区

标题: 【上海校区】机器学习算法（5）之支持向量机的详细版 [打印本页]

---

作者: 不二晨    时间: 2018-10-19 09:57
标题: 【上海校区】机器学习算法（5）之支持向量机的详细版
一、函数间隔与几何间隔

在正式介绍SVM的模型和损失函数之前，我们还需要先了解下函数间隔和几何间隔的知识。

　　在分离超平面固定为的时候，表示点x到超平面的距离。通过观察和y是否同号，我们判断分类是否正确，这些知识在感知机模型里有。这里我们引入函数间隔的概念，定义函数间隔为：



　　可以看到，它就是感知机模型里面的误分类点到超平面距离的分子。对于训练集中m个样本点对应的m个函数间隔的最小值，就是整个训练集的函数间隔。

　　函数间隔并不能正常反应点到超平面的距离，在感知机模型里我们也提到，当分子成比例的增长时，分母也是成倍增长。为了统一度量，我们需要对法向量w加上约束条件，这样我们就得到了几何间隔,定义为：



　　几何间隔才是点到超平面的真正距离，感知机模型里用到的距离就是几何距离。

二、支持向量

        在感知机模型中，我们可以找到多个可以分类的超平面将数据分开，并且优化时希望所有的点都离超平面远。但是实际上离超平面很远的点已经被正确分类，我们让它离超平面更远并没有意义。反而我们最关心是那些离超平面很近的点，这些点很容易被误分类。如果我们可以让离超平面比较近的点尽可能的远离超平面，那么我们的分类效果会好有一些。SVM的思想起源正起于此。

　　如下图所示，分离超平面为，如果所有的样本不光可以被超平面分开，还和超平面保持一定的函数距离（下图函数距离为1），那么这样的分类超平面是比感知机的分类超平面优的。可以证明，这样的超平面只有一个。和超平面平行的保持一定的函数距离的这两个超平面对应的向量，我们定义为支持向量，如下图虚线所示。



支持向量到超平面的距离为,两个支持向量之间的距离为。

三、SVM模型目标函数与优化

　SVM的模型是让所有点到超平面的距离大于一定的距离，也就是所有的分类点要在各自类别的支持向量两边。用数学式子表示为：



对于这个式子，我们从SVM的思想入手，找到离超平面最近的点，使它的几何间隔最大，即：



在数学上，我们总可以通过等比例的缩放w,b，来使得函数间隔



则有目标函数：







      由于的最大化等同于的最小化。这样SVM的优化函数等价于：



       由于目标函数是凸函数，同时约束条件不等式是仿射的，根据凸优化理论，我们可以通过拉格朗日函数将我们的优化目标转化为无约束的优化函数，这和最大熵模型原理小结中讲到了目标函数的优化方法一样。具体的，优化函数转化为：



根据对偶理论及KKT条件

现在我们要求的是：



首先我们来求L(w,b,α)基于w和b的极小值，即。这个极值我们可以通过对w和b分别求偏导数得到：



         从上两式子可以看出，我们已经求得了w和α的关系，只要我们后面接着能够求出优化函数极大化对应的α，就可以求出我们的w了，至于b，由于上两式已经没有b，所以最后的b可以有多个。

带入优化函数L(w,b,α)消去w了。我们定义:



现在我们来看将w替换为α的表达式以后的优化函数ψ(α)的表达式：



（9）式到(10)式使用了(a+b+c+…)(a+b+c+…)=aa+ab+ac+ba+bb+bc+…的乘法运算法则

      从上面可以看出，通过对w,b极小化以后，我们的优化函数ψ(α)仅仅只有α向量做参数。只要我们能够极大化ψ(α)，就可以求出此时对应的α，进而求出w,b.

对ψ(α)求极大化的数学表达式如下：



等价的极小化问题如下：



        只要我们可以求出上式极小化时对应的α向量就可以求出w和b了。具体怎么极小化上式得到对应的α，一般需要用到SMO算法，这个算法比较复杂，后面来讲。在这里，我们假设通过SMO算法，我们得到了对应的α的值α∗。

那么我们根据，可以求出对应的w的值.

求b则稍微麻烦一点。注意到，对于任意支持向量，都有



       假设我们有S个支持向量，则对应我们求出S个b∗,理论上这些b∗都可以作为最终的结果， 但是我们一般采用一种更健壮的办法，即求出所有支持向量所对应的，然后将其平均值作为最后的结果。注意到对于严格线性可分的SVM，b的值是有唯一解的，也就是这里求出的所有b∗都是一样的，这里我们仍然这么写是为了和后面加入软间隔后的SVM的算法描述一致。

      怎么得到支持向量呢？根据KKT条件中的对偶互补条件，如果αi>0则有即点在支持向量上，否则如果αi=0则有，即样本在支持向量上或者已经被正确分类。

四、线性可分SVM的算法过程

        输入是线性可分的m个样本(x1,y1),(x2,y2),...,(xm,ym)其中x为n维特征向量。y为二元输出，值为1，或者-1.

　　输出是分离超平面的参数w∗和b∗和分类决策函数。

　　算法过程如下：

　　1）构造约束优化问题



　　　　2）用SMO算法求出上式最小时对应的α向量的值α∗向量.

　　　　3) 计算

　　　　4) 找出所有的S个支持向量,即满足对应的样本，通过，计算出每个支持向量对应的,计算出这些. 所有的对应的平均值即为最终的,这样最终的分类超平面为：，最终的分类决策函数为：

五、线性SVM的软间隔最大化

        线性可分SVM的学习方法对于非线性的数据集是没有办法使用的， 有时候不能线性可分的原因是线性数据集里面多了少量的异常点，由于这些异常点导致了数据集不能线性可分， 那么怎么可以处理这些异常点使数据集依然可以用线性可分的思想呢？



如何解决这些问题呢？SVM引入了软间隔最大化的方法来解决。

回顾下硬间隔最大化的条件：



      SVM对训练集里面的每个样本(xi,yi)引入了一个松弛变量ξi≥0,使函数间隔加上松弛变量大于等于1，也就是说：

         (注意：这里的本身就是一个函数间隔)

       对比硬间隔最大化，可以看到我们对样本到超平面的函数距离的要求放松了，之前是一定要大于等于1，现在只需要加上一个大于等于0的松弛变量能大于等于1就可以了。当然，松弛变量不能白加，这是有成本的，每一个松弛变量ξi, 对应了一个代价ξi，这个就得到了我们的软间隔最大化的SVM学习条件如下：



         这里,C>0为惩罚参数，可以理解为我们一般回归和分类问题正则化时候的参数。C越大，对误分类的惩罚越大，C越小，对误分类的惩罚越小。

         也就是说，我们希望尽量小，误分类的点尽可能的少。C是协调两者关系的正则化惩罚系数。在实际应用中，需要调参来选择。

六、线性SVM软间隔最大化目标函数的优化

和线性可分SVM的优化方式类似，我们首先将软间隔最大化的约束问题用拉格朗日函数转化为无约束问题如下：



其中 μi≥0,αi≥0,均为拉格朗日系数。

这个优化目标也满足KKT条件，也就是说，我们可以通过拉格朗日对偶将我们的优化问题转化为等价的对偶问题来求解如下：



首先我们来求优化函数对于w,b,ξ的极小值，这个可以通过求偏导数求得：



好了，我们可以利用上面的三个式子去消除w和b了。





        仔细观察可以发现，这个式子和我们上面线性可分SVM的一样。唯一不一样的是约束条件。现在我们看看我们的优化目标的数学形式：



对于C−αi−μi=0，αi≥0，μi≥0，这3个式子，我们可以消去μi，只留下αi，也就是说0≤αi≤C。 同时将优化目标函数变号，求极小值，如下：



         这就是软间隔最大化时的线性可分SVM的优化目标形式，和上面的硬间隔最大化的线性可分SVM相比，我们仅仅是多了一个约束条件0≤αi≤C。我们依然可以通过SMO算法来求上式极小化时对应的α向量就可以求出w和b了。

七、软间隔最大化时的支持向量

      在硬间隔最大化时，支持向量比较简单，就是满足就可以了。根据KKT条件中的对偶互补条件，如果αi>0则有即点在支持向量上，否则如果αi=0则有，即样本在支持向量上或者已经被正确分类。

　　　　在软间隔最大化时，则稍微复杂一些，因为我们对每个样本引入了松弛变量。我们从下图来研究软间隔最大化时支持向量的情况，第i个点到对应类别支持向量的距离为。根据软间隔最大化时KKT条件中的对偶互补条件

我们有：

         a) 如果α=0,那么,即样本在间隔边界上或者已经被正确分类。如图中所有远离间隔边界的点。

　　  b) 如果0<α<C,那么,即点在间隔边界上。

　　  c) 如果α=C，说明这是一个可能比较异常的点，需要检查此时ξi

　　　　i)如果0≤ξi≤1,那么点被正确分类，但是却在超平面和自己类别的间隔边界之间。如图中的样本2和4.

　　　　ii)如果ξi=1,那么点在分离超平面上，无法被正确分类。

　　　　iii)如果ξi>1,那么点在超平面的另一侧，也就是说，这个点不能被正常分类。如图中的样本1和3.

(补充几点：

这里距离其实就是第i个点到分离超平面的几何间隔，分子本身是到到超平面的函数间隔
这里理解的关键除了上面说的KKT的对偶互补条件，还有就是拉格朗日系数，以及松弛变量 ，我们的目标是除了满足KKT条件外，还要最小化目标函数，即希望越小越好，而也是越小越好。


对于时，这时KKT条件完全满足，即使小到为0，也不破坏KKT条件，因此这些点可以被正确分类。


对于时，为满足KKT条件只有，此时即使小到为0，可以让即可。
而时，这里需要理解正则化系数C，它是为了模型泛化引入的一个值，当样本点无法被支持向量正确分开时，拉格朗日系数才会为C。所以有下面的三种异常情况：在分离超平面和支持向量间，在分类超平面上，或者在另一侧。)


八、合页损失函数

线性支持向量机还有另外一种解释如下：





称为合页损失函数(hinge loss function)，下标+表示为：



       也就是说，如果点被正确分类，且函数间隔大于1，损失是0，否则损失是1−y(w∙x+b),如下图中的绿线。我们在下图还可以看出其他各种模型损失和函数间隔的关系：对于0-1损失函数，如果正确分类，损失是0，误分类损失1， 如下图黑线，可见0-1损失函数是不可导的。对于感知机模型，感知机的损失函数是[−yi(w∙x+b)]+，这样当样本被正确分类时，损失是0，误分类时，损失是−yi(w∙x+b)，如下图紫线。对于逻辑回归之类和最大熵模型对应的对数损失，损失函数是 ,如下图红线所示。



九、线性不可分支持向量机与核函数

       线性可分SVM通过软间隔最大化，可以解决线性数据集带有异常点时的分类处理，但是现实生活中的确有很多数据不是线性可分的，这些线性不可分的数据也不是去掉异常点就能处理这么简单。那么SVM怎么能处理中这样的情况呢？接下来讨论线性不可分SVM和核函数的原理。

抛砖迎玉：

     在线性回归中，我们知道如何将多项式回归转化为线性回归。比如一个只有两个特征的p次方多项式回归的模型：



　我们令x0=1,x1=x1,x2=x2,x3=x21,x4=x22,x5=x1x2 ,这样我们就得到了下式：



         可以发现，我们又重新回到了线性回归，这是一个五元线性回归，可以用线性回归的方法来完成算法。对于每个二元样本特征(x1,x2),我们得到一个五元样本特征，通过这个改进的五元样本特征，我们重新把不是线性回归的函数变回线性回归。

也就是说，对于二维的不是线性的数据，我们将其映射到了五维以后，就变成了线性的数据。

        这给了我们启发，也就是说对于在低维线性不可分的数据，在映射到了高维以后，就变成线性可分的了。这个思想我们同样可以运用到SVM的线性不可分数据上。也就是说，对于SVM线性不可分的低维特征数据，我们可以将其映射到高维，就能线性可分，此时就可以运用上面的线性可分SVM的算法思想了。

核函数的引入

　    上一节我们讲到线性不可分的低维特征数据，我们可以将其映射到高维，就能线性可分。现在我们将它运用到我们的SVM的算法上。回顾线性可分SVM的优化目标函数：



       注意到上式低维特征仅仅以内积的形式出现，如果我们定义一个低维特征空间到高维特征空间的映射ϕ（比如上面的例子就是从2维到5维的映射），将所有特征映射到一个更高的维度，让数据线性可分，我们就可以继续按前面的方法来优化目标函数，求出分离超平面和分类决策函数了。也就是说现在的SVM的优化目标函数变成：



可以看到，和线性可分SVM的优化目标函数的区别仅仅是将内积替换为。

        看起来似乎这样我们就已经完美解决了线性不可分SVM的问题了，但是事实是不是这样呢？我们看看，假如是一个2维特征的数据，我们可以将其映射到5维来做特征的内积，如果原始空间是三维，可以映射到到19维空间，似乎还可以处理。但是如果我们的低维特征是100个维度，1000个维度呢？那么我们要将其映射到超级高的维度来计算特征的内积。这时候映射成的高维维度是爆炸性增长的，这个计算量实在是太大了，而且如果遇到无穷维的情况，就根本无从计算了。

好吧，核函数该隆重出场了！



       假设ϕ是一个从低维的输入空间χ（欧式空间的子集或者离散集合）到高维的希尔伯特空间的H映射。那么如果存在函数K(x,z)，对于任意x,z∈χ，都有：K(x,z)=ϕ(x)∙ϕ(z),我们就称K(x,z)K(x,z)为核函数。

核函数的理解：

        从上面的式子乍一看还是不明白核函数怎么帮我们解决线性不可分的问题的。仔细观察上式可以发现，K(x,z)的计算是在低维特征空间来计算的，它避免了在刚才我们提到了在高维维度空间计算内积的恐怖计算量。也就是说，我们可以好好享受在高维特征空间线性可分的结果，却避免了高维特征空间恐怖的内积计算量。

我们遇到线性不可分的样例时，常用做法是把样例特征映射到高维空间中去(如上面的多项式回归）但是遇到线性不可分的样例，一律映射到高维空间，那么这个维度大小是会高到令人恐怖的。此时，核函数就体现出它的价值了，核函数的价值在于它虽然也是将特征进行从低维到高维的转换，但核函数好在它在低维上进行计算，而将实质上的分类效果（利用了内积）表现在了高维上，这样避免了直接在高维空间中的复杂计算，真正解决了SVM线性不可分的问题。

核函数的定理有一个复杂的数学推导过程，这里不做过多的叙述，感兴趣的可以参考下李航老师的《统计学习方法》。

下面我们来看看常见的核函数, 选择这几个核函数介绍是因为scikit-learn中默认可选的就是下面几个核函数。

线性核函数

    线性核函数（Linear Kernel）其实就是我们前面的线性可分SVM，表达式为：





　也就是说，线性可分SVM我们可以和线性不可分SVM归为一类，区别仅仅在于线性可分SVM用的是线性核函数。

多项式核函数

　多项式核函数（Polynomial Kernel）是线性不可分SVM常用的核函数之一，表达式为：





其中，都需要自己调参定义。

高斯核函数

     高斯核函数（Gaussian Kernel），在SVM中也称为径向基核函数（Radial Basis Function,RBF），它是非线性分类SVM最主流的核函数。libsvm默认的核函数就是它。表达式为：





其中，大于0，需要自己调参定义。

Sigmoid核函数

Sigmoid核函数（Sigmoid Kernel）也是线性不可分SVM常用的核函数之一，表达式为：



其中，都需要自己调参定义。

十、分类SVM的算法小结

引入了核函数后，我们的SVM算法才算是比较完整了。现在我们对分类SVM的算法过程做一个总结。不再区别是否线性可分。

　    输入是m个样本(x1,y1),(x2,y2),...,(xm,ym),其中x为n维特征向量。y为二元输出，值为1，或者-1.

　    输出是分离超平面的参数和和分类决策函数。

　　　　算法过程如下：

　　　　1）选择适当的核函数和一个惩罚系数C>0, 构造约束优化问题



              2）用SMO算法求出上式最小时对应的αα向量的值向量.

　　　   3) 得到，此处可以不直接显式的计算。

　　      4) 找出所有的S个支持向量,即满足对应的样本，通过，计算出每个支持向量对应的,计算出这些 所有的对应的平均值即为最终的

　　 这样最终的分类超平面为：，最终的分类决策函数为：

十一、支持向量机算法参数

这里以svc（SVM classifier）为例

svc官网参数



class 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)

Parameters:       
C : float, optional (default=1.0)
Penalty parameter C of the error term.
误差项的惩罚参数C，用于平衡模型损失和模型复杂度。C越大，越不能容忍出现误差，容易过拟合。 C太小，容易欠拟合。
kernel : string, optional (default=’rbf’)
Specifies the kernel type to be used in the algorithm. It must be one of ‘linear’, ‘poly’, ‘rbf’, ‘sigmoid’, ‘precomputed’ or a callable. If none is given, ‘rbf’ will be used. If a callable is given it is used to pre-compute the kernel matrix from data matrices; that matrix should be an array of shape (n_samples, n_samples).
1. 因为polynomial kernel的参数太多导致模型太复杂。一般不选择polynomial kernel。
2. 一般优先考虑RBF，可以让模型达到最佳精准度。而且毕竟RBF kernel可以处理非线性的情况。
3. 如果feature的数量很大，跟样本数量差不多，这时候可以选用linear kernel。因为高维空间中的数据往往是(近似地)线性可分的，直接选用linear kernel可以节约模型的训练时间。
degree : int, optional (default=3)
Degree of the polynomial kernel function (‘poly’). Ignored by all other kernels.
核函数中的degree设置(针对多项式核函数)(默认3)
gamma : float, optional (default=’auto’)
Kernel coefficient for ‘rbf’, ‘poly’ and ‘sigmoid’. If gamma is ‘auto’ then 1/n_features will be used instead.
核函数中的gamma函数设置(针对多项式/rbf/sigmoid核函数)
选择RBF函数作为kernel后， 核函数系数有效。gamma的值越大，在转换后的空间中，训练样本被散得越开。
默认是’auto’，此时核函数系数为：1/n_features

coef0 : float, optional (default=0.0)
Independent term in kernel function. It is only significant in ‘poly’ and ‘sigmoid’.
针对多项式/sigmoid核函数
probability : boolean, optional (default=False)
Whether to enable probability estimates. This must be enabled prior to calling fit, and will slow down that method.
shrinking : boolean, optional (default=True)
Whether to use the shrinking heuristic.
tol : float, optional (default=1e-3)
Tolerance for stopping criterion.
cache_size : float, optional
Specify the size of the kernel cache (in MB).
class_weight : {dict, ‘balanced’}, optional
Set the parameter C of class i to class_weight*C for SVC. If not given, all classes are supposed to have weight one. The “balanced” mode uses the values of y to automatically adjust weights inversely proportional to class frequencies in the input data as n_samples / (n_classes * np.bincount(y))
verbose（详细的） : bool, default: False
Enable verbose output. Note that this setting takes advantage of a per-process runtime setting in libsvm that, if enabled, may not work properly in a multithreaded context.
启用详细输出。注意，这个设置利用了libsvm中的每个进程运行时设置，如果启用了这个设置，那么在多线程环境中可能无法正常工作。
max_iter : int, optional (default=-1)
Hard limit on iterations within solver, or -1 for no limit.
decision_function_shape : ‘ovo’, ‘ovr’, default=’ovr’
Whether to return a one-vs-rest (‘ovr’) decision function of shape (n_samples, n_classes) as all other classifiers, or the original one-vs-one (‘ovo’) decision function of libsvm which has shape (n_samples, n_classes * (n_classes - 1) / 2).
Changed in version 0.19: decision_function_shape is ‘ovr’ by default.
New in version 0.17: decision_function_shape=’ovr’ is recommended.
Changed in version 0.17: Deprecated decision_function_shape=’ovo’ and None.
random_state : int, RandomState instance or None, optional (default=None)
The seed of the pseudo random number generator to use when shuffling the data. If int, random_state is the seed used by the random number generator; If RandomState instance, random_state is the random number generator; If None, the random number generator is the RandomState instance used by np.random.
Attributes:       
support_ : array-like, shape = [n_SV]
Indices of support vectors.
support_vectors_ : array-like, shape = [n_SV, n_features]
Support vectors.
n_support_ : array-like, dtype=int32, shape = [n_class]
Number of support vectors for each class.
dual_coef_ : array, shape = [n_class-1, n_SV]
Coefficients of the support vector in the decision function. For multiclass, coefficient for all 1-vs-1 classifiers. The layout of the coefficients in the multiclass case is somewhat non-trivial. See the section about multi-class classification in the SVM section of the User Guide for details.
coef_ : array, shape = [n_class-1, n_features]
Weights assigned to the features (coefficients in the primal problem). This is only available in the case of a linear kernel.
coef_ is a readonly property derived from dual_coef_ and support_vectors_.
intercept_ : array, shape = [n_class * (n_class-1) / 2]
Constants in decision function.
十二、SVM总结

SVM的空间消耗主要是存储训练样本和核矩阵。
时间消耗《A Tutorial on Support Vector Machines for Pattern Recognition》  1998KluwerAcademicPublishers,Boston，训练计算复杂度在O(Nsv^3+LNsv^2+d*L*Nsv)和O(d*L^2)之间，其中Nsv是支持向量的个数，L是训练集样本的个数，d是每个样本的维数(原始的维数，没有经过向高维空间映射之前的维数)
优点：

1、使用核函数可以向高维空间进行映射
2、使用核函数可以解决非线性的分类
3、分类思想很简单，就是将样本与决策面的间隔最大化
4、分类效果较好
缺点：

1、 SVM算法对大规模训练样本难以实施，由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。
针对这个问题的主要改进有J.Platt的SMO算法、T.Joachims的SVM、C.J.C.Burges等的PCGC、张学工的CSVM

2、 用SVM解决多分类问题存在困难，法直接支持多分类，但是可以使用间接的方法来做
经典的支持向量机算法只给出了二类分类的算法，而在数据挖掘的实际应用中，一般要解决多类的分类问题。可以通过多个二类支持向量机的组合来解决。主要有：

一对多组合模式、一对一组合模式和SVM决策树；通过构造多个分类器的组合来解决。

其他观点：SVM在小样本训练集上能够得到比其它算法好很多的结果。支持向量机之所以成为目前最常用，效果最好的分类器之一，在于其优秀的泛化能力，这是是因为其本身的优化目标是结构化风险最小，而不是经验风险最小，因此，通过margin的概念，得到对数据分布的结构化描述，因此减低了对数据规模和数据分布的要求。SVM也并不是在任何场景都比其他算法好，对于每种应用，最好尝试多种算法，然后评估结果。如SVM在邮件分类上，还不如逻辑回归、KNN、bayes的效果好。  
---------------------
【转载】
作者：不曾走远~
原文：https://blog.csdn.net/qq_20412595/article/details/82112457

---

作者: 不二晨    时间: 2018-10-25 10:45

---

作者: 魔都黑马少年梦    时间: 2018-11-1 16:20

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2