决策树（上）—— ID3、C4.5、CART

最近想学习一下LightGBM，一直对决策树不是很熟悉，所以学习一下~

本文主要参考了阿泽作者的笔记，对于不理解的地方，我会添加个人注释。

决策树是一个非常常见并且优秀的机器学习算法，它易于理解、可解释性强，其可作为分类算法，也可用于回归模型。

预备知识

这部分内容主要参考了决策树算法-理论篇-如何计算信息纯度 。

信息熵

定义

信息熵（一般用H 表示），度量信息熵的单位是比特。就是说，信息量的多少是可以量化的。一条信息量的多少与信息的不确定性有关，可以认为，信息量就等于不确定性的多少（信息的不确定度）。

设$X$是一个取有限个值的离散随机变量，其信息熵的计算公式如下：

$$\mathrm{H}(\mathrm{X})=-\sum_{i=1}^{n} p\left(x_{i}\right) \log p\left(x_{i}\right)$$

其中，该公式的含义是：

• 待分类的事物可以分在多个分类中，这里的$n$就是分类的数目
• $H(X)$ 表示熵，数学含义是，所有类别包含的信息期望值
• $\log p\left(x_{i}\right)$表示符号的信息值，$p\left(x_{i}\right) $是选择该类的概率，$p(x_i)=P(X=x_i), i=1,2,\dots, n$
• 公式中的$log$一般以2为底
• 由定义可知，熵只依赖于$X$的分布，而与$X$的取值无关，所以也可将$X$的熵记作$H(p)$。

总之，就是要知道，信息量的多少是可以用数学公式计算出来的，用信息论中的专业术语就叫做信息熵。信息熵越大，信息量也就越大。

下面这张图片解释了信息熵的由来。

计算

假设我们有如下数据集：

序号	条件:天气晴朗?	条件:是否刮风?	结果:去踢球吗?
1	是	否	去
2	是	是	不去
3	否	是	不去
4	否	否	不去

可以看到这个表格中有4 行（第一行表头不算），4 列数据。一般在机器学习中，最后一列称为目标(target)，前边的列都称为特征(features)。

根据表格，我们可以知道，所有的分类共有2 种，也就是“去” 和“不去”，“去”出现了1 次，“不去”出现了3 次。

分别计算“去” 和“不去” 出现的概率：

• P(去) = 1 / 4 = 0.25
• P(不去) = 3 / 4 = 0.75

然后，根据熵的计算公式来计算“去”和“不去” 的信息熵，其中log 以2 为底：

• H(去) = 0.25 * log 0.25 = -0.5
• H(不去) = 0.74 * log 0.75 = -0.31127812445913283

所以，整个表格含有的信息量就是：

• H(表格) = -(H(去) + H(不去)) = 0.81127812445913283

代码实现

将计算信息熵的过程用Python 代码实现，如下：

import math

# 本函数用于计算一组数据的信息熵
# data_set 是一个列表，代表一组数据
# data_set 的元素data 也是一个列表
def calc_ent(data_set):
    labels = {} # 用于统计每个label 的数量
    
    for data in data_set:
        label = data[-1]	# 只用最后一个元素做计算
        if label not in labels:
            labels[label] = 0

        labels[label] += 1 

    ent = 0 # 熵
    n = len(data_set)   # 数据条数

    # 计算信息熵
    for label in labels:
        prob = float(labels[label]) / n # label 的概率
        ent -= prob * math.log(prob, 2) # 根据信息熵公式计算

    return ent

下面用该函数来计算表格的信息熵：

# 将表格转化为 python 列表
# "yes" 表示"去"
# "no" 表示"不去"
data_set = [['yes'], ['no'], ['no'], ['no']] 
ent = calc_ent(data_set)
print(ent)	# 0.811278124459

可见，用代码计算出来的结果是 0.811278124459，跟我们手算的结果 0.81127812445913283 是一样的（保留的小数位数不同）。

信息纯度

信息的纯度与信息熵成反比，可以将信息熵理解为 “不纯度” 。

• 信息熵越大，信息量越大，数据不确定性越高，信息越杂乱，纯度越低。意味着分类的各个类型占比近似很难区分
• 信息熵越小，信息量越小，数据不确定性越低，信息越规整，纯度越高。意味着在数据集里我们要分类的某一种类型占比很高

举一个例子，比如我们想分类A和B，用公式量化来体现就是：

1）如果分类结果中A和B各占50%，那么意味着分类结果很失败，这无异于随机地乱猜，完全没起到分类效果，公式计算结果如下：

2）如果分类结果中A占比100%，B占比0%或者B占比100%，A占比0%时，那么意味着分类很成功，因为我们成功地区分了A和B，我们就说此时的纯度很高，公式计算结果如下：

条件熵

条件熵$H(Y|X)$表示在已知随机变量$X$的条件下随机变量$Y$的不确定性。随机变量$X$给定的条件下随机变量$Y$的条件熵$H(Y|X)$，定义为$X$给定条件下$Y$的条件概率分布的熵对$X$的数学期望。

$$H(Y \mid X)=\sum_{i=1}^{n} p(x_i) H\left(Y \mid X=x_{i}\right)$$

信息增益

定义

信息增益就是，在根据某个属性划分数据集的前后，信息量发生的变化。

信息熵代表不纯度，只要将分类前后的不纯度相减，那就可以得到一种 “纯度提升值” 的指标，我们把它叫做 “信息增益”。

特征$A$对训练数据集$D$的信息增益$Gain(D,A)$，定义为集合$D$的经验熵$H(D)$与特征$A$给定条件下$D$的条件熵$H(D|A)$之差。信息增益的计算公式如下：

$$Gain(D,A)=H(D)-H(D|A)$$

所有子节点的信息熵会按照子节点在父节点中的出现的概率来计算，这叫做归一化信息熵。

信息增益的目的在于，将数据集划分之后带来的纯度提升，也就是信息熵的下降。如果数据集在根据某个属性划分之后，能够获得最大的信息增益，那么这个属性就是最好的选择。

所以，我们想要找到根节点，就需要计算每个属性作为根节点时的信息增益，那么获得信息增益最大的那个属性，就是根节点。

计算

信息增益等于按照某个属性划分前后的信息熵之差。它的计算方式简单来说，先基于特征A进行划分，再基于目标变量进行划分，这是一个嵌套的过程。

这个表格划分之前的信息熵我们已经知道了，就是我们在上面计算的结果：

• H(表格) = 0.81127812445913283。

接下来，我们计算按照“天气晴朗”划分的信息增益。按照“天气晴朗”划分后有两个表格。

表格1，“天气晴朗”的值为“是”：

序号	条件:天气晴朗?	条件:是否刮风?	结果:去踢球吗?
1	是	否	去
2	是	是	不去

分类共有2 种，也就是“去” 和“不去”，“去”出现了1 次，“不去”出现了1 次。

所以，“去” 和“不去” 出现的概率均为0.5：

• P(去) = P(不去) = 1 / 2 = 0.5

然后，“去”和“不去” 的信息熵，其中log 以2 为底：

• H(去) = H(不去) = 0.5 * log 0.5 = -0.5

所以，表格1 含有的信息量就是：

• H(表格1) = -(H(去) + H(不去)) = 1

表格2，“天气晴朗”的值为“否”：

序号	条件:天气晴朗?	条件:是否刮风?	结果:去踢球吗?
3	否	是	不去
4	否	否	不去

所有的分类只有1 种，是“不去”。所以：

• P(不去) = 1

然后，“不去” 的信息熵，其中log 以2 为底：

• H(不去) = 1 * log 1 = 0

所以，表格2 含有的信息量就是：

• H(表格2) = 0

总数据共有4 份：

• 表格1 中有2 份，概率为 2/4 = 0.5
• 表格2 中有2 份，概率为 2/4 = 0.5

所以，最终按照“天气晴朗”划分的信息增益为：

• G(天气晴朗) = H(表格) - (0.5*H(表格1) + 0.5*H(表格2)) = H(表格) - 0.5 = 0.31127812445913283。

决策树概述

不同于逻辑回归，决策树属于非线性模型，可以用于分类，也可用于回归。它是一种树形结构，可以认为是if-then规则的集合，是以实例为基础的归纳学习。基本思想是自顶向下，以信息增益（或信息增益比，基尼系数等）为度量构建一颗度量标准下降最快的树，每个内部节点代表一个属性的测试，直到叶子节点处只剩下同一类别的样本。它的决策流程如下所示：

ID3

ID3 算法是建立在奥卡姆剃刀（用较少的东西，同样可以做好事情）的基础上：越是小型的决策树越优于大的决策树。

奥卡姆剃刀：“如无必要，勿增实体”，即“简单有效原理”。

思想

从信息论的知识中我们知道：信息熵越大，从而样本纯度越低。ID3 算法的核心思想就是以信息增益来度量特征选择，选择信息增益最大的特征进行分裂。算法采用自顶向下的贪婪搜索遍历可能的决策树空间（C4.5 也是贪婪搜索）。 其大致步骤为：

1. 初始化特征集合和数据集合；
2. 计算数据集合信息熵和所有特征的条件熵，选择信息增益最大的特征作为当前决策节点；
3. 更新数据集合和特征集合（删除上一步使用的特征，并按照特征值来划分不同分支的数据集合）；
4. 重复 2，3 两步，若子集值包含单一特征，则为分支叶子节点。

从这个过程，我们可以发现：最开始选择的特征肯定是提供信息量最大的，因为它是遍历所有特征后选择的结果。因此，按照决策过程中特征从上到下的顺序，我们也可以将特征的重要程度进行排序。这也就解释了为什么树模型有feature_importance这个参数了。

划分标准

ID3 使用的分类标准是信息增益，它表示得知特征 A 的信息而使得样本集合不确定性减少的程度。

数据集的信息熵：

$$H(D)=-\sum_{k=1}^{K} \frac{\left|C_{k}\right|}{|D|} \log _{2} \frac{\left|C_{k}\right|}{|D|}$$

其中$C_k$表示集合$D$中属于第$k$类样本的样本子集。

针对某个特征 $A$，对于数据集 $D$ 的条件熵 $H(D|A)$为：

$$\begin{aligned} H(D \mid A) &=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} H\left(D_{i}\right) \\ &=-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|}\left(\sum_{k=1}^{K} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|} \log _{2} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|}\right) \end{aligned}$$

其中 $D_i$ 表示 $D$ 中特征 $A$ 取第$ i$ 个值的样本子集，$ D_{ik}$ 表示$ D_i $中属于第$ k $类的样本子集。

信息增益 = 信息熵 - 条件熵：

$$Gain(D,A)=H(D)-H(D|A)$$

信息增益越大表示使用特征 A 来划分所获得的“纯度提升越大”。

缺点

• ID3 没有剪枝策略，容易过拟合；
• 信息增益准则对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于 1。这是因为当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，条件熵越小，因此划分之后的熵更低，由于划分前的熵是一定的，因此信息增益更大，因此信息增益比较偏向取值较多的特征；
• 只能用于处理离散分布的特征；
• 没有考虑缺失值。

C4.5

C4.5 算法最大的特点是克服了 ID3 对特征数目的偏重这一缺点，引入信息增益率来作为分类标准。

思想

C4.5 相对于 ID3 的缺点对应有以下改进方式：

• 引入悲观剪枝策略进行后剪枝；
• 引入信息增益率作为划分标准；
• 将连续特征离散化，假设 n 个样本的连续特征 A 有 m 个取值，C4.5 将其排序并取相邻两样本值的平均数共 m-1 个划分点，分别计算以该划分点作为二元分类点时的信息增益，并选择信息增益最大的点作为该连续特征的二元离散分类点。

对于缺失值的处理可以分为两个子问题：

• 问题一：在特征值缺失的情况下进行划分特征的选择？（即如何计算特征的信息增益率）

  C4.5 的做法是：对于具有缺失值特征，用没有缺失的样本子集所占比重来折算；

• 问题二：选定该划分特征，对于缺失该特征值的样本如何处理？（即到底把这个样本划分到哪个结点里）

  C4.5 的做法是：将样本同时划分到所有子节点，不过要调整样本的权重值，其实也就是以不同概率划分到不同节点中。

划分标准

利用信息增益率可以克服信息增益的缺点，其公式为

$$\begin{aligned} Gain_{ratio}(D,A)&=\frac{Gain(D,A)}{H_A(D)} \\ H_A(D) &=-\sum_{i=1}^{n}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|} \end{aligned} \\$$

$H_A(D)$ 称为特征 $A$ 的固有值，$n$是特征$A$取值的个数。它的计算公式与熵类似，只不过数据集的熵是依据类别进行划分的，而这里是将特征A取值相同的样本划分到同一个子集中，来计算熵。

信息增益比本质： 是在信息增益的基础之上乘上一个惩罚参数——分裂信息(Split information)。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。

这里需要注意，信息增益率对可取值较少的特征有所偏好（分母越小，整体越大），因此 C4.5 并不是直接用增益率最大的特征进行划分，而是使用一个启发式方法：先从候选划分特征中找到信息增益高于平均值的特征，再从中选择增益率最高的。

剪枝策略

为什么要剪枝：过拟合的树在泛化能力的表现非常差。

预剪枝

在节点划分前来确定是否继续增长，及早停止增长的主要方法有：

• 节点内数据样本低于某一阈值；
• 所有节点特征都已分裂；
• 节点划分前准确率比划分后准确率高。

预剪枝不仅可以降低过拟合的风险而且还可以减少训练时间，但另一方面它是基于“贪心”策略，会带来欠拟合风险。

后剪枝

在已经生成的决策树上进行剪枝，从而得到简化版的剪枝决策树。

C4.5 采用的悲观剪枝方法，用递归的方式从低往上针对每一个非叶子节点，评估用一个最佳叶子节点去代替这课子树是否有益。如果剪枝后与剪枝前相比其错误率是保持或者下降，则这棵子树就可以被替换掉。C4.5 通过训练数据集上的错误分类数量来估算未知样本上的错误率。

后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但同时其训练时间会大的多。

缺点

• 剪枝策略可以再优化；
• C4.5 用的是多叉树，用二叉树效率更高；
• C4.5 只能用于分类；
• C4.5 使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；
• C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。

CART

ID3 和 C4.5 虽然在对训练样本集的学习中可以尽可能多地挖掘信息，但是其生成的决策树分支、规模都比较大，CART 算法的二分法可以简化决策树的规模，提高生成决策树的效率。

思想

CART 包含的基本过程有分裂，剪枝和树选择。

• 分裂：分裂过程是一个二叉递归划分过程，其输入和预测特征既可以是连续型的也可以是离散型的，CART 没有停止准则，会一直生长下去；
• 剪枝：采用代价复杂度剪枝，从最大树开始，每次选择训练数据熵对整体性能贡献最小的那个分裂节点作为下一个剪枝对象，直到只剩下根节点。CART 会产生一系列嵌套的剪枝树，需要从中选出一颗最优的决策树；
• 树选择：用单独的测试集评估每棵剪枝树的预测性能（也可以用交叉验证）。

CART 在 C4.5 的基础上进行了很多提升。

• C4.5 为多叉树，运算速度慢，CART 为二叉树，运算速度快；
• C4.5 只能分类，CART 既可以分类也可以回归；
• CART 使用 Gini 系数作为变量的不纯度量，减少了大量的对数运算；
• CART 采用代理测试来估计缺失值，而 C4.5 以不同概率划分到不同节点中；
• CART 采用“基于代价复杂度剪枝”方法进行剪枝，而 C4.5 采用悲观剪枝方法。

划分标准

熵模型拥有大量耗时的对数运算，基尼指数在简化模型的同时还保留了熵模型的优点。基尼指数代表了模型的不纯度，基尼系数越小，不纯度越低，特征越好。所以决策树分裂选取Feature的时候，要选择使基尼指数最小的Feature，但注意信息增益（率）则是选择最大值，这个值的选取是相反的。

对于给定的样本集合$D$，其基尼指数定义为：

$$\begin{aligned} Gini(D)&=\sum_{k=1}^{K}\frac{|C_k|}{|D|}(1-\frac{|C_k|}{|D|}) \\ &=1-\sum_{k=1}^{K}(\frac{|C_k|}{|D|})^2 \end{aligned} \\$$

在特征$A$的条件下，集合$D$的基尼指数定义为：

$$\\ Gini(D|A) &= \sum_{i=1}^{n}\frac{|D_i|}{|D|}Gini(D_i)$$

其中 $k$ 代表类别。

基尼指数反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。因此基尼指数越小，则数据集纯度越高。基尼指数偏向于特征值较多的特征，类似信息增益。基尼指数可以用来度量任何不均匀分布，是介于 0~1 之间的数，0 是完全相等，1 是完全不相等，

此外，当 CART 为二分类，其表达式为：

$$Gini(D|A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2) \\$$

我们可以看到在平方运算和二分类的情况下，其运算更加简单。当然其性能也与熵模型非常接近。

那么问题来了：基尼指数与熵模型性能接近，但到底与熵模型的差距有多大呢？

我们知道 $ln(x) = -1+x +o(x)$ ，所以

$$\begin{aligned} H(X)&=-\sum_{k=1}^{K} p_{k} \ln p_{k}\\&\approx \sum_{k=1}^{K} p_{k}\left(1-p_{k}\right) \end{aligned} \\$$

我们可以看到，基尼指数可以理解为熵模型的一阶泰勒展开。这边在放上一张很经典的图：

特征处理

连续特征

如果特征值是连续值：特征a有连续值m个，从小到大排列。m个数值就有m-1个切分点，分别使用每个切分点把连续数值离散划分成两类，将节点数据集按照划分点分为D1和D2子集，然后计算每个划分点下对应的基尼指数，对比所有信息增益比（CART基尼指数），选择值最小（最大）的一个作为最终的特征划分。

以上就实现了将连续特征值离散化，但是CART与ID3，C4.5处理离散属性不同的是：如果当前节点为连续属性，则该属性（剩余的属性值）后面还可以参与子节点的产生选择过程。

离散特征

如果特征值是离散值：CART的处理思想与C4.5稍微所有不同。如果离散特征值多于两个，那么C4.5会在节点上根据特征值划分出多叉树。但是CART则不同，无论离散特征值有几个，在节点上都划分成二叉树。CART树是如何进行分类的呢？

还是假设特征a有m个离散值。分类标准是：每一次将其中一个特征分为一类，其它非该特征分为另外一类。依照这个标准遍历所有的分类情况，计算每种分类下的基尼指数，最后选择值最小的一个作为最终的特征划分。

特征值连续和离散有各自的处理方法，不应该混淆使用。比如分类0,1,2只代表标签含义，如果进行加减的运算或者求平均则没有任何意义。因此，CART分类树会根据特征类型选择不同的划分方法，并且与C4.5不同是，它永远只有两个分支。

缺失值处理

上文说到，模型对于缺失值的处理会分为两个子问题：

1. 如何在特征值缺失的情况下进行划分特征的选择？
2. 选定该划分特征，模型对于缺失该特征值的样本该进行怎样处理？

对于问题 1，CART 一开始严格要求分裂特征评估时只能使用在该特征上没有缺失值的那部分数据，在后续版本中，CART 算法使用了一种惩罚机制来抑制提升值，从而反映出缺失值的影响（例如，如果一个特征在节点的 20% 的记录是缺失的，那么这个特征就会减少 20% 或者其他数值）。

对于问题 2，CART 算法的机制是为树的每个节点都找到代理分裂器，无论在训练数据上得到的树是否有缺失值都会这样做。在代理分裂器中，特征的分值必须超过默认规则的性能才有资格作为代理（即代理就是代替缺失值特征作为划分特征的特征），当 CART 树中遇到缺失值时，这个实例划分到左边还是右边是决定于其排名最高的代理，如果这个代理的值也缺失了，那么就使用排名第二的代理，以此类推，如果所有代理值都缺失，那么默认规则就是把样本划分到较大的那个子节点。代理分裂器可以确保无缺失训练数据上得到的树可以用来处理包含确实值的新数据。

剪枝策略

采用一种“基于代价复杂度的剪枝”方法进行后剪枝，这种方法会生成一系列树，每个树都是通过将前面的树的某个或某些子树替换成一个叶节点而得到的，这一系列树中的最后一棵树仅含一个用来预测类别的叶节点。然后用一种成本复杂度的度量准则来判断哪棵子树应该被一个预测类别值的叶节点所代替。这种方法需要使用一个单独的测试数据集来评估所有的树，根据它们在测试数据集熵的分类性能选出最佳的树。

我们来看具体看一下代价复杂度剪枝算法：

首先我们将最大树称为 $T_0$，我们希望减少树的大小来防止过拟合，但又担心去掉节点后预测误差会增大，所以我们定义了一个损失函数来达到这两个变量之间的平衡。损失函数定义如下：

$$C_\alpha(T)=C(T)+\alpha|T| \\$$

$T$ 为任意子树，$ C(T) $为预测误差， $|T|$ 为子树 $T$ 的叶子节点个数， $\alpha$ 是参数，$ C(T) $衡量训练数据的拟合程度， $|T| $衡量树的复杂度， $\alpha$ 权衡拟合程度与树的复杂度。

那么如何找到合适的 $\alpha$ 来使得复杂度和拟合度达到最好的平衡点呢，最好的办法就是令$ \alpha$ 从 0 取到正无穷，对于每一个固定的 $\alpha $，我们都可以找到使得 $C_\alpha(T) $最小的最优子树 $T(\alpha) $。当$ \alpha$ 很小的时候，$ T_0$ 是最优子树；当 $\alpha $最大时，单独的根节点是这样的最优子树。随着 $\alpha$ 增大，我们可以得到一个这样的子树序列：$ T_0, T_1, T_2, T_3, … ,T_n$ ，这里的子树$ T_{i+1} $生成是根据前一个子树 $T_i $剪掉某一个内部节点生成的。

Breiman 证明：将 $\alpha$ 从小增大， $0=\alpha_0<\alpha_0<…<\alpha_n<\infty$ ，在每个区间$ [\alpha_i,\alpha_{i+1}) $中，子树 $T_i $是这个区间里最优的。

这是代价复杂度剪枝的核心思想。

我们每次剪枝都是针对某个非叶节点，其他节点不变，所以我们只需要计算该节点剪枝前和剪枝后的损失函数即可。

对于任意内部节点 $t$，剪枝前的状态，有 $|T_t|$ 个叶子节点，预测误差是$ C(T_t) $；剪枝后的状态：只有本身一个叶子节点，预测误差是$ C(t) $。

因此剪枝前以 $t $节点为根节点的子树的损失函数是：

$$C_\alpha(T)=C(T_t)+\alpha|T| \\$$

剪枝后的损失函数是

$$C_\alpha(t) = C(t)+\alpha \\$$

通过 Breiman 证明我们知道一定存在一个 $\alpha $使得 $C_\alpha(T)=C_\alpha(t)$ ，使得这个值为：

$$\alpha = \frac{C(t)-C(T_t)}{|T_t|-1} \\$$

$\alpha$ 的意义在于，$ [\alpha_i,\alpha_{i+1}) $中，子树 $T_i $是这个区间里最优的。当 $\alpha $大于这个值是，一定有 $C_\alpha(T)>C_\alpha(t)$ ，也就是剪掉这个节点后都比不剪掉要更优。所以每个最优子树对应的是一个区间，在这个区间内都是最优的。

然后我们对 $T_i$ 中的每个内部节点$ t $都计算：

$$g(t) = \frac{C(t)-C(T_t)}{|T_t|-1} \\$$

$g(t)$ 表示阈值，故我们每次都会减去最小的$ T_t $。

类别不平衡

CART 的一大优势在于：无论训练数据集有多失衡，它都可以将其子冻消除不需要建模人员采取其他操作。

CART 使用了一种先验机制，其作用相当于对类别进行加权。这种先验机制嵌入于 CART 算法判断分裂优劣的运算里，在 CART 默认的分类模式中，总是要计算每个节点关于根节点的类别频率的比值，这就相当于对数据自动重加权，对类别进行均衡。

对于一个二分类问题，节点 node 被分成类别 1 当且仅当：

$$\frac{N_1(node)}{N_1(root)} > \frac{N_0(node)}{N_0(root)} \\$$

比如二分类，根节点属于 1 类和 0 类的分别有 20 和 80 个。在子节点上有 30 个样本，其中属于 1 类和 0 类的分别是 10 和 20 个。如果 10/20>20/80，该节点就属于 1 类。

通过这种计算方式就无需管理数据真实的类别分布。假设有 $K $个目标类别，就可以确保根节点中每个类别的概率都是$ 1/K$。这种默认的模式被称为“先验相等”。

先验设置和加权不同之处在于先验不影响每个节点中的各类别样本的数量或者份额。先验影响的是每个节点的类别赋值和树生长过程中分裂的选择。

回归树

CART（Classification and Regression Tree，分类回归树），从名字就可以看出其不仅可以用于分类，也可以应用于回归。与分类树不同，回归树的预测变量是连续值，比如预测一个人的年龄，又或者预测季度的销售额等等。另外，回归树在选择特征的度量标准和决策树建立后预测的方式上也存在不同。

连续值处理

对于连续值，CART 分类树采用基尼系数的大小来度量特征的各个划分点。在回归模型中，我们使用常见的RSS残差平方和。线性回归的损失函数是以最小化离差平方和的形式给出的，回归树使用的度量标准也是一样的，通过最小化残差平方和作为判断标准，公式如下：

$$\min _{j, s}\left[\min _{c_{1}} \sum_{x_{i} \in R_{1}(j, s)}\left(y_{i}-c_{1}\right)^{2}+\min _{c_{2}} \sum_{x_{2} \in R_{2}(j, s)}\left(y_{i}-c_{2}\right)^{2}\right]$$

其中，$R_1、R_2$是划分的两个子集，回归树是二叉树，固只有两个子集； $c_1、c_2$是$R_1、R_2$子集的样本均值，$y_i$是样本目标变量的真实值，$j$是当前的样本特征，$s$是划分点。

上面公式的含义是：计算所有的特征以及相应所有切分点下的残差平方和，找到一组(特征$j$，切分点$s$)，以满足：分别最小化左子树和右子树的残差平方和，并在此基础上再次最小化二者之和。

预测方式

对于决策树建立后做预测的方式，上面讲到了 CART 分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别，它采用的是用最终叶子的均值或者中位数来预测输出结果。以均值为例，进行详细描述。

一个回归树对应着输入特征空间的一个划分，以及在划分单元上的输出值。先假设数据集已被划分，R1,R2,…,Rm共m的子集，回归树要求每个划分Rm中都对应一个固定的输出值$c_m$。这个$c_m$值其实就是每个子集中所有样本的目标变量$y$的平均值，并以此$c_m$作为该子集的预测值。

$$f(x)=\sum_{m=1}^{M} c_{m} I\left(x \in R_{m}\right)$$

缺点

1. 无论是ID3、C4.5还是CART，在做特征选择的时候都是选择最优的一个特征来做分类决策，但是大多数，分类决策不应该是由某一个特征决定的，而是应该由一组特征决定的。这样决策得到的决策树更加准确。这个决策树叫做多变量决策树(multi-variate decision tree)。在选择最优特征的时候，多变量决策树不是选择某一个最优特征，而是选择最优的一个特征线性组合来做决策。这个算法的代表是OC1，这里不多介绍。
2. 如果样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习里面的随机森林之类的方法解决。

ID3、C4.5 和 CART 总结

最后通过总结的方式对比下 ID3、C4.5 和 CART 三者之间的差异。

除了之前列出来的划分标准、剪枝策略、连续值确实值处理方式等之外，我再介绍一些其他差异：

• 划分标准的差异：ID3 使用信息增益偏向特征值多的特征，C4.5 使用信息增益率克服信息增益的缺点，偏向于特征值小的特征，CART 使用基尼指数克服 C4.5 需要求 log 的巨大计算量，偏向于特征值较多的特征。
• 使用场景的差异：ID3 和 C4.5 都只能用于分类问题，CART 可以用于分类和回归问题；ID3 和 C4.5 是多叉树，速度较慢，CART 是二叉树，计算速度很快；
• 样本数据的差异：ID3 只能处理离散数据且缺失值敏感，C4.5 和 CART 可以处理连续性数据且有多种方式处理缺失值；从样本量考虑的话，小样本建议 C4.5、大样本建议 CART。C4.5 处理过程中需对数据集进行多次扫描排序，处理成本耗时较高，而 CART 本身是一种大样本的统计方法，小样本处理下泛化误差较大 ；
• 样本特征的差异：ID3 和 C4.5 层级之间只使用一次特征，CART 可多次重复使用特征；
• 剪枝策略的差异：ID3 没有剪枝策略，C4.5 是通过悲观剪枝策略来修正树的准确性，而 CART 是通过代价复杂度剪枝。

决策树算法优缺点总结

我们前面介绍了决策树的特征选择，生成，和剪枝，然后对ID3, C4.5和CART算法也分别进行了详细的分析。下面我们来看看决策树算法作为一个大类别的分类回归算法的优缺点。

优点

1. 简单直观，生成的决策树很直观。
2. 基本不需要预处理，不需要提前归一化，处理缺失值。
3. 使用决策树预测的代价是O(log2m)， m为样本数。
4. 既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
5. 可以处理多维度输出的分类问题。
6. 相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释
7. 可以交叉验证的剪枝来选择模型，从而提高泛化能力。
8. 对于异常点的容错能力好，健壮性高。

决策树算法的缺点

1. 决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
2. 决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
3. 寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。
4. 有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。
5. 如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。

参考

决策树算法-理论篇-如何计算信息纯度
【机器学习】决策树（上）——ID3、C4.5、CART（非常详细）
决策树—信息增益，信息增益比，Geni指数的理解
决策树学习笔记（一）：特征选择
决策树学习笔记（三）：CART算法，决策树总结