【机器学习】决策树-海口c网

一、引言

二、决策树的构造

三、决策树的ID3算法

四、决策树的C4.5算法

五、决策树的CART算法

六、动手实现决策树C4.5的算法详解步骤以及Python完整代码实现

一、引言

在机器学习中，有一种与神经网络并行的非参数化模型——决策树模型及其变种。顾名思义，决策树采用了与树类似的结构。现实中的树是根在下、从下往上生长的，决策树却是根在上，从上往下生长的。但是，两者都有根、枝干的分叉与叶子。在决策树中，最上面的节点称为根节点，最下面没有分叉的节点称为叶节点。其中，根节点和内部节点都有一些边指向其他节点，这些被指向的节点就称为它的子节点。叶节点是树的最末端，没有指向其他根节点的边，而除根结点之外，每个内部节点和叶节点都有唯一的节点指向它，该节点称为其父节点。本文详细介绍了决策树的构造、ID3算法、C4.5的算法、CART算法以及C4.5算法的详细步骤用Python代码实现。

二、决策树的构造

1. 决策树的基本概念

决策树是一种非参数监督学习算法，通过将数据集按照特定特征递归地分裂为较小的子集，从而构建出一个预测模型。决策树结构包括：

根节点：代表整个数据集。
内部节点：表示对特征的测试。
分支：表示测试的输出。
叶节点：代表最终的分类结果或回归值。

决策树的构造本质上是一个特征选择和递归划分的过程，目标是构建一个能够最大程度反映数据内在规律的树结构。

2. 决策树构造的基本框架

决策树构造通常遵循"自顶向下、递归分治"的策略，基本算法框架为：

函数 BuildDecisionTree(数据集D, 特征集A, 选择标准criterion):
    创建节点N
    
    # 终止条件
    如果 满足终止条件:
        将N标记为叶节点，赋予类别/值
        返回N
        
    # 选择最优特征
    根据criterion选择最优特征A_best和分割点
    
    # 根据特征分割数据
    将数据集D根据A_best分割为若干子集{D_1, D_2, ..., D_v}
    
    # 递归构建子树
    对于每个子集D_j:
        子树j = BuildDecisionTree(D_j, A - {A_best}, criterion)
        将子树j连接到节点N
        
    返回N

终止条件通常包括：
（1）节点中的样本全部属于同一类别。

（2）特征集为空或样本在所有特征上取值相同。

（3）节点中的样本数小于预定阈值。

三、决策树的ID3算法

1. ID3算法基本原理

ID3(Iterative Dichotomiser 3)算法是由Ross Quinlan在1986年提出的决策树生成算法，它通过信息论中的熵(entropy)和信息增益(information gain)来构建决策树。ID3算法的核心思想是：在每一步构建决策树的过程中，选择能够最大化信息增益的特征作为当前节点的分裂特征。

2. 信息论基础

2.1 熵(Entropy)

熵是信息论中表示随机变量不确定性的度量。对于一个随机变量 $Y$ ，其熵 $H(Y)$ 定义为：

$H(Y) = -\sum_{i=1}^{n} P(y_i) \log_2 P(y_i)$

其中：
$y_i$ 是随机变量 $Y$ 可能的取值。
$P(y_i)$ 是 $y_i$ 出现的概率。
$n$ 是 $Y$ 可能取值的数量。
$\log_2$ 表示以2为底的对数。

在决策树中，对于一个数据集 $D$ ，假设类别标签有 $K$ 个可能取值，第 $k$ 个类别的样本数为 $|C_k|$ ，则数据集 $D$ 的熵为：

$H(D) = -\sum_{k=1}^{K} \frac{|C_k|}{|D|} \log_2 \frac{|C_k|}{|D|}$

其中 $\frac{|C_k|}{|D|}$ 表示类别 $k$ 在数据集中的占比。

2.2 条件熵(Conditional Entropy)

条件熵 $H(Y|X)$ 表示在已知随机变量 $X$ 的条件下，随机变量 $Y$ 的不确定性：

$H(Y|X) = \sum_{j=1}^{m} P(x_j) H(Y|X=x_j)$

其中：
$x_j$ 是随机变量 $X$ 的可能取值。

$P(x_j)$ 是 $x_j$ 出现的概率。
$H(Y|X=x_j)$ 是在 $X=x_j$ 条件下 $Y$ 的熵。

在决策树中，对于特征 $A$ ，数据集 $D$ 可以划分为 $v$ 个子集 $\{D_1, D_2, ..., D_v\}$ ，则条件熵 $H(D|A)$ 为：

$H(D|A) = \sum_{j=1}^{v} \frac{|D_j|}{|D|} H(D_j)$

其中 $\frac{|D_j|}{|D|}$ 表示子集 $D_j$ 在数据集中的占比。

2.3 信息增益(Information Gain)

信息增益表示由于使用特征$A$划分数据集而导致的不确定性减少量：

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

用公式展开为：

$Gain(D, A) = -\sum_{k=1}^{K} \frac{|C_k|}{|D|} \log_2 \frac{|C_k|}{|D|} - \left( -\sum_{j=1}^{v} \frac{|D_j|}{|D|} \sum_{k=1}^{K} \frac{|D_j^k|}{|D_j|} \log_2 \frac{|D_j^k|}{|D_j|} \right)$

其中：
$|D_j^k|$ 表示子集 $D_j$ 中属于类别$k$的样本数。

3. ID3算法完整流程

ID3算法采用自顶向下的贪心方法构建决策树，其完整的数学流程如下：

（1）计算当前数据集的熵：

$H(D) = -\sum_{k=1}^{K} \frac{|C_k|}{|D|} \log_2 \frac{|C_k|}{|D|}$

（2）对每个未使用的特征 $A$ ：
计算条件熵 $H(D|A)$ ：

$H(D|A) = \sum_{j=1}^{v} \frac{|D_j|}{|D|} H(D_j)$

计算信息增益 $Gain(D, A)$ ：

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

（3）选择信息增益最大的特征 $A_{best}$ 作为当前节点的分裂特征：

$A_{best} = \arg\max_{A} Gain(D, A)$

（4）对 $A_{best}$ 的每个可能取值 $a_j$ ：
（1）创建子节点，并将满足 $A_{best} = a_j$ 的样本分配给该子节点。
（2）如果子节点的样本都属于同一类别 $C_k$ ，则将子节点标记为叶节点，类别为 $C_k$ ，
否则，对子节点递归执行步骤1-4。

4. ID3算法的特点与局限性

4.1 特点：
（1）使用信息增益作为特征选择的度量，倾向于选择具有较大信息增益的特征。
（2）构建的决策树通常较为平衡。
（3）计算简单，易于实现。

4.2 局限性：
（1）偏向多值特征：ID3算法中的信息增益度量会偏向于选择取值较多的特征。例如，对于一个唯（2）一标识符特征（如ID），其信息增益会非常高，但对分类几乎没有泛化能力。
（3）无法处理连续值特征：ID3算法只能处理离散值特征，需要对连续值特征进行离散化处理。
（4）无法处理缺失值：没有内置处理缺失值的机制。
（5）容易过拟合：没有剪枝策略，容易生成过于复杂的树。
（6）无法处理不平衡数据：对于类别不平衡的数据集，ID3算法可能会偏向于主要类别。

5. ID3算法的数学推导

ID3算法的关键是选择最优特征，这是通过最大化信息增益实现的。以下是这一过程的数学推导：

假设特征 $A$ 将数据集 $D$ 分割成 $v$ 个子集 $\{D_1, D_2, ..., D_v\}$ ，这些子集的熵可分别计算为：

$H(D_j) = -\sum_{k=1}^{K} \frac{|D_j^k|}{|D_j|} \log_2 \frac{|D_j^k|}{|D_j|}$

其中 $|D_j^k|$ 是子集 $D_j$ 中属于类别 $k$ 的样本数量。

条件熵 $H(D|A)$ 是这些子集熵的加权平均：

$H(D|A) = \sum_{j=1}^{v} \frac{|D_j|}{|D|} H(D_j)$

用具体公式表示为：

$H(D|A) = \sum_{j=1}^{v} \frac{|D_j|}{|D|} \left( -\sum_{k=1}^{K} \frac{|D_j^k|}{|D_j|} \log_2 \frac{|D_j^k|}{|D_j|} \right)$

而信息增益是原始熵与条件熵的差值：

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

展开后：

$Gain(D, A) = -\sum_{k=1}^{K} \frac{|C_k|}{|D|} \log_2 \frac{|C_k|}{|D|} - \sum_{j=1}^{v} \frac{|D_j|}{|D|} \left( -\sum_{k=1}^{K} \frac{|D_j^k|}{|D_j|} \log_2 \frac{|D_j^k|}{|D_j|} \right)$

6. ID3算法伪代码

函数 ID3(数据集D, 特征集A, 阈值ε):
    创建节点N
    
    # 如果数据集D中所有样本属于同一类别C_k
    如果 D中样本都属于类别C_k:
        将N标记为C_k类叶节点
        返回N
        
    # 如果特征集A为空或数据集D中样本在A上取值相同
    如果 A为空 或 D中样本在A上取值相同:
        将N标记为叶节点，类别为D中样本数最多的类
        返回N
        
    # 否则，计算A中各特征的信息增益，选择信息增益最大的特征A_best
    对于每个特征A_i in A:
        计算信息增益Gain(D, A_i)
    A_best = 信息增益最大的特征
    
    # 如果最大信息增益小于阈值ε，则不再划分
    如果 Gain(D, A_best) < ε:
        将N标记为叶节点，类别为D中样本数最多的类
        返回N
        
    # 以A_best为划分特征构建子树
    将N标记为特征A_best对应的内部节点
    对于A_best的每个可能取值a_j:
        D_j = 满足A_best=a_j的D的子集
        如果 D_j为空:
            创建叶节点N_j，类别为D中样本数最多的类
            将N_j作为N的子节点
        否则:
            调用ID3(D_j, A - {A_best}, ε)获得子树
            将子树作为N的子节点
            
    返回N

7. 一个简单的ID3算法示例

假设我们有一个关于是否去钓鱼的决策问题，特征包括：天气(Outlook)、温度(Temperature)、湿度(Humidity)和刮风(Windy)，类别为是否去钓鱼(PlayTennis)。

假设部分数据如下：