C4.5决策树算法手算实战：从原理到分步计算详解

1次阅读

没有评论

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

决策树算法的核心是选择最优划分特征。ID3 算法使用信息增益，但它存在偏向选择取值较多特征的问题。例如，若用「身份证号」作为特征，信息增益会最大，但这显然没有意义。

C4.5 算法引入信息增益率（Gain Ratio）来解决这个问题：

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

其中 SplitInfo 是拆分信息，用来惩罚取值过多的特征。

我们使用经典的天气预测数据集，包含 5 个样本：

天气	温度	湿度	风速	是否打球
晴	28	85	弱	否
晴	30	90	强	否
阴	25	78	弱	是
雨	20	80	弱	是
雨	18	70	强	否

以「风速」为例：

计算原始信息熵：

$$
H(D) = -\frac{2}{5}\log_2\frac{2}{5} – \frac{3}{5}\log_2\frac{3}{5} ≈ 0.971
$$

计算按风速划分后的条件熵：

$$
H(D| 风速 = 弱) = -\frac{2}{3}\log_2\frac{2}{3} – \frac{1}{3}\log_2\frac{1}{3} ≈ 0.918
$$

$$
H(D| 风速 = 强) = 0
$$

信息增益：

$$
Gain = H(D) – (\frac{3}{5}×0.918 + \frac{2}{5}×0) ≈ 0.42
$$

拆分信息：

$$
SplitInfo = -\frac{3}{5}\log_2\frac{3}{5} – \frac{2}{5}\log_2\frac{2}{5} ≈ 0.971
$$

信息增益率：

$$
GainRatio ≈ 0.42 / 0.971 ≈ 0.433
$$

对于温度这样的连续特征，C4.5 会先排序，然后取相邻值的中间点作为候选分割点：

排序后的温度值：18, 20, 25, 28, 30
候选分割点：19, 22.5, 26.5, 29
对每个分割点计算信息增益率，选择最大的

以 22.5 为例：

左子集（≤22.5）：2 个样本（1 个是，1 个否）
右子集（>22.5）：3 个样本（1 个是，2 个否）

计算过程类似离散特征，最终会选择信息增益率最大的分割点。

from sklearn.tree import DecisionTreeClassifier
import pandas as pd

# 准备数据
data = {'Outlook': ['Sunny', 'Sunny', 'Overcast', 'Rain', 'Rain'],
    'Temp': [28, 30, 25, 20, 18],
    'Humidity': [85, 90, 78, 80, 70],
    'Wind': ['Weak', 'Strong', 'Weak', 'Weak', 'Strong'],
    'Play': ['No', 'No', 'Yes', 'Yes', 'No']
}
df = pd.DataFrame(data)

# 特征编码
df = pd.get_dummies(df, columns=['Outlook', 'Wind'])

# 训练 C4.5 决策树
clf = DecisionTreeClassifier(criterion='entropy', splitter='best')
clf.fit(df.drop('Play', axis=1), df['Play'])

# 查看特征重要性
print(clf.feature_importances_)