机器学习之决策树

决策树是一个树结构。每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。

作为一个基本的机器学习算法，目前很多实用性很强的著名算法都是基于决策树构建的，比如 XGBoost, LightGBM, GBDT, Adaboost, Random Forest。可参考 ->集成学习

上面说的大概有些抽象，举一个例子，下面是一个数据集，我们需要根据天气属性判断是否有人会打高尔夫球，其中：

• 天气状况有晴、云、雨。
• 气温用华氏温度表示。
• 湿度用百分比表示。
• 风度用有风无风表示。

假设在树的第一层选用 outlook 属性作为切分的话，我们可以划分成如下图所示的这样一棵树：

在进行节点切分的时候我们有四个选择，基于 outlook/temperature/humidity/windy，那么我们到底应该选择哪一个进行切分的？

对于这种分类问题，通常有三种方式，信息增益、信息增益率、基尼系数，分别对应三大算法：id3、c4.5、cart。下面我们来具体看一下。

p.s: 本文主要介绍决策树的三种构建算法，具体的优化细节比如剪枝以及处理连续值缺失值等问题，后续在补充。

信息熵

在分析信息增益之前，我们先来看一下信息熵。在信息论中，随机离散事件出现的概率存在着不确定性。为了衡量这种信息的不确定性，信息学之父香农引入了信息熵（entropy）的概念，并给出了计算信息熵的数学公式：

p(i|t) 代表了节点 t 为分类 i 的概率，其中 log2 为取以 2 为底的对数。当不确定性越大时，信息熵也就越高。

假设有 2 个集合：

1. 集合 1：5 个男生，1 个女生。
2. 集合 2：3 个男生，3 个女生。

将男生看做类别 1，女生看做是类别 2。在集合一种类别 1 的概率是 1/6，类别 2 的概率为 5/6，所以可以算出信息熵为：

在集合二中，类别 1 和类别 2 的概率都是 0.5，所以信息熵为：

可以看到， 信息熵越大，纯度越低 。当集合中的所有样本均匀混合时，信息熵最大，纯度最低。

ID3

信息增益指的就是划分可以带来纯度的提高，信息熵的下降。它的计算公式，是父亲节点的信息熵减去所有子节点的信息熵。

ID3 生成算法核心是在决策树的每个结点上应用信息增益准则选择特征，递归地构建决策树。

• 从根结点开始，计算结点所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征划分出子结点。
• 再对子结点递归地调用以上方法，构建决策树。
• 直到所有特征的信息增益均很小或者没有特征可以选择为止，最后得到一个决策树 。如果不设置特征信息增益的下限，则可能会使得每个叶子都只有一个样本点，从而划分得太细。

类比上面的高夫球例子，在第一次拆分的时候，a 有四个取值：outlook/temperature/humidity/windy，分别计算出这四个属性下根节点的信息增益，选择让信息增益取值最大来拆分。类比树的第二层、第三层也是同理。

C4.5

信息增益率定义如下：

因为 ID3 在计算的时候，倾向于选择取值多的属性，也就是说 v 越多的话，信息增益越大。为了避免这个问题，C4.5 采用信息增益率的方式来选择属性。信息增益率 = 信息增益 / 属性熵。当属性有很多值的时候，相当于被划分成了许多份，虽然信息增益变大了，但是对于 C4.5 来说，属性熵也会变大，所以整体的信息增益率并不大。

CART

分类树

CART 树采用基尼指数选择最优特征。基尼系数反应了样本的不确定程度。当基尼系数越小的时候，说明样本之间的差异小，不确定程度低。CART 算法在构建分类树的时候，会选择基尼系数最小的属性作为属性划分。

表示 t 属于 的概率，节点 t 的基尼系数等于 1 减去各类别概率的平方和。下面举一个具体的例子来说明一下：

• 集合 1：六个男生。所以 。

• 集合 2：三个男生，三个女生。 ， ，所以 。

集合1的基尼系数更小，相比集合2更稳定。

在 CART 算法中，假设基于某属性对集合 进行分裂，划分成了上面集合一 和集合二 。集合 D 的基尼系数为：

也就是：

回归树

前面提到的 id3/c4.5 算法都是 n 叉树，cart 树是一棵二叉树，所以在决策时，只能做是或否的决策，即使一个 feature 有多个取值。

上面讲的基尼系数可以应用到分类场景中，对于回归场景，我们可以使用样本的离散程度来评价不纯度。样本离散程度的计算方式是，先计算所有样本的均值，然后计算每个样本值到均值的差值。假设 x 为样本个体，均值为 u。有两种计算方式，一种是去差值的绝对值，一种是根据方差。

绝对值计算：

方差为每个样本值减去样本均值的平方和除以样本个数：

正则化

减枝

基于训练样本来生成决策树时，如果不做任何限制，那么就会完全过拟合，这样决策树就没有任何泛化能力了。如何防止过拟合呢？通常可以进行预减枝和后减枝。

预减枝

预减枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化能力（在训练时加入验证集随时进行泛化验证）的提升，则停止划分并将当前结点标记为叶节点。

预剪枝抑制了很多分支的展开，这降低过拟合的同时还减少了训练时间，但是却存在欠拟合的风险；预剪枝基于贪心策略，往往可以达到局部最优解却不能达到全局最优解，也就是说预剪枝生成的决策树不一定是最佳的决策树。XGBoost 和 LightGBM 使用的树就是预剪枝的 CART 决策树，这能保证他们的训练速度较快。

后减枝

后剪枝则是先从训练集中生成一颗完整的树，然后自底向上对非叶节点进行考察，若该节点对应的子树替换为叶节点能够提升泛化能力，则进行剪枝将该子树替换为叶节点，否则不剪枝。后剪枝技术通常比预剪枝保留了更多的分支，它是自底向上的剪枝，因此它的欠拟合风险较小，泛化能力往往优于预剪枝，然而因为总是要完全生长一棵树，这就要花费很多时间训练了，数据集规模大、维度高时并不适用实际应用。