第4章：决策树（Decision Trees）
一、导读
1.1 本章学习目标
第4章介绍决策树——一种直观、可解释的分类与回归方法。决策树通过一系列特征测试将数据递归划分，形成树形结构，每个叶节点对应一个预测结果。决策树不仅可以用于分类，还可以用于回归，是集成学习中最重要的基学习器。
本章的核心学习目标包括：
- 理解决策树的基本思想：通过特征测试递归划分数据空间，形成"if-then"规则
- 掌握三种特征选择准则：信息增益（ID3）、增益率（C4.5）、基尼指数（CART）
- 理解剪枝策略：预剪枝和后剪枝的区别、各自的优势和风险
- 掌握连续值和缺失值的处理方法：如何在决策树中处理非离散特征
- 理解决策树的可解释性：为什么决策树在实际应用中仍然广泛使用
- 了解决策树的优缺点：哪些场景适合使用决策树
1.2 为什么本章如此重要
决策树是机器学习中最直观的算法之一。它的决策过程可以自然地表示为"if-then"规则，非常适合需要可解释性的场景（如医疗诊断、金融风控）。同时，决策树也是集成学习的核心组件——随机森林、GBDT、XGBoost 等强大算法都以决策树为基学习器。
从理论角度看，决策树的特征选择过程与信息论密切相关。信息熵、信息增益等概念不仅是决策树的核心，也是理解特征选择、模型复杂度等问题的重要工具。
1.3 核心问题引导
决策树是如何选择"最优"特征来划分数据的？
信息增益为什么偏好取值较多的特征？增益率如何解决这个问题？
基尼指数和信息熵有什么区别？为什么 CART 选择基尼指数？
不剪枝的决策树会怎样？预剪枝和后剪枝各有什么优缺点？
连续特征（如年龄、收入）如何在决策树中处理？
决策树为什么容易过拟合？如何控制？
二、核心概念详解
2.1 决策树的基本结构
决策树是一个树形结构：
- 根节点：包含所有训练数据，对应最重要的特征测试
- 内部节点：对应一个特征测试
- 分支：特征测试的每个取值对应一个分支
- 叶节点：对应一个预测结果（类别或数值）
python
class TreeNode:
"""决策树节点"""
def __init__(self, feature=None, threshold=None, left=None, right=None, value=None):
self.feature = feature # 分裂特征索引
self.threshold = threshold # 分裂阈值
self.left = left # 左子树
self.right = right # 右子树
self.value = value # 叶节点值
class DecisionTreeClassifier:
"""决策树分类器（CART）"""
def __init__(self, max_depth=5, min_samples_split=2):
self.max_depth = max_depth
self.min_samples_split = min_samples_split
self.root = None
def fit(self, X, y):
self.root = self._build_tree(X, y, depth=0)
return self
def _build_tree(self, X, y, depth):
n_samples, n_features = X.shape
n_classes = len(np.unique(y))
# 停止条件
if (depth >= self.max_depth or
n_samples < self.min_samples_split or
n_classes == 1):
leaf_value = self._most_common_label(y)
return TreeNode(value=leaf_value)
# 选择最优特征
best_feature, best_threshold = self._best_split(X, y)
if best_feature is None:
return TreeNode(value=self._most_common_label(y))
# 分裂数据
left_mask = X[:, best_feature] <= best_threshold
right_mask = ~left_mask
if np.sum(left_mask) == 0 or np.sum(right_mask) == 0:
return TreeNode(value=self._most_common_label(y))
# 递归构建子树
left = self._build_tree(X[left_mask], y[left_mask], depth + 1)
right = self._build_tree(X[right_mask], y[right_mask], depth + 1)
return TreeNode(best_feature, best_threshold, left, right)
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
gini = (np.sum(left_mask) * self._gini(y[left_mask]) +
np.sum(right_mask) * self._gini(y[right_mask])) / len(y)
if gini < best_gini:
best_gini = gini
best_feature = feature
best_threshold = threshold
return best_feature, best_threshold
def _gini(self, y):
"""基尼指数"""
_, counts = np.unique(y, return_counts=True)
probs = counts / len(y)
return 1 - np.sum(probs ** 2)
def _most_common_label(self, y):
return np.bincount(y).argmax()
def predict(self, X):
return np.array([self._predict(x, self.root) for x in X])
def _predict(self, x, node):
if node.value is not None:
return node.value
if x[node.feature] <= node.threshold:
return self._predict(x, node.left)
return self._predict(x, node.right)2.2 特征选择准则
2.2.1 信息熵与信息增益（ID3）
信息熵（entropy）衡量数据集的纯度：
$$Ent(D) = -\sum_{k=1}^{n} p_k \log_2 p_k$$
信息增益 = 划分前的信息熵 - 划分后的条件信息熵：
$$Gain(D, a) = Ent(D) - \sum_{v=1}^{V} \frac{|D^v|}{|D|} Ent(D^v)$$
python
def entropy(y):
"""计算信息熵"""
_, counts = np.unique(y, return_counts=True)
probs = counts / len(y)
return -np.sum(probs * np.log2(probs + 1e-10))
def information_gain(y, y_left, y_right):
"""计算信息增益"""
n = len(y)
n_left, n_right = len(y_left), len(y_right)
gain = entropy(y) - (n_left / n * entropy(y_left) + n_right / n * entropy(y_right))
return gain
# 示例
y = np.array([1, 1, 1, 0, 0, 0, 0, 0])
print(f"数据集信息熵: {entropy(y):.4f}")
# 按某个特征划分
y_left = np.array([1, 1, 1, 0])
y_right = np.array([0, 0, 0, 0])
print(f"划分后信息熵: 左={entropy(y_left):.4f}, 右={entropy(y_right):.4f}")
print(f"信息增益: {information_gain(y, y_left, y_right):.4f}")ID3 的局限性：信息增益偏好取值较多的特征。例如，用"编号"特征划分，每个样本一个分支，信息增益最大，但毫无泛化能力。
2.2.2 增益率（C4.5）
增益率通过引入"固有值"来校正信息增益的偏好：
$$Gain\_ratio(D, a) = \frac{Gain(D, a)}{IV(a)}$$
其中 $IV(a) = -\sum_{v=1}^{V} \frac{|D^v|}{|D|} \log_2 \frac{|D^v|}{|D|}$
python
def intrinsic_value(y, y_left, y_right):
"""固有值"""
n = len(y)
n_left, n_right = len(y_left), len(y_right)
p_left = n_left / n
p_right = n_right / n
iv = 0
if p_left > 0:
iv -= p_left * np.log2(p_left)
if p_right > 0:
iv -= p_right * np.log2(p_right)
return iv
def gain_ratio(y, y_left, y_right):
"""增益率"""
gain = information_gain(y, y_left, y_right)
iv = intrinsic_value(y, y_left, y_right)
return gain / (iv + 1e-10)
print(f"增益率: {gain_ratio(y, y_left, y_right):.4f}")C4.5 的改进：增益率对取值较多的特征有惩罚。但 C4.5 也有一个缺点——它偏好取值较少的特征（与 ID3 相反），因此实际中采用启发式：先选信息增益高于平均的特征，再从中选增益率最高的。
2.2.3 基尼指数（CART）
基尼指数衡量从数据集中随机抽取两个样本，类别不一致的概率：
$$Gini(D) = 1 - \sum_{k=1}^{n} p_k^2$$
特征 a 的基尼指数：
$$Gini\_index(D, a) = \sum_{v=1}^{V} \frac{|D^v|}{|D|} Gini(D^v)$$
python
def gini_index(y):
"""基尼指数"""
_, counts = np.unique(y, return_counts=True)
probs = counts / len(y)
return 1 - np.sum(probs ** 2)
def gini_for_split(y, y_left, y_right):
"""划分后的基尼指数"""
n = len(y)
return (len(y_left) / n * gini_index(y_left) +
len(y_right) / n * gini_index(y_right))
print(f"基尼指数: {gini_index(y):.4f}")
print(f"划分后基尼指数: {gini_for_split(y, y_left, y_right):.4f}")CART 选择基尼指数的原因：
- 计算简单：不需要对数运算
- 与熵的效果类似，但计算更快
- CART 生成的是二叉树，每次只选一个特征的一个切分点
2.3 剪枝策略
2.3.1 为什么需要剪枝
不剪枝的决策树会尽可能生长，直到每个叶节点只包含同一类的样本。这会导致严重的过拟合——树过于复杂，对训练数据拟合得很好，但对新数据泛化能力差。
2.3.2 预剪枝
预剪枝在决策树生成过程中，对每个节点在分裂前先进行评估。如果当前分裂不能带来泛化性能的提升（通过验证集评估），则停止分裂，将该节点标记为叶节点。
python
def pre_pruning_demo():
"""预剪枝演示"""
np.random.seed(42)
# 生成数据
X = np.random.rand(100, 2)
y = (X[:, 0] + X[:, 1] > 1.0).astype(int)
# 添加噪声
flip = np.random.choice(100, 10, replace=False)
y[flip] = 1 - y[flip]
# 划分训练集和验证集
indices = np.random.permutation(100)
train_idx, val_idx = indices[:70], indices[70:]
# 不剪枝
tree_full = DecisionTreeClassifier(max_depth=100)
tree_full.fit(X[train_idx], y[train_idx])
train_acc = np.mean(tree_full.predict(X[train_idx]) == y[train_idx])
val_acc = np.mean(tree_full.predict(X[val_idx]) == y[val_idx])
# 预剪枝（限制深度）
tree_pruned = DecisionTreeClassifier(max_depth=3)
tree_pruned.fit(X[train_idx], y[train_idx])
train_acc_p = np.mean(tree_pruned.predict(X[train_idx]) == y[train_idx])
val_acc_p = np.mean(tree_pruned.predict(X[val_idx]) == y[val_idx])
print("=== 预剪枝效果 ===")
print(f"不剪枝: 训练准确率={train_acc:.2%}, 验证准确率={val_acc:.2%}")
print(f"预剪枝: 训练准确率={train_acc_p:.2%}, 验证准确率={val_acc_p:.2%}")
print("\n预剪枝降低了训练准确率，但可能提高验证准确率")
print("预剪枝的优点：减少训练时间，降低过拟合风险")
print("预剪枝的缺点：可能欠拟合（贪心本质）")
pre_pruning_demo()2.3.3 后剪枝
后剪枝先生成一棵完整的决策树，然后自底向上对每个内部节点进行评估。如果将该节点对应的子树替换为叶节点能带来泛化性能的提升，则进行替换。
python
def post_pruning_concept():
"""后剪枝概念说明"""
print("=== 后剪枝策略 ===")
print("1. 生成完整的决策树（不限制深度）")
print("2. 从最底层的内部节点开始，自底向上评估")
print("3. 对每个节点，比较保留子树 vs 替换为叶节点")
print("4. 使用验证集评估泛化性能")
print("5. 如果替换后泛化性能更好，则进行剪枝")
print()
print("后剪枝的优点：保留了更多有效分裂，欠拟合风险小")
print("后剪枝的缺点：训练完整树的开销大")
post_pruning_concept()2.4 连续值处理
2.4.1 二分法
对于连续特征 a，CART 采用二分法：将特征值排序，取相邻值的中点作为候选切分点。
python
def continuous_split_demo():
"""连续值处理演示"""
# 假设有一个连续特征"密度"
density = np.array([0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9])
labels = np.array([0, 0, 0, 1, 1, 1, 1, 1])
# 候选切分点：相邻值的中点
sorted_idx = np.argsort(density)
sorted_density = density[sorted_idx]
sorted_labels = labels[sorted_idx]
print("=== 连续值二分法 ===")
print(f"排序后的密度值: {sorted_density}")
print(f"对应标签: {sorted_labels}")
print()
best_gini = float('inf')
best_threshold = None
for i in range(len(sorted_density) - 1):
threshold = (sorted_density[i] + sorted_density[i+1]) / 2
left_mask = sorted_density <= threshold
right_mask = ~left_mask
y_left = sorted_labels[left_mask]
y_right = sorted_labels[right_mask]
gini = gini_for_split(sorted_labels, y_left, y_right)
print(f"切分点 {threshold:.2f}: 左={y_left.tolist()}, 右={y_right.tolist()}, "
f"基尼={gini:.4f}")
if gini < best_gini:
best_gini = gini
best_threshold = threshold
print(f"\n最优切分点: {best_threshold:.2f}, 基尼指数: {best_gini:.4f}")
continuous_split_demo()2.5 缺失值处理
当训练数据中存在缺失值时，决策树需要特殊处理：
特征选择时：仅使用无缺失值的样本计算信息增益，然后按比例推广
划分时：将带有缺失值的样本同时分配到所有子节点，按权重分配
python
def missing_value_handling():
"""缺失值处理概念"""
print("=== 缺失值处理 ===")
print("1. 特征选择时：")
print(" - 仅用无缺失值的样本计算信息增益")
print(" - 将信息增益乘以无缺失值样本的比例")
print()
print("2. 样本划分时：")
print(" - 有确定值的样本：按特征值分配到对应子节点")
print(" - 有缺失值的样本：同时分配到所有子节点")
print(" - 权重按各子节点的样本比例分配")
print()
print("示例：")
print("假设特征A有10个样本，其中2个缺失")
print("无缺失的8个样本中，5个去左子树，3个去右子树")
print("缺失的2个样本：5/8的权重去左子树，3/8的权重去右子树")
missing_value_handling()三、实战案例
3.1 案例一：西瓜数据集上的决策树
python
def watermelon_decision_tree():
"""在西瓜数据集上构建决策树"""
# 西瓜数据集
X = np.array([
[0, 0, 0], # 青绿, 蜷缩, 浊响
[1, 0, 0], # 乌黑, 蜷缩, 浊响
[1, 0, 1], # 乌黑, 蜷缩, 沉闷
[0, 0, 0], # 青绿, 蜷缩, 浊响
[1, 1, 0], # 乌黑, 稍蜷, 浊响
[0, 2, 0], # 青绿, 硬挺, 浊响
[1, 0, 0], # 乌黑, 蜷缩, 浊响
[0, 1, 1], # 青绿, 稍蜷, 沉闷
[1, 1, 0], # 乌黑, 稍蜷, 浊响
[0, 0, 0], # 青绿, 蜷缩, 浊响
])
y = np.array([1, 1, 0, 1, 1, 0, 1, 0, 1, 1]) # 1=好瓜, 0=坏瓜
# 训练决策树
tree = DecisionTreeClassifier(max_depth=3)
tree.fit(X, y)
# 预测
y_pred = tree.predict(X)
accuracy = np.mean(y_pred == y)
print("=== 西瓜决策树 ===")
print(f"训练准确率: {accuracy:.2%}")
print(f"\n决策规则：")
print("如果 根蒂=蜷缩:")
print(" 如果 敲声=浊响 → 好瓜")
print(" 如果 敲声=沉闷 → 坏瓜")
print("如果 根蒂≠蜷缩:")
print(" 如果 色泽=乌黑 → 好瓜")
print(" 如果 色泽=青绿 → 坏瓜")
watermelon_decision_tree()3.2 案例二：三种特征选择准则对比
python
def compare_split_criteria():
"""对比三种特征选择准则"""
np.random.seed(42)
# 生成数据
n = 200
X = np.random.rand(n, 4)
y = (X[:, 0] > 0.5).astype(int)
# 划分
indices = np.random.permutation(n)
train_idx, test_idx = indices[:150], indices[150:]
X_train, X_test = X[train_idx], X[test_idx]
y_train, y_test = y[train_idx], y[test_idx]
# 使用不同准则的决策树
results = {}
for max_depth in [1, 2, 3, 5, 10]:
tree = DecisionTreeClassifier(max_depth=max_depth)
tree.fit(X_train, y_train)
train_acc = np.mean(tree.predict(X_train) == y_train)
test_acc = np.mean(tree.predict(X_test) == y_test)
results[max_depth] = (train_acc, test_acc)
print("=== 不同深度的决策树 ===")
print(f"{'深度':<8} {'训练准确率':<12} {'测试准确率':<12}")
print("-" * 35)
for depth, (train, test) in results.items():
print(f"{depth:<8} {train:<12.2%} {test:<12.2%}")
print("\n观察：")
print("- 深度增加 → 训练准确率单调递增")
print("- 测试准确率先增后降（过拟合）")
print("- 最优深度在测试准确率最高处")
compare_split_criteria()3.3 案例三：决策树可视化
python
def visualize_decision_tree():
"""决策树规则提取与可视化"""
np.random.seed(42)
# 简单数据集
X = np.array([
[1, 1], [1, 0], [0, 1], [0, 0],
[2, 2], [2, 1], [1, 2], [0, 2],
])
y = np.array([1, 0, 0, 0, 1, 1, 1, 0])
tree = DecisionTreeClassifier(max_depth=2)
tree.fit(X, y)
def print_tree(node, depth=0, prefix=""):
indent = " " * depth
if node.value is not None:
label = "好瓜" if node.value == 1 else "坏瓜"
print(f"{indent}{prefix}→ {label}")
else:
print(f"{indent}{prefix}特征{node.feature} <= {node.threshold:.1f}?")
print_tree(node.left, depth + 1, "是: ")
print_tree(node.right, depth + 1, "否: ")
print("=== 决策树结构 ===")
print_tree(tree.root)
visualize_decision_tree()四、本章小结
第4章系统介绍了决策树的核心内容：
基本结构：决策树通过递归的特征测试将数据划分，形成树形的"if-then"规则。
特征选择准则：
- ID3：信息增益，偏好取值多的特征
- C4.5：增益率，校正信息增益的偏好
- CART：基尼指数，计算简单，生成二叉树
剪枝策略：预剪枝（边生成边评估）和后剪枝（先生成后剪枝），各有优缺点。
连续值处理：二分法，取相邻值的中点作为候选切分点。
缺失值处理：按权重分配样本到各子节点。
决策树的优势在于可解释性强、不需要特征缩放、能处理混合类型特征。缺点是容易过拟合、对数据变化敏感。在实际应用中，决策树更多作为集成学习的基学习器使用。
五、思考与练习
思考题
信息增益为什么偏好取值较多的特征？请举一个具体的例子说明。
预剪枝和后剪枝哪个更容易欠拟合？为什么？
决策树能否处理多分类问题？如何处理？
决策树对特征的尺度（scale）敏感吗？为什么？
为什么决策树不需要特征标准化？
编程练习
实现 ID3 算法（使用信息增益作为特征选择准则），与 CART 进行比较。
实现后剪枝算法：先生成完整决策树，然后用验证集自底向上评估是否需要剪枝。
在不同噪声水平的数据上，比较剪枝与不剪枝的决策树的泛化性能。