机器学习-算法-决策树

发表于 | 分类于 ，

决策树简介

决策树（Decision Tree）是一种基本的监督学习方法，可用于分类与回归。它将特征空间递归地划分为若干区域，每个区域对应一个预测值；从根节点到叶节点的路径，等价于一条 if-else 判定规则。决策树的可解释性极强——训练得到的”知识”以层次结构直接呈现，非专业人员也能读懂。

段末注释：监督学习（Supervised Learning） 指利用带标签样本学习输入到输出的映射；分类（Classification） 预测离散类别，回归（Regression） 预测连续数值。

读前说明：配图位于同名目录 1201.机器学习-算法-决策树/；正文图链写 ./1201.机器学习-算法-决策树/文件名，便于编辑器预览与 Hexo 部署。

产生的基础

决策树的思想可追溯至 20 世纪 60 年代的模式识别研究，但真正系统化是在信息论与统计学习发展起来之后：

算法 提出者 / 时间 核心贡献
ID3 Ross Quinlan，1986 以信息增益（Information Gain）为分裂准则，面向离散特征
C4.5 Ross Quinlan，1993 引入信息增益率，支持连续特征与缺失值处理
CART Breiman 等，1984 可同时做分类与回归；分类用基尼指数（Gini Index），回归用均方误差（MSE）

决策树算法演进时间线

图：决策树三代经典算法演进——ID3 用信息增益处理离散特征，C4.5 引入信息增益率并支持连续值，CART 以基尼/MSE 统一分类与回归。

其理论基础来自：

  1. 信息论：Shannon 熵（Entropy）度量集合的不确定性，选择能最大程度降低不确定性的特征进行分裂。
  2. 分而治之（Divide and Conquer）：将复杂问题递归分解为若干简单子问题，与人类逐步做判断的思维方式一致。
  3. 贪心搜索（Greedy Search）：每一步只选当前最优分裂，不做全局回溯——计算高效，但不保证全局最优。

段末注释：信息增益（Information Gain，IG） 衡量用某特征分裂后数据集不确定性下降的幅度；基尼指数（Gini Index） 衡量从集合中随机抽两个样本、其类别不一致的概率。

算法原理

决策树算法原理示意图

图：自上而下——根/内部/叶三类节点构成树形判定结构；中间按”纯度提升最大”递归切分样本；底部对比分裂前后的混乱度（熵），右侧剪枝抑制过拟合。

1. 树结构

一棵决策树由三类节点组成：

  • 根节点（Root）：包含全部训练样本，从这里开始分裂。
  • 内部节点（Internal Node）：对应一次特征测试（如”年龄 ≤ 30？”）。
  • 叶节点（Leaf）：给出最终预测——分类任务输出类别（或各类别概率），回归任务输出均值。

从根到叶的路径构成一条判定序列；整棵树可视为特征空间上的分段常数函数（分类）或分段线性/常数逼近（回归）。

2. 训练过程（递归建树）

1
2
3
4
5
6
输入：训练集 D，特征集 A
1. 若 D 中样本全属同一类（或 |D| ≤ 阈值），标记为叶节点，返回
2. 在 A 中选取使"纯度提升最大"的特征 a 及其最优切分点
3. 按 a 将 D 划分为若干子集 D₁, D₂, ...
4. 对每个 Dᵢ 递归调用上述过程
5. 返回以 a 为根的子树

“纯度”的度量方式决定算法变体，常见三种：

信息熵与信息增益（ID3 / C4.5）

数据集 $D$ 的熵定义为：

$$H(D) = -\sum_{k=1}^{K} p_k \log_2 p_k$$

其中 $p_k$ 是第 $k$ 类样本在 $D$ 中的比例，$K$ 为类别数。

用特征 $a$ 分裂后的信息增益为：

$$\text{IG}(D, a) = H(D) - \sum_{v \in \text{Values}(a)} \frac{|D_v|}{|D|} H(D_v)$$

ID3 选择使 $\text{IG}(D, a)$ 最大的特征；C4.5 改用信息增益率以惩罚取值过多的特征：

$$\text{GainRatio}(D, a) = \frac{\text{IG}(D, a)}{H_a(D)}$$

基尼指数（CART 分类）

$$Gini(D) = 1 - \sum_{k=1}^{K} p_k^2$$

选择使子节点加权基尼指数最小的特征与切分点。Scikit-Learn 默认使用 CART 实现。

均方误差（CART 回归）

对回归树，叶节点预测值为该区域内样本 $y$ 的均值；分裂准则为最小化：

$$MSE = \frac{1}{|D|}\sum_{i \in D}(y_i - \bar{y})^2$$

3. 剪枝（Pruning）

无约束生长的树会对训练集”死记硬背”，导致过拟合（Overfitting）。常用控制手段：

策略 做法 典型超参数
预剪枝 建树过程中提前停止 max_depth、min_samples_split、min_samples_leaf
后剪枝 先建满树，再自底向上合并子树 ccp_alpha（代价复杂度剪枝）

代价复杂度剪枝的目标函数为：

$$C_\alpha(T) = C(T) + \alpha |T|$$

其中 $C(T)$ 是树 $T$ 在训练集上的误差，$|T|$ 是叶节点数，$\alpha$ 控制复杂度惩罚力度。

4. 预测

  • 分类：从根节点出发，按样本特征值沿树向下走，到达叶节点后取该叶的类别（或概率分布）。
  • 回归：同样沿树向下，叶节点输出该区域内训练样本 $y$ 的均值。

适用场景

决策树适用场景示意图

图：决策树擅长”规则可读”的业务场景——医疗诊断、信贷审批、工业质检等；也适合混合特征、特征重要性分析与作为随机森林等集成方法的基学习器。

决策树在以下场景中表现突出：

  1. 需要强可解释性：医疗诊断规则、信贷审批、工业质检——业务方需要理解”为什么这样判”。
  2. 混合类型特征：同时含数值型（年龄、收入）与类别型（性别、地区）特征，无需手动 One-Hot 编码（sklearn 内部处理）。
  3. 非线性关系：通过分段划分自然捕捉特征间的交互，无需假设线性。
  4. 多分类问题：原生支持多类别，无需像二分类那样扩展。
  5. 特征重要性分析：分裂越靠前的特征、使纯度下降越多的特征，重要性越高。
  6. 作为集成基学习器：随机森林（Random Forest）、梯度提升树（GBDT、XGBoost、LightGBM）均以决策树为基模型，兼顾精度与（相对）可解释性。

典型应用：客户流失预测、疾病风险分层、传感器故障分类、房价区间估计等。

局限性

决策树局限性示意图

图：单棵决策树的四类典型局限——过拟合、贪心局部最优、轴对齐切分无力处理 XOR 模式、对训练扰动敏感；底部给出剪枝与集成等缓解思路。

局限 说明
易过拟合 树越深，对训练集拟合越细，泛化能力下降；必须配合剪枝或集成方法
贪心非全局最优 每步局部最优分裂不能保证整棵树最优；求最优树是 NP-Complete 问题
对数据扰动敏感 训练集微小变化可能导致树结构大幅改变（高方差）
轴对齐切分 每次只沿单一特征做垂直/水平切分，难以表达 XOR 等对角线边界
类别不平衡 多数类主导分裂，少数类易被忽略；需配合 class_weight 或采样策略
外推能力弱 回归树预测值不会超出训练集 $y$ 的范围

缓解思路：限制树深度、使用随机森林/GBDT 集成、交叉验证调参、对不平衡数据加权。

示例展示

直观例子：相亲决策

决策树符合人类”逐条判断”的思维：根据特征值做一系列独立决策，每条路径对应一种结论。

假设有人给你介绍对象，你了解到三个特点：白不白、富不富、美不美，据此决定去不去相亲。所有可能组合如下：

全部可能性

每当出现新对象，依次判断各特点，这个过程自然形成一棵树：

decision_tree_0.png

每一层提出一个问题，沿不同分支走到叶节点即做出决策（去 / 不去）。本质是对特征空间按某一维度切分，反复切分直至叶节点。

切分顺序不同，树形不同；树足够深时可在训练集上完全分对，但泛化会变差——这正是需要剪枝的原因。

若仔细观察，部分叶节点可以合并（例如多条路径都得出”去”），合并后树更简洁，也更容易看出哪些特征更重要：

decision_tree_1.png

数值例子：手动理解信息增益

样本 天气 温度 去游泳
1 晴 高 否
2 晴 中 是
3 阴 高 是
4 雨 低 否

4 个样本、2 类（是/否），初始熵：

$$H(D) = -\frac{2}{4}\log_2\frac{2}{4} - \frac{2}{4}\log_2\frac{2}{4} = 1.0 \text{ bit}$$

按”天气”分裂：晴→{否, 是}，阴→{是}，雨→{否}，子集加权熵 $= 0.811$，信息增益 $= 1.0 - 0.811 = 0.189$。

按”温度”分裂：高→{否, 是}，中→{是}，低→{否}，子集加权熵 $= 0.811$，信息增益同样 $= 0.189$。

此例中两个特征增益相同；实际数据中会选增益更大（或基尼下降更多）的特征优先分裂。

示例代码

1. 分类：Iris 数据集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, plot_tree
from sklearn.metrics import accuracy_score, classification_report
import matplotlib.pyplot as plt

# 加载数据
iris = load_iris()
X_train, X_test, y_train, y_test = train_test_split(
    iris.data, iris.target, test_size=0.3, random_state=42
)

# 训练决策树（预剪枝：限制深度与叶节点最小样本数）
clf = DecisionTreeClassifier(
    criterion="gini",       # 分裂准则：gini 或 entropy
    max_depth=3,
    min_samples_leaf=2,
    random_state=42,
)
clf.fit(X_train, y_train)

# 评估
y_pred = clf.predict(X_test)
print(f"准确率: {accuracy_score(y_test, y_pred):.3f}")
print(classification_report(y_test, y_pred, target_names=iris.target_names))

# 特征重要性
for name, imp in zip(iris.feature_names, clf.feature_importances_):
    print(f"{name}: {imp:.3f}")

# 可视化决策树
plt.figure(figsize=(12, 8))
plot_tree(
    clf,
    feature_names=iris.feature_names,
    class_names=iris.target_names,
    filled=True,
    rounded=True,
)
plt.title("Iris 决策树 (max_depth=3)")
plt.savefig("iris_decision_tree.png", dpi=150, bbox_inches="tight")
plt.show()

2. 回归：波士顿房价风格连续预测

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from sklearn.datasets import fetch_california_housing
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeRegressor
from sklearn.metrics import mean_squared_error, r2_score

housing = fetch_california_housing()
X_train, X_test, y_train, y_test = train_test_split(
    housing.data, housing.target, test_size=0.2, random_state=42
)

reg = DecisionTreeRegressor(
    max_depth=5,
    min_samples_leaf=10,
    random_state=42,
)
reg.fit(X_train, y_train)
y_pred = reg.predict(X_test)

print(f"MSE:  {mean_squared_error(y_test, y_pred):.3f}")
print(f"R²:   {r2_score(y_test, y_pred):.3f}")

3. 手动计算熵与信息增益

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import math
from collections import Counter

def entropy(labels):
    """计算标签列表的熵（以 bit 为单位）。"""
    n = len(labels)
    counts = Counter(labels)
    return -sum((c / n) * math.log2(c / n) for c in counts.values())

def information_gain(parent, children):
    """parent: 父节点标签列表；children: 各子节点标签列表的列表。"""
    n = len(parent)
    h_parent = entropy(parent)
    h_children = sum(len(c) / n * entropy(c) for c in children)
    return h_parent - h_children

# 对应上文"去游泳"示例
labels = ["否", "是", "是", "否"]
print(f"H(D) = {entropy(labels):.3f}")

# 按"天气"分裂：晴={否,是}，阴={是}，雨={否}
gain_weather = information_gain(
    labels,
    [["否", "是"], ["是"], ["否"]],
)
print(f"IG(天气) = {gain_weather:.3f}")

# 按"温度"分裂：高={否,是}，中={是}，低={否}
gain_temp = information_gain(
    labels,
    [["否", "是"], ["是"], ["否"]],
)
print(f"IG(温度) = {gain_temp:.3f}")

4. 超参数调优建议

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from sklearn.model_selection import GridSearchCV

param_grid = {
    "max_depth": [3, 5, 7, None],
    "min_samples_split": [2, 5, 10],
    "min_samples_leaf": [1, 2, 5],
    "criterion": ["gini", "entropy"],
}

grid = GridSearchCV(
    DecisionTreeClassifier(random_state=42),
    param_grid,
    cv=5,
    scoring="accuracy",
)
grid.fit(X_train, y_train)
print("最优参数:", grid.best_params_)
print("交叉验证得分:", grid.best_score_)

小结

维度 要点
基础 源于信息论与分治思想；ID3 → C4.5 → CART 逐步完善
原理 贪心递归分裂，以熵/基尼/MSE 衡量纯度；剪枝控制复杂度
适用 可解释分类/回归、混合特征、特征重要性、集成基模型
局限 过拟合、非全局最优、轴对齐切分、对扰动敏感
实践 sklearn DecisionTreeClassifier / DecisionTreeRegressor + plot_tree 可视化

Reference

  1. Scikit-Learn 决策树文档
  2. Quinlan, J. R. (1986). Induction of Decision Trees. Machine Learning, 1(1), 81–106.
  3. Breiman, L. et al. (1984). Classification and Regression Trees. Wadsworth.
-------------本文结束感谢您的阅读-------------