第5章数据分类

2023/2/6数据仓库与数据挖掘1第5章数据分类5.1引例2023/2/6数据仓库与数据挖掘2通俗来说，决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：女儿：多大年纪了？女母亲：26。女儿：长的帅不帅？母亲：挺帅的。女儿：收入高不？母亲：不算很高，中等情况。

女儿：是公务员不？母亲：是，在税务局上班呢。女儿：那好，我去见见。5.1引例2023/2/6数据仓库与数据挖掘3这个女孩的决策过程就是典型的分类树决策。相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见。假设这个女孩对男人的要求是：30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，那么这个可以用下图表示女孩的决策逻辑：年龄长相收入公务员决策26帅高是32帅高是28帅中等是28帅低否28丑高是2023/2/6数据仓库与数据挖掘45.1引例分类的定义分类是指把数据样本映射到一个事先定义的类中的学习过程，即给定一组输入的属性向量及其对应的类，用基于归纳的学习算法得出分类。医疗诊断

银行信贷等领域应用2023/2/6数据仓库与数据挖掘55.1引例AgeSalaryClass30highc125highc2………描述属性类别属性分类问题使用的数据集格式：2023/2/6数据仓库与数据挖掘65.1引例分类问题使用的数据集格式描述属性可以是连续型属性，也可以是离散型属性；而类别属性必须是离散型属性。连续型属性是指在某一个区间或者无穷区间内该属性的取值是连续的，例如属性“年龄”离散型属性是指该属性的取值是不连续的，例如属性“长相”和“收入”2023/2/6数据仓库与数据挖掘75.1引例分类问题使用的数据集格式分类问题中使用的数据集可以表示为X={(xi,yi)|i=1,2,…,total}xi=(xi1,xi2,…,xid)，其中xi1,xi2,…,xid分别对应d个描述属性A1,A2,…,Ad的具体取值yi表示数据样本Xi的类标号，假设给定数据集包含m个类别，则yi∈{c1,c2,…,cm}，其中c1,c2,…,cm是类别属性C的具体取值未知类标号的数据样本x用d维特征向量x=(x1,x2,…,xd)来表示2023/2/6数据仓库与数据挖掘85.3决策树5.3.1决策树的基本概念5.3.2决策树算法ID35.3.3ID3算法应用举例5.3.4决策树算法C4.55.3.5SQLServer2005中的决策树应用5.3.6决策树剪枝2023/2/6数据仓库与数据挖掘95.3决策树决策树Quinlan在1986提出的ID3

在1993提出的C4.5ID3只能处理离散型描述属性

选用信息增益最大的属性划分训练样本C4.5能处理离散型以及连续型描述类型

采用信息增益比作为选择分枝属性的标准2023/2/6数据仓库与数据挖掘105.3决策树决策树的优点：进行分类器设计时，决策树分类方法所需时间相对较少决策树的分类模型是树状结构，简单直观，比较符合人类的理解方式可以将决策树中到达每个叶节点的路径转换为IF—THEN形式的分类规则，这种形式更有利于理解年龄公司职员信誉度c1c2c1c2c1≤4041~50>50是否良优2023/2/6数据仓库与数据挖掘5.3.1决策树的基本概念是一种归纳学习的方法,采用自顶向下的递归方式产生一个类似于流程图的树结构在根节点和各内部节点上选择合适的描述属性，并且根据该属性的不同取值向下建立分枝年龄公司职员信誉度c1c2c1c2c1≤4041~50>50是否良优2023/2/6数据仓库与数据挖掘125.3.1决策树的基本概念公司职员年龄收入信誉度买保险否≤40高良c2否≤40高优c2否41~50高良c1否>50中良c1是>50低良c1是>50低优c2是41~50低优c1否≤40中良c2是≤40低良c1是>50中良c1是≤40中优c1否41~50中优c1是41~50高良c1否>50中优c2描述属性类别属性12年龄公司职员信誉度c1c2c1c2c1≤4041~50>50是否良优2023/2/6数据仓库与数据挖掘135.3.1决策树的基本概念年龄公司职员信誉度c1c2c1c2c1≤4041~50>50是否良优2023/2/6数据仓库与数据挖掘145.3.2决策树算法ID3ID3只能处理离散型描述属性；在选择根节点和各个内部节点上的分枝属性时，采用信息增益作为度量标准，选择具有最高信息增益的描述属性作为分枝属性测试样例的信息期望:√信息期望的计算;平均信息期望;

√信息期望的减少(Gain)2023/2/6数据仓库与数据挖掘155.3.2决策树算法ID3需要说明的是:在创建根节点的时候,数据集X是最初给定的所有数据公司职员年龄收入信誉度买保险否≤40高良c2否≤40高优c2否41~50高良c1否>50中良c1是>50低良c1是>50低优c2是41~50低优c1否≤40中良c2是≤40低良c1是>50中良c1是≤40中优c1否41~50中优c1是41~50高良c1否>50中优c2年龄2023/2/6数据仓库与数据挖掘165.3.2决策树算法ID3需要说明的是:在创建内部节点时,数据集X是上层节点的某个分枝对应的数据集.公司职员年龄收入信誉度买保险是41~50低优c1否41~50高良c1否41~50中优c1是41~50高良c1年龄C12/6/202317决策树的建立计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买树根？建立一个好的决策树的关键是决定树根和子树根的属性2/6/202318决策树的建立年龄计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买计数年龄收入学生信誉归类：买计算机？128中高否良买64中低是优买32中中否优买32中高是良买计数年龄收入学生信誉归类：买计算机？60老中否良买64老低是良买64老低是优不买132老中是良买63老中否优不买1老中否优买青中老2/6/202319决策树的建立--对测试样例的信息期望年龄计数年龄收入学生信誉归类：买计算机？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老中否优买信息期望=0信息期望=？信息期望=？张三属于哪一类？为了回答该问题，对张三的信息期望值是多少？信息期望=？2/6/202320决策树的建立--对测试样例的信息期望年龄计数年龄收入学生信誉归类：买计算机？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/6/202321决策树的建立--对测试样例的信息期望所需要研究的属性为“分类属性”。假设该属性共分m类，而它们每一类在数据表中计数的总和分别为s1,s2…,sm。 令s=s1+s2+…+sm

那么对于任一样例，决定它所属类别的信息期望可以用下面的公式来计算：

I(s1,s2…,sm)=-pilog2(pi)

其中pi=si/si=1m计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买信息期望？2/6/202322例：左表 分类属性：买计算机？ 该属性共分两类(m=2):买/不买

s1=641, s2=383 s=s1+s2=1024 p1=s1/s=641/1024=0.6260 p2=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老中否优买信息期望？决策树的建立--对测试样例的信息期望2/6/202323讨论：“买”/“不买”计算机的人数之间的比例对于信息期望值的影响

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信息期望的数值与分类属性中各类计数之间的比例有关信息期望的数值与计数总数无关计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买信息期望？决策树的建立--对测试样例的信息期望2/6/202324计数年龄收入种族信誉加何种油2000老低亚裔良Supreme1500老高白人良Regular3900中中西班牙良Plus3200中低非洲优Supreme5200青高白人优Regular1800青中亚裔优Plus2400青高亚裔良Regular2200青高非洲优Regular1600老中西班牙良Plus2000青高西班牙良Regular例：分类属性：加何种油？ 该属性共分三类(m=3):Regular/Plus/Supreme s1=13300,s2=7300,s3=5200 s=s1+s2+s3=25800 p1=s1/s=13300/25800=0.5155 p2=s2/s=7300/25800=0.2829 p3=s3/s=5200/25800=0.2016

I(s1,s2,s3)=I(13300,7300,5200)

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

信息期望=？决策树的建立--对测试样例的信息期望2/6/202325计数年龄收入种族信誉加何种油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.5851当分类属性的种类增加时，对测试样例的信息期望通常也相应增加。信息期望=？决策树的建立--对测试样例的信息期望2/6/202326年龄计数年龄收入学生信誉归类：买计算机？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/6/202327信息期望的减少(又称Gain—信息增益)=信息期望–平均信息期望

基于节点数据表基于该节点的所有直系分支数据表决策树的建立--对测试样例的信息期望2/6/2023DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved28计数年龄收入学生信誉归类：买计算机？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.91572. 青年组比例:(128+256)/1024=0.375

中年组比例:256/1024=0.25

老年组比例:(257+127)/1024=0.3753. 平均信息期望（加权总和）：

E(年龄）=0.375*0.9183 +0.25*0+0.375*0.9157=0.68774. Gain(年龄)=I(641,383)-E(年龄) =0.9537–0.6877=0.2660平均信息期望？决策树的建立--对测试样例的信息期望2/6/2023DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved29计数年龄收入学生信誉归类：买计算机？60老中否良买128青中否良不买132老中是良买64青中是优买32中中否优买63老中否优不买1老中否优买1. 假定选择收入作树根节点，则：

高收入组:I(160,128)=0.9911

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

低收入组:I(192,64)=0.81332. 高收入组比例:288/1024=0.2813

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

低收入组比例:256/1024=0.253. 平均信息期望（加权总和）：

E(收入）=0.2813*0.9911 +0.4687*0.9697 +0.25*0.8133=0.93614. Gain(收入)=I(641,383)-E(收入) =0.9537–0.9361=0.0176平均信息期望？计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买32中高是良买计数年龄收入学生信誉归类：买计算机？64老低是良买64老低是优不买64中低是优买64青低是良买决策树的建立--对测试样例的信息期望2/6/2023DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved301. 假定选择学生作树根节点，则：

学生组:I(420,64)=0.5635

非学生组:I(221,319)=0.97612. 学生组比例:484/1024=0.4727

非学生组比例:540/1024=0.52733. 平均信息期望（加权总和）：

E(学生）=0.4727*0.5635 +0.5273*0.9761 =0.78114. Gain(学生)=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中高是良买平均信息期望？决策树的建立--对测试样例的信息期望2/6/2023DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved311. 假定选择信誉作树根节点，则：

良好组:I(480,192)=0.8631

优秀组:I(161,191)=0.99482. 良好组比例:672/1024=0.6563

优秀组比例:352/1024=0.34373. 平均信息期望（加权总和）：

E(信誉）=0.6563*0.8631 +0.3437*0.9948 =0.90484. Gain(信誉)=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中高是良买平均信息期望？决策树的建立--对测试样例的信息期望2/6/2023DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved32决定树根节点

E(年龄）=0.6877，Gain(年龄)=0.2660 E(收入）=0.9361，Gain(收入)=0.0176 E(学生）=0.7811，Gain(学生)=0.1726 E(信誉）=0.9048，Gain(信誉)=0.0453决策树的建立--对测试样例的信息期望2/6/2023DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved33年龄计数收入学生信誉归类：买计算机？64高否良不买64高否优不买128中否良不买64低是良买64中是优买计数收入学生信誉归类：买计算机？60中否良买64低是良买64低是优不买132中是良买63中否优不买1中否优买青中老树叶计数收入学生信誉归类：买计算机？128高否良买64低是优买32中否优买32高是良买决策树的建立--对测试样例的信息期望2/6/2023DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved34年龄计数收入学生信誉归类：买计算机？64高否良不买64高否优不买128中否良不买64低是良买64中是优买计数收入学生信誉归类：买计算机？60中否良买64低是良买64低是优不买132中是良买63中否优不买1中否优买青中老买决策树的建立--对测试样例的信息期望2/6/2023DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved35平均信息期望？信息期望？计数收入学生信誉归类：买计算机？64高否良不买64高否优不买128中否良不买64低是良买64中是优买平均信息期望（加权总和）：

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低是良买青年组数据表分析：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决策树的建立--对测试样例的信息期望2/6/2023DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved36信息期望？计数收入学生信誉归类：买计算机？64高否良不买64高否优不买128中否良不买64低是良买64中是优买平均信息期望（加权总和）：E(学生）=0.3333*0+0.6667*0=0Gain(学生)=I(128,256)-E(学生)=0.9183–0=0.9183结论:不需要考虑属性信誉，决定选择属性学生青年组数据表分析：

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中是优买平均信息期望？决策树的建立--对测试样例的信息期望2/6/2023DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved37年龄计数收入信誉归类：买计算机？64低良买64中优买计数收入学生信誉归类：买计算机？60中否良买64低是良买64低是优不买132中是良买63中否优不买1中否优买青中老买学生计数收入信誉归类：买计算机？64高良不买64高优不买128中良不买否是树叶决策树的建立--对测试样例的信息期望2/6/2023DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved38年龄计数收入学生信誉归类：买计算机？60中否良买64低是良买64低是优不买132中是良买63中否优不买1中否优买青中老买学生否是买不买决策树的建立--对测试样例的信息期望2/6/2023DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved39信息期望？平均信息期望（加权总和）：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低是优不买平均信息期望？决策树的建立--对测试样例的信息期望2/6/2023DataMiningTool-DecisionTree,JiahuangJi,Ph.D.AllRightsReserved40信息期望？平均信息期望（加权总和）：E(学生）=0.6771*0.8051+0.3229*0.9998