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

1次阅读

没有评论

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

决策树算法中，ID3 使用信息增益作为特征选择标准，但存在偏向取值多的特征的问题。比如有一个特征是 ”ID”，每个样本的 ID 都不同，按信息增益会选择这个特征，但这显然没有意义。

C4.5 引入了信息增益率来解决这个问题：

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

其中 SplitInfo 是分裂信息，表示特征 A 将数据集 D 划分成多少份的信息量。这样即使一个特征取值很多，如果 SplitInfo 也很大，最终信息增益率也不会很高。

我们使用经典的天气预测数据集，包含 4 个特征和 1 个目标变量（是否出去玩）：

天气	温度	湿度	有风	出去玩
晴	高	高	否	否
晴	高	高	是	否
多云	高	高	否	是
雨	中	高	否	是
雨	低	正常	否	是
雨	低	正常	是	否
多云	低	正常	是	是
晴	中	高	否	否
晴	低	正常	否	是
雨	中	正常	否	是
晴	中	正常	是	是
多云	中	高	是	是
多云	高	正常	否	是
雨	中	高	是	否

计算初始信息熵：

$$ Ent(D) = -\frac{5}{14}\log_2\frac{5}{14} – \frac{9}{14}\log_2\frac{9}{14} ≈ 0.940 $$

以 ” 天气 ” 为例计算信息增益：
晴:5 个样本 (2 是,3 否)
多云:4 个样本 (4 是,0 否)
雨:5 个样本 (3 是,2 否)

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

$$ Ent(多云) = 0 $$

$$ Ent(雨) ≈ 0.971 $$

$$ Gain(D, 天气) = 0.940 – (\frac{5}{14}×0.971 + \frac{4}{14}×0 + \frac{5}{14}×0.971) ≈ 0.246 $$

计算分裂信息：

$$ SplitInfo(D, 天气) = -\frac{5}{14}\log_2\frac{5}{14} – \frac{4}{14}\log_2\frac{4}{14} – \frac{5}{14}\log_2\frac{5}{14} ≈ 1.577 $$

信息增益率：

$$ GainRatio(D, 天气) ≈ \frac{0.246}{1.577} ≈ 0.156 $$

对于 ” 温度 ” 这样的连续特征，C4.5 的做法是：

将温度值排序：[低, 低, 低, 中, 中, 中, 中, 高, 高, 高, 高, 高]
计算相邻值的中间点作为候选分割点
对每个分割点计算信息增益率
选择信息增益率最大的分割点

经计算，温度的最佳分割点是 ” 中 ”，将温度分为≤中和 > 中两组。

选择信息增益率最大的特征作为当前节点的分裂特征，然后对每个子节点递归执行上述过程，直到：

所有样本属于同一类别
没有剩余特征可供划分
节点样本数小于预定阈值

from sklearn.tree import DecisionTreeClassifier
import pandas as pd

# 准备数据
data = {
    'Outlook': ['Sunny','Sunny','Overcast','Rainy','Rainy','Rainy','Overcast','Sunny',
               'Sunny','Rainy','Sunny','Overcast','Overcast','Rainy'],
    'Temp': ['High','High','High','Medium','Low','Low','Low','Medium',
            'Low','Medium','Medium','Medium','High','Medium'],
    'Humidity': ['High','High','High','High','Normal','Normal','Normal','High',
                'Normal','Normal','Normal','High','Normal','High'],
    'Windy': [False,True,False,False,False,True,True,False,
             False,False,True,True,False,True],
    'Play': ['No','No','Yes','Yes','Yes','No','Yes','No',
            'Yes','Yes','Yes','Yes','Yes','No']
}

df = pd.DataFrame(data)

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

# 训练模型
clf = DecisionTreeClassifier(criterion='entropy', max_depth=3)
clf.fit(df.drop('Play',axis=1), df['Play'])

# 可视化决策树
from sklearn.tree import plot_tree
import matplotlib.pyplot as plt
plt.figure(figsize=(12,8))
plot_tree(clf, feature_names=df.drop('Play',axis=1).columns, 
          class_names=['No','Yes'], filled=True)
plt.show()