数据挖掘算法总括

数据挖掘算法总括决策树•需要掌握决策树根节点的选取（计算）2020/1/30DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved3决策树的建立1.决策树建立的关键2.对测试样例的信息期望(Theexpectedinformationneededtoclassifyagivensample(中文可能称：评价函数))信息期望的分析与计算平均信息期望信息期望的减少（Gain）3.决策树建立步骤（例）2020/1/30DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved4决策树的建立--决策树建立的关键计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买树根？建立一个好的决策树的关键是决定树根和子树根的属性2020/1/30DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved5决策树的建立--决策树建立的关键年龄计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买计数年龄收入学生信誉归类：买计算机？128中高否良买64中低是优买32中中否优买32中高是良买计数年龄收入学生信誉归类：买计算机？60老中否良买64老低是良买64老低是优不买132老中是良买63老中否优不买1老中否优买青中老2020/1/30DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved6决策树的建立--对测试样例的信息期望年龄计数年龄收入学生信誉归类：买计算机？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老中否优买张三属于哪一类？为了回答该问题，对张三的信息期望值是多少？2020/1/30DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved7决策树的建立--对测试样例的信息期望年龄计数年龄收入学生信誉归类：买计算机？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老中否优买2020/1/30DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved8决策树的建立--对测试样例的信息期望•让我们称所需要研究的属性为“分类属性”。假设该属性共分m类，而它们每一类在数据表中计数的总和分别为s1,s2…,sm。令s=s1+s2+…+sm那么对于任一样例，决定它所属类别的信息期望可以用下面的公式来计算：I(s1,s2…,sm)=-pilog2(pi)其中pi=si/si=1m计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买2020/1/30DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved9决策树的建立--对测试样例的信息期望例：左表分类属性：买计算机？该属性共分两类(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计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买2020/1/30DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved10决策树的建立--对测试样例的信息期望信息期望的减少(又称Gain)=信息期望–平均信息期望基于节点数据表基于该节点的所有直系分支数据表2020/1/30DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved11决策树的建立--对测试样例的信息期望计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买计数年龄收入学生信誉归类：买计算机？128中高否良买64中低是优买32中中否优买32中高是良买计数年龄收入学生信誉归类：买计算机？60老中否良买64老低是良买64老低是优不买132老中是良买63老中否优不买1老中否优买•平均信息期望，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.26602020/1/30DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved12计数年龄收入学生信誉归类：买计算机？60老中否良买128青中否良不买132老中是良买64青中是优买32中中否优买63老中否优不买1老中否优买决策树的建立--对测试样例的信息期望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计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买32中高是良买计数年龄收入学生信誉归类：买计算机？64老低是良买64老低是优不买64中低是优买64青低是良买2020/1/30DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved13决策树的建立--对测试样例的信息期望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中高是良买2020/1/30DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved14决策树的建立--对测试样例的信息期望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中高是良买2020/1/30DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved15决策树的建立--对测试样例的信息期望•决定树根节点E(年龄）=0.6877，Gain(年龄)=0.2660E(收入）=0.9361，Gain(收入)=0.0176E(学生）=0.7811，Gain(学生)=0.1726E(信誉）=0.9048，Gain(信誉)=0.0453数据仓库的数据模型•能够分析题目的语义，并画出对应的数据模型。星型模式实例time_keydayday_of_the_weekmonthquarteryeartimelocation_keystreetcitystate_or_provincecountrylocationSalesFactTabletime_keyitem_keybranch_keylocation_keyunits_solddollars_soldavg_salesMeasuresitem_keyitem_namebrandtypesupplier_typeitembranch_keybranch_namebranch_typebranch雪花模式实例time_keydayday_of_the_weekmonthquarteryeartimelocation_keystreetcity_keylocationSalesFactTabletime_keyitem_keybranch_keylocation_keyunits_sold