分享
分销 收藏 举报 申诉 / 194

类型ch7-2-数据挖掘算法--分类方法.ppt

  • 上传人:仙人****88
  • 文档编号:14767333
  • 上传时间:2026-11-17
  • 格式:PPT
  • 页数:194
  • 大小:2.50MB
  • 下载积分:10 金币
  • 配套讲稿:

    如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。

    特殊限制:

    部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。

    关 键  词:
    ch7 数据 挖掘 算法 分类 方法
    资源描述:
    单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第七章 数据挖掘算法,分类,分 类,分类的概念,基于距离的分类方法,Bayesian Classification,Classification by Back Propagation,Support Vector Machines,Associative Classification:Classification by association rule analysis,Lazy Learners(or Learning from your Neighbors),Other Classification Methods,Prediction,Accuracy,Summary,分类的基本概念,分类是指将数据映射到预先定义好的群组或类。,在分析测试数据之前,类别就已经被确定了,所以分类统称被称作有指导的学习。,分类算法要求基于数据属性来定义类别。分类算法通常通过观察已知所属类别的数据的特征来描述类别。,分类的基本概念,分类具有广泛的应用,例如医疗诊断、信用卡系统的信用分级、图像模式识别等。,为了识别乘客是否是潜在的恐怖分子或罪犯,机场安全摄像站需要对乘客的脸部进行扫描并辨识脸部的基本模式(例如双眼间距、嘴的大小及形状、头的形状),然后将得到的模式与数据库中的已知恐怖分子或罪犯的模式进行逐个比较,看看是否与其中的某一模式相匹配。,分类步骤,1,建立一个模型,描述预定的数据类集或概念集,数据元组也称作样本、实例或对象。,为建立模型而被分析的数据元组形成训练数据集。,训练数据集中的单个元组称作训练样本,假定每个元组属于一个预定义的类,由一个称作类标号(,classlabel,)的属性确定。由于提供了每个训练样本的类标号,因此也称作有指导的学习。,通过分析训练数据集来构造分类模型,可用分类规则、决策树或数学公式等形式提供。,分类步骤,2.,使用模型进行分类,首先评估模型(分类法)的预测准确率。,将已知的类标号与该样本的学习模型类预测比较,准确率等于测试集的样本中被模型正确分类的百分比,测试集应该与训练集的内容相互独立,否则会出现过分适应的情况,如果认为模型的准确率可以接受,就可以用它对类标号未知的数据元组或对象进行分类。,(1),模型的构建,Training,Data,Classification,Algorithms,IF rank=professor,OR years 6,THEN tenured=yes,Classifier,(Model),NAME,RANK,YEARS,TENURED,Mike,Assistant Prof,3,no,Mary,Assistant Prof,7,yes,Bill,Professor,2,yes,Jim,Associate Prof,7,yes,Dave,Assistant Prof,6,no,Anne,Associate Prof,3,no,(2),利用模型分类,Classifier,Testing,Data,Unseen Data,(Jeff,Professor,4),Tenured?,有指导,vs.,无指导的学习,有指导的学习,(,分类,),指导,:,训练数据是已经被标注好类标号的数据,用来进行有指导的分类。,新数据是基于训练集进行分类的。,无指导的学习,(,聚类,),训练数据的类标号不可知,是观察式学习,基于距离的方法,基于决策树的方法,基于神经网络的方法,基于规则的方法,常用分类方法,预测的准确率,这涉及模型正确地预测新的或先前未见过的数据的类标号的能力,速度,构造模型的速度,利用模型进行分类的速度,强壮性,给定噪声数据或具有空缺值的数据,模型正确预测的能力,可伸缩性,当给定大量数据时,有效地构造模型的能力,可解释性,涉及学习模型提供的理解和洞察的层次,评价分类方法,分 类,分类的概念,基于距离的分类方法,Bayesian Classification,Classification by Back Propagation,Support Vector Machines,Associative Classification:Classification by association rule analysis,Lazy Learners(or Learning from your Neighbors),Other Classification Methods,Prediction,Accuracy,Summary,基于距离的分类算法,与一个类中的成员和另一个类中的成员之间的相似性相比,被映射到同一个类中的成员彼此之间被认为是更加相似的。,相似性(距离)度量可以用来识别数据库中不同成员之间的“相似程度”。,定义,给定一个数据库,D,=,t,1,,,t,2,,,,,t,n,和一组类,C,=,C,1,,,,,C,m,。,假定每个元组包括一些数值型的属性值:,t,i,=,t,i1,,,t,i2,,,,,t,ik,,,每个类也包含数值性属性值:,C,j,=,C,j1,,,C,j2,,,,,C,jk,,,则分类问题是要分配每个,t,i,到满足如下条件的类,C,j,:,sim,(,t,i,,,C,j,)=,sim,(,t,i,,,C,l,),,,C,l,C,,,C,l,C,j,,,其中,sim,(,t,i,,,C,j,),被称为相似性。,在实际的计算中往往用距离来表征,距离越近,相似性越大,距离越远,相似性越小。,距离的计算方法有多种,最常用的是通过计算每个类的中心来完成。,基于距离的分类算法,基于距离的分类算法的一般性描述,算法通过对每个元组和各个类的中心来比较,从而可以找出他的最近的类中心,得到确定的类别标记。,算法,基于距离的分类算法,输入:每个类的中心,C,1,,,,,C,m,;,待分类的元组,t,。,输出:输出类别,c,。,(,1,),dist=,;,/,距离初始化,(,2,),FOR i:=1 to m DO,(,3,),IF,dis,(,c,i,,,t,)dist THEN BEGIN,(,4,),c,i,;,(,5,),distdist(,c,i,,,t,),;,(,6,),END.,基于距离的分类方法的直观解释,(,a,),类定义,(,b,),待分类样例,(,c,),分类结果,K,最近邻居算法(,KNN,),Nearest,neighbor(KNN,),通过计算每个训练数据到待分类元组的距离,取和待分类元组距离最近的,K,个训练数据,,K,个数据中哪个类别的训练数据占多数,则待分类元组就属于哪个类别。,训练样本用,n,维数值属性描述。每个样本代表,n,维空间的一个点。所有的训练样本都放在,n,维模式空间中。给定一个样本,,k-,最临近分类法搜索模式空间,找出最接近未知样本的,k,个训练样本。,K,最近邻居算法(,KNN,),要求的信息,训练集,距离计算值,要获取的最邻近的邻居的数目,k,一个未知的记录进行分类,计算与其它训练记录之间的距离,识别出,k,个最近的邻居,使用最近邻居的类标号来标识未知元组的类(,by taking majority vote,),K,最近邻居算法(,KNN,),计算两个点之间的距离,如:,Euclidean distance,从最近邻居列表中决定分类的结果,选出,k,个最近的邻居中的多数票的类标号,可以根据距离为每一个投票增加权重,Weight factor,w=1/d2,算法,K-,近邻分类算法,输入:训练数据,T,;,近邻数目,K,;,待分类的元组,t,。,输出:输出类别,c,。,(,1,),N,=,;,(,2,),FOR each,d,T,DO BEGIN,(,3,),IF|,N,|,K,THEN,(,4,),N,=,N,d,;,(,5,),ELSE,(,6,),IF,u,N,such that,sim,(,t,,,u,),sim,(,t,,,d,)THEN BEGIN,(,7,),N,=,N,-,u,;,(,8,),N,=,N,d,;,(,9,),END,(,10,),END,(,11,),c=class to which the most uN,.,K,最近邻居算法(,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,,,对,分类。,对,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,为矮个。,K,最近邻居算法(,KNN,),K,值的选取,如果,k,过于小,那么将会对数据中存在的噪声过于敏感,如果,k,过大,邻居中可能包含其他类的点,一个经验的取值法则为,k,,,q,为训练元组的数目。商业算法通常以,10,作为默认值。,分 类,分类的概念,基于距离的分类方法,基于决策树的分类方法,Classification by Back Propagation,Support Vector Machines,Associative Classification:Classification by association rule analysis,Lazy Learners(or Learning from your Neighbors),Other Classification Methods,Prediction,Accuracy,Summary,基于决策树的分类方法,决策树(,decision tree,),决策树是以实例为基础的归纳学习算法。它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则。,类似于流程图的树结构,其中每个内部节点表示在一个属性上的测试,每个分支代表一个测试输出,而每个树叶节点代表类或类分布。树的最顶层节点是根节点。,例如,在贷款申请中,要对申请的风险大小做出判断。,收入,40000,高负债,工作时间,5,年,是,否,是,否,“年收入大于¥,40000”,并且“高负债”的用户被认为是“高风险”;,“年收入小于¥,40000”,但“工作时间大于,5,年”的申请,是“低风险”;,N,Y,Y,N,N,Y,buys_computer,的决策树示意,Age?,Credit_rating?,student?,yes,no,yes,yes,no,40,3040,yes,no,fair,excellent,决策树(,decision tree,),1986,年,Quinlan,提出了著名的,ID3,算法。,在,ID3,算法的基础上,,1993,年,Quinlan,又提出了,C4.5,算法。,为了适应处理大规模数据集的需要,后来又提出了若干改进的算法,其中,SLIQ(super-,vised,learning in quest),和,SPRINT(scalable,parallelizableinduction,of decision trees),是比较有代表性的两个算法。,基于决策树的分类方法,决策树分类的特点,决策树分类方法采用自顶向下的递归方式,在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分枝,在决策树的叶结点得到结论。,所以从决策树的根到叶结点的一条路径就对应着一条合取规则,整棵决策树就对应着一组析取表达式规则。,基于决策树的分类算法的一个最大的优点就是它在学习过程中不需要使用者了解很多背景知识(这同时也是它的最大的缺点),只要训练例子能够用属性,-,结论式表示出来,就能使用该算法来学习。,使用决策树进行分类分为两步:,第,1,步:利用训练集建立并精化一棵决策树,建立决策树 模型。这个过程实际上是一个从数据中获取知识,进行机器学习的过程。,第,2,步:利用生成完毕的决策树对输入数据进行分类。对输入的记录,从根结点依次测试记录的属性值,直到到达某个叶结点,从而找到该记录所在的类。,决策树分类的步骤,问题的关键是建立一棵决策树,即决策树分类模型的建立。这个过程通常分为两个阶段:,建树(,Tree Building,):,决策树建树算法见下,可以看得出,这是一个递归的过程,最终将得到一棵树。,剪枝(,Tree Pruning,):,剪枝目的是降低由于训练集存在噪声而产生的起伏。,决策树分类的步骤,决策树归纳算法,基本算法,(,贪心算法,),树以代表训练样本的单个结点开始(根)(所有的数据都在根结点),如果样本都在同一类。则该结点成为树叶,并用该类标记;,决策树归纳算法,基本算法,(,贪心算法,),否则,选择能够最好的将样本分类的属性,该属性成为该结点的,“,测试,”,或,“,判定,”,属性;,对于测试属性的每个已知的值,创建一个分枝,并据此划分样本;,算法使用同样的过程,,递,归的形成每个划分上的样本决策树;,决策树归纳算法,可以清楚地看到,决策树是一种自顶向下增长树的贪婪算法,在每个节点选取能最好分类样本的属性,继续这个过程直到这棵树能完美地分类训练集,或所有的属性均已被用过。,算法的重点是属性的选取。,决策树归纳算法,算法递归执行的终止条件(停止分支的条件),对于给定的节点,所有的例子都属于同一个类,虽然对于某一个节点当前的例子不属于同一个类,但是已经没有属性可用来选择继续进行分支处理。此时采用,majority voting,投票的方式决定分类结果,没有用于分支的例子(样本满足属性的取值),以,Samples,中的多数创建 一个树叶,作为分类的结果,决策树生成算法描述,DTree(examples,attributes),If,所有样本属于同一分类,返回标号为该分类的叶结点,Else if,属性值为空,返回标号为最普遍分类的叶结点,Else,选取一个属性,,A,,作为根结点,For A,的每一个可能的值,vi,令,examplesi,为具有,A=vi,的样本子集,从根结点出发增加分支(,A=vi),如果,examplesi,为空,则创建标号为最普遍分类的叶结点,否则递归创建子树,调用,DTree(examplesi,attributes,-A),ID3,算法,ID3,是,Quinlan,提出的一个著名决策树生成方法:,决策树中每一个非叶结点对应着一个非类别属性,树枝代表这个属性的值。一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性值。,每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联。,采用信息增益来选择能够最好地将样本分类的属性。,决策树深入,分裂属性选择,决策树的简化,分裂属性选择,选择属性的方法,选择具有最大信息增益的属性作为当前节点的测试属性,该属性使得对结果划分中的样本分类所需的信息量最小,并反映划分的最小随机性。,用信息增益这种信息论的理论方法,使得对一个对象分类所需要的期望测试数目达到最小,并确保找到一棵简单的树。,分裂属性选择,怎样计算信息增益(,information gain,),通过描述属性可以减少类标属性的不确定性。,如:由番茄、茄子、黄瓜三种蔬菜,现在对蔬菜分类。在不给任何描述时,该蔬菜可能是番茄、茄子、黄瓜三种之一,不确定性大。给出该蔬菜是,“,长形,”,形状描述时,该蔬菜可能是茄子、黄瓜两种之一,不确定性减少。在给出该蔬菜是,“,紫的,”,颜色描述时,只可能是茄子了,不确定性为零。,怎样计算信息增益(,information gain,),虽然通过描述属性可以减少类标属性的不确定性,但是不同描述属性减少类标属性不确性的程度不同,即不同描述属性对减少类标属性不确定性的贡献不同。,这种不确定性可以用信息论中的熵来描述。,分裂属性选择,分裂属性选择,怎样计算信息增益(,information gain,),如:假设有番茄、茄子、黄瓜三种蔬菜,对某蔬菜分类,形状描述与颜色描述的贡献是不同的。在给出蔬菜的颜色描述时,如果颜色是红的,则该蔬菜是番茄;如果颜色是紫的,则该蔬菜是茄子;如果颜色是绿的,则该蔬菜是黄瓜,不确定性减少为,0,。而在给出该蔬菜形状时,如果形状是圆的,则该蔬菜是番茄;如果形状是长的,则该蔬菜可能是茄子,也可能是黄瓜,不确定性还是存在。,怎样计算信息增益(,information gain,),信息增益被定义为原始分割的熵与划分以后各分割的熵累加得到的总熵之间的差。,信息增益是指划分前后进行正确预测所需的信息量之差。,选择具有最高信息增益的属性作为当前节点的测试属性。,分裂属性选择,设,S,是有,s,个训练样本数据的集合,类标号属性具有,m,个不同值,定义,m,个不同类,C,i,(,i=1,2,m,),,s,i,是类,C,i,中的样本数,则对一个给定的训练样本分类所需要的,期望信息为,:,其中,p,i,是任意样本属于,C,i,的概率,可用,s,i,/s,来估计,信息增益的计算,其中,为第,j,个子集的权,等于子集(,A,值为,a,j,),中的样本数除以,S,中的样本数。,设属性,A,具有,v,个不同值,a,1,a,2,a,v,,,则可用属性,A,将,S,划分为,v,个子集,S,1,S,2,S,v,,,S,j,中包含的样本在属性,A,上具有值,a,j,。,如果选择,A,作为测试属性,则这些子集对应于由包含集合,S,的结点生长出来的分枝。设,s,ij,是,子集,S,j,中类,C,i,的样本数,则,按照,A,划分成子集的熵为,:,信息增益的计算,由,A,划分的信息增益为:,Gain(A)=I(s1,s2,sm,)-E(A),对于给定的子集,S,j,,,它的信息,I(s,1j,s,2j,s,mj,),可用下式计算,是,S,j,中的样本属于类,C,i,的概率,信息增益的计算,ID3,信息量大小的度量,决策树算法,Gain,(,S,,,A,)是属性,A,在集合,S,上的信息增益,Gain,(,S,,,A,),=Entropy,(,S,),-Entropy,(,S,,,A,),Gain,(,S,,,A,)越大,说明选择测试属性对分类提供的信息越多,计数,年龄,收入,学生,信誉,归类:买计算机,?,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,决策树算法,计数,年龄,收入,学生,信誉,归类:买计算机,?,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,第,1,步计算决策属性的熵,决策属性“买计算机?”。该属性分,两类:买,/,不买,S1(,买,)=641,S2,(不买),=383,S=S1+S2=1024,P1=641/1024=0.6260,P2=383/1024=0.3740,I(S1,S2)=I(641,383),=-P1Log,2,P1-P2Log,2,P2,=-(P1Log,2,P1+P2Log,2,P2),=0.9537,决策树算法,计数,年龄,收入,学生,信誉,归类:买计算机,?,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,第,2,步计算条件属性的熵,条件属性共有,4,个。分别是年龄、,收入、学生、信誉。,分别计算不同属性的信息增益。,决策树算法,计数,年龄,收入,学生,信誉,归类:买计算机,?,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,第,2-1,步计算年龄的熵,年龄共分三个组:,青年、中年、老年,青年买与不买比例为,128/256,S1(,买,)=128,S2,(不买),=256,S=S1+S2=384,P1=128/384,P2=256/384,I(S1,S2)=I(128,256),=-P1Log,2,P1-P2Log,2,P2,=-(P1Log,2,P1+P2Log,2,P2),=0.9183,决策树算法,计数,年龄,收入,学生,信誉,归类:买计算机,?,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,第,2-2,步计算年龄的熵,年龄共分三个组:,青年、中年、老年,中年买与不买比例为,256/0,S1(,买,)=256,S2,(不买),=0,S=S1+S2=256,P1=256/256,P2=0/256,I(S1,S2)=I(256,,,0),=-P1Log,2,P1-P2Log,2,P2,=-(P1Log,2,P1+P2Log,2,P2),=0,决策树算法,计数,年龄,收入,学生,信誉,归类:买计算机,?,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,第,2-3,步计算年龄的熵,年龄共分三个组:,青年、中年、老年,老年买与不买比例为,125/127,S1(,买,)=125,S2,(不买),=127,S=S1+S2=252,P1=125/252,P2=127/252,I(S1,S2)=I(125,,,127),=-P1Log,2,P1-P2Log,2,P2,=-(P1Log,2,P1+P2Log,2,P2),=0.9157,决策树算法,计数,年龄,收入,学生,信誉,归类:买计算机,?,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,第,2-4,步计算年龄的熵,年龄共分三个组:,青年、中年、老年,所占比例,青年组,384/1025=0.375,中年组,256/1024=0.25,老年组,384/1024=0.375,计算年龄的平均信息期望,E,(年龄),=0.375*0.9183+,0.25*0+,0.375*0.9157,=0.6877,G,(年龄信息增益),=0.9537-0.6877,=0.2660,(,1,),决策树算法,计数,年龄,收入,学生,信誉,归类:买计算机,?,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,第,3,步计算收入的熵,收入共分三个组:,高、中、低,E,(收入),=0.9361,收入信息增益,=0.9537-0.9361,=0.0176,(2),决策树算法,计数,年龄,收入,学生,信誉,归类:买计算机,?,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,第,4,步计算学生的熵,学生共分二个组:,学生、非学生,E,(学生),=0.7811,年龄信息增益,=0.9537-0.7811,=0.1726,(,3,),决策树算法,计数,年龄,收入,学生,信誉,归类:买计算机,?,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,第,5,步计算信誉的熵,信誉分二个组:,良好,优秀,E,(信誉),=0.9048,信誉信息增益,=0.9537-0.9048,=0.0453,(,4,),决策树算法,计数,年龄,收入,学生,信誉,归类:买计算机,?,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,第,6,步计算选择节点,年龄信息增益,=0.9537-0.6877,=0.2660,(,1,),收入信息增益,=0.9537-0.9361,=0.0176,(,2,),年龄信息增益,=0.9537-0.7811,=0.1726,(,3,),信誉信息增益,=0.9537-0.9048,=0.0453,(,4,),决策树算法,计数,年龄,收入,学生,信誉,归类:买计算机,?,64,青,高,否,良,不买,64,青,高,否,优,不买,128,青,中,否,良,不买,64,青,低,是,良,买,64,青,中,是,优,买,年龄,青年,中年,老年,买,/,不买,买,买,/,不买,叶子,决策树算法,计数,年龄,收入,学生,信誉,归类:买计算机,?,64,青,高,否,良,不买,64,青,高,否,优,不买,128,青,中,否,良,不买,64,青,低,是,良,买,64,青,中,是,优,买,青年买与不买比例为,128/256,S1(,买,)=128,S2,(不买),=256,S=S1+S2=384,P1=128/384,P2=256/384,I(S1,S2)=I(128,256),=-P1Log2P1-P2Log2P2,=-(P1Log2P1+P2Log2P2),=0.9183,决策树算法,计数,年龄,收入,学生,信誉,归类:买计算机,?,64,青,高,否,良,不买,64,青,高,否,优,不买,128,青,中,否,良,不买,64,青,低,是,良,买,64,青,中,是,优,买,如果选择收入作为节点,分高、中、低,平均信息期望(加权总和,):,E(,收入),=0.3333*0+0.5*0.9183+0.1667*0=0.4592,Gain(,收入,)=,I(128,256),-E(,收入,)=,0.9183,0.4592=0.4591,I(0,128)=0,比例,:128/384=0.3333,I(64,128)=0.9183,比例,:192/384=0.5,I(64,0)=0,比例,:64/384=0.1667,注意,决策树算法,计数,年龄,收入,学生,信誉,归类:买计算机,?,64,青,高,否,良,不买,64,青,高,否,优,不买,128,中,高,否,良,买,60,老,中,否,良,买,64,老,低,是,良,买,64,老,低,是,优,不买,64,中,低,是,优,买,128,青,中,否,良,不买,64,青,低,是,良,买,132,老,中,是,良,买,64,青,中,是,优,买,32,中,中,否,优,买,32,中,高,是,良,买,63,老,中,否,优,不买,1,老,中,否,优,买,年龄,青年,中年,老年,学生,买,信誉,叶子,否,是,优,良,买,不买,买,/,不买,买,叶子,叶子,叶子,决策树算法,决策树归纳算法计算每个属性的信,息,增益,,,并从,中,挑,选,出信,息,增益,最大的属性作为,给定,集合,S,的测,试,属性,并由,此,产,生,相应,的分支,结点,。所,产,生的,结点,被标记,为,相应,的属性,,并根,据这一属性的,不同,取值分别,产,生,相应,的(决策树)分支,每个分支,代,表,一个,被,划,分的,样,本,子,集。,信息增益的计算,实例,1,:,一个商,场,顾客数据库(,训练样,本集合),样本集合的类别属性为:,“,buy_computer,”,,,该属性有两个不同取值,即,yes,no,,,因此就有两个不同的类别,(m=2),。设,C,1,对应 类别,yes,,,C,2,对应 类别,no,。,类别,C,1,包含,9,个样本,类别,C,2,包含,5,个样本。为了计算每个属性的信息增益,首先利用公式计算出所有(对一个给定样本进行分类所需要)的信息,具体计算过程如下:,实例,1,:,接,着需要计算每个属性的(信,息,),熵,。,假,设,先从,属性,“,age,”,开始,,,根,据属性,“,age,”,每个取值在,yes,类别和,no,类别中的分,布,,,就,可以计算出每个分,布,所对,应,的信,息,。,实例,1,:,然后,利用,公,式计算出,若根,据属性,“,age,”,对,样,本集合进行,划,分,所获得对一个数据对象进行分类而需要的信,息,熵,为:,由,此获得利用属性,“,age,”,对,样,本集合进行,划,分所获得的信,息,增益,为:,实例,1,:,类,似,可得,Gain(income)=0.029,,,Gain(student)=0.151,,,Gain(credit_rating)=0.048,。,显然选择,属性,“,age,”,所获得的信,息,增益,最大,,因,此,被,作为测,试,属性用于,产,生,当,前分支,结点,。这个,新,产,生的,结点,被标记,为,“,age,”,;,同时根,据属性,“,age,”,的,三,个,不同,取值,,产,生,三,个,不同,的分支,,当,前的,样,本集合,被,划,分为,三,个,子,集,如图所示。,最终产生的决策树,?,实例,1,:,编号,年龄,学生,信誉等级,类别标号,1,=30,是,良好,会购买,2,40,否,一般,会购买,4,40,否,良好,不会购买,5,40,否,一般,会购买,6,3140,是,一般,会购买,7,40,是,一般,会购买,9,40,否,良好,不会购买,11,=30,否,一般,不会购买,12,3140,是,一般,会购买,13,3140,否,一般,会购买,14,3140,是,良好,会购买,实例,1,:,“年龄”在各个属性中具有最大的信息增益,所以选择“年龄”属性作为第一个测试属性,创建一个节点,用“年龄”标记。,计算剩余各个属性的相应的信息增益,选择信息增益最大的属性作为测试属性,这时信息增益最大的是“学生”属性,创建一个节点,用“学生”标记。,实例,1,:,决策树中分类规则获取,决策树所表示的分类知识可以被抽取出来并可用,IF-THEN,分类规则形式加以表示。,从决策树的根结点到任一个叶结点所形成的一条路径就构成了一条分类规则。,沿着决策树的一条路径所形成的属性,-,值偶对就构成了分类规则条件部分(,IF,部分)中的一个合取项,叶结点所标记的类别就构成了规则的结论内容(,THEN,部分)。,IF-THEN,分类规则表达方式易于被人理解,且当决策树较大时,,IF-THEN,规则表示形式的优势就更加突出。,Example,IF,age,=“=30”AND,student,=“,no,”THEN,buys_computer,=“,no,”,IF,age,=“40”AND,credit_rating,=“,excellent,”THEN,buys_computer,=“,no,”,IF,age,=“0,,,F1:,30%,,,F2,:,30%-99%,F3:,100%,变为,F1,F2,F3,。,表,2,转化后的客户信息表,年龄,学历,职业,缴费方式,开户时间,费用变化率,客户流失,N3,W3,Z1,T1,H2,F1,NO,N2,W2,Z2,T2,H2,F2,NO,N1,W3,Z1,T3,H1,F2,YES,N1,W3,Z1,T2,H1,F1,NO,N1,W1,Z2,T2,H1,F1,NO,N2,W2,Z3,T3,H1,F3,YES,N3,W1,Z3,T1,H2,F1,NO,决策树算法,ID3,算法实际应用,-,在电信行业应用实例(,5,),YES,NO,年 龄,职 业,YES,缴费方式,YES,YES,NO,YSES,NO,NO,在网时长,NO,F1,F2,F3,N1,N2,N3,T1,T2,T3,Z1,Z2,Z3,H1,H2,费用变化率,决策树算法,ID3,算法实际应用,-,在电信行业应用实例(,6,),在图中,,NO,表示客户不流失,,YES,表示客户流失。从图可以看出,客户费用变化率,为,100%,的客户肯定已经流失;而费用变化率低于,30%,的客户;即每月资费相对稳定的客,户一般不会流失,费用变化率在,30%,99%,的客户有可能流失,其中年龄在,40,50,岁之间,的客户流失的可能性非常大,而年龄低于,40,岁的客
    展开阅读全文

    开通VIP折扣优惠下载文档

    提示  咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。

    咨信网小贴示:
    1、浏览或下载可查看了解,请点击【咨信网告知】。
    2、下载文件中如有侵权或不适当内容,将立即纠正。
    3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
    4、开具发票登录电脑端申请,请点击【索取发票】。

    咨信网客服组:【微信客服】

    自信AI创作助手
    关于本文
    本文标题:ch7-2-数据挖掘算法--分类方法.ppt
    链接地址:https://www.zixin.com.cn/doc/14767333.html

    Copyright ©2010-2026   All Rights Reserved  宁波自信网络信息技术有限公司 版权所有   |  客服电话:0574-28810668    微信客服:咨信网客服    投诉电话:18658249818   

    违法和不良信息举报邮箱:help@zixin.com.cn    文档合作和网站合作邮箱:fuwu@zixin.com.cn    意见反馈和侵权处理邮箱:1219186828@qq.com   | 证照中心

    12321jubao.png12321网络举报中心 电话:010-12321  jubao.png中国互联网举报中心 电话:12377   gongan.png浙公网安备33021202000488号  icp.png浙ICP备2021020529号-1 浙B2-20240490   


    关注我们 :微信公众号  抖音  微博  LOFTER               

    自信网络  |  ZixinNetwork