https://blog.csdn.net/qq_29153321/article/details/105299243

除了上篇博客提到的决策树与剪枝、bagging与随机森林、极端随机树、Adaboost、GBDT算法外，还有以下几种算法：

目录

1 KNN

2 贝叶斯分类

3 逻辑回归

4 SVM

KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的某个（些）属性的平均值赋给该样本，就可以得到该样本对应属性的值。

优点

一、 简单、有效。 二、 由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。 三、 该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

缺点

一、 KNN算法是懒散学习方法（lazy learning,基本上不学习），一些积极学习的算法要快很多。 二、该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法（和该样本距离小的邻居权值大）来改进。 三、 计算量较大。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。

贝叶斯定理

朴素贝叶斯分类的思想和工作过程：

      朴素贝叶斯分类的思想真的很朴素，它的思想基础是这样的：对于给出的待分类项，求解此项出现的条件下各个类别出现的概率，哪个最大，就认为此待分类属于哪个类别。

　　朴素贝叶斯分类的工作过程如下：

　　(1)、设D是训练元组和它们相关联的类标号的集合。每个元组用一个n维属性向量X={x1,x2,...,xn}表示。

　　(2)、假定有m个类C1 ,C2,...Cm。给定元组X，分类法将预测X属于具有最高后验概率的类。也就是说，朴素贝叶斯分类法预测X属于类Ci，当且仅当

       　　 P(Ci|X)>P(Cj|X)     1≤j≤m, j≠i

       　　这样，P(Ci|X)最大的类C1称为最大后验概率。根据贝叶斯定理

　　(3)、由于P(X)对所有类为常数，所以只需要P(Ci|X)P(Ci)最大即可。若类的先验概率未知，则通常假定这些类是等概率的，即P(C1)=P(C2)=...=P(Cm)，并据此对P(Ci|X)最大化，否则最大化P(Ci|X)P(Ci)

　　(4)、给定具有很多属性的数据集，计算P(Ci|X)的开销非常大。为了降低计算开销，可以做类条件独立的朴素假定。给定元组的类标号，假定属性值有条件地相互独立。因此，

      　　考察该属性是分类的还是连续值的，例如为了计算P(X|Ci)，考虑如下两种情况：

　　　　(a)、如果Ak是分类属性，则P(xk|Ci)是D中属性A

k的值为xk的Ci类的元组数除以D中Ci类的元组数|Ci,D|

　　　　(b)、如果Ak是连续值属性，则假定连续值属性服从均值为η、标准差为σ的高斯分布，由下式定义：

　　　　即P(xk |Ci)=g(xk,ηci,σci)

　　(5)、为了预测X得类标号，对每个类Ci，计算P(Ci|X)P(Ci)。该分类法预测输入元组X的类为Ci，当且仅当，P(X|Ci)P(Ci)>P(X|Cj)P(Cj)， 1≤j≤m, j≠i。即是，被预测的类标号是使P(X|Ci)P(Ci)最大的类Ci。

拉普拉斯校准（laplace）

　　当P(xk|Ci)=0怎么办，当某个类别下某个特征项没有出现时就出现这种现象，这时会出现的情况是：尽管没有这个零概率，仍然可能得到一个表明X属于Ci类的高概率。有一个简单的技巧来避免该问题，可以假定训练数据库D很大，以至于对每个计数加1造成的估计概率的变化可以忽略不计。但可以方便地避免概率值为0.这种概率估计计数称为拉普拉斯校准或拉普拉斯估计法。

优点

一、 朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。 二、 NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。

缺点

一、 理论上，NBC模型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此，这是因为NBC模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的（可以考虑用聚类算法先将相关性较大的属性聚类），这给NBC模型的正确分类带来了一定影响。在属性个数比较多或者属性之间相关性较大时，NBC模型的分类效率比不上决策树模型。而在属性相关性较小时，NBC模型的性能最为良好。 二、 需要知道先验概率 三、 分类决策存在错误率

逻辑回归解决的是分类问题。LR可以视作单层单节点的“DNN”, 是一种宽而不深的结构，所有的特征直接作用在最后的输出结果上。

逻辑回归损失函数

优点

一、预测结果是界于0和1之间的概率； 二、可以适用于连续性和类别性自变量； 三、容易使用和解释；

缺点

一、对模型中自变量多重共线性较为敏感，例如两个高度相关自变量同时放入模型，可能导致较弱的一个自变量回归符号不符合预期，符号被扭转。​需要利用因子分析或者变量聚类分析等手段来选择代表性的自变量，以减少候选变量之间的相关性； 二、预测结果呈“S”型，因此从log(odds)向概率转化的过程是非线性的，在两端随着​log(odds)值的变化，概率变化很小，边际值太小，slope太小，而中间概率的变化很大，很敏感。 导致很多区间的变量变化对目标概率的影响没有区分度，无法确定阀值。

      Svm（support Vector Mac）又称为支持向量机，是一种二分类的模型。当然如果进行修改之后也是可以用于多类别问题的分类。支持向量机可以分为线性核非线性两大类。其主要思想为找到空间中的一个更够将所有数据样本划开的超平面，并且使得本本集中所有数据到这个超平面的距离最短。

一、基于最大间隔分隔数据

1.1支持向量与超平面

    希望寻找到这样的直线，使得距离这条直线最近的点到这条直线的距离最短。这是可以理解的，因为假如数据样本是随机出现的，那么这样分割之后数据点落入到其类别一侧的概率越高那么最终预测的准确率也会越高。在高维空间中这样的直线称之为超平面，因为当维数大于三的时候我们已经无法想象出这个平面的具体样子。那些距离这个超平面最近的点就是所谓支持向量，实际上如果确定了支持向量也就确定了这个超平面。

                                  图 1                                                 图2

1.2寻找最大间隔

1.2.1点到超平面的距离公式

      既然这样的直线是存在的，那么我们怎样寻找出这样的直线呢？与二维空间类似，超平面的方程也可以写成一下形式：

                                                                                                                                            （1.1）

有了超平面的表达式之后之后，我们就可以计算样本点到平面的距离了。假设为样本的中的一个点，其中表示为第个特征变量。那么该点到超平面的距离就可以用如下公式进行计算：

                                                                         （1.2）

其中||W||为超平面的范数，常数b类似于直线方程中的截距。

上面的公式可以利用解析几何或高中平面几何知识进行推导，这里不做进一步解释。

1.2.2最大间隔的优化模型

    现在我们已经知道了如何去求数据点到超平面的距离，在超平面确定的情况下，我们就能够找出所有支持向量，然后计算出间隔margin。每一个超平面都对应着一个margin，我们的目标就是找出所有margin中最大的那个值对应的超平面。因此用数学语言描述就是确定w、b使得margin最大。这是一个优化问题其目标函数可以写成：

                                                                                        （1.3）

其中表示数据点的标签，且其为-1或1。距离用计算，这是就能体会出-1和1的好处了。如果数据点在平面的正方向(即+1类)那么是一个正数，而当数据点在平面的负方向时(即-1类)，依然是一个正数，这样就能够保证始终大于零了。注意到当w和b等比例放大时，d的结果是不会改变的。因此我们可以令所有支持向量的u为1，而其他点的u大1这是可以办通过调节w和b求到的。因此上面的问题可以简化为： 

                                                                                                    （1.4）

为了后面计算的方便，我们将目标函数等价替换为：

                                                                                                                                （1.5）

这是一个有约束条件的优化问题，通常我们可以用拉格朗日乘子法来求解。拉格朗日乘子法的介绍可以参考这篇博客。应用拉格朗日乘子法如下：

令    

                                                                             （1.6）

求L关于求偏导数得：

                                                                                                    （1.7）

将(1.7)代入到(1.6)中化简得：

                                                       （1.8）

原问题的对偶问题为：

                                                                                              （1.9）

该对偶问题的KKT条件为

                                                                                              （1.10）

到此，似乎问题就能够完美地解决了。但是这里有个假设：数据必须是百分之百可分的。但是实际中的数据几乎都不那么“干净”，或多或少都会存在一些噪点。为此下面我们将引入了松弛变量来解决这种问题。

1.2.3松弛变量

    由上一节的分析我们知道实际中很多样本数据都不能够用一个超平面把数据完全分开。如果数据集中存在噪点的话，那么在求超平的时候就会出现很大问题。从图三中课看出其中一个蓝点偏差太大，如果把它作为支持向量的话所求出来的margin就会比不算入它时要小得多。更糟糕的情况是如果这个蓝点落在了红点之间那么就找不出超平面了。

                                                         图 3

因此引入一个松弛变量ξ来允许一些数据可以处于分隔面错误的一侧。这时新的约束条件变为:

                                                                              （1.11）

式中ξi的含义为允许第i个数据点允许偏离的间隔。如果让ξ任意大的话，那么任意的超平面都是符合条件的了。所以在原有目标的基础之上，我们也尽可能的让ξ的总量也尽可能地小。所以新的目标函数变为：

                                                                                           （1.12）

                                                                         （1.13）

其中的C是用于控制“最大化间隔”和“保证大部分的点的函数间隔都小于1”这两个目标的权重。将上述模型完整的写下来就是：

                                                                       （1.14）

新的拉格朗日函数变为：

                                                       （1.15）

接下来将拉格朗日函数转化为其对偶函数，首先对分别求ξ的偏导，并令其为0,结果如下：

                                                             （1.16）

代入原式化简之后得到和原来一样的目标函数：

                                                                     （1.17）

但是由于我们得到而，因此有所以对偶问题写成：

                                                   （1.18）

经过添加松弛变量的方法，我们现在能够解决数据更加混乱的问题。通过修改参数C，我们可以得到不同的结果而C的大小到底取多少比较合适，需要根据实际问题进行调节。

1.2.4核函数

    以上讨论的都是在线性可分情况进行讨论的，但是实际问题中给出的数据并不是都是线性可分的，比如有些数据可能是如图4样子。

                                                          图4

那么这种非线性可分的数据是否就不能用svm算法来求解呢？答案是否定的。事实上，对于低维平面内不可分的数据，放在一个高维空间中去就有可能变得可分。以二维平面的数据为例，我们可以通过找到一个映射将二维平面的点放到三维平面之中。理论上任意的数据样本都能够找到一个合适的映射使得这些在低维空间不能划分的样本到高维空间中之后能够线性可分。我们再来看一下之前的目标函数：

（1.19）

定义一个映射使得将所有映射到更高维空间之后等价于求解上述问题的对偶问题：

（1.20）

这样对于线性不可分的问题就解决了，现在只需要找出一个合适的映射即可。当特征变量非常多的时候在，高维空间中计算内积的运算量是非常庞大的。考虑到我们的目的并不是为找到这样一个映射而是为了计算其在高维空间的内积，因此如果我们能够找到计算高维空间下内积的公式，那么就能够避免这样庞大的计算量，我们的问题也就解决了。实际上这就是我们要找的核函数，即两个向量在隐式映射后的空间中的内积。下面的一个简单例子可以帮助我们更好地理解核函数。

通过以上例子，我们可以很明显地看到核函数是怎样运作的。上述问题的对偶问题可以写成如下形式：

（1.21）

那么怎样的函数才可以作为核函数呢？下面的一个定理可以帮助我们判断。

Mercer定理：任何半正定的函数都可以作为核函数。其中所谓半正定函数是指拥有训练集数据集合，我们定义一个矩阵的元素，这个矩阵是的矩阵，如果这个矩阵是半正定的，那么就称为半正定函数。

值得注意的是，上述定理中所给出的条件是充分条件而非充要条件。因为有些非正定函数也可以作为核函数。

下面是一些常用的核函数：

                                             表1 常用核函数表

核函数名称

核函数表达式

核函数名称

核函数表达式

线性核

指数核

多项式核

拉普拉斯核

高斯核

Sigmoid核

    现在我们已经了解了一些支持向量机的理论基础，我们通过对偶问题的的转化将最开始求的问题转化为求的对偶问题。只要找到所有的(即找出所有支持向量)，我们就能够确定。然后就可以通过计算数据点到这个超平面的距离从而判断出该数据点的类别。

二、Smo算法原理

2.1 约束条件

     根据以上问题的分析，我们已经将原始问题转化为了求的值，即求下面优化模型的解：

（2.1）

求解的值的方法有很多，Smo算法就是其中一种比较常用的方法。该算法是由John Platt在1996年发布，他的思路是将大的优化问题转化为小的优化问题。而这些小的优化问题往往更容易求解，并且对它们进行顺序求解的结果和将它们作为整体求解的结果完全一致但是Smo算法的时间要小得多。

     Smo算法的原理为：每次任意抽取两个乘子和，然后固定和以外的其它乘子，使得目标函数只是关于和的函数。然后增大其中一个乘子同时减少另外一个。这样，不断的从一堆乘子中任意抽取两个求解，不断的迭代求解子问题，最终达到求解原问题的目的。

     而原对偶问题的子问题的目标函数可以表达成：

（2.2）

其中：

（2.3）

这里之所以算两个是因为的限制，如果只改变其中的一个量，那么这个约束条件可能就不成立了。要解决这个问题，我们必须得选取这样的两个乘子。那么怎样确定这样的和呢？这是我们首先要考虑的问题，在《机器学习实战》这本书中，作者首先给出了一种简化版的方法，遍历每一个然后在剩余的中随机选取一个进行优化。虽然样也能够解决问题，但是运算量太大，因此考虑找一种更好的方法来寻找对。

为了表述方便，定义一个特征到输出结果的输出函数：

（2.4）

该对偶问题中KKT条件为：

（2.5）

根据上述问题的KKT条件可以得出目标函数中的的含义如下：

1、 ，表明是正常分类，在边界外；

2、，表明是支持向量，在边界上；

3、，表明在两边界之间。

最优解需要满足KKT条件，因此需要满足以上的三个条件都满足。而不满足这三个条件的情况也有三种：

1、0则是不满足的，而原本=0;

3、=1但是=0或者=C则表明不满足的，而原本应该是0