1.10. 决策树#

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

例如，在下面的示例中，决策树从数据中学习，用一组 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
#导出树的其他方法

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

并且可以使用 conda install python-graphviz 安装 Python 包。

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

下面是一个在完整鸢尾花数据集上训练的上述树的 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
../_images/iris.svg
../_images/sphx_glr_plot_iris_dtc_001.png

另外，树也可以使用函数 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

示例

1.10.2. 回归#

../_images/sphx_glr_plot_tree_regression_001.png

决策树也可以应用于回归问题，使用 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个输出的平均减少量的分割标准。

本模块通过在:class:DecisionTreeClassifier 和:class:DecisionTreeRegressor 中实现这种策略来支持多输出问题。如果在一组形状为 (n_samples, n_outputs) 的输出数组Y上拟合决策树，那么得到的估计器将：

  • 在 predict 时输出n_output值；

  • 在 predict_proba 时输出一个包含n_output个类概率数组的列表。

多输出树在回归中的使用示例见:ref:sphx_glr_auto_examples_tree_plot_tree_regression_multioutput.py 。在这个例子中，输入X是一个实数值，输出Y是X的正弦和余弦。

../_images/sphx_glr_plot_tree_regression_multioutput_001.png

多输出树在分类中的使用示例见:ref:sphx_glr_auto_examples_miscellaneous_plot_multioutput_face_completion.py 。在这个例子中，输入X是面部上半部分的像素，输出Y是这些面部下半部分的像素。

../_images/sphx_glr_plot_multioutput_face_completion_001.png
target:

../auto_examples/miscellaneous/plot_multioutput_face_completion.html

scale:

75

align:

center

示例

参考文献

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)\) 。如上所示，节点的不纯度取决于准则。最小成本复杂度剪枝找到使 \(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, and C. Stone. Classification and Regression Trees. Wadsworth, Belmont, CA, 1984.

学习，Springer，2009年。

On this page
Show Source