决策树培训 课件

DataMiningTool

－DecisionTree福建省粒计算及其应用重点实验室赵红2014年11月DataMiningTool

－Decision提要数据挖掘简介决策树的用途决策树的建立（ID3）C4.5示例WekaJ48源码解析212/25/2022提要212/20/2022数据挖掘简介谁加何种类型的油？3姓名年龄收入种族信誉电话地址加何种油张三234000亚裔良281-322-03282714Ave.MSupreme李四342800白人优713-239-78305606HollyCrRegular王二701900西班牙优281-242-32222000BellBlvd.Plus赵五18900非洲良281-550-0544100MainStreetSupreme刘兰342500白人优713-239-7430606HollyCtRegular杨俊278900亚裔优281-355-7990233RiceBlvd.Plus张毅389500亚裔优281-556-0544399SugarRd.Regular……数据挖掘简介谁加何种类型的油？3姓名年龄收入种族信誉电话地址数据挖掘简介你能判定他/她买计算机的可能性大不大吗？412/25/2022姓名年龄收入学生信誉电话地址邮编买计算机张三234000是良281-322-03282714Ave.M77388买李四342800否优713-239-78305606HollyCr78766买王二701900否优281-242-32222000BellBlvd.70244不买赵五18900是良281-550-0544100MainStreet70244买刘兰342500否优713-239-7430606HollyCt78566买杨俊278900否优281-355-7990233RiceBlvd.70388不买张毅389500否优281-556-0544399SugarRd.78244买……数据挖掘简介你能判定他/她买计算机的可能性大不大吗？412/数据挖掘简介我们拥有什么:Hugeamountofdata(GTE:1TB/day)我们需要什么:Informationandknowledge我们应该怎么办:Datamining512/25/2022数据挖掘简介我们拥有什么:512/20/2022排名挖掘主题算法得票数发表时间作者陈述人1分类C4.5611993Quinlan,J.RHiroshiMotoda2聚类k-Means601967MacQueen,J.BJoydeepGhosh3统计学习SVM581995Vapnik,V.NQiangYang4关联分析Apriori521994RakeshAgrawalChristosFaloutsos5统计学习EM482000McLachlan,GJoydeepGhosh6链接挖掘PageRank461998Brin,S.ChristosFaloutsos7集装与推进AdaBoost451997Freund,Y.Zhi-HuaZhou8分类kNN451996Hastie,TVipinKumar9分类NaïveBayes452001Hand,D.JQiangYang10分类CART341984L.BreimanDanSteinberg数据挖掘10大算法ICDM2006Panel(会议的专题讨论)共有145人选出了数据挖掘10大算法。排名挖掘主题算法得票数发表时间作者陈述人1分类C4.5611建立分类模型的一般方法建立分类模型的一般方法决策树的用途新顾客（测试样例），你能帮助公司将这位客人归类吗？即：你能预测这位顾客是属于“买、不买”计算机的那一类？又：你需要多少有关这位客人的信息才能回答这个问题？812/25/2022计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买决策树的用途新顾客（测试样例），你能帮助公司将这位客人归类吗决策树的用途912/25/2022谁在买计算机？他/她会买计算机吗？年龄？学生？信誉？买青中老否是优良不买买买不买计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买决策树的用途912/20/2022谁在买计算机？他/她会买计决策树的用途1012/25/2022一棵很糟糕的决策树收入？学生？青中否是高低中信誉？良优年龄？不买买买不买计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买决策树的用途1012/20/2022一棵很糟糕的决策树收入？决策树的用途什么是决策树Adecisiontreeisaflow-chart-liketreestructureEachinternalnodedenotesatestonanattributeEachbranchrepresentsanoutcomeofthetestLeafnodesrepresentclassesorclassdistributions.1112/25/2022年龄？学生？信誉？买青中老否是优良不买买买不买决策树的用途什么是决策树1112/20/2022年龄？学生？决策树的建立决策树建立的关键对测试样例的信息期望(信息熵)信息期望的分析与计算平均信息期望信息期望的减少（信息增益）决策树建立步骤（例）1212/25/2022决策树的建立决策树建立的关键1212/20/2022补充：信息熵例子例如：桌子甲上有10个水果。其中，有2个为苹果，有8个为橘子。桌子乙上有10个水果。其中，有5个为苹果，有5个为橘子。从直观上感觉:桌子甲上的水果分类比较集中于橘子。桌子乙上的水果分类，比较均匀。因此我们说桌子甲上的水果分类比较纯。桌子乙上的水果分类比较混乱。1312/25/2022补充：信息熵例子例如：1312/20/2022补充：信息熵熵——系统凌乱程度的度量。凌乱程度在同一个集合中，分类越集中于某一类，越不凌乱；分类越均匀分散于不同的类，则越凌乱。通俗说法：不确定性越大，熵也就越大；把它搞清楚所需要的信息量也就越大。1412/25/2022补充：信息熵熵——系统凌乱程度的度量。1412/20/202补充：关于某布尔分类的熵函数S为某正反样例的样例集（布尔分类）S的所有成员属于同一类，Entropy(S)=0；S的正反样例数量相等，Entropy(S)=1；S的正反样例数量不等，熵介于0和1之间补充：关于某布尔分类的熵函数S为某正反样例的样例集（布尔分类补充：更一般的熵定义更一般地，如果目标属性具有c个不同的值，那么S相对于c个状态的分类的熵定义为：其中，pi是S中属于类别i的比例。如果目标属性具有c个可能值，那么熵最大可能为log2c。补充：更一般的熵定义更一般地，如果目标属性具有c个不同的值，补充：用信息增益度量期望的熵降低信息增益是定义属性分类训练数据的能力的度量标准。简单地说，一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低。更精确地讲，一个属性A相对样例集合S的信息增益Gain(S,A)，被定义为：其中，Values(A)是属性A所有可能值的集合，Sv是S中属性A的值为v的子集。补充：用信息增益度量期望的熵降低信息增益是定义属性分类训练数决策树的建立--决策树建立的关键建立一个好的决策树的关键是决定树根和子树根的属性1812/25/2022树根？计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买决策树的建立--决策树建立的关键建立一个好的决策树的关键是决策树的建立--对测试样例的信息期望信息期望？张三属于哪一类？为了回答该问题，对张三的信息期望值是多少？1912/25/2022年龄计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买计数年龄收入学生信誉归类：买计算机？128中高否良买64中低是优买32中中否优买32中高是良买计数年龄收入学生信誉归类：买计算机？60老中否良买64老低是良买64老低是优不买132老中是良买63老中否优不买1老中否优买计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买决策树的建立--对测试样例的信息期望信息期望？张三属于哪一决策树的建立--对测试样例的信息期望所需要研究的属性为“分类属性”假设该属性共分m类，每一类的个数分别为

s1,s2…,sm令s=s1+s2+…+sm决定测试样例所属类别的信息期望：I(s1,s2…,sm)=-pi

log2(pi)其中pi

=si/s2012/25/2022i=1m决策树的建立--对测试样例的信息期望所需要研究的属性为“分类决策树的建立--例分类属性：买计算机？该属性共分两类(m=2):买/不买s1=641,s2=383

s=s1+s2=1024p1=s1/s=641/1024=0.6260

p2=s2/s=383/1024=0.3740I(s1,s2)=I(641,383)

=-(p1

log2(p1)+p2

log2(p2))

=0.95372112/25/2022决策树的建立--例分类属性：买计算机？2112/20/202决策树的建立--对测试样例的信息期望讨论：“买”/“不买”计算机的人数之间的比例对于信息期望值的影响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信息期望的数值与分类属性中各类计数之间的比例有关信息期望的数值与计数总数无关2212/25/2022决策树的建立--对测试样例的信息期望讨论：“买”/“不买”决策树的建立--对测试样例的信息期望例：分类属性：加何种油？该属性共分三类(m=3):Regular/Plus/Supremes1=13300,s2=7300,s3=5200

s=s1+s2+s3=25800p1=s1/s=13300/25800=0.5155

p2=s2/s=7300/25800=0.2829

p3=s3/s=5200/25800=0.2016I(s1,s2,s3)=I(13300,7300,5200)

=-(p1log2(p1)+p2log2(p2)+p3log2(p3))

=1.47392312/25/2022计数年龄收入种族信誉加何种油2000老低亚裔良Supreme1500老高白人良Regular3900中中西班牙良Plus3200中低非洲优Supreme5200青高白人优Regular1800青中亚裔优Plus2400青高亚裔良Regular2200青高非洲优Regular1600老中西班牙良Plus2000青高西班牙良Regular决策树的建立--对测试样例的信息期望例：分类属性：加何种油决策树的建立--对测试样例的信息期望讨论：三种汽油购买人数之间的比例对于需解决的信息量的影响

I(13300,7300,5200)=1.4739

I(25800,0,0)=0

I(0,10,0)=0

I(641,383,0)=0.9537

I(900,100,24)=0.6183

I(64,64,64)=1.5850当分类属性的种类增加时，对测试样例的信息期望通常也相应增加。2412/25/2022决策树的建立--对测试样例的信息期望讨论：三种汽油购买人数决策树的建立--对测试样例的信息期望信息期望？平均信息期望？2512/25/2022年龄计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买计数年龄收入学生信誉归类：买计算机？128中高否良买64中低是优买32中中否优买32中高是良买计数年龄收入学生信誉归类：买计算机？60老中否良买64老低是良买64老低是优不买132老中是良买63老中否优不买1老中否优买信息期望的减少？计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买决策树的建立--对测试样例的信息期望信息期望？平均信息期望决策树的建立--对测试样例的信息期望信息期望的减少(又称Gain，信息增益)=信息期望–平均信息期望信息期望基于节点数据表平均信息期望基于该节点的所有直系分支数据表2612/25/2022决策树的建立--对测试样例的信息期望信息期望的减少(又称G决策树的建立--对测试样例的信息期望平均信息期望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.26602712/25/2022计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买计数年龄收入学生信誉归类：买计算机？128中高否良买64中低是优买32中中否优买32中高是良买计数年龄收入学生信誉归类：买计算机？60老中否良买64老低是良买64老低是优不买132老中是良买63老中否优不买1老中否优买决策树的建立--对测试样例的信息期望平均信息期望E，是节点决策树的建立--对测试样例的信息期望2. 假定选择收入作树根节点，则： 高收入组:I(160,128)=0.9911

中收入组:I(289,191)=0.9697

低收入组:I(192,64)=0.8113

高收入组比例:288/1024=0.2813

中收入组比例:480/1024=0.4687

低收入组比例:256/1024=0.25平均信息期望（加权总和）：E(收入）=0.2813*0.9911+0.4687*0.9697+0.25*0.8113=0.9361Gain(收入)：I(641,383)-E(收入)=0.9537–0.9361=0.01762812/25/2022决策树的建立--对测试样例的信息期望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.17262912/25/2022决策树的建立--对测试样例的信息期望3. 假定选择学生作树决策树的建立--对测试样例的信息期望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.04533012/25/2022决策树的建立--对测试样例的信息期望4. 假定选择信誉作树决策树的建立--对测试样例的信息期望决定树根节点E(年龄)=0.6877，Gain(年龄)=0.2660E(收入)=0.9361，Gain(收入)=0.0176E(学生)=0.7811，Gain(学生)=0.1726E(信誉)=0.9048，Gain(信誉)=0.04533112/25/2022决策树的建立--对测试样例的信息期望决定树根节点3112/决策树的建立--决策树建立步骤（例）3212/25/2022年龄计数收入学生信誉归类：买计算机？64高否良不买64高否优不买128中否良不买64低是良买64中是优买计数收入学生信誉归类：买计算机？60中否良买64低是良买64低是优不买132中是良买63中否优不买1中否优买青中老树叶计数收入学生信誉归类：买计算机？128高否良买64低是优买32中否优买32高是良买决策树的建立--决策树建立步骤（例）3212/20/202决策树的建立--决策树建立步骤（例）3312/25/2022年龄计数收入学生信誉归类：买计算机？64高否良不买64高否优不买128中否良不买64低是良买64中是优买计数收入学生信誉归类：买计算机？60中否良买64低是良买64低是优不买132中是良买63中否优不买1中否优买青中老买决策树的建立--决策树建立步骤（例）3312/20/202决策树的建立--青年组数据表分析（例）1.假定选择收入作节点I(128,256)=0.9183E(收入）=0.3333*0+0.5*0.9183+0.1667*0=0.4592Gain(收入)=I(128,256)-E(收入)=0.9183–0.4592=0.4591I(0,128)=0

比例:128/384=0.3333I(64,128)=0.9183

比例:192/384=0.5I(64,0)=0

比例:64/384=0.16673412/25/2022计数收入学生信誉归类：买计算机？64高否良不买64高否优不买128中否良不买64低是良买64中是优买计数收入学生信誉归类：买计算机？64高否良不买64高否优不买计数收入学生信誉归类：买计算机？128中否良不买64中是优买计数收入学生信誉归类：买计算机？64低是良买决策树的建立--青年组数据表分析（例）1.假定选择收入作节决策树的建立--青年组数据表分析（例）2.假定选择学生作节点I(128,256)=0.9183E(学生）=0.3333*0+0.6667*0=0Gain(学生)=I(128,256)-E(学生)=0.9183–0=0.9183I(128,0)=0

比例:128/384=0.3333I(0,256)=0

比例:256/384=0.6667结论:不需要考虑属性信誉，决定选择属性学生3512/25/2022计数收入学生信誉归类：买计算机？64高否良不买64高否优不买128中否良不买64低是良买64中是优买计数收入学生信誉归类：买计算机？64高否良不买64高否优不买128中否良不买计数收入学生信誉归类：买计算机？64低是良买64中是优买决策树的建立--青年组数据表分析（例）2.假定选择学生作节决策树的建立--决策树建立步骤（例）3612/25/2022年龄计数收入信誉归类：买计算机？64低良买64中优买计数收入学生信誉归类：买计算机？60中否良买64低是良买64低是优不买132中是良买63中否优不买1中否优买青中老买学生计数收入信誉归类：买计算机？64高良不买64高优不买128中良不买否是树叶决策树的建立--决策树建立步骤（例）3612/20/202决策树的建立--决策树建立步骤（例）3712/25/2022年龄计数收入学生信誉归类：买计算机？60中否良买64低是良买64低是优不买132中是良买63中否优不买1中否优买青中老买学生否是买不买决策树的建立--决策树建立步骤（例）3712/20/202决策树的建立--老年组数据表分析（例）1.假定选择收入作节点I(257,127)=0.9157E(收入）=0.3333*1+0.6667*0.8050=0.8700Gain(收入)=I(257,127)-E(收入)=0.9157–0.8700=0.0457I(64,64)=1

比例:128/384=0.3333I(193,63)=0.8050

比例:256/384=0.66673812/25/2022计数收入学生信誉归类：买计算机？60中否良买64低是良买64低是优不买132中是良买63中否优不买1中否优买计数收入学生信誉归类：买计算机？60中否良买132中是良买63中否优不买1中否优买计数收入学生信誉归类：买计算机？64低是良买64低是优不买决策树的建立--老年组数据表分析（例）1.假定选择收入作节决策树的建立--老年组数据表分析（例）2.假定选择学生作节点I(257,127)=0.9157E(学生）=0.6771*0.8051+0.3229*0.9998=0.8680Gain(学生)=I(257,127)-E(学生)=0.9157–0.8680=0.0477I(196,64)=0.8051

比例:260/384=0.6771I(61,63)=0.9998

比例:124/384=0.32293912/25/2022计数收入学生信誉归类：买计算机？60中否良买64低是良买64低是优不买132中是良买63中否优不买1中否优买计数收入学生信誉归类：买计算机？60中否良买63中否优不买1中否优买计数收入学生信誉归类：买计算机？64低是良买64低是优不买132中是良买决策树的建立--老年组数据表分析（例）2.假定选择学生作节决策树的建立--老年组数据表分析（例）3.假定选择信誉作节点I(257,127)=0.9157E(信誉）=0.6667*0+0.3333*0.0659=0.0220Gain(信誉)=I(257,127)-E(信誉)=0.9157–0.0220=0.8937I(256,0)=0

比例:256/384=0.6667I(1,127)=0.0659

比例:128/384=0.3333结论:决定选择属性信誉4012/25/2022计数收入学生信誉归类：买计算机？60中否良买64低是良买64低是优不买132中是良买63中否优不买1中否优买计数收入学生信誉归类：买计算机？64低是优不买63中否优不买1中否优买计数收入学生信誉归类：买计算机？60中否良买64低是良买132中是良买决策树的建立--老年组数据表分析（例）3.假定选择信誉作节决策树的建立--决策树建立步骤（例）4112/25/2022年龄计数收入学生归类：买计算机？60中否买64低是买132中是买青中老买学生否是买不买信誉计数收入学生归类：买计算机？64低是不买63中否不买1中否买优良树叶决策树的建立--决策树建立步骤（例）4112/20/202决策树的建立--决策树建立步骤（例）4212/25/2022年龄青中老买学生否是买不买信誉计数收入学生归类：买计算机？64低是不买63中否不买1中否买优良买……决策树的建立--决策树建立步骤（例）4212/20/202决策树算法流程（ID3）选择节点分裂属性；建立新节点，划分数据集；判断节点是否到生长停止条件，如果是，终止生长，如果不是，转到第1步。树停止生长条件节点内的数据已经完全属于同一类别。节点内测数据样本数低于某一阈值。所有属性都已经被分裂过。决策树算法流程（ID3）选择节点分裂属性；从ID3到C4.5从ID3到C4.5共同之处：通过自顶向下构造决策树进行学习；构造过程的开始：哪一个属性将在树的根节点被测试？区别：选择测试属性时的准则ID3:增益准则(Gaincriterion)—衡量给定属性区分训练样例的能力。C4.5:增益率准则(Gainratiocriterion)44从ID3到C4.5从ID3到C4.5共同之处：44ID3信息增益存在的问题由划分个数引起的偏置问题当某个属性具有取值越多=>划分越多=>分块越小，数据纯度可能越高=>进而引起偏置问题当某个属性具有多个取值时，信息增益度量会赋予该属性的有用程度一个不适当的指示。ID3信息增益存在的问题由划分个数引起的偏置问题ID3信息增益存在的问题在极端情况下，比如在是否打高尔夫球的例子中，“日期”这个属性。对于每个实例都取得不同的值。这个属性所形成的划分，使得每个子集都仅有一个实例。根据信息增益的定义，“日期”这个属性将会有信息增益度量值会最高。而实际上，这个属性可能是无关或者无用的。46ID3信息增益存在的问题在极端情况下，比如在是否打高尔夫球的C4.5信息增益率设样本集S按离散属性F的V个不同的取值划分为S1…Sv共V个子集定义Split(S,F)：则用F对S进行划分的信息增益率为：C4.5信息增益率设样本集S按离散属性F的V个不同的取值划分C4.5例属性穿衣指数温度湿度风力天气舒适度1较多35701不舒适2较多33787不舒适3较多34804不舒适4正常32850舒适5正常33855舒适6很多25902不舒适7很多24883不舒适8很多30501舒适9很多32606不舒适10较多26860不舒适48C4.5例属性穿衣指数温度湿度风力天气舒适度1较多35701C4.5例分类属性：天气舒适度？该属性共分两类(m=2):舒适/不舒适s1=3,s2=7

s=s1+s2=10p1=s1/s=0.3

p2=s2/s=0.7I(s1,s2)=I(3,7)

=-(p1

log2(p1)+p2

log2(p2))

=0.8814912/25/2022C4.5例分类属性：天气舒适度？4912/20/2022C4.5例假定选择穿衣指数作树根节点，则： 较多组:I(4,0)=0

正常组:I(2,0)=0

很多组:I(3,1)=-3/4log2(3/4)-1/4log2(1/4)=0.8113

较多组比例:4/10

正常组比例:2/10

很多组比例:4/10平均信息期望（加权总和）：E(穿衣指数)=0+0+0.4*0.8113=0.3255012/25/2022C4.5例假定选择穿衣指数作树根节点，则：5012/20/2C4.5例Gain(穿衣指数)I(3,7)–E(穿衣指数)=0.881–0.325=0.556Split_infor(穿衣指数,S)=-4/10log2(4/10)-4/10log2(4/10)-2/10log2(2/10)=1.522GainRatio(穿衣指数,S)=0.556/1.522

=0.36535112/25/2022C4.5例Gain(穿衣指数)5112/20/2022C4.5例－选划分点242526303232333334355212/25/2022属性穿衣指数温度湿度风力天气舒适度1较多35701不舒适2较多33787不舒适3较多34804不舒适4正常32850舒适5正常33855舒适6很多25902不舒适7很多24883不舒适8很多30501舒适9很多32606不舒适10较多26860不舒适C4.5例－选划分点24252630323233333435C4.5例－选划分点2425263032323333343553E(温度<=24,S)=-9/10*(3/9*log2(3/9)+6/9*log2(6/9))=0.8265Gain(温度<=24,S)I(3,7)–E(温度)=0.881-0.8265=0.0545Split_infor(温度<=24,S)=-9/10*log2(9/10)-1/10*log2(1/10)=0.469GainRatio(温度<=24,S)=0.0545/0.469

=0.116212/25/2022C4.5例－选划分点24252630323233333435C4.5例－选划分点242526303232333334355412/25/2022属性穿衣指数温度湿度风力天气舒适度1较多35701不舒适2较多33787不舒适3较多34804不舒适4正常32850舒适5正常33855舒适6很多25902不舒适7很多24883不舒适8很多30501舒适9很多31606不舒适10较多26860不舒适C4.5例－选划分点24252630323233333435C4.5例－选划分点2425263032323333343555E(温度<=26,S)=-3/10*(3/3*log2(3/3)+0/3)-7/10*(3/7*log2(3/7)+4/7*log2(4/7))=0.6897Gain(温度<=26,S)I(3,7)–E(温度)=0.881-0.6897=0.1913Split_infor(温度<=26,S)=-3/10*log2(3/10)-7/10*log2(7/10)=0.8813GainRatio(温度<=26,S)=0.1913/0.8813

=0.217112/25/2022C4.5例－选划分点24252630323233333435C4.5例－选划分点GainRatio(温度<=24,S)=0.12;GainRatio(温度<=25,S)=0.16;GainRatio(温度<=26,S)=0.217;GainRatio(温度<=30,S)=0.006;GainRatio(温度<=32,S)=0.0057;GainRatio(温度<=33,S)=0.16;GainRatio(温度<=34,S)=0.12;因此，温度26为温度的最佳划分点；信息增益率为0.217.56C4.5例－选划分点GainRatio(温度<=24,SC4.5例－选属性属性“湿度”的信息增益率GainRatio(湿度<=50,S)=0.42.属性“风力”的信息增益率；GainRatio(风力<=1,S)=0.21.GainRatio(湿度<50,S)最大，所以选择湿度作为根节点，最佳划分点为湿度为50%.57C4.5例－选属性属性“湿度”的信息增益率57C4.5比ID3的改进1)用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；

2)能够完成对连续属性的离散化处理；

3)在树构造过程中进行剪枝；

4)能够对不完整数据进行处理。C4.5算法优点：产生的分类规则易于理解，准确率较高。C4.5算法缺点：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。C4.5比ID3的改进1)用信息增益率来选择属性，克服了用福建省粒计算及其应用重点实验室赵红2014年9月C4.5示例

WekaJ48福建省粒计算及其应用重点实验室C4.5示例

WekaJ48C4.5示例数据：weka中的weather数据（字符型、数值型）Arff文件outlook,temperature,humidity,windy,playsunny,hot,high,FALSE,nosunny,hot,high,TRUE,noovercast,hot,high,FALSE,yesrainy,mild,high,FALSE,yesrainy,cool,normal,FALSE,yesrainy,cool,normal,TRUE,noovercast,cool,normal,TRUE,yessunny,mild,high,FALSE,nosunny,cool,normal,FALSE,yesrainy,mild,normal,FALSE,yessunny,mild,normal,TRUE,yesovercast,mild,high,TRUE,yesovercast,hot,normal,FALSE,yesrainy,mild,high,TRUE,nooutlook,temperature,humidity,windy,playsunny,85,85,FALSE,nosunny,80,90,TRUE,noovercast,83,86,FALSE,yesrainy,70,96,FALSE,yesrainy,68,80,FALSE,yesrainy,65,70,TRUE,noovercast,64,65,TRUE,yessunny,72,95,FALSE,nosunny,69,70,FALSE,yesrainy,75,80,FALSE,yessunny,75,70,TRUE,yesovercast,72,90,TRUE,yesovercast,81,75,FALSE,yesrainy,71,91,TRUE,noC4.5示例数据：weka中的weather数据（字符型、数weka中的weather数据（字符型、数值型）outlooktemperaturehumiditywindyplaysunnyhothighFALSEnosunnyhothighTRUEnoovercasthothighFALSEyesrainymildhighFALSEyesrainycoolnormalFALSEyesrainycoolnormalTRUEnoovercastcoolnormalTRUEyessunnymildhighFALSEnosunnycoolnormalFALSEyesrainymildnormalFALSEyessunnymildnormalTRUEyesovercastmildhighTRUEyesovercasthotnormalFALSEyesrainymildhighTRUEnooutlooktemperaturehumiditywindyplaysunny8585FALSEnosunny8090TRUEnoovercast8386FALSEyesrainy7096FALSEyesrainy6880FALSEyesrainy6570TRUEnoovercast6465TRUEyessunny7295FALSEnosunny6970FALSEyesrainy7580FALSEyessunny7570TRUEyesovercast7290TRUEyesovercast8175FALSEyesrainy7191TRUEno61weka中的weather数据（字符型、数值型）outlooC4.5示例WekaJ48C4.5示例WekaJ48WekaJ48算法源码解析WekaJ48算法源码解析WekaJ48算法源码解析高级类J48WekaJ48算法源码解析高级类J48WekaJ48算法源码解析可剪枝的C4.5分类器WekaJ48算法源码解析可剪枝的C4.5分类器WekaJ48算法源码解析分类树WekaJ48算法源码解析分类树WekaJ48算法源码解析分类树WekaJ48算法源码解析分类树WekaJ48算法源码解析C4.5分裂模式WekaJ48算法源码解析C4.5分裂模式WekaJ48算法源码解析C4.5分裂模式WekaJ48算法源码解析C4.5分裂模式WekaJ48算法源码解析C4.5分裂模式WekaJ48算法源码解析C4.5分裂模式WekaJ48算法源码解析选择分裂属性WekaJ48算法源码解析选择分裂属性WekaJ48算法源码解析处理离散属性WekaJ48算法源码解析处理离散属性WekaJ48算法源码解析计算增益WekaJ48算法源码解析计算增益WekaJ48算法源码解析计算增益率WekaJ48算法源码解析计算增益率WekaJ48算法源码解析熵和条件熵WekaJ48算法源码解析熵和条件熵WekaJ48算法源码解析属性熵WekaJ48算法源码解析属性熵WekaJ48算法源码解析处理连续属性WekaJ48算法源码解析处理连续属性WekaJ48算法源码解析处理连续属性WekaJ48算法源码解析处理连续属性WekaJ48算法源码解析处理所有可能的分裂点WekaJ48算法源码解析处理所有可能的分裂点WekaJ48算法源码解析剪枝算法WekaJ48算法源码解析剪枝算法WekaJ48算法源码解析剪枝算法WekaJ48算法源码解析剪枝算法WekaJ48算法源码解析计算错误率WekaJ48算法源码解析计算错误率DataMiningTool

－DecisionTree福建省粒计算及其应用重点实验室赵红2014年11月DataMiningTool

－DecisionDataMiningTool

－DecisionTree福建省粒计算及其应用重点实验室赵红2014年11月DataMiningTool

－Decision提要数据挖掘简介决策树的用途决策树的建立（ID3）C4.5示例WekaJ48源码解析8512/25/2022提要212/20/2022数据挖掘简介谁加何种类型的油？86姓名年龄收入种族信誉电话地址加何种油张三234000亚裔良281-322-03282714Ave.MSupreme李四342800白人优713-239-78305606HollyCrRegular王二701900西班牙优281-242-32222000BellBlvd.Plus赵五18900非洲良281-550-0544100MainStreetSupreme刘兰342500白人优713-239-7430606HollyCtRegular杨俊278900亚裔优281-355-7990233RiceBlvd.Plus张毅389500亚裔优281-556-0544399SugarRd.Regular……数据挖掘简介谁加何种类型的油？3姓名年龄收入种族信誉电话地址数据挖掘简介你能判定他/她买计算机的可能性大不大吗？8712/25/2022姓名年龄收入学生信誉电话地址邮编买计算机张三234000是良281-322-03282714Ave.M77388买李四342800否优713-239-78305606HollyCr78766买王二701900否优281-242-32222000BellBlvd.70244不买赵五18900是良281-550-0544100MainStreet70244买刘兰342500否优713-239-7430606HollyCt78566买杨俊278900否优281-355-7990233RiceBlvd.70388不买张毅389500否优281-556-0544399SugarRd.78244买……数据挖掘简介你能判定他/她买计算机的可能性大不大吗？412/数据挖掘简介我们拥有什么:Hugeamountofdata(GTE:1TB/day)我们需要什么:Informationandknowledge我们应该怎么办:Datamining8812/25/2022数据挖掘简介我们拥有什么:512/20/2022排名挖掘主题算法得票数发表时间作者陈述人1分类C4.5611993Quinlan,J.RHiroshiMotoda2聚类k-Means601967MacQueen,J.BJoydeepGhosh3统计学习SVM581995Vapnik,V.NQiangYang4关联分析Apriori521994RakeshAgrawalChristosFaloutsos5统计学习EM482000McLachlan,GJoydeepGhosh6链接挖掘PageRank461998Brin,S.ChristosFaloutsos7集装与推进AdaBoost451997Freund,Y.Zhi-HuaZhou8分类kNN451996Hastie,TVipinKumar9分类NaïveBayes452001Hand,D.JQiangYang10分类CART341984L.BreimanDanSteinberg数据挖掘10大算法ICDM2006Panel(会议的专题讨论)共有145人选出了数据挖掘10大算法。排名挖掘主题算法得票数发表时间作者陈述人1分类C4.5611建立分类模型的一般方法建立分类模型的一般方法决策树的用途新顾客（测试样例），你能帮助公司将这位客人归类吗？即：你能预测这位顾客是属于“买、不买”计算机的那一类？又：你需要多少有关这位客人的信息才能回答这个问题？9112/25/2022计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买决策树的用途新顾客（测试样例），你能帮助公司将这位客人归类吗决策树的用途9212/25/2022谁在买计算机？他/她会买计算机吗？年龄？学生？信誉？买青中老否是优良不买买买不买计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买决策树的用途912/20/2022谁在买计算机？他/她会买计决策树的用途9312/25/2022一棵很糟糕的决策树收入？学生？青中否是高低中信誉？良优年龄？不买买买不买计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买决策树的用途1012/20/2022一棵很糟糕的决策树收入？决策树的用途什么是决策树Adecisiontreeisaflow-chart-liketreestructureEachinternalnodedenotesatestonanattributeEachbranchrepresentsanoutcomeofthetestLeafnodesrepresentclassesorclassdistributions.9412/25/2022年龄？学生？信誉？买青中老否是优良不买买买不买决策树的用途什么是决策树1112/20/2022年龄？学生？决策树的建立决策树建立的关键对测试样例的信息期望(信息熵)信息期望的分析与计算平均信息期望信息期望的减少（信息增益）决策树建立步骤（例）9512/25/2022决策树的建立决策树建立的关键1212/20/2022补充：信息熵例子例如：桌子甲上有10个水果。其中，有2个为苹果，有8个为橘子。桌子乙上有10个水果。其中，有5个为苹果，有5个为橘子。从直观上感觉:桌子甲上的水果分类比较集中于橘子。桌子乙上的水果分类，比较均匀。因此我们说桌子甲上的水果分类比较纯。桌子乙上的水果分类比较混乱。9612/25/2022补充：信息熵例子例如：1312/20/2022补充：信息熵熵——系统凌乱程度的度量。凌乱程度在同一个集合中，分类越集中于某一类，越不凌乱；分类越均匀分散于不同的类，则越凌乱。通俗说法：不确定性越大，熵也就越大；把它搞清楚所需要的信息量也就越大。9712/25/2022补充：信息熵熵——系统凌乱程度的度量。1412/20/202补充：关于某布尔分类的熵函数S为某正反样例的样例集（布尔分类）S的所有成员属于同一类，Entropy(S)=0；S的正反样例数量相等，Entropy(S)=1；S的正反样例数量不等，熵介于0和1之间补充：关于某布尔分类的熵函数S为某正反样例的样例集（布尔分类补充：更一般的熵定义更一般地，如果目标属性具有c个不同的值，那么S相对于c个状态的分类的熵定义为：其中，pi是S中属于类别i的比例。如果目标属性具有c个可能值，那么熵最大可能为log2c。补充：更一般的熵定义更一般地，如果目标属性具有c个不同的值，补充：用信息增益度量期望的熵降低信息增益是定义属性分类训练数据的能力的度量标准。简单地说，一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低。更精确地讲，一个属性A相对样例集合S的信息增益Gain(S,A)，被定义为：其中，Values(A)是属性A所有可能值的集合，Sv是S中属性A的值为v的子集。补充：用信息增益度量期望的熵降低信息增益是定义属性分类训练数决策树的建立--决策树建立的关键建立一个好的决策树的关键是决定树根和子树根的属性10112/25/2022树根？计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买决策树的建立--决策树建立的关键建立一个好的决策树的关键是决策树的建立--对测试样例的信息期望信息期望？张三属于哪一类？为了回答该问题，对张三的信息期望值是多少？10212/25/2022年龄计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买计数年龄收入学生信誉归类：买计算机？128中高否良买64中低是优买32中中否优买32中高是良买计数年龄收入学生信誉归类：买计算机？60老中否良买64老低是良买64老低是优不买132老中是良买63老中否优不买1老中否优买计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买决策树的建立--对测试样例的信息期望信息期望？张三属于哪一决策树的建立--对测试样例的信息期望所需要研究的属性为“分类属性”假设该属性共分m类，每一类的个数分别为

s1,s2…,sm令s=s1+s2+…+sm决定测试样例所属类别的信息期望：I(s1,s2…,sm)=-pi

log2(pi)其中pi

=si/s10312/25/2022i=1m决策树的建立--对测试样例的信息期望所需要研究的属性为“分类决策树的建立--例分类属性：买计算机？该属性共分两类(m=2):买/不买s1=641,s2=383

s=s1+s2=1024p1=s1/s=641/1024=0.6260

p2=s2/s=383/1024=0.3740I(s1,s2)=I(641,383)

=-(p1

log2(p1)+p2

log2(p2))

=0.953710412/25/2022决策树的建立--例分类属性：买计算机？2112/20/202决策树的建立--对测试样例的信息期望讨论：“买”/“不买”计算机的人数之间的比例对于信息期望值的影响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信息期望的数值与分类属性中各类计数之间的比例有关信息期望的数值与计数总数无关10512/25/2022决策树的建立--对测试样例的信息期望讨论：“买”/“不买”决策树的建立--对测试样例的信息期望例：分类属性：加何种油？该属性共分三类(m=3):Regular/Plus/Supremes1=13300,s2=7300,s3=5200

s=s1+s2+s3=25800p1=s1/s=13300/25800=0.5155

p2=s2/s=7300/25800=0.2829

p3=s3/s=5200/25800=0.2016I(s1,s2,s3)=I(13300,7300,5200)

=-(p1log2(p1)+p2log2(p2)+p3log2(p3))

=1.473910612/25/2022计数年龄收入种族信誉加何种油2000老低亚裔良Supreme150