1.10. 决策树

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

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

决策树的优点如下：

易于理解和解释。树可以进行可视化.
需要的数据量少。其他技术通常需要数据规范化，比如，需要创建虚拟变量，删除空白值。但是请注意，此模块不支持缺失值
使用树的成本（即预测数据）在用于训练树的数据点的数量上是呈对数分布的。
能够处理数值型数据和分类数据。其他技术通常只能分析一种变量类型的数据集。有关详细信息，请参见算法。
能够处理多输出问题。
使用白盒模型。如果在模型中某种给定的情况是可观察的，则可以通过布尔逻辑轻松解释条件。相比之下，在黑匣子模型中（例如，在人工神经网络中），结果可能更难以解释。
可以使用统计测试验证模型。这使我们有可能解释模型的可靠性。
即使生成数据的真实模型在某种程度上违反了它的假设，也可以表现良好。

决策树的缺点包括：

决策树模型可能会创建过于复杂的模型，从而无法很好地概括数据，导致模型泛化能力弱。这称为过度拟合。为避免此问题，必须使用诸如剪枝（当前不支持），设置叶节点处所需的最小样本数或设置树的最大深度之类的机制。
决策树可能不稳定，因为数据的微小变化可能导致生成完全不同的树。使用集成决策树可以缓解这个问题。
在多方面性能最优甚至简单概念的要求下，学习最优决策树问题都是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))

我们还可以使用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

或者，也可以使用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. 回归

决策树也可以应用于回归问题，使用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数组的列表。

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

在Face completion with a multi-output estimators中演示了使用多输出树进行分类。在本例中，输入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. 复杂度

一般来说，构建平衡二叉树的运行时间是$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_split或min_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.

https://en.wikipedia.org/wiki/Decision_tree_learning
https://en.wikipedia.org/wiki/Predictive_analytics
J.R. Quinlan. C4. 5: programs for machine learning. Morgan Kaufmann, 1993.
T. Hastie, R. Tibshirani and J. Friedman. Elements of Statistical Learning, Springer, 2009.