决策树141118

DataMiningTool－DecisionTree福建省粒计算及其应用重点实验室赵红2014年11月提要数据挖掘简介决策树的用途决策树的建立（ID3）C4.5示例WekaJ48源码解析28/29/2019数据挖掘简介谁加何种类型的油？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……数据挖掘简介你能判定他/她买计算机的可能性大不大吗？48/29/2019姓名年龄收入学生信誉电话地址邮编买计算机张三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买……数据挖掘简介我们拥有什么:Hugeamountofdata(GTE:1TB/day)我们需要什么:Informationandknowledge我们应该怎么办:Datamining58/29/2019排名挖掘主题算法得票数发表时间作者陈述人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大算法。建立分类模型的一般方法ApplyModel归纳推论LearnModel模型TidAttrib1Attrib2Attrib3Class1YesLarge125KNo2NoMedium100KNo3NoSmall70KNo4YesMedium120KNo5NoLarge95KYes6NoMedium60KNo7YesLarge220KNo8NoSmall85KYes9NoMedium75KNo10NoSmall90KYes10TidAttrib1Attrib2Attrib3Class11NoSmall55K?12YesMedium80K?13YesLarge110K?14NoSmall95K?15NoLarge67K?10测试集学习算法训练集决策树的用途新顾客（测试样例），你能帮助公司将这位客人归类吗？即：你能预测这位顾客是属于“买、不买”计算机的那一类？又：你需要多少有关这位客人的信息才能回答这个问题？88/29/2019计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买决策树的用途98/29/2019谁在买计算机？他/她会买计算机吗？年龄？学生？信誉？买青中老否是优良不买买买不买计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买决策树的用途108/29/2019一棵很糟糕的决策树收入？学生？青中否是高低中信誉？良优年龄？不买买买不买计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买决策树的用途什么是决策树Adecisiontreeisaflow-chart-liketreestructureEachinternalnodedenotesatestonanattributeEachbranchrepresentsanoutcomeofthetestLeafnodesrepresentclassesorclassdistributions.118/29/2019年龄？学生？信誉？买青中老否是优良不买买买不买决策树的建立决策树建立的关键对测试样例的信息期望(信息熵)信息期望的分析与计算平均信息期望信息期望的减少（信息增益）决策树建立步骤（例）128/29/2019补充：信息熵例子例如：桌子甲上有10个水果。其中，有2个为苹果，有8个为橘子。桌子乙上有10个水果。其中，有5个为苹果，有5个为橘子。从直观上感觉:桌子甲上的水果分类比较集中于橘子。桌子乙上的水果分类，比较均匀。因此我们说桌子甲上的水果分类比较纯。桌子乙上的水果分类比较混乱。138/29/2019补充：信息熵熵——系统凌乱程度的度量。凌乱程度在同一个集合中，分类越集中于某一类，越不凌乱；分类越均匀分散于不同的类，则越凌乱。通俗说法：不确定性越大，熵也就越大；把它搞清楚所需要的信息量也就越大。148/29/2019补充：关于某布尔分类的熵函数S为某正反样例的样例集（布尔分类）S的所有成员属于同一类，Entropy(S)=0；S的正反样例数量相等，Entropy(S)=1；S的正反样例数量不等，熵介于0和1之间补充：更一般的熵定义更一般地，如果目标属性具有c个不同的值，那么S相对于c个状态的分类的熵定义为：其中，pi是S中属于类别i的比例。如果目标属性具有c个可能值，那么熵最大可能为log2c。ciiippS12log)(Entropy补充：用信息增益度量期望的熵降低信息增益是定义属性分类训练数据的能力的度量标准。简单地说，一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低。更精确地讲，一个属性A相对样例集合S的信息增益Gain(S,A)，被定义为：其中，Values(A)是属性A所有可能值的集合，Sv是S中属性A的值为v的子集。()||(,)()()||vvvValuesASGainSAEntropySEntropySS决策树的建立--决策树建立的关键建立一个好的决策树的关键是决定树根和子树根的属性188/29/2019树根？计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买决策树的建立--对测试样例的信息期望信息期望？张三属于哪一类？为了回答该问题，对张三的信息期望值是多少？198/29/2019年龄计数年龄收入学生信誉归类：买计算机？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)=-pilog2(pi)其中pi=si/s208/29/2019i=1m决策树的建立--例分类属性：买计算机？该属性共分两类(m=2):买/不买s1=641,s2=383s=s1+s2=1024p1=s1/s=641/1024=0.6260p2=s2/s=383/1024=0.3740I(s1,s2)=I(641,383)=-(p1log2(p1)+p2log2(p2))=0.9537218/29/2019决策树的建立--对测试样例的信息期望讨论：“买”/“不买”计算机的人数之间的比例对于信息期望值的影响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信息期望的数值与分类属性中各类计数之间的比例有关信息期望的数值与计数总数无关228/29/2019决策树的建立--对测试样例的信息期望例：分类属性：加何种油？该属性共分三类(m=3):Regular/Plus/Supremes1=13300,s2=7300,s3=5200s=s1+s2+s3=25800p1=s1/s=13300/25800=0.5155p2=s2/s=7300/25800=0.2829p3=s3/s=5200/25800=0.2016I(s1,s2,s3)=I(13300,7300,5200)=-(p1log2(p1)+p2log2(p2)+p3log2(p3))=1.4739238/29/2019计数年龄收入种族信誉加何种油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当分类属性的种类增加时，对测试样例的信息期望通常也相应增加。248/29/2019决策树的建立--对测试样例的信息期望