机器学习回顾——决策树详解

决策树基础概念与应用详解

1. 决策树基础概念

1.1 什么是决策树

决策树是一种树形结构的预测模型，其核心思想是通过一系列规则对数据进行递归划分。它模拟人类决策过程，广泛应用于分类和回归任务。具体结构包括：

• 内部节点：表示对某个特征的条件判断，例如"年龄>30岁？"或"收入<5万？"
• 分支：代表判断结果的可能取值，如"是/否"或离散特征的各个类别
• 叶节点：包含最终的预测结果。在分类任务中可能输出"批准贷款"或"拒绝贷款"；在回归任务中可能输出具体数值如"房价=45.6万"

1.2 决策树的主要组成部分

1. 根节点：位于树的最顶端，包含完整的训练数据集。例如在客户信用评估中，根节点可能包含所有申请人的特征数据
2. 决策节点：进行条件判断的内部节点，通常会选择最具区分度的特征进行判断。如选择"信用评分"而非"性别"作为关键判断标准
3. 叶节点：终止节点，存储最终决策结果。在医疗诊断中，可能输出"良性"或"恶性"的诊断结论
4. 分支：连接节点的路径，表示决策条件的具体取值。例如"体温>38.5℃"的分支可能导向"疑似感染"的子节点

1.3 决策树的工作流程

决策树的构建遵循以下详细步骤：

1. 特征选择：在当前节点计算所有特征的分裂质量（使用信息增益、基尼指数等指标），选择最优特征
2. 数据分割：根据选定特征的取值将数据集划分为若干子集。例如将"收入"特征按阈值50k划分为高/低收入两组
3. 递归构建：对每个子节点重复步骤1-2，直到满足以下任一停止条件：
   • 节点样本数小于预设阈值（如min_samples_leaf=5）
   • 所有样本属于同一类别（纯度达到100%）
   • 树达到最大深度限制（如max_depth=10）
   • 继续分裂不能显著改善模型性能
4. 剪枝处理：为防止过拟合，可能进行预剪枝或后剪枝操作

2. 决策树构建算法

2.1 ID3算法

核心思想：通过最大化信息增益来选择特征分裂点，倾向于选择能够最有效降低不确定性的特征。

信息熵计算： H(S) = -∑ p_i log₂ p_i 其中p_i是第i类样本在集合S中的比例。例如对于一个二分类问题（正例60%，负例40%）： H(S) = -0.6log₂0.6 - 0.4log₂0.4 ≈ 0.971

信息增益计算： Gain(S, A) = H(S) - ∑ (|S_v|/|S|) * H(S_v) 其中S_v是特征A取值为v的子集。例如，对于包含100个样本的节点，按特征A分为两个子集（60个和40个），分别计算其熵值后加权平均。

实际应用中的局限性：

1. 偏向于选择取值较多的特征（如"用户ID"这种唯一标识符）
2. 无法直接处理连续型特征，需要预先离散化
3. 对缺失值敏感，缺乏有效的处理机制
4. 没有剪枝步骤，容易生成过深的树导致过拟合

2.2 C4.5算法

核心改进：

1. 信息增益率：解决ID3对多值特征的偏好问题 GainRatio(S, A) = Gain(S, A) / SplitInfo(S, A) 其中SplitInfo(S, A) = -∑ (|S_v|/|S|) * log₂(|S_v|/|S|) 这相当于对信息增益进行标准化处理

2. 连续特征处理：采用二分法自动离散化连续特征

   • 对特征值排序后，取相邻值的中点作为候选分割点
   • 选择信息增益率最大的分割点

3. 缺失值处理：

   • 在计算信息增益时，仅使用特征A不缺失的样本
   • 预测时，如果遇到缺失值，可以按照分支样本比例分配

4. 剪枝策略：

   • 采用悲观剪枝(PEP)方法
   • 基于统计显著性检验决定是否剪枝

2.3 CART算法

算法特点：

1. 二叉树结构：每个节点只产生两个分支，简化决策过程

   • 对于离散特征：生成"是否属于某类别"的判断
   • 对于连续特征：生成"是否≤阈值"的判断

2. 基尼指数（用于分类）： Gini(S) = 1 - ∑ p_i² 基尼指数表示从数据集中随机抽取两个样本，其类别不一致的概率。值越小表示纯度越高。

3. 回归树实现：

   • 分裂标准：最小化平方误差 MSE = 1/n ∑ (y_i - ŷ)²
   • 叶节点输出：该节点所有样本的目标变量均值
   • 特征选择：选择使MSE降低最多的特征和分割点

3. 决策树的关键技术

3.1 特征选择标准

分类任务：

1. 信息增益（ID3）：

   • 优点：理论基础强，符合信息论原理
   • 缺点：对多值特征有偏好

2. 信息增益率（C4.5）：

   • 优点：解决了多值特征偏好问题
   • 缺点：可能过度补偿，倾向于选择分裂信息小的特征

3. 基尼指数（CART）：

   • 优点：计算简单，不涉及对数运算
   • 缺点：没有信息增益的理论基础

回归任务：

1. 方差减少：选择使子节点目标变量方差和最小的分裂
2. 最小二乘偏差：直接优化预测误差的平方和

3.2 剪枝技术

预剪枝（提前停止树的生长）：

1. 最大深度限制（max_depth）：控制树的层数
2. 最小样本分裂数（min_samples_split）：节点样本数少于该值则不再分裂
3. 最小叶节点样本数（min_samples_leaf）：确保叶节点有足够样本支撑
4. 最大特征数（max_features）：限制每次分裂考虑的特征数量

后剪枝（先构建完整树再修剪）：

1. 代价复杂度剪枝（CCP）：

   • 计算各节点的α值：α = (R(t)-R(T_t))/(|T_t|-1)
   • 剪去使整体代价函数Cα(T)=R(T)+α|T|最小的子树
   • 通过交叉验证选择最优α

2. 悲观错误剪枝（PEP）：

   • 基于统计检验，认为训练误差是乐观估计
   • 使用二项分布计算误差上限，决定是否剪枝

3.3 连续值和缺失值处理

连续值处理流程：

1. 对特征值排序（如年龄：22,25,28,30,36,...）
2. 取相邻值中点作为候选分割点（如(22+25)/2=23.5）
3. 计算每个候选点的分裂质量指标
4. 选择最佳分割点构建决策节点

缺失值处理策略：

1. 替代法：

   • 分类：用众数填充
   • 回归：用均值填充
   • 优点：实现简单
   • 缺点：可能引入偏差

2. 概率分配：

   • 根据特征值分布概率将样本分配到各分支
   • 保持样本权重不变
   • 更合理但实现复杂

3. 特殊分支：

   • 为缺失值创建专用分支路径
   • 需要足够多的缺失样本支持

4. 决策树的优缺点

4.1 优势分析

1. 模型可解释性：

   • 决策路径可以直观展示，适合需要解释预测结果的场景
   • 例如在信贷审批中，可以明确告知客户"因收入不足被拒"

2. 数据处理优势：

   • 不需要特征缩放（如标准化）
   • 能同时处理数值型（年龄、收入）和类别型（性别、职业）特征
   • 自动进行特征选择（忽略无关特征）

3. 计算效率：

   • 预测时间复杂度为O(树深度)，通常非常高效
   • 适合实时预测场景，如欺诈检测

4. 多功能性：

   • 可处理多输出问题（同时预测多个目标变量）
   • 适用于分类和回归任务

5. 可视化能力：

   • 可通过图形展示决策流程
   • 便于向非技术人员解释模型逻辑

4.2 局限性

1. 过拟合风险：

   • 可能生成过于复杂的树，捕捉数据中的噪声
   • 需要通过剪枝、设置最小叶节点样本数等约束控制

2. 模型不稳定性：

   • 训练数据的微小变化可能导致完全不同的树结构
   • 可通过集成方法（如随机森林）缓解

3. 局部最优问题：

   • 贪心算法无法保证全局最优
   • 可能错过更好的特征组合分裂方式

4. 连续变量处理：

   • 需要将连续特征离散化
   • 可能丢失连续特征的精细信息

5. 忽略特征相关性：

   • 独立考虑每个特征的分裂效果
   • 无法捕捉特征间的交互作用

5. 决策树的实际应用

5.1 分类任务实现（乳腺癌诊断）

from sklearn.datasets import load_breast_cancer
from sklearn.tree import DecisionTreeClassifier, export_graphviz
from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn.metrics import accuracy_score, classification_report, confusion_matrix
import matplotlib.pyplot as plt

# 加载威斯康星乳腺癌数据集
data = load_breast_cancer()
X = data.data  # 包含30个特征（半径、纹理等）
y = data.target  # 0=恶性，1=良性
feature_names = data.feature_names

# 划分训练测试集（70%训练，30%测试）
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.3, random_state=42, stratify=y)

# 设置参数网格进行调优
param_grid = {
    'criterion': ['gini', 'entropy'],
    'max_depth': [3, 5, 7, None],
    'min_samples_split': [2, 5, 10],
    'min_samples_leaf': [1, 2, 5]
}

# 创建决策树分类器
clf = DecisionTreeClassifier(random_state=42)

# 使用网格搜索寻找最优参数
grid_search = GridSearchCV(clf, param_grid, cv=5, scoring='accuracy')
grid_search.fit(X_train, y_train)

# 最佳参数模型
best_clf = grid_search.best_estimator_
print(f"最佳参数：{grid_search.best_params_}")

# 在测试集上评估
y_pred = best_clf.predict(X_test)
print(f"测试集准确率：{accuracy_score(y_test, y_pred):.4f}")
print(classification_report(y_test, y_pred))

# 可视化混淆矩阵
cm = confusion_matrix(y_test, y_pred)
plt.figure(figsize=(6,6))
plt.imshow(cm, interpolation='nearest', cmap=plt.cm.Blues)
plt.title("Confusion Matrix")
plt.colorbar()
plt.xticks([0,1], ["Malignant", "Benign"])
plt.yticks([0,1], ["Malignant", "Benign"])
plt.xlabel("Predicted")
plt.ylabel("Actual")
for i in range(2):
    for j in range(2):
        plt.text(j, i, str(cm[i,j]), ha="center", va="center", color="white" if cm[i,j] > cm.max()/2 else "black")
plt.show()

# 导出决策树图形（需要graphviz）
export_graphviz(best_clf, out_file="breast_cancer_tree.dot",
                feature_names=feature_names,
                class_names=data.target_names,
                filled=True, rounded=True)

5.2 回归任务实现（房价预测）

from sklearn.datasets import fetch_california_housing
from sklearn.tree import DecisionTreeRegressor
from sklearn.model_selection import train_test_split, RandomizedSearchCV
from sklearn.metrics import mean_squared_error, r2_score, mean_absolute_error
import numpy as np
import pandas as pd

# 加载加州房价数据集
housing = fetch_california_housing()
X = housing.data  # 8个特征（经度、纬度、房龄等）
y = housing.target  # 房价中位数（单位：10万美元）
feature_names = housing.feature_names

# 转换为DataFrame便于分析
df = pd.DataFrame(X, columns=feature_names)
df['MedHouseVal'] = y

# 划分训练测试集
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.3, random_state=42)

# 设置参数分布进行随机搜索
param_dist = {
    'criterion': ['mse', 'friedman_mse', 'mae'],
    'max_depth': np.arange(3, 15),
    'min_samples_split': np.arange(2, 20),
    'min_samples_leaf': np.arange(1, 15),
    'max_features': ['auto', 'sqrt', 'log2', None]
}

# 创建决策树回归器
reg = DecisionTreeRegressor(random_state=42)

# 随机参数搜索
random_search = RandomizedSearchCV(reg, param_dist, n_iter=100, cv=5,
                                 scoring='neg_mean_squared_error',
                                 random_state=42)
random_search.fit(X_train, y_train)

# 最佳参数模型
best_reg = random_search.best_estimator_
print(f"最佳参数：{random_search.best_params_}")

# 在测试集上评估
y_pred = best_reg.predict(X_test)
print(f"测试集MSE：{mean_squared_error(y_test, y_pred):.4f}")
print(f"测试集MAE：{mean_absolute_error(y_test, y_pred):.4f}")
print(f"测试集R²：{r2_score(y_test, y_pred):.4f}")

# 特征重要性分析
importance = pd.DataFrame({
    'feature': feature_names,
    'importance': best_reg.feature_importances_
}).sort_values('importance', ascending=False)

# 绘制特征重要性
plt.figure(figsize=(10,6))
plt.barh(importance['feature'], importance['importance'])
plt.xlabel("Feature Importance")
plt.title("Decision Tree Feature Importance")
plt.gca().invert_yaxis()
plt.show()