第6章 ID3决策树.ppt

第6章 ID3决策树分类算法主讲教师：唐德玉本结要点一、引言二、什么是决策树三、决策树的建立（ID3算法）四、Microsoft SQL Server 2005实践决策树五、决策树的数据准备2*你能判定他/她买计算机的可能性大不大吗？3医 药信息分析与应用课程组 姓名姓名年龄年龄收入收入学生学生信誉信誉电话电话地址地址邮编邮编买计算买计算机机张三张三234000是是良良281-322-03282714 Ave.M77388买买李四李四342800否否优优713-239-78305606 Holly Cr78766买买王二王二701900否否优优281-242-32222000 Bell Blvd.70244不买不买赵五赵五18900是是良良281-550-0544100 Main Street70244买买刘兰刘兰342500否否优优713-239-7430606 Holly Ct78566买买杨俊杨俊278900否否优优281-355-7990233 Rice Blvd.70388不买不买张毅张毅389500否否优优281-556-0544399 Sugar Rd.78244买买*一、引例决策树的用途4医药信息分析与应用课程组计数计数年龄年龄收入收入学生学生信誉信誉归类：买归类：买计算机？计算机？64青青高高否否良良不买不买64青青高高否否优优不买不买128中中高高否否良良买买60老老中中否否良良买买64老老低低是是良良买买64老老低低是是优优不买不买64中中低低是是优优买买128青青中中否否良良不买不买64青青低低是是良良买买132老老中中是是良良买买64青青中中是是优优买买32中中中中否否优优买买32中中高高是是良良买买63老老中中否否优优不买不买1 老老中中否否优优买买假定公司收集了左表数据，假定公司收集了左表数据，那么对于任意给定的客人那么对于任意给定的客人（测试样例），你能帮助公（测试样例），你能帮助公司将这位客人归类吗？司将这位客人归类吗？即：你能预测这位客人是属即：你能预测这位客人是属于于“买买”计算机的那一类，计算机的那一类，还是属于还是属于“不买不买”计算机的计算机的那一类？那一类？又：你需要多少有关这位客又：你需要多少有关这位客人的信息才能回答这个问题人的信息才能回答这个问题？决策树可以帮助你解决决策树可以帮助你解决好好这这个问题个问题*决策树的用途*5医药信息分析与应用课程组计数计数年龄年龄收入收入学生学生信誉信誉归类：买归类：买计算机？计算机？64青青高高否否良良不买不买64青青高高否否优优不买不买128中中高高否否良良买买60老老中中否否良良买买64老老低低是是良良买买64老老低低是是优优不买不买64中中低低是是优优买买128青青中中否否良良不买不买64青青低低是是良良买买132老老中中是是良良买买64青青中中是是优优买买32中中中中否否优优买买32中中高高是是良良买买63老老中中否否优优不买不买1 老老中中否否优优买买谁在买计算机？谁在买计算机？他他/她会买计算机吗？她会买计算机吗？年龄？年龄？学生？学生？信誉？信誉？买买青青中中老老否否是是优优良良不买不买买买买买不买不买决策树的用途*6医药信息分析与应用课程组一棵很糟糕的决策树一棵很糟糕的决策树收入？收入？学生？学生？青中否是高低中信誉？信誉？良优年龄？年龄？不买不买买买买买不买不买计数计数年龄年龄收入收入学生学生信誉信誉归类：买归类：买计算机？计算机？64青青高高否否良良不买不买64青青高高否否优优不买不买128中中高高否否良良买买60老老中中否否良良买买64老老低低是是良良买买64老老低低是是优优不买不买64中中低低是是优优买买128青青中中否否良良不买不买64青青低低是是良良买买132老老中中是是良良买买64青青中中是是优优买买32中中中中否否优优买买32中中高高是是良良买买63老老中中否否优优不买不买1 老老中中否否优优买买二、什么是决策树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 represent classes or class distributions.*7医药信息分析与应用课程组年龄年龄？学生？学生？信誉？信誉？买买青青中中老老否否是是优优良良否否买买买买否否三、决策树的建立1.决策树建立的关键2.对测试样例的信息期望(The expected information needed to classify a given sample(中文可能称：评价函数)w信息期望 的分析与计算w平均信息期望w信息期望的减少（Gain）3.决策树建立步骤（例）*8医药信息分析与应用课程组1.决策树建立的关键1、决策树建立的关键*9医药信息分析与应用课程组树根？树根？建立一个好的决建立一个好的决策树的关键是决策树的关键是决定树根和子树根定树根和子树根的属性的属性计数计数年龄年龄收入收入学生学生信誉信誉归类：买归类：买计算机？计算机？64青青高高否否良良不买不买64青青高高否否优优不买不买128中中高高否否良良买买60老老中中否否良良买买64老老低低是是良良买买64老老低低是是优优不买不买64中中低低是是优优买买128青青中中否否良良不买不买64青青低低是是良良买买132老老中中是是良良买买64青青中中是是优优买买32中中中中否否优优买买32中中高高是是良良买买63老老中中否否优优不买不买1 老老中中否否优优买买*10医药信息分析与应用课程组年龄年龄计计数数年年龄龄收收入入学学生生信信誉誉归类：买计算归类：买计算机？机？64青青高高否否良良不买不买64青青高高否否优优不买不买128青青中中否否良良不买不买64青青低低是是良良买买64青青中中是是优优买买计数计数年龄年龄收入收入学生学生信誉信誉归类：买计算机？归类：买计算机？128中中高高否否良良买买64中中低低是是优优买买32中中中中否否优优买买32中中高高是是良良买买计数计数年龄年龄收入收入学生学生信誉信誉归类：买计算机？归类：买计算机？60老老中中否否良良买买64老老低低是是良良买买64老老低低是是优优不买不买132老老中中是是良良买买63老老中中否否优优不买不买1 老老中中否否优优买买青青中中老老1.决策树建立的关键2.对测试样例的信息期望张三属于哪一类？为了回答该问题，对张三的信息期望值是多少？*11医药信息分析与应用课程组年年龄龄计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买计数年龄收入学生信誉归类：买计算机？归类：买计算机？128中高否良买64中低是优买32中中否优买32中高是良买计数年龄收入学生信誉归类：买计算机？归类：买计算机？60老中否良买64老低是良买64老低是优不买132老中是良买63老中否优不买1 老中否优买*12医药信息分析与应用课程组年年龄龄计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买计数年龄收入学生信誉归类：买计算机？归类：买计算机？128中高否良买64中低是优买32中中否优买32中高是良买计数年龄收入学生信誉归类：买计算机？归类：买计算机？60老中否良买64老低是良买64老低是优不买132老中是良买63老中否优不买1 老中否优买2.对测试样例的信息期望2.2.对测试样例的信息期望对测试样例的信息期望让我们称所需要研究的属性为“分类属性”。假设该属性共分m类，而它们每一类在数据表中计数的总和分别为s1,s2,sm。令 s=s1+s2+sm那么对于任一样例，决定它所属类别的信息期望可以用下面的公式来计算：I(s1,s2,sm)=-pi log2(pi)其中 pi=si/s*13医药信息分析与应用课程组 i=1m计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买*14医药信息分析与应用课程组例：左表分类属性：买计算机？该属性共分两类(m=2):买/不买s1=641,s2=383s=s1+s2=1024p1=s1/s=641/1024=0.6260p2=s2/s=383/1024=0.3740 I(s1,s2)=I(641,383)=-(p1 log2(p1)+p2 log2(p2)=0.95372.对测试样例的信息期望计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买*15医药信息分析与应用课程组2.对测试样例的信息期望讨论：“买”/“不买”计算机的人数之间的比例对于信息期望值的影响I(641,383)=0.9537I(512,512)=I(4,4)=1I(51,973)=I(973,51)=0.2856I(0,1024)=I(256,0)=0I(128,256)=0.9183I(257,127)=0.9157信息期望的数值与分类属性中各类计数之间的比例有关信息期望的数值与计数总数无关计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买*16医药信息分析与应用课程组2.对测试样例的信息期望年年龄龄计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买计数年龄收入学生信誉归类：买计算机？归类：买计算机？128中高否良买64中低是优买32中中否优买32中高是良买计数年龄收入学生信誉归类：买计算机？归类：买计算机？60老中否良买64老低是良买64老低是优不买132老中是良买63老中否优不买1 老中否优买*17医药信息分析与应用课程组2.对测试样例的信息期望信息期望的减少信息期望的减少(又称又称Gain)=信息期望信息期望 平均信息期望平均信息期望 基于节点数据表基于节点数据表基于该节点的所有直系基于该节点的所有直系分支数据表分支数据表*18医药信息分析与应用课程组2.对测试样例的信息期望平均信息期望，E，是节点各直系分支的信息期望值的加权总和1）假定选择年龄作树根节点，则：青年组:I(128,256)=0.9183中年组:I(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.6877Gain(年龄)=I(641,383)-E(年龄)=0.9537 0.6877=0.2660计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买计数年龄收入学生信誉归类：买计算机？归类：买计算机？128中高否良买64中低是优买32中中否优买32中高是良买计数年龄收入学生信誉归类：买计算机？归类：买计算机？60老中否良买64老低是良买64老低是优不买132老中是良买63老中否优不买1 老中否优买*19医药信息分析与应用课程组2.对测试样例的信息期望2)假定选择收入作树根节点，则：高收入组:I(160,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.9361Gain(收入)=I(641,383)-E(收入)=0.9537 0.9361=0.0176计数年龄收入学生信誉归类：买计算机？归类：买计算机？60老中否良买128青中否良不买132老中是良买64青中是优买32中中否优买63老中否优不买1 老中否优买计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买32中高是良买计数年龄收入学生信誉归类：买计算机？归类：买计算机？64老低是良买64老低是优不买64中低是优买64青低是良买*20医药信息分析与应用课程组2.对测试样例的信息期望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.7811Gain(学生)=I(641,383)-E(学生)=0.9537 0.7811=0.1726计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买128青中否良不买32中中否优买63老中否优不买1 老中否优买计数年龄收入学生信誉归类：买计算机？归类：买计算机？64老低是良买64老低是优不买64中低是优买64青低是良买132老中是良买64青中是优买32中高是良买*21医药信息分析与应用课程组2.对测试样例的信息期望4.假定选择信誉作树根节点，则：良好组: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.9048Gain(信誉)=I(641,383)-E(信誉)=0.9537 0.9048=0.0453计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否优不买64老低是优不买64中低是优买64青中是优买32中中否优买63老中否优不买1 老中否优买计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买128中高否良买60老中否良买64老低是良买128青中否良不买64青低是良买132老中是良买32中高是良买*22医药信息分析与应用课程组2.对测试样例的信息期望决定树根节点 E(年龄）=0.6877，Gain(年龄)=0.2660E(收入）=0.9361，Gain(收入)=0.0176E(学生）=0.7811，Gain(学生)=0.1726E(信誉）=0.9048，Gain(信誉)=0.0453*23医药信息分析与应用课程组3.决策树建立步骤1)决定分类属性2)对目前的数据表，建立一个节点N。3)如果数据表中的数据都属于同一类，N就是树叶，在树叶上标上所属的那一类。4)如果数据表中没有其他属性可以考虑，N也是树叶，按照少数服从多数的原则在树叶上标上所属类别。5)否则，根据平均信息期望值E或Gain值选出一个最佳属性作为节点N的测试属性。6)节点属性选定以后，对于该属性的每一个值：w从N生成一个分支，并将数据表中与该分支有关的数据收集形成分支节点的数据表，在表中删除节点属性那一栏。w如果分支数据表非空，则运用以上算法从该节点建立子树。*24医药信息分析与应用课程组3.决策树建立步骤年龄计数收入学生信誉归类：买计算机？归类：买计算机？64高否良不买64高否优不买128中否良不买64低是良买64中是优买计数收入学生信誉归类：买计算机？归类：买计算机？60中否良买64低是良买64低是优不买132中是良买63中否优不买1 中否优买青 中 老树叶计数收入学生信誉归类：买计算机？归类：买计算机？128高否良买64低是优买32中否优买32高是良买*25医药信息分析与应用课程组3.决策树建立步骤年龄计数收入学生信誉归类：买计算机？归类：买计算机？64高否良不买64高否优不买128中否良不买64低是良买64中是优买计数收入学生信誉归类：买计算机？归类：买计算机？60中否良买64低是良买64低是优不买132中是良买63中否优不买1 中否优买青 中 老买*26医药信息分析与应用课程组3.决策树建立步骤平均信息期望（加权总和）：E(收入）=0.3333*0+0.5*0.9183+0.1667*0=0.4592Gain(收入)=I(128,256)-E(收入)=0.9183 0.4592=0.4591计数收入学生信誉归类：买计算机？归类：买计算机？64高否良不买64高否优不买128中否良不买64低是良买64中是优买计数收入学生信誉归类：买计算机？归类：买计算机？64高否良不买64高否优不买计数收入学生信誉归类：买计算机？归类：买计算机？128中否良不买64中是优买计数收入学生信誉归类：买计算机？归类：买计算机？64低是良买青年组数据表分析：青年组数据表分析：1.假定选择收入作节点假定选择收入作节点I(128,256)=0.9183I(0,128)=0 比例比例:128/384=0.3333I(64,128)=0.9183 比例比例:192/384=0.5I(64,0)=0比例比例:64/384=0.1667*27医药信息分析与应用课程组3.决策树建立步骤平均信息期望（加权总和）：E(学生）=0.3333*0+0.6667*0=0Gain(学生)=I(128,256)-E(学生)=0.9183 0=0.9183结论:不需要考虑属性信誉，决定选择属性学生计数收入学生信誉归类：买计算机？归类：买计算机？64高否良不买64高否优不买128中否良不买64低是良买64中是优买青年组数据表分析：青年组数据表分析：2.假定选择学生作节点假定选择学生作节点I(128,256)=0.9183I(128,0)=0 比例比例:128/384=0.3333I(0,256)=0 比例比例:256/384=0.6667计数收入学生信誉归类：买计算机？归类：买计算机？64高否良不买64高否优不买128中否良不买计数收入学生信誉归类：买计算机？归类：买计算机？64低是良买64中是优买*28医药信息分析与应用课程组3.决策树建立步骤年龄计数收入信誉归类：买计算机？归类：买计算机？64低良买64中优买计数收入学生信誉归类：买计算机？归类：买计算机？60中否良买64低是良买64低是优不买132中是良买63中否优不买1 中否优买青 中 老买学生计数收入信誉归类：买计算机？归类：买计算机？64高良不买64高优不买128中良不买否 是树叶*29医药信息分析与应用课程组3.决策树建立步骤年龄计数收入学生信誉归类：买计算机？归类：买计算机？60中否良买64低是良买64低是优不买132中是良买63中否优不买1 中否优买青 中 老买学生否 是买不买*30医药信息分析与应用课程组3.决策树建立步骤平均信息期望（加权总和）：E(收入）=0.3333*1+0.6667*0.8050=0.8700Gain(收入)=I(257,127)-E(收入)=0.9157 0.8700=0.0457老年组数据表分析：老年组数据表分析：1.假定选择收入作节点假定选择收入作节点I(257,127)=0.9157I(64,64)=1 比例比例:128/384=0.3333I(193,63)=0.8050 比例比例:256/384=0.6667计数收入学生信誉归类：买计算机？归类：买计算机？60中否良买64低是良买64低是优不买132中是良买63中否优不买1 中否优买计数收入学生信誉归类：买计算机？归类：买计算机？60中否良买132中是良买63中否优不买1 中否优买计数收入学生信誉归类：买计算机？归类：买计算机？64低是良买64低是优不买*31医药信息分析与应用课程组3.决策树建立步骤平均信息期望（加权总和）：E(学生）=0.6771*0.8051+0.3229*0.9998=0.8680Gain(学生)=I(257,127)-E(学生)=0.9157 0.8680=0.0477老年组数据表分析：老年组数据表分析：2.假定选择学生作节点假定选择学生作节点I(257,127)=0.9157I(196,64)=0.8051 比例比例:260/384=0.6771 I(61,63)=0.9998比例比例:124/384=0.3229计数收入学生信誉归类：买计算机？归类：买计算机？60中否良买64低是良买64低是优不买132中是良买63中否优不买1 中否优买计数收入学生信誉归类：买计算机？归类：买计算机？60中否良买63中否优不买1 中否优买计数收入学生信誉归类：买计算机？归类：买计算机？64低是良买64低是优不买132中是良买*32医药信息分析与应用课程组3.决策树建立步骤平均信息期望（加权总和）：E(信誉）=0.6667*0+0.3333*0.0659=0.0220Gain(信誉)=I(257,127)-E(信誉)=0.9157 0.0220=0.8937结论:决定选择属性信誉老年组数据表分析：老年组数据表分析：3.假定选择信誉作节点假定选择信誉作节点I(257,127)=0.9157I(256,0)=0比例比例:256/384=0.6667 I(1,127)=0.0659比例比例:128/384=0.3333计数收入学生信誉归类：买计算机？归类：买计算机？60中否良买64低是良买64低是优不买132中是良买63中否优不买1 中否优买计数收入学生信誉归类：买计算机？归类：买计算机？64低是优不买63中否优不买1 中否优买计数收入学生信誉归类：买计算机？归类：买计算机？60中否良买64低是良买132中是良买*33医药信息分析与应用课程组3.决策树建立步骤年龄计数收入学生归类：买计算机？归类：买计算机？60中否买64低是买132中是买青 中 老买学生否 是买不买信誉计数收入学生归类：买计算机？归类：买计算机？64低是不买63中否不买1 中否买优 良树叶*34医药信息分析与应用课程组3.决策树建立步骤年龄青 中 老买学生否 是买不买信誉计数收入学生归类：买计算机？归类：买计算机？64低是不买63中否不买1 中否买优 良买*35医药信息分析与应用课程组三、决策树的建立-讨论信息期望值（评价函数）的其他计算方法min(p1,p2,pm)m*(p1*p2*pm)p1 log(p1)+p2 log(p2)+pm log(pm)他们的共同特点：当数据对所考察的归类属性均匀分布的时候，绝对值最大，当有一类个数为零时，值为零。决策树的剪枝决策树的优化买良否中老60买良否高中128不买优否高青64不买良否高青64归类：买计算机？归类：买计算机？信誉学生收入年龄计数*36医药信息分析与应用课程组决策树的数据准备姓名姓名年龄年龄收入收入学生学生信誉信誉电话电话地址地址邮编邮编买计算机买计算机张三张三234000是是良良281-322-03282714 Ave.M77388买买李四李四342800否否优优713-239-78305606 Holly Cr78766买买王二王二701900否否优优281-242-32222000 Bell Blvd.70244不买不买赵五赵五18900是是良良281-550-0544100 Main Street70244买买刘兰刘兰342500否否优优713-239-7430606 Holly Ct78566买买杨俊杨俊278900否否优优281-355-7990233 Rice Blvd.70388不买不买张毅张毅389500否否优优281-556-0544399 Sugar Rd.78244买买计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买四、Microsoft SQL Server 2005实践决策树1.建立数据库2.导入数据3.建立数据挖掘模型4.数据挖掘查看器*37医药信息分析与应用课程组五、决策树的数据准备数据调查表的设计与整理Data cleaning删除/减少noise，补填missing valuesData transformation数据标准化（data normalization）数据归纳（generalize data to higher-level concepts using concept hierarchies）例如：年龄归纳为老、中、青三类控制每个属性的可能值不超过七种（最好不超过五种）Relevance analysis对于与问题无关的属性：删对于属性的可能值大于七种又不能归纳的属性：删*38医药信息分析与应用课程组*39医药信息分析与应用课程组RecommendationJiawei Han etc.Data Mining:Concepts and Techniques,Morgan Kaufmann PublisherThank You