1.10. 决策树

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

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

决策树的一些优点是

• 易于理解和解释。树可以可视化。

• 需要很少的数据准备。其他技术通常需要数据归一化，需要创建虚拟变量，并删除空白值。一些树和算法组合支持 缺失值。

• 使用树的成本（即预测数据）与用于训练树的数据点的数量的对数成正比。

• 能够处理数值数据和分类数据。但是，scikit-learn 实现目前不支持分类变量。其他技术通常专门用于分析仅包含一种变量类型的数据集。有关更多信息，请参阅 算法。

• 能够处理多输出问题。

• 使用白盒模型。如果在模型中观察到特定情况，则该条件的解释可以通过布尔逻辑轻松解释。相比之下，在黑盒模型（例如，在人工神经网络中），结果可能更难解释。

• 可以使用统计检验来验证模型。这使得可以考虑模型的可靠性。

• 即使其假设在一定程度上被生成数据的真实模型所违反，也能表现良好。

决策树的缺点包括

• 决策树学习器可以创建过度复杂的树，这些树不能很好地概括数据。这被称为过拟合。为了避免这个问题，需要使用修剪、设置叶节点所需的最小样本数或设置树的最大深度等机制。

• 决策树可能不稳定，因为数据中的微小变化可能会导致生成完全不同的树。这个问题可以通过在集成中使用决策树来缓解。

• 决策树的预测既不平滑也不连续，而是如上图所示的分段常数逼近。因此，它们不擅长外推。

• 学习最优决策树的问题在几个方面（包括最优性和简单概念）都是已知的 NP 完全问题。因此，实际的决策树学习算法基于启发式算法，例如贪婪算法，在每个节点上做出局部最优决策。此类算法不能保证返回全局最优决策树。这可以通过在集成学习器中训练多棵树来缓解，其中特征和样本是随机抽取并替换的。

• 有一些概念很难学习，因为决策树不容易表达它们，例如 XOR、奇偶校验或多路复用器问题。

• 如果某些类占主导地位，决策树学习器会创建有偏差的树。因此，建议在使用决策树拟合之前平衡数据集。

1.10.1. 分类

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

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

>>> 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]）。

使用 Iris 数据集，我们可以构建一棵树，如下所示

>>> 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)
[...]

导出树的替代方法

我们还可以使用 export_graphviz 导出器将树导出为 Graphviz 格式。如果您使用 conda 包管理器，则可以使用 conda install python-graphviz 安装 graphviz 二进制文件和 python 包。

或者，可以从 graphviz 项目主页下载 graphviz 二进制文件，并使用 pip install graphviz 从 pypi 安装 Python 包装器。

以下是使用整个 iris 数据集训练的上述树的 graphviz 导出示例；结果保存在输出文件 iris.pdf 中

>>> import graphviz 
>>> dot_data = tree.export_graphviz(clf, out_file=None) 
>>> graph = graphviz.Source(dot_data) 
>>> graph.render("iris") 

export_graphviz 导出器还支持各种美学选项，包括根据节点的类别（或回归值）对节点进行着色，以及根据需要使用显式变量和类别名称。Jupyter 笔记本还自动在内联中呈现这些绘图

>>> dot_data = tree.export_graphviz(clf, out_file=None, 
...                      feature_names=iris.feature_names,  
...                      class_names=iris.target_names,  
...                      filled=True, rounded=True,  
...                      special_characters=True)  
>>> graph = graphviz.Source(dot_data)  
>>> graph 

或者，可以使用函数 export_text 以文本格式导出树。此方法不需要安装外部库，并且更紧凑

>>> from sklearn.datasets import load_iris
>>> from sklearn.tree import DecisionTreeClassifier
>>> from sklearn.tree import export_text
>>> iris = load_iris()
>>> decision_tree = DecisionTreeClassifier(random_state=0, max_depth=2)
>>> decision_tree = decision_tree.fit(iris.data, iris.target)
>>> r = export_text(decision_tree, feature_names=iris['feature_names'])
>>> print(r)
|--- petal width (cm) <= 0.80
|   |--- class: 0
|--- petal width (cm) >  0.80
|   |--- petal width (cm) <= 1.75
|   |   |--- class: 1
|   |--- petal width (cm) >  1.75
|   |   |--- class: 2

示例

• 绘制在 iris 数据集上训练的决策树的决策面

• 了解决策树结构

1.10.2. 回归

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

与分类设置一样，fit 方法将接受数组 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 的正弦和余弦。

在 使用多输出估计器完成人脸 中演示了多输出树在分类中的使用。在此示例中，输入 X 是人脸的上半部分的像素，输出 Y 是这些人脸的下半部分的像素。

示例

• 多输出决策树回归

• 使用多输出估计器完成人脸

参考文献

• M. Dumont 等人，使用随机子窗口和多输出随机树进行快速多类图像标注，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 中实现了哪一个？

各种决策树算法

ID3（迭代二分器 3）由 Ross Quinlan 于 1986 年开发。该算法创建了一个多路树，为每个节点（即以贪婪的方式）找到将为分类目标产生最大信息增益的分类特征。树木被生长到最大尺寸，然后通常应用一个修剪步骤来提高树对看不见的数据进行泛化的能力。

C4.5 是 ID3 的继任者，它消除了特征必须是分类的限制，方法是动态地定义一个离散属性（基于数值变量），该属性将连续属性值划分为一组离散的区间。C4.5 将训练好的树（即 ID3 算法的输出）转换为一组 if-then 规则。然后评估每个规则的准确性以确定应用它们的顺序。修剪是通过删除规则的前提条件来完成的，如果规则的准确性在没有前提条件的情况下得到提高。

C5.0 是 Quinlan 在专有许可下发布的最新版本。它使用更少的内存并构建比 C4.5 更小的规则集，同时更准确。

CART（分类和回归树）与 C4.5 非常相似，但它不同之处在于它支持数值目标变量（回归）并且不计算规则集。CART 使用在每个节点产生最大信息增益的特征和阈值来构建二叉树。

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}\)。常见的杂质度量如下。

基尼

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

对数损失或熵

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

香农熵

熵标准计算可能类别的香农熵。它将到达给定叶子 \(m\) 的训练数据点的类别频率作为它们的概率。使用**香农熵作为树节点分割标准等效于最小化真实标签 \(y_i\) 和树模型 \(T\) 对类别 \(k\) 的概率预测 \(T_k(x_i)\) 之间的对数损失**（也称为交叉熵和多项式偏差）。

要看到这一点，首先回想一下在数据集 \(D\) 上计算的树模型 \(T\) 的对数损失定义如下

\[\mathrm{LL}(D, T) = -\frac{1}{n} \sum_{(x_i, y_i) \in D} \sum_k I(y_i = k) \log(T_k(x_i))\]

其中 \(D\) 是 \(n\) 对 \((x_i, y_i)\) 的训练数据集。

在分类树中，叶子节点内的预测类别概率是恒定的，即：对于所有 \((x_i, y_i) \in Q_m\)，都有：\(T_k(x_i) = p_{mk}\) 对于每个类别 \(k\)。

此属性使得能够将 \(\mathrm{LL}(D, T)\) 重写为为每个叶子 \(T\) 计算的香农熵之和，并按到达每个叶子的训练数据点的数量加权

\[\mathrm{LL}(D, T) = \sum_{m \in T} \frac{n_m}{n} H(Q_m)\]

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{1}{n_m} \sum_{y \in Q_m} (y \log\frac{y}{\bar{y}_m} - y + \bar{y}_m)\]

设置 criterion="poisson" 可能是您目标是计数或频率（每个单位的计数）时的不错选择。在任何情况下，\(y >= 0\) 是使用此标准的必要条件。请注意，它比 MSE 标准拟合得慢得多。

平均绝对误差

\[ \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' 且标准为 'gini'、'entropy' 或 'log_loss'（用于分类）或 'squared_error'、'friedman_mse' 或 'poisson'（用于回归）时，内置支持缺失值。

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

决策过程如下：

• 默认情况下，在预测时，具有缺失值的样本将被分类为训练期间找到的分割中使用的类别。

  >>> 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])
  

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)\)。如上所示，节点的杂质取决于标准。最小成本复杂度剪枝找到 \(T\) 的子树，该子树使 \(R_\alpha(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 参数时，此过程停止。

示例

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

参考文献

[BRE]

L. Breiman, J. Friedman, R. Olshen 和 C. Stone。分类与回归树。Wadsworth，贝尔蒙特，加利福尼亚州，1984 年。

• https://en.wikipedia.org/wiki/Decision_tree_learning

• https://en.wikipedia.org/wiki/Predictive_analytics

• J.R. Quinlan。C4. 5：机器学习程序。摩根考夫曼，1993 年。

• T. Hastie、R. Tibshirani 和 J. Friedman。统计学习要素，施普林格，2009 年。