页面树结构

2017-11-09 ApacheCN 开源组织,第二期邀请成员活动,一起走的更远 : http://www.apachecn.org/member/209.html


MachineLearning 优酷地址 : http://i.youku.com/apachecn

转至元数据结尾
转至元数据起始

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

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

决策树的一些优点是:

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

决策树的缺点包括:

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

 

分类 

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

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

或者,如果我们安装了Python模块pydotplus,我们可以直接在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笔记本还可以使用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])

例子:

 

多输出问题

一种多输出的问题是监督学习问题与若干输出来预测时,即当Y为大小的2D阵列。[n_samples, n_outputs]

当输出之间没有相关性时,解决这种问题的一个非常简单的方法是构建n个独立模型,即每个输出一个,然后使用这些模型来独立地预测n个输出中的每一个。然而,由于可能与相同输入相关的输出值本身相关,所以通常更好的方法是建立一个能够同时预测所有n个输出的单个模型。首先,它需要较少的训练时间,因为只建立了一个估计器。其次,所得到的估计量的泛化精度往往会增加。

关于决策树,这一策略可以很容易地用于支持多输出问题。这需要以下更改:

  • 在叶中存储n个输出值,而不是1;
  • 使用分割标准来计算所有n个输出的平均减少量。

该模块通过实现双方这一战略提供了多路输出的问题,支持DecisionTreeClassifier和 DecisionTreeRegressor。如果决策树适合大小的输出数组Y,则所得到的估计器将:[n_samples, n_outputs]

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

多输出决策树回归中演示了使用 多输出树进行回归。在这个例子中,输入X是单个实数值,输出Y是X的正弦和余弦。

使用多输出树进行分类,在使用多输出估计的Face完成中进行了演示 。在该示例中,输入X是面的上半部分的像素,并且输出Y是这些面的下半部分的像素。

参考文献:

 

复杂性

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

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

 

实用窍门

  • 决策树倾向于对具有大量特征的数据进行过度整合。获取正确的样本比例数量是很重要的,因为在高维空间中具有少量样本的树很可能会过度使用。
  • 考虑事先进行维(PCA, ICA特征选择),使您的树更好地找到具有歧视性的特征。
  • 通过使用该export 功能可视化您正在训练的树。使用max_depth=3作为初始树深度以获取树是如何配合你的数据的感觉,再增加深度。
  • 请记住,填充树的样本数量是树生长到的每个附加级别的两倍。使用max_depth控制树的大小,以防止过度拟合。
  • 使用min_samples_splitmin_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算法的优化版本。

 

数学公式

给定训练向量i = 1,...,l和标签向量 ,决策树递归地分割空间,使得具有相同标签的样本被分组在一起。

让节点米上的数据表示Q。对于每个候选分割由特征Ĵ和阈值t_m,将数据划分为 子集

在杂质米用的杂质函数被计算 ,这取决于任务的选择正在解决(分类或回归)

选择最小化杂质的参数

递归的子集,并 直至达到所允许的最大深度, 

分类标准

如果一个目标是采用值0,1,...,K-1的分类结果,对于节点米,表示R_m具有N_m 观察的区域,

是节点中k类观测的比例 米

杂质的常见措施是基尼

交叉熵

和错误分类

回归标准

如果目标是连续值,则对于米表示R_m具有N_m观测值的区域的节点,最小化的共同标准是均方误差

参考文献:

 

  • 无标签