第6章 ID3决策树.ppt

1、第6章 ID3决策树分类算法,主讲教师： 唐德玉,本结要点,一、引言 二、什么是决策树 三、决策树的建立（ID3算法） 四、Microsoft SQL Server 2005实践决策树 五、决策树的数据准备,2,01:41:24,你能判定他/她买计算机的可能性大不大吗？,3,医 药信息分析与应用课程组,01:41:25,一、引例,决策树的用途,4,医药信息分析与应用课程组,假定公司收集了左表数据，那么对于任意给定的客人（测试样例），你能帮助公司将这位客人归类吗？ 即：你能预测这位客人是属于“买”计算机的那一类，还是属于“不买”计算机的那一类？ 又：你需要多少有关这位客人的信息才能回答这个问题？

2、,决策树可以帮助你解决好这个问题,01:41:25,决策树的用途,01:41:25,5,医药信息分析与应用课程组,谁在买计算机？,他/她会买计算机吗？,决策树的用途,01:41:25,6,医药信息分析与应用课程组,一棵很糟糕的决策树,二、什么是决策树,A decision tree is a flow-chart-like tree structure, where each internal node denotes a test on an attribute, each branch represents an outcome of the test, and leaf nodes re

3、present classes or class distributions.,01:41:25,7,医药信息分析与应用课程组,三、决策树的建立,1.决策树建立的关键 2.对测试样例的信息期望(The expected information needed to classify a given sample(中文可能称：评价函数) 信息期望 的分析与计算 平均信息期望 信息期望的减少（Gain） 3.决策树建立步骤（例）,01:41:25,8,医药信息分析与应用课程组,1.决策树建立的关键,1、决策树建立的关键,01:41:25,9,医药信息分析与应用课程组,建立一个好的决策树的关键是决定树

4、根和子树根的属性,01:41:25,10,医药信息分析与应用课程组,年龄,1.决策树建立的关键,2. 对测试样例的信息期望,张三属于哪一类？为了回答该问题，对张三的信息期望值是多少？,01:41:25,11,医药信息分析与应用课程组,年龄,信息期望=0,信息期望=？,信息期望=？,信息期望=？,01:41:26,12,医药信息分析与应用课程组,年龄,平均信息期望？,信息期望的减少？,信息期望？,2. 对测试样例的信息期望,2. 对测试样例的信息期望,让我们称所需要研究的属性为“分类属性”。假设该属性共分m类，而它们每一类在数据表中计数的总和分别为s1, s2 , sm。 令 s = s1+ s

5、2 + +sm 那么对于任一样例，决定它所属类别的信息期望可以用下面的公式来计算： I(s1, s2 , sm) = - pi log2(pi) 其中 pi = si /s,01:41:26,13,医药信息分析与应用课程组,信息期望？,01:41:26,14,医药信息分析与应用课程组,例：左表 分类属性：买计算机？ 该属性共分两类(m=2): 买/不买 s1 = 641, s2 = 383 s = s1+ s2 = 1024 p1 = s1 /s = 641/1024 = 0.6260 p2 = s2 /s = 383/1024 = 0.3740 I(s1, s2) = I(641, 383)

6、 = - (p1 log2(p1) + p2 log2(p2) = 0.9537,2. 对测试样例的信息期望,信息期望？,01:41:26,15,医药信息分析与应用课程组,2. 对测试样例的信息期望,讨论：“买”/“不买”计算机的人数之间的比例对于信息期望值的影响 I(641, 383) = 0.9537 I(512, 512) = I(4, 4) = 1 I(51, 973) = I(973, 51) = 0.2856 I(0, 1024) = I(256, 0) = 0 I(128, 256) = 0.9183 I(257, 127) = 0.9157 信息期望的数值与分类属性中各类计数之

7、间的比例有关 信息期望的数值与计数总数无关,信息期望？,01:41:26,16,医药信息分析与应用课程组,2. 对测试样例的信息期望,年龄,平均信息期望？,信息期望的减少？,信息期望？,01:41:26,17,医药信息分析与应用课程组,2. 对测试样例的信息期望,信息期望的减少(又称Gain) = 信息期望 平均信息期望,基于节点数据表,基于该节点的所有直系分支数据表,01:41:26,18,医药信息分析与应用课程组,2. 对测试样例的信息期望,平均信息期望，E，是节点各直系分支的信息期望值的加权总和 1）假定选择年龄作树根节点，则： 青年组: I(128,256)=0.9183 中年组: I

8、(256,0)=0 老年组: I(257,127)=0.9157 青年组比例: (128+256)/1024=0.375 中年组比例: 256/1024=0.25 老年组比例: (257+127)/1024=0.375 平均信息期望（加权总和）： E(年龄）= 0.375*0.9183 +0.25*0+0.375*0.9157 = 0.6877 Gain(年龄) = I(641, 383)-E(年龄) =0.9537 0.6877 = 0.2660,平均信息期望？,01:41:26,19,医药信息分析与应用课程组,2. 对测试样例的信息期望,2)假定选择收入作树根节点，则： 高收入组: I(1

9、60,128)=0.9911 中收入组: I(289,191)=0.9697 低收入组: I(192,64)=0.8133 高收入组 比例: 288/1024=0.2813 中收入组比例: 480/1024=0.4687 低收入组比例: 256/1024=0.25 平均信息期望（加权总和）： E(收入）= 0.2813 * 0.9911 + 0.4687 * 0.9697 + 0.25 * 0.8133 = 0.9361 Gain(收入) = I(641, 383)-E(收入) =0.9537 0.9361= 0.0176,平均信息期望？,01:41:26,20,医药信息分析与应用课程组,2.

10、 对测试样例的信息期望,3)假定选择学生作树根节点，则： 学生组: I(420,64)=0.5635 非学生组: I(221,319)=0.9761 学生组比例: 484/1024=0.4727 非学生组比例: 540/1024=0.5273 平均信息期望（加权总和）： E(学生）= 0.4727 * 0.5635 + 0.5273 * 0.9761 = 0.7811 Gain(学生) = I(641, 383)-E(学生) =0.9537 0.7811= 0.1726,平均信息期望？,01:41:26,21,医药信息分析与应用课程组,2. 对测试样例的信息期望,4.假定选择信誉作树根节点，则

11、： 良好组: I(480,192)=0.8631 优秀组: I(161,191)=0.9948 良好组比例: 672/1024=0.6563 优秀组比例: 352/1024=0.3437 平均信息期望（加权总和）： E(信誉）= 0.6563 * 0.8631 + 0.3437 * 0.9948 = 0.9048 Gain(信誉) = I(641, 383)-E(信誉) =0.9537 0.9048= 0.0453,平均信息期望？,01:41:26,22,医药信息分析与应用课程组,2. 对测试样例的信息期望,决定树根节点 E(年龄）= 0.6877， Gain(年龄) = 0.2660 E(收

12、入）= 0.9361，Gain(收入) = 0.0176 E(学生）= 0.7811，Gain(学生) = 0.1726 E(信誉）= 0.9048，Gain(信誉) = 0.0453,01:41:26,23,医药信息分析与应用课程组,3.决策树建立步骤,1)决定分类属性 2)对目前的数据表，建立一个节点N。 3)如果数据表中的数据都属于同一类，N就是树叶，在树叶上标上所属的那一类。 4)如果数据表中没有其他属性可以考虑，N也是树叶，按照少数服从多数的原则在树叶上标上所属类别。 5)否则，根据平均信息期望值E或Gain值选出一个最佳属性作为节点N的测试属性。 6)节点属性选定以后，对于该属性的

13、每一个值： 从N生成一个分支， 并将数据表中与该分支有关的数据收集形成分支节点的数据表，在表中删除节点属性那一栏。 如果分支数据表非空，则运用以上算法从该节点建立子树。,01:41:26,24,医药信息分析与应用课程组,3.决策树建立步骤,年龄,青 中 老,树叶,01:41:27,25,医药信息分析与应用课程组,3.决策树建立步骤,年龄,青 中 老,01:41:27,26,医药信息分析与应用课程组,3.决策树建立步骤,平均信息期望（加权总和）： E(收入）= 0.3333 * 0 + 0.5 * 0.9183 + 0.1667 * 0 = 0.4592 Gain(收入) = I(128, 25

14、6) - E(收入)=0.9183 0.4592 = 0.4591,平均信息期望？,信息期望？,青年组数据表分析： 1. 假定选择收入作节点 I(128,256) = 0.9183,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,01:41:27,27,医药信息分析与应用课程组,3.决策树建立步骤,平均信息期望（加权总和）： E(学生）= 0.3333 * 0 + 0.6667 * 0 = 0 Gain(学生) = I(128, 256) - E(学生)=0.9

15、183 0 = 0.9183 结论: 不需要考虑属性信誉，决定选择属性学生,信息期望？,青年组数据表分析： 2. 假定选择学生作节点 I(128,256) = 0.9183,I(128,0)=0 比例: 128/384=0.3333 I(0,256)=0 比例: 256/384=0.6667,平均信息期望？,01:41:27,28,医药信息分析与应用课程组,3.决策树建立步骤,年龄,青 中 老,学生,否 是,树叶,01:41:27,29,医药信息分析与应用课程组,3.决策树建立步骤,年龄,青 中 老,学生,否 是,01:41:27,30,医药信息分析与应用课程组,3.决策树建立步骤,平均信息期

16、望（加权总和）： E(收入）= 0.3333 * 1 + 0.6667 * 0.8050 = 0.8700 Gain(收入) = I(257, 127) - E(收入)=0.9157 0.8700 = 0.0457,信息期望？,老年组数据表分析： 1. 假定选择收入作节点 I(257,127) = 0.9157,I(64,64)=1 比例: 128/384=0.3333 I(193,63)=0.8050 比例: 256/384=0.6667,平均信息期望？,01:41:27,31,医药信息分析与应用课程组,3.决策树建立步骤,平均信息期望（加权总和）： E(学生）= 0.6771 * 0.80

17、51 + 0.3229 * 0.9998 = 0.8680 Gain(学生) = I(257, 127) - E(学生)=0.9157 0.8680= 0.0477,信息期望？,老年组数据表分析： 2. 假定选择学生作节点 I(257,127) = 0.9157,I(196,64)=0.8051 比例: 260/384=0.6771 I(61,63)=0.9998 比例: 124/384=0.3229,平均信息期望？,01:41:27,32,医药信息分析与应用课程组,3.决策树建立步骤,平均信息期望（加权总和）： E(信誉）= 0.6667 * 0 + 0.3333 * 0.0659 = 0.

18、0220 Gain(信誉) = I(257, 127) - E(信誉)=0.9157 0.0220 = 0.8937 结论: 决定选择属性信誉,信息期望？,老年组数据表分析： 3. 假定选择信誉作节点 I(257,127) = 0.9157,I(256,0)=0 比例: 256/384=0.6667 I(1,127)=0.0659 比例: 128/384=0.3333,平均信息期望？,01:41:27,33,医药信息分析与应用课程组,3.决策树建立步骤,年龄,青 中 老,学生,否 是,信誉,优 良,树叶,01:41:27,34,医药信息分析与应用课程组,3.决策树建立步骤,年龄,青 中 老,学生,否 是,信誉,优 良,01:41:27,35,医药信息分析与应用课程组,三、决策树的建立- 讨论,信息期望值（评价函数）的其他计算方法 min(p1, p2, , pm ) m * (p1* p2* *pm ) p1 log(p1) + p2 log(p2) + + pm log(pm) 他们的共同特点：当数据对所考察的归类属性均匀分