集成学习

1. 简介

1.1 定义

• 传统机器学习算法 (例如：决策树，人工神经网络，支持向量机，朴素贝叶斯等) 的目标都是寻找一个最优分类器尽可能的将训练数据分开。
• 集成学习 (Ensemble Learning) 算法的基本思想就是将多个分类器组合，从而实现一个预测效果更好的集成分类器。集成算法可以说从一方面验证了中国的一句老话：三个臭皮匠，赛过诸葛亮

• 集成学习通过建立几个模型来解决单一预测问题。它的工作原理是生成多个分类器/模型，各自独立地学习和作出预测。这些预测最后结合成组合预测，因此优于任何一个单分类的做出预测。
• 集成学习是一种思想，不是某一个算法

1.2 分类

集成算法大致可以分为：Bagging，Boosting 和Stacking等类型。

• bagging 并行 多个学习器互不相关 可以并行训练
• boosting 串行 后一个学习器依赖于前一个学习器
• stacking 多个学习器的输出作为后面一个学习器的输入

2. Bagging和随机森林

2.1 简介

1. 定义

• Bagging (Boostrap Aggregating) 是由 Breiman 于 1996 年提出。
• Bagging + 决策树/线性回归/逻辑回归/深度学习… = bagging集成学习方法

2. 基本思想

1. 每次采用有放回的抽样从训练集中取出t个训练样本组成新的训练集。
2. 利用新的训练集，训练得到m个子模型。
3. 对于分类问题，采用投票的方法，得票最多子模型的分类类别为最终的类别；对于回归问题，采用简单的平均方法得到预测值。

3. 优点

1. 均可在原有算法上提高约2%左右的泛化正确率
2. 简单, 方便, 通用

4. 集成原理

• 目标：把下面的圈和方块进行分类

• 实现过程：

1. 采样不同数据集

2. 训练分类器

3. 平权投票，获取最终结果

4. 主要实现过程小结

2.2 随机森林

1. 简介

1.1 定义

• 随机森林(Random Forests)是一种利用决策树作为基学习器的Bagging集成学习算法。

1.2 模型构建

• 数据采样
  • 作为一种集成算法，随机森林同样采用有放回的采样，对于总体训练集，抽样一个子集作为训练样本集。除此之外，假设训练集的特征个数为d，每次仅选择k(k<d)个构建决策树。因此，随机森林除了能够做到样本扰动外，还添加了特征扰动，对于特征的选择个数，推荐值为。
• 树的构建
  • 每次根据采样得到的数据和特征构建一棵决策树。在构建决策树的过程中，会让决策树生长完全而不进行剪枝。构建出的若干棵决策树则组成了最终的随机森林。

2. 优点

• 随机森林在众多分类算法中表现十分出众，其主要的优点包括：
  • 由于随机森林引入了样本扰动和特征扰动，从而很大程度上提高了模型的泛化能力，尽可能地避免了过拟合现象的出现。
  • 随机森林可以处理高维数据，无需进行特征选择，在训练过程中可以得出不同特征对模型的重要性程度。
  • 随机森林的每个基分类器采用决策树，方法简单且容易实现。同时每个基分类器之间没有相互依赖关系，整个算法易并行化。

3. 构造过程

例如, 如果你训练了5个树, 其中有4个树的结果是True, 1个树的结果是False, 那么最终投票结果就是True

随机森林够造过程中的关键步骤（M表示特征数目）：

1）一次随机选出一个样本，有放回的抽样，重复N次（有可能出现重复的样本）

2） 随机去选出m个特征, m <<M，建立决策树

1. 随机抽样训练集目的：

   如果不进行随机抽样，每棵树的训练集都一样，那么最终训练出的树分类结果也是完全一样的。

2. 有放回地抽样目的：

   如果不是有放回的抽样，那么每棵树的训练样本都是不同的，都是没有交集的，这样每棵树都是“有偏的”，都是绝对“片面的”

4. api

随机森林api介绍

sklearn.ensemble.RandomForestClassifier(n_estimators=10, criterion=’gini’, max_depth=None, bootstrap=True, random_state=None, min_samples_split=2)
n_estimators：integer，optional（default = 10）森林里的树木数量120,200,300,500,800,1200
Criterion：string，可选（default =“gini”）分割特征的测量方法
max_depth：integer或None，可选（默认=无）树的最大深度 5,8,15,25,30
max_features="auto”,每个决策树的最大特征数量
1
2
3
4
5

If "auto", then max_features=sqrt(n_features).
If "sqrt", then max_features=sqrt(n_features)(same as "auto").
If "log2", then max_features=log2(n_features).
If None, then max_features=n_features.
1
2
3
4

bootstrap：boolean，optional（default = True）是否在构建树时使用放回抽样
min_samples_split:节点划分最少样本数
min_samples_leaf:叶子节点的最小样本数
1
2
3

• 超参数：n_estimator, max_depth, min_samples_split,min_samples_leaf

5. 应用

案例

# 随机森林去进行预测
# 1 实例化随机森林
rf = RandomForestClassifier()
# 2 定义超参数的选择列表
param = {"n_estimators": [120,200,300,500,800,1200], "max_depth": [5, 8, 15, 25, 30]}

# 超参数调优
# 3 使用GridSearchCV进行网格搜索
gc = GridSearchCV(rf, param_grid=param, cv=2)

gc.fit(x_train, y_train)

print("随机森林预测的准确率为：", gc.score(x_test, y_test))

1
2
3
4
5
6
7
8
9
10
11
12
13
14

3. Boosting

3.1 简介

1. 定义

Boosting 是一种提升算法，可以将弱的学习算法提升(boost)为强的学习算法。

2. 基本思想

1. 利用初始训练样本集训练得到一个基学习器。
2. 提高被基学习器误分的样本的权重，使得那些被错误分类的样本在下一轮训练中可以得到更大的关注，利用调整后的样本训练得到下一个基学习器。
3. 重复上述步骤，直至得到M个学习器。
4. 对于分类问题，采用有权重的投票方式；对于回归问题，采用加权平均得到预测值。

3. 实现过程

实现过程

1. 训练第一个学习器

2. 调整数据分布

3. 训练第二个学习器

4. 再次调整数据分布

5. 依次训练学习器，调整数据分布

6. 整体过程实现

3.2 Adaboost

1. 简介

1.1 定义

• Adaboost是Boosting算法中有代表性的一个
• 原始的Adaboost算法用于解决二分类问题

1.2 基本思想

1. 一个训练集
   
   其中

2. 初始化训练集权重

3.

4. 基学习器在最终学习器中的权重系数

5. 更新训练集的权重，供下一轮使用

其中Zm为规范化因子

根据该更新公式，如果第m轮预测对了的样本，更新权重，乘以1/(e^am)系数， 如果第m轮预测错了的样本，更新权重，乘以(e^am)系数，

6. 就会把每一轮预测错误的样本权重提升,保证Dm+1为一个概率分布，最终根据构建的m个基学习器得到最终学习器：

• y = sign(x)函数 ,如果x>0，则y=1 如果x<=0 则y=-1.hm的预测结果是-1或者+1

3.3 GBDT

1. 简介

1.1 定义

• GBDT(Gradient Boosting Decision Tree)是另一种基于Boosting思想的集成算法，除此之外GBDT还有其他的叫法，例如GBM(Gradient Boosting Machine),GBRT(Gradient Boosting RegressionTree),MART(Multiple Additive Regression Treee)
• GBDT算法由3个主要概念构成：
  GradientBoosting（GB），RegressionDesicionTree(DT或RT）和Shrinkage
• GBDT用的是回归树，分类树主要用于处理响应变量为类别型的数据，例如天气(可以为晴，阴或下雨等)。回归树主要用于处理响应变量为数值型的数据，例如商品的价格。当然回归树也可以用于二分类问题，对于回归树预测出的数值结果，通过设置一个阈值即可以将数值型的预测结果映射到二分类问题标签上，即Y = -1， +1
  对于Gradient Boosting而言，首先Boosting并不是Adaboost中的概念，也不是RandomForest中的重抽样。在Adaboost中，Boost是指在生成每个新的基学习器时，根据上一轮基学习器分类对错对训练集设置不同的权重，使得在上一轮中分类错误的样本在生成新的基学习器时更被重视。GBDT中在应用Boost概念时，每一轮所使用的数据集没有经过重抽样，也没有更新样本的权重，而是每一轮选择了不同的回归目标，即上一轮计算得到的残差(Residual)。其次Gredient是指在新一轮中在残差减少的梯度Gradient上建立新的基学习器。
  示例

1.2 思想

• GBDT boost思想，每一轮所使用的数据集没有经过重抽样，也没有更新样本的权重，而是每一轮选择了不同的回归目标，即上一轮计算得到的残差。就是上一轮预测结果和真实标签的差值。该差值作为下一轮训练样本的标签。

预测时，根据预测样本的特征，把预测样本分到某一个分支，以这个分支样本标签的均值，作为这一轮的预测结果，放入到下一个模型继续预测，最终把所有模型的预测结果累加得到最终的预测结果。

2. 工作流程

下面我们通过一个年龄预测的示例，简单介绍的工作流程。

假设存在 4 个人P = p1, p2, p3, p4 ，他们的年龄分别为14, 16, 24, 26。其中p1, p2分别是高一和高三学生，p3, p4分别是应届毕业生和工作两年的员工。利用原始的决策树模型进行训练可以得到如下图所示的结果：

利用训练模型，由于数据量少，在此我们限定每个基学习器中的叶子节点最多为个，即树的深度最大为层。训练得到的结果如下图所示：

在训练第一棵树过程中，利用平均年龄作为预测值，由于p1, p2年龄相近，p3, p4年龄相近被划分为两组。通过计算两组中真实年龄和预测的年龄的差值，可以得到第一棵树的残差R = -1, 1, -1, 1。残差的意思就是： A的预测值 - A的实际值 = A的残差。 因此在训练第二棵树的过程中，利用第一棵树的残差作为标签值，最终所有人的年龄均正确被预测，即最终的残差均为 0。

则对于训练集中的个4人，利用训练得到的GBDT模型进行预测，结果如下：

1. p1：14岁高一学生。购物较少，经常问学长问题，预测年龄Age = 15 -1 = 14。
2. p2：16岁高三学生。购物较少，经常回答学弟问题，预测年龄Age = 15 + 1 = 16。
3. p3：24岁应届毕业生。购物较多，经常问别人问题，预测年龄Age = 25 - 1 = 24。
4. p4：26岁 2 年工作经验员工。购物较多，经常回答别人问题，预测年龄Age = 25 + 1 = 26。

3. 算法原理

GBDT 的全称是 Gradient Boosting Decision Tree，梯度提升树，在传统机器学习算法中，GBDT算的上TOP3的算法。

3.1 Decision Tree：CART回归树

1. 简介

• GBDT使用的决策树是CART回归树，无论是处理回归问题还是二分类以及多分类，GBDT使用的决策树通通都是都是CART回归树。

为什么不用CART分类树呢？
因为GBDT每次迭代要拟合的是梯度值，是连续值所以要用回归树。

对于回归树算法来说最重要的是寻找最佳的划分点，那么回归树中的可划分点包含了所有特征的所有可取的值。

在分类树中最佳划分点的判别标准是熵或者基尼系数，都是用纯度来衡量的，但是在回归树中的样本标签是连续数值，所以再使用熵之类的指标不再合适，取而代之的是平方误差，它能很好的评判拟合程度。

2. 回归树生成算法

• 输入：训练数据集D:
• 输出：回归树.
• 在训练数据集所在的输入空间中，递归的将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树：

1. 选择最优切分特征j与切分点s，求解
   

遍历特征,对固定的切分特征扫描切分点,选择使得上式达到最小值的对.

2. 用选定的对划分区域(j, s)并决定相应的输出值
3. 继续对两个子区域调用步骤1和2，直至满足停止条件。
4. 将输入空间划分为M个区域R1, R2,…RM, 生成决策树：

3.2 Gradient Boosting： 拟合负梯度

梯度提升树（Grandient Boosting）是提升树（Boosting Tree）的一种改进算法。

• 提升树：

先来个通俗理解：假如有个人30岁，我们首先用20岁去拟合，发现损失有10岁，这时我们用6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。最后将每次拟合的岁数加起来便是模型输出的结果。

• 提升树算法：

1. 初始化f0(x) = 0
2. 对m=1,2,…,M
   2.1 计算残差

2.2 拟合残差rmi学习一个回归树，得到hm(x)
2.3 更新

3. 得到回归问题提升树

在提升树算法中，

假设我们前一轮迭代得到的强学习器是：$$f_{t-1}(x)$$

损失函数是：$$L(y,f_{t-1}(x))$$

我们本轮迭代的目标是找到一个弱学习器：$$h_t(x)$$

最小化让本轮的损失：$$L(y,f_t(x))=L(y,f_{t-1}(x)+h_t(x))$$

当采用平方损失函数时：
$$r=y-f_{t-1}(x)$$是当前模型拟合数据的残差(residual)。

提升树只需要简单地拟合当前模型的残差。

例子中的第一次迭代的残差是10岁，第二 次残差4岁

• 梯度提升树

当损失函数是平方损失和指数损失函数时，梯度提升树每一步优化是很简单的，但是对于一般损失函数而言，往往每一步优化起来不那么容易。
针对这一问题，Friedman提出了梯度提升树算法，这是利用最速下降的近似方法，其关键是利用损失函数的负梯度作为提升树算法中的残差的近似值。

• 负梯度

• 第t轮的第i个样本的损失函数的负梯度为：

• 此时不同的损失函数将会得到不同的负梯度，如果选择平方损失：

• 负梯度为：

此时GBDT的负梯度就是残差，所以说对于回归问题，我们要拟合的就是残差。

对于分类问题

• 二分类和多分类的损失函数都是logloss。

• GBDT算法原理
  将Decision Tree和Gradient Boosting这两部分组合在一起

• GBDT算法：

（1）初始化弱学习器
$$f_0(x)=\arg \underset{c}{\min }\sum _{i=1}^{N}L(y_i,c)$$

（2）对有m = 1, 2, … ,M

（a）对每个样本i = 1, 2, …,N，计算负梯度，即残差 $$r_{im}=-{\left[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}\right]}_{f(x)=f_{m-1}(x)}$$

（b）将上步得到的残差作为样本新的真实值，并将数据$$(x_i,r_{im}),i=1,2,..N$$作为下棵树的训练数据，得到一颗新的回归树$$f_m(x)$$其对应的叶子节点区域为$$R_{jm},j=1,2,\cdots ,J$$。其中J为回归树t的叶子节点的个数。

（c）对叶子区域j = 1, 2, …, J计算最佳拟合值 $${{\rm Y}}_{jm}=\underset{{\rm Y}}{\underbrace{\arg \min }}\sum _{x_i\in R_{jm}}L(y_i,f_{m-1}(x_i)+{\rm Y})$$

（d）更新强学习器
$$f_m(x)=f_{m-1}(x)+\sum _{i=1}^J{r}_{jm}I(x\in R_{jm})$$

（3）得到最终学习器
$$f(x)=f_M(x)=f_0(x)+\sum _{m=1}^M\sum _{j=1}^J{r}_{jm}I(x\in R_{jm}$$

• 应用

1. 数据介绍
   根据如下数据，预测最后一个样本的身高。

2. 模型训练
   2.1 设置参数：
   学习率：learning_rate = 0.1
   迭代次数：n_trees = 5
   树的深度：max_depth = 3
   2.2 开始训练
   1.初始化弱学习器:

损失函数为平方损失，因为平方损失函数是一个凸函数，直接求导，倒数等于零，得到c。

令导数等于0

所以初始化时，取值为所有训练样本标签值的均值。c = (1.1 + 1.3 + 1.7 + 1.8）/4 = 1.475，此时得到初始学习器f0(x)：f0(x) = c =1.475
2.对迭代轮数m = 1, 2, …, M:
由于设置了迭代次数n_trees = 5：，这里的M = 5。

计算负梯度，根据上文损失函数为平方损失时，负梯度就是残差，再直白一点y就是 与上一轮得到的学习器fm-1的差值：

残差在下表列出：

此时将残差作为样本的真实值来训练弱学习器，即下表数据

接着，寻找回归树的最佳划分节点，遍历每个特征的每个可能取值。

从年龄特征的5开始，到体重特征的70结束，分别计算分裂后两组数据的平方损失(Square Error)

SEl左节点平方损失，SEr右节点平方损失，找到使平方损失和SEsum = SEL + SEr最小的那个划分节点，即为最佳划分节点。

例如：以年龄21为划分节点，将小于21的样本划分为到左节点，大于等于21的样本划分为右节点。左节点包括 ，右节点包括样本，

所有可能划分情况如下表所示：

以上划分点是的总平方损失最小为0.025有两个划分点：年龄21和体重60，所以随机选一个作为划分点，这里我们选 年龄21 现在我们的第一棵树长这个样子：

我们设置的参数中树的深度max_depth=3，现在树的深度只有2，需要再进行一次划分，这次划分要对左右两个节点分别进行划分：

对于左节点，只含有0,1两个样本，根据下表我们选择年龄7划分

对于右节点，只含有2,3两个样本，根据下表我们选择年龄30划分（也可以选体重70）

现在我们的第一棵树长这个样子：

此时我们的树深度满足了设置，还需要做一件事情，给这每个叶子节点分别赋一个参数，来拟合残差。

这里其实和上面初始化学习器是一个道理，平方损失，求导，令导数等于零，化简之后得到每个叶子节点的参数r，其实就是标签值的均值。这个地方的标签值不是原始的 y，而是本轮要拟合的标残差 y0-f0(x).
根据上述划分结果，为了方便表示，规定从左到右为第1, 2, 3, 4个叶子结点

此时的树长这个样子：

此时可更新强学习器，需要用到参数学习率：learning_rate = 0.1，用lr表示。

用学习率是Shrinkage的思想，如果每次都全部加上（学习率为1）很容易一步学到位导致过拟合。
重复此步骤，直到 m>5 结束，最后生成5棵树。

结果中，0.9倍这个现象，和其学习率有关。这是因为数据简单每棵树长得一样，导致每一颗树的拟合效果一样，而每棵树都只学上一棵树残差的0.1倍，导致这颗树只能拟合剩余0.9了。

3.得到最后的强学习器：

4.预测样本：

在中，样本4的年龄为25，大于划分节点21岁，又小于30岁，所以被预测为0.2250;
在中，样本4的…此处省略…所以被预测为0.2025;
在中，样本4的…此处省略…所以被预测为0.1823;
在中，样本4的…此处省略…所以被预测为0.1640;
在中，样本4的…此处省略…所以被预测为0.1476.
最终预测结果：