决策树（理论）
目录
一、何为决策树
决策树（Decision Tree）是一种分类和回归方法，是基于各种情况发生的所需条件构成决策树，以实现期望最大化的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。它的运行机制非常通俗易懂，因此被誉为机器学习中，最“友好”的算法。下面通过一个简单的例子来阐述它的执行流程。假设根据大量数据（含 3 个指标：天气、温度、风速）构建了一棵“可预测学校会不会举办运动会”的决策树（如下图所示）。
接下来，当我们拿到某个数据时，就能做出对应预测。
在对任意数据进行预测时，都需要从决策树的根结点开始，一步步走到叶子结点（执行决策的过程）。如，对下表中的第一条数据（ [ 阴天，寒冷，强 ] ）：首先从根结点出发，判断 “天气” 取值，而该数据的 “天气” 属性取值为 “阴天”，从决策树可知，此时可直接输出决策结果为 “举行”。这时，无论其他属性取值为什么，都不需要再执行任何决策（类似于 “短路” 现象）。
1、决策树的组成
决策树由结点和有向边组成。结点有两种类型：内部结点（圆）和叶结点（矩形）。其中，内部结点表示一个特征（属性）；叶结点表示一个类别。而有向边则对应其所属内部结点的可选项（属性的取值范围）。
在用决策树进行分类时，首先从根结点出发，对实例在该结点的对应属性进行测试，接着会根据测试结果，将实例分配到其子结点；然后，在子结点继续执行这一流程，如此递归地对实例进行测试并分配，直至到达叶结点；最终，该实例将被分类到叶结点所指示的结果中。
在决策树中，若把每个内部结点视为一个条件，每对结点之间的有向边视为一个选项，则从根结点到叶结点的每一条路径都可以看做是一个规则，而叶结点则对应着在指定规则下的结论。这样的规则具有互斥性和完备性，从根结点到叶结点的每一条路径代表了一类实例，并且这个实例只能在这条路径上。从这个角度来看，决策树相当于是一个 if-then 的规则集合，因此它具
有非常好的可解释性（白盒模型），这也是为什么说它是机器学习算法中最“友好”的一个原因。
2、决策树的构建
前面介绍了决策树的相关概念，接下来讨论如何构建一棵决策树。
决策树的本质是从训练集中归纳出一套分类规则，使其尽量符合以下要求：
- 具有较好的泛化能力；
- 在 1 的基础上尽量不出现过拟合现象。
注意到一件事：当目标数据的特征较多时，构建的具有不同规则的决策树也相当庞大（成长复杂度为 𝑂(𝑛!) ）。如当仅考虑 5 个特征时，就能构建出 5×4×3×2×1=120 种。在这么多树中，选择哪一棵才能达到最好的分类效果呢？实际上，这个问题的本质是：应该将样本数据的特征按照怎样的顺序添加到一颗决策树的各级结点中？这便是构建决策树所需要关注的问题核心。
如，在前面的例子中，为什么要先对“天气”进行划分，然后再是“温度”和“风速”呢（下图1）？可不可以先对“风速”进行划分，然后再是“温度”和“天气”呢（下图2）？
一种很直观的思路是：如果按照某个特征对数据进行划分时，它能最大程度地将原本混乱的结果尽可能划分为几个有序的大类，则就应该先以这个特征为决策树中的根结点。接着，不断重复这一过程，直到整棵决策树被构建完成为止。
基于此，引入信息论中的“熵”。
二、熵
1、熵的作用
熵（Entropy)是表示随机变量不确定性的度量。说简单点就是物体内部的混乱程度。比如下边的两幅图中，从 图1 到 图2 表示了熵增的过程。对于决策树的某个结点而言，它在对样本数据进行分类后，我们当然希望分类后的结果能使得整个样本集在各自的类别中尽可能有序，即希望某个特征在被用于分类后，能最大程度地降低样本数据的熵。
现在假设有这样一个待分类数据（如下图所示），若分类器 1 选择特征 𝑥1、分类器 2 选择特征 𝑥2 分别为根构建了一棵决策树，其效果如下：
则根据以上结果，可以很直观地认为，决策树 2 的分类效果优于决策树 1 。从熵的角度看，决策树 2 在通过特征 𝑥2 进行分类后，整个样本被划分为两个分别有序的类簇；而决策树 1 在通过特征 𝑥1 进行分类后，得到的分类结果依然混乱（甚至有熵增的情况），因此这个特征在现阶段被认为是无效特征。
2、熵的定义
故此，可以这样认为：构建决策树的实质是对特征进行层次选择，而衡量特征选择的合理性指标，则是熵。为便于说明，下面先给出熵的定义：设 𝑋 是取值在有限范围内的一个离散随机变量，其概率密度为：
下图展示了有关 与
的定义（其中，𝑘 是该集合中元素的类别数）：
则随机变量 𝑋 的熵定义为
从该式的定义可以看出，熵仅仅依赖于 𝑋 的分布而与其取值无关，所以也可以将 𝑋 的熵记为 𝐻(𝑝) 。
由于随机变量 𝑋 的概率密度 ,因此
。此时，若在
前加上负号，就有
。所以，
。当某个集合含有多个类别时，此时 𝑘 较大， 𝑝𝑖 的数量过多；且整体的 𝑝𝑖 都会因 𝑘 的过大而普遍较小，从而使得 𝐻(X) 的值过大。这正好符合“熵值越大，事物越混乱”的定义。
3、熵的计算
例如，现在有两个集合：𝐴 = { 1,2 } ， 𝐵 = { 1,2,3,4,5,6 } ，若以这两个集合为取值空间，则可分别计算其熵。
对于集合 𝐴 ，先计算其分布列为：
于是可得到其熵为：
对于集合 𝐵 ，计算其分布列为：
于是可得到其熵为：
结果显示，𝐴 集合的熵值要低一些，从两个集合的内容也能很轻易看出： 𝐴 集合只有两种类别，相对稳定；而 𝐵 集合中的类别过多，显得混乱。从另一个角度看：若视集合 𝐴 为“抛 1 次硬币的结果”；视集合 𝐵 为“掷 1 次骰子的结果”，则显然掷骰子的不确定性比投硬币的不确定性要高。
取极端情况，当集合中仅有一类元素时，如 𝐶 = { 1,1,1,1,1,1 } 时，此时其分布列为：
其熵为：
取到最小值，即表明当前集合状态不混乱，非常有序。
4、条件熵的引入
根据熵的定义，在构建决策树时我们可采用一种很简单的思路来进行“熵减”：每当要选出一个内部结点时，考虑样本中的所有“尚未被使用”特征，并基于该特征的取值对样本数据进行划分。即有：
对于每个特征，都可以算出“该特征各项取值对运动会举办与否”的影响（而衡量各特征谁最合适的准则，即是熵）。为此，引入条件熵。首先看原始数据集 𝐷 （共14天）的熵，该数据的标签只有两个（“举办”与“不举办”），且各占一半，故可算出该数据集的初始熵为：
对于每个特征，我们逐个分析，先从“天气”开始：
- 天气 = “晴天” 时，归类集合的熵为
；
- 天气 = “阴天” 时，归类集合的熵为
；
- 天气 = “雨天” 时，归类集合的熵为
。
从原始数据表可知，“天气” 特征取值为 “晴天”、“阴天”、“雨天” 的概率分别为 、
、
，因此，若以 “天气” 特征为现阶段的内部节点（用于划分的特征），则整个系统的熵值为：
5、条件熵的计算
在上面的计算中，我们将“天气”特征展开，以分别求解各取值对应集合的熵。实际上，该式的计算正是在求条件熵。条件熵 𝐻(𝑌 | 𝑋) 表示在已知随机变量 𝑋 的条件下随机变量 𝑌 的不确定性。它的数学定义是：若设随机变量 (𝑋, 𝑌) ，其联合概率密度为
则定义条件熵 𝐻(𝑌 | 𝑋) ：在给定 𝑋 的条件下 𝑌 的条件概率分布对 𝑋 的数学期望，即
其中， (表示指定集合中的元素类别) 。
按照这样的定义，可算出其余各特征的条件熵分别为：
特征取 “温度” 时：
特征取 “风速” 时：
特征取 “湿度” 时：
三、划分选择
从前面的讨论可以知道，决策树学习的关键在于：如何选择最优划分属性。一般而言，随着划分过程的不断进行，我们自然希望决策树各分支结点所包含的样本尽可能属于同一类别，即结点的 “纯度” (purity) 越来越高。下面介绍几类较为主流的评选算法。
1、信息增益（ ID3 算法选用的评估标准）
信息增益 𝑔(𝐷, 𝑋) ：表示某特征 𝑋 使得数据集 𝐷 的不确定性减少程度，定义为集合 𝐷 的熵与在给定特征 𝑋 的条件下 𝐷 的条件熵 𝐻(𝐷 | 𝑋) 之差，即
从该式可以看出，信息增益表达了样本数据在被分类后的专一性。因此，它可以作为选择当前最优特征的一个指标。
根据前面的计算结果，可知集合 𝐷 的熵 𝐻(𝐷) = 0.6931 ，特征 “天气”、“温度”、“风速”、“湿度” 的条件熵分别为 𝐻(D | X天气) = 0.3961 、𝐻(D | X温度) = 0.6931、𝐻(D | X风速) = 0.5983、𝐻(D | X湿度) = 0.6315。根据这些数据，可以算出全部特征在被用于分类时，各自的信息增益：
上面各特征求得的信息增益中，“天气” 特征对应的是最大的。也就是说，如果将 “天气” 作为决策树的第一个划分特征，系统整体的熵值将降低 0.297，是所有备选特征中效果最好的。因此，根据 “学校举办运动会的历史数据” 构建决策树时，根节点最好取 “天气” 特征。
接下来，在 “晴天” 中的数据将按上面的流程继续执行，直到构建好一棵完整的决策树（或达到指定条件）。不过此时，备选特征只剩下 “温度”、“风速” 和 “湿度” 3 项（往后，每当决策树的深度加 1 时，都会减少一个）。
2、信息增益率（ C4.5 算法选用的评估标准）
以信息增益作为划分数据集的特征时，其偏向于选择取值较多的特征。比如，当在学校举办运动会的历史数据中加入一个新特征 “编号” 时，该特征将成为最优特征。因为给定 “编号” 就一定知道那天是否举行过运动会，因此 “编号” 的信息增益很高。
按 “编号” 进行划分得到的决策树：
其条件熵：
信息增益：
但实际我们知道，“编号” 对于类别的划分并没有实际意义。故此，引入信息增益率。
信息增益率 𝑔𝑅(𝐷, 𝑋) 定义为其信息增益 𝑔(𝐷, 𝑋) 与数据集 𝐷 在特征 𝑋 上值的熵 𝐻𝑋(𝐷) 之比，即：
其中， ， 𝑘 是特征 𝑋 的取值类别个数。从上式可以看出，信息增益率考虑了特征本身的熵（此时，当某特征取值类别较多时，𝑔𝑅(𝐷, 𝑋) 式中的分母也会增大），从而降低了 “偏向取值较多的特征” 这一影响。根据该式，可得到基于各特征划分的信息增益率如下：
从上面的结果可以看出，信息增益率能明显降低取值较多的特征偏好现象，从而更合理地评估各特征在划分数据集时取得的效果。因此，信息增益率是现阶段用得较多的一种算法。
3、基尼系数（ CART 算法选用的评估标准）
从前面的讨论不难看出，无论是 ID3 还是 C4.5 ，都是基于信息论的熵模型出发而得，均涉及了大量对数运算。能不能简化模型同时又不至于完全丢失熵模型的优点呢？分类回归树（Classification and Regression Tree，CART）便是答案，它通过使用基尼系数来代替信息增益率，从而避免复杂的对数运算。基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。注：这一点和信息增益（率）恰好相反。
在分类问题中，假设有 𝑘 个类别，且第 𝑘 个类别的概率为 𝑝𝑘 ，则基尼系数为
对于给定数据集 𝐷 ，假设有 𝑘 个类别，且第 𝑘 个类别的数量为 𝐶𝑘 ，则该数据集的基尼系数为
从上式可以看出，基尼系数表征了样本集合里一个随机样本分类错误的平均概率。例如：
如果数据集 𝐷 根据特征 𝑋 的取值将其划分为 {𝐷1,𝐷2, … ,𝐷m} ，则在特征 𝑋 的条件下，划分后的集合 𝐷 的基尼系数为：
由于基尼系数 𝐺𝑖𝑛𝑖(𝐷) 表示集合 𝐷 的不确定性，则基尼系数 𝐺𝑖𝑛𝑖(𝐷, 𝑋) 表示 “基于指定特征 𝑋 进行划分后，集合 𝐷 的不确定性”。该值越大，就表示数据集 𝐷 的不确定性越大，也就说明以该特征 进行划分越容易分乱。基于前面各特征对数据集的划分，可得到其对应的基尼系数为：
4、基尼增益
同信息增益一样，如果将数据集 𝐷 的基尼系数减去数据集 𝐷 根据特征 𝑋 进行划分后得到的基尼系数
就得到基尼增益（系数）。显然，采用越好的特征进行划分，得到的基尼增益也越大。基于前面各特征对数据集的划分，可得到其对应的基尼增益。
步骤一：先算出初始数据集合 D 的基尼系数。
步骤二：计算基尼系数计算基尼增益率。
可见，基尼增益在处理诸如 “编号” 这一类特征时，仍然会认为其是最优特征（此时，可采取类似信息增益率的方式，选用基尼增益率 ）。但对常规特征而言，其评估的合理性还是较优的。
5、基尼增益率
基尼增益率 𝐺𝑅(𝐷, 𝑋) 定义为其尼基增益 𝐺(𝐷, 𝑋) 与数据集 𝐷 在特征 𝑋 上的取值个数之比，即
容易看出，基尼增益率考虑了特征本身的基尼系数（此时，当某特征取值类别较多时， 𝐺𝑅(𝐷, 𝑋) 式中的分母也会增大），从而降低了 “偏向取值较多的特征” 这一影响。根据该式，可得到基于各特征划分的基尼增益率如下：
从上面的结果可以看出，基尼增益率能明显降低取值较多的特征偏好现象，从而更合理地评估各特征在划分数据集时取得的效果。
四、决策树中的连续值处理
在前面的数据集中，各项特征（以及标签）均为离散型数据，但有时处理的数据对象可能会含有连续性数值，为了解决这一问题，我们可以对数据进行离散化处理。此时，可把连续取值的数据值域划分为多个区间，并将每个区间视为该特征的一个取值，如此就完成了从连续性数据到离散性数据的转变。例如，当 “学校举办运动会的历史数据” 为下表时，我们可根据这些数据（并结合相关知识）将温度特征的取值作以下划分：
将 “温度” 属性进行分区处理：
对于一些尚无明确划分标准的特征（如下面是一组无具体含义的数据）：
我们要如何将这些数据进行离散化呢？一种较为直接的方式是：对原数据进行排序，再取任意相邻值的中位点作为划分点，例如：可以 65 和 72 的中位点（）进行划分。对数据进行离散化处理是希望划分之后的数据集更加纯净，所以这里依然可以用信息熵来作为对划分的度量，并选取划分效果最好的点作为划分点。
对于长度为 的数据，其备选中位点有
个：
我们需要算出这 个备选中位点划分出的数据集的信息熵，信息熵最小的就是最优划分点。
在评估决策树执行分类或回归任务的效果时，其方式也有所不同。对于分类任务，可用熵或基尼系数；对于回归任务，则需要用方差来衡量最终落到某个叶子节点中的数值之间的差异（方差越小则说明数据之间的差异越小，越应该被归类到一类）。注：决策树在执行回归任务时，其最终反馈的结果应当取某个叶子结点中所有数的均值。
五、决策树中的预剪枝处理（正则化）
对于决策树而言，当你不断向下划分，以构建一棵足够大的决策树时（直到所有叶子结点熵值均为 0），理论上就能将近乎所有数据全部区分开。所以，决策树的过拟合风险非常大。为此，需要对其进行剪枝处理。
常用的剪枝策略主要有两个：
- 预剪枝；构建决策树的同时进行剪枝处理（更常用）；
- 后剪枝：构建决策树后再进行剪枝处理。
预剪枝策略可以通过限制树的深度、叶子结点个数、叶子结点含样本数以及信息增量来完成。
1、限制决策树的深度
下图展示了通过限制树的深度以防止决策树出现过拟合风险的情况。
2、限制决策树中叶子结点的个数
下图展示了通过限制决策树中叶子结点的个数以防止决策树出现过拟合风险的情况。
3、限制决策树中叶子结点包含的样本个数
下图展示了通过限制决策树中叶子结点包含的样本个数以防止决策树出现过拟合风险的情况。
4、限制决策树的最低信息增益
下图展示了通过限制决策树中叶子结点包含的样本个数以防止决策树出现过拟合风险的情况。
六、决策树中的后剪枝处理
后剪枝的实现依赖如下衡量标准：
其中， 𝐿𝛼(𝑇) 表示最终损失（希望决策树的最终损失越小越好），𝐺𝑖𝑛𝑖(𝑇) 表示当前结点的熵或基尼系数， |𝑇| 表示当前结点包含的数据样本个数， 𝑇𝑙𝑒𝑎𝑓 表示当前结点被划分后产生的叶子结点个数（显然，叶子节点越多损失越大），𝛼 是由用户指定的偏好系数（ 𝛼 越大代表我们对 “划分出更多的子结点” 的惩罚越大，即越不偏好于决策树的过分划分，因此有助于控制模型过拟合；反之，𝛼 越小表示我们对 “划分出更多的子结点” 的惩罚越小，即更希望决策树能在训练集上得到较好的结果，而不在意过拟合风险）。
下面以一幅图像来展示后剪枝处理的算法原理：
七、实战部分
本文主要介绍了决策树的构建原理，其中涵盖了大量的有关熵、信息增益的内容（这两部分也正是决策树的精髓所在，只有深刻理解了这两方面的知识才能真正地理解决策树）。最后，文章还介绍了如何对决策树进行剪枝操作。有关剪枝操作的内容，可通过做实验的方式对其进行详细理解。下面附上实战链接：
实战链接
END
文章出处登录后可见！
