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

1次阅读

没有评论

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

决策树是一种常用的机器学习算法，主要用于分类和回归任务。它通过一系列的判断规则来对数据进行分类，这些规则形成的结构就像一棵倒置的树。决策树的构建过程就是一个递归地选择最优特征进行分裂的过程。

ID3 算法 ：使用信息增益作为特征选择标准，倾向于选择取值较多的特征，容易导致过拟合。
C4.5 算法 ：改进 ID3 算法，使用信息增益率作为特征选择标准，能够有效减少对取值较多特征的偏好，同时支持连续值特征和缺失值处理。

信息增益率是 C4.5 算法的核心，它通过引入分裂信息来惩罚取值较多的特征。计算步骤如下：

计算熵（Entropy）：衡量数据的不确定性。
$$
Entropy(S) = -\sum_{i=1}^{c} p_i \log_2 p_i
$$
计算条件熵（Conditional Entropy）：给定特征 A 后，数据的不确定性。
$$
Entropy(S|A) = \sum_{v \in Values(A)} \frac{|S_v|}{|S|} Entropy(S_v)
$$
计算信息增益（Information Gain）：
$$
Gain(S, A) = Entropy(S) – Entropy(S|A)
$$
计算分裂信息（Split Information）：
$$
SplitInfo(S, A) = -\sum_{v \in Values(A)} \frac{|S_v|}{|S|} \log_2 \frac{|S_v|}{|S|}
$$
计算信息增益率（Gain Ratio）：
$$
GainRatio(S, A) = \frac{Gain(S, A)}{SplitInfo(S, A)}
$$

假设我们有一个简单的数据集，包含天气、温度、湿度和是否打篮球四个特征。我们以天气为例，演示信息增益率的计算过程。

计算初始熵 ：
打篮球的样本数：9
不打篮球的样本数：5
总样本数：14
熵：$Entropy(S) = -\left(\frac{9}{14} \log_2 \frac{9}{14} + \frac{5}{14} \log_2 \frac{5}{14}\right) \approx 0.940$
计算条件熵 ：
天气有晴天、阴天、雨天三种取值。
晴天：打篮球 3，不打篮球 2，熵：$Entropy(S_{sunny}) = -\left(\frac{3}{5} \log_2 \frac{3}{5} + \frac{2}{5} \log_2 \frac{2}{5}\right) \approx 0.971$
阴天：打篮球 4，不打篮球 0，熵：$Entropy(S_{overcast}) = 0$
雨天：打篮球 2，不打篮球 3，熵：$Entropy(S_{rainy}) \approx 0.971$
条件熵：$Entropy(S|weather) = \frac{5}{14} \times 0.971 + \frac{4}{14} \times 0 + \frac{5}{14} \times 0.971 \approx 0.693$
计算信息增益 ：
$Gain(S, weather) = 0.940 – 0.693 = 0.247$
计算分裂信息 ：
$SplitInfo(S, weather) = -\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(S, weather) = \frac{0.247}{1.577} \approx 0.157$

import math

def entropy(data):
    total = len(data)
    if total == 0:
        return 0
    positives = sum(data)
    negatives = total - positives
    p_pos = positives / total
    p_neg = negatives / total
    if p_pos == 0 or p_neg == 0:
        return 0
    return - (p_pos * math.log2(p_pos) + p_neg * math.log2(p_neg))

def gain_ratio(data, feature_values, target_values):
    total_entropy = entropy(target_values)
    split_info = 0
    conditional_entropy = 0
    for value in set(feature_values):
        subset = [target_values[i] for i in range(len(target_values)) if feature_values[i] == value]
        weight = len(subset) / len(target_values)
        conditional_entropy += weight * entropy(subset)
        split_info -= weight * math.log2(weight) if weight > 0 else 0
    gain = total_entropy - conditional_entropy
    return gain / split_info if split_info > 0 else 0

# 示例数据
weather = ['sunny', 'sunny', 'overcast', 'rainy', 'rainy', 'rainy', 'overcast', 'sunny', 'sunny', 'rainy', 'sunny', 'overcast', 'overcast', 'rainy']
play = [1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0]

print("Gain Ratio for weather:", gain_ratio(play, weather, play))