WBQ决策树举例

2015-4-15DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved1决策树的用途不买优否中老63买优否中老1买良是高中32买优否中中32买优是中青64买良是中老132买良是低青64不买良否中青128买优是低中64不买优是低老64买良是低老64买良否中老60买良否高中128不买优否高青64不买良否高青64归类：买计算机？信誉学生收入年龄计数假定公司收集了左表数据，那么对于任意给定的客人（测试样例），你能帮助公司将这位客人归类吗？即：你能预测这位客人是属于“买”计算机的那一类，还是属于“不买”计算机的那一类？又：你需要多少有关这位客人的信息才能回答这个问题？决策树可以帮助你解决好这个问题2015-4-15DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved2分类算法•基于统计的算法：回归、贝叶斯•基于距离的算法：简单算法、K最近邻算法•基于决策树的算法：ID3、C4.5、C5.0、CART•基于神经网络的算法•基于规则的算法基于统计的算法直接基于统计信息进行分类；基于距离的算法利用相似性或者距离度量进行分类；决策树和神经网络利用各自的结构进行分类；基于规则的算法生成if-then规则进行分类2015-4-15DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved3决策树的用途不买优否中老63买优否中老1买良是高中32买优否中中32买优是中青64买良是中老132买良是低青64不买良否中青128买优是低中64不买优是低老64买良是低老64买良否中老60买良否高中128不买优否高青64不买良否高青64归类：买计算机？信誉学生收入年龄计数谁在买计算机？他/她会买计算机吗？年龄？学生？信誉？买青中老否是优良不买买买不买2015-4-15DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved4什么是决策树•决策树（DecisionTree,DT）是由根和每个内部节点都被标记为一个问题的树。从每个节点引出的弧代表与该节点相关联的问题的可能答案。每个叶节点代表对问题解决方案的一个预测。年龄？学生？信誉？买青中老否是优良不买买买不买2015-4-15DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved5决策树模型•决策树模型是一个计算模型，•它由三部分组成：定义中的决策树创建决策树的算法将树应用于数据并解决所考虑问题的算法。2015-4-15DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved6决策树的构造2015-4-15DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved7ID3算法2015-4-15DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved8选择属性的方法2015-4-15DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved9信息熵2015-4-15DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved10信息增益2015-4-15DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved11ID3算法描述2015-4-15DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved12决策树的建立1.决策树建立的关键2.测试样例的信息期望Š信息期望的分析与计算Š平均信息期望Š信息期望的减少（Gain）3.决策树建立步骤2015-4-15DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved13决策树建立的关键不买优否中老63买优否中老1买良是高中32买优否中中32买优是中青64买良是中老132买良是低青64不买良否中青128买优是低中64不买优是低老64买良是低老64买良否中老60买良否高中128不买优否高青64不买良否高青64归类：买计算机？信誉学生收入年龄计数树根？建立一个好的决策树的关键是决定树根和子树根的属性2015-4-15DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved14决策树建立的关键年龄买优是中青64买良是低青64不买良否中青128不买优否高青64不买良否高青64归类：买计算机？信誉学生收入年龄计数买良是高中32买优否中中32买优是低中64买良否高中128归类：买计算机？信誉学生收入年龄计数不买优否中老63买优否中老1买良是中老132不买优是低老64买良是低老64买良否中老60归类：买计算机？信誉学生收入年龄计数青中老2015-4-15DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved15测试样例的信息期望年龄不买优否中老63买优否中老1买良是高中32买优否中中32买优是中青64买良是中老132买良是低青64不买良否中青128买优是低中64不买优是低老64买良是低老64买良否中老60买良否高中128不买优否高青64不买良否高青64归类：买计算机？信誉学生收入年龄计数买优是中青64买良是低青64不买良否中青128不买优否高青64不买良否高青64归类：买计算机？信誉学生收入年龄计数买良是高中32买优否中中32买优是低中64买良否高中128归类：买计算机？信誉学生收入年龄计数不买优否中老63买优否中老1买良是中老132不买优是低老64买良是低老64买良否中老60归类：买计算机？信誉学生收入年龄计数张三属于哪一类？为了回答该问题，计算张三的信息期望值是多少？2015-4-15DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved16测试样例的信息期望年龄不买优否中老63买优否中老1买良是高中32买优否中中32买优是中青64买良是中老132买良是低青64不买良否中青128买优是低中64不买优是低老64买良是低老64买良否中老60买良否高中128不买优否高青64不买良否高青64归类：买计算机？信誉学生收入年龄计数买优是中青64买良是低青64不买良否中青128不买优否高青64不买良否高青64归类：买计算机？信誉学生收入年龄计数买良是高中32买优否中中32买优是低中64买良否高中128归类：买计算机？信誉学生收入年龄计数不买优否中老63买优否中老1买良是中老132不买优是低老64买良是低老64买良否中老60归类：买计算机？信誉学生收入年龄计数2015-4-15DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved17测试样例的信息期望•称所需要研究的属性为“分类属性”。假设该属性共分m类，而它们每一类在数据表中计数的总和分别为s1,s2…,sm。令s=s1+s2+…+sm对于任一样例，决定它所属类别的信息期望可以用公式计算：I(s1,s2…,sm)=-pilog2(pi)其中pi=si/s∑i=1m不买优否中老63买优否中老1买良是高中32买优否中中32买优是中青64买良是中老132买良是低青64不买良否中青128买优是低中64不买优是低老64买良是低老64买良否中老60买良否高中128不买优否高青64不买良否高青64归类：买计算机？信誉学生收入年龄计数2015-4-15DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved18测试样例的信息期望例：左表分类属性：买计算机？该属性共分两类(m=2):买/不买s1=641,s2=383s=s1+s2=1024p1=s1/s=641/1024=0.6260p2=s2/s=383/1024=0.3740I(s1,s2)=I(641,383)=-(p1log2(p1)+p2log2(p2))=0.9537不买优否中老63买优否中老1买良是高中32买优否中中32买优是中青64买良是中老132买良是低青64不买良否中青128买优是低中64不买优是低老64买良是低老64买良否中老60买良否高中128不买优否高青64不买良否高青64归类：买计算机？信誉学生收入年龄计数2015-4-15DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved19测试样例的信息期望讨论：“买”/“不买”计算机的人数之间的比例对于信息期望值的影响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•信息期望的数值与分类属性中各类计数之间的比例有关•信息期望的数值与计数总数无关不买优否中老63买优否中老1买良是高中32买优否中中32买优是中青64买良是中老132买良是低青64不买良否中青128买优是低中64不买优是低老64买良是低老64买良否中老60买良否高中128不买优否高青64不买良否高青64归类：买计算机？信誉学生收入年龄计数2015-4-15DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved20测试样例的信息期望Regular优非洲高青2200Plus良西班牙中老1600Regular良西班牙高青2000Regular优白人高青5200Plus优亚裔中青1800Regular良亚裔高青2400优良良良信誉非洲西班牙白人亚裔种族Supreme低中3200Plus中中3900Regular高老1500Supreme低老2000加何种油收入年龄计数例：分类属性：加何种油？该属性共分三类(m=3):Regular/Plus/Supremes1=13300,s2=7300,s3=5200s=s1+s2+s3=25800p1=s1/s=13300/25800=0.5155p2=s2/s=7300/25800=0.2829p3=s3/s=5200/25800=0.2016I(s1,s2,s3)=I(13300,7300,5200)=-(p1log2(p1)+p2log2(p2)+p3log2(p3))=1.47392015-4-15DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved21测试样例的信息期望Regular优非洲高青2200Plus良西班牙中老1600Regular良西班牙高青2000Regular优白人高青5200Plus优亚裔中青1800Regular良亚裔高青2400优良良良信誉非洲西班牙白人亚裔种族Supreme低中3200Plus中中3900Regular高老1500Supreme低老2000加何种油收入年龄计数讨论：三种汽油购买人数之间的比例对于需解决的信息量的影响I(13300,7300,5200)=1.4739I(25800,0,0)=0I(0,10,0)=0I(641,383,0)=0.9537I(900,100,24)=0.6183I(64,64,64)=1.5851•当分类属