决策树
概述
决策树是一种基于树状结构的机器学习算法,用于分类和回归任务。它通过对特征空间进行递归的二分(或多分)来构建一个树结构,每个内部节点代表一个特征,每个叶节点代表一个类别(对于分类问题)或一个数值(对于回归问题)。决策树的每个节点表示一个问题,其答案将决定进一步向哪个分支移动。
- 模型结构
-
根部节点(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)