1.10. 决策树

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

例如，在下面的示例中，决策树从数据中学习，用一组 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 Notebook还会自动内联渲染这些绘图。

>>> 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\)，对于每个类别\(k\)，都有\(T_k(x_i) = p_{mk}\)。

此属性使得可以将\(\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{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' 内置支持缺失值，其中分割随机确定。有关分隔符在非缺失值上的差异的更多详细信息，请参阅 Forest 部分。

存在缺失值时支持的标准为 '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 参数时，此过程停止。

示例

• 使用成本复杂度剪枝的后剪枝决策树

参考文献

[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：机器学习程序。Morgan Kaufmann，1993 年。

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