支持向量机-SVM

作者: Spinggang | 来源:发表于2019-12-02 18:53 被阅读0次

引言

文章根据 udacity 的机器学习视频进行整理，提供给初学者进行参考，为了降低学习门槛，文中尽量避免了复杂的数学公式，使用比较简单的例子叙述相关原理。如发现错误欢迎指正。

1. 简介

支持向量机(SVM) 是一种强大的分类算法，它的目标不仅仅是分类数据。更重要的是找到点点之间的最佳界线。让我们来开它具体的实现方法吧！

2. 基本原理

在开始之前，我们先看一下划分数据的方法。下图有两个数据集，分别是蓝点和红点。现在用一条直线将它们进行划分，如下图：

划分数据集图

如果这是选择题，让你选择是左边的好，还是右边的比较好？相信大多数人都会选择左边，因为左边的黄色线距离红点和蓝点适当，而右边的蓝线则对于两边的某些的点比较近。这个怎么能看出来呢？可以通过点到线的距离，如下图。很明显左边的蓝点到线的距离明显要比右边蓝点到线的距离要长，所以左边的分类方法将胜出。但其实就是SVM所做的事。

划分数据集

2.1 误差

在有监督学习中，我们都会用到误差函数，误差函数结合梯度下降算法才能更好的训练模型。在支持向量机中，误差函数与其他误差函数有不一样的地方，现在来看看支持向量机中的误差函数。

2.1.1 误差函数

回想一下什么是分类？分类简单来说其实就是用一条线将不同的两个数据集进行分开。如下图所示：

划分数据集

但是现在，我们将不仅仅是划分数据集，还需要做到让线尽可能的原理这些数据集。怎么实现？我们需要增加额外的两条线，这两条线（代指下图中的虚线）与主线等距且平行。然后我们尝试将这两条线间的距离间隔最大化。如图：

划分数据集

同样来看一个复杂的数据集，比如下图这个数据集。

使用一条横线进行划分，但我们的要求还需要主线到点的距离尽量的宽。如何评测这个划分：一是查看误分类了多少个点、二是查看间距有多宽，同时保证间距内没有点。查看误分类的点：即查看红色区域有几个蓝色的点；蓝色区域有几个红色的点。查看间距：要保证间距尽量的宽，同时不能有点，在间距内存在点需要进行惩罚，作为误差。所以根据上图的划分即存在如下图的误差(画圈的点即为误差)：

总结可以知道误差函数等于分类误差加边际误差。即：

ERROR = CLASSIFICATION ERROR （分类误差） + MARGIN ERROR （边际误差）

2.1.2 分类误差

现在来看分类误差。在下图中，我们用一条直线，假设这条线为 Wx + b = 0 划分数据集。但是需要的不仅仅这条线，还需要两条与之平行且等距离的线形成间隔。这两条线的假设为 Wx + b = 1 和 Wx + b = -1 。

现在需要对误分类的点进行操作。误分类的点：一个是红色区域内的蓝点、一个是蓝色区域内的红点。同时保证间距内没有任何点，如果存在点将作为误差加入。这样一来就有了如下图所示的误差。一个是以 Wx + b = -1 直线划分的误差，存在 3 个分类错误的红点。一个是以 Wx + b = 1 划分的误差，存在 3 个划分错误的蓝点。

为了建立误差，我们选取绝对值，假设为 1 。那么在蓝色区域从底线 Wx + b = -1 起，误差分别为 0、1、2、3、4、5 。同样红色区域，以Wx + b = 1 起。误差分别为 0、1、2、3、4、5。如下图

如此，可以看到对应的蓝色区域红点误差分别为：0.5 、1.5、3.5 。红色区域内蓝点误差：2、3、0.3 。所以分类误差等于：

Classification Error = 0.5 + 1.5 + 3.5 + 2 + 3 + 0.3

2.1.3 边际误差

现在看边际误差。如下图同样的两组数据集，包含主线和间距。唯一不同的是左边的间距比较大；右边的间距比较小。

现在需要将间隔转化为误差，转化为误差就可以使用梯度下降最小化。我们需要实现在间隔最大的时候，误差最小。间隔最小的时候，误差最大。这是因为我们需要一个拥有最大间隔的模型。

这其实很简单。如下图所示，用 Wx + b = 0 表示主线、其中 Wx + b = 1 和 Wx+ b = -1 表示虚线。两条虚线之间的距离为间距(间距) 。

那么其间距等于：（PS：关于公式的相关资料可查看：https://www.cnblogs.com/paulonetwo/p/9971010.html）

$Margin = \frac{2}{|W|}$

误差等于：

$Error = {{|X|}^{2}}$

根据公式，假设 W = （3, 4) 和 W = （6, 8）的两个例子。如下图计算：

Example 1 ：

Example 2 ：

Example 1 中： margin = 2/5 、Error = 25 。 Example 2 中： margin = 2/10 = 1/5、Error = 100 。

即实现间距大的情况下、误差小。间距小的情况小、误差大。

2.2 C 参数

什么是C参数？从概念上讲 C 参数是让SVM算法更加具有灵活性。来看一个例子：

有这样的两组数据集。以一条直线进行划分，如下图所示，那一条更好？

可能有的会认为左边的更好，有的可能会认为右边好。事实上这并没有标准答案，只是在不同的情况下，需要选择不同模型。例如：在医学角度上，通常会选择右边的模型，因为右边的模型正确分类，没有错误。然后在其他情况下，通常会选择左边的模型，因为左边的模型，因为左边的模型有更大的间距。对此，SVM 算法通过 C 参数来增加灵活性，保证在不同的场景下选择不同的模型。

C 参数只是分类误差之前的一个常数项。如下图：

Error = C * Classification Error + Margin Error

我们将 C 参数乘以分类误差，如果 C 参数比较大。那么大部分都是分类误差，那么模型将更注重数据的分类，而不是寻找合适的间距。如果 C 参数比较小，那么模型将更注重合适的间距，而不是正确的数据分类。

C 参数是一个常量，为了寻找合适的值。实际应用中可通过网格搜索等技巧寻找合适的值。

2.3 多项式内核

什么是多相式内核？这听起来比较复杂。但并非如此，来看一个简单例子。让我们快速理解多项式内核。

2.3.1 多项式内核(一)

数据分类。简单的描述就是通过一条直线将数据进行分开，然而SVM算法出来将数据划分，还会找到最合适间距。如果是复杂的情况下，无法使用一条直线将数据进行划分，如下图的数据：

在这样的一维平面下，无法使用一条直线将数据进行划分，这该怎么操作？一个方法就是，将一维数据映射到二维平面上。只需要在原来基础上增加一个 y 轴，绘制 $y = x^{2}$ 函数曲线。如图：

然后将对应 x 轴上的数据进行映射到 $y = x^{2}$ 曲线上，如下图：

如此，便可以使用 SVM 算法进行划分了，假设这条线是 y = 4 。如下图：

现在的问题是如何回到原来的一维直线上，并划分边界。很简单，结合 $y = x^{2}$ 和 $y = 4$ 求解 $x$ 。可得到 $x = 2$ 和 $x = -2$ 两个解。接下来就是将 $x = 2$ 和 $x = -2$ 带入到原来模型中，这两个解就是模型的分界线。

如此便很好的划分了数据集。这种方法被称为核技巧，广泛用于支持向量机以及其他机器学习算法中。

2.3.2 多项式内核(二)

核方法非常有趣，但用在更高维度中将更加有趣。现在一起来看看。

假设有这样的一个数据集，无法通过一条直线进行划分。如下图所示，我们将再次使用核方法进行完成。

完成这个的划分，一种方法是使用一个圆将红点和蓝点分开。如下图所示：

一种方法是引进第三维度，脱离水平面去思考。将红点和蓝点分别映射到不同的平面上。如下图：

使用圆形的方法牺牲了线性度，不在使用线性维度，而是使用多次项方程式。使用第三维度的方法，牺牲了数据的维度，不在是二维层面，而是三维。其实两种方法事实上都是一样的。这就是核方法。

在 2.3.1 多项式内核一 中我们使用 $x^{2}$ 很好的解决了一维数据的划分。再次我们将使用类似的方法，只不过这次是二维数据集，但方法同样，只不过这次可能是 $x^{2} + y^{2}$ 、 $x + y$ 、 $xy$ ... 其中一种。

将 $x^{2} + y^{2}$ 、 $x + y$ 、 $xy$ 代入数据进行计算，来观察下列中，那种能更好的划分数集。

观察上图，似乎 $x^{2} + y^{2}$ 能更好的进行划分数据集。为什么呢？可将数据集放到一个轴上查看。如下图：

其中蓝色数字 2 表示原来二维平面上的点、红色数字 18 表示原来二维平面上的点。两点之间有较大的间距，且可以用一条直线很好的划分。

相比 $xy$ 和 $x + y$ 。简单看一下 $xy$ 对应的在一维轴上的点，如图：

可以看出蓝色 1 和 -1 可代表原来二维轴上蓝色的点、红色的 9 和 -9 代表原来二维轴的红点。但是它们之间无法通过一条直线进行划分。同理 $xy$ 也是如此。

根据结论得到了 $x^{2} + y^{2}$ 能更好的表示数据。其中 $x^{2} + y^{2} = 18$ 表示红点、 $x^{2} + y^{2} = 2$ 表示蓝点。怎么分开呢？

其实这个方程式就是 $x^{2} + y^{2} = z$ 为数学中圆的方程式。

同样对于增加第三维度的方法（也叫建楼法）， $z = 18$ 和 $z = 2$ 。在中间划分一个层 $z = 10$ 绘制出一个理想的面。对于一个圆，则是 $x^{2} + y^{2} = z$ 。即如下图：

2.3.3 总结

假设在一个二维的平面中，有一组数据无法通过线性进行分开，我们通过把数据嵌入到一个五维的世界中，假设点为 $（x,y）$ ，在五维的世界中则是 $(x,y,x^{2},y^{2},xy)$ 。现在数据处于一个高纬度中，我们可以分为一个四维超平面，之后返回到二维世界中，得到一个二次多项式，这会很好的划分数据集。这被称做多项式核函数。总之，多项式核函数是一个超参数，可以有更高次项数，比如三次（ $x^{3}、y^{3}$ ）。可以通过训练找到最佳函数。