数据挖掘_分类方法

1、 第四章 分类方法卢梦雅；潘小刚；吕琪；潘蒙第1节 分类的基本概念分类的基本概念分类的目的分类的目的：学会一个分类函数或分类模型，也称之为分类器，该模型能把数据库中的数据项映射到给定类别中的某一个类别。分类的作用分类的作用：可用于预测，预测的目的是从历史数据记录中自动推导出给定数据的推广描述，从而能对未来的数据进行类预测。分类的输出时离散的类别值。分类的应用：分类的应用：医疗诊断、信用卡系统的信用分级、图像模式识别等。分类的基本概念 分类也成为有监督学习，与之相对应的是无监督学习，比如聚类。分类和聚类的最大区别在于，分类数据中的一部分的类别是已知的，而聚类数据的类别是位置的。 建立分类模型需要

2、学习一部分已知数据，如果训练的时间过长，或者预测模型参数太多而样本较少，则导致过度训练。 分类器的构造方法很广泛分类器的构造方法很广泛：统计方法统计方法：包括贝叶斯法、非参数法等；机器学习方法：机器学习方法：包括决策树法、规则归纳法；决策树法对应的是决策树或者判别树，规则归纳法则有决策表和产生式规则等；神经网络方法神经网络方法：主要是BP算法；分类的基本概念从主要技术上看，分类方法主要有： （1）基于距离的分类方法； （2）决策树分类方法； （3）贝叶斯分类方法； （4）规则归纳法；第2节 分类的步骤分类的基本概念条件条件类别类别条件条件类别类别90成绩A60成绩70D80成绩90B成绩60F

3、70成绩40MedFairClaire40MedFairAndre Beau3140HighExcellent分类算法分类算法分类规则分类规则If age=3140 andIncome =highThenCredit_rating=excellent训练训练分类的基本概念使用测试数据测试数据NameNameAgeAgeIncomeIncomeCredit_ratingCredit_ratingFrank Jones40HighFairSlyvia30LowFairAnne3140 HighExcellent分类规则分类规则新数据新数据（John Henri，3140，high）Credit r

4、ating？Excellent第3节 基于距离的分类算法基于距离的分类算法 在实际的计算中，往往距离越近，相似性越大，距在实际的计算中，往往距离越近，相似性越大，距离越远，相似性越小；离越远，相似性越小；距离的计算方法有很多，最为常用的是通过计算每距离的计算方法有很多，最为常用的是通过计算每个类的中心类进行；个类的中心类进行；基于距离的分类算法基于距离的分类算法基于距离的分类算法：输入：每个类的中心 ；待分类的元祖t。输出：输出类别c。Dist=；/距离的初始化；For i=1 to m DOIf dis(c,t)dist then beginc=IDist-dist(ci,t);End;上述

5、算法，通过每个元祖和每个类的中心来比较，从而可以找出它的最近的类的中心，从而得到确定的类别标记。1mC，.,C基于距离的分类算法基于距离的分类：基于距离的分类算法 在现实生活中，经常采用一种基于距离的分类算法：k-最临近方法（KNN）：通过计算每个训练数据到待分类元祖的距离，取和待分类元祖距离，取和待分类元祖距离最近的k个训练数据，k个数据中哪个类别的训练数据占多数，则待分类元祖就属于哪个类别； kNN对一个数据元素进行分类时，是通过它和训练集的每一个元组进行相似度计算和比较完成的。因此，如果对n个未知元素进行分类的话，复杂度为O（nq），鉴于训练数据集容量是常熟，复杂度看组是O（n）基于距离

6、的分类算法姓名姓名性别性别身高（身高（m）类别类别Kristina女1.6矮Jim男2高Maggie女1.9中等Martha女1.86中等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；基于距离的分类算法姓名姓名性别性别身高（身高（m）类别类别Kristina女1.6矮Bob男1.85中等Maggie女1.9中等Martha女1.86中等Stephanie女1,7矮Jim男2

7、.0高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；第6个记录替代第2个基于距离的分类算法姓名姓名性别性别身高（身高（m）类别类别Kristina女1.6矮Bob男1.85中等Kathy女1.6矮Martha女1.86中等Stephanie女1,7矮Jim男2.0高Maggie女1.9中等Dave男1.7矮Worth男2.2高Steven男2.1高Debbie女1.8中等Todd男1.95中等Kim女1.9中等Amy女1

8、.8中等Wynette女1.75中等例：采用最邻近方法对元组K=5；第7个记录替代第3个基于距离的分类算法姓名姓名性别性别身高（身高（m）类别类别Kristina女1.6矮Dave男1.7矮Kathy女1.6矮Martha女1.86中等Stephanie女1,7矮Jim男2.0高Maggie女1.9中等Bob男1.85中等Worth男2.2高Steven男2.1高Debbie女1.8中等Todd男1.95中等Kim女1.9中等Amy女1.8中等Wynette女1.75中等例：采用最邻近方法对元组K=5；第8个记录替代第2个基于距离的分类算法姓名姓名性别性别身高（身高（m）类别类别Kristin

9、a女1.6矮Dave男1.7矮Kathy女1.6矮Debbie女1.8中等Stephanie女1,7矮Jim男2.0高Maggie女1.9中等Bob男1.85中等Worth男2.2高Steven男2.1高Martha女1.86中等Todd男1.95中等Kim女1.9中等Amy女1.8中等Wynette女1.75中等例：采用最邻近方法对元组K=5；第11个记录替代第4个基于距离的分类算法姓名姓名性别性别身高（身高（m）类别类别Kristina女1.6矮Dave男1.7矮Kathy女1.6矮Wynette女1.75中等Stephanie女1,7矮Jim男2.0高Maggie女1.9中等Bob男1.

10、85中等Worth男2.2高Steven男2.1高Martha女1.86中等Todd男1.95中等Kim女1.9中等Amy女1.8中等Debbie女1.8中等例：采用最邻近方法对元组K=5；第15个记录替代第4个.在这五项中，四个属于矮个，一个属于中等，最终k-最邻近算法认为Pat为矮个。第4节 决策树分类方法数据库数据库分类标记分类标记性别性别年龄年龄婚姻婚姻否否是是否否是是FemaleFemaleMaleMale35353535未婚未婚已婚已婚2022-5-81、决策树分类方法决策树是一个类似于流程图的树结构，其中每个内部结点表示在一个属性上的测试，每个分支代表一个测试输出，而每个树叶结点

11、代表类或类分布。2、一般分类的步骤模型建立(Model Building)模型评估(Model Evaluation)使用模型(Use Model)2022-5-83.决策树分类的步骤数据库2022-5-8训练样本(training samples)建立模型测试样本(testing samples)评估模型例：资料训练样训练样本本婚姻年龄 家庭 所得否是否是未婚已婚3535低高否小康1.建立模型测试样本2.模型评估错误率为66.67%修改模型3.使用模型2022-5-84、分类算法的评估（1）预测的准确度：指模型正确地预测新的或先前未见过的数据的类标号的能力。（2）模型强健性 :指给定噪声数据

12、或具有缺失值的数据，模型正确预测的能力。（3） 计算复杂性:指产生和使用模型的计算花费,建模的速度、预测的速度。（4）描述的简洁性 （5）处理规模性2022-5-82022-5-8决策树归纳的基本算法是贪心算法，它以自顶向下递归各个击破的方式构造决策树。贪心算法：在每一步选择中都采取在当前状态下最好/优的选择。在其生成过程中，分割方法即属性选择度量是关键。通过属性选择度量，选择出最好的将样本分类的属性。根据分割方法的不同，决策树可以分为两类：基于信息论的方法（较有代表性的是ID3、C4.5算法等）和最小GINI指标方法（常用的有CART、SLIQ及SPRINT算法等）。二、决策树(Decisi

13、on Tree)（一）决策树的结构根部节点(root node)中间节点(non-leaf node)(代表测试的条件)分支(branches)(代表测试的结果)叶节点(leaf node)(代表分类后所获得的分类标记)2022-5-8(二)决策树的基本算法Generate_decision_tree/根据给定数据集产生一个决策树输入：输入：训练样本，各属性均取离散数值，可供归纳的候选属性集为:attribute_list。输出：输出：决策树。处理流程程：处理流程程：（1）创建一个结点；（2）若该结点中的所有样本均为同一类别C，则（3）返回N作为一 个叶结点并标志为类别C；（4）若attrib

14、ute_list为空，则（5）返回N作为一个叶结点并标记为该结点所含样本中类别个数最多的类别；（6）从attribute_list选择一个信息增益最大的属性test_attribute；（7）并将结点N标记为test_attribute；（8）对于test_attribute中的每一个已知取值ai准备划分结点N所包含的样本集；（9）根据test_attribute=ai条件，从结点N产生相应的一个分支，以表示该测试条件；（10）设si为test_attribute=ai条件所获得的样本集合；（11）若si为空，则将相应叶结点标记为该结点所含样本中类别个数最多的类别；（12）否则将相应叶结点标志

15、为Generate_decision_tree(si,attribute_list-test_attribute)返回值；例：n根部节点n中间节点n停止分支2022-5-8（三）ID3算法2022-5-8Quinlan(1979)提出，以Shannon(1949)的信息论为依据。ID3算法的基本思路：1.从树的根节点处的所有训练样本开始，选取一个属性来划分这些样本。对属性的每一个值产生一分枝。分枝属性值的相应样本子集被移到新生成的子节点上。2.这个算法递归地应用于每个子节点，直到一个节点上的所有样本都分区到某个类中。3.到达决策树的叶节点的每条路径表示一个分类规则。ID3算法的属性选择度量就是

16、使用信息增益，选择最高信息增益的属性作为当前节点的测试属性。信息论：若一事件有k种结果，对应的概率为Pi。则此事件发生后所得到的信息量I(视为Entropy)为：I=-(p1*log2(p1)+ p2*log2(p2)+ pk*log2(pk)Example 1：设 k=4p1=0.25,p2=0.25,p3=0.25,p4=0.25 I=-(.25*log2(.25)*4)=2Example 2：设k=4p1=0,p2=0.5,p3=0,p4=0.5I=-(.5*log2(.5)*2)=1Example 3：设 k=4p1=1,p2=0,p3=0,p4=0 I=-(1*log2(1)=020

17、22-5-82022-5-8信息增益Example(Gain) n=16 n1=4I(16,4)=(4/16)*log2(4/16)+(12/16)*log2(12/16)=0.8113E(年龄)=(6/16)*I(6,1)+(10/16)*I(10,3)=0.7946Gain(年龄)=I(16,4)-E(年龄)=0.0167nGain(年龄)=0.0167nMax:作为第一个分类依据2022-5-8nGain(性别)=0.0972nGain(家庭所得)=0.0177ExamplenGain(家庭所得)=0.688I(7,3)=-(3/7)*log2(3/7)+(4/7)*log2(4/7)=

18、0.9852nGain(年龄)=0.9852nGain(年龄)=0.2222I(9,1)=-(1/9)*log2(1/9)+(8/9)*log2(8/9)=0.5032nGain(家庭所得)=0.50322022-5-8Example(end)ID3算法分类规则：IF性别=Female AND家庭所得= 低所得THEN购买RV房车=否IF性别=Female AND家庭所得= 小康THEN购买RV房车=否IF性别=Female AND家庭所得= 高所得THEN购买RV房车=是IF性别=Male AND年龄35 THEN购买RV房车=否IF性别=Male AND年龄35 THEN购买RV房车=是n

19、资料nDecision Tree2022-5-8（四）决策树的建立过程1、决策树的停止决策树是通过递归分割(recursive partitioning)建立而成，递归分割是一种把数据分割成不同小的部分的迭代过程。 如果有以下情况发生，决策树将停止分割：该群数据的每一笔数据都已经归类到同一类别。该群数据已经没有办法再找到新的属性来进行节点分割。该群数据已经没有任何尚未处理的数据。2022-5-82、决策树的剪枝(pruning)在现实世界中，获得的数据并不可能保证其完美性与完整性，所以，在当被用来创建决策树的训练数据集中存在有噪声，或者数量太少以至于不能产生目标函数的有代表性的采样的时候，我们

20、使用决策树算法生成的决策树很多分支反映的是训练数据集中的异常。在上面任意一种情况发生的时候，利用简单算法产生的树会出现过度拟合训练样例的现象。 决策树学习可能遭遇模型过度拟合（over fitting）的问题，过度拟合是指模型过度训练，导致模型记住的不是训练集的一般性，反而是训练集的局部特性。如何处理过度拟合呢？对决策树进行修剪。树的修剪有几种解决的方法，主要为先剪枝和后剪枝方法。2022-5-8（1）先剪枝方法在先剪枝方法中，通过提前停止树的构造（例如，通过决定在给定的节点上不再分裂或划分训练样本的子集）而对树“剪枝”。一旦停止，节点成为树叶。确定阀值法：在构造树时，可将信息增益用于评估岔的

21、优良性。如果在一个节点划分样本将导致低于预定义阀值的分裂，则给定子集的进一步划分将停止。测试组修剪法：在使用训练组样本产生新的分岔时，就立刻使用测试组样本去测试这个分岔规则是否能够再现，如果不能，就被视作过度拟合而被修剪掉，如果能够再现，则该分岔予以保留而继续向下分岔。2022-5-8（2）后剪枝方法后剪枝方法是由“完全生长”的树剪去分枝。通过删除节点的分枝，剪掉叶节点。案例数修剪是在产生完全生长的树后，根据最小案例数阀值，将案例数小于阀值的树节点剪掉。成本复杂性修剪法是当决策树成长完成后，演算法计算所有叶节点的总和错误率，然后计算去除某一叶节点后的总和错误率，当去除该叶节点的错误率降低或者不

22、变时，则剪掉该节点。反之，保留。2022-5-8应用案例：在农业中的应用2022-5-8第一步：属性离散化2022-5-8第二步：概化（泛化）2022-5-8第三步：计算各属性的期望信息2022-5-8=(17/30)*LOG(17/30),2)+(10/30)*LOG(10/30),2)+(3/30)*LOG(3/30),2)计算各属性的信息增益2022-5-8第四步：决策树2022-5-8ID3算法性能分析 ID系列的搜索策略为：（1）优先选择较短的树而不是较长的；（2）选择那些信息增益高的属性离根节点较近的树。 结论：ID系列算法的归纳偏置是因为它在选的时候较短的树比较长的树优先所产生的

23、，也就是那些信息增益高的属性更靠近的根节点将会有优先生成树的特权。（五 ）C4.5算法532022-5-8类别属性的信息熵C4.5算法 主要引入的新方法和新增功能： （1）分裂 （2）连续数据 （3）缺失数据 （4）规则 （1）C4.5的分裂属性选择度量 为了避免ID3算法的归纳偏置，弥补ID系列算法的不足就要舍弃信息增益这个度量而选择别的决策属性作为度量标准。Quinlan在他1986年中的论文中提出了一种可以使用的度量标准：增益比率。 增益比率通过加入一个被称为分裂信息（split information）的项来惩罚类似Date这样的属性，分裂信息用来衡量属性分裂数据的广度和均匀性，它由如

24、下公式所示：)(log)(21DeDeDSplitIrvjrA 增益比率的公式如下所示：)()()(ASplitIAGainAGainRatio（2）C4.5对连续数据的处理 ID3算法最初的定义是假设属性值是离散值，但在实际环境中，有很多属性是连续的，不能够用一个确定的标准来对其进行划分。C4.5使用下面的一系列处理过程来对连续的属性划分成离散的属性，进而达到能够建立决策树的目的C4.5对连续数据的处理 Step1 根据训练数据集D中各个属性的值对该训练数据集进行排序； Step2 利用其中各属性的值对该训练数据集动态地进行划分； Step3 在划分后的得到的不同的结果集中确定一个阈值，该阈

25、值将训练数据集数据划分为两个部分； Step4 针对这两边各部分的值分别计算它们的增益或增益比率，以保证选择的划分使得增益最大。（3）C4.5对缺失数据的处理 为了评估属性A是否是决策节点n的最佳测试属性，要计算决策树在该节点的信息增益Gain(D,A)。假定是S中的一个训练样例，并且其属性A的通过值分得的信息值表示为 ei .（4）C4.5对生成规则的利用 只要生成了决策树后，就可以把树转换成一个IF-THEN规则的集合。当然，每种算法生成的决策树都可以转换成相应的if-then规则，C4.5算法处理规则与其他算法不同在于它把规则存储在一个二维数组中，每一行都代表着树中的一个规则，即从树根到

26、叶子之间的一个路径 .C4.5算法的优缺点 优点：产生的分类规则易于理解，准确率较高。 缺点：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。扩展： 现已有的C5.0算法则是C4.5算法的修订版 ，适用在处理大数据集，采用Boosting（提升）方式提高模型准确率，又称为Boosting Trees，在软件上的计算速度比较快，占用的内存资源较少。（六）（六） 应用实例分析应用实例分析 下面我们利用书上表4-4根据天气是否打网球的训练数据集，利用ID3算法来判断某天是否适合打网球。

27、 （1）类别属性信息熵的计算由于未分区前，训练数据集中共有14个实例，其中有9个实例属于p类（适合打网球的），5个实例属于n类（不适合打网球），因此分区前类别属性的熵为：bitnpI940. 0145log145149log149),(22应用实例分析 （2）非类别属性信息熵的计算若选择Outlook为测试属性。 0.694bit)52log5253log53(155)40log4044log44(144)53log5352log52(145)(222222OutlookE应用实例分析l 因此，这种划分的信息增益是：l Gain(Outlook)=I(p,n) - E(Outlook) = 0

28、.940 - 0.694 =0.246 bit 同理，可以求出 其它三个属性的信息增益为 ： Gain(Temperatures)=0.029bit，Gain(Humidity)=0.151bit，Gain(Wind)=0.048bit。 由上可知，属性值Outlook在各个属性中具有最高的增益，被选作分裂属性。则第一个根节点T被用标记，并对于每个属性值生长一个分支。（3）递归地创建决策树的树枝和叶子l 选择作为测试属性后，将训练实例集分为三个子集，生成三个子节点，对每个子节点递归采用上述过程进行分类直至每个节点都成为叶节点而已。 应用实例分析应用实例分析l 属性值Outlook在各个属性中具有最高的增益，被选作分裂属性。则第一个根节点T被用标记，并对于每个属性值生长一个分支：根据信息增益结果生成的以Outlook为根节点的初级决策树图 应用实例分析应用实例分析l A分析图中的sunny分支，计算其子属性的信息增益值来决