第七章分类与预测.

《数据挖掘》主讲：王名扬信息与计算机工程学院2引言—要挖掘知识的类型概念描述：特征化和比较；关联规则；分类/预测；聚类分析；其他的数据挖掘任务。引言根据现有的知识，我们得到了一些关于爬行动物和鸟类的信息，我们能否对新发现的物种，比如动物A，动物B进行分类？动物种类体型翅膀数量脚的只数是否产蛋是否有毛类别狗中04否是爬行动物猪大04否是爬行动物牛大04否是爬行动物麻雀小22是是鸟类天鹅中22是是鸟类大雁中22是是鸟类动物A大02是无？动物B中22否是？2019年12月19日星期四4分类是数据挖掘中重要的任务分类的目的是学会一个分类器（分类函数或模型），该分类器能把待分类的数据映射到给定的类别中。分类可用于预测。从历史数据纪录中自动推导出对给定数据的推广描述，从而能对未来数据进行类预测。iiniiiyxxxxf),......,,,(3212019年12月19日星期四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分类过程示意图训练集分类算法输入输出1.创建分类模型2.模型评估和预测类别未知的数据集测试集模型评估预测预测结果分类模型有指导的学习VS.无指导的学习有指导的学习（用于分类）–训练样本的类标号已知；–新数据使用训练数据集中得到的规则进行分类无指导的学习（用于聚类）–训练样本的类标号未知；–通过一系列的度量、观察，试图确立数据中的类或聚类的存在17数据预测预测：构造和使用模型评估无标号样本类，或评估给定样本可能具有的属性值或值区间与分类区别：二者是两类主要的预测问题。•分类是预测离散或标号值；•预测是预测连续或有序值；观点：用预测法预测类标号为分类；用预测法预测连续值（一般用回归法）为预测。18示例背景：假定已建立AllElectronics公司的邮寄清单数据库。邮寄清单用于分发介绍新产品和降价信息材料。数据库描述顾客的属性，包括姓名、年龄、收入、职业和信誉度，并按照顾客是否在该公司购买计算机进行分类。19示例分类模型：假定新的顾客添加到数据库中，由于向每位顾客分发促销材料费用很高，因此，可以根据数据库中已有顾客信息构建分类模型，用以预测需向哪些顾客分发材料。预测模型：假定想预测在一个财政年度，一个顾客将在AllElectronics进行的主要的购买的数量，则可以构建一个预测模型。2.分类和预测的基本问题？21问题(1)：数据准备1）准备分类和预测的数据：数据的预处理数据清理：噪声（平滑技术）；空缺值（统计手段）相关性分析（特征选择）：删除不相关和冗余属性，如银行贷款申请时填写的星期数，可能与贷款是否申请成功无关；数据变换：数据离散化（数据概化）：如属性“收入”的数值就可以被离散化为若干区间，如低、中等和高；数据规范化：将给定属性的值按比例缩放至较小的区间，如[0,1]。22问题(2)：评估分类模型2）评估方法：对用于分类或预测的方法或模型进行评估预测的准确率：模型正确预测未知对象类别或数值的能力；速度：1）建立模型的时间；2）使用模型的时间强壮性（鲁棒性）：处理噪声和空缺值的能力；可伸缩（扩展）性：处理大型数据及构造模型的能力；可理解性：模型的可理解能力；规则的优越性：1）判定树的大小；2）分类规则的简洁性。6.2基于距离的分类算法基本思想？几种常见的距离分类算法？1.基于距离分类的基本思想？2019年12月19日星期四25基于距离的分类算法的思路定义：给定一个数据库D={t1，t2，…，tn}和一组类C={C1，…，Cm}。假定每个元组包括一些数值型的属性值：ti={ti1，ti2，…，tik}，每个类也包含数值性属性值：Cj={Cj1，Cj2，…，Cjk}，则分类问题是要分配每个ti到满足如下条件的类Cj：sim(ti，Cj)=sim(ti，Ci)，Ci∈C，Ci≠Cj，其中sim(ti，Cj)被称为相似性。2019年12月19日星期四26基于距离的分类算法的思路在实际的计算中往往用距离来表征：距离越近，相似性越大；距离越远，相似性越小。如何度量距离？欧几里得距离；曼哈坦距离；明考斯基距离；加权的明考斯基距离。（一）欧几里得距离欧式距离由对应元素间差值平方和的平方根所表示，即：)()()(),(),,,(),,,,(2222112121bnanbababnbbbanaaaxxxxxxbadxxxxxxxxnba维向量，两个和设有如何度量距离？（二）曼哈顿距离对应元素间差值绝对值的和表示，即：bnanbabaxxxxxxbad2211),(欧几里得距离与曼哈顿距离的共同点：(1)即距离是一个非负的数值(2)自身的距离为0(3)即距离函数具有对称性(4)即距离函数满足三角不等式0),(bad0),(,0),(bbdaad),(),(abdbad),(),(),(kbdkadbad如何度量距离？(三)明可夫斯基距离是欧几里得距离和曼哈顿距离的概化ppbnanpbapbaxxxxxxbad/12211),(其中p是一个正整数：当p=1时，表示曼哈顿距离；当p=2时，表示欧几里得距离。(四)加权的明可夫斯基距离如果对每一个变量根据其重要性赋予一个权重，就得到加权的明考斯基距离。ppbnannpbapbaxxwxxwxxwbad/1222111),(如何度量距离？2019年12月19日星期四30基于距离的分类算法的思路在实际的计算中往往用距离来表征：距离越近，相似性越大；距离越远，相似性越小。距离的计算方法有多种，最常用的是通过计算样本到每个类中心的距离来完成。2019年12月19日星期四31基于距离的分类算法的一般性描述算法计算每个元组到各个类中心的距离，从而可以找出离它的最近的类中心，得到确定的类别标记。算法基于距离的分类算法输入：每个类的中心C1，…，Cm；待分类的元组t。输出：输出类别c。（1）dist=∞；//距离初始化（2）FORi:=1tomDO（3）IFdis(ci，t)distTHENBEGIN（4）c←i；（5）dist←dist(ci，t)；（6）END.2019年12月19日星期四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年12月19日星期四37（1）K-近邻分类算法K-近邻分类算法（KNearestNeighbors，简称KNN）通过计算每个训练数据到待分类元组的距离，取和待分类元组距离最近的K个训练数据，K个数据中哪个类别的训练数据占多数，则待分类元组就属于哪个类别。2019年12月19日星期四38（1）K-近邻分类算法算法4-2K-近邻分类算法输入：训练数据T；近邻数目K；待分类的元组t。输出：输出类别c。（1）N=；（2）FOReachd∈TDOBEGIN（3）IF|N|≤KTHEN（4）N=N∪{d}；（5）ELSE（6）IFu∈Nsuchthatsim(t，u)〈sim(t，d)THENBEGIN（7）N=N-{u}；（8）N=N∪{d}；（9）END（10）END（11）c=classtowhichthemostu∈N.KNN的直观解释1、定义的直观形式：找出与目标最接近的K个样本；将目标划分到找出的K个样本中出现最频繁的类。2、K的直观形式：以目标样本为中心；划出一个刚好包含K个样本的圆；当K增大时，圆半径增大。XXX(a)1-近邻(b)2-近邻(c)3-近邻XKNN的直观解释3、直观的例子手写识别记录手写体特征；计算手写体与标准汉字的相似度；根据相似度（距离），找出K个备选集；选择一个正确汉字人种识别欧洲人的鼻子、亚洲人的眼睛非洲人的肤色、亚洲人的头发Unknownrecord形象的例子KNN的分类思想如果它走路像鸭子,叫声也像鸭子,那么它可能就是只鸭子TrainingRecordsTestRecordComputeDistanceChoosekofthe“nearest”recordsKNN的特点1、非参数统计方法不需引入参数回归分析是参数统计方法2、k的选择K=1时，将待分类样本划入与其最接近的样本的类；K=|X|时，仅根据训练样本进行频率统计，将待分类样本划入最多的类；K需要合理选择，太小容易受干扰、太大增加计算复杂性3、算法的复杂度维数灾难：当维数增加时，算法的复杂度会急剧增加一般采用降维处理6.3决策树分类算法决策树的基本概念？决策树生成算法？剪枝方法？提取分类规则？1.决策树的基本概念？决策树基本概念解决分类问题的一般方法TIDA1A2A3类1Y100LN2N125SN3Y400LY4N415MN学习算法学习模型模型应用模型TIDA1A2A3类1Y100L？2N125S？3Y400L？4N415M？训练集（类标号已知）检验集（类标号未知）归纳推论46基本概念决策树（decisiontree）：决策树是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策树对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。年龄？学生？信誉？买青中老否是优良不买买买不买47决策树的基本组成决策树的基本组成决策树是类似流程图的倒立的树型结构。最顶层节点为根节点，是整个决策树的开始；树的每个内部节点表示在一个属性上的测试，其每个分支代表一个测试输出；树的每个叶节点代表一个类别。年龄？学生？信誉？买青中老否是优良不买买买不买48基本概念决策树的生成包括两个过程：（1）