1.10 决策树

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

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

决策树的一些优点:

  • 易于理解和解释。树可以被可视化。
  • 几乎不需要数据准备。其他算法通常需要数据标准化,需要创建虚拟变量并删除缺失值。但是,请注意,此模块不支持缺失值。
  • 使用树的成本(即预测数据)是用于训练树的数据点数的对数。
  • 能够处理数值型和分类型数据。其他技术通常专门分析只有一种类型变量的数据集。有关更多信息,请参见algorithms
  • 能够处理多输出问题。
  • 使用白盒模型。如果给定的情况在模型中是可以观察到的,那么对条件的解释就很容易用布尔逻辑来解释。相反,在黑箱模型中(例如,在人工神经网络中),结果可能很难解释。
  • 可以使用统计测试验证模型。这样就有可能对模型的可靠性作出解释。
  • 即使它的假设在某种程度上被生成数据的真实模型所违背,它也表现得很好。

决策树的缺点包括:

  • 决策树学习器可以创建过于复杂的树,不能很好地概括数据。这就是所谓的过拟合。为了避免这个问题,必须设置剪枝、设置叶节点所需的最小样本数或设置树的最大深度等机制。

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

  • 学习最优决策树的问题在最优性的几个方面都是NP-complete的,甚至对于简单的概念也是如此。因此,实际的决策树学习算法是基于启发式算法,如贪婪算法,在每个节点上进行局部最优决策。这种算法不能保证返回全局最优决策树。这可以通过训练多棵树再集成一个学习器来缓解,其中特征和样本被随机抽取并替换。

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

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

1.10.1 分类

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

与其他分类器一样,DecisionTreeClassifier使用两个数组作为输入:形状为[n_samples, n_features]的数组(稀疏或稠密),以及整数值数组,形状[n_samples],保存训练样本的类标签:

>>> from sklearn import tree
>>> X = [[00], [11]]
>>> Y = [01]
>>> 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) 

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

另外,还可以从Graphviz项目主页下载用于Graphviz的二进制文件,并从pypi使用 pip install graphviz安装Python包装器并安装Graphviz。

下面是对整个 iris 数据集进行训练的树的图形输出示例;结果保存在一个输出文件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
<BLANKLINE>
示例
在iris数据集中绘制决策树的决策面
理解决策树结构

1.10.2 回归

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

与分类的设置一样,fit方法需要参数数组X和y,只是在这种情况下,y可以有浮点数值,而不是整数值:

>>> from sklearn import tree
>>> X = [[00], [22]]
>>> y = [0.52.5]
>>> clf = tree.DecisionTreeRegressor()
>>> clf = clf.fit(X, y)
>>> clf.predict([[11]])
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的列表。

多输出决策树回归中说明了多输出树在回归上的应用。 在该示例中,输入X是单个实数值,并且输出Y是X的正弦和余弦。

使用多输出估算器完成人脸绘制中演示了多输出树的分类的使用。在这个例子中,输入X是人脸的上半部分的像素,输出Y是这些人脸的下半部的像素。

示例
多输出决策树回归
使用多输出估算器完成人脸绘制

参考

M. Dumont et al, Fast multi-class image annotation with random subwindows and multiple output randomized trees, International Conference on Computer Vision Theory and Applications 2009

1.10.4 复杂度

通常,构建平衡二叉树的运行时间代价是和查询时间是。虽然树构造算法试图生成平衡树,但它们并不总是平衡的。假设子树保持近似平衡,每个节点的代价成本是通过搜索找到熵减少最大的特征。这在每个节点上的成本为,导致整个树的总成本(通过将每个节点的成本求和)是

1.10.5 实用技巧

  • 对于拥有大量特征的数据决策树会趋向于过拟合。获得一个合适的样本与特征的比例十分重要,因为具有高维空间中只有少量的样本的, 那树是十分容易过拟合的。

  • 考虑在此之前进行降维((PCA, ICA, 或者 Feature selection) ),以便给您的树更好的机会找到更有区分度的特征。

  • 通过 export 功能可以可视化您的决策树。使用 max_depth=3 作为初始树深度,让决策树知道如何适应您的数据,然后再增加树的深度。

  • 了解决策树结构理解决策树的结构 将有助于更深入地了解决策树是如何进行预测的,这对于理解数据中的重要特性非常重要。

  • 通过 export 功能可以可视化您的决策树。使用 max_depth=3 作为初始树深度,让决策树知道如何适应您的数据,然后再增加树的深度。

  • 通过使用 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 数学公式

给定训练向量 I和标签向量,决策树递归地划分空间,使得具有相同标签的样本被分到一样的组。

让节点处的数据集用表示,对于一个由特征和阈值组成的候选划分数据集,将数据划分为两个子集。

节点处的不存度用不存度函数计算,其选择取决于正在解决的任务(分类或回归)。

选择使不存度最小化的参数

对子集进行递归,直到达到最大允许的深度,

1.10.7.1 分类标准

如果目标是变量的值0,1,…K-1的分类结果,对于节点,表示具有个观测值的区域,令:

表示的是节点中k类观测的比例。

常见的不存度度量的方法是 Gini

熵(Entropy)

和错误分类(Misclassification)

其中是节点中的训练数据。

1.10.7.2 回归标准

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

均方误差:

平均绝对误差:

其中是节点中的训练数据。

1.10.8 最小成本复杂度剪枝

最小代价复杂度剪枝是一种用于修剪树以避免过拟合的算法,在[BRE]第3章中描述了这种算法。该算法由作为复杂度参数进行参数化。复杂度参数用于定义给定树的成本复杂度度量

其中,中的终端节点数,传统上定义为终端节点的总误分类率。或者,scikit-learn使用终端节点的总样本加权不存度作为。如上所述,节点的不存度取决于标准(criterion)。最小成本-复杂度剪枝找到的子树,使最小化。

单节点的代价复杂度度量为 被定义为一棵树,其中分支节点是它的根。一般而言,节点的不存度大于其叶子节点的不存度之和,。然而,节点及其分支 的成本复杂度度量取决于。我们定义了一个节点的有效为与它们相等的值, 或者。一个非叶子节点,其最小的是最弱的连接(weakest link),并将被修剪。当被剪枝的树的最小的ccp_alpha参数大时,此过程将停止。

示例
具有成本复杂度的后剪枝决策树

参考

[BRE] L. Breiman, J. Friedman, R. Olshen, and C. Stone. Classification and Regression Trees. Wadsworth, Belmont, CA, 1984.