Decision Trees
笔记作者：BrickLoo
决策树的使用
在前面的文章中，当我们使用模型处理问题时，通常会先对各种因素的取值加权评估，再根据最终的计算结果做出相应决策。然而，
- 这要求我们使用数值描述属性，并使用这个数值进行加权计算，因此在设计一个合理的数值描述可能是比较麻烦的事情；
- 同时，人们在做出一个决策的时候，通常是对属性逐一分析和筛选，不需要如此复杂的加权计算。
因此，面对一些比较简单的问题，我们可以设计一个对属性参数逐一分析的模型，并使用树状结构描述这个分析流程，这样
- 既方便了计算，
- 也更容易处理具有离散类别的属性，
- 还很容易将其实现为人们容易理解的程序；
- 同时，由于符合人们的思维方式，一些问题上还能拥有不错的性能效果。
这，就是决策树。
树中，每一个节点代表当前需要分析的属性，节点下的每一个分支表示这个属性的取值在相应条件下进入的分支，分支之下的节点则是根据属性的取值做出了判断后，下一个要分析的属性。直到我们能通过各种属性的分析判断出结果后，我们会进入树的叶节点，并用它表示这个分支最后能取到什么值，应当做出什么决策。
因此，当我们使用决策树进行决策的时候，我们实际上是在不断地进行条件判断，并通过分类处理来代替加权计算。
决策树的构建
Hunt 算法
这个算法大致介绍了从数据集构造出一颗决策树的思路。当我们拥有一些数据时，我们可以以一个节点为根节点，然后
- 判断数据是否无需划分：如果这些数据属于同一个类别，我们就可以用当前节点作为叶节点，并在节点中记录类别信息。当我们以后到达这个叶节点时，就可以判断样本属于这个类别。
- 判断数据是否无法划分：如果没有充足的特征作为划分条件（因为通常情况下我们不会再次根据使用过的特征进行分类）或者没有数据（当一个节点拥有不止两个分支时，可能会存在没有数据的分支），我们可以用当前节点作为叶节点，并以样本数最多的类别或者默认类别作为其类别。
- 划分数据：经过上面两个判断，我们可以放心地挑选一个属性及其合适的条件进行数据划分，并在当前节点记录用于划分的属性和条件。然后，我们可以对每个分支上的子节点及其对应的数据重新使用 Hunt 算法。
划分数据策略
如何划分
对于属性的参数值类型，我们可以将其分为连续的和离散的两种。而从数据划分的分支数量来看，划分方式可以是两个分支或者多个分支。
对于取值连续的属性参数，我们的策略通常是设定阈值来对样本进行分类（例如先对样本中的取值进行排序，再取任意两个相邻数值的中间值作为阈值），并通过阈值数量来控制分支数量。
而对于取值离散的属性参数，比较简单的数据划分思路就是按照离散参数值的不同取值（例如类别名字）将数据划分进多个分支；不过，通常情况下，我们会希望数据能被划分进仅仅两个分支中，这时我们可以采用“是否为某一个取值”的条件，按照多分类问题中 one-versus-the-rest 的思想来处理。
如何评估划分质量
在挑选阈值或者离散参数值作为划分条件时，不同的选择也会有不同的模型性能。为了找到最佳的划分条件，我们需要找到一些指标来评估哪种划分条件更好。由于挑选决策树的数据划分条件时，我们还没有完整的决策树模型能拿来测试其在测试数据集上的性能，因此我们需要另外设计指标进行验证。常见的指标设计包括信息增益和 Gini 系数，它们都是经过实践检验的优秀设计。
信息增益
读者可以结合以下几篇文章理解信息熵与信息增益：
通俗理解信息熵
深入理解信息熵
信息熵
信息增益、信息增益率、Gini系数
Gini 系数
读者可以结合以下两篇文章理解 Gini 系数的公式：
基尼系数与基尼不纯度
GINI系数的含义与推导
个人将其理解为简化版的信息熵。
如何避免过拟合
要想避免决策树的过拟合，我们就需要尝试忽略无关紧要或是细枝末节的判断条件，避免模型学到一些不太合理的判断依据。实现这个目标的思路可以分为 Pre-pruning 和 Post-pruning 两种：
- Pre-pruning
- 如果一个节点中的样本数量少于一定的阈值，也可以不再根据特征进行数据划分，因为此时的规律不一定能够反映大样本量下的特征；
- 可以通过 $\chi^2$ 检验等方法判断样本的类别分布与当前可以用来划分数据的特征是否都不相关，如果都不相关则不再进行数据划分；
- 观察信息增益和 Gini 指数等评估数据划分质量的参数，如果提高不明显时也可以提前停止数据划分，并根据样本频率来决定类别。
- Post-pruning
- 首先完整地构建决策树，并评估其在验证集上的性能；
- 从决策树的细枝末节开始裁剪，尝试将最末的内部分支节点替换成根据样本频率来决定类别的叶节点；
- 重新评估模型在验证集上的性能，如果有助于提高性能就采用裁剪后的决策树，否则撤回裁剪操作；
- 反复回到第 2 步的尝试直到无法通过裁剪提高性能。