scikit-learn学习笔记（六）Decision Trees（决策树）

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

例如，在下面的示例中，决策树从数据中学习，以一组if-then-else决策规则近似正弦曲线。树越深，决策规则和钳工模型越复杂。

决策树的一些优点是：

简单的理解和解释。树木可视化。
需要很少的数据准备。其他技术通常需要数据归一化，需要创建虚拟变量，并删除空值。请注意，此模块不支持缺少值。
使用树的成本（即，预测数据）在用于训练树的数据点的数量上是对数的。
能够处理数字和分类数据。其他技术通常专门用于分析只有一种变量类型的数据集。有关更多信息，请参阅算法。
能够处理多输出问题。
使用白盒模型。如果给定的情况在模型中可以观察到，那么条件的解释很容易用布尔逻辑来解释。相比之下，在黑盒子模型（例如，在人造神经网络中），结果可能更难解释。
可以使用统计测试验证模型。这样可以说明模型的可靠性。
即使其假设被数据生成的真实模型有些违反，表现良好。

决策树的缺点包括：

决策树学习者可以创建不能很好地推广数据的过于复杂的树。这被称为过拟合。修剪（不支持当前）的机制，设置叶节点所需的最小样本数或设置树的最大深度是避免此问题的必要条件。
决策树可能不稳定，因为数据的小变化可能会导致完全不同的树生成。通过使用合奏中的决策树来减轻这个问题。
在最优性的几个方面甚至简单的概念中，学习最优决策树的问题已知是NP完整的。因此，实际的决策树学习算法基于启发式算法，例如在每个节点进行局部最优决策的贪心算法。这样的算法不能保证返回全局最优决策树。这可以通过在综合学习者中训练多个树木来缓解，其中特征和样本随机抽样取代。
有一些难以学习的概念，因为决策树不能很容易地表达它们，例如XOR，奇偶校验或复用器问题。
如果某些类占主导地位，决策树学习者会创造有偏见的树木。因此，建议在拟合之前平衡数据集与决策树。

分类

DecisionTreeClassifier 是能够对数据集执行多类分类的类。

与其他分类器一样，DecisionTreeClassifier将输入两个数组：数组X，稀疏或密集，大小为[n_samples，n_features]，保存训练样本，以及整数值的数组Y，大小[n_samples]，持有类标签训练样本：

>>> fromsklearn 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数据集，我们可以构造一个树，如下所示：

>>> fromsklearn.datasets importload_iris>>> fromsklearn import tree>>> iris =load_iris()>>> clf =tree.DecisionTreeClassifier()>>> clf =clf.fit(iris.data, iris.target)

经过训练，我们可以使用导出器以Graphviz格式导出树export_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

>>> importos>>> os.unlink('iris.dot')

或者，如果我们安装了Python模块pydotplus，我们可以直接在Python中生成PDF文件（或任何其他支持的文件类型）：

>>> importpydotplus >>> 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笔记本还可以使用Image（）函数内联渲染这些图：

>>> fromIPython.display importImage >>> 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预期具有浮点值而不是整数值：

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

])

复杂性

一般来说，构建平衡二叉树的运行时间成本是 $scikit-learn学习笔记（六）Decision Trees（决策树）$ 查询时间 $scikit-learn学习笔记（六）Decision Trees（决策树）$ 。虽然树构造算法试图产生平衡的树，但它们并不总是平衡的。假设子树保持近似平衡，每个节点的成本包括搜索， $scikit-learn学习笔记（六）Decision Trees（决策树）$ 以找到提供熵最大减少的特征。这 $scikit-learn学习笔记（六）Decision Trees（决策树）$ 在每个节点都有成本，从而导致整个树上的总成本（通过将每个节点的成本相加） $scikit-learn学习笔记（六）Decision Trees（决策树）$ 。

Scikit-learning为决策树的构建提供了更有效的实施。一个天真的实现（如上所述）将重新计算沿着给定特征的每个新分割点的类标签直方图（用于分类）或平均值（用于回归）。在所有相关样本上预定特征，并保留正在运行的标签数量，将降低每个节点的复杂度 $scikit-learn学习笔记（六）Decision Trees（决策树）$ ，从而导致总成本 $scikit-learn学习笔记（六）Decision Trees（决策树）$ 。这是所有基于树的算法的选项。默认情况下，它会打开梯度提升，一般来说，训练更快，但关闭所有其他算法，因为它倾向于减缓训练深度树上的训练。

实用窍门

决策树倾向于对具有大量特征的数据进行过度整合。获取正确的样本比例数量是很重要的，因为在高维空间中具有少量样本的树很可能会过度使用。
考虑事先进行降维（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非常稀疏，则在调用预测csc_matrix之前，建议在调用拟合和稀疏csr_matrix之前将其转换为稀疏。当特征在大多数样本中具有零值时，与密集矩阵相比，训练时间可以比稀疏矩阵输入快几个数量级。

树算法：ID3，C4.5，C5.0和 CART

所有各种决策树算法是什么，它们之间有什么不同？哪一个在scikit学习中实现？

ID3（Iterative Dichotomiser 3）是由罗斯奎因兰（Ros Quinlan）于1986年开发的。该算法创建一个多路树，找到每个节点（即以贪婪的方式）分类特征，这将产生分类目标的最大信息增益。树生长到最大尺寸，然后通常应用修剪步骤，以提高树的概括性来看待数据的能力。

C4.5是ID3的后继者，并通过动态定义将连续属性值分割成一组离散的间隔的离散属性（基于数字变量），消除了特征必须是分类的限制。C4.5将训练好的树（即ID3算法的输出）转换成if-then规则的集合。然后评估每个规则的这些准确性以确定应用它们的顺序。如果规则的准确性没有改善，则通过删除规则的前提条件来完成修剪。

C5.0是Quinlan根据专有许可证发布的最新版本。它使用更少的内存，并建立比C4.5更小的规则集，同时更准确。

CART（分类和回归树）与C4.5非常相似，但它不同之处在于它支持数值目标变量（回归），并且不计算规则集。CART使用在每个节点产生最大信息增益的特征和阈值来构造二叉树。

scikit-learn使用CART算法的优化版本。

数学公式

给定训练向量 $scikit-learn学习笔记（六）Decision Trees（决策树）$ i = 1，...，l和标签向量 $scikit-learn学习笔记（六）Decision Trees（决策树）$ ，决策树递归地分割空间，使得具有相同标签的样本被分组在一起。

让节点 $scikit-learn学习笔记（六）Decision Trees（决策树）$ 上的数据表示 $scikit-learn学习笔记（六）Decision Trees（决策树）$ 。对于每个候选分割 $scikit-learn学习笔记（六）Decision Trees（决策树）$ 由特征 $scikit-learn学习笔记（六）Decision Trees（决策树）$ 和阈值 $scikit-learn学习笔记（六）Decision Trees（决策树）$ ，将数据划分为 $scikit-learn学习笔记（六）Decision Trees（决策树）$ 与 $scikit-learn学习笔记（六）Decision Trees（决策树）$ 子集