C4.5决策树算法手算详解：从数学推导到实际应用

1次阅读

没有评论

共计 3235 个字符，预计需要花费 9 分钟才能阅读完成。

决策树是一种经典的机器学习算法，它通过树状结构对数据进行分类或回归。决策树的核心思想是通过一系列的判断规则，将数据集逐步划分成更小的子集，直到达到某种停止条件。

常见的决策树算法包括 ID3、C4.5 和 CART。其中，ID3 算法是最早的决策树算法之一，它使用信息增益作为属性选择的标准。然而，ID3 算法存在一些不足，例如倾向于选择取值较多的属性，并且无法处理连续值特征。

C4.5 算法是对 ID3 算法的改进，引入了信息增益率作为属性选择的标准，有效解决了 ID3 算法的偏向性问题。此外，C4.5 算法还能够处理连续值特征和缺失值，具有更强的实用性。

C4.5 算法的核心在于信息增益率的计算。信息增益率是信息增益与分裂信息的比值，它能够平衡属性取值数量对信息增益的影响。

信息熵是度量数据集不确定性的指标，定义为：

$$H(D) = -\sum_{i=1}^{n} p_i \log_2 p_i$$

其中，$D$ 表示数据集，$p_i$ 表示第 $i$ 类样本在数据集中的比例。

条件熵表示在已知某个属性的条件下，数据集的不确定性，定义为：

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

其中，$A$ 表示属性，$D_j$ 表示属性 $A$ 取第 $j$ 个值时的子集。

信息增益表示通过属性 $A$ 对数据集 $D$ 进行划分所获得的信息量，定义为：

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

分裂信息表示属性 $A$ 对数据集 $D$ 的划分程度，定义为：

$$SplitInfo(D, A) = -\sum_{j=1}^{m} \frac{|D_j|}{|D|} \log_2 \frac{|D_j|}{|D|}$$

信息增益率是信息增益与分裂信息的比值，定义为：

$$GainRatio(D, A) = \frac{Gain(D, A)}{SplitInfo(D, A)}$$

假设我们有一个简单的数据集，包含天气、温度、湿度和风力四个属性，以及是否打篮球的分类结果。数据集如下：

天气	温度	湿度	风力	打篮球
晴	高	高	无	否
晴	高	高	有	否
多云	高	高	无	是
雨	中	高	无	是
雨	低	中	无	是
雨	低	中	有	否
多云	低	中	有	是
晴	中	高	无	否
晴	低	中	无	是
雨	中	中	无	是
晴	中	中	有	是
多云	中	高	有	是
多云	高	中	无	是
雨	中	高	有	否

首先，计算整个数据集的信息熵。打篮球的类别分布为：是（9 个），否（5 个）。

$$H(D) = -\left(\frac{9}{14} \log_2 \frac{9}{14} + \frac{5}{14} \log_2 \frac{5}{14}\right) \approx 0.940$$

天气属性有三个取值：晴（5 个）、多云（4 个）、雨（5 个）。

计算条件熵：
晴：打篮球的类别分布为是（2 个），否（3 个）。
$$H(D_{ 晴}) = -\left(\frac{2}{5} \log_2 \frac{2}{5} + \frac{3}{5} \log_2 \frac{3}{5}\right) \approx 0.971$$
多云：打篮球的类别分布为是（4 个），否（0 个）。
$$H(D_{ 多云}) = 0$$
雨：打篮球的类别分布为是（3 个），否（2 个）。
$$H(D_{ 雨}) = -\left(\frac{3}{5} \log_2 \frac{3}{5} + \frac{2}{5} \log_2 \frac{2}{5}\right) \approx 0.971$$
条件熵：
$$H(D| 天气) = \frac{5}{14} \times 0.971 + \frac{4}{14} \times 0 + \frac{5}{14} \times 0.971 \approx 0.693$$
计算信息增益：
$$Gain(D, 天气) = 0.940 – 0.693 = 0.247$$
计算分裂信息：
$$SplitInfo(D, 天气) = -\left(\frac{5}{14} \log_2 \frac{5}{14} + \frac{4}{14} \log_2 \frac{4}{14} + \frac{5}{14} \log_2 \frac{5}{14}\right) \approx 1.577$$
计算信息增益率：
$$GainRatio(D, 天气) = \frac{0.247}{1.577} \approx 0.157$$

按照同样的方法，可以计算其他属性的信息增益率。选择信息增益率最大的属性作为分裂属性。

以下是计算信息增益率的 Python 代码实现：

import numpy as np

def entropy(labels):
    """计算信息熵"""
    _, counts = np.unique(labels, return_counts=True)
    probabilities = counts / len(labels)
    return -np.sum(probabilities * np.log2(probabilities))

def conditional_entropy(feature, labels):
    """计算条件熵"""
    unique_values = np.unique(feature)
    entropy_sum = 0
    for value in unique_values:
        subset_labels = labels[feature == value]
        entropy_sum += (len(subset_labels) / len(labels)) * entropy(subset_labels)
    return entropy_sum

def split_info(feature):
    """计算分裂信息"""
    unique_values, counts = np.unique(feature, return_counts=True)
    probabilities = counts / len(feature)
    return -np.sum(probabilities * np.log2(probabilities))

def gain_ratio(feature, labels):
    """计算信息增益率"""
    info_gain = entropy(labels) - conditional_entropy(feature, labels)
    split_information = split_info(feature)
    return info_gain / split_information if split_information != 0 else 0

# 示例数据
weather = np.array(['晴', '晴', '多云', '雨', '雨', '雨', '多云', '晴', '晴', '雨', '晴', '多云', '多云', '雨'])
play_basketball = np.array(['否', '否', '是', '是', '是', '否', '是', '否', '是', '是', '是', '是', '是', '否'])

# 计算天气属性的信息增益率
print("天气的信息增益率:", gain_ratio(weather, play_basketball))