常用机器学习算法汇总比较(完）

机器学习入门系列（2）--如何构建一个完整的机器学习项目，第九篇！

该系列的前八篇文章：

• 机器学习入门系列(2)--如何构建一个完整的机器学习项目(一)
• 机器学习数据集的获取和测试集的构建方法
• 特征工程之数据预处理（上）
• 特征工程之数据预处理（下）
• 特征工程之特征缩放&特征编码
• 特征工程(完)
• 常用机器学习算法汇总比较(上）
• 常用机器学习算法汇总比较(中）

常用机器学习算法汇总比较的最后一篇，介绍提升(Boosting)算法、GBDT、优化算法和卷积神经网络的基本原理、优缺点。

9. 提升(Boosting)方法

简述

提升方法(boosting)是一种常用的统计学习方法，在分类问题中，它通 过改变训练样本的权重，学习多个分类器 ，并将这些分类器进行线性组合，提供分类的性能。

boosting 和 bagging

boosting 和 bagging 都是集成学习（ensemble learning）领域的基本算法， 两者使用的多个分类器的类型是一致的 。

Bagging

bagging也叫 自助汇聚法（bootstrap aggregating） ，比如原数据集中有 N 个样本，我们每次从原数据集中 有放回 的抽取，抽取 N 次，就得到了一个新的有 N 个样本的数据集，然后我们抽取 S 个 N 次，就得到了 S 个有 N 个样本的新数据集，然后拿这 S 个数据集去训练 S 个分类器，之后应用这 S 个分类器进行分类，选择分类器 投票最多的类别 作为最后的分类结果。一般来说 自助样本的包含有 63% 的原始训练数据 ，因为：

假设共抽取 N 个样本，则 N 次都没有抽到的概率是

则一个样本被抽到的概率有

所以，当 N 很大时有： 。

这样，在一次 bootstrap 的过程中，会有 36% 的样本没有被采样到，它们被称为 out-off-bag(oob) ，这是自助采样带给 bagging 的里一个优点，因为我们可以用 oob 进行**“包外估计”(out-of-bag estimate)**。

bagging 通过降低基分类器的方差改善了泛化误差，bagging 的性能依赖于基分类器的稳定性。如果基分类器是 不稳定 的，bagging 有助于减少训练数据的随机波动导致的误差 ，如果基分类器是稳定的，即对训练数据集中的微小变化是鲁棒的，则组合分类器的误差主要由 基分类器偏移 所引起的，这种情况下， bagging 可能不会对基分类器有明显的改进效果，甚至可能降低分类器的性能。

boosting 与 bagging 的区别

• bagging 通过 有放回的抽取 得到了 S 个数据集，而 boosting 用的始终是 原数据集 ，但是 样本的权重会发生改变。
• boosting 对分类器的训练是串行的 ，每个新分类器的训练都会受到上一个分类器分类结果的影响。
• bagging 里面各个分类器的权重是相等的，但是 boosting 不是 ，每个分类器的权重代表的是其对应分类器在上一轮分类中的成功度。

AdaBoost 是 boosting 方法中最流行的版本

AdaBoost 算法

AdaBoost（adaptive boosting）是元算法，通过组合多个弱分类器来构建一个强分类器。

我们为训练数据中的每一个样本都赋予其一个权重，这些权重构成了向量 D，一开始，这些权重都初始化成相等值，然后每次添加一个弱分类器对样本进行分类，从第二次分类开始， 将上一次分错的样本的权重提高，分对的样本权重降低，持续迭代 。

此外，对于每个弱分类器而言， 每个分类器也有自己的权重，取决于它分类的加权错误率，加权错误率越低，则这个分类器的权重值 α 越高 ，最后综合多个弱分类器的分类结果和其对应的权重 α 得到预测结果，AdaBoost 是最好的监督学习分类方法之一。

优缺点

优点

1. 泛化误差低
2. 容易实现，分类准确率较高，没有太多参数可以调

缺点

• 对异常值比较敏感
• 训练时间过长
• 执行效果依赖于弱分类器的选择

10. GBDT

简述

GBDT 是一个 基于迭代累加的决策树算法 ，它通过构造一组弱的学习器（树），并把多颗决策树的结果累加起来作为最终的预测输出。

GBDT中的树是回归树，不是分类树。

随机森林(Random Forest，RF) 与 GBDT 对比

1. RF 中树的棵树是 并行 生成的；GBDT 中树是 顺序 生成的；两者中过多的树都会过拟合，但是 GBDT 更容易过拟合
2. RF 中每棵树分裂的特征 比较随机 ；GBDT 中前面的树优先分裂对大部分样本区分的特征，后面的树分裂对小部分样本区分特征
3. RF 中主要参数是 树的棵数 ；GBDT 中主要参数是 树的深度，一般为1

优缺点

优点

LogLoss

缺点

1. boosting 是个串行的过程，所以并行麻烦，需要考虑上下树之间的联系
2. 计算复杂度大
3. 不使用高维稀疏特征

调参

1. 树的个数 100~10000
2. 叶子的深度 3~8
3. 学习速率 0.01~1
4. 叶子上最大节点树 20
5. 训练采样比例 0.5~1
6. 训练特征采样比例

xgboost

xgboost 是 boosting Tree 的一个很牛的实现，它在 Kaggle 比赛中大放异彩。它有以下几个优良的特性：

1. 显示的把树模型复杂度作为正则项加到优化目标中。
2. 公式推导中用到了二阶导数，用了二阶泰勒展开。
3. 实现了分裂点寻找近似算法。
4. 利用了特征的稀疏性。
5. 数据事先 排序 并且以 block 形式存储，有利于并行计算。
6. 基于分布式通信框架 rabit，可以运行在 MPI 和 yarn 上。（最新已经不基于 rabit 了）
7. 实现做了面向体系结构的优化，针对 cache 和内存做了性能优化。

在项目实测中使用发现，Xgboost 的训练速度要远远快于传统的 GBDT 实现，10 倍量级。

代码实现

下面给出简单使用 xgboost 这个框架的例子。

# 划分数据集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.01, random_state=1729)
print(X_train.shape, X_test.shape)

#模型参数设置
xlf = xgb.XGBRegressor(max_depth=10, 
                        learning_rate=0.1, 
                        n_estimators=10, 
                        silent=True, 
                        objective='reg:linear', 
                        nthread=-1, 
                        gamma=0,
                        min_child_weight=1, 
                        max_delta_step=0, 
                        subsample=0.85, 
                        colsample_bytree=0.7, 
                        colsample_bylevel=1, 
                        reg_alpha=0, 
                        reg_lambda=1, 
                        scale_pos_weight=1, 
                        seed=1440, 
                        missing=None)

xlf.fit(X_train, y_train, eval_metric='rmse', verbose = True, eval_set = [(X_test, y_test)],early_stopping_rounds=100)

# 计算 auc 分数、预测
preds = xlf.predict(X_test)
复制代码

11. 优化算法

常见的最优化方法有梯度下降法、牛顿法和拟牛顿法、共轭梯度法等等

梯度下降法

梯度下降法是最早最简单，也是最为常用的最优化方法。

梯度下降法实现简单， 当目标函数是凸函数时，梯度下降法的解是全局解 。

一般情况下，其解 不保证是全局最优解 ，梯度下降法的速度也未必是最快的。

梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快下降方向，所以也被称为是”最速下降法“。最速下降法越接近目标值，步长越小，前进越慢。

梯度下降法的搜索迭代示意图如下图所示：

其缺点是：

（1）靠近极小值时收敛速度减慢，如下图所示；

（2）直线搜索时可能会产生一些问题；

（3）可能会“之字形”地下降。

从上图可以看出，梯度下降法在接近最优解的区域收敛速度明显变慢，利用梯度下降法求解需要很多次的迭代。

在机器学习中，基于基本的梯度下降法发展了三种梯度下降方法：

1. 批量梯度下降法：每次迭代都会采用整个训练集
2. 随机梯度下降法：每次迭代随机使用一个训练样本
3. 小批量梯度下降法：每次迭代采用一个小型的训练子集

其中小批量梯度下降法是前两种方法的一个折中，也是目前最常用的梯度下降法，它即避免了批量梯度下降法需要计算整个训练集的缺点，也不会像随机梯度下降法一样会出现训练震荡，不稳定的缺点。当然，它相比前两种方法的缺点就是比较容易陷入局部最小值中。

牛顿法

牛顿法是一种在实数域和复数域上近似求解方程的方法。方法使用函数 f(x) 的泰勒级数的前面几项来寻找方程 f(x) = 0 的根。

它是二阶算法，它使用了 Hessian 矩阵求权重的二阶偏导数，目标是采用损失函数的二阶偏导数寻找更好的训练方向。

牛顿法最大的特点就在于它的收敛速度很快。

牛顿法是基于当前位置的切线来确定下一次的位置，所以牛顿法又被很形象地称为是"切线法"。牛顿法的搜索路径（二维情况）如下图所示：

牛顿法搜索动态示例图：

关于牛顿法和梯度下降法的效率对比：

• 从本质上去看， 牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快 。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时， 不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大 。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。（牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。）
• 根据 wiki上的解释， 从几何上说，牛顿法就是用一个二次曲面去拟合当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面 ，通常情况下， 二次曲面的拟合会比平面更好 ，所以牛顿法选择的下降路径会更符合真实的最优下降路径。

注：红色的牛顿法的迭代路径，绿色的是梯度下降法的迭代路径。

优缺点

优点

二阶收敛，收敛速度快；

缺点

1. Hessian 矩阵（海森矩阵的逆）计算量较大，当问题规模较大时，不仅计算量大而且需要的存储空间也多，因此牛顿法在面对海量数据时由于每一步迭代的开销巨大而变得不适用；
2. 牛顿法在每次迭代时不能总是保证海森矩阵是正定的，一旦海森矩阵不是正定的，优化方向就会“跑偏”，从而使得牛顿法失效，也说明了牛顿法的鲁棒性较差。

拟牛顿法

拟牛顿法的本质思想是改善牛顿法每次需要求解复杂的 Hessian 矩阵的逆矩阵的缺陷，它使用正定矩阵来近似 Hessian 矩阵的逆，从而简化了运算的复杂度。

拟牛顿法和最速下降法一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。

另外， 因为拟牛顿法不需要二阶导数的信息，而是在每次迭代的时候计算一个矩阵，其逼近海塞矩阵的逆。最重要的是，该逼近值只是使用损失函数的一阶偏导来计算 ，所以有时比牛顿法更为有效。

如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。

共轭梯度法(Conjugate Gradient)

共轭梯度法是介于最速下降法与牛顿法之间的一个方法，**它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，**共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。在各种优化算法中，共轭梯度法是非常重要的一种。 其优点是所需存储量小，具有收敛快，稳定性高，而且不需要任何外来参数。

在共轭梯度训练算法中，因为是沿着 共轭方向（conjugate directions）执行搜索的 ，所以通常该算法要比沿着梯度下降方向优化收敛得更迅速。共轭梯度法的训练方向是与海塞矩阵共轭的。

共轭梯度法已经证实其在神经网络中要比梯度下降法有效得多。并且由于共轭梯度法并没有要求使用海塞矩阵，所以在大规模神经网络中其还是可以做到很好的性能。

启发式优化方法

启发式方法指人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案。启发式优化方法种类繁多，包括经典的模拟退火方法、遗传算法、蚁群算法以及粒子群算法等等。

还有一种特殊的优化算法被称之多目标优化算法，它主要针对同时优化多个目标（两个及两个以上）的优化问题，这方面比较经典的算法有 NSGAII 算法、MOEA/D 算法以及人工免疫算法等。

解决约束优化问题--拉格朗日乘数法

这个方法可以参考文章拉格朗日乘数法

Levenberg-Marquardt 算法

Levenberg-Marquardt 算法，也称之为衰减最小二乘法（damped least-squares method），该算法的损失函数采用平方误差和的形式。 该算法的执行也不需要计算具体的海塞矩阵，它仅仅只是使用梯度向量和雅可比矩阵（Jacobian matrix）。

Levenberg-Marquardt 算法是 为平方误差和函数所定制的 。这就让使用这种误差度量的神经网络训练地十分迅速。然而 Levenberg-Marquardt 算法还有一些缺点：

• 不能用于平方根误差或交叉熵误差（cross entropy error）等函数，
• 该算法还和正则项不兼容。
• 最后，对于大型数据集或神经网络，雅可比矩阵会变得十分巨大，因此也需要大量的内存。所以我们在大型数据集或神经网络中并不推荐采用 Levenberg-Marquardt 算法。

内存与收敛速度的比较

下图展示了所有上文所讨论的算法，及其收敛速度和内存需求。其中收敛速度最慢的是梯度下降算法，但该算法同时也只要求最少的内存。相反，Levenberg-Marquardt 算法可能是收敛速度最快的，但其同时也要求最多的内存。比较折衷方法是拟牛顿法。

总而言之：

• 如果我们的神经网络有数万参数，为了节约内存，我们可以使用梯度下降或共轭梯度法 。
• 如果 我们需要训练多个神经网络，并且每个神经网络都只有数百参数、数千样本，那么我们可以考虑 Levenberg-Marquardt 算法 。
• 而其余的情况，拟牛顿法都能很好地应对。

12. 卷积神经网络(CNN)

CNN 可以应用在场景分类，图像分类，现在还可以应用到自然语言处理(NLP)方面的很多问题，比如句子分类等。

LeNet 是最早的CNN结构之一，它是由大神 Yann LeCun 所创造的，主要是用在字符分类问题。

卷积神经网络主要包含四种不同的网络层，分别是卷积层，非线性层(也就是使用了ReLU函数)，Pooling层，全连接层，下面将一一介绍这几种网络层。

12.1 卷积层

卷积简介

CNN的名字由来就是因为其使用了卷积运算的缘故。卷积的目的主要是为了提取图片的特征。卷积运算可以保持像素之间的空间关系。

每张图片可以当做是一个包含每个像素值的矩阵，像素值的范围是 0~255,0 表示黑色，255 是白色。下面是一个 5 × 5 大小的矩阵例子，它的值是 0 或者 1。

接下来是另一个 3 × 3 矩阵：

上述两个矩阵通过卷积，可以得到如下图右侧粉色的矩阵结果。

黄色的矩阵在绿色的矩阵上从左到右，从上到下，每次滑动的步进值是1个像素，所以得到一个 3 × 3 的矩阵。

在CNN中，黄色的矩阵被叫做 滤波器(filter)或者核(kernel)或者是特征提取器 ，而通过卷积得到的矩阵则是称为“特征图(Feature Map)”或者“Activation Map”。

另外， 使用不同的滤波器矩阵是可以得到不同的 Feature Map ，例子如下图所示：

上图通过滤波器矩阵，实现了不同的操作，比如边缘检测，锐化以及模糊操作等。

在实际应用中，CNN 是可以在其训练过程中学习到这些滤波器的值，不过我们需要首先指定好滤波器的大小，数量以及网络的结构。使用越多的滤波器，可以提取到更多的图像特征，网络也就能够有更好的性能。

Feature Map 的尺寸是由以下三个参数来决定的：

• 深度(Depth) ： 深度等于滤波器的数量 。
• 步进(Stride) : 步进值是在使用滤波器在输入矩阵上滑动的时候，每次滑动的距离。步进值越大，得到的 Feature Map 的尺寸越小。
• Zero-padding : 有时候可以在输入矩阵的边界填补 0，这样就可以将滤波器应用到边缘的像素点上，一个好的 Zero-padding 是能让我们可以控制好特征图的尺寸的。使用该方法的卷积称为 wide convolution ，没有使用的则是 narrow convolution 。

卷积公式和参数量

卷积是大自然中最常见的运算，一切信号观测、采集、传输和处理都可以用卷积过程实现，其用公式表达如下：

上述公式中 表示卷积核。

在 CNN 中的卷积层的计算步骤与上述公式定义的二维卷积有点差异，首先是维度升至三维、四维卷积，跟二维卷积相比多了一个**“通道”(channel)**，每个通道还是按照二维卷积方式计算，而多个通道与多个卷积核分别进行二维卷积，得到多通道输出，需要“合并”为一个通道； 其次是卷积核在卷积计算时没有“翻转”，而是与输入图片做滑动窗口“相关”计算 。用公式重新表达如下：

这里假定卷积层有 L 个输出通道和 K 个输入通道，于是需要有 K×L 个卷积核实现通道数目的转换。其中 X^k 表示第 k 个输入通道的二维特征图，Y^l 表示第 l 个输出通道的二维特征图，H^{kl} 表示第 k 行、第 l 列二维卷积核。

假定卷积核大小是 I×J,每个输出通道的特征图大小是 M×N，则该层每个样本做一次前向传播时卷积层的计算量是

Calculations(MAC)=I×J×M×N×K×L。

卷积层的学习参数，也就是 卷积核数目乘以卷积核的尺寸-- 。

这里定义计算量-参数量之比是 CPR = 。

因此可以得出结论： 卷积层的输出特征图尺寸越大，CPR 越大，参数重复利用率越高。若输入一批大小为 B 的样本，则 CPR 值可提高 B 倍。

优点

卷积神经网络通过**『参数减少』与『权值共享』**大大减少了连接的个数，即需要训练的参数的个数。

假设我们的图像是 1000×1000 的，则有 10^6 个隐层神经元，那么它们全连接的话，也就是每个隐层神经元都连接图像的每个像素点，就有 10^12 个连接，也即 10^12 个权值参数需要训练，这显然是不值得的。

但是对于一个只识别特定特征的卷积核，需要大到覆盖整个图像的所有像素点吗？

通常是不需要的， 一个特定特征，尤其是第一层需要提取的特征，通常都相当基础，只占图像很小的一部分。所以我们设置一个较小的局部感受区域，比如 10*10 ，也即每个神经元只需要和这 10*10 的局部图像相连接，所以 10^6 个神经元也就有 10^8 个连接。这就叫参数减少。

那什么叫权值共享呢？

在上面的局部连接中，10^6 个神经元，每个神经元都对应 100 个参数，所以是 10^8 个参数， 那如果每个神经元所对应的参数都是相同的，那需要训练的参数就只有 100 个 。

这后面隐含的道理在于， 这 100 个参数就是一个卷积核，而卷积核是提取特征的方式，与其在图像上的位置无关，图像一个局部的统计特征与其他局部的统计特征是一样的，我们用在这个局部抽取特征的卷积核也可以用在图像上的其它任何地方 。

而且这 100 个参数只是一种卷积核，只能提取一种特征，我们完全可以采用 100 个卷积核，提取 100 种特征，而所需要训练的参数也不过 10^4，最开始我们训练 10^12 个参数，还只能提取一种特征。选取 100 个卷积核，我们就能得到 100 张特征图，每张特征图可以看做是一张图像的不同通道。

CNN 主要用来识别位移、缩放及其他形式扭曲不变性的二维图形。

由于 CNN 特征检测层通过训练数据进行学习，在使用 CNN 时， 避免了显式的特征抽取 ，而隐式地从训练数据中进行学习；

再者，由于同一个特征图上的神经元权值相同，所以 网络可以并行学习，这也是卷积网络相对于神经元彼此相连网络的一大优 势。

卷积神经网络以其 局部权值共享的特殊结构 在语音识别和图像处理方面有着独特的优越性，其布局更接近于实际的生物神经网络， 权值共享降低了网络的复杂性，避免了特征提取和分类过程中数据重建的复杂 度。

12.2 非线性层(ReLU)

非线性修正函数**ReLU(Rectified Linear Unit)**如下图所示：

这是一个对每个像素点实现点乘运算，并用 0 来替换负值像素点。

其目的是在 CNN 中加入非线性， 因为使用 CNN 来解决的现实世界的问题都是非线性的，而卷积运算是线性运算，所以必须使用一个如ReLU的非线性函数来加入非线性的性质 。

其他非线性函数还包括 tanh 和 Sigmoid ,但是 ReLU 函数已经被证明在大部分情况下性能最好。

12.3 Pooling层

**空间合并（Spatial Pooling)**也可以叫做子采样或者下采样，可以在保持最重要的信息的同时降低特征图的维度。它有不同的类型，如最大化，平均，求和等等。

对于 Max Pooling 操作，首先定义一个空间上的邻居，比如一个 2×2 的窗口，对该窗口内的经过 ReLU 的特征图提取最大的元素。除了提取最大的元素，还可以使用窗口内元素的平均值或者是求和的值。

不过， Max Pooling 的性能是最好的。例子可以如下图所示：

上图中使用的步进值是 2。

根据相关理论，特征提取的误差主要来自两个方面：

1. 邻域大小受限 造成的估计值方差增大；
2. 卷积层参数误差 造成估计均值的偏移。

一般来说，mean-pooling 能减小第一种误差，更多的保留图像的背景信息，max-pooling 能减小第二种误差，更多的保留纹理信息。

使用Pooling的原因有如下几点：

• 不变性，更关注是否存在某些特征而不是特征具体的位置。可以看作加了一个很强的先验，让学到的特征要能容忍一些的变化。
• 减小下一层输入大小，减小计算量和参数个数。
• 获得定长输出。（文本分类的时候输入是不定长的，可以通过池化获得定长输出）
• 防止过拟合或有可能会带来欠拟合

12.4 全连接层

全连接层就是 一个传统的多层感知器 ，它在输出层使用一个 softmax 激活函数。

其主要作用就是将 前面卷积层提取到的特征结合在一起然后进行分类 。

Softmax函数可以将输入是一个任意实数分数的向量变成一个值的范围是 0~1 的向量，但所有值的总和是 1。

在 CNN 出现之前，最早的深度学习网络计算类型都是全连接形式的。

比较卷积层和全连接层，卷积层在输出特征图维度实现了 权值共享 ，这是降低参数量的重要举措，同时，卷积层 局部连接 特性（相比全连接）也大幅减少了参数量。

因此卷积层参数量占比小，但计算量占比大，而全连接层是参数量占比大，计算量占比小。所以在进行计算加速优化时，重点放在卷积层；在进行参数优化、权值剪裁时，重点放在全连接层。

12.5 反向传播(Backpropagation)

CNN的整个训练过程如下所示：

1. 首先是随机初始化所有滤波器以及其他参数和权重值；
2. 输入图片，进行前向传播，也就是经过卷积层，ReLU 和 pooling 运算，最后到达全连接层进行分类，得到一个分类的结果，也就是输出一个包含每个类预测的概率值的向量；
3. 计算误差，也就是代价函数，这里代价函数可以有多种计算方法，比较常用的有平方和函数;
4. 使用反向传播来计算网络中对应各个权重的误差的梯度，一般是使用梯度下降法来更新各个滤波器的权重值，目的是为了让输出的误差，也就是代价函数的值尽可能小。
5. 重复上述第二到第四步，直到训练次数达到设定好的值。

小结

常用的机器学习算法就简单介绍到这里，下一篇会介绍模型的评估方法。

参考：

• 《统计学习方法》
• Ensemble learning:Bagging,Random Forest,Boosting
• 机器学习（四）--- 从gbdt到xgboost
• xgboost入门与实战（原理篇）
• 机器学习算法中GBDT和XGBOOST的区别有哪些？
• 常见的几种最优化方法
• An Intuitive Explanation of Convolutional Neural Networks
• 对CNN中pooling的理解
• 《深度学习轻松学：核心算法与视觉实践》
• ResNet解析

欢迎关注我的微信公众号--机器学习与计算机视觉，或者扫描下方的二维码，大家一起交流，学习和进步！