《[精选]决策树技术》由会员分享，可在线阅读，更多相关《[精选]决策树技术（32页珍藏版）》请在金锄头文库上搜索。
1、决策树技术 Decision Trees,组员：贾小彦 邓蓓蓓 戴维,内容提要,简介 决策树基本概念 决策树的优缺点 经典算法,简介,决策树和决策规则是解决实际应用中分类问题的数据挖掘方法。 一般来说，分类是把数据项映射到其中一个事先定义的类中的这样一个学习函数的过程。由一组输入的属性值向量(也叫属性向量)和相应的类，用基于归纳学习算法得出分类。 学习的目标是构建一个分类模型，通常也叫分类器。它可以根据有效的属性输入值预测一些实体(所给样本)的类。是一个在样本其他属性已知的情况下预测另外一个属性(样本的类)的模型(分类的结果)。,(a) 决策树方法的起源是概念学习系统CLS (b) 机器学习领
2、域前辈及大牛之一Quinlan,J.R, 在1983提出ID3决策树算法； 1993年正式提出了c4.5算法,并公布了源代码 2002年发表C5.0 （See5）商业版 决策树的另一类家族： CART 1984， Friedman& Breiman,决策树基本概念,决策树是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。,下图是一个简单的决策树。该问题有两个属性X,Y。所有属性值X1和YB的样本属于类2。不论属性Y的值是多少，值X 1的样本都属于类1。,决策树的表示,决策树的基本组成部分
3、：决策结点、分支和叶子。,决策树中最上面的结点称为根结点是整个决策树的开始。每个分支是一个新的决策结点，或者是树的叶子。 每个决策结点代表一个问题或者决策通常对应待分类对象的属性。 每个叶结点代表一种可能的分类结果,在沿着决策树从上到下的遍历过程中，在每个结点都有一个测试。对每个结点上问题的不同测试输出导致不同的分枝，最后会达到一个叶子结点。这一过程就是利用决策树进行分类的过程，利用若干个变量来判断属性的类别,决策树的优点 1、推理过程容易理解，决策推理过程可以表示成If Then形式； 2、推理过程完全依赖于属性变量的取值特点； 3、可自动忽略目标变量没有贡献的属性变量，也为判断属性变量的重
4、要性，减少变量的数目提供参考。,决策树的缺点 1、对连续性的字段比较难预测 2、当类别太多时，错误可能会增加的比较快 3、一般的算法分类的时候，只是根据一个属性来分类。 不是全局最优。,决策树的优、缺点,经典算法ID3学习算法,决策树的生成,基本算法 自上而下分而治之的方法 开始时，所有的数据都在根节点 属性都是种类字段 (如果是连续的，将其离散化) 所有记录用所选属性递归的进行分割 属性的选择是基于一个启发式规则或者一个统计的度量 停止分割的条件 一个节点上的数据都是属于同一个类别 没有属性可以再用于对数据进行分割,重要问题：哪个属性作为当前的测试节点,信息论相关内容,Shannon1948
5、年提出的信息论理论。事件ai的信息I （ ai ）可如下度量：,其中p(ai)表示事件ai发生的概率。 假设有n个互不相容的事件a1,a2,a3,.,an,它们中有且仅有一个发生，则其平均的信息量可如下度量：,上式，对数底数可以为任何数，不同的取值对应了熵的不同单位。 通常取2，并规定当p(ai)=0时 =0,公式1,在决策树分类中，假设S是训练样本集合，|S|是训练样本数，样本划分为n个不同的类C1,C2,.Cn，这些类的大小分别标记为|C1|，|C2|，.,|Cn|。则任意样本S属于类Ci的概率为：,Entropy（S，A）=（|Sv|/|S|）* Entropy(Sv) 公式2,是属性A
6、的所有可能的值v,Sv是属性A有v值的S子集 |Sv|是Sv 中元素的个数；|S|是S中元素的个数。,Gain（S，A）是属性A在集合S上的信息增益 Gain（S，A）= Entropy(s)-Entropy（S，A） 公式3 Gain（S，A）越大，说明选择测试属性对分类提供的信息越多,熵的计算,Eg1:,Eg2:,假定公司收集了左表数据，那么对于任意给定的客人（测试样例），你能帮助公司将这位客人归类吗？ 即：你能预测这位客人是属于“买”计算机的那一类，还是属于“不买”计算机的那一类？ 又：你需要多少有关这位客人的信息才能回答这个问题？,第1步计算决策属性的熵,决策属性“买计算机？”。该属性
7、分 两类：买/不买 S1(买)=641 S2（不买）= 383 S=S1+S2=1024 P1=641/1024=0.6260 P2=383/1024=0.3740 I(S1,S2)=I(641,383) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9537,第2步计算条件属性的熵,条件属性共有4个。分别是年龄、 收入、学生、信誉。 分别计算不同属性的信息增益。,第2-1步计算年龄的熵,年龄共分三个组： 青年、中年、老年 青年买与不买比例为128/256 S1(买)=128 S2（不买）= 256 S=S1+S2=384 P1=128/384 P2
8、=256/384 I(S1,S2)=I(128,256) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9183,第2-2步计算年龄的熵,年龄共分三个组： 青年、中年、老年 中年买与不买比例为256/0 S1(买)=256 S2（不买）= 0 S=S1+S2=256 P1=256/256 P2=0/256 I(S1,S2)=I(256，0) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0,第2-3步计算年龄的熵,年龄共分三个组： 青年、中年、老年 老年买与不买比例为125/127 S1(买)=125 S2（不
9、买）=127 S=S1+S2=252 P1=125/252 P2=127/252 I(S1,S2)=I(125，127) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9157,第2-4步计算年龄的熵,年龄共分三个组： 青年、中年、老年 所占比例 青年组 384/1025=0.375 中年组 256/1024=0.25 老年组 384/1024=0.375 计算年龄的平均信息期望 E（年龄）=0.375*0.9183+0.25*0+0.375*0.9157 =0.6877 G（年龄信息增益） =0.9537-0.6877 =0.2660 （1）,第3
10、步计算收入的熵,收入共分三个组： 高、中、低 E（收入）=0.9361 收入信息增益=0.9537-0.9361 =0.0176 (2),第4步计算学生的熵,学生共分二个组： 学生、非学生 E（学生）=0.7811 年龄信息增益=0.9537-0.7811 =0.1726 （3）,第5步计算信誉的熵,信誉分二个组： 良好，优秀 E（信誉）= 0.9048 信誉信息增益=0.9537-0.9048 =0.0453 （4）,第6步计算选择节点,年龄信息增益=0.9537-0.6877 =0.2660 （1） 收入信息增益=0.9537-0.9361 =0.0176 （2） 学生信息增益=0.953
11、7-0.7811 =0.1726 （3） 信誉信息增益=0.9537-0.9048 =0.0453 （4）,年龄,买/ 不买,买/ 不买,买,青年,中年,老年,叶子,青年买与不买比例为128/256 S1(买)=128 S2（不买）= 256 S=S1+S2=384 P1=128/384 P2=256/384 I(S1,S2)=I(128,256) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9183,如果选择收入作为节点分高、中、低,I(0,128)=0 比例: 128/384=0.3333 I(64,128)=0.9183 比例: 192/38
12、4=0.5 I(64,0)=0 比例: 64/384=0.1667,平均信息期望（加权总和）： E(收入）= 0.3333 * 0 + 0.5 * 0.9183 + 0.1667 * 0 = 0.4592 Gain(收入) = I(128, 256) - E(收入)=0.9183 0.4592 = 0.4591,ID3算法小结,ID3算法是一种经典的决策树学习算法。ID3算法的基本思想是，以信息熵为度量，用于决策树节点的属性选择，每次优先选取信息量最多的属性，亦即能使熵值变为最小的属性，以构造一颗熵值下降最快的决策树，到叶子节点处的熵值为0。此时，每个叶子节点对应的实例集中的实例属于同一类。,ID3算法存在的缺点,（1）ID3算法在选择根节点和各内部节点中的分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息。 （2）ID3算法只能对描述属性为离散型属性的数据集构造决策树 针对ID3算法存在的不足它被改进为C4.5算法,
