数据挖掘知识点串烧：SVM
数据挖掘知识点串烧：SVM
本文为数据茶水间群友原创，经授权在本公众号发表。
关于作者：DD-Kylin，一名喜欢编程与机器学习的统计学学生，勤学好问，乐于钻研，期待跟大家多多探讨机器学习的相关内容~
0x00 前言
有人认为支持向量机是所有机器学习算法中最难的一个了，但是仔细去看数据挖掘的招聘要求，你会发现支持向量机(SVM)出现的频率异常地高。果然，该过的坎再难都得跨，那就让我们一起来看看SVM究竟是什么吧~
0x01 初始SVM
问题1：你能给我讲讲什么是SVM吗？
回答：SVM是一种二分类模型，它的基本模型是在特征空间中寻找间隔最大化的分割超平面的线性分类器。如在下面的两个类别中(暂且称两个类为黄球和红球),
我们要将其分割开的方式有多种，但是究竟哪一种才是最优的分割方式呢？这就是支持向量机所要解决的问题。简单而又通俗点的理解：支持向量机的优化目标是找到一条线（w和b), 使得离该线最近的点之间的距离最长。但是在这个过程中，不同的数据所采用的分割策略可能会有所不同，主要的分割策略有三种：
- 当训练样本线性可分时，通过硬间隔最大化，学习一个线性分类器，即线性可分支持向量机；
- 当训练数据近似线性可分时，引入松弛变量，通过软间隔最大化，学习一个线性分类器，即线性支持向量机；
- 当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性支持向量机。
问题2：你知道什么是支持向量吗？alpha什么时候为0什么时候不为0？
回答：支持向量的本质其实也是向量。支持向量机是想找到一个分割超平面或者说分类面，使得它所产生的结果是最鲁棒的，即对未知实例的泛化能力是最强的(这也是支持向量机为什么采用间隔最大化的原因之一）。而支持向量就是这些支撑分割超平面的数据点，其实就是距离分界线最近的点，或者说分界面就是靠这些数据点来确定的，它们支撑着分界面。 对于边界上的样本来说，alpha不等于0，这些边界上的样本点属于支持向量，它们会对最终的结果产生影响。而对于非边界上的样本点来说,alpha等于0， 非边界上的这些样本点是非支持向量，非支持向量不会对最终的结果产生影响。
举个栗子，如在下方的图形中，A、B、C三点就属于支持向量，它们的alpha不为0，且支撑着分割超平面。而其它的样本点的alpha等于0，它们对分割超平面不会造成影响。
0x02 再会SVM
问题1:请问可以怎么提高SVM的泛化能力？
回答：我们知道SVM的约束条件常常会有过拟合(过拟合表现为在训练集上模型的预测结果很准，但是在未知数据上预测效果却很差)的风险,而决定分割超平面的是支持向量，如果这些支持向量中存在异常值点，那么我们还傻兮兮地严格按照SVM的定义去训练模型，那训练出来的模型效果肯定就不会太好。为了解决这个问题，我们可以使用软间隔来处理，所谓软间隔就是为SVM引入了一个松弛变量，使得SVM能够容忍异常值点的存在。因为引入了松弛变量之后，所有点到分割超平面的距离可以不需要严格地大于等于1了，而只需要>= 1-松弛变量值就可以了。
举个例子，如果松弛变量 = 0.1， 那么数据点到分割超平面的距离只需要>= 0.9就可以。通过这个方法就可以将异常值转为非支持向量，将异常值作为一个普通的数据点存在，那么我们的支持向量和分割超平面就都不会收到它的影响了。(下图是使用了软间隔对数据进行分类的可视化结果）
问题2：SVM为什么要引入核函数？
回答：在现实世界中，不是所有的样本都是线性可分的，有时候我们也会遇到线性不可分的样本。如以下情形：
在这种情况下，想要在二维空间中使用线性分割的方法将红球与黄球完全分割开似乎是不可能的。
对于这样的问题，我们可以将样本从原始空间映射到一个更高维的特征空间中，使得样本在这个特征空间中线性可分。我们知道如果原始空间是有限维，即属性数有限，那么就一定存在一个高维特征空间能够将样本分开。通过将输入空间映射到了高维的特征空间，可以把平面上不好区分的非线性数据很好地区分开。但是对于映射后的对偶问题，如果我们直接去计算的话会较为难算，为了解决这个问题，才引入了核函数(目的：为了解决映射后难以计算的问题，方法：设想在原始样本空间中能找到一个函数满足映射后需要计算的两个样本间的特征空间内积)即：
而目前我们所常用的核函数主要有线性核函数、多项式核函数、高斯核函数、拉普拉斯核函数、Sigmoid核函数。
当然，引入核函数之后，核函数的选择就变成了支持向量机中的最大变数了，若核函数的选择不正确的话，那么就可能将样本映射到了一个不合适的特征空间，导致的后果就很有可能是模型的性能不好。
(对于核函数这一部分，建议大家可以准备一下各种核函数的使用场景以及核函数的选择这一块的内容)
问题3：SVM中为什么会有SMO算法？
回答：SVM的基本型就是一个凸二次规划的问题,使用拉格朗日乘子法转换后所获得的关于alpha的函数的求解也是一个二次规划的问题，虽然可以直接使用二次规划问题的算法来进行求解；但是，该问题(二次规划问题)的规模正比于训练样本数，这会在实际任务中造成很大的开销，为求出alpha同时为避免通用的二次规划算法所造成的巨大开销，才引入了SMO算法。
(关于SMO，我觉得大家可以准备一下SMO的算法思想、SMO算法优化的终止条件等方面的知识)
0x03 优点 VS 缺点
问题：SVM有什么样的优点跟缺点呢？
回答：SVM的优点有：
- 可以使用核函数将原始数据映射到高维的特征空间上，进而解决非线性的分类问题；
- SVM的分类思想很简单，就是将样本与分类面的间隔最大化
- SVM的分类效果较好；
SVM的缺点有：
- SVM无法直接支持多分类任务，但是可以通过间接的方法来实现多分类(这点跟逻辑回归的分类思想很像，间接的多分类方法有一对一、一对其余、多对多这三种拆分策略)；
- 对某些缺失数据敏感,对核函数的选择也很敏感
0x04 总结
关于SVM，不得不说理解起来确实有难度。但是其分类思想还是很简单的，就是将样本跟分类面的间隔最大化。只是在这个过程中，所引入的求解方法及求解思想比较复杂。本文只是简单列举了几个小问题，关于这个模型其实还有很多需要了解的知识点。比如：如何确定C值、如何对SVM进行调参、什么是对偶问题、SVM为什么会引入对偶问题等。希望本文能起到一个抛砖引玉的作用，对于文章中所留下及本文中未提及的问题，希望各路大神能在留言下方帮忙解答与提出，一起交流讨论~
参考文献
- 《机器学习》 （周志华）
- 《数据挖掘-实用机器学习工具与技术》（Ian H.Witten, Eibe Frank, Mark A.Hall）(李川， 张永辉 译)
- 《机器学习实战》 （Aurelien Geron) (王静源、贾玮等译）