决策树

概述

决策树是一种基于树状结构的机器学习算法，用于分类和回归任务。它通过对特征空间进行递归的二分（或多分）来构建一个树结构，每个内部节点代表一个特征，每个叶节点代表一个类别（对于分类问题）或一个数值（对于回归问题）。决策树的每个节点表示一个问题，其答案将决定进一步向哪个分支移动。

模型结构
- 根部节点(root node)
- 中间节点(non-leaf node)：代表测试的条件
- 分支(branches)：代表测试的结果
- 叶节点(leaf node)：代表分类或预测值
分枝准则
- **信息增益（Information Gain）**根据熵的减少来衡量特征对分类的贡献。它计算当前节点的熵减去使用特征进行划分后子节点的熵的加权和。信息增益越大，表示使用该特征进行划分能够获得更多的信息，对分类更有益。
- **增益率（Gain Ratio）**结合了信息增益和特征分支度量之间的关系，避免了信息增益偏向于具有较多分支的特征。增益率通过信息增益除以分支度量来得到，可以更好地处理具有多个分支的特征。
- **基尼不纯度（Gini Impurity）**在节点上随机选择两个样本，它们不是同一类别的概率。基尼不纯度可以看作是在节点上错误分类的概率。选择特征时，选取能够降低基尼不纯度的特征。
- **均方误差（Mean Squared Error）**用于回归问题，它衡量了每个节点上的平方误差的和。选择特征时，选择使均方误差最小的特征。
剪枝
- 预修剪（Pre-Pruning）
- 后修剪 (Post-Pruning)

ID3 算法

**ID3（Iterative Dichotomiser 3）**是一种用于构建决策树的经典算法，它是由Ross Quinlan于1986年提出的。ID3算法通过递归地选择信息增益最大的特征来构建决策树。它适用于分类问题，将样本分到不同的类别中。

信息增益衡量了使用某个特征进行分割后数据集熵的减少。它可以通过计算父节点熵与子节点加权熵之差得到。

父节点熵： $$ H(D) = - \sum\frac{count(C_i)}{count(D)} \times \log\frac{count(C_i)}{count(D)} $$ 子节点加权熵： $$ H(D|A) = \sum \frac{count(D_v)}{count(D)} \times H(D_v) $$ 信息增益： $$ IG(D, A) = H(D) - H(D|A) $$

C4.5算法

C4.5是一种决策树算法，由Ross Quinlan在1993年提出，它是ID3算法的扩展和改进。C4.5算法在构建决策树时引入了剪枝技术，能够处理缺失值，同时支持数值型特征，并可以处理多类别分类问题。

增益率结合了信息增益和特征分支度量之间的关系，避免了信息增益偏向于具有较多分支的特征。 $$ GainRatio(D, A) = IG(D, A) / IV(A) $$ 分裂信息（Split Information）： $$ IV(A) = - \sum \frac{count(D_v)}{count(D)}\times\log\frac{count(D_v)}{count(D)} $$

CART 算法

**CART（Classification and Regression Trees）**是一种经典的决策树算法，它既可以用于分类问题，也可以用于回归问题。CART 算法由Breiman等人在1984年提出，其主要特点是使用基尼不纯度作为 criterion 来进行特征选择和分割。 $$ Gini(D) = 1 - \sum {\Large(}\frac{count(C_i)}{count(D)}{\Large)}^2 $$

from sklearn.datasets import load_iris, load_boston
from sklearn.tree import DecisionTreeClassifier, DecisionTreeRegressor
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score, mean_squared_error

# 示例：CART 决策树分类器
iris = load_iris()
X = iris.data
y = iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

tree_classifier = DecisionTreeClassifier(criterion='gini')
tree_classifier.fit(X_train, y_train)
y_pred = tree_classifier.predict(X_test)
accuracy = accuracy_score(y_test, y_pred)
print("Accuracy:", accuracy)

# 示例：CART 决策树回归器
boston = load_boston()
X = boston.data
y = boston.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

tree_regressor = DecisionTreeRegressor(criterion='mse')
tree_regressor.fit(X_train, y_train)
y_pred = tree_regressor.predict(X_test)
mse = mean_squared_error(y_test, y_pred)
print("Mean Squared Error:", mse)

剪枝

决策树的剪枝是为了防止过拟合，通过修剪决策树的一些分支来提高模型的泛化能力。剪枝可以通过去掉一些子树或合并一些叶节点来实现，从而减小树的复杂度，使其更能适应未见过的数据。

预剪枝（Pre-pruning）

预剪枝是在构建决策树时，在决策树生长的过程中，根据一些预定义的条件来限制决策树的生长。这些条件可以是最大深度、叶节点最小样本数、叶节点最小样本数比例等。预剪枝的目标是在决策树生长过程中就防止过拟合，从而生成一个较简单的模型。

DecisionTreeClassifier和DecisionTreeRegressor类提供了max_depth参数来控制树的最大深度，提供了min_samples_split、min_samples_leaf等参数来设置叶节点的最小样本数，以进行预剪枝。

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 = iris.data
y = iris.target

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

# 创建决策树分类器（使用预剪枝）
tree_classifier_preprune = DecisionTreeClassifier(max_depth=3)
tree_classifier_preprune.fit(X_train, y_train)

# 预测
y_pred = tree_classifier_preprune.predict(X_test)

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

后剪枝（Post-pruning）

后剪枝是在决策树构建完成后，通过自底向上地对决策树的节点进行检查和修剪。在后剪枝中，每个内部节点都会被检查，如果去掉该节点的子树并用一个叶节点替代可以提高泛化性能，则进行剪枝。后剪枝的目标是通过去除一些不必要的分支来提高模型的泛化能力。

DecisionTreeClassifier 和 DecisionTreeRegressor 类提供了 ccp_alpha 参数来控制后剪枝程度。

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 = iris.data
y = iris.target

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

# 创建决策树分类器
tree_classifier = DecisionTreeClassifier()

# 拟合模型
tree_classifier.fit(X_train, y_train)

# 预测
y_pred = tree_classifier.predict(X_test)

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

# 后剪枝（通过调整 ccp_alpha 参数）
path = tree_classifier.cost_complexity_pruning_path(X_train, y_train)
ccp_alphas = path.ccp_alphas
for alpha in ccp_alphas:
    pruned_tree = DecisionTreeClassifier(ccp_alpha=alpha)
    pruned_tree.fit(X_train, y_train)
    y_pred_pruned = pruned_tree.predict(X_test)
    accuracy_pruned = accuracy_score(y_test, y_pred_pruned)
    print("Alpha:", alpha, "Accuracy (After Pruning):", accuracy_pruned)