我学习决策树有一段时间了，从ID.3、C4.5、C5.0、CART到，包括最流行的. 网上已经有大量关于决策树的文章，但能够系统整理并与Paper+源码集成的却很少。

本系列文章旨在帮助读者从论文和代码层面更深入地理解算法背后的本质。

Tree 介绍了如何构建决策树。 经典算法：ID3、C4.5、CART组合模型/随机森林/BM1。 1.1 决策树简介

决策树“Tree”常用于数据领域的分类和回归，是一种流行的机器学习方法；

对于复杂的预测问题，通过建立树模型来生成分支节点，将其分为两个（二叉树）或多个（多叉树）相对简单的子集，在结构上分为不同的子问题。 按照规则分割数据集的过程将递归地继续下去（ ）。 随着树的深度不断增加，分支节点的子集变得越来越小，需要提出的问题数量也逐渐简化。 当分支节点的深度或者问题的简单性满足一定的停止规则（Rule）时，分支节点就会停止分裂。 这就是自上而下的停止阈值（ ）方法； 一些决策树还使用自下而上的剪枝（）方法。

对于预测问题，还有“”、“SVM”、“k-NN”等其他预测模型，下表是对这些解决方案优缺点的评估：

模型的优缺点（数据来自：《The of》）

那么为什么在神经网络已经非常流行的情况下我们还要继续使用经典的机器学习模型（如决策树、SVM等）呢？

1.1.1 决策树类型

根据数据和需求的不同，决策树可以简单概括为两类：

有人说有一种树叫分类回归树（CART）。 这是怎么回事？其实既可以分类，也可以返回。 详细内容稍后介绍。

例如，为了预测是否“Play”，收集了14天的数据。 数据特征包括“天气”、“温度”、“湿度”、“风”，如下图所示：

第14天数据集

可以看出，决策树是一棵分类树。 下图是一种可能的决策树分裂方案：

决策树（非唯一） 1.2 如何构造决策树

任何决策树的构建过程只需要考虑以下问题：

特征数据预处理？ 决策树是如何分裂的？

有了以上所有信息，就可以确定决策树的构建过程。

1.2.1 数据预处理

特征： 示例：“”取值 {Male, }，“Color”取值 {Red, , Green, Blue, White...}

某些机器学习软件包（例如）不支持字符串类型输入功能，仅支持数字类型。 因此，在输入模型之前，必须将特征数据数字化。 “特征”应该如何映射到“数字空间”？

这里有两种方法：

使用连续的自然数来表示特征值。 例如：0->Red、1->、2->Green、3->Blue... 优点：没有新的特征维度，特征矩阵不稀疏。 缺点：特征值本身是无序的，映射为自然数。 潜在的秩序性； 因此，这样的“特征”必须在算法层面进行特殊对待，抛弃数值的排序特征，使用One-Hot编码将一个特征维度“颜色”变成多维“IsRed”、“”等，每个维度都是二进制的，要么是0，要么是1。 优点：不会出现自然数映射带来的特征值排序问题。 缺点：当特征值数量较多时，会生成过多的特征维度。 ，特征矩阵稀疏（即出现大量0） 1.2.2 分割点搜索

决策树的核心部分是Split。 面对海量数据，如何选择合适的特征以及特征对应的分割位置； 不同的决策树算法（CART、ID3、C4.5）有不同的做法。 下面我们就从多个角度来分析切分点搜索背后的问题。

1.2.2.1 二叉树与多树

常见的决策树算法如CART一般采用Split，而ID3、C4.5等算法则采用伪方式Split。 为什么我说它是假的呢？

特征：-Split（左）、-Ways-Split（右）虽然多树可以通过分裂来完全分离特征，但工程算法的实现往往比二叉树更加困难； 而在一些类似“uuid”的特性中，落入每个叶子节点的样本数量很少甚至只有一个样本。 虽然我们区分了所有样本，但一般来说，这种区分是没有意义的； 我们还将在下一节中讨论“信息增益”和“信息增益比”，详细讨论为什么这种分割是不可取的。 1.2.2.2 如何找到分割点

寻找决策树的 Split 特征的分裂点是一个 NP 问题。 没有明确的方法可以在“多项式时间内”找到最优解。 类似的问题还有Graph； 对于此类问题，我们经常使用“启发式”“形式”方法，例如“贪心算法”，Tree的每一级Node在寻找分裂点时都使用最佳分裂。 该算法不能保证获得全局最优决策树，但可以在获得可接受的解的同时大大降低计算复杂度。

对“贪心算法”的简单理解：如果一棵决策树被限制为有N层，那么构建过程一定是自上而下的。 在建立当前层节点时，我们只选择使当前分裂收益最大化的分裂方式。 ，不关心下一步的收益，甚至下一步的分割； 有时前几步分裂的收益不是很大，但后面分类的收益却很大，导致整体收益比贪心算法高； 但由此产生的计算开销会大大增加，所以我们在算法实现中往往只会使用贪心算法来帮助我们选择一个相对可靠的解决方案。

常用的切入点搜索和评估方法包括以下几种：

分类决策树场景：

信息增益（熵减）/Gain ( ) 信息增益比/增益比 基尼不纯度/基尼误分类率/Mis-Error

回归决策树场景：

1.

我们不去解释这些“分割评估”是如何工作的，而是首先看看我们想要解决的问题的基本原理：“分类和回归”。

示例 1。

   水果分类
≡≡≡≡≡≡≡≡≡≡≡≡
假设有一批水果，特征包含了「编号」、「颜色」、「大小」、「形状」、「口味」，
请根据这些特征建立决策树进行分类
≡≡≡≡≡≡≡≡≡≡≡≡
+--------+--------+--------+-------+-------+-------------+
|  编号   |   颜色  |  大小  | 形状   | 口味   |    分类     |
+--------+--------+--------+-------+-------+-------------+
|    1   |   绿   |   大    |   圆  |   甜  |    西瓜      |
|    2   |   绿   |   中    |   圆  |   甜  |    西瓜      |
|    3   |   绿   |   中    |   圆  |   酸  |    苹果      |
|    4   |   红   |   小    |   圆  |   酸  |    葡萄      |
|    5   |   红   |   小    |   圆  |   甜  |    樱桃      |
|    6   |   黄   |   中    |   长  |   甜  |    香蕉      |
|    7   |   绿   |   中    |   长  |   无  |    黄瓜      |
|    8   |   黄   |   中    |   圆  |   酸  |    柠檬      |
+--------+--------+--------+-------+-------+-------------+
> 注意其中有两个「西瓜」样本, 区别在于大小；（毕竟西瓜也有大有小嘛O(∩_∩)O）

S=\left\{ 1, 2, 3, 4, 5, 6, 7, 8 \right\} 表示一组未分类的水果样本。 我们用“熵”来衡量这个集合中的未知信息；

熵计算公式： (x) =- \sum_{i}^{n}{p(i)*(i)}

例如，对于没有任何处理的集合S：

其中，p(i)​​=2/8是西瓜的出现频率，其余6个水果的出现频率均为1/8。 综合计算，集合S的熵为2.75； 也就是说，我们至少需要 2.75 位。 只有对信息进行编码，才能完全区分所有水果；

现在我们随机选择一个特征进行分割：“颜色”，如下图

          +------------+
          |     S      |
          +-----+------+
                |
              +-|-+
     红   +----+|+------+  黄
         |      |       |
    +----+    绿|       +---+
    |           |           |
+---v---+   +---v---+   +---v---+
|       |   |       |   |       |
|  4 5  |   | 1 2 3 |   |  6 8  |
|       |   |   7   |   |       |
+-------+   +-------+   +-------+

这时候我们计算集合S经过决策树“排序”后，熵如何变化呢？

与之前不同的是，这次样本位于不同的叶节点。 可以单独计算叶子节点的熵，然后通过加权求和计算总熵；

\\熵（红）= -1/2 * log_2(1/2) * 2 = 1 \（消耗1bit）\\熵（黄）= -1/2 * log_2(1/2) * 2 = 1\ (消耗1bit) \\熵(绿色) = -2/4 * log_2(2/4) -1/4 * log_2(1/4) * 2 = 1.5\ (消耗1.5bit) \\ ((S) ) = 2/8* 熵（红色） + 4/8* 熵（绿色） + 2/8* 熵（黄色） = 1.25

可以发现，经过“颜色”分裂后，整体样本集的熵从2.75下降到1.25，即原来需要2.75位来对所有样本进行编码，现在只需要1.25位来对样本进行编码； 其中，我们通过这个“特征分裂”得到的“信息增益”或“熵减少”为1.5；

结论一：通过量化“熵减”/“信息增益”，我们可以在一定程度上评估决策树分裂的好处。 通过最大化“信息增益”，可以帮助我们快速构建决策树；

示例 2.

如果刚才使用的分割特征是“数字”而不是“颜色”，我们可以通过一次分割来区分所有样本：

          +------------+
          |     S      |
          +-----+------+
                |
                +----------------------+-------+
      1  +----+ | +-----+ 3            |       |
         |      |       |              |4      |5   .........
    +----+     2|       +---+          |       |
    |           |           |          |       |
   西瓜         西瓜        苹果        葡萄     樱桃
 

计算分割后的熵：

熵((S)) = \frac{1}{8} * log_2(1) * 8 = 0

我们发现，这种“分裂”的“信息增益/熵减少”已经达到了Max值（这也意味着，如果仅根据“信息增益/熵减少”来选择分裂特征，那么这类特征肯定会被首先选择进行拆分）。 然而，这个功能拆分并不是我们想要的。 虽然可以一次性区分出所有样本，但是“”分割的数量过多，并且每个叶子节点的样本数量非常少（本例中为1），使得模型容易“过拟合”。 结合”。

聪明的数学家想到了改变“信息增益”的计算公式，用“分裂”的次数作为惩罚项：

增益\比率 = \frac{(旧) - (新)}{split\ } \\ split\ = -\sum_{}^{}{\frac{|S_i|}{|S|}} * log_2\frac {|S_i|}{|S|}

在 split\ 项中，|S_i| 是叶节点的样本数，|S| 是样本总数。 当“分裂”的“”数量增多时，惩罚项就会变大，导致分裂算法有效地避免选择此类特征进行分裂。 ;

结论2.1：“信息增益”并不能完全反映“分裂”的有效性。 通过改造并利用“信息增益比”公式，可以有效避免使用“uuid”、“”等特殊值的决策树分裂策略。 大特征陷入“信息增益最大化”的误区；

结论2.2：特征分割应该使用“二叉树”还是“多树”？ 你也可以从这个例子中得到启发。 二叉树的特性使其具有抑制“过拟合”的功能；

示例 3.

TODO 请尽快添加下面的 *v* 参考^树