：从分类平面，到求两类间的最大间隔，到转化为求间隔分之一，等优化问题，然后就是优化问题的解决办法，首先是用拉格拉日乘子把约束优化转化为无约束优化，对各个变量求导令其为零，得到的式子带入拉格朗日式子从而转化为对偶问题 ， 最后再利用SMO（序列最小优化）来解决这个对偶问题。 
C>0称为惩罚参数，一般事先由应用问题决定， 控制目标函数中两项 （“寻找 margin最大的超平面”和“保证数据点偏差量最小”）之间的权重，C越大时对误分类的惩罚增大，C值小时对误分类的惩罚减小。最小化目标函数包含两层含义：使
尽量小即间隔尽量大，同时使误分类点的个数尽量小，C是调和二者的系数。
2、SVM的推导，解释原问题和对偶问题，SVM原问题和对偶问题的关系，KKT限制条件，KKT条件用哪些，完整描述；软间隔问题，解释支持向量、核函数（哪个地方引入、画图解释高维映射，高斯核可以升到多少维，如何选择核函数），引入拉格朗日的优化方法的原因，最大的特点，损失函数解释
目标函数对原始问题是极大化,对偶问题则是极小化
原始问题目标函数中的收益系数（优化函数中变量前面的系数）是对偶问题约束不等式中的右端常数,而原始问题约束不等式中的右端常数则是对偶问题中目标函数的收益系数
原始问题和对偶问题的约束不等式的符号方向相反
原始问题约束不等式系数矩阵转置后即为对偶问题的约束不等式的系数矩阵
原始问题的约束方程数对应于对偶问题的变量数,而原始问题的变量数对应于对偶问题的约束方程数
对偶问题的对偶问题是原始问题
- 对偶问题将原始问题中的约束转为了对偶问题中的等式约束
- 方便核函数的引入
- 改变了问题的复杂度。由求特征向量w转化为求比例系数a，在原始问题下，求解的复杂度与样本的维度有关，即w的维度。在对偶问题下，只与样本数量有关。
- 求解更高效，因为只用求解比例系数a，而比例系数a只有支持向量才为非0，其他全为0.
1、当我们在解决线性不可分的问题时，我们需要通过一个映射函数，把样本值映射到更高维的空间或者无穷维 。在特征空间中，我们对线性可分的新样本使用前面提到过的求解线性可分的情况下的分类问题的方法时，需要计算样本内积，但是因为样本维数很高，容易造成“维数灾难”，所以这里我们就引入了核函数，把高维向量的内积转变成了求低维向量的内积问题。 2、内积的作用，内积也是可以衡量相似度的！分类问题就是一个找相似样本的过程，你跟我相似，你就属于我这个类，所以在求出的目标函数中会出现内积，可以用这个原理来理解 。内积是可以衡量两个向量的相似度的，例如，我们常常可以通过两个相量的距离和夹角来表示相似度，这些属性都可以通过两个向量的内积值来获得。
高斯核就是把每个数据都看做是一个基准然后分别计算所有数据与这个基准之间的高斯函数。这样如果原始数据维度是2，有n条数据，就成功的把一个2维的向量升到了n维。
那么为什么说高斯核函数能将数据映射到无穷维度空间呢？
“如果映射后空间是k维的话，那内积矩阵的秩最大是k。而任给n个互不重合的样本， Gaussian kernel的内积矩阵都是满秩的。所以你无论假设k是多少，都能找到n>k，矛 盾，所以必须是无限维的。 ”
意思是说，我现在有n条数据，那么我把k维成功升到了n维，你告诉我说高斯核函数能把数据集升到n维。这个时候我再给你加一条新的与原始数据不重合的样本，那么数据就可以映射到n+1维空间，与之前结论矛盾，因此，高斯核函数能将数据升到无穷维。
好处是：vc维提升（线性分类器的vc维是n+1,如果升到无穷维，则是vc维也是无穷的），即总能找到一个分类面将数据集很好的分开。vc维代表了分类能力。即在使用SVM的时候，只要C选的足够大，就可以保证拟合的很好，甚至是过拟合。
最常用的是Linear核与RBF核。
- Linear核：主要用于线性可分的情形。参数少，速度快，对于一般数据，分类效果已经很理想了。
- RBF核：主要用于线性不可分的情形。参数多，分类结果非常依赖于参数。有很多人是通过训练数据的交叉验证来寻找合适的参数，不过这个过程比较耗时。 个人体会：使用libsvm，默认参数，RBF核比Linear核效果稍差。通过进行大量参数的尝试，一般能找到比linear核更好的效果。
至于到底该采用哪种核，要根据具体问题，有的数据是线性可分的，有的不可分，需要多尝试不同核不同参数。如果特征的提取的好，包含的信息量足够大，很多问题都是线性可分的。当然，如果有足够的时间去寻找RBF核参数，应该能达到更好的效果。
优点：
(1)非线性映射是SVM方法的理论基础,SVM利用内积核函数代替向高维空间的非线性映射；
(2)对特征空间划分的最优超平面是SVM的目标,最大化分类边际的思想是SVM方法的核心；
(3)支持向量是SVM的训练结果,在SVM分类决策中起决定作用的是支持向量。
(4)SVM 是一种有坚实理论基础的新颖的小样本学习方法。它基本上不涉及概率测度及大数定律等,因此不同于现有的统计方法。从本质上看,它避开了从归纳到演绎的传统过程,实现了高效的从训练样本到预报样本的“转导推理”,大大简化了通常的分类和回归等问题。
(5)SVM 的最终决策函数只由少数的支持向量所确定,计算的复杂性取决于支持向量的数目,而不是样本空间的维数,这在某种意义上避免了“维数灾难”。
(6)少数支持向量决定了最终结果,这不但可以帮助我们抓住关键样本、“剔除”大量冗余样本,而且注定了该方法不但算法简单,而且具有较好的“鲁棒”性。这种“鲁棒”性主要体现在:
缺点：
(1) SVM算法对大规模训练样本难以实施
由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。针对以上问题的主要改进有有J.Platt的SMO算法、T.Joachims的SVM、C.J.C.Burges等的PCGC、张学工的CSVM以及O.L.Mangasarian等的SOR算法
(2) 用SVM解决多分类问题存在困难
经典的支持向量机算法只给出了二类分类的算法，而在数据挖掘的实际应用中，一般要解决多类的分类问题。可以通过多个二类支持向量机的组合来解决。主要有一对多组合模式、一对一组合模式和SVM决策树；再就是通过构造多个分类器的组合来解决。主要原理是克服SVM固有的缺点，结合其他算法的优势，解决多类问题的分类精度。如：与粗集理论结合，形成一种优势互补的多类问题的组合分类器。
(3)对缺失数据敏感，对参数和核函数的选择敏感 支持向量机性能的优劣主要取决于核函数的选取,所以对于一个实际问题而言,如何根据实际的数据模型选择合适的核函数从而构造SVM算法.目前比较成熟的核函数及其参数的选择都是人为的,根据经验来选取的,带有一定的随意性.在不同的问题领域,核函数应当具有不同的形式和参数,所以在选取时候应该将领域知识引入进来,但是目前还没有好的方法来解决核函数的选取问题.
两种方法线性划分两类事物时得到的线性分类器效果差不多。那具体的差别在哪呢？
SVM更关心的是靠近中间分割线的点，让他们尽可能地远离中间线，而不是在所有点上达到最优，因为那样的话，要使得一部分点靠近中间线来换取另外一部分点更加远离中间线。因此支持向量机和和逻辑斯蒂回归的不同点，一个是考虑局部（不关心已经确定远离的点，更考虑靠近中间分割线的点），一个是考虑全局（已经远离的点可能通过调整中间线使其能够更加远离）
这两个损失函数的目的都是增加对分类影响较大的数据点的权重，减少与分类关系较小的数据点的权重。SVM的处理方法是只考虑support vectors，也就是和分类最相关的少数点，去学习分类器。而逻辑回归通过非线性映射，大大减小了离分类平面较远的点的权重，相对提升了与分类最相关的数据点的权重,两者的根本目的都是一样的。
LR采用log损失，SVM采用合页损失。 LR对异常值敏感，SVM对异常值不敏感。 在训练集较小时，SVM较适用，而LR需要较多的样本。 LR模型找到的那个超平面，是尽量让所有点都远离他，而SVM寻找的那个超平面，是只让最靠近中间分割线的那些点尽量远离，即只用到那些支持向量的样本。 对非线性问题的处理方式不同，LR主要靠特征构造，必须组合交叉特征，特征离散化。SVM也可以这样，还可以通过kernel。 svm 更多的属于非参数模型，而logistic regression 是参数模型，本质不同。其区别就可以参考参数模型和非参模型的区别 怎么根据特征数量和样本量来选择SVM和LR模型呢：
如果Feature的数量很大，跟样本数量差不多，这时候选用LR或者是Linear Kernel的SVM 如果Feature的数量比较小，样本数量一般，不算大也不算小，选用SVM+Gaussian Kernel 如果Feature的数量比较小，而样本数量很多，需要手工添加一些feature变成第一种情况。(LR和不带核函数的SVM比较类似。)
因为原问题是凸二次规划问题，转换为对偶问题更加高效。为什么求解对偶问题更加高效？因为只用求解alpha系数，而alpha系数只有支持向量才非0，其他全部为0. alpha系数有多少个？样本点的个数
对偶问题将原始问题中的约束转为了对偶问题中的等式约束 方便核函数的引入 改变了问题的复杂度。由求特征向量w转化为求比例系数a，在原始问题下，求解的复杂度与样本的维度有关，即w的维度。在对偶问题下，只与样本数量有关。 求解更高效，因为只用求解比例系数a，而比例系数a只有支持向量才为非0，其他全为0.
SVM本质上是凸优化问题，如果增加的样本点只是无效约束，并不会影响其最后的结果。这也就是为什么SVM适合于小样本量数据集的原因。
随样本量而使模型自身发生改变的，是统计推断。最大似然，MAP，再到贝叶斯，每个都涉及到样本数prod的一项，这些方法建立的模才真正和样本数量有最直接的联系。
SVM如何解决多分类问题：
一对多法。训练时依次把某个类别的样本归为一类,其他剩余的样本归为另一类，这样k个类别的样本就构造出了k个SVM。分类时将未知样本分类为具有最大分类函数值的那类。
一对一法。其做法是在任意两类样本之间设计一个SVM，因此k个类别的样本就需要设计k(k-1)/2个SVM。当对一个未知样本进行分类时，最后得票最多的类别即为该未知样本的类别。Libsvm中的多类分类就是根据这个方法实现的。
层次支持向量机（H-SVMs）。层次分类法首先将所有类别分成两个子类，再将子类进一步划分成两个次级子类，如此循环，直到得到一个单独的类别为止。
支持向量回归 SVR：
1、贝叶斯分类器
优点：
同时具备接收大数据量训练和查询时具备高速度的特点 具有支持增量式训练的能力（不借助于旧有训练数据，每一组新的训练数据都有可能引起概率值的变化，而如决策树和支持向量机，则需要我们一次性将整个数据集都传给它们。） 对贝叶斯分类器实际学习状况的解释相对简单。 缺点：
无法处理基于特征值组合所产生的变化结果。例如：“在线”和“药店”分开出现时一般出现在正常邮件中，但当组合起来时“在线药店”却一般出现在垃圾邮件中，贝叶斯分类器无法理解这种特征组合。
2、决策树分类器
优点:
利用决策树可以很容易的解释一个受训模型，而且算法将最重要的判断因素很好的安排在了靠近树的根部位置。 决策树能找到能使信息增益达到最大化的分界线，因此它能够同时处理分类数据和数值数据。 与贝叶斯分类器相比，它能够很容易地处理变量之间的相互影响。 缺点：
不支持向量式训练，每次训练都要从头开始。
3、神经网络
优点：
能够处理复杂的非线性函数，并且能发现不同输入之间的依赖关系。 允许增量式训练 缺点：
神经网络是一种黑盒方法，无法确知推导过程。 在选择训练数据的比率及与问题相适应的网络规模方面，并没有明确的规则可以遵循。
4、支持向量机
优点：
在对新的观测数据进行分类时速度极快，因为支持向量机分类时只需判断坐标点位于分界线的哪一侧即可。 通过将分类输入转换成数值输入，可以令支持向量机同时支持分类数据和数值数据。 缺点：
针对每个数据集的最佳核变换函数及其相应的参数都是不一样的，而且每当遇到新的数据集时都必须重新确定这些函数及参数。 和神经网络一样，SVM也是一种黑盒技术，实际上，由于存在向高维空间的变换，SVM的分类过程甚至更加难于解释。
5、k-最近邻算法
优点：
能够利用复杂函数进行数值预测，同时又保持简单易懂的特点 合理的数据缩放量不但可以改善预测的效果，而且还可以告诉我们预测过程中各个变量的重要程度。 KNN是一种在线（online）技术，这意味着新的数据可以在任何时候被添加进来，而不需要进行任何的计算。 缺点：
为了完成预测，它要求所有的训练数据都必须缺一不可，为了找到最为接近的数据项，每一项待预测的数据必须和其他数据项进行比较，会产出极大的数据计算量。 寻找合理的缩放因子并不是那么简单。 SVM的速度：
SVM训练速度慢，主要是因为大量的非支持向量参与训练过程，从而进行了大量的二次规划计算，导致分类计算量大、分类速度慢。
但是在对新的观测数据进行分类时速度极快，因为支持向量机分类时只需判断坐标点位于分界线的哪一侧即可。
https://www.zhihu.com/question/24627666
核函数的作用：
1、当我们在解决线性不可分的问题时，我们需要通过一个映射函数，把样本值映射到更高维的空间或者无穷维。在特征空间中，我们对线性可分的新样本使用前面提到过的求解线性可分的情况下的分类问题的方法时，需要计算样本内积，但是因为样本维数很高，容易造成“维数灾难”，所以这里我们就引入了核函数，把高维向量的内积转变成了求低维向量的内积问题。 2、内积的作用，内积也是可以衡量相似度的！分类问题就是一个找相似样本的过程，你跟我相似，你就属于我这个类，所以在求出的目标函数中会出现内积，可以用这个原理来理解。内积是可以衡量两个向量的相似度的，例如，我们常常可以通过两个相量的距离和夹角来表示相似度，这些属性都可以通过两个向量的内积值来获得。
核函数只是用来计算映射到高维空间之后的内积的一种简便方法。
https://www.zhihu.com/question/19591450
对于基于支持向量机的大规模线性分类问题，目前已经能比较好地解决。
对于非线性分类问题，基于SMO方法的SVM-Light和LibSVM目前仍被广泛使用，他们最坏情况下复杂度是O(m^2)，并不适合在大规模数据集上做训练。不过在我接触过的应用场景里（比如对象检测），非线性SVM的最大问题不是训练时代价问题，而是检测时代价太高。
https://www.zhihu.com/question/30123068
https://www.zhihu.com/question/26726794
没有最好的分类器，只有最合适的分类器。
随机森林平均来说最强，但也只在9.9%的数据集上拿到了第一，优点是鲜有短板。
SVM的平均水平紧随其后，在10.7%的数据集上拿到第一。
神经网络（13.2%）和boosting（~9%）表现不错。
数据维度越高，随机森林就比AdaBoost强越多，但是整体不及SVM[2]。
数据量越大，神经网络就越强。
KNN，它的思路就是——对于待判断的点，找到离它最近的几个数据点，根据它们的类型决定待判断点的类型。
它的特点是完全跟着数据走，没有数学模型可言。
适用情景：需要一个特别容易解释的模型的时候。比如需要向用户解释原因的推荐算法。
贝叶斯：
典型的例子是Naive Bayes，核心思路是根据条件概率计算待判断点的类型。
是相对容易理解的一个模型，至今依然被垃圾邮件过滤器使用。
适用情景：
需要一个比较容易解释，而且不同维度之间相关性较小的模型的时候。
可以高效处理高维数据，虽然结果可能不尽如人意。
决策树的特点是它总是在沿着特征做切分。随着层层递进，这个划分会越来越细。
虽然生成的树不容易给用户看，但是数据分析的时候，通过观察树的上层结构，能够对分类器的核心思路有一个直观的感受。举个简单的例子，当我们预测一个孩子的身高的时候，决策树的第一层可能是这个孩子的性别。男生走左边的树进行进一步预测，女生则走右边的树。这就说明性别对身高有很强的影响。
适用情景：
因为它能够生成清晰的基于特征(feature)选择不同预测结果的树状结构，数据分析师希望更好的理解手上的数据的时候往往可以使用决策树。
同时它也是相对容易被攻击的分类器。这里的攻击是指人为的改变一些特征，使得分类器判断错误。常见于垃圾邮件躲避检测中。因为决策树最终在底层判断是基于单个条件的，攻击者往往只需要改变很少的特征就可以逃过监测。
受限于它的简单性，决策树更大的用处是作为一些更有用的算法的基石。
随机森林。严格来说，随机森林其实算是一种集成算法。它首先随机选取不同的特征(feature)和训练样本(training sample)，生成大量的决策树，然后综合这些决策树的结果来进行最终的分类。
随机森林在现实分析中被大量使用，它相对于决策树，在准确性上有了很大的提升，同时一定程度上改善了决策树容易被攻击的特点。
适用情景：
数据维度相对低（几十维），同时对准确性有较高要求时。
因为不需要很多参数调整就可以达到不错的效果，基本上不知道用什么方法的时候都可以先试一下随机森林。
SVM的核心思想就是找到不同类别之间的分界面，使得两类样本尽量落在面的两边，而且离分界面尽量远。
最早的SVM是平面的，局限很大。但是利用核函数，我们可以把平面投射成曲面，进而大大提高SVM的适用范围。
提高之后的SVM同样被大量使用，在实际分类中展现了很优秀的正确率。
适用情景：
SVM在很多数据集上都有优秀的表现。
相对来说，SVM尽量保持与样本间距离的性质导致它抗攻击的能力更强。
LR，它其实是回归类方法的一个变体。
回归方法的核心就是为函数找到最合适的参数，使得函数的值和样本的值最接近。例如线性回归(Linear regression)就是对于函数f(x)=ax+b，找到最合适的a,b。
LR拟合的就不是线性函数了，它拟合的是一个概率学中的函数，f(x)的值这时候就反映了样本属于这个类的概率。
适用情景：
LR同样是很多分类算法的基础组件，它的好处是输出值自然地落在0到1之间，并且有概率意义。
因为它本质上是一个线性的分类器，所以处理不好特征之间相关的情况。
虽然效果一般，却胜在模型清晰，背后的概率学经得住推敲。它拟合出来的参数就代表了每一个特征(feature)对结果的影响。也是一个理解数据的好工具。
线性判别分析(Linear discriminant analysis)，简称LDA。
LDA的核心思想是把高维的样本投射(project)到低维上，如果要分成两类，就投射到一维。要分三类就投射到二维平面上。这样的投射当然有很多种不同的方式，LDA投射的标准就是让同类的样本尽量靠近，而不同类的尽量分开。对于未来要预测的样本，用同样的方式投射之后就可以轻易地分辨类别了。
使用情景：
判别分析适用于高维数据需要降维的情况，自带降维功能使得我们能方便地观察样本分布。它的正确性有数学公式可以证明，所以同样是很经得住推敲的方式。
但是它的分类准确率往往不是很高，所以不是统计系的人就把它作为降维工具用吧。
同时注意它是假定样本成正态分布的，所以那种同心圆形的数据就不要尝试了。
神经网络 (Neural network)
它的核心思路是利用训练样本来逐渐地完善参数。还是举个例子预测身高的例子，如果输入的特征中有一个是性别（1:男；0:女），而输出的特征是身高（1:高；0:矮）。那么当训练样本是一个个子高的男生的时候，在神经网络中，从“男”到“高”的路线就会被强化。同理，如果来了一个个子高的女生，那从“女”到“高”的路线就会被强化。
最终神经网络的哪些路线比较强，就由我们的样本所决定。
神经网络的优势在于，它可以有很多很多层。如果输入输出是直接连接的，那它和LR就没有什么区别。但是通过大量中间层的引入，它就能够捕捉很多输入特征之间的关系。卷积神经网络有很经典的不同层的可视化展示(visulization)，我这里就不赘述了。
神经网络的提出其实很早了，但是它的准确率依赖于庞大的训练集，原本受限于计算机的速度，分类效果一直不如随机森林和SVM这种经典算法。
使用情景：
数据量庞大，参数之间存在内在联系的时候。
当然现在神经网络不只是一个分类器，它还可以用来生成数据，用来做降维，这些就不在这里讨论了。
提升算法（Boosting）
接下来讲的一系列模型，都属于集成学习算法(Ensemble Learning)，基于一个核心理念：当我们把多个较弱的分类器结合起来的时候，它的结果会比一个强的分类器更好。
典型的例子是AdaBoost。AdaBoost的实现是一个渐进的过程，从一个最基础的分类器开始，每次寻找一个最能解决当前错误样本的分类器。用加权取和(weighted sum)的方式把这个新分类器结合进已有的分类器中。
它的好处是自带了特征选择（feature selection），只使用在训练集中发现有效的特征(feature)。这样就降低了分类时需要计算的特征数量，也在一定程度上解决了高维数据难以理解的问题。
最经典的AdaBoost实现中，它的每一个弱分类器其实就是一个决策树。这就是之前为什么说决策树是各种算法的基石。
使用情景：
好的Boosting算法，它的准确性不逊于随机森林。实际使用中它还是很强的。因为自带特征选择（feature selection）所以对新手很友好，是一个“不知道用什么就试一下它吧”的算法。
装袋算法（Bagging）
同样是弱分类器组合的思路，相对于Boosting，其实Bagging更好理解。它首先随机地抽取训练集，以之为基础训练多个弱分类器。然后通过取平均，或者投票(voting)的方式决定最终的分类结果。
因为它随机选取训练集的特点，Bagging可以一定程度上避免过渡拟合(overfit)。
在[1]中，最强的Bagging算法是基于SVM的。如果用定义不那么严格的话，随机森林也算是Bagging的一种。
使用情景：
相较于经典的必使算法，Bagging使用的人更少一些。一部分的原因是Bagging的效果和参数的选择关系比较大，用默认参数往往没有很好的效果。
虽然调对参数结果会比决策树和LR好，但是模型也变得复杂了，没事有特别的原因就别用它了。
最大熵模型 (Maximum entropy model)
最大熵模型本身不是分类器，它一般是用来判断模型预测结果的好坏的。
对于它来说，分类器预测是相当于是：针对样本，给每个类一个出现概率。比如说样本的特征是：性别男。我的分类器可能就给出了下面这样一个概率：高（60%），矮（40%）。
而如果这个样本真的是高的，那我们就得了一个分数60%。最大熵模型的目标就是让这些分数的乘积尽量大。
LR其实就是使用最大熵模型作为优化目标的一个算法[4]。
隐马尔科夫 (Hidden Markov model)
这是一个基于序列的预测方法，核心思想就是通过上一个（或几个）状态预测下一个状态。
之所以叫“隐”马尔科夫是因为它的设定是状态本身我们是看不到的，我们只能根据状态生成的结果序列来学习可能的状态。
适用场景：
本文地址：http://xiaoguoguo.dbeile.cn/quote/1465.html 多贝乐 http://xiaoguoguo.dbeile.cn/ , 查看更多