Skip to content

1.10. 决策树

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

例如,在下面的示例中,决策树从数据中学习使用一组if-then-else决策规则来近似正弦曲线。决策树越深,决策规则就越复杂,模型就越拟合。

https://scikit-learn.org/stable/_images/sphx_glr_plot_tree_regression_0011.png

决策树的优点如下:

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

  • 需要的数据量少。其他技术通常需要数据规范化,比如,需要创建虚拟变量,删除空白值。但是请注意,此模块不支持缺失值

  • 使用树的成本(即预测数据)在用于训练树的数据点的数量上是呈对数分布的。

  • 能够处理数值型数据和分类数据。其他技术通常只能分析一种变量类型的数据集。有关详细信息,请参见算法

  • 能够处理多输出问题。

  • 使用白盒模型。 如果在模型中某种给定的情况是可观察的,则可以通过布尔逻辑轻松解释条件。 相比之下,在黑匣子模型中(例如,在人工神经网络中),结果可能更难以解释。

  • 可以使用统计测试验证模型。这使我们有可能解释模型的可靠性。

  • 即使生成数据的真实模型在某种程度上违反了它的假设,也可以表现良好。

决策树的缺点包括:

  • 决策树模型可能会创建过于复杂的模型,从而无法很好地概括数据,导致模型泛化能力弱。 这称为过度拟合。 为避免此问题,必须使用诸如剪枝(当前不支持),设置叶节点处所需的最小样本数或设置树的最大深度之类的机制。
  • 决策树可能不稳定,因为数据的微小变化可能导致生成完全不同的树。使用集成决策树可以缓解这个问题。
  • 在多方面性能最优甚至简单概念的要求下,学习最优决策树问题都是NP-complete问题,因此,实际的决策树学习算法是基于启发式算法,例如贪婪算法,在每个节点上都有局部最优决策。这种算法不能保证返回全局最优决策树。这问题可以通过在一个集成学习器中训练多个树来缓解,其中特征和样本通过替换随机采样。
  • 有些概念很难学习,因为决策树无法轻松表达它们,例如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])。

使用 Iris 数据集,我们可以构建一棵决策树,如下所示:

>>> from sklearn.datasets import load_iris
>>> from sklearn import tree
>>> X, y = load_iris(return_X_y=True)
>>> clf = tree.DecisionTreeClassifier()
>>> clf = clf.fit(X, y)

经过训练后,可以使用plot-tree函数绘制树:

>>> tree.plot_tree(clf.fit(iris.data, iris.target))

https://scikit-learn.org/stable/_images/sphx_glr_plot_iris_dtc_0021.png

我们还可以使用export_Graphviz 导出器以Graphviz格式导出决策树。如果使用conda包管理器,那么安装graphviz二进制文件

和python包可以使用以下命令:

conda install python-graphviz

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

下面是在整个 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 notebooks还会自动内联渲染这些图:

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

https://scikit-learn.org/stable/_images/iris.png

https://scikit-learn.org/stable/_images/sphx_glr_plot_iris_dtc_0011.png

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

>>> from sklearn.datasets import load_iris
>>> from sklearn.tree import DecisionTreeClassifier
>>> from sklearn.tree.export 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
<BLANKLINE>

案例:

1.10.2. 回归

https://scikit-learn.org/stable/_images/sphx_glr_plot_tree_regression_0011.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个输出的平均减少量。

此模块通过在DecisionTreeClassifierDecisionTreeRegressor中实现此策略来支持多输出问题。如果决策树与大小为[n_samples,n_outputs]的输出数组Y相匹配,则得到的估计器将:

  • predict上输出n_output值;
  • predict_proba上输出类概率的n_output数组的列表。

Multi-output Decision Tree Regression中演示了使用多输出决策树进行回归分析。在本例中,输入X是单个实数值,输出Y是X的正弦和余弦。

https://scikit-learn.org/stable/_images/sphx_glr_plot_tree_regression_multioutput_0011.png

Face completion with a multi-output estimators中演示了使用多输出树进行分类。在本例中,输入X是脸的上半部分的像素,输出Y是这些脸的下半部分的像素。

https://scikit-learn.org/stable/_images/sphx_glr_plot_multioutput_face_completion_0011.png

案例:

参考文献:

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, or Feature selection) ,使树能更好地找到有区分性的特征。
  • Understanding the decision tree structure将有助于了解决策树如何进行预测,这对于了解数据中的重要特征非常重要。
  • 使用export函数在训练时可视化您的树。使用 max_depth=3作为初始树深度,以了解树如何拟合您的数据,然后增加树深度。
  • 请记住,填充树所需的样本数量对于树增长到的每个附加级别都会增加一倍。 使用max_depth控制树的大小以防止过拟合。
  • 使用min_samples_splitmin_samples_leaf以控制叶子节点上的样本数。这个值很小通常意味着树将过拟合,而这个值很大将阻止决策树对样本的学习。尝试将min_samples_leaf=5作为初始值。如果样本大小的变化量很大,则可以使用使用浮点数作为这两个参数中的百分比。虽然min_samples_split可以创建任意小的叶子,min_samples_leaf保证每个叶子都有最小样本数,避免了回归问题中的低方差、过拟合叶节点的现象。对于类数较少的分类,min_samples_leaf=1 通常是最佳选择。
  • 在训练之前平衡数据集,以防止树偏向主导类。类平衡可以通过从每个类中抽取相等数量的样本来完成,或者最好通过将每个类的样本权重(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$表示。每个候选集$\theta = (j, t_m)$由特征$j$和阈值$t_m$组成,将数据划分为$Q_{left}(\theta)$和 $Q_{right}(\theta)$子集。 $$ Q_{left}(\theta) = {(x, y) | x_j <= t_m} \Q_{right}(\theta) = Q \setminus Q_{left}(\theta) $$ 使用杂质函数(impurity function)$H()$计算$m$处的杂质(impurity),该函数的选择取决于正在解决的任务(分类或回归)。 $$ G(Q, \theta)= \frac{n_{left}}{N_m} H(Q_{left}(\theta)) + \frac{n_{right}}{N_m} H(Q_{right}(\theta)) $$ 选择使杂质(impurity)最小化的参数 $$ \theta^ = \operatorname{argmin}\theta G(Q, \theta) $$ 对$Q{left}(\theta^)$和$Q_{right}(\theta^*)$子集进行递归运算,直到达到最大允许深度$N_m < \min_{samples}$或$N_m = 1$。

1.10.7.1. 分类标准

如果目标是一个分类结果,其值为0,1,…,K-1,对于节点$m$,用$N_m$ 观测值表示区域$R_m$,令 $$ p_{mk} = 1/ N_m \sum_{x_i \in R_m} I(y_i = k) $$ 为节点$m$中类k观测的比例

常见的杂质处理方法是Gini(基尼) $$ H(X_m) = \sum_k p_{mk} (1 - p_{mk}) $$ 熵(Entropy) $$ H(X_m) = - \sum_k p_{mk} \log(p_{mk}) $$ 和误分类(Misclassification) $$ H(X_m) = 1 - \max(p_{mk}) $$ 其中$X_m$是节点$m$中的训练数据。

1.10.7.2. 回归标准

如果目标是一个连续值,那么对于节点$m$,表示具有$N_m$个观测值的区域$R_m$,确定未来分割位置常用最小化标准是均方误差和平均绝对误差,前者使用终端节点的平均值最小化L2误差,后者使用终端节点的中值最小化L1误差。

均方误差(Mean Squared Error ): $$ \bar{y}m = \frac{1}{N_m} \sum{i \in N_m} y_i\H(X_m) = \frac{1}{N_m} \sum_{i \in N_m} (y_i - \bar{y}_m)^2 $$

平均绝对误差(Mean Absolute Error): $$ \bar{y}m = \frac{1}{N_m} \sum{i \in N_m} y_i\H(X_m) = \frac{1}{N_m} \sum_{i \in N_m} |y_i - \bar{y}_m| $$ 其中$X_m$是节点$m$中的训练数据。

1.10.8. 最小代价复杂度(Cost-Complexity)剪枝

最小代价复杂度剪枝是一种用于修剪树以避免过拟合的算法,如[BRE]第3章所述。该算法由$\alpha\ge0$参数化,称为复杂度参数。复杂性参数用于定义给定树$T$的成本复杂性度量$R_\alpha(T)$: $$ R_\alpha(T) = R(T) + \alpha|T| $$ 其中$|T|$是$T$中的终端节点数, $R(T)$通常被定义为终端节点的总误分类率。或者,scikit-learn将终端节点的总样本加权杂质用于$R(T)$。如上所示,节点的杂质取决于使用标准。最小代价复杂度剪枝查找使$R_\alpha(T)$最小化$T$的子树。

单个节点的成本复杂度度量为$R_\alpha(t)=R(t)+\alpha$。分支$T_t$被定义为其根结点为$t$的树。一般来说,节点的杂质大于其终端节点的杂质之和,$R_\alpha(T_t)<R_\alpha(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.

(C) 2007 - 2019, scikit-learn 开发人员 (BSD 许可证). 此页显示源码