第七章 分类与预测（课堂PPT）

数据挖掘,主讲：王名扬信息与计算机工程学院,1,2,引言要挖掘知识的类型,概念描述：特征化和比较；关联规则；分类/预测；聚类分析；其他的数据挖掘任务。,引言,根据现有的知识，我们得到了一些关于爬行动物和鸟类的信息，我们能否对新发现的物种，比如动物A，动物B进行分类？,3,2,4,分类是数据挖掘中重要的任务,分类的目的是学会一个分类器（分类函数或模型），该分类器能把待分类的数据映射到给定的类别中。分类可用于预测。从历史数据纪录中自动推导出对给定数据的推广描述，从而能对未来数据进行类预测。,2,5,分类方法的类型,从使用的主要技术上看，可以把分类方法归结为以下几种类型：基于距离的分类方法决策树分类方法贝叶斯分类方法。本章主要围绕这几种分类方法展开。,第6章,分类与预测,6,6.1分类与预测的基本知识6.2基于距离的分类算法6.3决策树分类方法6.4贝叶斯分类方法6.5规则归纳方法*,第6章,7,6.1分类和预测的基本知识,什么是分类？预测？分类和预测的基本问题,8,1.分类？预测？,9,10,基本概念,分类和预测是两种数据分析的形式，可用于提取描述重要数据类的模型或预测未来的数据趋势：分类（classification）：用于预测数据对象的分类标号（或离散值），如，通过构造分类模型对银行贷款进行风险评估（安全或危险）；预测（predication）：用于预测数据对象的连续取值，如，建立预测模型利用顾客收入与职业（参数）预测其可能用于购买计算机设备的支出大小。,11,数据分类过程,数据分类是一个两步的过程：1）建立分类模型：机器学习过程，通过某种分类算法对训练集进行训练，得到分类模型；“有指导的学习”、“有监督的学习”假定每个元组属于一个预定义的类，由一个称为类标号属性的属性确定；训练数据集：为建立分类模型而被分析的数据元组。,12,分类过程的第一步：学习建模,13,数据分类过程,数据分类是一个两步的过程：2）使用模型进行分类：测试数据集：用于评估模型的预测准确率。模型在测试集上的准确率是正确被模型分类的测试样本所占的百分比。如认为模型的准确率可以接受，就可以用它来对类标号未知的数据元组或对象进行分类。,14,分类过程的第二步：分类测试,15,分类过程示意图,有指导的学习VS.无指导的学习,有指导的学习（用于分类）训练样本的类标号已知；新数据使用训练数据集中得到的规则进行分类无指导的学习（用于聚类）训练样本的类标号未知；通过一系列的度量、观察，试图确立数据中的类或聚类的存在,16,17,数据预测,预测：构造和使用模型评估无标号样本类，或评估给定样本可能具有的属性值或值区间与分类区别：二者是两类主要的预测问题。分类是预测离散或标号值；预测是预测连续或有序值；观点：用预测法预测类标号为分类；用预测法预测连续值（一般用回归法）为预测。,18,示例,背景：假定已建立AllElectronics公司的邮寄清单数据库。邮寄清单用于分发介绍新产品和降价信息材料。数据库描述顾客的属性，包括姓名、年龄、收入、职业和信誉度，并按照顾客是否在该公司购买计算机进行分类。,19,示例,分类模型：假定新的顾客添加到数据库中，由于向每位顾客分发促销材料费用很高，因此，可以根据数据库中已有顾客信息构建分类模型，用以预测需向哪些顾客分发材料。预测模型：假定想预测在一个财政年度，一个顾客将在AllElectronics进行的主要的购买的数量，则可以构建一个预测模型。,2.分类和预测的基本问题？,20,21,问题(1)：数据准备,1）准备分类和预测的数据：数据的预处理数据清理：噪声（平滑技术）；空缺值（统计手段）相关性分析（特征选择）：删除不相关和冗余属性，如银行贷款申请时填写的星期数，可能与贷款是否申请成功无关；数据变换：数据离散化（数据概化）：如属性“收入”的数值就可以被离散化为若干区间，如低、中等和高；数据规范化：将给定属性的值按比例缩放至较小的区间，如0,1。,22,问题(2)：评估分类模型,2）评估方法：对用于分类或预测的方法或模型进行评估预测的准确率：模型正确预测未知对象类别或数值的能力；速度：1）建立模型的时间；2）使用模型的时间强壮性（鲁棒性）：处理噪声和空缺值的能力；可伸缩（扩展）性：处理大型数据及构造模型的能力；可理解性：模型的可理解能力；规则的优越性：1）判定树的大小；2）分类规则的简洁性。,6.2基于距离的分类算法,基本思想？几种常见的距离分类算法？,23,1.基于距离分类的基本思想？,24,2,25,基于距离的分类算法的思路,定义：给定一个数据库D=t1，t2，tn和一组类C=C1，Cm。假定每个元组包括一些数值型的属性值：ti=ti1，ti2，tik，每个类也包含数值性属性值：Cj=Cj1，Cj2，Cjk，则分类问题是要分配每个ti到满足如下条件的类Cj：sim(ti，Cj)=sim(ti，Ci)，CiC，CiCj，其中sim(ti，Cj)被称为相似性。,2,26,基于距离的分类算法的思路,在实际的计算中往往用距离来表征：距离越近，相似性越大；距离越远，相似性越小。如何度量距离？欧几里得距离；曼哈坦距离；明考斯基距离；加权的明考斯基距离。,如何度量距离？,27,欧几里得距离与曼哈顿距离的共同点：(1)即距离是一个非负的数值(2)自身的距离为0(3)即距离函数具有对称性(4)即距离函数满足三角不等式,如何度量距离？,28,(三)明可夫斯基距离是欧几里得距离和曼哈顿距离的概化,其中p是一个正整数：当p=1时，表示曼哈顿距离；当p=2时，表示欧几里得距离。,(四)加权的明可夫斯基距离如果对每一个变量根据其重要性赋予一个权重，就得到加权的明考斯基距离。,如何度量距离？,29,2,30,基于距离的分类算法的思路,在实际的计算中往往用距离来表征：距离越近，相似性越大；距离越远，相似性越小。距离的计算方法有多种，最常用的是通过计算样本到每个类中心的距离来完成。,2,31,基于距离的分类算法的一般性描述,算法计算每个元组到各个类中心的距离，从而可以找出离它的最近的类中心，得到确定的类别标记。,算法基于距离的分类算法输入：每个类的中心C1，Cm；待分类的元组t。输出：输出类别c。（1）dist=；/距离初始化（2）FORi:=1tomDO（3）IFdis(ci，t)0，F1:0,则在事件B已经发生的条件下，事件A发生的条件概率：,联合概率：若对任意两事件A、B都有P(A)0，P(B)0,则：P(AB)=P(A)P(BA)=P(B)P(AB),边际概率：若A1、A2构成互斥和完整的两个事件，A1和A2中的一个出现是事件B发生的必要条件，则事件B的边际概率公式为（全概率公式）：P(B)=P(BA1)P(A1)+P(BA2)P(A2),148,贝叶斯定理,贝叶斯定理是关于随机事件A和B的条件概率和边缘概率的一则定理。通常，事件A在事件B发生的条件下的概率，与事件B在事件A发生的条件下的概率是不一样的，然而，这两者是有确定的关系的，贝叶斯定理就是这种关系的陈述。,149,贝叶斯定理,由前面三个概率公式可以得到贝叶斯公式：,全概率：P(B)=P(BA1)P(A1)+P(BA2)P(A2),条件概率：,联合概率：P(AB)=P(A)P(BA)=P(B)P(AB),150,贝叶斯定理,两个事件的贝叶斯公式：若A1、A2构成互斥和完整的两个事件，A1和A2中的一个出现是事件B发生的必要条件，则两个事件的贝叶斯公式：,151,贝叶斯定理,n个事件的贝叶斯公式：假定存在一个互斥和完整的事件A1,A2,An，Ai中的某一个出现是事件B发生的必要条件，则n个事件的贝叶斯公式：,152,贝叶斯定理,在贝叶斯定理中，每个名词都有约定俗成的名称：P(A)：事件A的先验概率或边缘概率。“先验”指其不考虑任何B方面的因素。P(AB)：事件A的后验概率，即已知B发生后A的条件概率。P(BA)：事件B的后验概率，即已知A发生后B的条件概率。P(B)：是事件B的先验概率或边缘概率。,示例1,背景：办公室新来了一个雇员小王，小王是好人还是坏人，大家都在猜测。按人们的主观意识，一个人是好人还是坏人的概率均为0.5，坏人总是要做坏事，好人总是做好事，偶尔也会做一件坏事。一般好人做好事的概率是0.9，坏人做好事的概率是0.2.一天，小王做了一件好事，则小王是好人的概率有多大，小王究竟为好人还是坏人？,153,示例1,154,155,旅客搭乘飞机必须经电子仪器检查是否身上携带金属物品。如果携带金属，仪器会发出声音的概率是97%，但身上无金属物品仪器会发出声音的概率是5%。已知一般乘客身上带有金属物品的概率是30%，若某旅客经过仪器检查时发出声音，请问他身上有金属物品的概率是多少？,2,示例2,156,2,解：设C1=“有金属物”，X=“仪器会发声”，则,157,贝叶斯分类,设X为一个类别未知的数据样本，设H为某种假设，如：数据样本X属于某特定的类C。对于分类问题，我们希望确定P(HX)，即给定观测数据样本X，假定H成立的概率。,贝叶斯分类,设x是一个类别未知的数据样本，cj为某个类别，若数据样本x属于一个特定的类别cj，那么分类问题就是决定P(cj|x)，即在获得数据样本x时，确定x的最佳分类。,158,先验概率P(cj),后验概率P(x|cj),后验概率P(cj|x),贝叶斯分类,159,先验概率P(cj),P(cj)为类cj的先验概率(priorprobability)，它反映了我们所拥有的关于cj是正确分类的背景知识。通常可以用样例中属于cj的样例数|cj|比上总样例数|D|来近似，即:,160,后验概率P(x|cj)指的是当已知类别为cj的条件下，样本x出现的概率。,后验概率P(x|cj),若设x=，且属性值相互条件独立，即在属性间，不存在依赖关系，则P(x|cj)=P(a1,a2am|cj),161,后验概率P(cj|x),即给定数据样本x时cj成立的概率，而这正是我们所感兴趣的。,P(cj|x)被称为C的后验概率（posteriorprobability），因为它反映了在得到数据样本x后cj成立的置信度.,162,贝叶斯分类,计算Pmax(ci|x)=maxP(cj|x)j(1,|C|),则Pmax(ci|x)称为最大后验概率，并将x分到ci类中.,163,2.朴素贝叶斯分类？,164,朴素贝叶斯分类的工作过程,（1）每个数据样本X用一个n维特征向量：X=x1,x2,xn表示，分别描述对n个属性(A1,A2,An)的具体取值；（2）假定共有m个不同类别，C1,C2,Cm。给定一个类别未知的数据样本X，分类法将在已知X情况下，将X赋于后验概率最大的那个类别。即，朴素贝叶斯分类将类别未知的样本X归属到类别Ci，当且仅当：,即，最大化P(CiX)。其中的类别Ci称为最大后验假定。根据贝叶斯定理，有：,165,朴素贝叶斯分类的工作过程,（3）由于P(X)对于所有的类别均是相同的，因此只需要计算P(XCi)P(Ci)取最大即可。如果各类别的先验概率未知，通常假定这些类是等概率的，即：P(C1)=P(C2)=P(Cm)。这样变成只需要对P(XCi)求最大，否则就要P(XCi)P(Ci)取最大。否则，一般可以通过P(Ci)=si/s进行估算，其中si为训练样本集合中类别Ci的个数，s为整个训练样本集合的大小。,166,朴素贝叶斯分类的工作过程,（4）对于包含多个属性的数据集，直接计算P(XCi)的运算量是非常大的。为实现对P(XCi)的有效估算，朴素贝叶斯分类通常假设各属性是相互独立的，即在属性间，不存在依赖关系，则对于给定的类别Ci，有：,而P(x1Ci),P(x2Ci),P(xnCi)的值，可以由训练样本集进行估算。具体处理如下：,167,朴素贝叶斯分类的工作过程,1）如果Ak是符号属性，则P(xkCi)=sik/si，：其中sik为训练样本中类别为Ci且属性Ak取值vk的样本数，si为训练样本中类别为Ci的样本数。,168,朴素贝叶斯分类的工作过程,169,朴素贝叶斯分类的工作过程,（5）为预测一个未知样本X的类别，对每个类Ci，计算P(XCi)P(Ci)。则，样本X被指派到类Ci，当且仅当：P(XCi)P(Ci)P(XCj)P(Cj),170,朴素贝叶斯分类的效果,研究表明，与决策树和神经网络分类器相比，贝叶斯分类器在某些情况下具有更好的分类效果。但必须满足某些假定条件，如要求各属性间是相互独立的。,171,172,示例,示例,背景：给定与决策树归纳相同的训练数据集，希望使用朴素贝叶斯分类预测未知样本的类标号。基本信息：1）数据样本用age,income,student,credit-rating描述。类标号属性buys_computer具有两个不同取值yes,no。2）设C1对应类“yes”，C2对应类“no”。3）需分类的未知样本为：X=(age=“=30”,income=“medium”,student=“yes”,credit-rating=“fair”),173,示例,根据贝叶斯分类公式：由于P(X)对于所有的类别均是相同的，因此只需要计算P(XCi)P(Ci)取最大即可。P(Ci）为先验概率，可用如下公式计算：P(Ci)=si/s。对于P(XCi)，在假定各属性是相互独立的前提下，可按照如下公式计算：,174,P(Ci)的计算,P(Ci)为类别的先验概率，i=1,2，具体计算如下：,175,P(XCi)的计算,X=(age=“=30”,income=“medium”,student=“yes”,credit-rating=“fair”),176,结论,计算P(XCi)P(Ci)，并取最大值：,基于,177,朴素贝叶斯的独立假设,基本贝叶斯分类器是基于各属性相互独立这一假设来进行分类计算的：即，若给定一个数据样本类别，其样本属性的取值应是相互独立的。若假设成立，则与其他分类方法相比，朴素贝叶斯分类器应是最准确的。但实际中很少满足，因为变量间的相互依赖较为常见。克服方法：贝叶斯信念网络：决策树：每次只考虑一个属性。,178,3.贝叶斯信念网络？,179,180,基本概念,贝叶斯定理将数据信息与真实世界的信息（先验信息）联系在一起。除提供一种计算后验概率的方法外，贝叶斯定理的优势还在于能够帮助人们建立起分析复杂真实世界的模型贝叶斯信念网络。,181,基本概念,贝叶斯网络亦称贝叶斯信念网络，于1985年由JudeaPearl提出，它是一种模拟人类推理过程中因果关系的不确定性推理模型，其网络拓扑结构是一个有向无环图。节点用随机变量或命题标识，认为有直接关系的命题或变量用弧连接，例如，假设节点E直接影响到节点H，则建立从节点E到H的有向弧(E,H)，权值（即，连接强度）用条件概率P(HE)表示。,182,基本概念,一旦命题间直接的相关性由有向弧表示，条件概率由弧的权值来表示，则命题之间的静态结构关系的有关知识就表示出来了。,183,区别,朴素贝叶斯分类假定一个属性值对给定类的影响独立于其他属性的值，即在属性间不存在依赖关系，也因此被称为“朴素的”。贝叶斯信念网络也可以用于分类，它是图形模型。它优于朴素贝叶斯，能够处理属性子集间有依赖关系的分类。,184,贝叶斯信念网络的组成,贝叶斯信念网络由两部分组成：（1）有向无环图：每个节点代表一个随机变量，每条弧代表一个概率依赖。若存在一条从节点Y指向节点Z的弧，则Y是Z的一个父节点（双亲、前驱），而Z是Y的一个子节点（后继）。,185,示例,一个简单的贝叶斯信念网络示意图,186,示例,上图给出一个简单的贝叶斯信念网络的示意图：表示一个人是否患肺癌，既与他的家庭的肺癌史有关，也与该人是否吸烟有关。图中的弧同时也表示在给定父节点FamilyHistory和Smoker情况下，变量LungCancer有条件独立于Emphysema（肺气肿），这也就意味着若知道FamilyHistory和Smoker的值，变量Emphysema就不会提供任何有关LungCancer的附加信息。,187,贝叶斯信念网络的组成,贝叶斯信念网络由两部分组成：（2