模型选择-决策树

决策树（decision tree）是一种基本的分类与回归方法。在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是 if-then 规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。

【决策树组成】：

• 根决策点：对应一个特征判断。
• 决策节点：对应一个特征判断。
• 叶子节点：对应决策结果。

根决策点和决策节点又可统一用内部节点来表示。

【分类过程】：从根节点开始，对实例的某一特征进行判断，根据判断结果，将实例分配到其对应的子节点；这时，每个子节点对应该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶节点，最后将实例分到叶节点的类中。

“决策树可以认为是 if-then 规则的集合”

由决策树的根节点到每个叶子节点的路径对应一条规则，路径上内部节点的特征对应规则的条件，而叶节点的类对应规则的结论。为了更好地理解这句话，可以查看下图以及图所对应的 if-then 规则。

假设，此时有一位年龄25岁，长相中等收入高的靓仔路过，那么是否要见一面呢？根据上图决策树的流程来看，最终的结果是要见上一面。我们再将其转换为代码中的 if-then 规则。

if 年龄 <= 30:
    then if 长相 is '帅或中等':
        then if 收入 is '高':
            then 见

因此，从根决策点到叶子节点的每一条路径都可视为 if-then 规则，那么整棵决策树可视为 if-then 规则的集合。并且 if-then 规则集合具有一个重要的性质：互斥并且完备，每一个实例都被一条规则所覆盖，而且只被一条规则所覆盖（覆盖：实例的特征与规则上的特征一致或满足规则的条件）。

“决策树可以认为是定义在特征空间与类空间上的条件概率分布”

从概率的角度来说，路径的每一个决策节点表示样本的特征 $x^{(i)}$x(i)，叶子节点为因变量或输出值 y，那么该路径可表示为 $P(y|x^{(1)}x^{(2)}\cdots x^{(n)}) = P(Y|X)$P(y∣x(1)x(2)⋯x(n))=P(Y∣X)。因此，决策树的分类过程实际上可以理解：在指定特征序列的条件下，选择能使条件概率 P(Y|X) 最大的 Y。

从空间的角度来说，如果大家对 KD 树有了解的话应该能够很快理解决策树对空间的划分。假设我们现在有一个二维数据集，决策树根节点的判断条件是 x < 5，在二维坐标系上相当于在 x = 5 处划了一刀，将整个空间一分为二，形成两个子空间，左边是 x < 5，右边是 x > 5（或 x >= 5）。然后，在各自子空间内又可以继续进行划分。因此决策树的构建过程实质上是对特征空间的一个划分，最终将特征空间划分为互不相交的区域。

在完成对特征空间的划分后，在每个区域内定义每一个类的概率分布，从而构成一个条件概率分布。例如，二分类任务，在区域 x < 5，y > 3 内分类 1 和 -1 的概率分别为 0.8 和 0.2，条件概率可写为 P(Y=1|x < 5, y > 3) = 0.8，P(Y=-1|x < 5, y > 3) = 0.2。那么决策树的分类过程相当于先找到对应的区域，然后根据极大似然估计选择能使条件概率最大的分类结果。

决策树模型与学习

决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树。本质是从训练集中归纳出一组分类规则，或由训练集估计条件概率模型。

说到决策树算法，无论如何都绕不开以下三个步骤：

• 特征选择
• 决策树的生成
• 决策树的修剪

特征选择

特征选择在于选取对训练数据具有分类能力的特征，这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的，经验上扔掉这样的特征对决策树学习的精度影响大不。从这一点来看，决策树模型的特征选择实际上和特征工程的特征选择没有什么区别，这也是为什么特征选择的嵌入式方法中有基于树模型的特征选择法。

一般而言，随着划分过程不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一类别，即节点的“混乱度”越来越低。那么问题来了，什么是“混乱度”呢？

混乱度是指集合中数据的不确定性，在信息学中通常以信息熵来进行定量描述。

【熵（entropy）】：表示随机变量不确定性的度量。设 X 是一个取有限个值的离散随机变量，其概率分布为
$P(X=x_i) = p_i, i=1,2,...,n$P(X=xi​)=pi​,i=1,2,...,n
则随机变量 X 的熵定义为
$H(X) = -\sum_{i=1}^{n}p_ilogp_i$H(X)=−i=1∑n​pi​logpi​
通常，对数以 2 为底（单位：比特 bit）或以 e 为底（自然对象，单位：纳特 nat）。

由定义可知，熵只依赖于 X 的分布，而与 X 的取值无关，所以也可将 X 的熵记作 H§，即
$H(p) = -\sum_{i=1}^{n}p_ilogp_i$H(p)=−i=1∑n​pi​logpi​
熵越大，随机变量的不确定就越大。当随机变量只取两个值，例如 1，0 时，即 X 的分布为
$P(X=1) = p, P(X=0)=1-p, o \leq p \leq 1$P(X=1)=p,P(X=0)=1−p,o≤p≤1
熵为
$H(p) = -plog_2p-(1-p)log_2(1-p)$H(p)=−plog2​p−(1−p)log2​(1−p)
此时，熵 H§ 随概率 p 变化的曲线如下图所示。

当 p = 0 或 p = 1 时 H§ = 0，随机变量完全没有不确定性。当 p = 0.5 时，H§ = 1，熵取值最大，随机变量不确定最大。

举个不怎么恰当的例子，假设现在有 A、B、C 三个报刊，A 报道有 80% 的正确率，B 有 50% 的正确率，C 有 20% 的正确率。那么哪一个报刊最不可信？C 的正确率最低，应该是 C 吧？错，是 B。虽然 C 只有 20% 的正确率，但反过来想 C 有 80% 的错误率，那么我们把 C 报道的内容反过来看不就有 80% 的正确率了吗？比如说 C 报刊今日报道“喜迎 5G，4G 流量全免费”，我们看到这一条新闻，立马就在脑海中取反操作一下“哦，4G 流量没有免费呀”。有的时候，谎言说多了反而成为识别真伪的一种手段，而B 报刊因为正确与错误的概率对半，因此你无法确定这一条新闻到底是真还是假。

设有随机变量 (X, Y)，其联合概率分布为
$P(X=x_i, Y=y_j) = p_{ij}, i=1,2,...,n; j=1,2,...,m$P(X=xi​,Y=yj​)=pij​,i=1,2,...,n;j=1,2,...,m
条件熵 H(Y|X) 表示在已知随机变量 X 的条件下随机变量 Y 的不确定性。随机变量 X 给定的条件下随机变量 Y 的条件熵（conditional entropy）H(Y|X)，定义为 X 给定条件下 Y 的条件概率分布的熵对 X 的数学期望
$H(Y|X) = \sum_{i=1}^{n}p_iH(Y|X=x_i)$H(Y∣X)=i=1∑n​pi​H(Y∣X=xi​)
这里，$p_i = P(X=x_i), i=1,2,...,n$pi​=P(X=xi​),i=1,2,...,n。

当熵和条件熵中的概率由数据统计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵（empirical entropy）和经验条件熵（empirical conditional entropy）。此时，如果有 0 概率，令 0log0 = 0。

为了更好地理解信息熵以及特征选择等相关概念，先引入数据集，数据集取自周志华老师的西瓜书。

观察上述数据集可以发现只存在两类标签，即“是”与“否”。令随机变量 Y 表示数据集的标签数据，根据信息熵的定义可求得数据集的信息熵：
$P(y_1 = \text{&#x27;是&#x27;}) = \frac{8}{17} = p_1 \\ P(y_2 = \text{&#x27;否&#x27;}) = \frac{9}{17} = p_2 \\ H(Y) = -\sum_{y_i = 1}^2 p_i log_2 p_i = -(\frac{8}{17}log_2\frac{8}{17} + \frac{9}{17}log_2\frac{9}{17}) = 0.998$P(y1​=’是’)=178​=p1​P(y2​=’否’)=179​=p2​H(Y)=−yi​=1∑2​pi​log2​pi​=−(178​log2​178​+179​log2​179​)=0.998

在了解什么是信息熵以及条件熵之后，我们再来了解特征选择常用的准则：

• 信息增益准则
• 信息增益比准则

信息增益准则

【信息增益（information gain）】：表示得知特征 X 的信息而使得类 Y 的信息的不确定性减少的程度。通俗地讲，先对原始数据集计算一次信息熵，然后对每个特征划分数据集的结果（数据子集）计算一次信息熵，这两个信息熵的差值即为信息增益。

因此信息增益表示一个过程，而非具体的状态值。它代表前一个状态（划分前的数据集）的信息熵与后一个状态（划分后的数据集）的信息熵之间的差值。而信息熵代表随机变量的不确定性，即随机性。那么信息熵之间的差值越大，说明随机性减小，后一个状态的信息熵小，即不确定性（混乱度）更小，也可以说纯度越高。

上面是通过状态的变更来理解，也可以通过信息增益本身行为的含义进行理解：对样本集的划分使得信息的不确定性减小。那么信息增益越大，不确定性减小越多，处理后的样本集的纯度也就越高。

基于上述理解，我们自然是选择能让划分后的数据集不确定性小的特征，将该特征作为划分特征，这也是计算信息增益的目的。

【计算过程】：
假设离散特征 a 有 V 个可能的取值 $\{a^1, a^2, \cdots, a^V\}${a1,a2,⋯,aV}，若使用 a 来对样本集 D 进行划分，则会产生 V 个分支以及决策节点，其中第 i 个决策节点包含数据集 D 中所有在特征 a 且取值为 $a^v$av 的样本，记为 $D^v$Dv。再考虑到不同的决策节点所包含的样本数不同，给决策节点赋予权重 $|D^v| / |D|$∣Dv∣/∣D∣，既样本数越多的决策节点的影响越大，于是可计算出用特征 a 对样本集 D 进行划分所获得的“信息增益”。
$Gain(D, a) = H(D) - \sum_{i=1}^V \frac{|D^v|}{|D|}H(D^v)$Gain(D,a)=H(D)−i=1∑V​∣D∣∣Dv∣​H(Dv)
一般而言，信息增益越大，则意味着使用特征 a 进行划分后的数据集的不确定性低。因此，我们可以用信息增益来进行决策树的特征选择，著名的 ID3 决策树学习算法就是以信息增益为准则。

以西瓜数据集为例，计算出当前特征集合 {色泽，根蒂，敲声，纹理，脐部，触感} 中每个特征的信息增益。以属性“色泽”为例，它有 3 个可能的取值 {青绿，乌黑，浅白}。若使用该特征对数据集 D 进行划分，则可得到 3 个数据子集，分别记为 D1(色泽=青绿)，D2(色泽=乌黑)，D3(色泽=浅白)。

• D1 包含编号为 {1，4，6，10，13，17} 6 个实例，其中好瓜的概率 $p_1 = \frac{3}{6}$p1​=63​，坏瓜的概率 $p_2 = \frac{3}{6}$p2​=63​；
• D2 包含编号为 {2，3，7，8，9，15} 6 个实例，其中好瓜的概率 $p_1 = \frac{4}{6}$p1​=64​，坏瓜的概率 $p_2 = \frac{2}{6}$p2​=62​；
• D3 包含编号为 {5，11，12，14，16} 5 个实例，其中好瓜的概率 $p_1 = \frac{1}{5}$p1​=51​，坏瓜的概率 $p_2 = \frac{4}{5}$p2​=54​。

根据信息熵的公式计算按此“色泽”特征划分后的 3 个数据子集的信息熵：
$H(D^1) = -(\frac{3}{6}log_2\frac{3}{6} + \frac{3}{6}log_2\frac{3}{6}) = 1.000 \\ H(D^2) = -(\frac{4}{6}log_2\frac{4}{6} + \frac{2}{6}log_2\frac{2}{6}) = 0.918 \\ H(D^3) = -(\frac{1}{5}log_2\frac{1}{5} + \frac{4}{5}log_2\frac{4}{5}) = 0.722$H(D1)=−(63​log2​63​+63​log2​63​)=1.000H(D2)=−(64​log2​64​+62​log2​62​)=0.918H(D3)=−(51​log2​51​+54​log2​54​)=0.722

然后再根据信息增益的公式计算“色泽”特征的信息增益：
$Gain(D, \text{色泽}) = H(D) - \sum_{i=1}^3 \frac{|D^v|}{|D|} H(D^v) = 0.998 - (\frac{6}{17} \times 1.000 + \frac{6}{17} \times 0.918 + \frac{5}{17} \times 0.722) = 0.109$Gain(D,色泽)=H(D)−i=1∑3​∣D∣∣Dv∣​H(Dv)=0.998−(176​×1.000+176​×0.918+175​×0.722)=0.109

类似的，我们可计算出其他特征的信息增益：
$Gain(D, \text{根蒂}) = 0.143 \quad Gain(D, \text{敲声}) = 0.141 \quad Gain(D, \text{纹理}) = 0.381 \quad \\ Gain(D, \text{脐部}) = 0.289 \quad Gain(D, \text{触感}) = 0.006 \quad$Gain(D,根蒂)=0.143Gain(D,敲声)=0.141Gain(D,纹理)=0.381Gain(D,脐部)=0.289Gain(D,触感)=0.006
通过比较各特征的信息增益，可以发现特征“纹理”的信息增益最大，因此该特征被选为根决策点的划分特征。接着，将数据集按照特征进行划分，

【注意】：按特征划分后的数据子集不存在划分特征，例如按色泽划分后的三个数据子集 D1、D2 和 D3 不存在特征“色泽”，上图之所以仍然存在，是为了方便读者更容易识别划分后的数据子集。

完成根决策点的特征划分后，决策树学习算法将对新生成的决策节点做进一步的划分。以上图分支“纹理=清晰”所对应的决策节点为例，该节点包含的数据子集 D1 包含编号为 {1，2，3，4，5，6，8，10，15} 9 个实例，可用特征集合为 {色泽，根蒂，敲声，脐部，触感}。继续按照先前的步骤进行计算，仍然以特征“色泽”为例，它有 3 个可能的取值 {青绿，乌黑，浅白}。

• D1-1（色泽=青绿） 包含编号 {1，4，6，10} 4 个实例，其中好瓜的概率 $p_1 = \frac{3}{4}$p1​=43​，坏瓜的概率 $p_2 = \frac{1}{4}$p2​=41​；
• D1-2（色泽=乌黑） 包含编号 {2，3，8，15} 4 个实例，其中好瓜的概率 $p_1 = \frac{3}{4}$p1​=43​，坏瓜的概率 $p_2 = \frac{1}{4}$p2​=41​；
• D1-3（色泽=浅白） 包含编号 {5} 1 个实例，其中好瓜的概率 $p_1 = 1$p1​=1，坏瓜的概率 $p_2 = 0$p2​=0；

计算按“色泽”特征划分后的 3 个数据子集的信息熵：
$H(D^1) = -(\frac{7}{9}log_2\frac{7}{9} + \frac{2}{9}log_2\frac{2}{9}) = 0.764 \\ H(D^{1-1}) = -(\frac{3}{4}log_2\frac{3}{4} + \frac{1}{4}log_2\frac{1}{4}) = 0.811 \\ H(D^{1-2}) = -(\frac{3}{4}log_2\frac{3}{4} + \frac{1}{4}log_2\frac{1}{4}) = 0.811 \\ H(D^{1-3}) = -(1 \ log_2 1 + 0 \ log_2 0) = 0$H(D1)=−(97​log2​97​+92​log2​92​)=0.764H(D1−1)=−(43​log2​43​+41​log2​41​)=0.811H(D1−2)=−(43​log2​43​+41​log2​41​)=0.811H(D1−3)=−(1 log2​1+0 log2​0)=0

计算“色泽”特征的信息增益：
$Gain(D1, \text{色泽}) = 0.764 - (\frac{4}{9} \times 0.811 + \frac{4}{9} \times 0.811 + \frac{1}{9} \times 0) = 0.043$Gain(D1,色泽)=0.764−(94​×0.811+94​×0.811+91​×0)=0.043

再计算其他特征的信息增益：
$Gain(D^1, \text{色泽}) = 0.043 \quad Gain(D^1, \text{根蒂}) = 0.458 \quad Gain(D^1, \text{敲声}) = 0.331 \\ Gain(D^1, \text{脐部}) = 0.458 \quad Gain(D^1, \text{触感}) = 0.458$Gain(D1,色泽)=0.043Gain(D1,根蒂)=0.458Gain(D1,敲声)=0.331Gain(D1,脐部)=0.458Gain(D1,触感)=0.458
根蒂、脐部和触感，这三个特征均取得最大的信息增益，可任选其一作为划分特征。类似的，对每个决策节点进行上述操作，最终得到的决策树如下图所示。

代码实现

【前提】：数据集通过 pandas 读取。

• 所需库：pandas、numpy。
• Python 版本：3.6

首先，编写计算信息熵的函数。

def cal_shannon_entropy(dataset):
    """
    计算数据集的信息熵
    :param dataset: 数据集
    """
    # 获取数据集中的标签类别数
    labels, length = set(dataset[:, -1]), dataset.shape[0]
    shannon_sum = 0
    for label in labels:
        # 计算每个标签的概率
        p_label = dataset[dataset[:, -1] == label].shape[0] / length
        shannon_sum += -p_label * np.log(p_label)
    return shannon_sum

• 先获取数据集中的标签类别数（在西瓜数据集中标签只有两类“是”与“否”）以及数据集的数目；
• 在循环过程中计算每个标签的概率，$dataset[dataset[:, -1] == label].shape[0]$dataset[dataset[:,−1]==label].shape[0] 这段代码用以获取符合当前标签值的数据个数，即标签个数。标签个数除以数据集的数目，即为当前标签的概率；
• 获得标签的概率之后，即可套入公式 $-p_label * np.log(p_label)$−pl​abel∗np.log(pl​abel)，最后返回累加的结果。

接着，编写划分数据集的函数。

def split_dataset(dataset, feature, feature_value):
    """
    按照特征以及特征值划分数据集
    :param dataset: 数据集
    :param feature: 划分特征
    :param feature_value: 划分特征值
    """
    split_data = dataset[dataset[:, feature] == feature_value]
    return np.delete(split_data, feature, axis=1)

• 根据划分特征和划分并特征值从数据集中找出符合要求的数据子集，需要注意的是当前特征子集包含当前划分并特征，因此我们需要将其删除；
• 通过 np.delete() 函数将数据子集中划分特征那一列数据全部删除，np.delete() 具体用法请参考官方文档传送门。

最后，编写选择划分特征的函数。

def choose_best_feature(dataset):
    """
    选择最优的划分特征
    :param dataset: 数据集
    """
    # 获取数据集的特征数以及数据集的数目
    features, lentgh = dataset.shape[1] - 1, dataset.shape[0]
    # 计算划分前数据集的信息熵
    base_shannon = cal_shannon_entropy(dataset)
    # 存放划分后各数据子集的信息熵
    split_shannon = []
    for feature in features:
        # 获取当前特征的特征值
        feature_values = set(dataset[:, feature])
        shannon = 0
        for feature_value in feature_values:
            # 获取划分后的数据子集
            dataset_feature = split_dataset(dataset, feature, feature_value)
            # 当前数据子集的权重，即 |Dv| / |D|
            dataset_feature_p = dataset_feature.shape[0] / length
            shannon += dataset_feature_p * cal_shannon_entropy(dataset_feature)
        # 计算当前特征的信息增益，并添加到 split_shannon 列表中
        split_shannon.append(base_shannon - shannon)
    # 返回信息增益最大的特征
    return np.argmax(split_shannon)

• 首先，获取数据集的特征数、数目以及信息熵；
• 接着，通过循环依次计算每个特征的信息增益；
  • 获取当前特征的特征值，并初始化信息熵 shannon = 0；
  • 计算当前特征的信息增益，并添加到 split_shannon 列表；
• 最后，通过 np.argmax() 函数找出 split_shannon 列表中最大值的下标，该下标即为特征（feature），将该下标返回。关于 np.argmax() 函数的用法请参考官方文档传送门。

信息增益的“偏好”

在上述示例中，如果我们将“编号”也作为特征集合的一员，那么会发生什么情况？根据信息增益公式计算，“编号”的信息增益远大于其他特征的信息增益！为什么会这样？因为按照“编号”进行划分，将产生 17 条分支，每个分支的决策节点只包含一个实例，也就是说编号唯一对应一个结果（好瓜还是坏瓜），根据信息熵公式，划分后的数据子集的信息熵为 0。

在数据集不变的前提下，特征取值越多，分配给每个特征取值的数据子集也就越少，那么就有可能会出现该特征取值下的实例全部属于同一个类别的情况，因此信息增益也就越大。正是由于这种情况的存在，信息增益准则对可取数目较多的属性有所偏好。

信息增益比准则

由于信息增益准则对特征取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，使用“信息增益比（gain ratio）”准则来选择最优划分特征。

【信息增益比】：沿用信息增益准则的符号表示。
$Gain_ratio(D, a) = \frac{Gain(D, a)}{IV(a)} \\ IV(a) = -\sum_{i=1}^V \frac{|D^v|}{|D|}log_2 \frac{|D^v|}{|D|}$Gainr​atio(D,a)=IV(a)Gain(D,a)​IV(a)=−i=1∑V​∣D∣∣Dv∣​log2​∣D∣∣Dv∣​
其中，IV(a) 称为特征 a 的“固有值”（intrinsic value）。特征 a 的可能取值数目越多，则 IV(a) 的值通常会越大，且增长的速率要大于 Gain_ratio(D, a)。因此，信息增益比准则对特征取值数目较少的特征有所偏好。

代码实现

计算信息熵以及划分数据集都可以沿用信息增益准则代码实现部分的 cal_shannon_entropy() 以及 split_dataset() 函数。唯一需要修改的是挑选最优特征函数 choose_best_feature()。

def choose_best_feature(dataset):
    """
    选择最优的划分特征
    :param dataset: 数据集
    """
    features, lentgh = dataset.shape[1] - 1, dataset.shape[0]
    base_shannon = cal_shannon_entropy(dataset)
    split_shannon = []
    for feature in features:
        feature_values = set(dataset[:, feature])
        shannon = 0
        # 新增 ratio 变量，用以保存 IV(a)
        ratio = 0
        for feature_value in feature_values:
            dataset_feature = split_dataset(dataset, feature, feature_value)
            dataset_feature_p = dataset_feature.shape[0] / length
            shannon += dataset_feature_p * cal_shannon_entropy(dataset_feature)
            # 累加 ratio 变量
            ratio += -dataset_feature_p * np.log(dataset_feature_p)
        # 计算当前特征的信息增益比，并添加到 split_shannon 列表中
        split_shannon.append((base_shannon - shannon) / ratio)
    # 返回信息增益比最大的特征
    return np.argmax(split_shannon)

信息增益比的实现方式可以在信息增益的基础上计算 IV(a)，然后将信息增益除以 IV(a)。

著名的 C4.5 算法采用信息增益比来选择最优划分特征，需要注意的是，C4.5 算法不是直接选择信息增益比最大的划分特征，而是使用了一个启发式方法：先从特征集合中找出信息增益高于平均水平的特征，再从中选择信息增益比最高的特征。这样可以尽量避免信息增益以及信息增益比的偏好影响。

【C4.5 启发式方法代码】：

• 初始化 split_shannon 列表，用以存放信息增益以及信息增益比。

split_shannon = []

• 在循环计算各划分特征的信息增益和信息增益比的过程中，以元组的形式将信息增益和信息增益比保存到 split_shannon 列表中。

split_shannon.append((base_shannon - shannon, (base_shannon - shannon) / ratio))

• 按照信息增益升序的方式进行排序。

split_shannon.sort(key=lambda x:x[0])

• 从中挑选部分划分特征，挑选准则可以自行定义，例如选择列表的后半部分划分特征。

split_shannon = split_shannon[len(split_shannon) // 2:]

• 再按照信息增益比升序的方式进行排序。

split_shannon.sort(key=lambda x:x[1])

• 选择信息增益比最大的划分特征。

best_feature = split_shannon[-1]

基尼系数

关于基尼系数的介绍放到 CART 算法中。

决策树的生成

决策树的生成是一个递归过程。在决策树生成算法中，有三种情形会导致递归返回。

• （1）当前结点包含的样本全属于同一类别，无需划分；
• （2）当前特征集为空，或是所有样本在所有特征上取值相同（但类别不同，这应该就是样本本身的问题了），无法划分。
• （3）当前结点包含的样本集合为空，不能划分。

第（1）种情形下，把当前结点标记为叶结点，并将其类别设定为唯一类别。

第（2）种情形下，把当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别；

第（3）种情形下，把当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多的类别。

因篇幅有限，ID3、C4.5 以及 CART 的具体实现放到其他博客中。

• ID3 算法：传送门
• C4.5 算法：传送门
• CART 算法（上）：传送门
• CART 算法（下）：传送门

【三类算法的比较】：

算法	支持模型	树结构	特征选择	连续值处理	剪枝
ID3	分类	多叉树	信息增益	不支持	不支持
C4.5	分类	多叉树	信息增益比	支持	支持
CART	分类、回归	二叉树	基尼系数、均方误差	支持	支持

决策树的剪枝

决策树生成算法递归地产生决策树，这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没有那些准确，即出现过拟合现象。

【原因】：学习时过多地考虑如何提高对训练数据的正确分类，从而构建出复杂的决策树。

【办法】：考虑决策树的复杂度，对已生成的决策树进行简化，主动去掉一些分支来降低过拟合的风险。

【剪枝】：在决策树学习中将已生成的树进行简化的过程称为剪枝（pruning）。具体地，剪枝从已生成的决策树上裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型。

决策树的剪枝往往通过极小化决策树整体的损失函数（loss function）或代价函数（cost function）来实现。

设决策树 T 的叶结点个数为 |T|，t 是树 T 的叶结点，该叶结点有 $N_t$Nt​ 个样本点，其中 k 类的样本点有 $N_tk$Nt​k 个，k = 1, 2, …, K，$H_t(T)$ 为叶结点 t 上的经验熵，a >= 0为参数，则决策树学习的损失函数可以定义为
$C_a(T) = \sum_{t=1}^{|T|}N_tH_t(T) + \alpha|T|$Ca​(T)=t=1∑∣T∣​Nt​Ht​(T)+α∣T∣
其中经验熵为
$H_t(T) = -\sum_k\frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}$Ht​(T)=−k∑​Nt​Ntk​​logNt​Ntk​​
这时有
$C_\alpha(T) = C(T) + \alpha|T|$Cα​(T)=C(T)+α∣T∣
【说明】：

• C(T)：表示模型对训练数据的预测误差，即模型与训练数据的拟合程度。
• |T|：表示模型复杂度。
• a >= 0：控制预测误差与模型复杂度两者之间的影响。
  • 较大的 a 促使选择较简单的模型。
  • 较小的 a 促使选择较复杂的模型。
  • a = 0，意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。

剪枝，就是当 a 确定时，选择损失函数最小的模型，即损失函数最小的子树。子树越大，往往与训练数据拟合的越好，但是模型的复杂度就越高；相反，子树越小，模型的复杂度就越低，但是往往与训练数据的拟合不好。损失函数正好表示了对两者的平衡。

可以看出，决策树生成只考虑了通过提高信息增益（或信息增益比）对训练数据进行更好的拟合。而决策树剪枝通过优化损失函数还考虑了减小模型复杂度。

• 决策树生成学习局部的模型。
• 决策树剪枝学习整体的模型。

【算法】：决策树的剪枝算法。

• 输入：生成算法产生的整个决策树 T，参数 a。
• 输出：修剪后的子树 $T_\alpha$Tα​。
• 过程：

1. 计算每个结点的经验熵。
2. 递归地从树的叶结点向上回缩。设一组叶结点回缩到其父结点之前与之后的整体树分别为 Tb 和 Ta，其对应的损失函数值分别是 Ca(Tb) 与 Ca(Ta)，如果
   $C_\alpha(T_a) \leq C_\alpha(T_b)$Cα​(Ta​)≤Cα​(Tb​)
   则进行剪枝，即将父结点变为新的叶结点。
3. 返回（2），直至不能继续为止，得到损失函数最小的子树 Ta。

【注意】：根据过程（2）中的式子，只需考虑两个树的损失函数的差，其计算可以在局部进行。所以，决策树的剪枝算法可以由一种动态规划的算法实现。

【基本策略】：

• 预剪枝（prepruning）：在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点；
• 后剪枝（postpruning）：先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。

关于树的剪枝操作，《机器学习》中讲解得非常清晰且出彩，读者可以阅读《机器学习》来理解这部分内容。

总结

参考

• 《统计学习方法》李航
• 《机器学习》周志华
• 《百面机器学习》