机器学习——决策树剪枝算法

决策树是一种常用的机器学习模型，它能够根据数据特征的不同进行分类或回归。在决策树的构建过程中，剪枝算法是为了防止过拟合，提高模型的泛化能力而提出的重要技术。本篇博客将介绍剪枝处理的概念、预剪枝和后剪枝方法，以及决策树的损失函数（目标函数），并使用Python实现以上所有的算法。

1. 剪枝处理

在决策树的构建过程中，为了防止过拟合，通常会对生成的决策树进行剪枝处理。剪枝的目的是通过降低树的复杂度来提高模型的泛化能力。

2. 预剪枝与后剪枝

预剪枝是在决策树生成过程中，在决策树生长的过程中，根据一定的条件提前终止分支的生成。常用的预剪枝条件包括限制树的最大深度、叶节点最小样本数等。

后剪枝是在决策树生成完成后，通过一定的方法对决策树进行剪枝。后剪枝的思想是先生成一颗完全生长的决策树，然后根据损失函数（目标函数）对节点进行逐个判断，判断删除某一节点后是否能提高模型的泛化能力，如果能，则删除该节点。

3. 决策树的损失函数

决策树的损失函数（目标函数）是在剪枝过程中判断节点是否应该被剪枝的依据。通常使用的损失函数包括基于误分类率、基尼指数和交叉熵等。

3.1 基于误分类率的损失函数：

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

其中， $C (T)$ 是模型对训练数据的误分类率， $∣ T ∣$ 是决策树的叶节点个数， $\alpha$ 是调节参数。

3.2 基于基尼指数的损失函数：

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

其中， $C (T)$ 是模型的基尼指数， $∣ T ∣$ 是决策树的叶节点个数， $\alpha$ 是调节参数。

3.3 基于交叉熵的损失函数：

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

其中， $C (T)$ 是模型的交叉熵， $∣ T ∣$ 是决策树的叶节点个数， $\alpha$ 是调节参数。

4. Python实现

接下来，将使用Python实现预剪枝和后剪枝两种剪枝算法，并在相同的数据集上进行比较。

4.1 预剪枝算法

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

# 加载数据集
iris = load_iris()
X, y = iris.data, iris.target

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

# 构建决策树模型（预剪枝）
clf = DecisionTreeClassifier(criterion='entropy', max_depth=3, min_samples_split=5, min_samples_leaf=2, random_state=42)
clf.fit(X_train, y_train)

# 在测试集上进行预测
y_pred = clf.predict(X_test)

# 计算准确率
accuracy = accuracy_score(y_test, y_pred)
print("Pre-pruning Accuracy:", accuracy)

4.2 后剪枝算法

from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

# 加载数据集
iris = load_iris()
X, y = iris.data, iris.target

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

# 构建决策树模型（后剪枝）
clf = DecisionTreeClassifier(criterion='entropy', random_state=42)
clf.fit(X_train, y_train)

# 在测试集上进行预测
y_pred = clf.predict(X_test)

# 计算准确率
accuracy = accuracy_score(y_test, y_pred)
print("Before Pruning Accuracy:", accuracy)

# 后剪枝
path = clf.cost_complexity_pruning_path(X_train, y_train)
ccp_alphas, impurities = path.ccp_alphas, path.impurities

clfs = []
for ccp_alpha in ccp_alphas:
    clf = DecisionTreeClassifier(criterion='entropy', random_state=42, ccp_alpha=ccp_alpha)
    clf.fit(X_train, y_train)
    clfs.append(clf)

train_scores = [clf.score(X_train, y_train) for clf in clfs]
test_scores = [clf.score(X_test, y_test) for clf in clfs]

best_clf = clfs[test_scores.index(max(test_scores))]
y_pred = best_clf.predict(X_test)
accuracy = accuracy_score(y_test, y_pred)
print("After Pruning Accuracy:", accuracy)

示例

import matplotlib.pyplot as plt
import numpy as np
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score

# 加载数据集
iris = load_iris()
X, y = iris.data, iris.target

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

# 构建决策树模型（后剪枝）
clf = DecisionTreeClassifier(criterion='entropy', random_state=42)
clf.fit(X_train, y_train)

# 在测试集上进行预测
y_pred = clf.predict(X_test)

# 计算准确率
accuracy = accuracy_score(y_test, y_pred)
print("Before Pruning Accuracy:", accuracy)

# 后剪枝
path = clf.cost_complexity_pruning_path(X_train, y_train)
ccp_alphas, impurities = path.ccp_alphas, path.impurities

clfs = []
for ccp_alpha in ccp_alphas:
    clf = DecisionTreeClassifier(criterion='entropy', random_state=42, ccp_alpha=ccp_alpha)
    clf.fit(X_train, y_train)
    clfs.append(clf)

train_scores = [clf.score(X_train, y_train) for clf in clfs]
test_scores = [clf.score(X_test, y_test) for clf in clfs]

best_clf = clfs[test_scores.index(max(test_scores))]
y_pred = best_clf.predict(X_test)
accuracy = accuracy_score(y_test, y_pred)
print("After Pruning Accuracy:", accuracy)

# 绘制准确率随着剪枝参数的变化曲线
plt.figure(figsize=(10, 6))
plt.plot(ccp_alphas, train_scores, marker='o', label='Train', drawstyle="steps-post")
plt.plot(ccp_alphas, test_scores, marker='o', label='Test', drawstyle="steps-post")
plt.xlabel("CCP Alpha")
plt.ylabel("Accuracy")
plt.title("Accuracy vs. CCP Alpha for Decision Tree Pruning")
plt.legend()
plt.show()