数据挖掘-支持向量机
支持向量机（support vector machine，SVM）是一种出色的分类技术，也可以用于回归分析（SVR）。这种技术可以很好的应用于高维数据，避免维度灾难等问题。
SVM有一个特点就是使用训练集中的一个子集来表示决策边界，该子集称作 支持向量 。
SVM的核心目标是找到分类中的最大边缘超平面，让其作为决策边界，那么什么是最大边缘超平面呢？
但是可以发现，这种超平面有无数多个（图中就能看到有好多个），如果有一些未知的点需要预测分类，那么他们可能未必会被这些超平面完美的分隔：
以最下侧的超平面为例，如果我们有未知的点按照蓝色排布，那么可以看到，最下侧的这个超平面完全不能分类所有蓝色点的“-”号，那么如果它作为决策边界，泛化能力就不是很好。
我们肯定要从这些超平面中选一个最合理的作为决策边界，使得未知的点尽量的能被正确预测分类，那么肯定是上图中间的这个超平面最好了，我们目测就可以得到结果，因为 它离两边这些点的距离围成的面积应该是最大的，而且两边的面积基本是差不多的 。（个人理解）所以应该能装得下更多的未知点，也就能得到最好的泛化效果。
为了不用肉眼观测，能量化的得到这个结果，我们可以定义 最大边缘超平面 。
下图中有两个决策边界， 和 ，其中每个决策边界都对应着两个超平面(记作 )。其中 是由 进行两侧平移，直到接触到最近的一个训练集的点停止，生成的，同理 也是。
我们把两个超平面（同一个决策边界生成的）之间的距离叫做分类器的边缘，那么下图中，显然 生成的两个超平面距离应该是最大的， 就叫做 最大边缘超平面 （ 虽然是决策边界，但是决策边界都是超平面）。
通常来说，较大边缘的超平面具有更好的泛化误差，如果边缘比较小，那么决策边界的轻微扰动都可能对分类产生显著影响。
SVM算法的核心就是设计最大化决策边界边缘的分类器，以保证最坏情况下泛化误差最小 。
假设有一个包含 个训练样本的二元分类问题，每个样本表示为一个二元组 , 其中 ，对应于第i个样本的属性集（一个样本有多个属性/特征）,设y有-1和1两个类别，则一个 线性分类器的决策边界 可以写成如下形式：
其中的 为参数， 是法向量（垂直于决策边界）的向量，代表着超平面的方向，而 代表超平面与原点之间的距离（可以用一次函数的公式来理解）。
为什么 一定会垂直于决策边界呢？我们设有两个点 是决策边界上的两点，那么有：
二者相减有：
因为 肯定是平行于决策边界的，那么为了保证内积为0， 肯定要垂直于决策边界。
根据以上的决策边界，则肯定有：
如果上方的点是1类，下方是-1类，则有：
如果我们能得到 ，那么就可以用这个公式对未知点进行预测分类。代入公式，如果 就是1类，反之则为-1类。
接下来我们的任务就是如何求这两个参数，首先，既然是求最大边缘超平面，我们要把决策边界的边缘算出来。
根据上图，考虑那些离决策边界最近的方形和圆形，我们可以得到两个平行的超平面表示如下：
决策边界的边缘就是这两个超平面的距离。
参考上图的 ，不难得出边缘 为：
其中 是w的2范数。
很显然，我们想要让这个 最大，那么就要让 最小。
于是，接下来我们的求参数目标就明确了。
由于 肯定是非负的，我们可以改写一下
这个式子，让它变成求 的最小值。
既然要求最小值，就需要有另外一个约束条件，否则是没办法求的，我们来看之前总结的线性SVM分类器的公式：
由于 和 是决策边界的两个超平面，我们从上图中可以看出，所有的点（除了这两个超平面经过的点以外，经过的点是离决策边界最近的点），都肯定有 和 。
我们把y引入进来，那么这两个式子就能合到一起写为：
注意不要和之前总结的公式中的 弄混，那个条件是最终预测分类的公式，也就是表明只要在决策边界的上方就可以进行分类，而现在的>=1是在已知训练集的情况下求模型的参数。
综合以上的式子，我们可以得到求参数的基本式：
目标函数是二次的，而约束在参数 和 上是线性的，因此这是一个凸优化问题， 不存在局部优化的问题 。
求这一套公式的最小值，需要用到 拉格朗日乘数法 ，这个我也不是很明白，就按照百度百科的定义往里套：
虽然我们这里的附加条件是大于等于1的，不过不妨改写一下试试，则有：
其中的 就是 拉格朗日乘子 ，理论上来说，拉格朗日乘子可以为任何值。
如果约束条件是=0的话，我们就可以直接对 和 求偏导数，让他们等于0，就能求得参数。
但是目前条件并不是等于0的，而是大于等于0的。
处理不等式约束一种方法就是变换成一组等式约束，根据KKT条件，可以限制拉格朗日乘子飞赴，把之前的约束变换为：
该约束表明，除非训练样本满足方程 ，否则拉格朗日乘子必须为0。
结合上面展示决策边界和超平面的图，我们可以想到，满足这个方程的样本，肯定都在决策边界生成的两个超平面上。这些样本处的拉格朗日乘子肯定够大于0，而其他样本的拉格朗日乘子，肯定等于0，因此问题得到简化。 因为参数的确定仅依赖于这些在超平面上的样本。
这些在超平面上的样本，被称作 支持向量 ，这也就是支持向量机的命名缘由。
有了以上的修改后的约束，我们可以在 对 和 求偏导，并让他们等于0.
我们已知，这个时候的 和 是有满足条件的最优解的，把这两个式子代入原公式，就能得到 的最小值（当然此时因为不知道拉格朗日乘子，我们是求不出来的），代入公式可得：
该函数叫做对偶拉格朗日函数。
用这个函数，就是把之前求w和b的公式变换成了求拉格朗日乘子的公式，同时需要注意，这个式子中是求拉格朗日对偶函数的最大化问题。
我们可以用二次规划法或者SMO方法来求拉格朗日乘子。
二次规划算法比较通用，但是计算量比较大，SMO算法的核心就是把复杂的式子变换成比较简易的之后，用二次规划来计算。
SMO的基本思路是：先固定 之外的所有参数，然后求 上的极值，由于存在约束 ，如果固定了 之外的其他变量，则能求出 。
那么对偶函数里有两个λ，我们就可以固定这两个λ之外的参数，之后求解 。
其中有一个λ不满足KKT条件，则目标函数就会在迭代后减小，违背程度越大，变量更新后导致的目标函数值就越大。 所以SMO先选取违背KKT条件最大的变量，第二个变量选择使目标函数值见效最快的变量，使选取的两个变量对应样本之间的间隔最大。
然后可以变换为简单的二次规划问题：
找到一组λ后，就可以用原公式求得 的解，决策边界可以表示为：
之后b可以通过 求解。
因为λ通过数值计算得到，因此可能存在误差，则b可能不唯一。通常我们可以用b的 平均值 作为决策边界的参数。
如图所示，这组数据集有两个特征 和一个 标签，我们要对其进行建模分类，可以得到有两个拉格朗日乘子（支持向量上的），其他的均为0.
我们可以得到 有：
第一个 是针对 的参数，以此类推。
有了 ，可以求得 有：
可以根据两个b求平均值，得到b=7.93，因此就能得到分类的模型。
如果需要做预测，把对应点的x向量代入到模型中，求得结果为1的话，就是方形类，其他为圆形类。
上面讨论的模型最终都会生成一条直线，也就是线性的模型，那么往往需要判断非线性的如何处理呢，这里需要引入核函数的技术。
要把SVM应用到非线性决策边界的数据集上，就要把数据集从原来的坐标空间x变换到新的坐标空间中。
我们假定存在一个合适的函数 来变化给定的数据集，那么变换之后，我们就可以根据 来构建线性决策边界（类似于换元法，回忆一下）。变换之后，线性决策边界具有以下的形式：
根据线性SVM的参数计算公式，我们把公式里面的 换成 ，即可求解。
不过这种方式往往会涉及到向量对的点积，计算比较麻烦，当特征数较多时，可能会造成维度灾难的问题，因此我们要引入核函数。
核函数是一种使用原属性集计算变换后的空间中的相似度的方法，简而言之就是，我们如果按照上一段说的算法，则我们需要先计算 ，然后再计算参数，而我们运用核函数，可以直接计算\boldsymbol{x}就可以达到变换属性集的目的。
我们令 ，这样就可以把映射的函数变成了原属性集的计算。 就是核函数。
但是这个 一般我们是不知道的，因此我们要找寻几种通用的函数，让他们可以实现 的功能，以便模拟非线性的决策边界。
这里我们引入一个 Mercer定理 ， 所有的核函数都必须满足Mercer定理。
通常有如下几种核函数：
我们也可以通过核函数的组合来形成新的核函数：
我们直到一般算法都要防止过拟合，防止噪声带来的模型泛化能力下降，那么SVM的防止过拟合方法就是软边缘。
此外，根据KKT条件，可以变换约束如下：
注意，上述三个式子中的 是非零的，当且仅当训练样本位于直线 上或者 。另外对于误分类的训练样本， 都为0.
我们按照正常优化的算法，对 , , 求偏导数，可以得到参数：
代入原公式，可以得到只包括拉格朗日乘子的对偶拉格朗日函数。
这个式子看上去跟不加软边缘的对偶函数是一样的，但是约束是不同的。
软边缘的对偶函数约束为
之后就可以用二次规划或者SOM求参数值了，从而得到模型。
这就是带软边缘的SVM。
以上提到的都是二元分类的办法，那么多分类可以参考常用的多分类处理，用一对一方法，如果有多分类问题，我们可以分解为K（K-1）/2个二类分类器，每一个分类器用来区分一对类 。（注意这里的y都是单独的类，不是一堆类别的集合）
当为 构建分类器时，其他不属于这两类的点都被忽略掉。
之后针对需要预测分类的样本，我们用不同的分类器进行分类，最后进行投票，得到结果。
以上就是SVM（用于分类的支持向量机）的内容，最后看看该算法的特点：
