第七章-分类与预测.ppt

数据挖掘,主讲：王名扬 信息与计算机工程学院,2,引 言要挖掘知识的类型,概念描述：特征化和比较； 关联规则； 分类/预测； 聚类分析； 其他的数据挖掘任务。,引 言,根据现有的知识，我们得到了一些关于爬行动物和鸟类的信息，我们能否对新发现的物种，比如动物A，动物B进行分类？,2019年11月3日星期日,4,分类是数据挖掘中重要的任务,分类的目的是学会一个分类器（分类函数或模型），该分类器能把待分类的数据映射到给定的类别中。 分类可用于预测。从历史数据纪录中自动推导出对给定数据的推广描述，从而能对未来数据进行类预测。,2019年11月3日星期日,5,分类方法的类型,从使用的主要技术上看，可以把分类方法归结为以下几种类型： 基于距离的分类方法 决策树分类方法 贝叶斯分类方法。 本章主要围绕这几种分类方法展开。,第 6 章,分类与预测,6.1 分类与预测的基本知识 6.2 基于距离的分类算法 6.3 决策树分类方法 6.4 贝叶斯分类方法 6.5 规则归纳方法*,第 6 章,6.1 分类和预测的基本知识,什么是分类？预测？ 分类和预测的基本问题,1. 分类？预测？,10,基本概念,分类和预测是两种数据分析的形式，可用于提取描述重要数据类的模型或预测未来的数据趋势： 分类（classification）：用于预测数据对象的分类标号（或离散值），如，通过构造分类模型对银行贷款进行风险评估（安全或危险）； 预测（predication）：用于预测数据对象的连续取值，如，建立预测模型利用顾客收入与职业（参数）预测其可能用于购买计算机设备的支出大小。,11,数据分类过程,数据分类是一个两步的过程： 1）建立分类模型：机器学习过程，通过某种分类算法对训练集进行训练，得到分类模型；“有指导的学习”、“有监督的学习” 假定每个元组属于一个预定义的类，由一个称为类标号属性的属性确定； 训练数据集：为建立分类模型而被分析的数据元组。,12,分类过程的第一步：学习建模,13,数据分类过程,数据分类是一个两步的过程： 2）使用模型进行分类： 测试数据集：用于评估模型的预测准确率。模型在测试集上的准确率是正确被模型分类的测试样本所占的百分比。 如认为模型的准确率可以接受，就可以用它来对类标号未知的数据元组或对象进行分类。,14,分类过程的第二步：分类测试,15,分类过程示意图,有指导的学习 VS. 无指导的学习,有指导的学习（用于分类） 训练样本的类标号已知； 新数据使用训练数据集中得到的规则进行分类 无指导的学习（用于聚类） 训练样本的类标号未知； 通过一系列的度量、观察，试图确立数据中的类或聚类的存在,17,数据预测,预测： 构造和使用模型评估无标号样本类 ，或评估给定样本可能具有的属性值或值区间 与分类区别： 二者是两类主要的预测问题。 分类是预测离散或标号值； 预测是预测连续或有序值； 观点：用预测法预测类标号为分类；用预测法预测连续值（一般用回归法）为预测。,18,示例,背景： 假定已建立AllElectronics公司的邮寄清单数据库。邮寄清单用于分发介绍新产品和降价信息材料。数据库描述顾客的属性，包括姓名、年龄、收入、职业和信誉度，并按照顾客是否在该公司购买计算机进行分类。,19,示例,分类模型： 假定新的顾客添加到数据库中，由于向每位顾客分发促销材料费用很高，因此，可以根据数据库中已有顾客信息构建分类模型，用以预测需向哪些顾客分发材料。 预测模型： 假定想预测在一个财政年度，一个顾客将在AllElectronics进行的主要的购买的数量，则可以构建一个预测模型。,2. 分类和预测的基本问题？,21,问题(1)：数据准备,1）准备分类和预测的数据：数据的预处理 数据清理：噪声（平滑技术）；空缺值（统计手段） 相关性分析（特征选择）：删除不相关和冗余属性，如银行贷款申请时填写的星期数，可能与贷款是否申请成功无关； 数据变换： 数据离散化（数据概化）：如属性“收入”的数值就可以被离散化为若干区间，如低、中等和高； 数据规范化：将给定属性的值按比例缩放至较小的区间，如0,1。,22,问题(2)：评估分类模型,2）评估方法：对用于分类或预测的方法或模型进行评估 预测的准确率：模型正确预测未知对象类别或数值的能力； 速度：1）建立模型的时间；2）使用模型的时间 强壮性（鲁棒性）：处理噪声和空缺值的能力； 可伸缩（扩展）性：处理大型数据及构造模型的能力； 可理解性：模型的可理解能力； 规则的优越性：1）判定树的大小；2）分类规则的简洁性。,6.2 基于距离的分类算法,基本思想？ 几种常见的距离分类算法？,1. 基于距离分类的基本思想？,2019年11月3日星期日,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)被称为相似性。,2019年11月3日星期日,26,基于距离的分类算法的思路,在实际的计算中往往用距离来表征： 距离越近，相似性越大； 距离越远，相似性越小。 如何度量距离？ 欧几里得距离； 曼哈坦距离； 明考斯基距离； 加权的明考斯基距离。,如何度量距离？,欧几里得距离与曼哈顿距离的共同点： (1)即距离是一个非负的数值 (2)自身的距离为0 (3)即距离函数具有对称性 (4)即距离函数满足三角不等式,如何度量距离？,(三)明可夫斯基距离 是欧几里得距离和曼哈顿距离的概化,其中p是一个正整数：当p=1时，表示曼哈顿距离；当p=2时，表示欧几里得距离。,(四)加权的明可夫斯基距离 如果对每一个变量根据其重要性赋予一个权重，就得到加权的明考斯基距离。,如何度量距离？,2019年11月3日星期日,30,基于距离的分类算法的思路,在实际的计算中往往用距离来表征： 距离越近，相似性越大； 距离越远，相似性越小。 距离的计算方法有多种，最常用的是通过计算样本到每个类中心的距离来完成。,2019年11月3日星期日,31,基于距离的分类算法的一般性描述,算法计算每个元组到各个类中心的距离，从而可以找出离它的最近的类中心，得到确定的类别标记。,算法 基于距离的分类算法 输入：每个类的中心C1，Cm；待分类的元组t。 输出：输出类别c。 （1）dist=；/距离初始化 （2）FOR i:=1 to m DO （3） IF dis(ci，t)dist THEN BEGIN （4） c i； （5） distdist(ci，t)； （6） END.,2019年11月3日星期日,32,基于距离的分类方法的直观解释,（a）类定义,（b）待分类样例,（c）分类结果,33,距离分类例题,例： C1=(3,3,4,2), C2=(8,5,-1,-7), C3=(-5,-7,6,10); 请用基于距离的算法给以下样本分类： A (5,5,0,0); B(5,5,-5,-5); C(-5,-5,5,5),34,距离分类例题,欧几里得距离： d(A,C1)=(3-5)2+(3-5)2+(4-0)2+(2-0)2)1/2=5.3; d(A,C2)=(8-5)2+(5-5)2+(-5-0)2+(-5-0)2)1/2=7.7; d(A,C3)=(-5-5)2+(-7-5)2+(5-0)2+(5-0)2)1/2=17.1 显然应该将A划入C1类。,2 几种常见的距离分类算法？,36,几种常见的距离分类算法,（1）k-近邻算法； （2）K-means算法（聚类）； （3）K-mediods算法（聚类）。,2019年11月3日星期日,37,（1）K-近邻分类算法,K-近邻分类算法（K Nearest Neighbors，简称KNN）通过计算每个训练数据到待分类元组的距离，取和待分类元组距离最近的K个训练数据，K个数据中哪个类别的训练数据占多数，则待分类元组就属于哪个类别。,2019年11月3日星期日,38,（1）K-近邻分类算法,算法 4-2 K-近邻分类算法 输入： 训练数据T；近邻数目K；待分类的元组t。 输出： 输出类别c。 （1）N=； （2）FOR each d T DO BEGIN （3） IF |N|K THEN （4） N=Nd； （5） ELSE （6） IF u N such that sim(t，u)sim(t，d) THEN BEGIN （7） N=N-u； （8） N=Nd； （9） END （10）END （11）c=class to which the most uN.,KNN的直观解释,1、定义的直观形式： 找出与目标最接近的K个样本； 将目标划分到找出的K个样本中出现最频繁的类。 2、K的直观形式： 以目标样本为中心； 划出一个刚好包含K个样本的圆； 当K增大时，圆半径增大。,KNN的直观解释,3、直观的例子 手写识别 记录手写体特征； 计算手写体与标准汉字的相似度； 根据相似度（距离），找出K个备选集； 选择一个正确汉字 人种识别 欧洲人的鼻子、亚洲人的眼睛 非洲人的肤色、亚洲人的头发,形象的例子,KNN的分类思想 如果它走路像鸭子, 叫声也像鸭子, 那么它可能就是只鸭子,KNN的特点,1、非参数统计方法 不需引入参数 回归分析是参数统计方法 2、k的选择 K=1时，将待分类样本划入与其最接近的样本的类； K=|X|时，仅根据训练样本进行频率统计，将待分类样本划入最多的类； K需要合理选择，太小容易受干扰、太大增加计算复杂性 3、算法的复杂度 维数灾难：当维数增加时，算法的复杂度会急剧增加 一般采用降维处理,6.3 决策树分类算法,决策树的基本概念？ 决策树生成算法？ 剪枝方法？ 提取分类规则？,1. 决策树的基本概念？,决策树基本概念,解决分类问题的一般方法,学习算法,学习模型,模型,应用模型,训练集（类标号已知）,检验集（类标号未知）,归纳,推论,46,基本概念,决策树（decision tree）： 决策树是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策树对新数据进行分析。 本质上决策树是通过一系列规则对数据进行分类的过程。,年龄？,学生？,信誉？,青,中,老,否,是,优,良,47,决策树的基本组成,决策树的基本组成 决策树是类似流程图的倒立的树型结构。 最顶层节点为根节点，是整个决策树的开始； 树的每个内部节点表示在一个属性上的测试，其每个分支代表一个测试输出； 树的每个叶节点代表一个类别。,年龄？,学生？,信誉？,青,中,老,否,是,优,良,48,基本概念,决策树的生成包括两个过程： （1）树的建立 首先所有训练样本都在根节点； 依据所选的属性循环地划分样本。 （2） 树剪枝（tree pruning）： 在决策树构造时，许多分支可能反映的是训练数据中的噪声或孤立点。 树剪枝就是识别并消除这类分支，以提高在未知数据上分类的准确性。,49,2. 决策树的生成算法？,51,决策树的生成算法,基本的决策树生成算法是一个贪心算法，采用自上而下、分而治之的递归方式来构造。 决策树上的各个分支是在对数据不断分组的过程中逐渐生长出来的。 首先，选择一个属性作为根节点，然后把该属性的每一个可能的值作为子节点，这样就把整个训练集分成了几个子集，根节点属性的每个取值都对应着一个子集，然后递归应用到每个子树上进行进一步划分，直到对所有数据的继续分组不再有意义时，决策树的生长过程宣告结束，此时便生成了一棵完整的决策树。其中，测试属性的选择是构建决策树的关键环节，不同的决策树算法在此使用的技术都不尽相同。,52,决策树的生成算法,注意： 在决策树算法中，所有属性均为符号值，即离散值，因此若有取连续值的属性，必须首先进行离散化。,53,决策树的生成算法,常见的有如下几种决策树生成算法： CLS; ID3; C4.5; CART。,（1）CLS（Concept Learning System）算法,CLS算法是早期的决策树学习算法。它是许多决策树学习算法的基础。 CLS基本思想 从一棵空决策树开始，选择某一属性（分类属性）作为测试属性。该测试属性对应决策树中的决策结点。根据该属性的值的不同，可将训练样本分成相应的子集，如果该子集为空，或该子集中的样本属于同一个类，则该子集为叶结点，否则该子集对应于决策树的内部结点，即测试结点，需要选择一个新的分类属性对该子集进行划分，直到所有的子集都为空或者属于同一类。,CLS算法,CLS算法-决策树的构建,眼睛颜色,1,6,2,4,8,3,5,7,黑色,蓝色,灰色,不属于同一类，非叶结点,眼睛颜色,头发颜色,头发颜色,头发颜色,黑色,兰色,灰色,CLS算法,黄种人1,混血6,白种人2,白种人4,混血8,白种人3,白种人5,混血7,黑色,金色,金色,红色,黑色,金色,红色,黑色,CLS算法,1） 生成一颗空决策树和一张训练样本属性集; 2） 若训练样本集T 中所有的样本都属于同一类，则生成结点T ，并终止学习算法；否则 3） 根据某种策略从训练样本属性表中选择属性A 作为测试属性， 生成测试结点A 4） 若A的取值为v1,v2,vm， 则根据A 的取值的不同，将T 划分成 m个子集T1,T2,Tm; 5） 从训练样本属性表中删除属性A; 6） 转步骤2, 对每个子集递归调用CLS。,CLS算法存在的问题,在步骤3中，根据某种策略从训练样本属性表中选择属性A作为测试属性，没有规定选择测试属性的标准和依据。 实践表明，测试属性集的组成以及测试属性的先后对决策树的学习具有举足轻重的影响。 举例：下表为调查学生膳食结构和缺钙情况的关系，其中1表示包含食物，0表示不包含。,学生膳食结构和缺钙调查表,CLS算法存在的问题,采用不同的测试属性及其先后顺序将会生成不同的决策树,鸡肉,猪肉,猪肉,牛肉,牛肉,牛肉,不缺钙（2）,缺钙（3，6）,不缺钙（4）,不缺钙（10）,缺钙（5）,不缺钙（1）,鱼肉,缺钙（5）,不缺钙（7，9）,是,否,是,否,否,否,否,否,否,是,是,是,是,是,CLS算法存在的问题,牛奶,不缺钙 （1，2，4， 7，9，10）,缺钙 （3，5，6，8）,在上例中，显然生成的两种决策树的复杂性和分类意义相差很大. 由此可见，选择测试属性是决策树学习算法中需要研究的重要课题。,CLS算法存在的问题,（2）ID3算法,ID3算法主要针对属性选择问题，是决策树学习方法中最具影响和最为典型的算法。 ID3使用信息增益度选择测试属性。 选择当前所有分割属性中，信息增益最大的属性作为测试属性，该属性最能消除不确定性。,64,（2）ID3算法,类比：生活工作中的决策（做/不做？） 我们总是倾向于选择最具有决定性意义的辅助条件进行判定。 如：打不打室外羽毛球？ 是否刮风是最具有决定意义的因素。 如何度量信息量的大小？,ID3 信息量大小的度量,Shannon在1948年提出的信息论理论中，指出事件ai的信息量I( ai )可如下度量：,其中p(ai)表示事件ai发生的概率。 假设有n个互不相容的事件a1,a2,a3,.,an，则其平均的信息量 可如下度量：,上式中，对数底数可以为任何数，不同的取值对应了熵的不同单位。 通常取2，并规定当p(ai)=0时， =0,ID3 信息量大小的度量,68,ID3-属性选择方法,设S为包含s个数据样本的集合，假定类别属性C具有m个不同值Ci (i=1,2,m)。设si是类Ci中的样本个数，则，对一个给定数据对象进行分类所需要的期望信息可由下式给出：,其中，pi是任意样本属于类Ci的概率，按照si /S进行计算。Log函数是以2为底的函数。,（6.1）,H(x)=,69,（6.2）,ID3-属性选择方法,H(x/y)=,70,（6.4）,（6.3）,ID3-属性选择方法,I=H(X)-H(X/Y),71,ID3-属性选择方法,Gain(S, A)是属性A在集合S上的信息增益 Gain(S, A)= Entropy(S) Entropy(S, A) Gain(S, A)越大，说明选择测试属性对分类提供的信息越多.,ID3 属性选择方法,ID3算法示例,怎么建立决策树？ 谁是根节点？ 谁是下一层子节点？为什么是它？,第1步计算决策属性的熵,决策属性“买计算机？” 该属性分两类：买/不买 S1(买)=641 S2（不买）= 383 S=S1+S2=1024 P1=641/1024=0.6260 P2=383/1024=0.3740 I(S1,S2)=I(641,383) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9537,ID3算法示例,初始不确定性,第2步计算条件属性的熵,条件属性共有4个： 分别是年龄、收入、学生、信誉。 分别计算不同属性的信息增益。,ID3算法示例,第2-1步 计算年龄的熵,年龄共分三个组： 青年、中年、老年 1）青年： 买与不买比例为128/256 S1(买)=128 S2（不买）= 256 S=S1+S2=384 P1=128/384 P2=256/384 I(S1,S2)=I(128,256) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9183,ID3算法示例,第2-2步 计算年龄的熵,年龄共分三个组： 青年、中年、老年 2）中年： 买与不买比例为256/0 S1(买)=256 S2（不买）= 0 S=S1+S2=256 P1=256/256 P2=0/256 I(S1,S2)=I(256，0) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0,ID3算法示例,第2-3步计算年龄的熵,年龄共分三个组： 青年、中年、老年 3）老年： 买与不买比例为125/127 S1(买)=125 S2（不买）=127 S=S1+S2=252 P1=125/252 P2=127/252 I(S1,S2)=I(125，127) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9157,ID3算法示例,第2-4步 计算年龄的熵,年龄共分三个组： 青年、中年、老年 所占比例： 青年组 384/1025=0.375 中年组 256/1024=0.25 老年组 384/1024=0.375 计算年龄的平均信息期望 E（年龄）=0.375*0.9183+ 0.25*0+ 0.375*0.9157 =0.6877 G（年龄信息增益） =0.9537-0.6877 =0.2660 （1）,ID3算法示例,第3步 计算收入的熵,收入共分三个组： 高、中、低 E（收入）=0.9361 收入信息增益=0.9537-0.9361 =0.0176 （2）,ID3算法示例,第4步 计算学生的熵,学生共分二个组： 学生、非学生 E（学生）=0.7811 年龄信息增益=0.9537-0.7811 =0.1726 （3）,ID3算法示例,第5步 计算信誉的熵,信誉分二个组： 良好，优秀 E（信誉）= 0.9048 信誉信息增益=0.9537-0.9048 =0.0453 （4）,ID3算法示例,第6步计算选择节点,年龄信息增益=0.9537-0.6877 =0.2660 （1） 收入信息增益=0.9537-0.9361 =0.0176 （2） 年龄信息增益=0.9537-0.7811 =0.1726 （3） 信誉信息增益=0.9537-0.9048 =0.0453 （4）,ID3算法示例,年龄,青年,中年,老年,买/ 不买,买,买/ 不买,叶子,ID3算法示例,青年买与不买比例为128/256 S1(买)=128 S2（不买）= 256 S= S1 + S2 =384 P1=128/384 P2=256/384 I(S1, S2)=I(128,256) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9183,ID3算法示例,如果选择收入作为节点 分高、中、低,平均信息期望（加权总和）： E(收入）= 0.3333 * 0 + 0.5 * 0.9183 + 0.1667 * 0 = 0.4592 Gain(收入) = I(128, 256) - E(收入)=0.9183 0.4592 = 0.4591,高：I(0,128)=0 比例: 128/384=0.3333 中：I(64,128)=0.9183 比例: 192/384=0.5 低：I(64,0)=0 比例: 64/384=0.1667,注意,ID3算法示例,年龄,青年,中年,老年,学生,买,信誉,叶子,否,是,优,良,买,不买,买/ 不买,买,叶子,叶子,叶子,ID3算法示例,ID3算法实际应用-在电信行业应用实例（1）,通过ID3算法来实现客户流失的预警分析，找出客户流失的特征，以帮助电信公司有针对性地改善客户关系，避免客户流失. 利用决策树方法进行数据挖掘，一般有如下步骤：数据预处理、决策树挖掘操作，模式评估和应用。,ID3算法实际应用-在电信行业应用实例（1）,电信运营商的客户流失有三方面的含义： 一是指客户从一个电信运营商转网到其他电信运营商，这是流失分析的重点； 二是指客户月平均消费量降低，从高价值客户成为低价值客户。 三指客户自然流失和被动流失。,ID3算法实际应用-在电信行业应用实例（1）,在客户流失分析中有两个核心变量：财务原因非财务原因、 主动流失被动流失。 客户流失可以相应分为四种类型. 其中非财务原因主动流失的客户往往是高价值的客户。他们会正常支付服务费用，并容易对市场活动有所响应。这种客户是电信企业真正需要保住的客户。,（1）数据预处理 数据挖掘的处理对象是大量的数据，这些数据一般存储在数据库系统中（该用户相关数据存储在其CRM中），是长期积累的结果。但往往不适合直接挖掘，需要做数据的预处理工作，一般包括数据的选择(选择相关的数据)、净化(消除冗余数据)、转换、归约等。数据预处理工作准备是否充分，对于挖掘算法的效率乃至正确性都有关键性的影响。,ID3算法实际应用-在电信行业应用实例（1）,（1）数据预处理 该公司经过多年的电脑化管理，已有大量的客户个人基本信息(文中简称为客户信息表)。在客户信息表中，有很多属性，如姓名用户号码、用户标识、用户身份证号码(转化为年龄)、在网时间（竣工时间）、地址、职业、用户类别、客户流失（用户状态）等等，数据准备时必须除掉表中一些不必要的属性，一般可采用面向属性的归纳等方法去掉不相关或弱相关属性。,ID3算法实际应用-在电信行业应用实例（1）,1）属性删除： 将有大量不同取值且无概化操作符的属性或者可用其它属性来代替它的较高层概念的那些属性删除。比如客户信息表中的用户标识、身份证号码等，它们的取值太多且无法在该取值域内找到概化操作符，应将其删除，得到表1。,ID3算法实际应用-在电信行业应用实例（1）,2）属性概化： 用属性概化阈值控制技术沿属性概念分层上卷或下钻进行概化。 文化程度分为3类：W1初中以下(含初中)，W2高中(含中专)，W3大学(专科、本科及以上)； 职业类别：按工作性质来分共分3类：Z1一Z3； 缴费方式：托收：T1,营业厅缴费：T2,充值卡：T3。,ID3算法实际应用-在电信行业应用实例（1）,2）属性概化： 连续型属性概化为区间值。表中年龄、费用变化率和在网时间为连续型数据，由于建立决策树时，用离散型数据进行处理速度最快，因此对连续型数据进行离散化处理. 根据专家经验和实际计算信息增益，在“在网时长”属性中，通过检测每个划分，得到在阈值为5年时信息增益最大，从而确定最好的划分是在5年处，则这个属性的范围就变为5：H1,H2。 而在“年龄”属性中，信息增益有两个锋值，分别在40和50处，因而该属性的范围变为40-50即变为青年，中年，老年：N1,N2,N3； 费用变化率：指（当月话费近3个月的平均话费）/近3个月的平均话费）0，F1:30%，F2：30%-99%, F3:100%变为 F1,F2,F3。,ID3算法实际应用-在电信行业应用实例（1）,ID3算法实际应用-在电信行业应用实例（1）,在图中，NO表示客户不流失，YES表示客户流失。从图可以看出，客户费用变化率为100%的客户肯定已经流失；而费用变化率低于30%的客户；即每月资费相对稳定的客户一般不会流失，费用变化率在30%99%的客户有可能流失，其中年龄在4050岁之间的客户流失的可能性非常大，而年龄低于40岁的客户，用充值卡缴费的客户和在网时间较短的客户容易流失；年龄较大的客户，则工人容易流失。,ID3算法实际应用-在电信行业应用实例（1）,ID3算法小结,ID3算法是一种经典的决策树学习算法，由Quinlan于1979年提出。ID3算法的基本思想是，以信息熵为度量，用于决策树节点的属性选择，每次优先选取信息量最多的属性，亦即能使熵值变为最小的属性，以构造一棵熵值下降（不确定性降低）最快的决策树，到叶子节点处的熵值为0。此时，每个叶子节点对应的实例集中的实例属于同一类。,ID3算法小结,优点： 算法简单； 易于理解 缺点： 偏向分割属性中取值多的一个； 只能处理离散属性； ID3不包括树剪枝，易受噪声和波动影响； 不易对变化的数据集进行学习。,（3）C4.5算法,ID3缺点1：偏向分割属性中取值多的一个 原因：分割属性取值越多，每个值对应的子集规模越小。极限情况下，每个子集内只有一个单元（行），则它的信息增益必然最高（对不确定的消除达到最大）。 例如，用身份证号区别“是否相亲成功”，显然没有任何意义，但是确实符合ID3算法。,解决方法：引入增益比例,101,“相亲”,（3）C4.5算法,多,取值个数非常多的情况？,104,对取值个数非常少的情况如何？,105,G(X,Y),106,C4.5算法,如，只有一个取值的情况,排除取值个数很多的情况,107,108,对取值按照由小到大的顺序排序：,109,110,111,112,113,114,115,116,117,118,119,融合,（4）CART算法,CART：Classification and Regression Tree分类回归树 采用基于最小距离的基尼指数估计函数； 生成二叉树。,121,122,123,124,125,126,127,128,用测试集,2. 决策树剪枝？,130,131,132,133,3. 提取分类规则？,135,由决策树提取分类规则,决策树所表示的分类知识可以被抽取出来，并用IF-THEN的分类规则的形式表示。 从决策树的根节点到任一个叶节点所形成的一条路径构成一条分类规则。 其中，沿着决策树的一条路径所形成的属性-值对形成分类规则的前件（IF部分）的一个合取项；叶节点所标记的类别构成规则的后件（THEN部分）。 IF-THEN分类规则表达方式易于被人理解，尤其是当决策树较大时，优势更加突出。,136,示例,137,示例,138,6.4 贝叶斯分类方法,贝叶斯定理？ 朴素贝叶斯分类？ 贝叶斯信念网络？,1. 贝叶斯定理？,141,贝叶斯分类方法（Bayes）,贝叶斯分类是统计学分类方法，可预测类别所属的概率，如：一个数据对象属于某个类别的概率。 贝叶斯分类的基础是贝叶斯定理。 贝叶斯定理（Bayes theorem）：是概率论中的一个结果，跟随机变量的条件概率以及边缘（条件）概率分布有关。,142,在实际中，人们常会根据不确定性信息作出推理和决策，此时往往需要对各种结论出现的概率进行估计，这类推理称为概率推理。 贝叶斯推理的问题是条件概率推理问题。,贝叶斯分类方法（Bayes）,143,概率论基本知识回顾,概率论是研究随机性或不确定性等现象的数学。更精确的说，是用来模拟实验在同一环境下会产生不同结果的情状。 随机事件； 事件间的关系； 概率定义； 条件概率。,144,（1）随机事件,随机实验：随机实验是一个可观察结果的人工或自然的过程，其产生的结果可能不止一个，且不能事先确定会产生什么结果。 样本空间：样本空间是一个随机实验的全部可能出现的结果的集合，通常记作，中的点（即一个可能出现的实验结果）称为样本点，通常记作。 随机事件：随机事件是一个随机实验的一些可能结果的集合，是样本空间的一个子集。常用大写字母A,B,C,表示。,145,（2）事件间的关系,146,（3）概率定义,定义：设为一个随机实验的样本空间，对上的任意事件A，规定一个实数与之对应，记为P(A)，满足以下三条基本性质，称为事件A发生的概率：,147,（4）条件概率,条件概率：设A、B是两个随机事件，且P(B)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(B A1)P(A1)+P(B A2)P(A2),148,贝叶斯定理,贝叶斯定理是关于随机事件A和B的条件概率和边缘概率的一则定理。 通常，事件A在事件B发生的条件下的概率，与事件B在事件A发生的条件下的概率是不一样的，然而，这两者是有确定的关系的，贝叶斯定理就是这种关系的陈述。,149,贝叶斯定理,由前面三个概率公式可以得到贝叶斯公式：,全概率：P(B)=P(B A1)P(A1)+P(B A2)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. 一天，小王做了一件好事，则小王是好人的概率有多大，小王究竟为好人还是坏人？,示例1,155,旅客搭乘飞机必须经电子仪器检查是否身上携带金属物品。如果携带金属，仪器会发出声音的概率是97%，但身上无金属物品仪器会发出声音的概率是5%。 已知一般乘客身上带有金属物品的概率是30%，若某旅客经过仪器检查时发出声音，请问他身上有金属物品的概率是多少？,2019/11/3,示例2,156,2019/11/3,解：设C1=“有金属物”，X=“仪器会发声”，则,157,贝叶斯分类,设X为一个类别未知的数据样本，设H为某种假设，如：数据样本X属于某特定的类C。 对于分类问题，我们希望确定P(HX)，即给定观测数据样本X，假定H成立的概率。,贝叶斯分类,设x是一个类别未知的数据样本，cj为某个类别，若数据样本x属于一个特定的类别cj，那么分类问题就是决定P(cj|x)，即在获得数据样本x时，确定x的最佳分类。,先验概率P(cj),后验概率P(x|cj),后验概率P(cj|x),贝叶斯分类,先验概率P(cj),P(cj) 为类cj的先验概率(prior probability) ，它反映了我们所拥有的关于cj是正确分类的背景知识。 通常可以用样例中属于cj的样例数|cj|比上总样例数|D|来近似，即:,后验概率P(x|cj)指的是当已知类别为cj的条件下，样本x出现的概率。,后验概率P(x|cj),若设x = ，且属性值相互条件独立，即在属性间，不存在依赖关系，则 P(x|cj)= P(a1,a2am| cj),后验概率P(cj |x),即给定数据样本x时cj成立的概率，而这正是我们所感兴趣的。,P(cj|x )被称为C的后验概率（posterior probability），因为它反映了在得到数据样本x后cj成立的置信度.,贝叶斯分类,计算 Pmax (ci|x) = max P(cj|x) j(1,|C|),则Pmax (ci|x)称为最大后验概率，并将x分到ci类中.,2. 朴素贝叶斯分类？,朴素贝叶斯分类的工作过程,（1）每个数据样本X用一个n维特征向量：X=x1,x2,xn表示，分别描述对n个属性(A1,A2,An)的具体取值； （2）假定共有m个不同类别，C1,C2,Cm。给定一个类别未知的数据样本X，分类法将在已知X情况下，将X赋于后验概率最大的那个类别。即，朴素贝叶斯分类将类别未知的样本X归属到类别Ci，当且仅当：,即，最大化P(CiX)。其中的类别Ci称为最大后验假定。根据贝叶斯定理，有：,朴素贝叶斯分类的工作过程,（3）由于P(X)对于所有的类别均是相同的，因此只需要计算P(X Ci)P(Ci)取最大即可。 如果各类别的先验概率未知，通常假定这些类是等概率的，即：P(C1)=P(C2)=P(Cm)。这样变成只需要对P(X Ci)求最大，否则就要P(X Ci)P(Ci)取最大。 否则，一般可以通过P(Ci)=si/s进行估算，其中si为训练样本集合中类别Ci的个数，s为整个训练样本集合的大小。,朴素贝叶斯分类的工作过程,（4）对于包含多个属性的数据集，直接计算P(X Ci) 的运算量是非常大的。为实现对P(X Ci)的有效估算，朴素贝叶斯分类通常假设各属性是相互独立的，即在属性间，不存在依赖关系，则对于给定的类别Ci ，有：,而P(x1 Ci), P(x2 Ci), P(xn Ci)的值，可以由训练样本集进行估算。具体处理如下：,朴素贝叶斯分类的工作过程,1）如果Ak是符号属性，则P(xkCi)=sik/si，：其中sik为训练样本中类别为Ci且属性Ak取值vk的样本数，si为训练样本中类别为Ci的样本数。,朴素贝叶斯分类的工作过程,朴素贝叶斯分类的工作过程,（5）为预测一个未知样本X的类别，对每个类Ci，计算 P(X Ci)P(Ci)。则，样本X被指派到类Ci，当且仅当： P(XCi)P(Ci) P(XCj)P(Cj),朴素贝叶斯分类的效果,研究表明，与决策树和神经网络分类器相比，贝叶斯分类器在某些情况下具有更好的分类效果。 但必须满足某些假定条件，如要求各属性间是相互独立的。,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”),示例,根据贝叶斯分类公式： 由于P(X)对于所有的类别均是相同的，因此只需要计算P(X Ci)P(Ci)取最大即可。 P(Ci）为先验概率，可用如下公式计算： P(Ci)=si/s。 对于P(X Ci)，在假定各属性是相互独立的前提下，可按照如下公式计算：,P(Ci)的计算,P(Ci)为类别的先验概率，i=1,2，具体计算如下：,P(X Ci) 的计算,X=(age=“=30”, income=“medium”, student=“yes”, credit-rating=“fair”),结 论,计算P(X Ci)P(Ci)，并取最大值：,基于,朴素贝叶斯的独立假设,基本贝叶斯分类器是基于各属性相互独立这一假设来进行分类计算的：即，若给定一个数据样本类别，其样本属性的取值应是相互独立的。 若假设成立，则与其他分类方法相比，朴素贝叶斯分类器应是