第5章_数据分类(1)

1、2022-4-252022-4-25数据仓库与数据挖掘数据仓库与数据挖掘1第第5章章 数据分类数据分类25.1 引例引例q 分类的定义分类的定义分类是一个两步过程，即事先利用已有数据样本建立一分类是一个两步过程，即事先利用已有数据样本建立一个数学模型，然后对新的数据进行分类的过程。个数学模型，然后对新的数据进行分类的过程。用基于归纳的学习算法得出分类。用基于归纳的学习算法得出分类。q 分类与预测的区别分类与预测的区别p 分类：预测分类标号（离散值），根据训练数据集和类标号分类：预测分类标号（离散值），根据训练数据集和类标号属性构建分类模型，对新数据进行分类属性构建分类模型，对新数据进行分类.

2、例如：信任度等级划分问题例如：信任度等级划分问题q 预测：预测：预测函数值（连续值），根据训练数据集，建立连预测函数值（连续值），根据训练数据集，建立连续函数值模型，然后利用该模型计算新数据的函数值续函数值模型，然后利用该模型计算新数据的函数值 例如：回归分析，销售预测问题例如：回归分析，销售预测问题31）数据分类）数据分类一个两步过程一个两步过程q 假定每个元组属于一个预定义的类，由一个类标号属性确定假定每个元组属于一个预定义的类，由一个类标号属性确定q训练数据集：由为建立模型而被分析的数据元组形成：由为建立模型而被分析的数据元组形成q训练样本：训练数据集中的单个样本（元组）：训练数据集中的

3、单个样本（元组） 得到的学习模型可以用分类规则、判定树或数学公式的形式得到的学习模型可以用分类规则、判定树或数学公式的形式表示表示q 然后评估模型然后评估模型, 预测准确率预测准确率q 对每个测试样本，将已知的类标号和该样本的学习模型类预测对每个测试样本，将已知的类标号和该样本的学习模型类预测比较比较q 模型在给定测试集上的准确率是正确被模型分类的测试样本的模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比百分比q 测试集要独立于训练样本集，否则会出现测试集要独立于训练样本集，否则会出现“过分适应数据过分适应数据”的的情况情况q第二步，使用模型，对新的未知类的对象进行分类第二步，使用

4、模型，对新的未知类的对象进行分类q第一步，建立一个模型，描述预定数据类集和概念集第一步，建立一个模型，描述预定数据类集和概念集4AgeSalaryClass30highc125highc221lowc243highc118lowc233lowc1描述属性描述属性类别属性类别属性2）分类问题使用的数据集格式）分类问题使用的数据集格式5p描述属性可以是连续型属性，也可以描述属性可以是连续型属性，也可以是离散型属性；而类别属性必须是离是离散型属性；而类别属性必须是离散型属性。散型属性。 p连续型属性是指在某一个区间或者无连续型属性是指在某一个区间或者无穷区间内该属性的取值是连续的穷区间内该属性的取值

5、是连续的 ，例，例如属性如属性“Age” p离散型属性是指该属性的取值是不连离散型属性是指该属性的取值是不连续的续的 ，例如属性，例如属性“Salary”和和“Class” 6q分类问题中使用的训练数据样本集可以表示为分类问题中使用的训练数据样本集可以表示为: X=(xi,yi)|i=1,2,totalqxi=(xi1,xi2,xid) ，其中，其中xi1,xi2,xid分别对应分别对应d个描个描述属性述属性A1,A2,Ad的具体取值的具体取值qyi表示数据样本表示数据样本xi的类标号，假设给定数据集包含的类标号，假设给定数据集包含m个类别，则个类别，则yic1,c2,cm，其中，其中c1,c

6、2,cm是类是类别属性别属性C的具体取值的具体取值q未知类标号的数据样本未知类标号的数据样本x用用d维特征向量：维特征向量： x=(x1,x2,xd) 来表示。来表示。73）有指导的学习）有指导的学习 VS. 无指导的学习无指导的学习1）有指导的学习（用于分类）有指导的学习（用于分类）q 模型的学习在被告知每个训练样本模型的学习在被告知每个训练样本属于哪个类的“指导”下进行下进行q 新数据使用训练数据集中得到的规则进行分类新数据使用训练数据集中得到的规则进行分类2）无指导的学习（用于聚类）无指导的学习（用于聚类）q 每个训练样本的类编号是未知的，要学习的类集合或数每个训练样本的类编号是未知的，

7、要学习的类集合或数量也可能是事先未知的量也可能是事先未知的q 通过一系列的度量、观察来通过一系列的度量、观察来建立数据中的类编号或进行聚类85.2 分类问题概述分类问题概述5.2.1 分类的过程分类的过程获取数据获取数据预处理预处理分类器设计分类器设计分类决策分类决策9第一步第一步建立模型建立模型训练数据集NAME RANKYEARS TENUREDMikeAssistant Prof3noMaryAssistant Prof7yesBill Professor2yesJimAssociate Prof7yesDaveAssistant Prof6noAnneAssociate Prof3no

8、分类算法IF rank = professorOR years 6THEN tenured = yes 分类规则10分类规则测试集NAMERANKYEARS TENUREDTomAssistant Prof2noMerlisa Associate Prof7noGeorge Professor5yesJoseph Assistant Prof7yesTenured?评估已建立的模型评估已建立的模型IF rank = professorOR years 6THEN tenured = yes 准确率？准确率？11第二步第二步用模型进行分类用模型进行分类分类规则未知数据(Jeff, Profess

9、or, 4)Tenured?IF rank = professorOR years 6THEN tenured = yes 12p获取数据获取数据输入数据、对数据进行量化输入数据、对数据进行量化p预处理预处理去除噪声数据、对空缺值进行处理去除噪声数据、对空缺值进行处理数据集成或者变换数据集成或者变换 p分类器设计分类器设计划分数据集、分类器构造、分类器测试划分数据集、分类器构造、分类器测试p分类决策分类决策对未知类标号的数据样本进行分类对未知类标号的数据样本进行分类13p给定测试集给定测试集Xtest=(xi,yi)|i=1,2,Np N表示测试集中的样本个数表示测试集中的样本个数p xi表示

10、测试集中的数据样本表示测试集中的数据样本p yi表示数据样本表示数据样本xi的类标号的类标号p对于测试集的第对于测试集的第j个类别，假设个类别，假设p 被正确分类的样本数量为被正确分类的样本数量为TPjp 被错误分类的样本数量为被错误分类的样本数量为FNjp 其他类别被错误分类为该类的样本数据量为其他类别被错误分类为该类的样本数据量为FPj5.2.2 5.2.2 分类的评价准则分类的评价准则14p精确度：代表测试集中被正确分类的数据精确度：代表测试集中被正确分类的数据样本所占的比例样本所占的比例 NTPAccuracymjj115p查全率：表示在本类样本中被正确分类的查全率：表示在本类样本中被

11、正确分类的样本所占的比例样本所占的比例 p查准率：表示被分类为该类的样本中，真查准率：表示被分类为该类的样本中，真正属于该类的样本所占的比例正属于该类的样本所占的比例 mj1 ,FNTPTPRecalljjjjmj1 ,FPTPTPPrecisionjjjj16pF-measure：是查全率和查准率的组合：是查全率和查准率的组合表达式表达式 p是可以调节的，通常取值为是可以调节的，通常取值为1 mj1 ,PrecisionRecallPrecisionRecall)1 (measureFjj2jj2j17p几何均值几何均值 ：是各个类别的查全率的平方：是各个类别的查全率的平方根根 m1jjca

12、llRemeanG185.3 5.3 决策树决策树决策树的优点：决策树的优点：p进行分类器设计时，决策树分类方法所需时间进行分类器设计时，决策树分类方法所需时间相对较少相对较少p决策树的分类模型是树状结构，简单直观，比决策树的分类模型是树状结构，简单直观，比较符合人类的理解方式较符合人类的理解方式p可以将决策树中到达每个叶节点的路径转换为可以将决策树中到达每个叶节点的路径转换为IFTHENIFTHEN形式的分类规则，这种形式更有利于理形式的分类规则，这种形式更有利于理解解19p适用于离散值属性、连续值属性适用于离散值属性、连续值属性p采用自顶向下的递归方式产生一个类似于流采用自顶向下的递归方式

13、产生一个类似于流程图的树结构程图的树结构p在根节点和各内部节点上选择合适的描述属在根节点和各内部节点上选择合适的描述属性，并且根据该属性的不同取值向下建立分性，并且根据该属性的不同取值向下建立分枝枝 5.3.1 5.3.1 决策树的基本概念决策树的基本概念20公司职员公司职员年龄年龄收入收入信誉度信誉度买保险买保险否否40高高良良c2否否40高高优优c2否否4150高高良良c1否否50中中良良c1是是50低低良良c1是是50低低优优c2是是4150低低优优c1否否40中中良良c2是是40低低良良c1是是50中中良良c1是是40中中优优c1否否4150中中优优c1是是4150高高良良c1否否50

14、中中优优c2描述属性描述属性类别属性类别属性21q在给定已知类标号的数据集的情况下，决策树采用自顶在给定已知类标号的数据集的情况下，决策树采用自顶向下的递归方式产生一个类似于流程图的树结构。向下的递归方式产生一个类似于流程图的树结构。q树的最顶点称为根结点；最底层结点称为叶结点，每个树的最顶点称为根结点；最底层结点称为叶结点，每个叶结点代表样本的类别或者类分布叶结点代表样本的类别或者类分布；根结点和叶结点之间；根结点和叶结点之间的结点成为内部结点。决策树在的结点成为内部结点。决策树在根节点和各内部节点上选根节点和各内部节点上选择合适的描述属性，择合适的描述属性，并且根据该属性的不同取值向下建立

15、并且根据该属性的不同取值向下建立分枝。分枝。q对未知类标号的数据样本进行分类时，从根结点开始逐对未知类标号的数据样本进行分类时，从根结点开始逐层向下判断，直到叶结点，这样就可以得到该数据样本的层向下判断，直到叶结点，这样就可以得到该数据样本的类标号。类标号。 22年龄年龄公司职员公司职员信誉度信誉度c1c2c1c2c140415050是是否否良良优优23IF 年龄年龄 = “=40” AND 公司雇员公司雇员 = “no” THEN买买保险保险 = “C2”IF年龄年龄= “50” AND 信誉度信誉度 = “优优” THEN买保买保险险 = “C1”IF年龄年龄= “50” AND 信誉度信

16、誉度 = “良良” THEN买保险买保险 = “C2”判定树可以通过如下的判定树可以通过如下的IF-THEN IF-THEN 分类规则来表示。分类规则来表示。24qID3只能处理离散型描述属性；在选择只能处理离散型描述属性；在选择根节点和各个内部节点上的分枝属性根节点和各个内部节点上的分枝属性时，采用信息增益作为度量标准时，采用信息增益作为度量标准 ，选，选择具有最高信息增益的描述属性作为择具有最高信息增益的描述属性作为分枝属性分枝属性 q算法过程如下：算法过程如下：5.3.2 5.3.2 决策树算法决策树算法ID3ID325 假设给定的数据样本集为假设给定的数据样本集为: X=(xi,yi)

17、|i=1,2,total，其中样本其中样本xi（ i=1,2,total）用）用d维特征向量维特征向量xi=(xi1,xi2,xid) 来表示，来表示， xi1,xi2,xid分别对应分别对应d个描个描述属性述属性A1,A2,Ad的具体取值；的具体取值； yi（ i=1,2,total）表示数据样本表示数据样本xi的类标号，假设给定数据集包含的类标号，假设给定数据集包含m个类个类别，则别，则yic1,c2,cm，其中，其中c1,c2,cm是类别属性是类别属性C的具体取值的具体取值.26 2）计算描述属性）计算描述属性Af划分数据集划分数据集X所得的熵所得的熵q假设描述属性假设描述属性Af有有q

18、个不同取值，将个不同取值，将X划分为划分为q个子集个子集X1,X2,Xs,Xq ，其中，其中Xs（s=1,2,.,s)中的样本在中的样本在Af上上具有相同的取值。具有相同的取值。q假设假设ns表示表示Xs中的样本数量，中的样本数量，njs表示表示Xs中属中属于类别于类别cj的样本数量。则由描述属性的样本数量。则由描述属性Af划分数划分数据集据集X所得的熵为：所得的熵为：m1jj2jm21)c (P(log)c (P)n,.,n,n( I1)假设假设nj是数据集是数据集X中属于类别中属于类别cj的样本数量，的样本数量，则各类别的先验概率为则各类别的先验概率为P(cj)=nj/total，j=1,

19、2,m。对于给定数据集。对于给定数据集X，计算期望信息：，计算期望信息：273）计算）计算Af划分数据集时的信息增益：划分数据集时的信息增益： Gain(Af)=I(n1,n2,nm)-E(Af) )n,.,n( Itotalnn)A(Emss1q1smss1f sjsjsm1jjs2jsmss1n/np)p(logp)n,.,n( I其中：其中：Pjs 表示在子集Xs中类别为cj的数据样本所占的比例。熵值越小，表示属性对数据集划分的纯度越高。28图图5.3 ID35.3 ID3算法步骤算法步骤295.3.3 ID3算法应用举例算法应用举例 本节通过一个应用实例来说明ID3算法在生成决策树时是

20、怎样选择根结点和各个内部结点的。 【例51】根据表52中给出的训练集，利用ID3算法生成决策树，即选择根结点和各内部结点上的分枝属性。 【解】 问题的求解过程分为以下几个部分。 (1)计算对训练集分类所需的期望信息。 因为给定训练集中的样本数量为total=14，类标号为c1(表示买保险)的样本数量为n1=9，类标号为c2(表示不买保险)的样本数量为n2=5，所以训练集中两个类别的先验概率分别为:30根据式(56)，对训练集分类所需的期望信息为: (2)计算各个描述属性划分训练集时的信息增益。 首先，计算第一个描述属性A1(公司职员)的熵。A1包含两种具体取值，第一种取值为 “是”，表示数据样

21、本是公司职员；第二种取值为“否”，表示数据样本不是公司职员。利用该描述属性可以将训练集划分为两个样本子集：X 1和X2。样本子集X1中的数据样本都是公司职员，而样本子集X2中的数据样本都不是公司职员。31公司职员公司职员年龄年龄收入收入信誉度信誉度买保险买保险否否40高高良良c2否否40高高优优c2否否4150高高良良c1否否50中中良良c1是是50低低良良c1是是50低低优优c2是是4150低低优优c1否否40中中良良c2是是40低低良良c1是是50中中良良c1是是40中中优优c1否否4150中中优优c1是是4150高高良良c1否否50中中优优c232样本子集X1中的样本数量为n1=7，其中

22、类标号为c1的样本数量n1=6，类标号为c2 的样本数量为n21=1，则样本子集X1中两个类别的数据样本所占的比例分别为:根据式(58)，可以得到33 样本子集X2中的样本数量为n2=7，其中类标号为c1的样本数量n12=3，类标号为c2的样本数量为n22=4，则样本子集x2中两个类别的数据样本所占的比例分别为:根据式(58)，可以得到34 根据式(57)，计算出由描述属性A1(公司职员)划分训练集时所得的熵为 根据期望信息I(n1，n2)和熵E(A1)，并且根据式(59)，可以得到描述属性A1划分训练集时的信息增益为:35 同理，可以计算出描述属性A2(年龄)、A2(收入)和A4(信誉度)划

23、分训练集时的信息增益，它们的值分别为 Gain(A2)=0246，Gain(A3)=0029，Gain(A4)=0048 可以看出，描述属性A2划分训练集时得到的信息增益的值最大，所以选择它作为决策树的根结点。由于描述属性A2有3种具体取值，所以它包含3个分枝。也就是说，描述属性A2按照年龄40、4150和50将表52中的训练集划分为3个样本子集，如表53、表5.4和表5.5所示。 表53表52的训练集对应年龄40的样本子集36表54,表52的训练集对应年龄4l50的样本子集37 其中，表54(年龄在4150)对应的样本子集都属于同一个类别，即类别属性C(买保险)的取值都为c1，所以这个子集没

24、有必要再继续划分了，可以将它标注为一个叶结点，而且叶结点的类标号为c1。对于另外两个样本子集(表53和表55)，由于数据样本的类标号不统一，需要继续划分。 (3)对数据集进行继续划分。 对于表53(年龄40)和表55(年龄50)对应的样本子集，利用上述方法继续挑选信息增益的值最大的描述属性作为内部结点上的分枝属性，直到得到叶结点。需要注意的是，在计算信息增益时，不需要再计算属性A2(年龄)的信息增益了，也就是说，在选择下层结点的分枝属性时，不需要再计算上层结点中分枝属性的信息增益了。 经过上述迭代过程，可以得到图52所示的决策树。38534决策树算法C45 ID3算法存在以下缺点。 (1)ID

25、3算法在选择根结点和各内部结点中的分枝属性时，使用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息。 (2)ID3算法只能对描述属性为离散型属性的数据集构造决策树。 针对ID3算法的不足，决策树算法C45的改进如下所示。 (1)C45算法使用信息增益比来作为选择根结点和各内部结点中分枝属性的评价标准，克服了ID3算法使用信息增益选择属性时偏向于取值较多的属性的不足。39 在选择决策树中某个结点上的分枝属性时，假设该结点上的数据集为X，其中包含d个描述属性，样本总数为total。设描述属性Af(f=1，2，d)具有q个不同的取值a1

26、f，a2f，aqf)，利用描述属性Af可以将数据集X划分为q个子集X1，X2，Xq)，其中 Xs(s=1，2，q)中的样本在Af上具有相同的取值asf。设ns表示子集X，中的样本数量，则描述属性As划分给定数据集X的信息增益比的定义式如式(5一l0)所示。 在式(510)中，分子Gain(A，)的定义式如式(59)所示；分母split(Af)的定义式如式(511)所示。 C45选择信息增益比最大的描述属性作为分枝属性。40 (2)C45既可以处理离散型描述属性，也可以处理连续型描述属性。在选择某结点上的分枝属性时，对于离散型描述属性，C4。5的处理方法与ID3相同，按照该属性本身的取值个数进行

27、计算；对于某个连续型描述属性A。，假设在某个结点上的数据集的样本数量为total，C45将作以下处理。 将该结点上的所有数据样本按照连续型描述属性的具体取值，由小到大进行排序，得到属性值的取值序列A1c，A2c，Atotalc)。 在A1c,A2c，Atotalc，中生成total-1个分割点。第i(1itotal-1)个分割点的取值设置为vi=(Aic+A（ic+1）c)2，它可以将该结点上的数据集划分为两个子集，即描述属性AC的取值在区间A1c,vi的数据样本和在区间(vi，Atotalc的数据样本。由于描述属性Ac的最值序列包含total-1个分割点，所以它对数据集的划分有total一1

28、种方式。 41从total-1个分割点中选择最佳分割点。对于每一个分割点划分数据集的方式，C4.5计算它的信息增益比，并且从中选择信息增益比最大的分割点来划分数据集。 下面举例说明连续型描述属性的处理方法。将表52中的离散型描述属性A。(年龄)改为连续型描述属性，计算根结点上的分枝属性时，要用到表52中的所有数据样本，假设数据样本的年龄序列为(32，25，46，56，60，52，42，36，23，51，38，43，41，65)。在计算A：划分数据集的信息增益比时，需要进行如下处理。 对年龄序列由小到大排序，新的序列为23，25，32，36，38，41，42，43，46，51，52，56，606

29、5)。42对新的年龄序列生成分割点，由于样本数量为14，所以可以生成13个分割点。第一个分割点为(23+25)2=24，它可以将数据集划分为年龄在区间23，24的数据样本和在区间(24，653的数据样本，其余的分割点和划分方式同理可得。 选择最佳分割点，例如，对于第一个分割点，可以计算得到年龄在区间23，247和24，65的样本数量以及每个区间的数据样本中属于各个类别的样本数量。由此，根据式(56)式(511)，可以计算出第一个分割点的信息增益比。其余分割点的信息增益比同理可得。选择信息增益比最大的分割点作为描述属性A。(年龄)的最佳分割点。 43C45的算法步骤与图53所示的ID3的算法步骤

30、类似，只是将第(3)步中的信息增益改为信息增益比；而且当描述属性为连续型属性时，要将连续属性离散化，并且从中选择信息增益比最大的分割点将数据集划分为两个样本子集。因此，本节不再列出C45的算法步骤 4445465.3.4 决策树算法决策树算法C4.5lC4.5算法使用信息增益比来选择分枝算法使用信息增益比来选择分枝属性，克服了属性，克服了ID3算法使用信息增益时算法使用信息增益时偏向于取值较多的属性的不足偏向于取值较多的属性的不足l信息增益比的定义式为信息增益比的定义式为l其中其中d,.,2 , 1f ,)A(split)A(Gain)A(ratio_Gainfffd,.,2 , 1f , )totaln(logtotaln)A(splitq1ss2sf475.3.4 决策树算法决策树算法C4.5lC4.5既可以处理离散型描述属性，也既可以处理离散型描述属性，也可以处理连续型描述属性可以处理连续型描述属性 l对于连续值描述属性，对于连续值描述属性，C4.5将其转换将其转换为离散值属性为离散值属性l在在A1c,A2c,Atotalc中生成中生成total-1个分割个分割点点l第第i个分割点的取值设置个分割点的取值设置vi=(Aic+A(i+1)c)/2 l每个分割点将数据集划分为两个子集每个分割点将数据集划分为两个子集l挑选最适合的分割点对连续属性离散化挑选最适合的分割点对