决策树

关键词：

第5章 决策树

决策树(decision tree)是一种基本的分类与回归方法。本章主要讨论用于分类的决策树。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性，分类速度快。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新的数据，利用决策树模型进行分类。决策树学习通常包括3个步骤：特征选择、决策树的生成和决策树的修剪。

5.1 决策树模型与学习

定义5.1 (决策树) ：分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点(node)和有向边(directed edge)组成。结点有两种类型：内部结点(internal node )和叶结点(leaf node)。内部结点表示一个特征或属性，叶结点表示一个类。

用决策树分类，从根结点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分到叶结点的类中。

图中圆和方框分别表示内部结点和叶结点.

决策树与if-then规则

可以将决策树看成一个if-then规则的集合，转换成if-then规则的过程：由决策树的根结点到叶结点的每一条路径构建一条规则；路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥并且完备，每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。这里所谓覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。

决策树与条件概率分布

决策树还表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分(partition)上，将特征空间划分为互不相交的单元(cell)或区域(region)，并在每个单元定义一个类的概率分布就构成了一个条件概率分布。

决策树的一条路径对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。条件概率分布可以表示为P(Y|X)，X取值于给定划分下单元的集合，Y取值于类的集合。各叶结点(单元)上的条件概率往往偏向某一个类，即属于某一类的概率较大。决策树分类时将该结点的实例强行分到条件概率大的那一类去。

决策树学习

决策树学习本质上是从训练数据集中归纳出一组分类规则。可能有多个，可能没有。我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。

从另一个角度看，决策树学习是由训练数据集估计条件概率模型。基于特征空间划分的类的条件概率模型有无穷多个。我们选择的条件概率模型应该不仅对训练数据有很好的拟合，而且对未知数据有很好的预测。

决策树学习的损失函数：通常是正则化的极大似然函数

决策树学习的策略：是以损失函数为目标函数的最小化

因为从所有可能的决策树中选取最优决策树是NP完全问题，所以现实中决策树学习算法通常采用启发式方法，近似求解这一最优化问题，得到的决策树是次最优(sub-optimal)的。

决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。

剪枝：决策树可能对训练数据有很好的分类能力，但可能发生过拟合现象.。所以需要对已生成的树自下而上进行剪枝，将树变得更简单，从而使它具有更好的泛化能力。具体地，就是去掉过于细分的叶结点，使其回退到父结点，甚至更高的结点，然后将父结点或更高的结点改为新的叶结点.

特征选择：如果特征数量很多，在决策树学习开始时对特征进行选择，只留下对训练数据有足够分类能力的特征。

由于决策树表示一个条件概率分布，所以深浅不同的决策树对应着不同复杂度的概率模型。决策树的生成对应模型的局部选择，决策树的剪枝对应于模型的全局选择。决策树的生成只考虑局部最优，决策树的剪枝则考虑全局最优。

5.2 特征选择

特征选择问题：特征选择在于选取对训练数据具有分类能力的特征。通常特征选择的准则是信息增益或信息增益比。

设有随机变量(X,Y)，其联合概率分布为：

条件嫡H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件嫡(conditional entropy) H(Y|X)，定义为X给定条件下Y的条件概率分布的嫡对X的数学期望：

当嫡和条件嫡中的概率由数据估计(特别是极大似然估计)得到时，所对应的嫡与条件嫡分别称为经验熵( empirical entropy)和经验条件嫡(empirical conditional entropy )。

信息增益(information gain)表示得知特征X的信息而使得类Y的信息的不确定性减少的程度.

定义5.2(信息增益)：特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验嫡H(D)与特征A给定条件下D的经验条件嫡H(D|A)之差，即

决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

根据信息增益准则的特征选择方法是：对训练数据集(或子集)D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。

|D|表示其样本容量，即样本个数。设有K个类C_k，k=1,2,...,K，|C_k|为属于类C_k的样本个数。根据特征A的取值将D划分为n个子集D₁,D₂,...,D_n,|D_i|为D_i的样本个数。记子集D_i中属于类C_k的样本的集合为D_ik。

信息增益值的大小是相对于训练数据集而言的，并没有绝对意义。在分类问题困难时，也就是说在训练数据集的经验嫡大的时候，信息增益值会偏大，反之，信息增益值会偏小。

定义5.3 信息增益比：特征A对训练数据集D的信息增益比g_R(D,A)定义为其信息增益g(D,A)与训练数据集D的经验H(D)之比:

5.3 决策树的生成

ID3算法: ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征。

ID3算法只有树的生成，所以该算法生成的树容易产生过拟合

C4.5算法：与ID3算法相似，不同是用信息增益比来选择特征。

5.4 决策树的剪枝

决策树的生成算法容易构建过于复杂的决策树，产生过拟合。、

决策树的剪枝：在决策树学习中将已生成的树进行简化的过程称为剪枝(pruning)。具体地，剪枝从已生成的树上裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型.

决策树的剪枝往往通过极小化决策树整体的损失函数(loss fimction)或代价函数( cost function)来实现。

设树T的叶结点个数为|T|, t是树T的叶结点，该叶结点有N_t个样本点，其中k类的样本点有N_tk个，k=1,2,...,K，H_t(T)为叶结点t上的经验嫡，a>=0为参数，则决策树学习的损失函数可以定义为

C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，|T|表示平莫型复杂度，参数a>=0控制两者之间的影响。剪枝，就是当a确定时，选择损失函数最小的模型，即损失函数最小的子树。损失函数正好表示了对模型的复杂度和训练数据的拟合两者的平衡。

决策树生成只考虑了通过提高信息增益(或信息增益比)对训练数据进行更好的拟合，学习局部的模型；

决策树剪枝通过优化损失函数还考虑了减小模型复杂度，学习整体的模型。

利用损失函数最小原则进行剪枝就是用正则化的极大似然估计进行模型选择。

      

5.5  CART算法

分类与回归树(classification and regression tree, CART)模型同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。  CART算法由以下两步组成

    (1)决策树生成：基于训练数据集生成决策树，牛成的决策树要尽量大；

    (2)决策树剪枝：用验证数据集对己生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

CART生成：对回归树用平方误差最小化准则，对分类树用基尼指数(Gini index)最小化准则，进行特征选择。

回归树的生成：

分类树的生成

分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点.

定义5.4(基尼指数)：分类问题中，假设有K个类，样本点属于第k类的概率为p_k，则概率分布的基尼指数定义为

对于给定的样本集合D，其基尼指数为

如果样本集合D根据特征A是否取某一可能值a被分割成D1和D2两部分，则在特征A的条件下，集合D的基尼指数定义为

CART剪枝

CART剪枝算法由两步组成首先从生成算法产生的决策树T₀底端开始不断剪枝，直到T₀的根结点，形成一个子树序列代｛T_0,T₁,...,T_n｝；然后通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树。

(1) 剪枝。形成一个子树序列

在剪枝过程中，计算子树的损失函数:

可以用递归的方法对树进行剪枝，将a从小增大，a₀<a₁<...<a_n<+无穷，产生一系列的区间[a_i，a_i+1)，i =0,1,...,n；剪枝得到的子树序列对应着区间[a_i，a_i+1)，i =0,1,...,n的最优子树序列{T_0, T_{1, ... ,} Tn}，序列中的子树是嵌套的。

对T₀中每一内部结点t，计算

表示剪枝后整体损失函数减少的程度，在T₀中剪去g(t)最小的T_t，将得到的子树作为T₁，同时将最小的g(t)设为a_1，T₁为区间[a_1，a₂)的最优子树。如此剪枝下去，直至得到根结点。在这一过程中，不断地增加a的值，产生新的区间。

(2) 在剪枝得到的子树序列T_0, T_{1, ... ,} T_n中通过交叉验证选取最优子树T_a

具体地，利用独立的验证数据集，测试子树序列T_0, T_{1, ... ,} T_n中各棵子树的平方误差或基尼指数。平方误差或基尼指数最小的决策树被认为是最优的决策树。在子树序列中，每棵子树T_0, T_{1, ... ,} T_n都对应于一个参数a₀, a₁, ... , a_n。所以，当

最优子树T_k确定时，对应的a_k也确定了，即得到最优决策树T_a。

一文看懂决策树

 决策树是一种逻辑简单的机器学习算法，它是一种树形结构，所以叫决策树。本文将介绍决策树的基本概念、决策树学习的3个步骤、3种典型的决策树算法、决策树的10个优缺点。什么是决策树？决策树是一种解决分类问题... 查看详情

统计学习方法　李航　决策树

决策树一.决策树基本描述决策树是一种基本的分类与回归方法,呈树形结构,在分类问题中,表示基于特征对实例进行分类的过程.学习时,利用训练数据根据损失函数最小化的原则建立决策树模型.预测时,对新的数据,利用决策树模型... 查看详情

机器学习决策树

1、决策树简介1.1决策树概述决策树算法是一种基于树形结构的分类算法，它能从给定的无序的训练样本中，提炼出树型的分类模型，树形中包含判断模块和终止模块。它是一种典型的分类算法，首先对数据进行处理，利用归纳... 查看详情

大数据项目8（sklearn决策树）

决策树一、了解什么是决策树二、决策树模型三、决策树-信息增益四、信息增益比五、ID3算法六、决策树的剪枝一、了解什么是决策树分类分类树：分类标签值（天气？是否垃圾网页？）定性决策树：定... 查看详情

决策树

第5章决策树决策树(decisiontree)是一种基本的分类与回归方法。本章主要讨论用于分类的决策树。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合，也可以认为是定义... 查看详情

决策树 - 决策树如何在每个节点上选择规则

】决策树-决策树如何在每个节点上选择规则【英文标题】：DecisionTree-Howdoesdecisiontreeselectrulesoneachnode【发布时间】：2019-01-2808:16:16【问题描述】：我正在学习机器学习中的决策树算法我可以从教程中了解到，决策树在每个节点上... 查看详情

决策树（回归树）分析及应用建模

一、CART决策树模型概述（ClassificationAndRegressionTrees）    决策树是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得到什么值的类似规则的方法。??决策树算法属于有指导的学习，即原数据必须... 查看详情

机器学习算法之决策树（上）

信息熵决策树决策树优化剪枝决策树可视化决策树直观理解比特化(Bits) 查看详情

决策树的剪枝

决策树算法原理(ID3，C4.5)决策树算法原理(CART分类树)CART回归树 　　决策树的剪枝是通过极小化决策树整体的损失函数。(决策树的生成只考虑局部最优，决策树的剪枝考虑全局最优)　　设树T的叶节点为t，个数为|T|，该叶节... 查看详情

决策树

决策树原理对一系列问题进行if/else推导，最终实现决策决策树构建#导入numpyimportnumpyasnp#导入画图工具importmatplotlib.pyplotaspltfrommatplotlib.colorsimportListedColormap#导入树模型和数据集加载工具fromsklearnimporttree,datasets#导入数据集拆分工... 查看详情

雪饮者决策树系列决策树应用

　　本篇以信息增益最大作为最优化策略来详细介绍决策树的决策流程。　　首先给定数据集，见下图　　注：本数据来源于网络本篇将以这些数据作为训练数据（虽然少，但足以介绍清楚原理！），下图是决策树选择特征的流... 查看详情

构建决策树

构建决策树决策树信息熵划分基尼系数划分调用CART 决策树决策树，是通过数据归纳，总结出条件判断的学习模式。如果新来一位男生/客户/面试者，根据上面的树状图就可以作出是否见面/贷款/入职的决定，所以... 查看详情

决策树学习笔记（decisiontree）

　什么是决策树？　　决策树是一种基本的分类与回归方法。其主要有点事模型具有可得性，分类速度快。学习时，利用训练数据，根据损失函数最小化原则建立决策树模型；预测时，对新数据，利用决策树模型进行分类。　决... 查看详情

机器学习笔记-决策树

决策树(DecisionTree)决策树学习，建立一颗树结构的模型。此模型由一系列逻辑决策构成。在此结构中决策点代表某个属性上的决策，分支表示决策选择项，树的叶子节点是一系列联合决策的结论。决策树通过分而治之（Divideandconq... 查看详情

ml:决策树算法

...sp;在众多的分类模型中，应用最为广泛的两种分类模型是决策树模型(DecisionTreeModel)和朴素贝叶斯模型（NaiveBayesianModel，NBC）。决策树模型通过构造树来解决分类问题。首先利用训练数据集来构造一棵决策树，一旦树建立起来，... 查看详情

数据结构-决策树(分类)

数据结构-决策树一决策树的介绍二决策树的构造使用决策树做预测需要以下过程：1.信息熵2.条件熵(ConditionalEntropy)与信息增益（InformationGain）3.信息增益做特征选择的优缺点4.信息增益比(InfomationGainRatio)5.Gini系数一决... 查看详情

决策树

决策树（DTS）是一个非参数监督学习用于方法分类和回归。我们的目标是创建一个预测通过学习从数据推断出功能简单的决策规则的目标变量的值的典范。例如，在下面的例子中，决策树从数据学习来近似正弦曲线与一组，如果... 查看详情

C++ 决策树存储

】C++决策树存储【英文标题】：C++decisiontreestorage【发布时间】：2013-05-1918:36:51【问题描述】：我有一个决策树。我给这个决策树提供了一些输入值。然后决策树返回一个值。输入值可以是“孩子的数量”、“年龄”等。然后，... 查看详情