数据挖掘原理与算法04

2020年3月17日星期二1第三章分类方法内容提要分类的基本概念与步骤基于距离的分类算法决策树分类方法贝叶斯分类规则归纳与分类有关的问题2020年3月17日星期二2分类是数据挖掘中重要的任务分类的目的是学会一个分类器（分类函数或模型），该分类器能把待分类的数据映射到给定的类别中。分类可用于预测。从利用历史数据纪录中自动推导出对给定数据的推广描述，从而能对未来数据进行类预测。分类具有广泛的应用，例如医疗诊断、信用卡系统的信用分级、图像模式识别等。分类器的构造依据的方法很广泛：统计方法：包括贝叶斯法和非参数法等。机器学习方法：包括决策树法和规则归纳法。神经网络方法。其他，如粗糙集等（在前面绪论中也介绍了相关的情况）。2020年3月17日星期二3分类方法的类型从使用的主要技术上看，可以把分类方法归结为四种类型：基于距离的分类方法决策树分类方法贝叶斯分类方法规则归纳方法。本章将择选一些有代表性的方法和算法来介绍这四类分类方法。2020年3月17日星期二4分类问题的描述定义4-1给定一个数据库D={t1，t2，…，tn}和一组类C={C1，…，Cm}，分类问题是去确定一个映射f:DC，使得每个元组ti被分配到一个类中。一个类Cj包含映射到该类中的所有元组，即Cj={ti|f(ti)=Cj，1≤i≤n，而且tiD}。例如，把学生的百分制分数分成A、B、C、D、F五类，就是一个分类问题：D是包含百分制分数在内的学生信息，C={A、B、C、D、F}。解决分类问题的关键是构造一个合适的分类器：从数据库到一组类别集的映射。一般地，这些类是被预先定义的、非交叠的。2020年3月17日星期二5数据分类的两个步骤1．建立一个模型，描述预定的数据类集或概念集数据元组也称作样本、实例或对象。为建立模型而被分析的数据元组形成训练数据集。训练数据集中的单个元组称作训练样本，由于提供了每个训练样本的类标号，因此也称作有指导的学习。通过分析训练数据集来构造分类模型，可用分类规则、决策树或数学公式等形式提供。2．使用模型进行分类首先评估模型（分类法）的预测准确率。如果认为模型的准确率可以接受，就可以用它对类标号未知的数据元组或对象进行分类。2020年3月17日星期二6第三章分类方法内容提要分类的基本概念与步骤基于距离的分类算法决策树分类方法贝叶斯分类规则归纳与分类有关的问题2020年3月17日星期二7基于距离的分类算法的思路定义4-2给定一个数据库D={t1，t2，…，tn}和一组类C={C1，…，Cm}。假定每个元组包括一些数值型的属性值：ti={ti1，ti2，…，tik}，每个类也包含数值性属性值：Cj={Cj1，Cj2，…，Cjk}，则分类问题是要分配每个ti到满足如下条件的类Cj：sim(ti，Cj)=sim(ti，Cl)，Cl∈C，Cl≠Cj，其中sim(ti，Cj)被称为相似性。在实际的计算中往往用距离来表征，距离越近，相似性越大，距离越远，相似性越小。距离的计算方法有多种，最常用的是通过计算每个类的中心来完成。2020年3月17日星期二8基于距离的分类算法的一般性描述算法4-1通过对每个元组和各个类的中心来比较，从而可以找出他的最近的类中心，得到确定的类别标记。算法4-1基于距离的分类算法输入：每个类的中心C1，…，Cm；待分类的元组t。输出：输出类别c。（1）dist=∞；//距离初始化（2）FORi:=1tomDO（3）IFdis(ci，t)distTHENBEGIN（4）c←i；（5）dist←dist(ci，t)；（6）END.2020年3月17日星期二9基于距离的分类方法的直观解释（a）类定义（b）待分类样例（c）分类结果2020年3月17日星期二10K-近邻分类算法K-近邻分类算法（KNearestNeighbors，简称KNN）通过计算每个训练数据到待分类元组的距离，取和待分类元组距离最近的K个训练数据，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.2020年3月17日星期二11K-means算法：根据聚类中的均值进行聚类划分：输入：聚类个数k以及包含n个数据对象的数据库。输出：满足方差最小标准的k个聚类。2020年3月17日星期二12处理流程：（1）从n个数据对象任意选择k个对象作为初始聚类中心。（2）循环流程（3）到（4），直到每个聚类不再发生变化为止。（3）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离，并根据最小距离重新对相应对象进行划分。（4）重新计算每个有变化聚类的均值（中心对象）。2020年3月17日星期二13k-均值算法标准均方误差：kiCpiimpE12)(2020年3月17日星期二14聚类的分析过程2020年3月17日星期二15坐标表示5个点｛X1,X2,X3,X4,X5｝作为一个聚类分析的二维样本：X1＝（0,2），X2＝（0,0），X3＝（1.5,0），X4＝（5,0），X5＝（5,2）。假设要求的簇的数量k=2。对这5个点进行分类。2020年3月17日星期二16k-均值算法的性能分析：优点：K-均值算法是解决聚类问题的一种典型算法，这种算法简单、快速；对处理大型数据集，该算法是相对可伸缩的和高效的；算法尝试找出使平方误差函数值最小的k个划分。当结果簇是密集的，而簇与簇之间区别明显时，效果是较好的。2020年3月17日星期二17k-均值算法的性能分析：（续）缺点：K-均值算法只有在簇的平均值在被定义的情况下才能使用。要求用户事先必须拿出k，而且对初值不敏感，对于不同的初始值，可能会导致不同的聚类结果；不适合于发现非凸面形状的簇，或者大小差别很大的簇；对于“噪声”与孤立点数据是敏感的，少量的该类数据能够对平均值产生极大影响。2020年3月17日星期二18K-mediods算法：根据聚类中的中心对象进行划分：输入：聚类个数k以及包含n个数据对象的数据库。输出：满足基于各聚类中心对象的方差最小标准的k个聚类。PAM(PartitioningAroundMedoids围绕中心点划分)2020年3月17日星期二19处理流程：（1）从n个数据对象任意选择k个对象作为初始聚类中心代表。（2）循环流程（3）到（5），直到每个聚类不再发生变化为止。（3）依据每个聚类的中心代表对象以及各对象与这些中心对象间距离，并根据最小距离重新对相应对象进行划分。（4）任意选择一个非中心对象，计算其与中心对象交换的整个成本S。（5）若S为负值则交换非中心对象与中心对象以构成新聚类的k个中心对象。2020年3月17日星期二20为了判定一个非代表对象Oh是否是当前一个代表对象Oi的好的替代。对于每一个非中心点对象Oj，下面的四种情况被考虑：假设Oi被Oh代替作为新的中心点，Oj当前隶属于中心点对象Oi。如果Oj离某个中心点Om最近，im，那么Oj被重新分配给Om；假设Oi被Oh代替作为新的中心点，Oj当前隶属于中心点对象Oi。如果Oj离这个新的中心点Oh最近，那么Oj被分配给Oh；假设Oi被Oh代替作为新的中心点，但是Oj当前隶属于另一个中心点对象Om，im。如果Oj依然离Om最近，那么对象的隶属不发生变化；假设Oi被Oh代替作为新的中心点，但是Oj当前隶属于另一个中心点对象Om，im。如果Oj离这个新的中心点Oh最近，那么Oi被重新分配给Oh。2020年3月17日星期二21总代价定义：其中Cjih表示Oj在Oi被Oh代替后产生的代价。njjihihCTC12020年3月17日星期二22代价的计算公式：OI与Om是两个原中心点，Oh将代替Oi作为新的中心点。代价函数的计算方式如下：第一种情况：Oj当前隶属于Oi，但Oh替换Oi后Oj被重新分配给Om，则代价函数为：Cjih=d(j,m)-d(j,i)第二种情况：Oj当前隶属于Oi，但Oh替换Oi后Oj被重新分配给Oh，则代价函数为：Cjih=d(j,h)-d(j,i)第三种情况：Oj当前隶属于另一个中心点对象Om，im，但Oh替换Oi后Oj的隶属不发生变化，则代价函数为：Cjih=0第四种情况：Oj当前隶属于另一个中心点对象Om，im，但Oh替换Oi后Oj被重新分配给Oh，则代价函数为：Cjih=d(j,h)-d(j,m)2020年3月17日星期二23+OiPOj++Orandom+OiOj+P+Orandom用图1表示如下：2020年3月17日星期二24+OiPOj++Orandom+OiOj++POrandom2020年3月17日星期二25例：加入空间中有五个点{A,B,C,D,E}如图所示，各点之间的距离关系如下表，根据所给的数据进行分类。ABCDEABCDEA01223B10243C22015D24103E335302020年3月17日星期二26解：第一步：建立阶段：加入从5个对象中随机抽取的2个中心点为{A,B}，则样本被划分为{A,C,D}与{B,E};第二步交换阶段：假定中心点A,B分别被非中心点{C,D,E}替换，计算代价TCAC,TCAD,TCAE,TCBC,TCBD,TCBE;2020年3月17日星期二27计算TCAC如下：当A被C替换后，看A是否发生变化：A不再是一个中心点，C称为新的中心点，属于第一种情况。因为A离B比A离C近，A被分配到B中心点代表的簇：CAAC=d(A,B)-d(A,A)=1当A被C替换后，看B是否发生变化：属于第三种情况。当A被C替换以后，B不受影响：CBAC=02020年3月17日星期二28计算TCAC如下(续)当A被C替换后，看C是否发生变化：C原先属于A中心点所在的簇，当A被C替换以后，C是新中心点符合图1中的第二种情况：CCAC=d(C,C)-d(C,A)=-2当A被C替换后，看D是否发生变化：D原先属于A中心点所在的簇，当A被C替换以后，离D最近的中心点是C，符合图1的第二种情况：CDAC=d(D,C)-d(D,A)=-12020年3月17日星期二29计算TCAC如下(续)当A被C替换后，看E是否发生变化：E原先属于B中心点所在的簇，离E最近的中心点是B，符合图1的第三种情况：CEAC=0因此TCAC=-22020年3月17日星期二30算法的性能分析：K-中心点算法消除了k-平均算法对于孤立点的敏感性；当存在“噪声”与孤立点数据时，k-中心点方法比k-平均方法更健壮，这是因为中心点不像平均值那么容易被极端数据影响，但是，k-中心点方法的执行代价比k-平均方法高；算法必须指定聚类的数目k，k的取值对聚类质量有重大影响；K-中心点算法对于小的数据非常有效，但对于大数据集效率不高。2020年3月17日星期二31KNN的例子姓名性别身高(米)类别Kristina女1.6矮Jim男2高Maggie女1.9中等Martha女1.88中等Stephanie女1.7矮Bob男1.85中等Kathy女1.6矮Dave男1.7矮Worth男2.2高Steven男2.1高Debbie女1.8中等Todd男1.95中等Kim女1.9中等Amy女1.8中等Wynette女1.75中等2020年3月17日星期二32KNN的例子“高度”用于计算距离，K=5，对Pat，女，1.6分类。•对T前K=5个记录，N={Kristina，女，1.6、Jim，男，2、Maggie，女，1.9、