决策树技术.

《决策树技术.》由会员分享，可在线阅读，更多相关《决策树技术.（31页珍藏版）》请在金锄头文库上搜索。

1、决策树技术 Decision Trees 组员：贾小彦 邓蓓蓓 戴维 内容提要内容提要 n n 简介简介 n n 决策树基本概念决策树基本概念 n n 决策树的优缺点决策树的优缺点 n n 经典算法经典算法 简介简介 n决策树和决策规则是解决实际应用中分类问题 的数据挖掘方法。 n一般来说，分类是把数据项映射到其中一个事 先定义的类中的这样一个学习函数的过程。由 一组输入的属性值向量(也叫属性向量)和相应的 类，用基于归纳学习算法得出分类。 n学习的目标是构建一个分类模型，通常也叫分 类器。它可以根据有效的属性输入值预测一些 实体(所给样本)的类。是一个在样本其他属性已 知的情况下预测另外一个

2、属性(样本的类)的模型 (分类的结果)。 (a) 决策树方法的起源是概念学习系统CLS (b) 机器学习领域前辈及大牛之一Quinlan,J.R, 在1983提出ID3决策树算法； 1993年正式提出了c4.5算法,并公布了源代码 2002年发表C5.0 （See5）商业版 决策树的另一类家族： CART 1984， Friedman& Breiman 决策树基本概念决策树基本概念 决策树是一种典型的分类方法，首先对数据 进行处理，利用归纳算法生成可读的规则和决 策树，然后使用决策对新数据进行分析。本质 上决策树是通过一系列规则对数据进行分类的 过程。 下图是一个简单的决策树。该问题有两个属性

3、X,Y 。所有属性值X1和YB的样本属于类2。不论属 性Y的值是多少，值X 1的样本都属于类1。 决策树的表示 决策树的基本组成部分：决策结点、分支和叶子。 决策树中最上面的结点称 为根结点是整个决策树的开 始。每个分支是一个新的决策 结点，或者是树的叶子。 每个决策结点代表一个问 题或者决策通常对应待分类对 象的属性。 每个叶结点代表一种可能 的分类结果 在沿着决策树从上到下的遍历过程中，在每个结点都有 一个测试。对每个结点上问题的不同测试输出导致不同的 分枝，最后会达到一个叶子结点。这一过程就是利用决策 树进行分类的过程，利用若干个变量来判断属性的类别 决策树的优点 1、推理过程容易理解，

4、决策推理过程可以表示成If Then形式； 2、推理过程完全依赖于属性变量的取值特点； 3、可自动忽略目标变量没有贡献的属性变量，也为判 断属性变量的重要性，减少变量的数目提供参考。 决策树的缺点 1、对连续性的字段比较难预测 2、当类别太多时，错误可能会增加的比较快 3、一般的算法分类的时候，只是根据一个属性来分类。 不是全局最优。 决策决策树树的的优优、缺点缺点 经典算法ID3学习算法 决策树的生成 基本算法 自上而下分而治之的方法 开始时，所有的数据都在根节点 属性都是种类字段 (如果是连续的，将其离散化) 所有记录用所选属性递归的进行分割 属性的选择是基于一个启发式规则或者一个统计的度

5、量 停止分割的条件 一个节点上的数据都是属于同一个类别 没有属性可以再用于对数据进行分割 重要问题：哪个属性作为当前的测试 节点 信息论相关内容 Shannon1948年提出的信息论理论。事件ai的信息I （ ai ）可如下度量： 其中p(ai)表示事件ai发生的概率。 假设有n个互不相容的事件a1,a2,a3,.,an,它们中有且仅 有一个发生，则其平均的信息量可如下度量： 上式，对数底数可以为任何数，不同的取值对应了熵的不 同单位。 通常取2，并规定当p(ai)=0时 =0 公式1 在决策树分类中，假设S是训练样本集合，|S|是训练样本 数，样本划分为n个不同的类C1,C2,.Cn，这些类

6、的大小分 别标记为|C1|，|C2|，,|Cn|。则任意样本S属于类Ci的 概率为： Entropy（S，A）=（|Sv|/|S|）* Entropy(Sv) 公式2 是属性A的所有可能的值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: 假定公司收集了左表数据 ，那么对于任意给定的客 人（测试样例），你能帮 助公司将这位客人归类吗 ？

7、即：你能预测这位客人是 属于“买”计算机的那一 类，还是属于“不买”计 算机的那一类？ 又：你需要多少有关这位 客人的信息才能回答这个 问题？ 计 数 年龄收入学生信誉归类：买计算机 ？ 64青高否良不买 64青高否优不买 128中高否良买 60老中否良买 64老低是良买 64老低是优不买 64中低是优买 128青中否良不买 64青低是良买 132老中是良买 64青中是优买 32中中否优买 32中高是良买 63老中否优不买 1 老中否优买 第1步计算决策属性的熵 决策属性“买计算机？”。该属 性分 两类：买/不买 S1(买)=641 S2（不买）= 383 S=S1+S2=1024 P1=64

8、1/1024=0.6260 P2=383/1024=0.3740 I(S1,S2)=I(641,383) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9537 计 数 年龄收入学生信誉归类：买计算机 ？ 64青高否良不买 64青高否优不买 128中高否良买 60老中否良买 64老低是良买 64老低是优不买 64中低是优买 128青中否良不买 64青低是良买 132老中是良买 64青中是优买 32中中否优买 32中高是良买 63老中否优不买 1 老中否优买 第2步计算条件属性的熵 条件属性共有4个。分别是年龄、 收入、学生、信誉。 分别计算不同属性的

9、信息增益。 第2-1步计算年龄的熵 年龄共分三个组： 青年、中年、老年 青年买与不买比例为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 第2-2步计算年龄的熵 年龄共分三个组： 青年、中年、老年 中年买与不买比例为256/0 S1(买)=256 S2（不买）= 0 S=S1+S2=256 P1=256/256 P2=0/256 I(S1,S2)=I(256，0) =-P1Lo

10、g2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0 第2-3步计算年龄的熵 年龄共分三个组： 青年、中年、老 年 老年买与不买比例为 125/127 S1(买)=125 S2（不买）=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.

11、375 计算年龄的平均信息期望 E（年龄）=0.375*0.9183+0.25*0+0.375*0.9157 =0.6877 G（年龄信息增益） =0.9537-0.6877 =0.2660 （1） 计 数 年龄收入学生信誉归类：买计算机 ？ 64青高否良不买 64青高否优不买 128中高否良买 60老中否良买 64老低是良买 64老低是优不买 64中低是优买 128青中否良不买 64青低是良买 132老中是良买 64青中是优买 32中中否优买 32中高是良买 63老中否优不买 1 老中否优买 第3步计算收入的熵 收入共分三个组： 高、中、低 E（收入）=0.9361 收入信息增益=0.953

12、7 -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.9537-0.7811 =0.1726 （3） 信誉信息增益=0.9537-0.9048 =

13、0.0453 （4） 计 数 年龄收入学生信誉归类：买计算机 ？ 64青高否良不买 64青高否优不买 128青中否良不买 64青低是良买 64青中是优买 年龄 买/ 不 买 买/ 不 买 买 青年 中年 老年 叶子 计 数 年龄收入学生信誉归类：买计算机 ？ 64青高否良不买 64青高否优不买 128青中否良不买 64青低是良买 64青中是优买 青年买与不买比例为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+P

14、2Log2P2) =0.9183 计 数 年龄收入学生信誉归类：买计算机 ？ 64青高否良不买 64青高否优不买 128青中否良不买 64青低是良买 64青中是优买 如果选择收入作为节点分高、中、低 I(0,128)=0 比例: 128/384=0.3333 I(64,128)=0.9183 比例: 192/384=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.

15、4592 = 0.4591 计 数 年 龄 收入学生信誉归类：买计算 机？ 64青高否良不买 64青高否优不买 12 8 中高否良买 60老中否良买 64老低是良买 64老低是优不买 64中低是优买 12 8 青中否良不买 64青低是良买 13 2 老中是良买 64青中是优买 32中中否优买 32中高是良买 63老中否优不买 1 老中否优买 ID3算法小结 ID3算法是一种经典的决策树学习算法。ID3算 法的基本思想是，以信息熵为度量，用于决策树节 点的属性选择，每次优先选取信息量最多的属性， 亦即能使熵值变为最小的属性，以构造一颗熵值下 降最快的决策树，到叶子节点处的熵值为0。此时 ，每个叶子节点对应的实例集中的实例属于同一 类。 ID3算法存在的缺点 （1）ID3算法在选择根节点和各内部节点中的分 支属性时，采用信息增益作为评价标准。信息增 益的缺点是倾向于选择取值较多的属性，在有些 情况下这类属性可能不会提供太多有价值的信 息。 （2）ID3算法只能对描述属性为离散型属性的数 据集构造决策树 针对ID3算法存在的不足它被改进为C4.5算法