为什么我的决策树创建的拆分实际上并未划分样本？

Question

这是我对著名Iris数据集进行二特征分类的基本代码：

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier, export_graphviz
from graphviz import Source

iris = load_iris()
iris_limited = iris.data[:, [2, 3]] # This gets only petal length & width.

# I'm using the max depth as a way to avoid overfitting
# and simplify the tree since I'm using it for educational purposes
clf = DecisionTreeClassifier(criterion="gini",
                             max_depth=3,
                             random_state=42)

clf.fit(iris_limited, iris.target)

visualization_raw = export_graphviz(clf, 
                                    out_file=None,
                                    special_characters=True,
                                    feature_names=["length", "width"],
                                    class_names=iris.target_names,
                                    node_ids=True)

visualization_source = Source(visualization_raw)
visualization_png_bytes = visualization_source.pipe(format='png')
with open('my_file.png', 'wb') as f:
    f.write(visualization_png_bytes)

当我检查我的树的可视化时，我发现了这个：

乍一看，这是一棵相当普通的树，但我注意到它有些奇怪。节点 #6 总共有 46 个样本，其中只有一个是杂色的，因此该节点被标记为 virginica。这似乎是一个相当合理的停下来的地方。但是，出于某种我无法理解的原因，该算法决定进一步拆分为节点 #7 和 #8。但奇怪的是，仍然在那里的 1 versicolor 仍然被错误分类，因为两个节点最终都具有 virginica 类。为什么要这样做？它是否盲目地只关注基尼系数的减少而不考虑它是否有任何影响 - 这对我来说似乎是奇怪的行为，而且我找不到任何地方的记录。

是否可以禁用，或者这实际上是正确的？

Answer 1

为什么要这样做？

因为它提供了有关样本类别的更多信息。您是对的，这种拆分不会改变任何预测的结果，但模型现在更加确定了。考虑节点 #8 中的样本：在拆分之前，模型有 98% 的置信度认为这些样本是维吉尼亚。然而，在拆分后，模型说这些样本肯定是维吉尼亚。

是不是一味地只看基尼系数下降，根本不看有没有区别？

默认情况下，DecisionTree 会继续分裂，直到所有叶节点都是纯的。有一些参数会影响拆分行为。然而，它没有明确考虑拆分节点是否会在预测标签方面产生影响。

是否可以禁用，或者这实际上是正确的？

如果拆分产生两个具有相同标签的叶节点，我认为没有办法强制 DecisionTreeClassifier 不拆分。但是，通过仔细设置min_samples_leaf和/或min_impurity_decrease参数，您可以实现类似的目标。

Answer 2

来自决策树文档：

scikit-learn 使用 CART 算法的优化版本

Breiman 等人描述了 CART 算法。在同名的书中，那就是Classification and Regression Trees。在 CART 中，作者描述了他们如何在生长决策树时尝试多种提前停止的标准。最终，他们发现了现在所谓的最小成本复杂性修剪（MCCP）：不是使用临时停止标准，而是生长一棵大树，然后将其修剪回来，使用交叉验证来比较算法考虑的各种子树。MCCP 在 CART 第 3 章中进行了详细描述，决策树文档中提供了简要总结。

现在我们知道了sklearn.DecisionTreeClassifierCART 算法的实现，我们知道了很多事情。其一，使用默认设置，除非max_depth提供参数，否则树将完全展开。更准确地说，正如文档中提到的DecisionTreeClassifier.max_depth：

最大深度：int，默认=无

树的最大深度。如果没有，则扩展节点，直到所有叶子都是纯的或直到所有叶子包含少于 min_samples_split 样本。

这回答了您的第一个问题，即为什么节点 #6 被拆分：节点 #6 不是纯节点，如基尼指数函数所定义的，因此它被拆分为节点 #8（纯节点）和节点 #7。按照这个逻辑，你的下一个问题似乎很合理：

但奇怪的是，仍然存在的 1 个 versicolor 仍然被错误分类，因为无论如何两个节点最终都具有 virginica 类。它为什么要这样做？

也就是说，为什么7号节点没有扩容呢？一个关键细节是您的树的深度为 3 只是因为您传递max_depth=3给了构造函数。换句话说，您明确限制DecisionTreeClassifier了扩展节点#7。如果删除约束，您将从代码中获得以下树：

乍一看，我以为这样就可以解决问题了。事实上，T' 中几乎每个节点都是纯节点，除了节点 #7（现在标记为节点 #13）！最近，我必须从头开始实现决策树和随机森林，因此我对正在发生的事情有一个直觉。我的假设是，虽然节点 #13 中的样本具有不同的标签，但它们实际上具有相同的特征。事实证明这是正确的：

>>> X = iris_limited 
>>> node13 = X[(X[:, 0] > 2.45) & (X[:, 1] > 1.75) & (X[:, 0] <= 4.85)]
>>> node13
array([[4.8, 1.8],
       [4.8, 1.8],
       [4.8, 1.8]])

当您对数据执行变量选择时，这种行为并不例外：在本例中，您定义为排除萼片长度和萼片宽度变量iris_limited的数据子集。iris的客户端DecisionTree（例如RandomForest对象）可以通过指定max_features参数来明确请求变量选择：在这种情况下，将DecisionTree在每次分割时选择变量的随机子集，这实际上将解相关多个树 T0, T1, ..., Tk从相同的数据集构建的。

需要注意的是，默认情况下，sklearn.DecisionTreeClassifier不执行MCC 剪枝。要启用此功能（如果您正在种植一棵树，而不是森林或整体，您绝对应该这样做）将超参数设置ccp_alpha为某个实数，您可以使用交叉验证来选择该实数。在对 Loh 和 Vanichsetakul 所著的《通过广义判别分析进行树结构分类》一文的（批评）回应中 ，Breiman 和 Friedman 对 MCC 剪枝的功效做出了以下声明：

本文中介绍的过程 (FACT) 比 CART 提高速度的两种方法是使用临时的自上而下停止规则，以及不实施代理分割。自上而下的停止规则被用于 CART 的所有早期前身（AID、THAID 等）。他们在这一点上受到了严厉的批评（有充分的理由），这也是统计界不接受他们的主要原因。CART 中实现的最优复杂度树修剪算法（基于交叉验证选择）可能是 Breiman 等人最重要的贡献。(1984)树结构方法的演变。它往往能够可靠地生产出大小合适的树木。

在 CART 的研究过程中，我们花了近 两年时间尝试不同的停止规则。每个停止规则都在数百个具有不同结构的模拟数据集上进行了测试。每个新的停止规则在某些数据集上都失败了。直到构建了一棵非常大的树，然后使用交叉验证来控制修剪程度进行修剪，我们才获得了一致工作的东西。

让我们将 MCCP 应用于您的树。sklearn.model_selection提供广泛的交叉验证设施。我们将使用一些基本工具来对 alpha 进行合理的选择：

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier, export_graphviz
from sklearn.model_selection import GridSearchCV
# from sklearn.model_selection import train_test_split
from graphviz import Source

iris = load_iris()
iris_limited = iris.data[:, [2, 3]]
# X_train, X_test, y_train, y_test = train_test_split(iris_limited, iris.target, test_size=0.3, random_state=42)

parameters = [
    {'ccp_alpha': [1/(2**k) for k in range(5, 23)]}
]
search = GridSearchCV(
    DecisionTreeClassifier(criterion="gini", random_state=42),
    parameters, scoring='accuracy', cv=10
)
# search.fit(X_train, y_train)
search.fit(iris_limited, iris.target)

>>> search.best_params_

{'ccp_alpha': 0.015625}

现在让我们构建与之前相同的树可视化，但现在我们将使用GridSearchCV.best_estimator_，它是DecisionTree通过在我们指定的 alpha 参数空间上搜索而选择的 。

gviz_raw = export_graphviz(
    search.best_estimator_,
    out_file=None,
    special_characters=True,
    feature_names=["length", "width"],
    class_names=iris.target_names,
    node_ids=True
)
with open('iris-ccp.png', 'wb') as f:
    f.write(Source(gviz_raw).pipe(format='png'))

我们得到下面的树：

请注意，我们生成了一棵树 T*，它是前面两棵树的子树。例如，向下到节点 #6 的分支与您的初始示例相同。为了演示目的，我使用了与您相同的（完整的）Iris 数据集（通常，我们会将数据拆分为训练集和测试集，然后仅对训练样本执行交叉验证）。这棵树在 Iris 数据上的表现稍差：

>>> clf.score(iris_limited, iris.target)
0.9933333333333333

>>> clf_star.score(iris_limited, iris.target)
0.9733333333333334

然而，交叉验证是一种有效的方法，我们的树应该具有更好的泛化能力。此外，根据您的请求，修剪后的树没有扩展节点#6。但你不应该相信我。看看吧。正如您之前所做的那样，训练不进行修剪的 a DecisionTree，以及使用交叉验证创建的另一棵树 T*，如我们刚才所描述的。仅这一次，用一半的数据训练这些树：

from sklearn.model_selection import train_test_split
X_train, X_test, Y_train, Y_test = train_test_split(iris.data, iris.target, test_size=0.5, random_state=42)

clf = DecisionTreeClassifier(criterion="gini", random_state=42)
clf.fit(X_train, Y_train)
search = GridSearchCV(
    DecisionTreeClassifier(criterion="gini", random_state=42),
    parameters, scoring='accuracy', cv=10)
search.fit(X_train, Y_train)

>>> clf.score(X_test, Y_test)
0.9066666666666666

>>> search.best_estimator_.score(X_test, Y_test)
0.9333333333333333