SVM
 
 
 
SVM：Support Vector Machine
 
 
中文名：支持向量机
 
 
学习模型
 
有监督学习：需要事先对数据打上分类标签，这样机器就知道数据属于哪一类。
 
无监督学习：数据没有打上分类标签，有可能因为不具备先验知识，或打标签的成本很高，需要机器代替我们部分完成改工作，比如将数据进行聚类，方便后人工对每个类进行分析。
 
SVM 是有监督的学习模型：可以进行模式识别、分类以及回归分析。
 
SVM工作原理
 
示例： 桌面上有两种颜色混乱的小球，我们将这两种小球来区分开，我们猛拍桌子小球会腾起，在腾空的那一刹那，会出现一个水平切面，将两种颜色的球分开来。
 
原因： 二维平面无法找出一条直线来区分小球颜色，但是在三位空间。我们可以找到一个平面来区分小球颜色，该平面我们叫做超平面。
 
SVM计算过程： 就是帮我们找到一个超平面的过程，该超平面就是 SVM分类器。
 
分类间隔
 
我们在示例中，会找到一个决策面来将小球颜色分离，在保证决策面C不变，且分类不产生错误的情况下，我们可以移动决策面，来产生两个极限位置：决策面A和决策面B，分界线C就是最优决策面，极限位置到最优决策面的距离就是 分类间隔 。
 
我们可以转动最优决策面，会发现存在多个最优决策面，它们都能把数据集正确分开，这些最优决策面的分类间隔可能是不同的，拥有最大间隔的决策面就是 SVM 需要的最优解。
 
点到超平面距离公式
 
决策面在一维空间就是一个点、二维空间就是一条直线、三维空间就是一个平面，当空间维度更多，这个线性函数名称叫做 “超平面”：$g(x)=w^{T}x+b$，其中$w,x\in R^n$
 
w、x是n维空间里的向量，其中x是函数变量，w是法向量。法向量指的是垂直于平面直线所表示的向量，决定超平面的方向。
 
SVM就是帮我们找到一个超平面 ，这个超平面能将不同样本划分，使得样本集中的点到这个分类超平面的最小距离(分类间隔)最大化，在这个过程中 支持向量 就是离 分类超平面 最近的样本点，如果确定了支持向量也就确定了这个超平面，所以支持向量决定了分类间隔是多少，在最大间隔以外的样本点，对分类都没有意义。
 
SVM就是求解 最大分类间隔的过程，我们还要对分类间隔大小进行定义。
 
定义某类样本集到超平面的距离就是这个样本集合内的样本到超平面的最短距离，用di代表点xi到超平面wxi+b=0的欧氏距离。因此我们求di最小值，计算公式$$d_i=\frac{|w{x}_i+b|}{||w||}$$，其中$||w||$为超平面的范数，di可以用解析几何知识进行推导。
 
最大间隔优化模型
 
目标： 找出所有分类间隔中最大的那个值对应的超平面。
 
硬间隔、软间隔和非线性SVM
 
数据线性可分：模型称为硬间隔支持向量机 
  
硬间隔：完全分类准确，不存在分类错误的情况
软间隔：允许一定量的样本分类错误
 
非线性数据：模型称为非线性支持向量机
 
非线性数据集合： 两种颜色的小球，呈现大小圆环的形状。
 
非线性数据集合，不论多高级的分类器，只要映射函数是线性的，就没办法处理，SVM也处理不了。
 
核函数： 可以将样本从原始空间映射到一个更高的特质空间中，使得样本在新空间中线性可分，我们就以可以使用原来的推到进行计算，所有推到都是在新空间，而不是在原来的空间中进行。
 
在非线性SVM中，核函数的选择就是影响SVM最大的变量，下面是常用的核函数
 
线性核
多项式核
高斯核
拉普拉斯核
sigmoid核
 
这些函数的区别在于映射方式的不同，通过核函数就能把样本空间投射到新的高维空间中。
 
结果： 软间隔和核函数的提出，都是为了方便对超平面公式中的w和b进行求解，得到最大分类间隔的超平面。
 
SVM解决多分类问题
 
SVM本身就是一个二值分类器，最初是为二分类问题设计的，就是回答Yes/No，但是实际解决的问题，可能是多分类情况，比如：文本进行分类、图像进行识别。
 
多分类情况，可以将多个二分类器组合起来形成一个多分类器，常见方法有一对多法、一对一法两种。
 
一对多法
 
我们将物体分为A、B、C、D四种分类，先把其中的一类作为分类1，其他类归为分类2，我们来构造4种SVM，分为以下情况：
 
样本A作为正集，B、C、D作为负集
样本B作为正集，A、C、D作为负集
样本C作为正集，A、B、D作为负集
样本D作为正集，A、B、C作为负集
 
优点： 针对K个分类，需要训练K个分类器，分类速度较快
 
缺点： 训练速度慢，每个分类器需要对全部样本进行训练，而且负样本数量远大于正样本数量，会造成样本不对称情况，而且增加新的非累，需要重新对分类器进行构造。
 
一对一法
 
任意两类样本之间构造一个SVM，这样针对K类的样本，就会有$C(k,2)$类分类器，训练的时候更加灵活。
 
我们划分A、B、C三个类，可以构造3个分类器：
 
分类器：A、B
分类器：A、C
分类器：B、C
 
当对一个未知样本进行分类，每一个分类器有一个分类器结果，为1票，最终得票最多的类就是整个未知样本的类别。
 
优点： 新增一类，不需要重新训练所有的SVM，只需要训练和新增这一类样本的分类器，在训练单个SVM模型的时候，训练速度很快。
 
缺点： 分类器的个数与K的平方成正比，当K较大时，训练和测试的时间会比较慢。

SVM 的推导、特点、优缺点、多分类问题及应用
 作者：keepreder
 SVM有如下主要几个特点：
 
(1) 非线性映射是SVM方法的理论基础,SVM利用内积核函数代替向高维空间的非线性映射；
 
(2) 对特征空间划分的最优超平面是SVM的目标,最大化分类边际的思想是SVM方法的核心；
 
(3) 支持向量是SVM的训练结果,在SVM分类决策中起决定作用的是支持向量。
 
(4) SVM 是一种有坚实理论基础的新颖的小样本学习方法。它基本上不涉及概率测度及大数定律等,因此不同于现有的统计方法。从本质上看,它避开了从归纳到演绎的传统过程,实现了高效的从训练样本到预报样本的“转导推理”,大大简化了通常的分类和回归等问题。
 
(5) SVM 的最终决策函数只由少数的支持向量所确定,计算的复杂性取决于支持向量的数目,而不是样本空间的维数,这在某种意义上避免了“维数灾难”。
 
(6) 少数支持向量决定了最终结果,这不但可以帮助我们抓住关键样本、“剔除”大量冗余样本,而且注定了该方法不但算法简单,而且具有较好的“鲁棒”性。这种“鲁棒”性主要体现在:
 
    ①增、删非支持向量样本对模型没有影响;

    ②支持向量样本集具有一定的鲁棒性;

    ③有些成功的应用中,SVM 方法对核的选取不敏感
 
(7) SVM学习问题可以表示为凸优化问题，因此可以利用已知的有效算法发现目标函数的全局最小值。而其他分类方法（如基于规则的分类器和人工神经网络）都采用一种基于贪心学习的策略来搜索假设空间，这种方法一般只能获得局部最优解。
 
(8) SVM通过最大化决策边界的边缘来控制模型的能力。尽管如此，用户必须提供其他参数，如使用核函数类型和引入松弛变量等。
 
(9) SVM在小样本训练集上能够得到比其它算法好很多的结果。支持向量机之所以成为目前最常用，效果最好的分类器之一，在于其优秀的泛化能力，这是是因为其本身的优化目标是结构化风险最小，而不是经验风险最小，因此，通过margin的概念，得到对数据分布的结构化描述，因此减低了对数据规模和数据分布的要求。SVM也并不是在任何场景都比其他算法好，对于每种应用，最好尝试多种算法，然后评估结果。如SVM在邮件分类上，还不如逻辑回归、KNN、bayes的效果好。
 
(10) 它基于结构风险最小化原则，这样就避免了过学习问题，泛化能力强。
 
(11) 它是一个凸优化问题，因此局部最优解一定是全局最优解的优点。
 
(12) 泛华错误率低，分类速度快，结果易解释
 
不足之处：
 
(1) SVM算法对大规模训练样本难以实施
 SVM的空间消耗主要是存储训练样本和核矩阵，由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。针对以上问题的主要改进有有J.Platt的SMO算法、T.Joachims的SVM、C.J.C.Burges等的PCGC、张学工的CSVM以及O.L.Mangasarian等的SOR算法。
 
    如果数据量很大，SVM的训练时间就会比较长，如垃圾邮件的分类检测，没有使用SVM分类器，而是使用了简单的naive bayes分类器，或者是使用逻辑回归模型分类。
 
(2) 用SVM解决多分类问题存在困难
 经典的支持向量机算法只给出了二类分类的算法，而在数据挖掘的实际应用中，一般要解决多类的分类问题。可以通过多个二类支持向量机的组合来解决。主要有一对多组合模式、一对一组合模式和SVM决策树；再就是通过构造多个分类器的组合来解决。主要原理是克服SVM固有的缺点，结合其他算法的优势，解决多类问题的分类精度。如：与粗集理论结合，形成一种优势互补的多类问题的组合分类器。
 
(3)对缺失数据敏感，对参数和核函数的选择敏感
 支持向量机性能的优劣主要取决于核函数的选取,所以对于一个实际问题而言,如何根据实际的数据模型选择合适的核函数从而构造SVM算法.目前比较成熟的核函数及其参数的选择都是人为的,根据经验来选取的,带有一定的随意性.在不同的问题领域,核函数应当具有不同的形式和参数,所以在选取时候应该将领域知识引入进来,但是目前还没有好的方法来解决核函数的选取问题.
 
支持向量机的主要应用和研究的热点
 目前支持向量机主要应用在模式识别领域中的文本识别,中文分类,人脸识别等;同时也应用到许多的工程技术和信息过滤等方面.
 
    当前研究的热点主要是对支持向量机中算法的优化,包括解决SVM中二次规划求解问题,对大规模SVM的求解问题,对SVM中QP问题的求解问题等.另外就是如何更好的构造基于SVM的多类分类器,如何提高SVM的归纳能力和分类速度等.如何根据实际问题确定核函数也是一个重要的研究热点.