数据挖掘课件--分类方法

第四章分类方法内容提要分类的基本概念与步骤基于距离的分类算法决策树分类方法贝叶斯分类规则归纳与分类有关的问题分类是数据挖掘中重要的任务分类的目的是学会一个分类器（分类函数或模型），该分类器能把待分类的数据映射到给定的类别中。分类可用于预测。从利用历史数据纪录中自动推导出对给定数据的推广描述，从而能对未来数据进行类预测。分类具有广泛的应用，例如医疗诊断、信用卡系统的信用分级、图像模式识别等。分类器的构造依据的方法很广泛：统计方法：包括贝叶斯法和非参数法等。机器学习方法：包括决策树法和规则归纳法。神经网络方法。其他，如粗糙集等（在前面绪论中也介绍了相关的情况）。分类方法的类型从使用的主要技术上看，可以把分类方法归结为四种类型：基于距离的分类方法决策树分类方法贝叶斯分类方法规则归纳方法。本章将择选一些有代表性的方法和算法来介绍这四类分类方法。分类问题的描述定义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}。解决分类问题的关键是构造一个合适的分类器：从数据库到一组类别集的映射。一般地，这些类是被预先定义的、非交叠的。数据分类的两个步骤1．建立一个模型，描述预定的数据类集或概念集数据元组也称作样本、实例或对象。为建立模型而被分析的数据元组形成训练数据集。训练数据集中的单个元组称作训练样本，由于提供了每个训练样本的类标号，因此也称作有指导的学习。通过分析训练数据集来构造分类模型，可用分类规则、决策树或数学公式等形式提供。2．使用模型进行分类首先评估模型（分类法）的预测准确率。如果认为模型的准确率可以接受，就可以用它对类标号未知的数据元组或对象进行分类。第三章分类方法内容提要分类的基本概念与步骤基于距离的分类算法决策树分类方法贝叶斯分类规则归纳与分类有关的问题基于距离的分类算法的思路定义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)被称为相似性。在实际的计算中往往用距离来表征，距离越近，相似性越大，距离越远，相似性越小。距离的计算方法有多种，最常用的是通过计算每个类的中心来完成。基于距离的分类算法的一般性描述算法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.基于距离的分类方法的直观解释（a）类定义（b）待分类样例（c）分类结果K-近邻分类算法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.KNN的例子姓名性别身高(米)类别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中等“高度”用于计算距离，K=5，对Pat，女，1.6分类。•对T前K=5个记录，N={Kristina，女，1.6、Jim，男，2、Maggie，女，1.9、Martha，女，1.88和Stephanie，女，1.7}。•对第6个记录d=Bob，男，1.85，得到N={Kristina，女，1.6、Bob，男，1.85、Maggie，女，1.9、Martha，女，1.88和Stephanie，女，1.7}。•对第7个记录d=Kathy，女，1.6，得到N={Kristina，女，1.6、Bob，男，1.85、Kathy，女，1.6、Martha，女，1.88和Stephanie，女，1.7}。•对第8个记录d=Dave，男，1.7，得到N={Kristina，女，1.6、Dave，男，1.7、Kathy，女，1.6、Martha，女，1.88和Stephanie，女，1.7}。•对第9和10个记录，没变化。•对第11个记录d=Debbie，女，1.8，得到N={Kristina，女，1.6、Dave，男，1.7、Kathy，女，1.6、Debbie，女，1.8和Stephanie，女，1.7}。•对第12到14个记录，没变化。•对第15个记录d=Wynette，女，1.75，得到N={Kristina，女，1.6、Dave，男，1.7、Kathy，女，1.6、Wynette，女，1.75和Stephanie，女，1.7}。最后的输出元组是Kristina，女，1.6、Kathy，女，1.6、Stephanie，女，1.7、Dave，男，1.7和Wynette，女，1.75。在这五项中，四个属于矮个、一个属于中等。最终KNN方法认为Pat为矮个。Wynette，女，1.75。第四章分类方法内容提要分类的基本概念与步骤基于距离的分类算法决策树分类方法贝叶斯分类规则归纳与分类有关的问题决策树表示与例子决策树（DecisionTree）的每个内部结点表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶结点代表类或类分布。树的最顶层结点是根结点。buys_computer的决策树示意决策树分类的特点决策树分类方法采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分枝，在决策树的叶结点得到结论。所以从决策树的根到叶结点的一条路径就对应着一条合取规则，整棵决策树就对应着一组析取表达式规则。基于决策树的分类算法的一个最大的优点就是它在学习过程中不需要使用者了解很多背景知识（这同时也是它的最大的缺点），只要训练例子能够用属性-结论式表示出来，就能使用该算法来学习。决策树分类模型的建立通常分为两个步骤：决策树生成决策树修剪。决策树生成算法描述构造好的决策树的关键在于如何选择好的属性进行树的拓展。研究结果表明，一般情况下,树越小则树的预测能力越强。由于构造最小的树是NP-难问题，因此只能采取用启发式策略来进行。属性选择依赖于各种对例子子集的不纯度（Impurity）度量方法，包括信息增益（InformatinGain）、信息增益比（GainRatio）、Gini-index、距离度量（DistanceMeasure）、J-measure、G统计、χ2统计、证据权重（WeightofEvidence）、最小描述长度（MLP）、正交法（OrtogonalityMeasure）、相关度（Relevance）和Relief等。算法4-3Generate_decision_tree(samples,attribute_list)/*决策树生成算法*/输入：训练样本samples，由离散值属性表示；候选属性的集合attribute_list。输出：一棵决策树。（1）创建结点N；（2）IFsamples都在同一个类CTHEN返回N作为叶结点，以类C标记；（3）IFattribute_list为空THEN返回N作为叶结点，标记为samples中最普通的类；//多数表决（4）选择attribute_list中具有最高信息增益的属性test_attribute；（5）标记结点N为test_attribute；（6）FOReachtest_attribute中的已知值ai由结点N长出一个条件为test_attribute=ai的分枝；（7）设si是samples中test_attribute=ai的样本的集合；//一个划分（8）IFsi为空THEN加上一个树叶，标记为samples中最普通的类；（9）ELSE加上一个由Generate_decision_tree(si，attribute_list-test_attribute)返回的结点；决策树修剪算法基本的决策树构造算法没有考虑噪声，因此生成的决策树完全与训练例子拟合。在有噪声情况下，将导致过分拟合（Overfitting），即对训练数据的完全拟合反而使对现实数据的分类预测性能下降。现实世界的数据一般不可能是完美的，可能缺值（MissingValues）；数据不完整；含有噪声甚至是错误的。剪枝是一种克服噪声的基本技术，同时它也能使树得到简化而变得更容易理解。有两种基本的剪枝策略：预先剪枝（Pre-Pruning）：在生成树的同时决定是继续对不纯的训练子集进行划分还是停机。后剪枝（Post-Pruning）：是一种拟合+化简（fitting-and-simplifying）的两阶段方法。首先生成与训练数据完全拟合的一棵决策树，然后从树的叶子开始剪枝，逐步向根的方向剪。剪枝时要用到一个测试数据集合（TuningSet或AdjustingSet），如果存在某个叶子剪去后能使得在测试集上的准确度或其他测度不降低（不变得更坏），则剪去该叶子；否则停机。理论上讲，后剪枝好于预先剪枝，但计算复杂度大。剪枝过程中一般要涉及一些统计参数或阈值（如停机阈值）。要防止过分剪枝（Over-Pruning）带来的副作用。ID3算法ID3是Quinlan提出的一个著名决策树生成方法：决策树中每一个非叶结点对应着一个非类别属性，树枝代表这个属性的值。一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性值。每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联。采用信息增益来选择能够最好地将样本分类的属性。为了聚焦重点，将对ID3算法采用如下方式讲解：伪代码详细描述见课本；给出信息增益对应的计算公式；通过一个例子来说明它的主要过程。信息增益的计算设S是s个数据样本的集合，定义m个不同类Ci（i=1，2，…，m），设si是Ci类中的样本数。对给定的样本S所期望的信息值由下式给出：其中pi是任意样本属于Ci的概率：si/s。设属性A具有个不同值{a1,a2,…,av}，可以用属性A将样本S划分为{S1,S2,…,Sv}，设sij是Sj中Ci类的样本数，则由A划分成子集的熵由下式给出：有A进行分枝将获得的信息增益可以由下面的公式得到：miiimppsssI1221)(log),...,()s,...,s(