第5章决策树
决策树是一种基于规则的方法，它用一组嵌套的规则进行预测。在树的每个决策节点处，根据判断结果进入一个分支，反复执行这种操作直到到达叶子节点，得到预测结果。这些规则通过训练得到，而不是人工制定的。
5.1树形决策过程
首先看一个简单的例子。银行要确定是否给客户发放贷款，为此需要考察客户的收入与房产情况。在做决策之前，会先获取客户的这两个数据。如果把这个决策看作分类问题，两个指标就是特征向量的两个分量，分类的类别标签是可以贷款和不能贷款。银行按照下面的过程进行决策：
1.首先判断客户的年收入指标。如果大于20万，可以贷款；否则继续判断。
2.然后判断客户是否有房产。如果有房产，可以贷款；否则不能贷款。
用图形表示这个过程就是一棵决策树。决策过程从树的根节点开始，在内部节点处需要做判断，直到到达一个叶子节点处，得到决策结果。决策树由一系列分层嵌套的判定规则组成，是一个递归的结构。这个例子的决策树如下图5.1所示：
图5.1决策树的一个例子
收入为数值型特征，可以比较大小，这种特征为整数或小数。房产情况为类别型特征，取值为有房产和没有房产两种情况，这种特征不能比较大小。上图中决策树所有的内部节点为矩形，叶子节点即决策结果为椭圆形。
为便于用程序实现，一般将决策树设计成二叉树。与树的叶子节点、非叶子节点相对应，决策树的节点分为两种类型：
决策节点。在这些节点处需要进行判断以决定进入哪个分支，如用一个特征和设定的阈值进行比较。决策节点一定有两个子节点，它是非叶子节点。
叶子节点。表示最终的决策结果，它们没有子节点。在上面的例子中，叶子节点的值有两种，即能贷款和不能贷款。对于分类问题，叶子节点中存储的是类别标签。
决策树是一个分层结构，可以为每个节点赋予一个层次数。根节点的层次数为0，子节点的层次数为父节点层次数加1。树的深度定义为所有节点的最大层次数。上图决策树的深度为2，要得到一个决策结果最多经过2次判定。
典型的决策树有ID3[1]，C4.5[3]，CART（Classification and Regression Tree，分类与回
归树）[4]等，它们的区别在于树的结构与构造算法。分类与回归树既支持分类问题，也可用于回归问题。决策树是一种判别模型，天然支持多类分类问题。限于篇幅，本章只介绍分类与回归树。
分类树的映射函数是多维空间的分段线性划分，即用平行于各坐标轴的超平面对空间进行切分；回归树的映射函数是分段常数函数。决策树是分段线性函数而不是线性函数，它具有非线性建模的能力。只要划分的足够细，分段常数函数可以逼近闭区间上任意函数到任意指定精度，因此决策树在理论上可以对任意复杂度的数据进行拟合。对于分类问题，如果决策树深度够大，它可以将训练样本集的所有样本正确分类。但如果特征向量维数过高，可能会面临维数灾难导致准确率下降，维数灾难的概念将在第14章介绍。
下图5.2是决策树对空间划分的一个例子。这里有红色和蓝色两类训练样本，用下面两条平行于坐标轴的直线可以将这两类样本分开：
图5.2决策树对空间的划分
这个划分方案对应的决策树如下图5.3所示：
图5.3分类树
5.2分类与回归树
下面介绍分类与回归树的原理，它是二叉决策树。预测时从根节点开始，每次只对一个特征进行判定然后进入左子节点或者右子节点，直至到达一个叶子节点处，得到类别值或回归函数值。预测算法的时间复杂度与树的深度有关，判定的执行次数不超过决策树的深度。
5.3训练算法
现在要解决的关键问题是如何用训练样本建立决策树。无论是分类问题还是回归问题，决策树都要尽可能的对训练样本进行正确的预测。直观的想法是从根节点开始构造，递归的用训练样本集建立起决策树，这棵树能够将训练集正确的分类，或者对训练集的回归误差最小化。为此要解决以下问题：
特征向量有多个分量，每个决策节点上应该选择哪个分量做判定？这个判定会将训练样本集一分为二，然后用这两个子集构造左右子树。
在选定一个特征后，判定的规则是什么？即满足什么条件时进入左子树分支。对数值型变量要寻找一个分裂阈值进行判断，小于该阈值进入左子树，否则进入右子树。对于类别型变量则需要为它确定一个子集划分，将特征的取值集合划分成两个不相交的子集，如果特征的值属于第一个子集则进入左子树，否则进入右子树。
何时停止分裂，把节点设置为叶子节点？对于分类问题，当节点的样本都属于同一类型时停止，但这样可能会导致树的节点过多、深度过大，产生过拟合问题。另一种方法是当节点中的样本数小于一个阀值时停止分裂。
如何为每个叶节点赋予类别标签或者回归值？即到达叶子节点时样本被分为哪一类或者赋予一个什么实数值。
下面给出这几个问题的答案。特征有数值型变量和类别型变量两种情况，决策树有分类树和回归树两种类型，组合起来一共有4种情况。数值型变量是指能够比较大小的变量，如年龄，速度；类别型变量是整数编码，不能比较大小，如各种类型的动物。限于篇幅，我们
只对数值型变量进行介绍。
5.3.1递归分裂过程
训练算法是一个递归的过程。首先创建根节点，然后递归的建立左子树和右子树。如果练样本集为D ，训练算法的整体流程为：
1.用样本集D 建立根节点，找到一个判定规则，将样本集分裂成1D 和2D 两部分，同时为根节点设置判定规则。
2.用样本集1D 递归建立左子树。
3.用样本集2D 递归建立右子树。
4.如果不能再进行分裂，则把节点标记为叶子节点，同时为它赋值。
在确定这个递归流程之后，接下来要解决的核心问题是怎样对训练样本集进行分裂。
5.3.2寻找最佳分裂
训练时需要找到一个分裂规则把训练样本集分裂成两个子集，因此要确定分裂的评价标准，根据它寻找最佳分裂。对于分类问题，要保证分裂之后左右子树的样本尽可能的纯，即它们的样本尽可能属于不相交的某一类或者几类。为此需要定义不纯度的指标：当样本都属于某一类时不纯度为0；当样本均匀的属于所有类时不纯度最大。满足这个条件的有熵不纯度，Gini 不纯度，以及误分类不纯度等，下面分别进行介绍。
不纯度指标用样本集中每类样本出现的概率值构造。因此首先要计算每个类出现的概率，这通过训练样本集中每类样本数除以样本总数得到：
i i N p N
=其中i N 是第i 类样本数，N 为总样本数。根据这个概率值可以定义各种不纯度指标，下面分别介绍。
样本集D 的熵不纯度定义为：
()2log i i
i
E D p p =-∑熵是信息论中的一个重要概念，用来度量一组数据包含的信息量大小。当样本只属于某一类时熵最小，当样本均匀的分布于所有类中时熵最大。因此，如果能找到一个分裂让熵最小，这就是我们想要的最佳分裂。
样本集的Gini 不纯度定义为：
()2
1i i
G D p =-∑当样本属于某一类时Gini 不纯度的值最小，此时最小值为0；当样本均匀的分布与每一类时Gini 不纯度的值最大。这源自于如下的数学结论，在下面的约束条件下：
1
i i i p
p =≥∑对于如下目标函数：
2i
i p
∑所有变量相等时它有极小值，只有一个变量为1其他变量为0时该函数有极大值，这对应于Gini 不纯度的极小值。这一结论可以通过拉格朗日乘数法证明。即所有样本都来自同一类时Gini 不纯度的值最小，样本均匀的属于每一类时Gini 不纯度的值最大。将类概率的计算公式代入Gini 不纯度的定义，可以得到简化的计算公式：
()()222211/1/i i i i i i G D p
N N N N =-=-=-?? ???
∑∑∑样本集的误分类不纯度定义为：
()()
1max i E D p =-之所以这样定义是因为我们会把样本判定为频率最大的那一类，因此其他样本都会被错分，故错误分类率为上面的值。和上面的两个指标一样，当样本只属于某一类时误分类不纯度有最小值0，样本均匀的属于每一类时该值最大。
上面定义的是样本集的不纯度，我们需要评价的是分裂的好坏，因此需要根据样本集的不纯度构造出分裂的不纯度。分裂规则将节点的训练样本集分裂成左右两个子集，分裂的目标是把数据分成两部分之后这两个子集都尽可能的纯，因此我们计算左右子集的不纯度之和作为分裂的不纯度，显然求和需要加上权重，以反映左右两边的训练样本数。由此得到分裂的不纯度计算公式为：
()()
L
R L R N N G G D G D N N =+其中()L G D 是左子集的不纯度，()R G D 是右子集的不纯度，N 是总样本数，L N 是左子
集的样本数，R N 是右子集的样本数。
如果采用Gini 不纯度指标，将Gini 不纯度的计算公式代入上式可以得到：
22,,2222,,22,,111 1 1L i R i i
i L R L R L i R i i i L R L R L i R i i i
L R N N N N G N N N N N N N N N N N N N N N N =-+-=-+-=-+???? ? ? ?????
?? ? ???
?? ? ???
∑∑∑∑∑∑其中,L i N 是左子节点中第i 类样本数，,R i N 是右子节点中第i 类样本数。由于N 是常数，要让Gini 不纯度最小化等价于让下面的值最大化：
22,,L i
R i i i L R
N N G N N =+∑∑这个值可以看做是Gini 纯度，它的值越大，样本越纯。寻找最佳分裂时需要计算用每
个阈值对样本集进行分裂后的这个值，寻找该值最大时对应的分裂，它就是最佳分裂。这比直接按照Gini 系数的定义计算的计算量更小，避免了大量的浮点数运算。如果是数值型特征，对于每个特征将l 个训练样本按照该特征的值从小到大排序，假设排序后的值为：
1,...,l
x x 接下来从1x 开始，依次用每个i x 作为阈值，将样本分成左右两部分，计算上面的纯度值，该值最大的那个分裂阈值就是此特征的最佳分裂阈值。在计算出每个特征的最佳分裂阈值和上面的纯度值后，比较所有这些分裂的纯度值大小，该值最大的分裂为所有特征的最佳分裂。这里采用了贪心法的策略，每次都是选择当前条件下最好的分裂作为当前节点的分裂。对单个变量寻找最佳分裂阈值的过程如下图5.4
所示：
图5.4为数值型变量寻找最佳分裂阈值
对于回归树，衡量分裂的标准是回归误差即样本方差，每次分裂时选用使得方差最小化的那个分裂。假设节点的训练样本集有l 个样本(),i i y x ，其中i x 为特征向量，i y 为实数的标签值。节点的回归值为所有样本的均值，回归误差为所有样本的标签值与回归值的均方和误差，定义为：
()()2
11l i i E D y y l ==-∑可以证明，回归值为均值的时候，上面的均方误差最小。把均值的定义带入上式，得到：
()211222111222111221111111 2121 11 l
l i j i j l l l i i j j i j j l l l i i j i i j l l i i i i E D y y l l y y y y l l l y y y l l l y y l l ==========??=- ??????? ?=-+ ? ?????
?????? ?=-+ ? ? ??????
?????=- ? ? ?????
∑∑∑∑∑∑∑∑∑∑根据样本集的回归误差，我们同样可以构造出分裂的回归误差。分裂的目标是最大程度的减小回归误差，因此把分裂的误差指标定义为分裂之前的回归误差减去分裂之后左右子树的回归误差：
()()()L R L R N N E E D E D E D N N
=--
将误差的计算公式代入上式，可以得到：
22221111221122
2111111111 1111 L L R R L R N N N N L i i i i i i i i L L N N R i i i i R R N N N i i i i i i L R N E y y y y N N N N N N y y N N N y y y N N N N =========?????????? ? ?=---- ? ? ? ? ? ??????????
??????? ? ?- ? ? ??????
?????=-++ ? ?????∑∑∑∑∑∑∑∑∑2???? ? ? ?????由于N 和2
211N i i y N =??- ???
∑是常数，要让上式最大化等价于让下式最大化：221111L R N N i i i i L R E y y N N ==????=+ ? ?????∑∑寻找最佳分裂时要计算上面的值，让该值最大化的分裂就是最佳分裂。回归树对类别型特征的处理和分类树类似，只是E 值的计算公式不同，其他的过程相同。
5.3.3叶子节点值的设定
如果不能继续分裂，则将该节点设置为叶子节点。对于分类树，将叶子节点的值设置成本节点的训练样本集中出现概率最大的那个类；对于回归树，则设置为本节点训练样本标签值的均值。
5.3.4属性缺失问题
在某些情况下样本特征向量中一些分量没有值，这称为属性缺失。例如晚上我们无法观察到物体的颜色值，颜色属性就缺失了。在决策树的训练过程中，寻找最佳分裂时如果某一个属性上有些样本有属性缺失，可以把这些缺失该属性的样本剔除掉，然后照常训练，这是最简单的做法。
此外还可以使用替代分裂规则。对于每个决策树节点除了计算出一个最佳分裂规则作为主分裂规则，还会生成一个或者多个替代分裂规则作为备选。在预测时如果主分裂规则对应的特征出现缺失，则使用替代分裂规则进行判定。
现在的关键问题是怎样生成替代分裂规则。其目标是对训练样本的分裂结果要和主分裂尽可能接近，即被主分裂分到左边的样本要尽量被替代分裂分到左边；被主分裂分到右边的样本要尽量被替代分裂分到右边。主分裂和替代分裂对所有训练样本的分裂结果有4种情况，分别是：
LL,LR,RL,RR
LL 表示被主分裂、替代分裂都分到了左子树的样本数。LR 表示被主分裂分到了左子树，被替代分裂分到了右子树的样本数。RL 表示被主分裂分到了右子树，被替代分裂分到了左子树的样本数。RR 表示被主分裂和替代分裂都分到了右子树的样本数。
因此LL+RR 是主分裂和替代分裂的结果一致的样本数，LR+RL 是主分裂和替代分裂的结果不一致的样本数。由于可以将左右子树反过来，因此给定一个特征分量，在寻找替代分裂的分裂阈值时要让LL+RR 或者LR+RL 最大化，最后取它们的最大值：
()
max LL RR,LR RL ++该值对应的分裂阈值为替代分裂的分裂阈值。对于除最佳分裂所用特征之外的其他所有特征，都找出该特征的最佳分裂和上面的值。最后取该值最大的那个特征和分裂阈值作为替代分裂规则。
对单个特征寻找替代分裂阈值的处理流程如下：
1.对于每个特征将l 个训练样本按照该特征的值从小到大排序，假设排序后的值为：
1,...,l
x x 接下来从1x 开始，依次用每个i x 作为阈值，将样本分成左右两部分，同时用主分裂对这些样本进行预测，得到LL,LR,RL,RR 的值。
2.将LL RR,LR RL ++分别与它们的最大值比较，如果大于最大值，则更新最大值。3返回()max LL RR,LR RL ++对于的分裂阈值。
这一过程类似于寻找最佳分裂，但采用了不同的评价指标。得到每个特征分量的最佳分裂阈值以及()max LL RR,LR RL ++之后，比较各个特征的()max LL RR,LR RL ++值，取该值最大的那个特征作为替代分裂特征，对应的阈值作为替代分裂阈值。
5.3.5剪枝算法
如果决策树的结构过于复杂，可能会导致过拟合问题。此时需要对树进行剪枝，消掉某些节点让它变得更简单。剪枝的关键问题是确定减掉哪些树节点以及减掉它们之后如何进行节点合并。决策树的剪枝算法可以分为两类，分别称为预剪枝和后剪枝。前者在树的训练过程中通过停止分裂对树的规模进行限制；后者先构造出一棵完整的树，然后通过某种规则消除掉部分节点，用叶子节点替代。
预剪枝可以通过限定树的高度，节点的训练样本数，分裂所带来的纯度提升的最小值来来实现，具体做法在前面已经讲述，在源代码分析中会介绍实现细节。后剪枝的典型实现有降低错误剪枝（Reduced-Error Pruning ，简称REP ）、悲观错误剪枝（Pesimistic-Error Pruning ，简称PEP ）、代价-复杂度剪枝（Cost-Complexity Pruning ，简称CCP ）[5]等方案。分类与回归树采用的是代价-复杂度剪枝算法，下面重点介绍它的原理。
代价是指剪枝后导致的错误率的变化值，复杂度是指决策树的规模。训练出一棵决策树之后，剪枝算法首先计算该决策树每个非叶子节点的α值，它是代价与复杂度的比值。该值定义为：()()
1
t t E n E n n α-=-其中()E n 是节点n 的错误率，()t E n 是以节点n 为根的子树的错误率，t n 为子树的叶子节点数，即复杂度。α值是用树的复杂度归一化之后的错误率增加值，即将整个子树剪掉之后用一个叶子节点替代，相对于原来的子树错误率的增加值。该值越小，剪枝之后树的分类效果和剪枝之前越接近。上面的定义依赖于节点的错误率指标，下面对分类问题和回归问题介绍它的计算公式。对于分类问题，错误率定义为：
()()
max i N N E n N
-=其中N 是节点的总样本数，i N 是第i 类样本数，这就是之前定义的误分类指标。对于回归问题，错误率为节点样本集的均方误差：
()()2211i i i i E n y y N N ????=- ? ? ?????
∑∑子树的错误率为树的所叶子节点错误率之和。计算出α值之后，剪掉该值最小的节点得到剪枝后的树，然后重复这种操作直到剩下根节点，由此得到一个决策树序列：
0,...,m
T T 其中0T 是初始训练得到的决策树，1i T +在i T 的基础上剪枝得到的，即剪掉i T 中α值最小的那个节点为根的子树用一个叶子节点替代后得到的树。
整个剪枝算法分为两步完成：
第一步先训练出0T ，然后用上面的方法逐步剪掉树的所有非叶子节点，直到只剩下根节点，得到剪枝后的树序列。这一步的误差计算采用的是训练样本集。
第二步根据真实误差值从上面的树序列中挑选出一棵树作为剪枝后的结果。这可以通过交叉验证实现，用交叉验证的测试集对上一步得到的树序列的每一棵树进行测试，得到这些树的错误率，然后根据错误率选择最佳的树作为剪枝后的结果。
5.3.6训练算法的流程
下面给出决策树完整的训练算法。算法的输入为训练样本集，输出为训练得到的树。训练算法TrainDecisionTree 的流程为
TrainDecisionTree(D)
if (样本集无法再分裂或达到最大树深度或D 的样本数小于指定阈值)
leafNode =CalcLeafValue(D);//无法再分裂，设置为叶子节点，计算其值
return leafNode;//返回创建的叶子节点
else
(split,D1,D2)=FindBestSplit(D);//寻找最佳分裂split ，将训练集D 分为D1和D2node =CreteTreeNode();//创建当前节点
node->split =split;//设置节点的分裂规则
FinSurrogateSplit(D);//寻找替代分裂，加入到节点的分裂规则列表
node->leftChild =TrainDecisionTree(D1);//递归训练左子树
node->rightChild =TrainDecisionTree(D2);//递归训练右子树
return node;//泛化训练的树节点的
end if
如果需要做后剪枝处理，训练结束之后还要调用剪枝函数。
5.3.7计算变量的重要性
决策树可以输出特征分量的重要性，即每个特征分量对分类或回归的作用大小。计算方
法为对每个特征分量在整个决策树中的分裂质量累加求和。对于分类树，分裂质量是Gini 纯度值，即5.3.2节中定义的G 值；对于回归树，分裂质量是每次分裂时回归误差的下降值，即5.3.2节中定义的E 值。假设第i 个特征分量的分裂质量之和为i q ，然后对所有特征分量求和后分裂质量进行归一化
1
i
n i i q q
=∑这个值即为该特征分量的重要性。其中n 为特征向量的维数。显然该值越大变量越重要。统计所有节点的分裂质量需要对树进行遍历，可以使用任何一种遍历算法。这样做的依据是，如果一个变量被选来做分裂则说明它对分类或者回归很重要，如果它做分裂时的分裂质量很大，说明其对分类或者回归的贡献很大。
5.4实验程序
下面通过实验程序介绍决策树的使用。程序基于sklearn ，使用iris 数据集。具体做法与第4.4节相同。训练决策树时需要指定一些参数，包括分裂质量的度量指标，决策树的最大深度，允许分裂的最小训练样本数等。这里使用了默认的参数。程序源代码如下
import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn import tree
import matplotlib
%matplotlib inline
#生成所有测试样本点
def make_meshgrid(x,y,h=.02):
x_min,x_max =x.min()-1,x.max()+1
y_min,y_max =y.min()-1,y.max()+1
xx,yy =np.meshgrid(np.arange(x_min,x_max,h),
np.arange(y_min,y_max,h))
return xx,yy
#对测试样本进行预测，并显示
def plot_test_results(ax,clf,xx,yy,**params):
Z =clf.predict(np.c_[xx.ravel(),yy.ravel()])
Z =Z.reshape(xx.shape)
ax.contourf(xx,yy,Z,**params)
#载入iris 数据集
iris =datasets.load_iris()
#只使用前面连个特征
X =iris.data[:,:2]
#样本标签值
y=iris.target
#创建并训练决策树
clf=tree.DecisionTreeClassifier()
clf.fit(X,y)
title=('DecisionTreeClassifier')
fig,ax=plt.subplots(figsize=(5,5))
plt.subplots_adjust(wspace=0.4,hspace=0.4)
X0,X1=X[:,0],X[:,1]
#生成所有测试样本点
xx,yy=make_meshgrid(X0,X1)
#显示测试样本的分类结果
plot_test_results(ax,clf,xx,yy,cmap=plt.cm.coolwarm,alpha=0.8) #显示训练样本
ax.scatter(X0,X1,c=y,cmap=plt.cm.coolwarm,s=20,edgecolors='k') ax.set_xlim(xx.min(),xx.max())
ax.set_ylim(yy.min(),yy.max())
ax.set_xlabel('x1')
ax.set_ylabel('x2')
ax.set_xticks(())
ax.set_yticks(())
ax.set_title(title)
plt.show()
程序的运行结果如下图5.5所示。
图5.5决策树对iris数据集的分类结果
上图5.5中的分类决策线为直线段，这也证明了决策树是分段线性函数。
5.5应用
决策树具有实现简单，计算量小的优点，并具有很强的可解释性。训练得到的树模型符合人的直观思维，能够可视化的显示出来，因此便于理解，这对某些数据的分析非常重要。它被成功应用于经济和管理数据分析、疾病诊断、模式识别等各类问题。除了单独使用之外，决策树还作为弱分类器用于随机森林和AdaBoost等集成学习算法，在第12章和第13章中将会详细介绍。
参考文献
[1]J.Ross Quinlan.Induction of decision trees.Machine Learning,1(1):81-106,1986.
[2]J.Ross Quinlan.Learning efficient classification procedures and their application to chess end games.
1993.
[3]J.Ross Quinlan.C4.5:Programs for Machine Learning.Morgan Kaufmann,San Francisco,CA,1993.
[4]Breiman,L.,Friedman,J.Olshen,R.and Stone C.Classification and Regression Trees,Wadsworth,1984.
[5]Eibe Frank.Pruning Decision Trees and Lists.2000.
R语言-决策树算法
决策树算法 决策树定义 首先，我们来谈谈什么是决策树。我们还是以鸢尾花为例子来说明这个问题。 观察上图，我们判决鸢尾花的思考过程可以这么来描述：花瓣的长度小于 2.4cm的是setosa(图中绿色的分类)，长度大于1cm的呢?我们通过宽度来判别，宽度小于1.8cm的是versicolor(图中红色的分类)，其余的就是 virginica(图中黑色的分类) 我们用图形来形象的展示我们的思考过程便得到了这么一棵决策树： 这种从数据产生决策树的机器学习技术叫做决策树学习, 通俗点说就是决策树，说白了，这是一种依托于分类、训练上的预测树，根据已知预测、归类未来。 前面我们介绍的k-近邻算法也可以完成很多分类任务，但是他的缺点就是含义不清，说不清数据的内在逻辑，而决策树则很好地解决了这个问题，他十分好理解。从存储的角度来说，决策树解放了存储训练集的空间，毕竟与一棵树的存储空间相比，训练集的存储需求空间太大了。 决策树的构建 一、KD3的想法与实现 下面我们就要来解决一个很重要的问题：如何构造一棵决策树?这涉及十分有趣的细节。 先说说构造的基本步骤，一般来说，决策树的构造主要由两个阶段组成:第一阶段，生成树阶段。选取部分受训数据建立决策树，决策树是按广度优先建立直到每个叶节点包括相同的类标记为止。第二阶段，决策树修剪阶段。用剩余数据检验决策树，如果所建立的决策树不能正确回答所研究的问题，我们要对决策树进行修剪直到建立一棵正确的决策树。这样在决策树每个内部节点处进行属性值的比较，在叶节点得到结论。从根节点到叶节点的一条路径就对应着一条规则，整棵决策树就对应着一组表达式规则。 问题：我们如何确定起决定作用的划分变量。 我还是用鸢尾花的例子来说这个问题思考的必要性。使用不同的思考方式，我们不难发现下面的决策树也是可以把鸢尾花分成3类的。 为了找到决定性特征，划分出最佳结果，我们必须认真评估每个特征。通常划分的办法为信息增益和基尼不纯指数，对应的算法为C4.5和CART。 关于信息增益和熵的定义烦请参阅百度百科，这里不再赘述。 直接给出计算熵与信息增益的R代码：
决策树算法研究及应用? 王桂芹黄道 华东理工大学实验十五楼206室 摘要:信息论是数据挖掘技术的重要指导理论之一,是决策树算法实现的理论依据。决 策树算法是一种逼近离散值目标函数的方法,其实质是在学习的基础上,得到分类规则。本文简要介绍了信息论的基本原理,重点阐述基于信息论的决策树算法,分析了它们目前 主要的代表理论以及存在的问题,并用具体的事例来验证。 关键词:决策树算法分类应用 Study and Application in Decision Tree Algorithm WANG Guiqin HUANG Dao College of Information Science and Engineering, East China University of Science and Technology Abstract:The information theory is one of the basic theories of Data Mining,and also is the theoretical foundation of the Decision Tree Algorithm.Decision Tree Algorithm is a method to approach the discrete-valued objective function.The essential of the method is to obtain a clas-sification rule on the basis of example-based learning.An example is used to sustain the theory. Keywords:Decision Tree; Algorithm; Classification; Application 1 引言 决策树分类算法起源于概念学习系统CLS(Concept Learning System,然后发展 到ID3
3.1 分类与决策树概述 3.1.1 分类与预测 分类是一种应用非常广泛的数据挖掘技术，应用的例子也很多。例如，根据信用卡支付历史记录，来判断具备哪些特征的用户往往具有良好的信用；根据某种病症的诊断记录，来分析哪些药物组合可以带来良好的治疗效果。这些过程的一个共同特点是：根据数据的某些属性，来估计一个特定属性的值。例如在信用分析案例中，根据用户的“年龄”、“性别”、“收入水平”、“职业”等属性的值，来估计该用户“信用度”属性的值应该取“好”还是“差”，在这个例子中，所研究的属性“信用度”是一个离散属性，它的取值是一个类别值，这种问题在数据挖掘中被称为分类。 还有一种问题，例如根据股市交易的历史数据估计下一个交易日的大盘指数，这里所研究的属性“大盘指数”是一个连续属性，它的取值是一个实数。那么这种问题在数据挖掘中被称为预测。 总之，当估计的属性值是离散值时，这就是分类；当估计的属性值是连续值时，这就是预测。 3.1.2 决策树的基本原理 1.构建决策树 通过一个实际的例子，来了解一些与决策树有关的基本概念。 表3-1是一个数据库表，记载着某银行的客户信用记录，属性包括“姓名”、“年龄”、“职业”、“月薪”、......、“信用等级”，每一行是一个客户样本，每一列是一个属性（字段）。这里把这个表记做数据集D。 银行需要解决的问题是，根据数据集D，建立一个信用等级分析模型，并根据这个模型，产生一系列规则。当银行在未来的某个时刻收到某个客户的贷款申请时，依据这些规则，可以根据该客户的年龄、职业、月薪等属性，来预测其信用等级，以确定是否提供贷款给该用户。这里的信用等级分析模型，就可以是一棵决策树。在这个案例中，研究的重点是“信用等级”这个属性。给定一个信用等级未知的客户，要根据他/她的其他属性来估计“信用等级”的值是“优”、“良”还是“差”，也就是说，要把这客户划分到信用等级为“优”、“良”、“差”这3个类别的某一类别中去。这里把“信用等级”这个属性称为“类标号属性”。数据集D中“信用等级”属性的全部取值就构成了类别集合：Class={“优”，
决策树算法的原理与应用 发表时间：2019-02-18T17:17:08.530Z 来源：《科技新时代》2018年12期作者：曹逸知[导读] 在以后，分类问题也是伴随我们生活的主要问题之一，决策树算法也会在更多的领域发挥作用。江苏省宜兴中学江苏宜兴 214200 摘要：在机器学习与大数据飞速发展的21世纪，各种不同的算法成为了推动发展的基石.而作为十大经典算法之一的决策树算法是机器学习中十分重要的一种算法。本文对决策树算法的原理，发展历程以及在现实生活中的基本应用进行介绍，并突出说明了决策树算法所涉及的几种核心技术和几种具有代表性的算法模式。 关键词：机器学习算法决策树 1.决策树算法介绍 1.1算法原理简介 决策树模型是一种用于对数据集进行分类的树形结构。决策树类似于数据结构中的树型结构，主要是有节点和连接节点的边两种结构组成。节点又分为内部节点和叶节点。内部节点表示一个特征或属性, 叶节点表示一个类. 决策树(Decision Tree),又称为判定树, 是一种以树结构(包括二叉树和多叉树)形式表达的预测分析模型，决策树算法被评为十大经典机器学习算法之一[1]。 1.2 发展历程 决策树方法产生于上世纪中旬，到了1975年由J Ross Quinlan提出了ID3算法，作为第一种分类算法模型，在很多数据集上有不错的表现。随着ID3算法的不断发展，1993年J Ross Quinlan提出C4.5算法，算法对于缺失值补充、树型结构剪枝等方面作了较大改进，使得算法能够更好的处理分类和回归问题。决策树算法的发展同时也离不开信息论研究的深入，香农提出的信息熵概念，为ID3算法的核心，信息增益奠定了基础。1984年，Breiman提出了分类回归树算法，使用Gini系数代替了信息熵，并且利用数据来对树模型不断进行优化[2]。2．决策树算法的核心 2.1数据增益 香农在信息论方面的研究，提出了以信息熵来表示事情的不确定性。在数据均匀分布的情况下，熵越大代表事物的越不确定。在ID3算法中，使用信息熵作为判断依据，在建树的过程中，选定某个特征对数据集进行分类后，数据集分类前后信息熵的变化就叫作信息增益，如果使用多个特征对数据集分别进行分类时，信息增益可以衡量特征是否有利于算法对数据集进行分类，从而选择最优的分类方式建树。如果一个随机变量X的可以取值为Xi（i=1…n），那么对于变量X来说，它的熵就是
(收藏)决策树的作用与画法介绍？ 导语： 决策树是一种在结构化决策过程中出现复杂分支时所使用的特定决策情况的树形图模型。它的每个内部节点都表示一个属性上的测试，每个分支代表一个属性某个值域上的测试输出，每个叶节点都存放在一种类别。决策树是使用分支方法来说明各种可能性，评判项目风险及可行性。 免费获取决策树软件：https://www.doczj.com/doc/d26068271.html,/project/decisiontree/ 决策树符号 决策树通常包括决策节点，事件节点，结束等符号，如下图所示。图中所有的符号都是可以编辑的，用户可以根据自己的不同需求来改变符号的颜色，大小以及尺寸。
决策树的优点与缺点 优点：1.可读性好，具有描述性，易于人工理解与分析。 2. 效率高，一次创建可以反复使用。 3. 通过信息增益轻松处理不相关的属性， 缺点：1. 信息不是特别准确。 2. 决策容易受到法律问题和人为观点的影响。 亿图助你快速绘制决策树 第一步：新建空白页面 运行亿图软件，找到项目管理，通过双击模板页面下的决策树来打开一个空白页面。如果时间有限制的话，用户可以直接在例子页面选择合适的例子进行编辑以节省时间。
第二步：拖放符号 从右边符号库中拖放合适的决策树符号在空白页面上，并根据自己的需要调节符号的大小或颜色。 第三步：添加文本
用户有2种添加文本的方式。第一种是直接双击符号然后输入文本；第二种是ctrl+2打开一个文本框然后输入文本。 第四步：选择主题 导航到页面布局，从内置的主题中选择一个合适的主题让决策树显得更加专业和吸引人。 第五步：保存或导出决策树 回到文件页面，用户可以点击保存将决策树保存为默认的.eddx格式或者为了方便分享点击导出&发送将决策树导出为常见的文件格式。
《经济预测与决策》 课程论文 课程论文题目浅谈决策树于风险决策中的应用 专业统计学 班级 学号 姓名
浅谈决策树于风险决策中的应用 摘要：决策树是风险型决策中的一种重要的决策方法.与矩阵决策法相比，决策树具有方便简捷、层次清楚、能形象地显示决策过程等的优点.较为详细的介绍了决策树的思想及决策树的生成方法，并通过实例给出了决策树在决策问题中的具体应用方法. 关键词：风险型决策；决策方法；决策树
Abstract The decision tree is a kind of important decision-making method of risk decision. Compared with the matrix-decision method, decision tree is more convenient and has a clear level ,it also can visually display of the process in decision.This paper introduce the details with this method of how to generate the ideas and how to choose the right decision tree.In the end, give an example to explain this methods’application area. Keywords: The risk of decision-making; decision making method; decision tree
机器学习算法day04_决策树分类算法及应用课程大纲 决策树分类算法原理决策树算法概述 决策树算法思想 决策树构造 算法要点 决策树分类算法案例案例需求 Python实现 决策树的持久化保存 课程目标： 1、理解决策树算法的核心思想 2、理解决策树算法的代码实现 3、掌握决策树算法的应用步骤：数据处理、建模、运算和结果判定
1. 决策树分类算法原理 1.1 概述 决策树（decision tree）——是一种被广泛使用的分类算法。 相比贝叶斯算法，决策树的优势在于构造过程不需要任何领域知识或参数设置 在实际应用中，对于探测式的知识发现，决策树更加适用 1.2 算法思想 通俗来说，决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话： 女儿：多大年纪了？ 母亲：26。 女儿：长的帅不帅？ 母亲：挺帅的。 女儿：收入高不？ 母亲：不算很高，中等情况。 女儿：是公务员不？ 母亲：是，在税务局上班呢。 女儿：那好，我去见见。 这个女孩的决策过程就是典型的分类树决策。 实质：通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见 假设这个女孩对男人的要求是：30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，那么这个可以用下图表示女孩的决策逻辑
上图完整表达了这个女孩决定是否见一个约会对象的策略，其中： ◆绿色节点表示判断条件 ◆橙色节点表示决策结果 ◆箭头表示在一个判断条件在不同情况下的决策路径 图中红色箭头表示了上面例子中女孩的决策过程。 这幅图基本可以算是一颗决策树，说它“基本可以算”是因为图中的判定条件没有量化，如收入高中低等等，还不能算是严格意义上的决策树，如果将所有条件量化，则就变成真正的决策树了。 决策树分类算法的关键就是根据“先验数据”构造一棵最佳的决策树，用以预测未知数据的类别 决策树：是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。
1、为生产甲产品,小行星公司设计了两个基本方案:一就是建大工厂,二就是建小工厂。如果销路好,3年以后考虑扩建。建大工厂需投资300万元,建小工厂需投资160万元,3年后扩建另需投资140万元。扩建后可使用7年,其年度损益值与大工厂相同。每种自然状态的预测概率及年度损益值如下表: 2山姆公司的生产设备已经落后,需要马上更新。公司有人认为,目前产品销路增长,应在更新设备的同时扩大再生产的规模。但也有人认为,市场形势尚难判断,不如先更新设备,3年后再根据形势变化考虑扩大再生产的规模问题。这样,该公司就面临着两个决策方案。决策分析的有关资料如下: A、现在更新设备,需投资35万元, 3年后扩大生产规模,另需投资40万元。 B、现在更新设备的同时扩大再生产的规模,需投资60万元。 C、现在只更新设备,在销售情况良好时,每年可获利6万元;在销售情况不好时,每年可获利4、5万元。 D、如果现在更新与扩产同时进行,若销售情况好,前3年每年可获利12万元;后7年每年可获利15万元;若销售情况不好,每年只获利3万元。 E、每种自然状态的预测概率如下表 3某公司为满足某地区对某一产品的需求设计了三个方案:第一个方案就是新建一个大工厂,需投资320万元;第二个方案就是新建一个小工厂,需投资140
万元;第三方案就是先投资140万元建造一个小工厂,三年以后,如果销路好再考虑扩建,扩建需追加投资200万元,收益与新建大工厂方案相同。根据预测该产品在前三年销路好的概率为0、7,销路差的概率为0、3。如果前三年销路好,后七年销路好的概率为0、9,销路差的概率为0、1;如果前三年的铺路差,则后七年的 企业现在有两个方案可以选 择:(1)新建一个新产品生产车间, 投资需140万元;(2)扩建原有 车间,投资需60万元。两个方案 在不同自然状态下的年收益如下 表(5大华工厂的生产设备已经落后,需要马上更新。公司有人认为,目前产品销路增长,应在更新设备的同时扩大再生产的规模。但也有人认为,市场形势尚难判断,不如先更新设备,3年后再根据形势变化考虑扩大再生产的规模问题。这样,该公司就面临着两个决策方案。决策分析的有关资料如下: A 、现在更新设备,需投资35万元, 3年后扩大生产规模,另需投资40万元。 B 、现在更新设备的同时扩大再生产的规模,需投资60万元。 C 、现在只更新设备,在销售情况良好时,每年可获利6万元;在销售情况不好时,每年可获利4、5万元。 D 、如果现在更新与扩产同时进行,若销售情况好,前3年每年可获利12万元;后7年每年可获利15万元;若销售情况不好,每年只获利3万元。 E 、每种自然状态的预测概率如下表
决策树原理与应用：C5.0 分类预测指通过向现有数据的学习，使模型具备对未来新数据的预测能力。对于分类预测有这样几个重要，一是此模型使用的方法是归纳和提炼，而不是演绎。非数据挖掘类的软件的基本原理往往是演绎，软件能通过一系列的运算，用已知的公式对数据进行运算或统计。分类预测的基本原理是归纳，是学习，是发现新知识和新规律；二是指导性学习。所谓指导性学习，指数据中包含的变量不仅有预测性变量，还有目标变量；三是学习，模型通过归纳而不断学习。 事实上，预测包含目标变量为连续型变量的预测和目标变量为分在变量的分类预测。两者虽然都是预测，但结合决策树算法和我们之前介绍过的时间序列算法知，二者还是有明显的差别的。 Clementine决策树的特点是数据分析能力出色，分析结果易于展示。决策树算法是应用非常广泛的分类预测算法。 1.1决策树算法概述1.11什么是决策树决策树算法属于有指导的学习，即原数据必须包含预测变量和目标变量。决策树之所以如此命名，是因为其分析结果以一棵倒置的树的形式呈现。决策树由上到下依次为根节点、内部节点和叶节点。一个节点对应于数据中的一个字段，即一个字段——即Question——对数据进行一次划分。决策树分为分类决策树
（目标变量为分类型数值）和回归决策树（目标变量为连续型变量）。分类决策树叶节点所含样本中，其输出变量的众数就是分类结果；回归树的叶节点所含样本中，其输出变量的平均值就是预测结果。这一点需要格外注意。 与其它分类预测算法不同的是，决策树基于逻辑比较（即布尔比较）。可以简单描述为：If（条件1）Then（结果1）；If （条件2）Then（结果2）。这样，每一个叶节点都对应于一条布尔比较的推理规则，对新数据的预测就正是依靠这些复杂的推理规则。在实际应用中，一个数据产生的推理规则是极为庞大和复杂的，因此对推理规则的精简是需要关注的。 1.12决策树的几何理解将训练样本集（即操作中常说的Training Data）看做一个n维空间上的一个点，则上面我们提到的布尔比较后的推理规则就像是存在于这个n维空间中的“线”。决策树建立的过程形象上看，就是倒置的树生长的过程，其几何意义上是，每个分枝（每条推理规则）完成对n维空间区域划分的过程。决策树正式生成，则n维空间正式划分完毕，则每一个小区域，代表一个叶节点。通常n 维空间不易于理解，故采用倒置的树来表示此结果。需要注意的一点是，在划分过程中，要尽量做到不同类别的结果归于不同的“区域”。 1.13决策树的核心问题：生成与修剪决策树核心问题有二。一是利用Training Data完成决策树的生成过程；二是利用
计算题 一 1.为生产甲产品，小行星公司设计了两个基本方案：一是建大工厂，二是建小工厂。如果销路好，3年以后考虑扩建。建大工厂需投资300万元，建小工厂需投资160万元，3年后扩建另需投资140万元。扩建后可使用7年，其年度损益值与大工厂相同。每种自然状态的预测概率及年度损益值如下表： 前 3 年 后 7 年 根据上述资料试用决策树法做出决策。 四、计算题（15分）
答：建大厂收益=581-300=281 建小厂收益=447-160=287 所以应选择建小厂方案。 二 山姆公司的生产设备已经落后，需要马上更新。公司有人认为，目前产品销路增长，应在更新设备的同时扩大再生产的规模。但也有人认为，市场形势尚难判断，不如先更新设备，3年后再根据形势变化考虑扩大再生产的规模问题。这样，该公司就面临着两个决策方案。决策分析的有关资料如下： A、现在更新设备，需投资35万元， 3年后扩大生产规模，另需投资40万元。 B、现在更新设备的同时扩大再生产的规模，需投资60万元。 C、现在只更新设备，在销售情况良好时，每年可获利6万元；在销售情况不好时，每年可获利4、5万元。 D、如果现在更新与扩产同时进行，若销售情况好，前3年每年可获利12万元；后7年每年可获利15万元；若销售情况不好，每年只获利3万元。 E、每种自然状态的预测概率如下表
前 3 年 后 7 年 根据上述资料试用决策树法做出决策。 答案：
结点7收益值=0、85×7 × 15+0、15 ×7 ×3=92、4（万元）
结点8收益值=0、85×7 ×6+0、15 ×7 ×4、5=40、4（万元） 结点9收益值=0、1×7 × 15+0、9 ×7 ×3=29、4（万元） 结点10收益值=0、1×7 × 6+0、9 ×7 ×4、5=32、6（万元） 结点1收益值=0、7×[52、4+（3 × 6）]+0、3 ×[32、6+（3 × 4、5）]=63、1（万元） 结点2收益值=0、7×[92、4+（3 × 12）]+0、3 ×[29、4+（3 × 3）]=101、4（万元） 答：用决策树法进行决策应选择更新扩产方案，可获得收益41、4万元。 三 某厂准备生产Y种新产品，对未来的销售前景预测不准，可能出现高需求、中需求、低需求三种自然状态。组织有三个方案可供选择：新建一个车间；扩建原有车间；对原有车间的生产线进行局部改造。三个方案在5年内的经济效益见下表（单位：万元）： 0 1 请分别用悲观决策法、乐观决策法、最大最小后悔决策法做出决策。 悲观决策法指当存在几种自然状态的情况下，宁可把情况估计得坏一 些，从中选择一个收益最大的方案，决策稳妥可靠。按此准则，在低需求的自然状态下，5年内新建方案亏损160万，扩建方案保本，改造方案获利80万。改造方案最佳。 乐观决策法： 新建E=（0、7X600）+（1-0、7）X（-160）=372（万元） 扩建E=（0、7X400）+ （1-0、7）X0=280 （万元） 改造E=（0、7X300）+ （1-0、7）X80=234 （万元） 比较结果，新建方案最佳。 最大最小后悔决策，是用后悔值计算表进行计算的： 后悔值计算表
计算题 1.为生产甲产品，小行星公司设计了两个基本方案：一是建大工厂，二是建小工厂。如果销路好，3年以后考虑扩建。建大工厂需投资300万元，建小工厂需投资160万元，3年后扩建另需投资140万元。扩建后可使用7年，其年度损益值与大工厂相同。每种自然状态的预测概率及年度损益值如下表： 前 3 年 后 7 年
根据上述资料试用决策树法做出决策。 2、计算题（15分）
答：建大厂收益=581-300=281 建小厂收益=447-160=287 所以应选择建小厂方案。 3.山姆公司的生产设备已经落后，需要马上更新。公司有人认为，目前产品销路增长，应在更新设备的同时扩大再生产的规模。但也有人认为，市场形势尚难判断，不如先更新设备，3年后再根据形势变化考虑扩大再生产的规模问题。这样，该公司就面临着两个决策方案。决策分析的有关资料如下： A、现在更新设备，需投资35万元， 3年后扩大生产规模，另需投资40万元。 B、现在更新设备的同时扩大再生产的规模，需投资60万元。 C、现在只更新设备，在销售情况良好时，每年可获利6万元；在销售情况不好时，每年可获利4、5万元。
D、如果现在更新与扩产同时进行，若销售情况好，前3年每年可获利12万元；后7年每年可获利15万元；若销售情况不好，每年只获利3万元。 E、每种自然状态的预测概率如下表 前 3 年 后 7 年
根据上述资料试用决策树法做出决策。 答案：
结点7收益值=0、85×7 × 15+0、15 ×7 ×3=92、4（万元） 结点8收益值=0、85×7 ×6+0、15 ×7 ×4、5=40、4（万元） 结点9收益值=0、1×7 × 15+0、9 ×7 ×3=29、4（万元） 结点10收益值=0、1×7 × 6+0、9 ×7 ×4、5=32、6（万元） 结点1收益值=0、7×[52、4+（3 × 6）]+0、3 ×[32、6+（3 × 4、5）]=63、1（万元） 结点2收益值=0、7×[92、4+（3 × 12）]+0、3 ×[29、4+（3 × 3）]=101、4（万元） 答：用决策树法进行决策应选择更新扩产方案，可获得收益41、4万元。 4. 某厂准备生产Y种新产品，对未来的销售前景预测不准，可能出现高需求、中需求、低需求三种自然状态。组织有三个方案可供选择：新建一个车间；扩建原有车间； 对原有车间的生产线进行局部改造。三个方案在5年内的经济效益见下表（单位：万元）：
厉害了,决策树还可以这么画？ 导语： 决策树是一种在结构化决策过程中出现复杂分支时所使用的特定决策情况的树形图模型。它的每个内部节点都表示一个属性上的测试，每个分支代表一个属性某个值域上的测试输出，每个叶节点都存放在一种类别。决策树是使用分支方法来说明各种可能性，评判项目风险及可行性。 免费获取决策树软件：https://www.doczj.com/doc/d26068271.html,/project/decisiontree/ 决策树符号 决策树通常包括决策节点，事件节点，结束等符号，如下图所示。图中所有的符号都是可以编辑的，用户可以根据自己的不同需求来改变符号的颜色，大小以及尺寸。
决策树的优点与缺点 优点：1.可读性好，具有描述性，易于人工理解与分析。 2. 效率高，一次创建可以反复使用。 3. 通过信息增益轻松处理不相关的属性， 缺点：1. 信息不是特别准确。 2. 决策容易受到法律问题和人为观点的影响。 亿图助你快速绘制决策树 第一步：新建空白页面 运行亿图软件，找到项目管理，通过双击模板页面下的决策树来打开一个空白页面。如果时间有限制的话，用户可以直接在例子页面选择合适的例子进行编辑以节省时间。
第二步：拖放符号 从右边符号库中拖放合适的决策树符号在空白页面上，并根据自己的需要调节符号的大小或颜色。 第三步：添加文本
用户有2种添加文本的方式。第一种是直接双击符号然后输入文本；第二种是ctrl+2打开一个文本框然后输入文本。 第四步：选择主题 导航到页面布局，从内置的主题中选择一个合适的主题让决策树显得更加专业和吸引人。 第五步：保存或导出决策树 回到文件页面，用户可以点击保存将决策树保存为默认的.eddx格式或者为了方便分享点击导出&发送将决策树导出为常见的文件格式。
基于关联规则的决策树算法 汪海锐1,2，李 伟2 (1. 河海大学计算机与信息学院，江苏 常州 213022；2. 海军蚌埠士官学校，安徽 蚌埠 233012) 摘 要：通过将关联规则与决策树算法相结合，形成一种基于关联规则的决策树算法。该算法对不同时期同一事务的异种数据结构进行处理，得到一种可扩展的多分支分类决策树，使得改进后的决策树算法具有良好的可扩展性。该算法解决了传统分类算法在数据集维度发生变化时分类过程无法持续进行的问题。 关键词关键词：：决策树；关联规则；分类算法；扩展性；组合算法 Decision Tree Algorithm Based on Association Rules W ANG Hai-rui 1,2, LI Wei 2 (1. Institute of Computer & Information, Hohai University, Changzhou 213022, China; 2. Navy Petty Officer Academy, Bengbu 233012, China) 【Abstract 】This paper combines association rules and decision tree algorithm, and proposes a new decision tree classification based on association rule. The decision tree algorithm can handle dissimilar transaction data set record blocks which are same investigations conducted in different times to the same transactions. Through the decision tree algorithm, it can get a multi-crunodes decision tree, which has a good extendable performance. The algorithm solves the problem, which exists in the traditional classification, that is the traditional classification can not classify effectively and sustaine when dimensions of dataset change. 【Key words 】decision tree; association rule; classification algorithm; extendable performance; combining algorithm DOI: 10.3969/j.issn.1000-3428.2011.09.035 计 算 机 工 程 Computer Engineering 第37卷 第9期 V ol.37 No.9 2011年5月 May 2011 ·软件技术与数据库软件技术与数据库·· 文章编号文章编号：：1000—3428(2011)09—0104—03 文献标识码文献标识码：：A 中图分类号中图分类号：：TP311.12 1 概述 在数据挖掘的诸多分支中，分类具有极大的实际意义， 渐渐成为数据挖掘在生活中应用的一个重要课题，也使得各种分类算法成为当前的研究热点。在分类算法中，决策树算法[1-2]是一个极为经典的分类算法，有不少学者对其进行研究改进。对于现行的决策树算法，虽然不少学者从多个方面提出了改进，部分算法解决了其缺值处理、并行处理等局限性，但它们同时都具有一个不可回避的缺点：无法适应因采样数据时期不同而导致的属性值不一致问题。同时，传统的决策树算法对于很庞大的数据集而言是很不合适的，由此一些研究人员采用了不同的方法来处理这个问题，如并行的处理方法、多决策树合并算法来提高决策树算法的效率，为此，文献[3]对数据集进行划分，将大数据集划分成小的数据集，再 在小数据集上应用决策树算法，生成小的决策树，再将各个 小的决策树联合起来形成整个决策树。该方法虽然解决了大数据集的分类问题，但降低了分类的准确度。 本文结合关联规则与决策树算法形成一种新的分类算法，既具有决策树的优点，又具有关联规则可并行处理的性质。该算法主要着眼于现实世界的事务数据集是不断变化的，在数据的采集过程中可能会出现某段时间只采集某一事务数据的某些属性值样本，而后期的采集又增加了一些属性，从而形成了对同一事务不同时期的数据采集，构成异种数据集。在这些数据集中可能还会出现新增的类别，也可能会出现某些类别的消亡。在此情况下，按照传统的决策树算法，一旦某一时段的数据集采集完成就进行处理，则如果该时段之后的新增数据集增加了采样属性，那么旧的数据集就有可能会失效或无法使用。如果在新数据集采集完成之前已经对旧数据集进行处理，则造成前期所有的处理工作都无用。为此， 本文考虑利用不同时期的数据集，建立新的决策树算法，使决策树具备良好的伸缩性及可调整性。 2 基于关联规则的决策树算法 2.1 算法流程及简介 本文通过决策树算法与关联规则的结合形成基于关联规则的决策树算法，并对传统决策树算法与关联规则进行结合，形成新的分类算法，该算法同时具有决策树分类准确、易于理解等特点。本算法主要流程如图1所示。
决策树分类算法 决策树是一种用来表示人们为了做出某个决策而进行的一系列判断过程的树形图。决策树方法的基本思想是：利用训练集数据自动地构造决策树，然后根据这个决策树对任意实例进行判定。 1．决策树的组成 决策树的基本组成部分有：决策节点、分支和叶，树中每个内部节点表示一个属性上的测试，每个叶节点代表一个类。图1就是一棵典型的决策树。 图1 决策树 决策树的每个节点的子节点的个数与决策树所使用的算法有关。例如，CART算法得到的决策树每个节点有两个分支，这种树称为二叉树。允许节点含有多于两个子节点的树称为多叉树。 下面介绍一个具体的构造决策树的过程，该方法
是以信息论原理为基础，利用信息论中信息增益寻找数据库中具有最大信息量的字段，建立决策树的一个节点，然后再根据字段的不同取值建立树的分支，在每个分支中重复建立树的下层节点和分支。 ID3算法的特点就是在对当前例子集中对象进行分类时，利用求最大熵的方法，找出例子集中信息量（熵）最大的对象属性，用该属性实现对节点的划分，从而构成一棵判定树。 首先，假设训练集C 中含有P 类对象的数量为p ，N 类对象的数量为n ，则利用判定树分类训练集中的对象后，任何对象属于类P 的概率为p/(p+n)，属于类N 的概率为n/(p+n)。 当用判定树进行分类时，作为消息源“P ”或“N ”有关的判定树，产生这些消息所需的期望信息为： n p n log n p n n p p log n p p )n ,p (I 22++-++- = 如果判定树根的属性A 具有m 个值｛A 1, A 2, …, A m ｝，它将训练集C 划分成｛C 1, C 2, …, C m ｝，其中A i 包括C 中属性A 的值为A i 的那些对象。设C i 包括p i 个类P 对象和n i 个类N 对象，子树C i 所需的期望信息是I(p i , n i )。以属性A 作为树根所要求的期望信息可以通过加权平均得到
决策树决策树研发二部
目录 1. 算法介绍 (1) 1.1. 分支节点选取 (1) 1.2. 构建树 (3) 1.3. 剪枝 (10) 2. sk-learn 中的使用 (12) 3. sk-learn中源码分析 (13)
1. 算法介绍 决策树算法是机器学习中的经典算法之一，既可以作为分类算法，也可以作 为回归算法。决策树算法又被发展出很多不同的版本，按照时间上分，目前主要包括，ID3、C4.5和CART版本算法。其中ID3版本的决策树算法是最早出现的，可以用来做分类算法。C4.5是针对ID3的不足出现的优化版本，也用来做分类。CART也是针对 ID3优化出现的，既可以做分类，可以做回归。 决策树算法的本质其实很类似我们的if-elseif-else语句，通过条件作为分支依据，最终的数学模型就是一颗树。不过在决策树算法中我们需要重点考虑选取分支条件的理由，以及谁先判断谁后判断，包括最后对过拟合的处理，也就是剪枝。这是我们之前写if语句时不会考虑的问题。 决策树算法主要分为以下3个步骤： 1. 分支节点选取 2. 构建树 3. 剪枝 1.1. 分支节点选取 分支节点选取，也就是寻找分支节点的最优解。既然要寻找最优，那么必须要有一个衡量标准，也就是需要量化这个优劣性。常用的衡量指标有熵和基尼系数。 熵：熵用来表示信息的混乱程度，值越大表示越混乱，包含的信息量也就越多。比如，A班有10个男生1个女生，B班有5个男生5个女生，那么B班的熵值就比A班大，也就是B班信息越混乱。 Entropy = -V p ” 基尼系数：同上，也可以作为信息混乱程度的衡量指标。 Gini = 1 - p： l-L
决策树算法的原理与应用 摘要：在机器学习与大数据飞速发展的21世纪，各种不同的算法成为了推动发 展的基石.而作为十大经典算法之一的决策树算法是机器学习中十分重要的一种算法。本文对决策树算法的原理，发展历程以及在现实生活中的基本应用进行介绍，并突出说明了决策树算法所涉及的几种核心技术和几种具有代表性的算法模式。 关键词：机器学习算法决策树 1.决策树算法介绍 1.1算法原理简介 决策树模型是一种用于对数据集进行分类的树形结构。决策树类似于数据结 构中的树型结构，主要是有节点和连接节点的边两种结构组成。节点又分为内部 节点和叶节点。内部节点表示一个特征或属性, 叶节点表示一个类. 决策树(Decision Tree),又称为判定树, 是一种以树结构(包括二叉树和多叉树)形式表达的 预测分析模型，决策树算法被评为十大经典机器学习算法之一[1]。 1.2 发展历程 决策树方法产生于上世纪中旬，到了1975年由J Ross Quinlan提出了ID3算法，作为第一种分类算法模型，在很多数据集上有不错的表现。随着ID3算法的 不断发展，1993年J Ross Quinlan提出C4.5算法，算法对于缺失值补充、树型结 构剪枝等方面作了较大改进，使得算法能够更好的处理分类和回归问题。决策树 算法的发展同时也离不开信息论研究的深入，香农提出的信息熵概念，为ID3算 法的核心，信息增益奠定了基础。1984年，Breiman提出了分类回归树算法，使 用Gini系数代替了信息熵，并且利用数据来对树模型不断进行优化[2]。 2．决策树算法的核心 2.1数据增益 香农在信息论方面的研究，提出了以信息熵来表示事情的不确定性。在数据 均匀分布的情况下，熵越大代表事物的越不确定。在ID3算法中，使用信息熵作 为判断依据，在建树的过程中，选定某个特征对数据集进行分类后，数据集分类 前后信息熵的变化就叫作信息增益，如果使用多个特征对数据集分别进行分类时，信息增益可以衡量特征是否有利于算法对数据集进行分类，从而选择最优的分类 方式建树。 如果一个随机变量X的可以取值为Xi（i=1…n），那么对于变量X来说，它 的熵就是 在得到基尼指数增益之后，选择基尼指数增益最大的特征来作为当前步骤的 分类依据，在之后的分类中重复迭代使用这一方法来实现模型的构造。 3. 决策树算法的优缺点 3.1决策树算法的优点[3] （1）计算速度快，算法简单，分类依据清晰 （2）在处理数据时，有很高的准确度，同时分类结果清晰，步骤明朗。 （3）可以处理连续和种类字段 （4）适合高维数据 3.2决策树算法的缺点 （1）决策树算法可以帮助使用者创建复杂的树，但是在训练的过程中，如
人工智能技术报告 数据挖掘决策树经典算法 决策树算法简介 决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。 决策树方法最早产生于上世纪60年代，到70年代末。由J Ross Quinlan 提出了ID3算法，此算法的目的在于减少树的深度。但是忽略了叶子数目的研究。C4.5算法在ID3算法的基础上进行了改进，对于预测变量的缺值处理、剪枝技术、派生规则等方面作了较大改进，既适合于分类问题，又适合于回归问题。 决策树算法构造决策树来发现数据中蕴涵的分类规则．如何构造精度高、规模小的决策树是决策树算法的核心内容。决策树构造可以分两步进行。第一步，决策树的生成：由训练样本集生成决策树的过程。一般情况下，训练样本数据集是根据实际需要有历史的、有一定综合程度的，用于数据分析处理的数据集。第二步，决策树的剪技：决策树的剪枝是对上一阶段生成的决策树进行检验、校正和修下的过程，主要是用新的样本数扼集（称为测试数据集）中的数据校验决策树生成过程中产生的初步规则，将那些影响预衡准确性的分枝剪除 决策树的工作原理 决策树一般都是自上而下的来生成的。 选择分割的方法有多种，但是目的都是一致的，即对目标类尝试进行最佳的分割。 从根节点到叶子节点都有一条路径，这条路径就是一条“规则”。 决策树可以是二叉的，也可以是多叉的。 对每个节点的衡量： 1) 通过该节点的记录数； 2) 如果是叶子节点的话，分类的路径； 3) 对叶子节点正确分类的比例。 有些规则的效果可以比其他的一些规则要好。
决策树研发二部
目录 1. 算法介绍 (1) 1.1.分支节点选取 (1) 1.2.构建树 (3) 1.3.剪枝 (10) 2. sk-learn中的使用 (12) 3. sk-learn中源码分析 (13)
1.算法介绍 决策树算法是机器学习中的经典算法之一，既可以作为分类算法，也可以作为回归算法。决策树算法又被发展出很多不同的版本，按照时间上分，目前主要包括，ID3、C4.5和CART版本算法。其中ID3版本的决策树算法是最早出现的，可以用来做分类算法。C4.5是针对ID3的不足出现的优化版本，也用来做分类。CART也是针对ID3优化出现的，既可以做分类，可以做回归。 决策树算法的本质其实很类似我们的if-elseif-else语句，通过条件作为分支依据，最终的数学模型就是一颗树。不过在决策树算法中我们需要重点考虑选取分支条件的理由，以及谁先判断谁后判断，包括最后对过拟合的处理，也就是剪枝。这是我们之前写if语句时不会考虑的问题。 决策树算法主要分为以下3个步骤： 1.分支节点选取 2.构建树 3.剪枝 1.1.分支节点选取 分支节点选取，也就是寻找分支节点的最优解。既然要寻找最优，那么必须要有一个衡量标准，也就是需要量化这个优劣性。常用的衡量指标有熵和基尼系数。 熵：熵用来表示信息的混乱程度，值越大表示越混乱，包含的信息量也就越多。比如，A班有10个男生1个女生，B班有5个男生5个女生，那么B班的熵值就比A班大，也就是B班信息越混乱。 基尼系数：同上，也可以作为信息混乱程度的衡量指标。
有了量化指标后，就可以衡量使用某个分支条件前后，信息混乱程度的收敛效果了。使用分支前的混乱程度，减去分支后的混乱程度，结果越大，表示效果越好。 #计算熵值 def entropy(dataSet): tNum = len(dataSet) print(tNum) #用来保存标签对应的个数的，比如,男：6，女：5 labels = {} for node in dataSet: curL = node[-1] #获取标签 if curL not in labels.keys(): labels[curL] = 0 #如果没有记录过该种标签，就记录并初始化为0 labels[curL] += 1 #将标签记录个数加1 #此时labels中保存了所有标签和对应的个数 res = 0 #计算公式为-p*logp，p为标签出现概率 for node in labels: p = float(labels[node]) / tNum res -= p * log(p, 2) return res #计算基尼系数 def gini(dataSet): tNum = len(dataSet) print(tNum) # 用来保存标签对应的个数的，比如,男：6，女：5 labels = {} for node in dataSet: curL = node[-1] # 获取标签 if curL not in labels.keys(): labels[curL] = 0 # 如果没有记录过该种标签，就记录并初始化为0 labels[curL] += 1 # 将标签记录个数加1 # 此时labels中保存了所有标签和对应的个数 res = 1