ReaderMX.
原力注入

动手学决策树算法

原GrissomFI约 8 分钟

决策树算法简介

代码地址：https://github.com/ForceInjection/hands-on-ML/blob/main/nju_software/%E5%86%B3%E7%AD%96%E6%A0%91.ipynb


1. 决策树

1.1 什么是决策树

决策树是一种监督学习算法，广泛应用于分类和回归任务。它通过递归地分裂数据集，将数据分成越来越小的子集，直到达到某种停止条件。每个内部节点表示一个特征或属性，每个分支表示一个决策规则，每个叶节点表示一个类别或预测值。决策树的结构直观，易于理解和解释，因此在许多领域都有广泛应用。

1.2 决策树的结构

  • 根节点：包含所有样本的初始节点。
  • 内部节点：表示一个特征或属性的测试。
  • 叶节点：表示一个类别或预测值。
  • 分支：表示根据特征测试结果的决策路径。

1.3 决策树的构建过程

  1. 选择分裂特征：使用信息增益、基尼指数等指标选择最佳的分裂特征。
  2. 递归分裂：对每个子节点重复分裂过程，直到满足停止条件。
  3. 停止条件：所有样本属于同一类，或没有更多特征可以分裂，或达到预设的树深度。

1.4 决策树的优缺点

  • 优点：
    • 可解释性强，决策过程直观。
    • 能够处理非线性关系。
    • 对缺失值和异常值有一定的鲁棒性。
  • 缺点：
    • 容易过拟合，导致泛化能力下降。
    • 对数据的小变化敏感，可能导致树结构的不稳定。

2. 信息熵

对于一个离散的随机变量 ，其概率分布为 ，信息熵  定义为：

其中， 是随机变量  取值为   的概率， 表示以2为底的对数。

2.1 信息熵的性质

  1. 非负性：信息熵总是非负的，即 。
  2. 对称性：信息熵对概率分布的顺序不敏感，即  与  的顺序无关。
  3. 最大值：当所有  相等时，信息熵达到最大值。对于  个等概率事件，最大信息熵为 。
  4. 最小值：当某个  且其他  时，信息熵达到最小值0。

2.2 信息熵的直观解释

信息熵可以理解为对随机变量的平均信息量的度量。例如，考虑一个公平的六面骰子，每个面的概率都是 。此时，信息熵为：

这表示掷一次骰子的平均信息量约为2.585比特。

2.3 信息熵的计算示例

假设有一个二分类问题，其中类别A的概率为0.7，类别B的概率为0.3。计算信息熵：

2.4 信息熵的物理意义

信息熵是衡量随机变量不确定性的指标。熵值越高，表示不确定性越大；熵值越低，表示不确定性越小。

3. 信息增益

信息增益（Information Gain）是信息熵的一个重要应用，用于衡量某个特征对减少不确定性的作用。信息增益定义为：

其中， 是随机变量  的信息熵， 是在已知特征  的条件下，随机变量  的条件信息熵。

3.1 信息增益的物理意义

信息增益衡量了某个特征对减少不确定性的作用。信息增益越大，表示该特征对分类的贡献越大。

3.2 信息增益的计算示例

假设有一个数据集，包含两个特征  和 ，以及目标变量 。计算特征  的信息增益：

  1. 计算根节点的信息熵 。
  2. 计算在已知特征  的条件下，目标变量  的条件信息熵 。
  3. 信息增益 。

4. 示例

4.1 数据集

以下是一个简单的数据集，用于预测是否玩高尔夫球。数据集包括天气（晴天、多云、下雨）和湿度（高、正常）两个特征，以及目标变量是否玩高尔夫球（是或否）。

天气
湿度
是否玩高尔夫球
晴天
高
否
晴天
高
否
晴天
高
是
多云
高
是
多云
正常
是
下雨
高
否
下雨
正常
是
下雨
正常
是
晴天
正常
是
晴天
正常
是
多云
高
是
多云
正常
是
下雨
高
否
下雨
正常
是

4.2 决策树构建的过程

决策树的构建过程通常包括以下几个步骤：

  1. 计算根节点的信息熵。
  2. 计算每个特征的信息增益。
  3. 选择信息增益最大的特征作为分裂特征。
  4. 递归地对每个子节点重复上述步骤，直到所有样本都属于同一类或没有更多特征可以分裂。

4.3 决策树构建的过程（ID3 算法）

接下来，我们将使用 ID3 算法手工构建决策树。以下是详细的步骤：

4.3.1 计算根节点的信息熵

信息熵的公式为：

其中， 是类别  在数据集  中的比例。

在根节点中，数据集  包含 14 个样本，其中“是”的有 9 个，“否”的有 5 个。

4.3.2 计算每个特征的信息增益

信息增益的公式为：

4.3.2.1 计算“天气”的信息增益

“天气”有三种取值：晴天、多云、下雨。

  • 晴天：有 5 个样本，其中“是”的有 2 个，“否”的有 3 个。

  • 多云：有 4 个样本，全是“是”。

  • 下雨：有 5 个样本，其中“是”的有 3 个，“否”的有 2 个。

加权平均熵：

“天气”的信息增益：

4.3.2.2 计算“湿度”的信息增益

“湿度”有两种取值：高、正常。

  • 高：有 7 个样本，其中“是”的有 3 个，“否”的有 4 个。

  • 正常：有 7 个样本，全是“是”。

加权平均熵：

“湿度”的信息增益：

4.3.3 选择信息增益最大的特征作为分裂特征

比较“天气”和“湿度”的信息增益：

“湿度”的信息增益更大，因此选择“湿度”作为根节点的分裂特征。

4.3.4 递归地对每个子节点重复上述步骤

4.3.4.1 子节点 1：湿度为“高”

在湿度为“高”的子节点中，有 7 个样本，其中“是”的有 3 个，“否”的有 4 个。

计算“天气”的信息增益：

  • 晴天：有 3 个样本，全是“否”。

  • 多云：有 1 个样本，是“是”。

  • 下雨：有 3 个样本，全是“否”。

加权平均熵：

“天气”的信息增益：

选择“天气”作为分裂特征。

4.3.4.2 子节点 2：湿度为“正常”

在湿度为“正常”的子节点中，有 7 个样本，全是“是”。

由于所有样本都属于同一类，停止分裂。

4.4 决策树

根据上述步骤，构建的决策树如下：

ounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(line        湿度        /  \      高   正常      /      \    天气      是    /  |  \  晴天 多云 下雨   否   是   否

4.5 总结

通过上述步骤，我们使用 ID3 算法手工构建了决策树。最终的决策树以“湿度”为根节点，根据湿度的取值进一步分裂，直到所有样本都属于同一类。

5. 参考文献

  • [1] Quinlan, J. R. (1986). Induction of Decision Trees. Machine Learning, 1(1), 81-106.
  • [2] Mitchell, T. M. (1997). Machine Learning. McGraw-Hill.

6. 总结

决策树是一种直观且强大的监督学习算法，通过递归地分裂数据集来构建树结构。信息熵和信息增益是选择分裂特征的关键指标，能够有效减少不确定性，提高分类准确性。通过上述示例，我们详细展示了如何使用ID3算法构建决策树，希望对读者理解和应用决策树算法有所帮助。

7. 示例代码

7.1 Python 代码

ounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(linefrom sklearn.tree import DecisionTreeClassifierfrom sklearn.preprocessing import LabelEncoderimport pandas as pdimport matplotlib.pyplot as pltfrom matplotlib import rcParamsfrom sklearn.tree import plot_treefrom sklearn.tree import export_textfrom matplotlib.text import Text
# 配置 matplotlib 使用字体rcParams['font.sans-serif'] = ['Heiti TC']rcParams['axes.unicode_minus'] = False  # 解决负号显示问题
# 创建数据集data = {    '天气': ['晴天', '晴天', '晴天', '多云', '多云', '下雨', '下雨', '下雨', '晴天', '晴天', '多云', '多云', '下雨', '下雨'],    '湿度': ['高', '高', '高', '高', '正常', '高', '正常', '正常', '正常', '正常', '高', '正常', '高', '正常'],    '是否玩高尔夫球': ['否', '否', '是', '是', '是', '否', '是', '是', '是', '是', '是', '是', '否', '是']}
# 将数据转换为 DataFramedf = pd.DataFrame(data)
print(df.to_string(index=False))
# 对特征进行编码le_weather = LabelEncoder()le_humidity = LabelEncoder()df['天气_encoded'] = le_weather.fit_transform(df['天气'])df['湿度_encoded'] = le_humidity.fit_transform(df['湿度'])
# 特征和目标变量X = df[['天气_encoded', '湿度_encoded']]  # 确保 X 是一个 DataFramey = df['是否玩高尔夫球']
# 创建决策树分类器clf = DecisionTreeClassifier(criterion='entropy', random_state=42)
# 训练模型clf.fit(X, y)
# 打印决策树的结构plt.figure(figsize=(18, 12))tree_plot = plot_tree(clf, feature_names=['天气', '湿度'], class_names=['否', '是'], filled=True, rounded=True)# 遍历图中的每个文本元素并调整字体大小for t in plt.gca().get_children():    if isinstance(t, Text):        t.set_fontsize(18)  # 设置字体大小为 10plt.show()
# 通过文本打印决策树tree_rules = export_text(clf, feature_names=['天气', '湿度'])print("决策树文本结构:")print(tree_rules)
# 预测新样本new_samples = [    [le_weather.transform(['晴天'])[0], le_humidity.transform(['高'])[0]],  # 晴天, 高    [le_weather.transform(['晴天'])[0], le_humidity.transform(['正常'])[0]],  # 晴天, 正常    [le_weather.transform(['多云'])[0], le_humidity.transform(['高'])[0]],  # 多云, 高    [le_weather.transform(['多云'])[0], le_humidity.transform(['正常'])[0]],  # 多云, 正常    [le_weather.transform(['下雨'])[0], le_humidity.transform(['高'])[0]],  # 下雨, 高    [le_weather.transform(['下雨'])[0], le_humidity.transform(['正常'])[0]]  # 下雨, 正常]
# 将 new_samples 转换为 DataFrame，并设置列名new_samples_df = pd.DataFrame(new_samples, columns=['天气_encoded', '湿度_encoded'])
# 使用 DataFrame 进行预测predictions = clf.predict(new_samples_df)print("预测结果:")for sample, prediction in zip(new_samples, predictions):    print(f"天气: {le_weather.inverse_transform([sample[0]])[0]}, 湿度: {le_humidity.inverse_transform([sample[1]])[0]} → {prediction}")

7.2 运行结果

ounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(lineounter(line天气 湿度 是否玩高尔夫球晴天  高       否晴天  高       否晴天  高       是多云  高       是多云 正常       是下雨  高       否下雨 正常       是下雨 正常       是晴天 正常       是晴天 正常       是多云  高       是多云 正常       是下雨  高       否下雨 正常       是
# 图见最后
决策树文本结构:|--- 湿度 <= 0.50|   |--- class: 是|--- 湿度 >  0.50|   |--- 天气 <= 0.50|   |   |--- class: 否|   |--- 天气 >  0.50|   |   |--- 天气 <= 1.50|   |   |   |--- class: 是|   |   |--- 天气 >  1.50|   |   |   |--- class: 否
预测结果:天气: 晴天, 湿度: 高 → 否天气: 晴天, 湿度: 正常 → 是天气: 多云, 湿度: 高 → 是天气: 多云, 湿度: 正常 → 是天气: 下雨, 湿度: 高 → 否天气: 下雨, 湿度: 正常 → 是
tree
tree

KEEP THE THREAD GOING

更多来源文章

Kimi K3 注意力机制深度解析：KDA、Gated MLA 与 AttnRes 的混合架构

2.8 万亿参数的 Kimi K3 原生支持 1M token 上下文窗口。它的注意力系统不是单一种类的升级，而是三种机制的协同设计：69 层 KDA负责高效长上下文处理，24 层 Gated MLA 提供全局精确检索锚点，Attention Residuals 则将"注意力"从序列维度扩展到模型深度维度

阅读全文