数据仓库与数据挖掘原理及应用(第二版) 教学课件 ppt 作者 王丽珍 周丽华 陈红梅 第8章

第八章 分类与预测,2,第八章 目录,8.1 分类过程 8.2 决策树分类 8.3 前馈神经网络分类 8.4 贝叶斯分类 8.5 回归分析 8.6 本章小结,3,引言（1）,分类的任务是通过分析由已知类别数据对象组成的训练数据集，建立描述并区分数据对象类别的分类函数或分类模型（也常常称作分类器）。 分类的目的是利用分类模型预测未知类别数据对象的所属类别。,4,引言（2）,分类和聚类是两个容易混淆的概念，事实上它们具有显著区别。在分类中，为了建立分类模型而分析的数据对象的类别是已知的，然而，在聚类时处理的所有数据对象的类别都是未知的。因此，分类是有指导的，而聚类是无指导的。,5,引言（3）,数据分类与数值预测都是预测问题，都是首先通过分析训练数据集建立模型，然后利用模型预测数据对象。但是，在数据挖掘中，如果预测目标是数据对象在类别属性（离散属性）上的取值（类别），则称为分类；如果预测目标是数据对象在预测属性（连续属性）上的取值或取值区间，则称为预测。 例如，对100名男女进行体检，测量了身高和体重，但是事后发现，a和b两人忘了填写性别，c和d两人漏了记录体重。现在根据其他96人的情况，推断a和b两人的性别是分类，而估计c和d两人的体重是预测。,6,8.1 分类过程（1）,分类过程分为两个阶段：学习阶段与分类阶段，如图8.1所示，图中左边是学习阶段，右边是分类阶段。 图8.1 分类过程,7,8.1 分类过程（2）,1. 学习阶段 （1）建立分类模型：通过分类算法分析训练数据集建立分类模型。 训练数据集S中的元组或记录称为训练样本，每个训练样本由m+1个属性描述，其中有且仅有一个属性称为类别属性，表示训练样本所属的类别。属性集合可用矢量X=（A1, , Am, C）表示，其中Ai（1im）对应描述属性，可以具有不同的值域，当一个属性的值域为连续域时，该属性称为连续属性（Numerical Attribute），否则称为离散属性（Discrete Attribute）；C表示类别属性，C=（c1, c2, , ck），即训练数据集有k个不同的类别。,8,8.1 分类过程（3）,分类算法有决策树分类算法、神经网络分类算法、贝叶斯分类算法、k-最近邻分类算法、遗传分类算法、粗糙集分类算法、模糊集分类算法等。分类算法可以根据下列标准进行比较和评估。 1）准确率。涉及分类模型正确地预测新样本所属类别的能力。 2）速度。涉及建立和使用分类模型的计算开销。 3）强壮性。涉及给定噪声数据或具有空缺值的数据，分类模型正确地预测的能力。 4）可伸缩性。涉及给定大量数据，有效地建立分类模型的能力。 5）可解释性。涉及分类模型提供的理解和洞察的层次。 分类模型有分类规则、判定树等。,9,8.1 分类过程（4）,（2）评估分类模型的准确率：利用测试数据集评估分类模型的准确率。 测试数据集中的元组或记录称为测试样本。 分类模型正确分类的测试样本数占总测试样本数的百分比称为该分类模型的准确率。如果分类模型的准确率可以接受，就可以利用该分类模型对新样本进行分类。否则，需要重新建立分类模型。,10,8.1 分类过程（5）,评估分类模型准确率的方法有保持（holdout）、k-折交叉确认等。 保持方法将已知类别的样本随机地划分为训练数据集与测试数据集两个集合，一般，训练数据集占2/3，测试数据集占1/3。分类模型的建立在训练数据集上进行，分类模型准确率的评估在测试数据集上进行。 k-折交叉确认方法将已知类别的样本随机地划分为大小大致相等的k个子集S1, , Sk，并进行k次训练与测试。第i次，子集Si作为测试数据集，分类模型准确率的评估在其上进行，其余子集的并集作为训练数据集，分类模型的建立在其上进行。进行k次训练得到k个分类模型，当利用分类模型对测试样本或者新样本进行分类时，可以综合考虑k个分类模型的分类结果，将出现次数最多的分类结果作为最终的分类结果。,11,8.1 分类过程（6）,2. 分类阶段 分类阶段就是利用分类模型对未知类别的新样本进行分类。 数值预测过程： 与数据分类过程相似。首先通过分析由预测属性取值已知的数据对象组成的训练数据集，建立描述数据对象特征与预测属性之间的相关关系的预测模型，然后利用预测模型对预测属性取值未知的数据对象进行预测。 数值预测技术主要采用回归统计技术，例如，一元线性回归、多元线性回归、非线性回归等。,12,8.2 决策树分类 8.2.1 决策树（1）,决策树：一棵决策树由一个根节点，一组内部节点和一组叶节点组成。每个内部节点（包括根节点）表示在一个属性上的测试，每个分枝表示一个测试输出，每个叶节点表示一个类，有时不同的叶节点可以表示相同的类。,13,8.2.1 决策树（2）,图8.2 判断顾客是否购买计算机的决策树,14,8.2.1 决策树（3）,建立一棵决策树，需要解决的问题主要有： 1）如何选择测试属性？ 测试属性的选择顺序影响决策树的结构甚至决策树的准确率，一般使用信息增益度量来选择测试属性。 2）如何停止划分样本？ 从根节点测试属性开始，每个内部节点测试属性都把样本空间划分为若干个（子）区域，一般当某个（子）区域的样本同类时，就停止划分样本，有时也通过阈值提前停止划分样本。,15,8.2.2 建立决策树（1）,1. 算法思想及描述 首先，在整个训练数据集S、所有描述属性A1, A2, , Am上递归地建立决策树。即将S作为根节点；如果S中的样本属于同一类别，则将S作为叶节点并用其中的类别标识，决策树建立完成（递归出口）； 否则在S上计算当给定Ak（1km）时类别属性C的信息增益G(C, Ak)，选择信息增益最大的Ai作为根节点的测试属性；如果Ai的取值个数为v（取值记为a1, a2, , av），则Ai将S划分为v个子集S1, S2, , Sv（Sj（1jv）为S中Ai=aj的样本集合），同时根节点产生v个分枝与之对应。其次，分别在训练数据子集S1, S2, , Sv、剩余描述属性A1, , Ai-1, Ai+1, , Am上采用相同方法递归地建立决策树子树（递归）。,16,8.2.2 建立决策树（2）,可能出现如下情况，需要停止建立决策（子）树的递归过程。 1）某节点对应的训练数据（子）集为空。此时，该节点作为叶节点并用父节点中占多数的样本类别标识。 2）某节点没有对应的（剩余）描述属性。此时，该节点作为叶节点并用该节点中占多数的样本类别标识。,17,8.2.2 建立决策树（3）,算法：决策树分类算法Generate_decision_tree（S, A） 输入：训练数据集S，描述属性集合A 输出：决策树 步骤： （1）创建对应S的节点Node （2）if S中的样本属于同一类别c then 以c标识Node并将Node作为叶节点返回 （3）if A为空 then 以S中占多数的样本类别c标识Node并将Node作为叶节点返回,18,8.2.2 建立决策树（4）,（4）从A中选择对S而言信息增益最大的描述属性Ai作为Node的测试属性 （5）for Ai的每个可能取值aj（1jv ）/设Ai的可能取值为a1, a2, , av （5.1）产生S的一个子集Sj /Sj（1jv）为S中Ai=aj的样本集合 （5.2）if Sj为空 then 创建对应Sj的节点Nj，以S中占多数的样本类别c标识Nj，并将Nj作为叶节点形成Node的一个分枝 （5.3）else 由Generate_decision_tree（Sj, A-Ai）创建子树形成Node的一个分枝,19,8.2.2 建立决策树（5）,2. 信息增益：在决策树分类算法中使用信息增益度量来选择测试属性。 从信息论角度看，通过描述属性可以减少类别属性的不确定性。 假设有蕃茄、茄子、黄瓜三种蔬菜，现在对某蔬菜分类。在不给任何描述时，该蔬菜可能是蕃茄、茄子、黄瓜三种之一，不确定性大。在给出该蔬菜是“长的”形状描述时，该蔬菜可能是茄子、黄瓜两种之一，不确定性减小。在给出该蔬菜是“紫的”颜色描述时，该蔬菜只可能是茄子了，不确定性为零。,20,8.2.2 建立决策树（6）,离散型随机变量X的无条件熵定义为 式中，p(xi)为X= xi的概率；u为X的可能取值个数。 根据H(X)的极值性，当 时，即当不确定性最大时，H(X)最大。根据H(X)的确定性，当 时，即当不确定性为零时，H(X)=0。所以，H(X)反映X的不确定性。,21,8.2.2 建立决策树（7）,给定离散型随机变量Y，离散型随机变量X的条件熵定义为 式中，p(xiyj)为X=xi, Y=yj的联合概率；p(xi/yj)为已知Y=yj时，X= xi的条件概率；u，v分别为X，Y的可能取值个数。 可以证明，H(X/Y)H(X)。所以，通过Y可以减少X的不确定性。,22,8.2.2 建立决策树（8）,假设训练数据集是关系数据表r1, r2, , rn，其中描述属性为A1, A2, , Am、类别属性为C，类别属性C的无条件熵定义为 式中，u为C的可能取值个数，即类别个数，类别记为c1, c2, , cu；si为属于类别ci的记录集合，|si|即为属于类别ci的记录总数。,23,8.2.2 建立决策树（9）,给定描述属性Ak（1km），类别属性C的条件熵定义为 式中，v为Ak的可能取值个数，取值记为a1, a2, , av；sj为Ak=aj的记录集合，|sj|即为Ak=aj的记录数目；sij为Ak=aj且属于类别ci的记录集合，|sij|即为Ak=aj且属于类别ci的记录数目。,24,8.2.2 建立决策树（10）,不同描述属性减少类别属性不确定性的程度不同，即不同描述属性对减少类别属性不确定性的贡献不同。 例如，假设有蕃茄、茄子、黄瓜三种蔬菜，现在对某蔬菜分类，形状描述与颜色描述的贡献是不同的。在给出该蔬菜的颜色描述时，如果颜色是红的，则该蔬菜是蕃茄；如果颜色是紫的，则该蔬菜是茄子；如果颜色是绿的，则该蔬菜是黄瓜，不确定性减少为0。而在给出该蔬菜的形状描述时，如果形状是圆的，则该蔬菜是蕃茄；如果形状是长的，则该蔬菜可能是茄子，也可能是黄瓜，不确定性还是存在。,25,8.2.2 建立决策树（11）,采用类别属性的无条件熵与条件熵的差（信息增益）来度量描述属性减少类别属性不确定性的程度。 给定描述属性Ak（1km），类别属性C的信息增益定义为 G(C, Ak)=E(C)-E(C, Ak) 可以看出，G(C, Ak)反映Ak减少C不确定性的程度，G(C, Ak)越大，Ak对减少C不确定性的贡献越大。,26,8.2.2 建立决策树（12）,例8.1 假设蔬菜数据表如表8.1所示，“颜色”、“形状”是描述属性，“蔬菜”是类别属性，分别求给定“颜色”、“形状”属性时，“蔬菜”属性的信息增益。,27,8.2.2 建立决策树（13）,G(蔬菜，颜色)1.5850-0=1.5850 G(蔬菜，形状)1.5850-0.6667=0.9183,28,8.2.2 建立决策树（14）,例8.2 建立例8.1的决策树。 因为G(蔬菜，颜色)G(蔬菜，形状)，所以选择“颜色”属性作为根节点的测试属性，得到的决策树如图8.3所示。 图8.3 例8.1的决策树,29,8.2.2 建立决策树（15）,例8.3 假设顾客数据表如表8.2所示，“购买计算机”属性是类别属性，其余属性是描述属性，建立决策树。 考虑根节点： G(购买计算机，年龄)=0.246 G(购买计算机，收入)=0.029 G(购买计算机，学生)=0.151 G(购买计算机，信誉)=0.048 所以根节点的测试属性为“年龄” 考虑分枝“年龄='30'”节点 G(购买计算机，收入)=0.571 G(购买计算机，学生)=0.971 G(购买计算机，信誉)=0.02 所以分枝“年龄='30'”节点的测试属性为“学生”,30,8.2.2 建