1.10. 决策树#

决策树 (DT) 是一种非参数的有监督学习方法，用于分类和回归。其目标是通过学习从数据特征中推断出的简单决策规则，创建一个预测目标变量值的模型。树可以被视为分段常数逼近。

例如，在下面的示例中，决策树从数据中学习，通过一组if-then-else决策规则来逼近正弦曲线。树越深，决策规则越复杂，模型拟合度越高。

../_images/sphx_glr_plot_tree_regression_001.png

决策树的一些优点是

易于理解和解释。树可以被可视化。
需要较少的数据准备。其他技术通常需要数据归一化，创建哑变量并移除空值。一些树和算法组合支持缺失值。
使用树（即预测数据）的成本与训练树所用的数据点数量呈对数关系。
能够处理数值和类别数据。然而，scikit-learn的实现目前不支持类别变量。其他技术通常专门分析只有一种变量类型的数据集。更多信息请参见算法。
能够处理多输出问题。
使用白盒模型。如果模型中某个给定情况是可观察的，那么其条件解释可以很容易地用布尔逻辑来阐明。相比之下，在黑盒模型（例如，人工神经网络）中，结果可能更难解释。
可以使用统计测试验证模型。这使得考虑模型的可靠性成为可能。
即使其假设在某种程度上被生成数据的真实模型所违反，它也能表现良好。

决策树的缺点包括

决策树学习器可能创建过于复杂的树，从而无法很好地泛化数据。这称为过拟合。为了避免这个问题，需要剪枝、设置叶节点所需的最小样本数或设置树的最大深度等机制。
决策树可能不稳定，因为数据的微小变化可能导致生成完全不同的树。通过在集成方法中使用决策树可以缓解这个问题。
决策树的预测既不平滑也不连续，而是如上图所示的分段常数逼近。因此，它们不擅长外推。
学习最优决策树的问题在多个优化方面，甚至对于简单概念，都是NP完全的。因此，实用的决策树学习算法基于启发式算法，例如贪婪算法，其中在每个节点做出局部最优决策。此类算法无法保证返回全局最优决策树。通过在集成学习器中训练多棵树可以缓解这个问题，其中特征和样本是随机有放回抽样的。
有些概念很难学习，因为决策树不容易表达它们，例如异或（XOR）、奇偶校验或多路复用器问题。
如果某些类别占主导地位，决策树学习器会创建有偏的树。因此，建议在用决策树拟合之前平衡数据集。

1.10.1. 分类#

DecisionTreeClassifier 是一个能够对数据集执行多类别分类的类。

与其他分类器一样，DecisionTreeClassifier 接受两个数组作为输入：一个稀疏或稠密的数组 X，形状为 (n_samples, n_features)，包含训练样本；以及一个整数值数组 Y，形状为 (n_samples,)，包含训练样本的类别标签。

>>> from sklearn import tree
>>> X = [[0, 0], [1, 1]]
>>> Y = [0, 1]
>>> clf = tree.DecisionTreeClassifier()
>>> clf = clf.fit(X, Y)

拟合后，模型可以用于预测样本的类别。

>>> clf.predict([[2., 2.]])
array([1])

如果存在多个类别具有相同且最高的概率，分类器将预测这些类别中索引最低的类别。

作为输出特定类别的替代方案，可以预测每个类别的概率，这是叶节点中该类别训练样本的比例。

>>> clf.predict_proba([[2., 2.]])
array([[0., 1.]])

DecisionTreeClassifier 能够进行二元分类（标签为[-1, 1]）和多类别分类（标签为[0, …, K-1]）。

使用鸢尾花数据集，我们可以构建一棵树，如下所示：

>>> from sklearn.datasets import load_iris
>>> from sklearn import tree
>>> iris = load_iris()
>>> X, y = iris.data, iris.target
>>> clf = tree.DecisionTreeClassifier()
>>> clf = clf.fit(X, y)

训练后，可以使用 plot_tree 函数绘制树。

>>> tree.plot_tree(clf)
[...]

../_images/sphx_glr_plot_iris_dtc_002.png

示例

1.10.2. 回归#

决策树也可应用于回归问题，使用 DecisionTreeRegressor 类。

与分类设置中一样，拟合方法将接受数组 X 和 y 作为参数，只是在这种情况下，y 预计为浮点值而不是整数值。

>>> from sklearn import tree
>>> X = [[0, 0], [2, 2]]
>>> y = [0.5, 2.5]
>>> clf = tree.DecisionTreeRegressor()
>>> clf = clf.fit(X, y)
>>> clf.predict([[1, 1]])
array([0.5])

示例

决策树回归

1.10.3. 多输出问题#

多输出问题是一种有监督学习问题，有多个输出需要预测，即当 Y 是形状为 (n_samples, n_outputs) 的二维数组时。

当输出之间没有相关性时，解决这类问题的一个非常简单的方法是构建 n 个独立模型，即每个输出一个模型，然后使用这些模型独立预测 n 个输出中的每一个。然而，由于同一输入相关的输出值本身很可能存在相关性，因此通常更好的方法是构建一个能够同时预测所有 n 个输出的单一模型。首先，这需要更少的训练时间，因为只构建一个估计器。其次，所得估计器的泛化精度通常会提高。

对于决策树，此策略可以很容易地用于支持多输出问题。这需要进行以下更改：

在叶节点中存储 n 个输出值，而不是 1 个；
使用在所有 n 个输出上计算平均缩减量的分裂准则。

此模块通过在 DecisionTreeClassifier 和 DecisionTreeRegressor 中实现此策略来支持多输出问题。如果决策树拟合到形状为 (n_samples, n_outputs) 的输出数组 Y，则生成的估计器将：

在 predict 时输出 n_output 个值；
在 predict_proba 时输出一个包含 n_output 个类别概率数组的列表。

多输出树在回归中的应用在决策树回归中有所演示。在此示例中，输入 X 是一个单一实数值，输出 Y 是 X 的正弦和余弦。

../_images/sphx_glr_plot_tree_regression_002.png

多输出树在分类中的应用在使用多输出估计器进行人脸补全中有所演示。在此示例中，输入 X 是人脸上半部分的像素，输出 Y 是人脸下半部分的像素。

../_images/sphx_glr_plot_multioutput_face_completion_001.png

示例

使用多输出估计器进行人脸补全

参考文献

M. Dumont et al, 基于随机子窗口和多输出随机树的快速多类别图像标注，2009 年计算机视觉理论与应用国际会议

1.10.4. 复杂度#

通常，构建平衡二叉树的运行时成本为 \(O(n_{samples}n_{features}\log(n_{samples}))\)，查询时间为 \(O(\log(n_{samples}))\)。尽管树构建算法试图生成平衡树，但它们并非总是平衡的。假设子树保持大致平衡，每个节点的成本包括搜索 \(O(n_{features})\) 以找到在不纯度准则中提供最大减少的特征，例如对数损失（等同于信息增益）。这在每个节点的成本为 \(O(n_{features}n_{samples}\log(n_{samples}))\)，导致整个树的总成本（通过对每个节点的成本求和）为 \(O(n_{features}n_{samples}^{2}\log(n_{samples}))\)。

1.10.5. 实用建议#

决策树在具有大量特征的数据上容易过拟合。获得正确的样本与特征数量比率很重要，因为在高维空间中样本较少的树很可能过拟合。
考虑预先进行降维（PCA、ICA 或特征选择），以使您的树更有机会找到具有区分性的特征。
理解决策树结构将有助于更深入地了解决策树如何进行预测，这对于理解数据中的重要特征至关重要。
在训练时使用 export 函数可视化您的树。使用 max_depth=3 作为初始树深度，以了解树如何拟合您的数据，然后增加深度。
请记住，树每增加一层，填充树所需的样本数量就会翻倍。使用 max_depth 控制树的大小以防止过拟合。
使用 min_samples_split 或 min_samples_leaf 通过控制考虑哪些分裂，来确保每个决策都由多个样本决定。非常小的数字通常意味着树会过拟合，而非常大的数字则会阻止树学习数据。可以尝试将 min_samples_leaf=5 作为初始值。如果样本量变化很大，这两个参数可以使用浮点数作为百分比。虽然 min_samples_split 可以创建任意小的叶节点，但 min_samples_leaf 保证每个叶节点都有最小尺寸，从而避免回归问题中低方差、过拟合的叶节点。对于类别较少的分类问题，min_samples_leaf=1 通常是最佳选择。

请注意，min_samples_split 直接考虑样本，并且独立于（如果提供了）sample_weight（例如，一个包含 m 个加权样本的节点仍被视为恰好包含 m 个样本）。如果需要在分裂时考虑样本权重，请考虑 min_weight_fraction_leaf 或 min_impurity_decrease。
在训练前平衡数据集，以防止树偏向于占主导地位的类别。类别平衡可以通过从每个类别中抽取相同数量的样本来完成，或者优选地，通过将每个类别的样本权重总和（sample_weight）归一化到相同的值。另请注意，基于权重的预剪枝准则，例如 min_weight_fraction_leaf，相比于不考虑样本权重的准则（如 min_samples_leaf），对主导类别的偏向会更小。
如果样本是加权的，使用基于权重的预剪枝准则（例如 min_weight_fraction_leaf）来优化树结构会更容易，这确保了叶节点至少包含样本权重总和的一部分。
所有决策树内部都使用 np.float32 数组。如果训练数据不是此格式，将创建数据集的副本。
如果输入矩阵 X 非常稀疏，建议在调用 fit 之前将其转换为稀疏 csc_matrix，并在调用 predict 之前转换为稀疏 csr_matrix。当大多数样本中的特征值为零时，稀疏矩阵输入的训练时间比稠密矩阵快几个数量级。

1.10.6. 树算法：ID3、C4.5、C5.0 和 CART#

各种决策树算法有哪些？它们之间有什么区别？scikit-learn 中实现了哪种算法？

scikit-learn 使用 CART 算法的优化版本；然而，scikit-learn 的实现目前不支持类别变量。

1.10.7. 数学公式#

给定训练向量 \(x_i \in R^n\) (i=1,…, l) 和标签向量 \(y \in R^l\)，决策树递归地划分特征空间，使得具有相同标签或相似目标值的样本被分组在一起。

令节点 \(m\) 处的数据表示为 \(Q_m\)，包含 \(n_m\) 个样本。对于每个候选分裂 \(\theta = (j, t_m)\)，由特征 \(j\) 和阈值 \(t_m\) 组成，将数据划分为 \(Q_m^{left}(\theta)\) 和 \(Q_m^{right}(\theta)\) 子集

\[ \begin{align}\begin{aligned}Q_m^{left}(\theta) = \{(x, y) | x_j \leq t_m\}\\Q_m^{right}(\theta) = Q_m \setminus Q_m^{left}(\theta)\end{aligned}\end{align} \]

然后使用不纯度函数或损失函数 \(H()\) 计算节点 \(m\) 的候选分裂的质量，其选择取决于正在解决的任务（分类或回归）。

\[G(Q_m, \theta) = \frac{n_m^{left}}{n_m} H(Q_m^{left}(\theta)) + \frac{n_m^{right}}{n_m} H(Q_m^{right}(\theta))\]

选择最小化不纯度的参数

\[\theta^* = \operatorname{argmin}_\theta G(Q_m, \theta)\]

对子集 \(Q_m^{left}(\theta^*)\) 和 \(Q_m^{right}(\theta^*)\) 进行递归，直到达到最大允许深度，\(n_m < \min_{samples}\) 或 \(n_m = 1\)。

1.10.7.1. 分类准则#

如果目标是一个分类结果，取值为 0,1,…,K-1，对于节点 \(m\)，令

\[p_{mk} = \frac{1}{n_m} \sum_{y \in Q_m} I(y = k)\]

为节点 \(m\) 中类别 k 观测值的比例。如果 \(m\) 是一个叶节点，该区域的 predict_proba 被设置为 \(p_{mk}\)。常见的不纯度度量如下：

基尼（Gini）

\[H(Q_m) = \sum_k p_{mk} (1 - p_{mk})\]

对数损失或熵

\[H(Q_m) = - \sum_k p_{mk} \log(p_{mk})\]

1.10.7.2. 回归准则#

如果目标是连续值，那么对于节点 \(m\)，用于确定未来分裂位置的常见最小化准则有均方误差（MSE 或 L2 误差）、泊松偏差以及平均绝对误差（MAE 或 L1 误差）。MSE 和泊松偏差都将叶节点的预测值设置为节点的学习平均值 \(\bar{y}_m\)，而 MAE 则将叶节点的预测值设置为中位数 \(median(y)_m\)。

均方误差

\[ \begin{align}\begin{aligned}\bar{y}_m = \frac{1}{n_m} \sum_{y \in Q_m} y\\H(Q_m) = \frac{1}{n_m} \sum_{y \in Q_m} (y - \bar{y}_m)^2\end{aligned}\end{align} \]

平均泊松偏差

\[H(Q_m) = \frac{2}{n_m} \sum_{y \in Q_m} (y \log\frac{y}{\bar{y}_m} - y + \bar{y}_m)\]

如果您的目标是计数或频率（每单位计数），则将 criterion="poisson" 设置为一个不错的选择。无论如何，\(y >= 0\) 是使用此准则的必要条件。请注意，它的拟合速度比 MSE 准则慢得多。出于性能原因，实际实现最小化的是半平均泊松偏差，即平均泊松偏差除以 2。

平均绝对误差

\[ \begin{align}\begin{aligned}median(y)_m = \underset{y \in Q_m}{\mathrm{median}}(y)\\H(Q_m) = \frac{1}{n_m} \sum_{y \in Q_m} |y - median(y)_m|\end{aligned}\end{align} \]

请注意，它的拟合速度比 MSE 准则慢得多。

1.10.8. 缺失值支持#

DecisionTreeClassifier 和 DecisionTreeRegressor 内置支持缺失值，使用 splitter='best'，其中分裂以贪婪方式确定。ExtraTreeClassifier 和 ExtraTreeRegressor 内置支持缺失值，使用 splitter='random'，其中分裂是随机确定的。有关分裂器在非缺失值上的差异的更多详细信息，请参阅森林部分。

支持缺失值时，分类任务支持的准则有 'gini'、'entropy' 或 'log_loss'，回归任务支持的准则有 'squared_error'、'friedman_mse' 或 'poisson'。

首先，我们将描述 DecisionTreeClassifier 和 DecisionTreeRegressor 如何处理数据中的缺失值。

对于非缺失数据的每个潜在阈值，分裂器将评估所有缺失值进入左节点或右节点的分裂。

决策如下：

默认情况下，在预测时，缺失值样本会根据训练期间发现的分裂中使用的类别进行分类。

>>> from sklearn.tree import DecisionTreeClassifier
>>> import numpy as np

>>> X = np.array([0, 1, 6, np.nan]).reshape(-1, 1)
>>> y = [0, 0, 1, 1]

>>> tree = DecisionTreeClassifier(random_state=0).fit(X, y)
>>> tree.predict(X)
array([0, 0, 1, 1])

如果两个节点的准则评估结果相同，则预测时缺失值的平局通过将缺失值分配给右节点来解决。分裂器还会检查所有缺失值进入一个子节点而所有非缺失值进入另一个子节点的分裂情况。

>>> from sklearn.tree import DecisionTreeClassifier
>>> import numpy as np

>>> X = np.array([np.nan, -1, np.nan, 1]).reshape(-1, 1)
>>> y = [0, 0, 1, 1]

>>> tree = DecisionTreeClassifier(random_state=0).fit(X, y)

>>> X_test = np.array([np.nan]).reshape(-1, 1)
>>> tree.predict(X_test)
array([1])

如果在训练期间某个给定特征没有出现缺失值，那么在预测时，缺失值会被映射到具有最多样本的子节点。

>>> from sklearn.tree import DecisionTreeClassifier
>>> import numpy as np

>>> X = np.array([0, 1, 2, 3]).reshape(-1, 1)
>>> y = [0, 1, 1, 1]

>>> tree = DecisionTreeClassifier(random_state=0).fit(X, y)

>>> X_test = np.array([np.nan]).reshape(-1, 1)
>>> tree.predict(X_test)
array([1])

ExtraTreeClassifier 和 ExtraTreeRegressor 处理缺失值的方式略有不同。在分裂节点时，会选择一个随机阈值来分裂非缺失值。然后，非缺失值将根据随机选择的阈值发送到左子节点和右子节点，而缺失值也将随机发送到左子节点或右子节点。这在每个分裂中，对于考虑的每个特征都会重复进行。然后选择其中最好的分裂。

在预测期间，缺失值的处理方式与决策树相同：

默认情况下，在预测时，缺失值样本会根据训练期间发现的分裂中使用的类别进行分类。
如果在训练期间某个给定特征没有出现缺失值，那么在预测时，缺失值会被映射到具有最多样本的子节点。

1.10.9. 最小成本复杂度剪枝#

最小成本复杂度剪枝是一种用于剪枝以避免过拟合的算法，在 [BRE] 的第 3 章中有所描述。该算法由复杂性参数 \(\alpha\ge0\) 参数化。该复杂性参数用于定义给定树 \(T\) 的成本复杂度度量 \(R_\alpha(T)\)

\[R_\alpha(T) = R(T) + \alpha|\widetilde{T}|\]

其中 \(|\widetilde{T}|\) 是 \(T\) 中的叶节点数量，\(R(T)\) 传统上定义为叶节点的总误分类率。或者，scikit-learn 使用叶节点的总样本加权不纯度作为 \(R(T)\)。如上所示，节点的不纯度取决于准则。最小成本复杂度剪枝找到使 \(R_\alpha(T)\) 最小化的 \(T\) 的子树。

单个节点的成本复杂度度量为 \(R_\alpha(t)=R(t)+\alpha\)。分支 \(T_t\) 定义为以节点 \(t\) 为根的树。通常，节点的不纯度大于其叶节点不纯度之和，即 \(R(T_t)<R(t)\)。然而，节点 \(t\) 及其分支 \(T_t\) 的成本复杂度度量可以相等，这取决于 \(\alpha\)。我们将节点的有效 \(\alpha\) 定义为它们相等时的值，即 \(R_\alpha(T_t)=R_\alpha(t)\) 或 \(\alpha_{eff}(t)=\frac{R(t)-R(T_t)}{|T|-1}\)。具有最小 \(\alpha_{eff}\) 值的非叶节点是最弱的连接，将被剪枝。当剪枝后树的最小 \(\alpha_{eff}\) 大于 ccp_alpha 参数时，此过程停止。

示例

使用成本复杂度剪枝对决策树进行后剪枝