知识发现与机器学习

《知识发现与机器学习》由会员分享，可在线阅读，更多相关《知识发现与机器学习（86页珍藏版）》请在金锄头文库上搜索。

1、2019年4月20日星期六,DMKD Sides By MAO,1,第三章 分类方法 内容提要,分类的基本概念与步骤 基于距离的分类算法 决策树分类方法 贝叶斯分类 规则归纳 与分类有关的问题,2019年4月20日星期六,DMKD Sides By MAO,2,分类是数据挖掘中重要的任务,分类的目的是学会一个分类器（分类函数或模型），该分类器能把待分类的数据映射到给定的类别中。 分类可用于预测。从利用历史数据纪录中自动推导出对给定数据的推广描述，从而能对未来数据进行类预测。 分类具有广泛的应用，例如医疗诊断、信用卡系统的信用分级、图像模式识别等。 分类器的构造依据的方法很广泛： 统计方法：包括

2、贝叶斯法和非参数法等。 机器学习方法：包括决策树法和规则归纳法。 神经网络方法。 其他，如粗糙集等（在前面绪论中也介绍了相关的情况）。,2019年4月20日星期六,DMKD Sides By MAO,3,分类方法的类型,从使用的主要技术上看，可以把分类方法归结为四种类型： 基于距离的分类方法 决策树分类方法 贝叶斯分类方法 规则归纳方法。 本章将择选一些有代表性的方法和算法来介绍这四类分类方法。,2019年4月20日星期六,DMKD Sides By MAO,4,分类问题的描述,定义4-1 给定一个数据库 D=t1，t2，tn和一组类 C=C1，Cm，分类问题是去确定一个映射 f: DC，使得

3、每个元组ti被分配到一个类中。一个类Cj 包含映射到该类中的所有元组，即Cj = ti | f(ti) = Cj，1 i n， 而且ti D。 例如，把学生的百分制分数分成A、B、C、D、F五类，就是一个分类问题： D是包含百分制分数在内的学生信息， C=A、B、C、D、F。 解决分类问题的关键是构造一个合适的分类器：从数据库到一组类别集的映射。一般地，这些类是被预先定义的、非交叠的。,2019年4月20日星期六,DMKD Sides By MAO,5,数据分类的两个步骤,1建立一个模型，描述预定的数据类集或概念集 数据元组也称作样本、实例或对象。 为建立模型而被分析的数据元组形成训练数据集。

4、 训练数据集中的单个元组称作训练样本，由于提供了每个训练样本的类标号，因此也称作有指导的学习。 通过分析训练数据集来构造分类模型，可用分类规则、决策树或数学公式等形式提供。 2使用模型进行分类 首先评估模型（分类法）的预测准确率。 如果认为模型的准确率可以接受，就可以用它对类标号未知的数据元组或对象进行分类。,2019年4月20日星期六,DMKD Sides By MAO,6,第三章 分类方法 内容提要,分类的基本概念与步骤 基于距离的分类算法 决策树分类方法 贝叶斯分类 规则归纳 与分类有关的问题,2019年4月20日星期六,DMKD Sides By MAO,7,基于距离的分类算法的思路,

5、定义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) ，ClC，ClCj， 其中sim(ti，Cj)被称为相似性。 在实际的计算中往往用距离来表征，距离越近，相似性越大，距离越远，相似性越小。 距离的计算方法有多种，最常用的是通过计算每个类的中心来完成。,2019年4月20日星期六,DMKD Sides By MAO,8,基于距离的分类算法的一般性描述,算法 4

6、-1通过对每个元组和各个类的中心来比较，从而可以找出他的最近的类中心，得到确定的类别标记。,算法 4-1 基于距离的分类算法 输入：每个类的中心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年4月20日星期六,DMKD Sides By MAO,9,基于距离的分类方法的直观解释,（a）类定义,（b）待分类样例,（c）分类结果,2019年4月20日星期六,DMKD Sides

7、 By MAO,10,K-近邻分类算法,K-近邻分类算法（K Nearest Neighbors，简称KNN）通过计算每个训练数据到待分类元组的距离，取和待分类元组距离最近的K个训练数据，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）

8、N=N-u； （8） N=Nd； （9） END （10）END （11）c=class to which the most uN.,2019年4月20日星期六,DMKD Sides By MAO,11,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

9、中等 Kim 女 1.9 中等 Amy 女 1.8 中等 Wynette 女 1.75 中等,“高度”用于计算距离，K=5，对分类。 对T前K=5个记录，N=、和。 对第6个记录d=，得到N=、和。 对第7个记录d=，得到N=、和。 对第8个记录d=，得到N=、和。 对第9和10个记录，没变化。 对第11个记录d=，得到N=、和。 对第12到14个记录，没变化。 对第15个记录d=，得到N=、和。 最后的输出元组是、和。在这五项中，四个属于矮个、一个属于中等。最终KNN方法认为Pat为矮个。 。,2019年4月20日星期六,DMKD Sides By MAO,12,第三章 分类方法 内容提要,

10、分类的基本概念与步骤 基于距离的分类算法 决策树分类方法 贝叶斯分类 规则归纳 与分类有关的问题,2019年4月20日星期六,DMKD Sides By MAO,13,决策树表示与例子,决策树（Decision Tree）的每个内部结点表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶结点代表类或类分布。树的最顶层结点是根结点。 buys_computer的决策树示意,2019年4月20日星期六,DMKD Sides By MAO,14,决策树分类的特点,决策树分类方法采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分枝，在决策树的叶结点

11、得到结论。所以从决策树的根到叶结点的一条路径就对应着一条合取规则，整棵决策树就对应着一组析取表达式规则。 基于决策树的分类算法的一个最大的优点就是它在学习过程中不需要使用者了解很多背景知识（这同时也是它的最大的缺点），只要训练例子能够用属性-结论式表示出来，就能使用该算法来学习。 决策树分类模型的建立通常分为两个步骤： 决策树生成 决策树修剪。,2019年4月20日星期六,DMKD Sides By MAO,15,决策树生成算法描述,构造好的决策树的关键在于如何选择好的属性进行树的拓展。研究结果表明，一般情况下或具有较大概率地说，树越小则树的预测能力越强。由于构造最小的树是NP-难问题，因此只

12、能采取用启发式策略来进行。 属性选择依赖于各种对例子子集的不纯度（Impurity）度量方法，包括信息增益（Informatin Gain）、信息增益比（Gain Ratio）、Gini-index、距离度量（Distance Measure）、J-measure、G统计、2统计、证据权重（Weight of Evidence）、最小描述长度（MLP）、正交法（Ortogonality Measure）、相关度（Relevance）和 Relief等。,算法 4-3 Generate_decision_tree(samples, attribute_list) /*决策树生成算法*/ 输入：训

13、练样本samples，由离散值属性表示；候选属性的集合attribute_list。 输出：一棵决策树。 （1） 创建结点N； （2） IF samples 都在同一个类C THEN 返回N 作为叶结点，以类 C标记； （3） IF attribute_list为空 THEN 返回N作为叶结点，标记为samples中最普通的类；/多数表决 （4） 选择attribute_list中具有最高信息增益的属性test_attribute； （5） 标记结点N为test_attribute； （6） FOR each test_attribute中的已知值ai 由结点N长出一个条件为test_attr

14、ibute=ai的分枝； （7）设si是samples 中test_attribute =ai的样本的集合；/一个划分 （8）IF si 为空 THEN 加上一个树叶，标记为samples中最普通的类； （9）ELSE 加上一个由Generate_decision_tree(si， attribute_list-test_attribute)返回的结点；,2019年4月20日星期六,DMKD Sides By MAO,16,决策树修剪算法,基本的决策树构造算法没有考虑噪声，因此生成的决策树完全与训练例子拟合。在有噪声情况下，将导致过分拟合（Overfitting），即对训练数据的完全拟合反而使

15、对现实数据的分类预测性能下降。 现实世界的数据一般不可能是完美的，可能缺值（Missing Values）；数据不完整；含有噪声甚至是错误的。 剪枝是一种克服噪声的基本技术，同时它也能使树得到简化而变得更容易理解。有两种基本的剪枝策略： 预先剪枝（Pre-Pruning）：在生成树的同时决定是继续对不纯的训练子集进行划分还是停机。 后剪枝（Post-Pruning）：是一种拟合+化简（fitting-and-simplifying）的两阶段方法。首先生成与训练数据完全拟合的一棵决策树，然后从树的叶子开始剪枝，逐步向根的方向剪。剪枝时要用到一个测试数据集合（Tuning Set或Adjustin

16、g Set），如果存在某个叶子剪去后能使得在测试集上的准确度或其他测度不降低（不变得更坏），则剪去该叶子；否则停机。理论上讲，后剪枝好于预先剪枝，但计算复杂度大。 剪枝过程中一般要涉及一些统计参数或阈值（如停机阈值）。要防止过分剪枝（Over-Pruning）带来的副作用。,2019年4月20日星期六,DMKD Sides By MAO,17,ID3算法,ID3是Quinlan提出的一个著名决策树生成方法： 决策树中每一个非叶结点对应着一个非类别属性，树枝代表这个属性的值。一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性值。 每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联。 采用信息增益来选择能够