原文章为scikit-learn中"用户指南"-->"监督学习的第十节：Decision Trees"######
决策树(Decision Trees ，DTs)是一组用于分类和回归的无参监督学习。它们的目标是创建一个模型，然后这个模型通过从数据特征学习出一套简单的决策规则后，来预测出目标值。
以下方的实例为例子，决策树从数据特征中近似地获得一条由一组** 如果...就...否则... **这样的决策规则组成的正弦曲线。随着树的深度增加，其决策规则和拟合模型就会变得越来越复杂。
决策树的优点有：
- 能够简单的解释和理解其原理，并且能够以可视化的形式来显示决策树。
- 只需要对数据进行很少的准备工作。其他技术通常需要正则化后的数据，缺失的数据则需要添加假数据或者是删除空值。不过要注意的是这个模块还不支持处理缺失的数据。
- 树的计算代价（例如预测数据）是用于训练的树中，数据点数量的对数。
- 能够同时处理数值型和连续型的数据。其他技术通常只支持一种数据类型。可以查看算法文章以获得更多的信息。
- 可以处理带有多输出的问题。
- 白盒模型。如果在模型中可以观察到特定情况，那么就可以通过简单的布尔逻辑条件来表达出这一情况。相比之下，黑盒模型（例如人造神经网络）的结果可能就不是那么容易就可以表现出来了。
- 可以使用统计测试来验证模型。这使得模型能够更具有可靠性。
- 能够良好的辨别出人造的非法数据。
然后其缺点也有：
- 决策树学习器能够为当前问题创建出一个超复杂的树，但是这个树的泛化能力却很差，这种低效的现象称之为过拟合。可以通过对叶子节点设置最小值或者是给树的深度设置最大值这样的一些"修剪机制"来避免过拟合现象(暂时还不支持直接设置，需要手动修剪)。
- 决策树是不稳定的。可能会因为一个细微的改变而产生一个完全不同的树。不过这个问题可以通过树的整体方法来缓解。(即取多个生成树的均值)
- 能否生成一个最优决策树的问题在于，不管你是需要一个在多方面都是最优的决策树，还是说仅仅只需要一个理论上最优的决策树，他都是一个NP完全问题。所以在实际使用中的决策树学习算法都是基于像启发式算法般这样的贪婪算法，使得在每个节点上都取其局部最优值。当然，使用这样的算法并不能保证产生的树是一个全局最优树，所以可以让一组训练器训练出多个树，其中训练器的特征和数据点都使用随机获取。然后再去评估这些树以选出"全局最优树"。
- 有一些概念使用决策树并不能很好的去学习，像异或，奇偶性和复用器等问题。
- 决策树学习器会在偏斜数据集（某一类的数据占了多数）中创建出一个偏斜树。所以严重建议在拟合之前对数据集进行平衡。
1.10.1. 分类#
DecisionTreeClassifier 是一个有能力从数据集产生多元分类的分类器。跟其他分类器一样，DecisionTreeClassifier需要两个输入数组：携带训练数据的稀疏或密集的数组** X ，尺寸为[样本数量, 特征数量]，和一个为X提供类标签的整数数组 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])的一个分类器。
在使用Sklearn的鸢尾花数据库上，我们可以使用下列步骤来构造出一个树：
>>> from sklearn.datasets import load_iris
>>> from sklearn import tree
>>> iris = load_iris()
>>> clf = tree.DecisionTreeClassifier()
>>> clf = clf.fit(iris.data, iris.target)
在这个模型经过训练之后，我们可以使用 export_graphviz 导出函数来将其导出成 Graphviz 格式的文件。
然后下面代码展示了如何在经过鸢尾花数据库上的树的导出：
>>> with open("iris.dot", 'w') as f:
... f = tree.export_graphviz(clf, out_file=f)
然后我们可以使用 Graphviz 的 dot 工具来创建一个PDF文件（或者是其他支持的文件格式）: dot -Tpdf iris.dot -o iris.pdf。
>>> import os
>>> os.unlink('iris.dot')
另一种方法是，如果我们已经安装了 pydotplus这个Python模块，我们可以在Python中直接生成PDF文件（或者是其他受支持的文件格式）：
>>> import pydotplus
>>> dot_data = tree.export_graphviz(clf, out_file=None)
>>> graph = pydotplus.graph_from_dot_data(dot_data)
>>> graph.write_pdf("iris.pdf")
export_graphviz导出器也支持一些"艺术性"的功能，包括为他们的分类添加颜色（或者是回归中的值）或者是突出想要显示变量 与 类名。IPython notebooks 同样能够使用 Image() 方法来渲染并在行内显示。
>>> from IPython.display import Image
>>> 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 = pydotplus.graph_from_dot_data(dot_data)
>>> Image(graph.create_png())
模型在拟合过后，这个模型就能够用来预测样本的类：
>>> clf.predict(iris.data[:1, :])
array([0])
另一种预测方法能够输出每个类的对应概率，其中这个概率指的是在同一个叶子节点中，训练样本对应各类的分数：
>>> clf.predict_proba(iris.data[:1, :])
array([[ 1., 0., 0.]])
决策树同样能够用来处理回归问题，使用DecisionTreeRegressor这个类.
跟分类中的设置一样，这个类的拟合函数也需要两个数组（** 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 个独立的模型来进行预测，即使用这些模型去预测出 n 个输出值。但是，因为这些输出值都是拥有同一个输入，所以你很难去说这些值之间是没有任何关联的，因此另一种更好的方式是去建立一个有能力同时预测出 n 个输出值的模型。
这个方法有两个优点，第一个是它只需要很少的训练时间（相比之前的 n **个模型来说），因为它只有一个估计器。然后，生成结果的泛化精度也会有所增加。
对普通的决策树来说，使用一种策略就能够容易地让它支持多输出值的问题。
只需要进行下列的改变就可以了：
- 在叶子节点中将原来只储存一个值改成存储n个输出值；
- 使用树的一些分割标准来计算所有** n **个输出值的平均减少量。
DecisionTreeClassifier 和 DecisionTreeRegressor这两个模块都内置提供了使用这种策略来处理多输出值问题。如果一个决策树在拟合一个尺寸为[样本数量, 输出值的数量]的输出数组** Y ** ，那么估计结果将会是：
- 在使用** predict **时输出 输出值的数量
- 在使用** predict_prob **时输出 一个关于类概率的输出值的数量列表。
在回归中使用多输出树的例子，可以从这篇 多输出树回归 获得参考。在这篇例子，** 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. 复杂度#
一般来说，构造一个二叉树的时间复杂度是** O(样本数量 * 特征数量 * log(样本数量)) ，然后它的查询时间是 O(log(样本数量)) 。尽管这个树的构造算法是尽量往平衡树的方向来生成的，但是在事实上一般是做不到平衡的。所以这里假设这棵树的子树已经能够近似的看成是一颗平衡树了，然后每个节点的开销则通过 O(特征数量) 搜索的组合来找出一个能够极大的降低熵的特征。因此每个节点的开销为 O(特征数量 · 样本数量 · log(样本数量)) ，然后可以导出一整棵树的开销（通过合计每个节点的开销）为 O(特征数量 · 样本数量^2 · log(样本数量)) **
Scikit-learn实现了一个更有效的来构造决策树的方法。一个原始的实现方式（也就是上面提到的那样）会为每一个新的分割点，来沿着其特征以重新计算类标签的直方图（处理分类问题）或均值（处理回归问题）。对所有的相关样本的特征进行预分类和在训练时固定类标签的数量会把决策树的每个节点的复杂度降低为** O(特征数量 · log(样本数量)) ，然后整个树的开销则变成了 O(特征数量 · 样本数量 · log(样本数量)) **。在基于树的算法里都有开启这个方法的选项。在默认情况下是设置为梯度增强，因为这样会加速训练过程，不过把它关闭或者设置成其他算法则会降低训练的速度，因为树的训练深度增加了。
1.10.5. 实用技巧#
- 在使用大量的特征时，决策树会趋向于过拟合。例如高维（特征）空间中的少量样本就通常会引起过拟合。所以设置一个合适的样本数 / 特征数的比例很重要。
- 在事先先用一些降维方法（PCA， ICA， 或 特征选择）对数据降下维，这样会使得训练出来的树会更容易找到关键点。
- 在训练的过程中使用** export 函数来可视化你的树。可以先用 max_depth=3 **的初始深度来观察树要如何你的数据，然后再视情况来修改深度。
- 要注意样本的数量，当树的深度增加一层，数据量的需求就会加倍。使用** max_depth **参数来控制树的深度以防止过拟合。
- 使用** min_samples_split 或者 min_samples_leaf 这两个参数来控制每个叶子节点上面的样本数量。小数量通常意味着树会过拟合，而太大的数量则会使得树难以从数据中进行学习。尝试 min_samples_leaf=5 作为初始值。如果样本数量的变化过于剧烈，可以对这两个参数设置百分值。这两个参数的主要区别在于 min_samples_leaf 会在每个叶子节点里保存一个最小数量的样本，而 min_samples_split 能够创建出一个很随意的用来存放样本的小节点，虽说 min_samples_split **在文献里更常见一些。
- 在进行训练之前先平衡一下你的数据集，防止树中的部分标签占据主导地位。可以通过为每一类的样本都取同样的大小来做到类平衡，又或者是把每一类的样本权重(**
sample_weight )归一化成一个统一的数值。但同时也要注意选择基于权重的预修剪方式，例如 min_weight_fraction_leaf 方法就会比在不使用样本权重的 min_samples_leaf **方法下有着更少的主导类。 - 如果样本是带有权重的，那这样使用像** min_weight_fraction_leaf **这样基于权重预修剪方法的话，会让树结构的优化过程变得简单一点，它确保了每个树节点都至少确定了一部分样本权重。
- 一般默认情况下，所有的决策树都是使用** np.float32 **数组。如果训练集不适合这个格式的话，那么则会多复制出一份转化为该格式的数据集副本。
- 如果输入的矩阵** X 非常稀疏，那就建议在对它进行拟合使用 spares.csc_matrix 函数，而在预测之前使用 spares.csr_matrix **函数进行压缩。(csc_matrix(column， 对列进行压缩) ，csr_matrix(row， 对行进行压缩))。相比于一个密集矩阵，在特征上包含许多零值的稀疏矩阵的训练时间会比前者快上几个数量级。
1.10.6. 树的各种算法：ID3，C4.5，C5.0 和 CART#
决策树究竟有哪些算法？他们之间又有什么不一样？而SKlearn又实现了哪些算法呢？
ID3（Iterative Dichotomiser 3，迭代二叉树 第3代）为罗斯·昆兰在1986年所开发的。这个算法创建了一个多叉树，并（以一种贪婪的方式）寻找每个节点上的分类特征，并为分类目标获取出最大的信息收益。一般这种算法生成的树都会"生长"到最大尺寸，所以经常需要一个修剪阶段来提高其应用在新数据上的能力。
C4.5 是 ID3 算法的后继者，它通过动态地定义离散参数（基于数值变量），将连续的属性值转化为一组间距离散来取消特征必须是分类型的这一约束条件。C4.5将经过训练的树（即经过ID3算法输出的多叉树）转化为一个"如果...即..."的规则组。然后这些规则组将会通过评估后，以确定其排序位置。如果树的准确度没有提高，那么将会通过去除一些规则来完成修剪操作。
C5.0 是昆兰根据其所有权下对该算法的最新版本。比起C4.5，它占用的内存更少，建立出的规则组规模更小，但精准度更高。
CART (Classification and Regression Trees，分类与回归树)跟 C4.5 相比很相似，但是其不同点在于它（在回归问题）支持数值的目标变量和不需要计算规则组。CART 通过在每个节点上使用特征和阈值来产生出最大的信息收益。
scikit-learn 中使用的CART算法是经过优化后的版本。
1.10.7. 数学公式#
给定一个训练向量 ** xi ∈ R^n, i = 1,..., ι ** 和 标签向量** y ∈ R^ι **，然后决策树递归地分割这两组空间，使得拥有相同标签的向量组组合在一起。
然后让** m 点上的数据用 Q 表示。对每一个候选组 θ = (j, t_m) 关联一个特征 j 和阈值 t_m ，然后将原来的数据 Q 分割为 Q_left(θ) 和 Q_right(θ) **两个子集。
不纯度** m 则通过不纯度函数 H() **来计算出，而这一函数取决于要解决的任务来决定（分类或回归）
然后最小化不纯度的参数
然后对** Q_left(θ) 和 Q_right(θ) 递归这一过程，至到到达最大深度，N_m < min_samples** 或 ** N_m = 1**。
1.10.7.1. 分类标准##
如果目标是一个在取值为[0, K-1]的分类型输出，则在节点** m 上，可以表示在区域 R_m 上有 N_m **个观测值，使得
为** k 类在节点 m **中与观测值的比例。
然后常见的计算不纯度的方法有：基尼
交叉熵
和 错分类
1.10.7.2. 回归标准##
如果目标是一个连续值，那么在节点** m 上，可以表示在区域 R_m 里有 N_m **个观测值，然后常见的最小化方式是使用均方误差
引用
- https://en.wikipedia.org/wiki/Decision_tree_learning
- https://en.wikipedia.org/wiki/Predictive_analytics
- L. Breiman, J. Friedman, R. Olshen, and C. Stone. Classification and Regression Trees. Wadsworth, Belmont, CA, 1984.
- 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.
（在尝试翻译这篇文档的时候难免会因为各种问题而出现错翻，如果发现的话，烦请指出，谢谢> <）
