第5章：决策树（Decision Tree）
一、导读
1.1 本章学习目标
第5章介绍决策树——一种直观的分类和回归方法。决策树通过树形结构进行决策：内部节点表示特征测试，分支表示测试结果，叶节点表示最终决策。决策树的优势在于其可解释性——你可以清晰地看到"如果特征A>0.5且特征B<0.3，则分类为正类"这样的规则。
本章的核心学习目标包括：
- 理解决策树的结构：内部节点、分支、叶节点的含义
- 掌握三种经典算法：ID3（信息增益）、C4.5（信息增益比）、CART（基尼指数）
- 理解特征选择的准则：为什么不同的准则会导致不同的决策树？
- 掌握剪枝策略：预剪枝和后剪枝如何防止过拟合？
- 理解如何处理连续值和缺失值
- 实现CART决策树算法
1.2 为什么本章如此重要
决策树是机器学习中最直观、最可解释的模型之一。它不需要特征标准化，可以处理数值和类别特征，天然支持多分类，而且生成的规则易于理解和解释。在需要可解释性的场景（如医疗诊断、金融风控）中，决策树往往是首选。
更重要的是，决策树是许多强大集成方法的基础。随机森林、梯度提升树（GBDT）、XGBoost、LightGBM——这些在数据科学竞赛中表现最好的算法，都以决策树为基学习器。理解决策树，就是理解这些强大算法的基石。
1.3 核心问题引导
在阅读本章时，请带着以下问题思考：
决策树是如何选择特征的？信息增益、信息增益比、基尼指数有什么区别？
为什么ID3算法倾向于选择取值多的特征？C4.5如何修正这个问题？
CART算法为什么使用基尼指数而不是信息增益？
决策树为什么会过拟合？剪枝是如何解决这个问题的？
预剪枝和后剪枝各有什么优缺点？
如何处理连续特征和缺失值？
二、核心概念详解
5.1 决策树的结构
决策树是一种树形结构：
- 根节点：包含所有训练样本，进行第一次特征测试
- 内部节点：对应一个特征测试，将样本划分到不同分支
- 分支：对应特征测试的一个可能结果
- 叶节点：对应一个最终的决策（类别或数值）
python
# 决策树的直观表示
# 决策树示例：判断是否去打网球
"""
天气 = ?
/ | \
晴天 阴天 雨天
| | |
湿度=? 打球 风力=?
/ \ / \
高 正常 强 弱
| | | |
不打 打球 不打 打球
"""5.2 特征选择：信息增益（ID3）
ID3算法使用信息增益（Information Gain）来选择特征。信息增益越大，说明该特征对分类的贡献越大。
5.2.1 信息熵
信息熵（Entropy）度量数据集的混乱程度：
H(D) = - Σ_k (|C_k| / |D|) * log2(|C_k| / |D|)其中 C_k 是类别 k 的样本集合。熵越大，数据集越混乱。
5.2.2 条件熵
条件熵度量在已知特征 A 的条件下，数据集的不确定性：
H(D|A) = Σ_v (|D_v| / |D|) * H(D_v)其中 D_v 是特征 A 取值为 v 的样本集合。
5.2.3 信息增益
信息增益 = 数据集的熵 - 条件熵：
g(D, A) = H(D) - H(D|A)python
import numpy as np
def entropy(y):
"""计算信息熵"""
_, counts = np.unique(y, return_counts=True)
probs = counts / len(y)
return -np.sum(probs * np.log2(probs + 1e-10))
def conditional_entropy(X, feature_idx, y):
"""计算条件熵"""
values = np.unique(X[:, feature_idx])
h = 0
for v in values:
mask = X[:, feature_idx] == v
h += np.sum(mask) / len(y) * entropy(y[mask])
return h
def information_gain(X, feature_idx, y):
"""计算信息增益"""
return entropy(y) - conditional_entropy(X, feature_idx, y)
# 示例
X = np.array([
[0, 0], [0, 1], [0, 1], [0, 0],
[1, 0], [1, 1], [1, 1], [1, 0],
[0, 0], [0, 1], [1, 0], [1, 1],
])
y = np.array([0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1])
print(f"数据集熵: {entropy(y):.4f}")
for i in range(X.shape[1]):
ig = information_gain(X, i, y)
print(f"特征{i}的信息增益: {ig:.4f}")5.3 信息增益比（C4.5）
ID3算法有一个缺陷：倾向于选择取值多的特征。例如，如果用"样本编号"作为特征，信息增益会非常大（每个样本一个分支，每个分支熵为0），但这显然没有意义。
C4.5算法使用信息增益比（Gain Ratio）来修正这个问题：
g_R(D, A) = g(D, A) / H_A(D)其中 H_A(D) 是特征 A 的固有值（Intrinsic Value）：
H_A(D) = - Σ_v (|D_v| / |D|) * log2(|D_v| / |D|)取值越多的特征，H_A(D) 越大，信息增益比会被惩罚。
python
import numpy as np
def intrinsic_value(X, feature_idx):
"""计算特征的固有值"""
values = np.unique(X[:, feature_idx])
h = 0
for v in values:
p = np.sum(X[:, feature_idx] == v) / len(X)
if p > 0:
h -= p * np.log2(p)
return h
def gain_ratio(X, feature_idx, y):
"""计算信息增益比"""
ig = information_gain(X, feature_idx, y)
iv = intrinsic_value(X, feature_idx)
if iv == 0:
return 0
return ig / iv
# 对比
print(f"{'特征':>5} {'信息增益':>10} {'固有值':>10} {'增益比':>10}")
print("-" * 38)
for i in range(X.shape[1]):
ig = information_gain(X, i, y)
iv = intrinsic_value(X, i)
gr = gain_ratio(X, i, y)
print(f"{i:>5} {ig:>10.4f} {iv:>10.4f} {gr:>10.4f}")5.4 基尼指数（CART）
CART（Classification and Regression Trees）算法使用基尼指数（Gini Index）来选择特征。
5.4.1 基尼指数
数据集 D 的基尼指数：
Gini(D) = 1 - Σ_k p_k^2其中 p_k 是类别 k 的比例。基尼指数越小，数据集越"纯净"。
5.4.2 特征 A 的基尼指数
在特征 A 的条件下，数据集的基尼指数：
Gini(D, A) = Σ_v (|D_v| / |D|) * Gini(D_v)选择使 Gini(D, A) 最小的特征。
python
import numpy as np
def gini_index(y):
"""计算基尼指数"""
_, counts = np.unique(y, return_counts=True)
probs = counts / len(y)
return 1 - np.sum(probs ** 2)
def gini_for_feature(X, feature_idx, y):
"""计算特征划分后的基尼指数"""
values = np.unique(X[:, feature_idx])
gini = 0
for v in values:
mask = X[:, feature_idx] == v
gini += np.sum(mask) / len(y) * gini_index(y[mask])
return gini
# 示例
print(f"数据集基尼指数: {gini_index(y):.4f}")
for i in range(X.shape[1]):
g = gini_for_feature(X, i, y)
print(f"特征{i}的基尼指数: {g:.4f}")5.5 CART算法
CART算法既可以用于分类，也可以用于回归。
5.5.1 分类树
CART分类树使用基尼指数选择特征，生成二叉树（每个节点只有两个分支）。
对于二值特征 A：
Gini(D, A=a) = (|D1|/|D|) * Gini(D1) + (|D2|/|D|) * Gini(D2)其中 D1 是 A=a 的样本，D2 是 A≠a 的样本。
对于连续特征 A，CART 遍历所有可能的切分点：
Gini(D, A≤s) = (|D1|/|D|) * Gini(D1) + (|D2|/|D|) * Gini(D2)python
import numpy as np
class DecisionTreeNode:
def __init__(self):
self.feature = None
self.threshold = None
self.left = None
self.right = None
self.value = None # 叶节点的类别
class CARTClassifier:
def __init__(self, max_depth=5, min_samples_split=2):
self.max_depth = max_depth
self.min_samples_split = min_samples_split
def _gini(self, y):
if len(y) == 0:
return 0
_, counts = np.unique(y, return_counts=True)
probs = counts / len(y)
return 1 - np.sum(probs ** 2)
def _best_split(self, X, y):
best_gini = float('inf')
best_feature = None
best_threshold = None
for feature in range(X.shape[1]):
thresholds = np.unique(X[:, feature])
for threshold in thresholds:
left_mask = X[:, feature] <= threshold
right_mask = ~left_mask
if np.sum(left_mask) == 0 or np.sum(right_mask) == 0:
continue
n = len(y)
gini = (np.sum(left_mask) / n * self._gini(y[left_mask]) +
np.sum(right_mask) / n * self._gini(y[right_mask]))
if gini < best_gini:
best_gini = gini
best_feature = feature
best_threshold = threshold
return best_feature, best_threshold
def _build_tree(self, X, y, depth):
node = DecisionTreeNode()
# 停止条件
if depth >= self.max_depth or len(y) < self.min_samples_split or len(np.unique(y)) == 1:
_, counts = np.unique(y, return_counts=True)
node.value = np.argmax(counts)
return node
feature, threshold = self._best_split(X, y)
if feature is None:
_, counts = np.unique(y, return_counts=True)
node.value = np.argmax(counts)
return node
node.feature = feature
node.threshold = threshold
left_mask = X[:, feature] <= threshold
right_mask = ~left_mask
node.left = self._build_tree(X[left_mask], y[left_mask], depth + 1)
node.right = self._build_tree(X[right_mask], y[right_mask], depth + 1)
return node
def fit(self, X, y):
self.root = self._build_tree(X, y, 0)
return self
def _predict_one(self, x, node):
if node.value is not None:
return node.value
if x[node.feature] <= node.threshold:
return self._predict_one(x, node.left)
else:
return self._predict_one(x, node.right)
def predict(self, X):
return np.array([self._predict_one(x, self.root) for x in X])
# 测试
from sklearn.datasets import load_iris
iris = load_iris()
X, y = iris.data, iris.target
tree = CARTClassifier(max_depth=3)
tree.fit(X[:120], y[:120])
accuracy = np.mean(tree.predict(X[120:]) == y[120:])
print(f"CART决策树准确率: {accuracy:.4f}")5.6 剪枝策略
决策树容易过拟合。剪枝是防止过拟合的重要手段。
5.6.1 预剪枝（Pre-pruning）
在构建过程中提前停止：
- 限制最大深度
- 限制最小样本数
- 限制信息增益阈值
5.6.2 后剪枝（Post-pruning）
先构建完整的树，然后自底向上剪枝。如果剪掉一个子树后验证集准确率不降低（或提升），就剪掉。
python
import numpy as np
def cross_validate_pruning(X, y, max_depths, k=5):
"""通过交叉验证选择最优最大深度（预剪枝）"""
from collections import Counter
results = {}
for max_depth in max_depths:
scores = []
n = len(X)
fold_size = n // k
for i in range(k):
start = i * fold_size
end = start + fold_size if i < k - 1 else n
val_idx = list(range(start, end))
train_idx = list(range(0, start)) + list(range(end, n))
tree = CARTClassifier(max_depth=max_depth)
tree.fit(X[train_idx], y[train_idx])
score = np.mean(tree.predict(X[val_idx]) == y[val_idx])
scores.append(score)
results[max_depth] = (np.mean(scores), np.std(scores))
print(f"{'最大深度':>8} {'准确率':>10} {'标准差':>10}")
print("-" * 30)
for depth, (mean, std) in results.items():
print(f"{depth:>8} {mean:>10.4f} {std:>10.4f}")
best_depth = max(results, key=lambda x: results[x][0])
print(f"\n最优最大深度: {best_depth}")
# 测试
iris = load_iris()
cross_validate_pruning(iris.data, iris.target, max_depths=[1, 2, 3, 4, 5, 10])5.7 特征重要性
决策树可以自然地给出特征重要性：每个特征在树中被使用的次数和位置反映了它的重要性。
python
import numpy as np
def feature_importance(tree, X, y):
"""从决策树中提取特征重要性"""
importance = np.zeros(X.shape[1])
def traverse(node, n_samples):
if node is None or node.value is not None:
return
importance[node.feature] += n_samples
traverse(node.left, n_samples // 2)
traverse(node.right, n_samples // 2)
traverse(tree.root, len(X))
importance /= importance.sum()
return importance
# 测试
iris = load_iris()
tree = CARTClassifier(max_depth=4)
tree.fit(iris.data, iris.target)
imp = feature_importance(tree, iris.data, iris.target)
feature_names = iris.feature_names
print("特征重要性:")
for name, importance in sorted(zip(feature_names, imp), key=lambda x: -x[1]):
print(f" {name}: {importance:.4f}")三、实战案例
3.1 鸢尾花数据集上的决策树
python
import numpy as np
from sklearn.datasets import load_iris
iris = load_iris()
X, y = iris.data, iris.target
# 训练决策树
tree = CARTClassifier(max_depth=3)
tree.fit(X, y)
accuracy = np.mean(tree.predict(X) == y)
print(f"训练准确率: {accuracy:.4f}")
# 打印决策规则
def print_rules(node, depth=0, conditions=[]):
if node is None:
return
if node.value is not None:
cond_str = " AND ".join(conditions) if conditions else "ALL"
print(f"{' ' * depth}IF {cond_str} THEN class={node.value}")
return
feature_name = iris.feature_names[node.feature]
print_rules(node.left, depth + 1, conditions + [f"{feature_name} <= {node.threshold:.2f}"])
print_rules(node.right, depth + 1, conditions + [f"{feature_name} > {node.threshold:.2f}"])
print("\n决策规则:")
print_rules(tree.root)3.2 不同特征选择准则的对比
python
import numpy as np
def compare_split_criteria():
"""对比信息增益、信息增益比和基尼指数"""
np.random.seed(42)
# 生成数据：特征0有3个值，特征1有10个值
n = 300
X = np.column_stack([
np.random.choice([0, 1, 2], n),
np.random.choice(range(10), n),
])
y = (X[:, 0] > 0).astype(int) # 只有特征0有用
print(f"{'特征':>5} {'信息增益':>10} {'增益比':>10} {'基尼指数':>10}")
print("-" * 38)
for i in range(2):
ig = information_gain(X, i, y)
gr = gain_ratio(X, i, y)
gi = gini_for_feature(X, i, y)
print(f"{i:>5} {ig:>10.4f} {gr:>10.4f} {gi:>10.4f}")
print("\n特征1取值多，信息增益大，但增益比正确地惩罚了这一点")
compare_split_criteria()四、本章小结
第5章介绍了决策树：
决策树结构：内部节点（特征测试）、分支（测试结果）、叶节点（决策）。
特征选择：ID3用信息增益，C4.5用信息增益比（修正取值偏好），CART用基尼指数。
CART算法：生成二叉树，可用于分类（基尼指数）和回归（平方误差）。
剪枝：预剪枝限制树的生长，后剪枝在完整树基础上回退。两者都防止过拟合。
特征重要性：决策树自然地给出特征重要性排序。
决策树的核心启示是：可解释性和性能可以兼得。决策树生成的规则易于理解，同时通过集成方法可以达到很高的性能。
五、思考与练习
思考题
信息增益为什么倾向于选择取值多的特征？信息增益比如何修正这个问题？
CART算法为什么生成二叉树而不是多叉树？这有什么优势？
预剪枝和后剪枝各有什么优缺点？在实际中如何选择？
决策树对数据的哪些特性敏感？哪些不敏感？
如何用决策树处理回归问题？
编程练习
从零实现CART分类树，在鸢尾花数据集上测试，并可视化决策规则。
实现预剪枝（限制最大深度和最小样本数），观察对过拟合的影响。
实现特征重要性的计算，在鸢尾花数据集上分析哪些特征最重要。