deep learning 人工智能机器学习 tensorflow 深度学习决策树随机森林 XGBoost

机器学习

Publish Date: 2025-02-15

Word Count: 4.2k

Read Times: 15 Min

Read Count:

吴恩达机器学习 course2 week4 决策树

1 什么是决策树

“神经网络”和“决策树/决策树集合”都被广泛应用于很多商业应用，并且在各类机器学习比赛中也取得了很好的成绩。但相比于“神经网络”，“决策树/决策树集合”却并没有在学术界引起很多关注。本周就来介绍“决策树/决策树集合”这个非常强大的工具。

【问题1】“识别猫”：二元分类，对于给定的特征，判断是否为猫。

输入特征：“耳朵形状”、“脸型”、“胡须”。
输出：是否为猫。
默认数据集：三个“二元输入特征”，对应一个“二元输出结果”。

“决策树(decision tree)”采用“二叉树”的结构，从根节点(root node)开始，不断地进行一系列判断，最终到达叶子节点(leaf node)，也就是预测结果。上面的“识别猫”问题将贯穿本周，用于帮助我们理解“决策树”中的概念。比如针对“识别猫”的数据集，我们可以构建如下所示的“决策树”，此时有一个新的输入，就可以按照该“决策树”进行推理

可以看到按照“决策树”的判断过程，这个新的输入最终被预测为猫，符合预期。但显然，对于当前给定的训练集，若没有其他约束条件的话，上述问题的决策树显然不止一种，如下图：

在上述这些不同的决策树当中，某些性能很好、某些性能很差。所以“决策树学习算法”就是，在所有可能的决策树中，找出当前数据集所对应的性能最好的决策树模型。下面是我们需要考虑的两条准则：

如何选择在每个节点使用什么特征进行拆分？

希望拆分后，能尽可能的区分不同的结果 y ，理想状态就是所有子集都各自是不同种类 y 的集合。也就是拆分后，希望尽可能的减少信息的“不确定度”。比如在图1中，由于使用“Ear shape”进行拆分可以使“猫”尽量集中于同一个子集中，“不确定度”最小，“纯度”最大（maximize purity），所以选择其为根节点。后面会介绍如何计算这种“不确定度”。

什么时候停止拆分？

子集被完全区分。

达到设置的最大深度。

降低的“不确定度”低于某个阈值。

当前节点的子集大小低于某个阈值(某个数)。

注1：树不应太深、太大，否则有过拟合的风险。

注2：第二节会详细介绍构建“决策树”的步骤

2 单个决策树

2-1 纯度

前面提到希望每次在节点进行拆分时，都尽可能的降低信息的“不确定度”，也就是尽可能提升信息的“**纯度(purity)”。这个“不确定度”使用“熵(entropy)**”来进行计算，下面是“熵”的计算公式和曲线。由于“熵”的物理意义就是“信息的不确定度/不纯的程度”，所以机器学习中又喜欢称“熵”为“杂质(impurity)”。这些都只是花里胡哨的名字而已，只需要记住：

熵”就是“杂质”，表示信息的混乱程度，也就是“不纯”的程度。

$$
Entropy: H(P)=-\sum_{all \ i}p_ilog_{2}(p_i) \implies H(p_1) = - p_1 \log_2(p_1) - (1 - p_1) \log_2(1 - p_1)
$$

注意，除了“熵”之外，还有其他方法来衡量“信息不纯的程度”，比如开源软件包中会提供“Gini指数”。它表示从数据集中随机选择两个样本，其类别标签不一致的概率，下面是其计算公式。但是为了首先掌握决策树的构建过程，而不是让过多的琐碎的概念困扰，本课程我们就只用“熵”来表示信息的“不纯度”。

$$
\text{Gini index:} \quad G(P) = 1 - \sum_{all \ i} p_i^2 \implies G(p_1) = 1 - p_1^2 - (1 - p_1)^2 = 2p_1(1 - p_1)
$$

2-2 选择拆分信息增益

在构建决策树时，如何选择在节点上分割哪些特征。关键在于选择能够最大降低熵或杂质的特征。每次拆分都应最大程度的减少信息的不确定度，也就是“熵”（或最大化纯度），而减少的“熵”的大小则被称为“信息增益”。

选择根节点——三个特征的信息增益计算

显然，在三种“二元输入特征”中，“Ear shape”的“信息增益”最大，所以选为根节点。
$$
Information \ Gain = H(p₁^{root}) - (w^{left}H(p₁^{left}) + w^{right}H(p₁^{right}))
$$

$H(p₁^{root})$: 拆分前的不确定度
$w^{left}$: 拆分后，左分支的集合的比例
$w^{right}$: 拆分后，右分支的集合比例
$H(p₁^{left})$: 拆分后，左分支的不确定度
$H(p₁^{right})$: 拆分后，右分支的不确定度

2-3 整合（构建决策树——二元输入特征）

构建（二元输入特征）决策树的过程：

在根节点，找出最大的“信息增益”所对应的特征，作为拆分标准。
创建左右分支，各自找出剩余特征中“信息增益”最大的，作为各自的拆分标准。
不断向下进行拆分，直到：
- 熵”为0，也就是完全分类。
- 达到预设的最大深度。可以使用“验证集”选择最合适的深度。
- 所有剩余特征的“信息增益”都低于某个阈值。
- 子集的大小低于某个阈值(某个数)。

注1：停止拆分是为了保证树不会变的太大、太笨重，进而降低过拟合的风险。
注2：上述算法可以使用“递归”。
注3：在构建过程中，左右分支可能会选取相同的特征。

2-4 独热编码One-hot(构建决策树——多元输入特征)

若想针对“多元输入特征”构建决策树，可能会有如下针对“二元输入特征”决策树的改进思路：

创建多分支【不推荐】。整体思路和前面一样，只不过某些节点可能是多分支，但由于每个输入特征的可选种类不一定相同，这种方法会增加计算难度和代码量。
将“多元特征”转换成“独热码(One-hot)”【推荐】：不仅可以继续使用之前二元特征的决策树思路，甚至也可以转换成神经网络的训练模式。

比如下面的“耳朵形状(Ear shape)”有三种可能取值“尖的(Pointy)”、“松软的(Floppy)”、“椭圆形的(Oval)”，将其转换成独热码后，相当于将1个“三元输入特征”转化成3个“二元输入特征”，于是我们只需要对训练集进行一小步预处理，即可复用上述“二元输入特征”的思路：

2-5 连续有价值的功能（构建决策树——连续的输入特征）

和上一小节类似，也是将“连续输入特征”转换成“二元输入特征”，然后继续进行构建。但不同的是，“多元特征”只需在最开始进行预处理，而在没被当前所在分支使用前，“连续输入特征”需要在每个节点都进行一次计算。具体来说，就是选择一个阈值，依照该阈值对当前节点的集合进行拆分，可以使“信息增益”最大，不同节点所计算的阈值可能不同。于是，就可以将“连续输入特征”转换成判断大小的“二元输入特征”。比如在“识别猫”问题中，引入“重量”这一连续取值的输入特征，由于选取“9”作为阈值可以使“信息增益”最大，于是便将“重量”这一“连续输入特征”，转换成“是否小于等于9磅？”这个“二元输入特征”：

Choose the 9 mid-points between the 10 examples as possible splits, and find the split that gives the highest
information gain.

2-6 回归树

将“决策树(decision trees)”算法推广到“回归树(regression trees)”，也就是将“决策树”的预测结果扩展到连续的取值。和之前的“拆分后尽可能减少信息的不确定度”类似，“回归树”使用“方差(variance)”来衡量信息的不确定度。于是，拆分后的方差为左右两分支的方差的加权平均，权值也是 左右分支的子集大小 占 拆分前集合大小 的比例。相应的“信息增益”为：

$$
Information \ gain=V(s^{root})−(w^{left}V(s^{left})+w^{right}V(s^{right}))
$$

$V(s^{root})$: 拆分前的集合数据的方差。
$w^{left}$: 拆分后，左分支的集合的比例
$w^{right}$: 拆分后，右分支的集合的比例
$V(s^{left})$: 拆分后，左分支的集合数据的方差
$V(s^{right})$: 拆分后，右分支的集合数据的方差

“信息增益”只是一个泛在的概念，虽然上述定义和2-1不同，但物理意义相通

回到“识别猫”问题，现在将“重量”作为需要预测的结果(如下左图)。于是，在每次进行拆分时，就使用“方差”来计算“信息增益”，并选择“信息增益”最大的特征作为当前节点的拆分标准。最后达到终止拆分条件，“决策树”构建完成时，直接使用最终分类的均值作为以后的预测值：

每次拆分都尽可能的减少方差

使用均值作为当前分支的预测结果

3 决策树集合

上一节已经详细的讨论了如何构建单个“决策树”。事实上，如果训练很多“决策树”组成“**决策树集合(dicision tree ensemble)**”，那么会得到更准确、更稳定的预测结果。下面就来介绍几种构建“决策树集合”的方法。

3-1 使用多个决策树

使用单个决策树完成任务时，有一个很大的缺点：单个决策树对于训练集的微小变化非常敏感。比如下图中，只是替换了训练集中的单个样本，就导致训练出完全不一样的决策树：

对于一个新的输入，不同的决策树很可能会有不同的预测结果。于是为了使算法更强壮，我们就需要创建不同的训练集，构建出不同的决策树组成“决策树集合(dicision tree ensemble)”。对于新的输入，使用这个“决策树集合”对所有输出结果进行投票，选择最有可能的结果，于是就可以降低算法对于单个决策树的依赖程度，也就可以降低了对于数据的敏感程度：

3-2 有放回抽样（袋装决策树）

最简单的构建不同训练集的方法，就是“**有放回抽样(sampling with replacement)**”。假设原始训练集大小为 m，每次训练前都随机地有放回抽取 m 次样本，作为本次的训练集：

于是我们便可以创建出，有微小不同的多个训练集。注意到，单次的抽取结果中，可以有重复的样本。上面这种方法就称为“袋装决策树(bagged decision tree)”：

“袋装决策树”创建方法：

假设原始训练集大小为 m
并且“决策树集合”的大小为 B (bag)，于是
```
for b = 1 to B:
    1. 从原始训练集有放回抽取m次，形成本次训练集。
    2. 然后使用该训练集训练单个决策树。
```
注：B 一般取64~128，选取更大的 B 可能会提升算法性能，但当 B 超过100后就不会有太大的性能增益。

3-3 随机森林算法

“袋装决策树”有个缺点，就是很多决策树在根节点或者根节点附近的区域都非常相似。于是为了避免这个问题，在上述“袋装决策树”的基础上，训练单个决策树时，对于每个节点都会从 n 个特征中随机选取 k 个特征组成子集, 然后在这个子集中选取最大的“信息增益”(k < n)。一般来说，都会取 $k = \sqrt{n}$ . 于是，每次的训练集都是随机选取的，单个决策树的每个节点特征都是从随机选取的子集中选取的，这便称为“随机森林(random forest)”。

正是这些由“随机选取”产生的微小变动组合在一起，使得“随机森林”比单个决策树更加健壮，于是训练集的任何微小变化都不会对随机森林的输出有太大的影响。

“随机森林”创建方法：

for b = 1 to B:
    1. 从原始训练集有放回抽取m次，形成本次训练集。
    2. 然后使用该训练集训练单个决策树。
          选择单个节点拆分标准时，随机选取k个特征进行计算。

注：B 一般取64~128，选取更大的 B 可能会提升算法性能，但当 B 超过100后就不会有太大的性能增益。

注2：一般取 $ k=\sqrt{n}$

3-4 XGBoost 算法

下面介绍比“随机森林(Random forest)”更强的算法——梯度提升树(Gradient boost tree)。每次抽取新的训练集时，都以更高概率选择上一次决策树训练出错的样本。这就是“增强(boosting)”的含义，类似于“刻意练习”。具体的增加多少概率的数学过程是非常复杂的，本课程不过多讨论，会用就行。“**XGBoost(eXtreme Gradient Boosting, 极限梯度提升算法)**”就是“梯度提升树”的一种，下面是其特点：

XGBoost已经集成好开源库，调用简单。
非常快速和高效。
内置了选择单次训练集的方法，所以无需手动为每次训练生成训练集。
对于“拆分标准”、“停止拆分标准”有很好的默认选项。
内置了正则化防止过拟合。
机器学习竞赛中表现出色，如Kaggle。“XGBoost”和“深度学习”算法是在竞赛表现优异的两大算法。

（如果您改为弹奏这首曲子，然后将注意力集中在曲子中您还没有弹得那么好的部分，并一遍又一遍地练习那些较小的部分。我们将查看决策树，到目前为止我们已经训练过，并查看我们在哪些方面还做得不够好。然后在构建下一个决策树时，我们将更多地关注我们还没有做好的例子。因此，我们不是查看所有训练示例，而是更多地关注示例的子集，这些示例还没有做得很好，并获得新的决策树，下一个决策树报告集成以尝试在它们上做得很好。）

多年以来，研究人员提出了很多构建决策树、选取决策树样本的方法。迄今为止，构建决策树集合最常用的方法就是“XGBoost算法”。它运行速度快、开源、易于使用，在很多机器学习比赛、商业应用中广泛使用。XGBoost的内部实现原理非常复杂，所以大家都是直接调用封装好的XGBoost库：

# 分类问题
from xgboost import XGBClassfier
model = XGBClassfier()
model.fit(X_train, y_train)
y_pred = model.predict(X_test)

# 回归问题
from xgboost import XGBRegressor
model = XGBRegressor()
model.fit(X_train, y_train)
y_pred = model.predict(X_test)