第3章分类《数据挖掘》课件

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章分类,of,56,1,高级大数据人才培养丛书之一，大数据挖掘技术与应用,分类,是一种很重要的数据挖掘技术，也是数据挖掘研究的重点和热点之一。分类的目的是分析输入数据，通过训练集中的数据表现出来的特性，为每一个类找到一种准确描述或者模型，这种描述常常用谓词来表示。由此生成的类描述用来对未来的测试数据进行分类。尽管这些未来测试数据的类标签是未知的，仍可以由此预测这些新数据所属的类。也可以由此对数据中每一个类有更好的理解,。,More,应用市场：,医疗诊断、人脸检测、故障诊断和故障,预警,第三章分类of561高级大数据人才培养丛书之一，大数据挖掘,3.1,基本概念,第三章分类,3.2,决策树,3.3,贝叶斯分类,3.5,实战：,决策树算法在,Weka,中的实现,习题,3.4,支持向量机,of,56,2,高级大数据人才培养丛书之一，大数据挖掘技术与应用,3.1基本概念第三章分类3.2决策树3.3贝叶斯分类,分类,（,Classification,）是一种重要的数据分析形式，它提取刻画重要数据类的模型。这种模型称为分类器，预测分类的（离散的、无序的）类标号。这些类别可以用离散值表示，其中值之间的次序没有意义,。,3.1.1,分类,的基本概念,of,56,3,3.1,基本概念,第三章 分类,分类,也可定义为：,分类,的任务就是通过学习得到一个目标函数,(Target,Function),，把每个属性,集,x,映射,到一个预先定义的类,标号,y,。,分类（Classification）是一种重要的数据,数据,分类过程有两阶段：,（,1,）学习阶段（构建分类模型）。,（,2,）分类阶段（使用模型预测给定数据的类标号）,。,3.1.2,分类,的,过程,of,56,4,3.1,基本概念,第三章 分类,建立分类模型的一般方法,数据分类过程有两阶段：3.1.2 分类的过程of56,分类器,的性能和所选择的训练集和测试集有着直接关系。一般情况下，先用一部分数据建立模型，然后再用剩下的数据来测试和验证这个得到的模型。如果使用相同的训练集和测试集，那么模型的准确度就很难使人信服。保持法和交叉验证是两种基于给定数据随机选样划分的，是常用的评估分类方法准确率的,技术。,3.1.3,分类器,性能的评估方法,of,56,5,3.1,基本概念,第三章 分类,分类器的性能和所选择的训练集和测试集有着直接关系。一,6,3.2,决策树,第三章分类,3.1,基本概念,3.3,贝叶斯分类,3.5,实战：,决策树算法在,Weka,中的实现,习题,3.4,支持向量机,of,56,6,高级大数据人才培养丛书之一，大数据挖掘技术与应用,63.2决策树第三章分类3.1基本概念3.3贝叶斯分,7,决策树,（,Decision Tree,）是一种类似于流程图的树结构，其中每个内部节点（非树叶节点）表示在属性上的测试，每个分支表示该测试上的一个输出，而每个树叶节点存放一个类标号，树的最顶层节点是根节点。决策树生成方式一般情况下都是由上而下的。每次不同的事件或决策都有可能引发至少两个以上的事件，形成不同的结果，这种决策方法用图形表示出来很像一棵树，所以称之为决策树。决策树是一种简单且广泛使用的分类器。通过训练数据来构建决策树，可高效地对未知的数据进行分类,。,3.2.1,决策树概述,of,56,7,3.2,决策树,第三章 分类,决策树,是数据挖掘的有力工具之一，决策树学习算法是从一组样本数据集（一个样本数据也可以称为实例）为基础的一种归纳学习算法，它着眼于从一组无次序、无规则的样本数据（概念）中推理出决策树表示形式的分类规则。,7 决策树（Decision Tree）是一种类似于流,8,基于,决策树的决策算法是属于实用性很好的总结预测算法之一，是一个趋近于非连续型函数值的算法,。决策树,在各行各业有着非常多的广泛应用，如在医院的临床决策、人脸检测、故障诊断、故障预警、医疗数据挖掘、案例分析、分类预测的软件系统等方面都有很大的用处,。,决策树,的最佳用途是图解说明如何领会决策与相关事件的相互作用,。,3.2.2,决策树,的用途和特性,of,56,8,3.2,决策树,第三章 分类,8 基于决策树的决策算法是属于实用性很好的总结预测算法,9,决策树,是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得到什么值的类似规则的方法。决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树。,直观,看，决策树分类器就像判断模块和终止块组成的流程图，终止块表示分类结果（也就是树的叶子）。判断模块表示对一个特征取值的,判断（,该特征有几个值，判断模块就有几个分支）,。,3.2.3,决策树,工作原理,of,56,9,3.2,决策树,第三章 分类,买电脑的决策树,9 决策树是通过一系列规则对数据进行分类的过程。它提供,10,10,上图,表示,了一个关心电子产品的用户是否会购买电脑，用它可以预测某条记录（某个人）的购买意向。树中包含了三种节点：,根节点（,root rode,），它没有入边，但有两条或多条出边。,子节点（,child node,），恰有一条入边和两条或多条出边。,叶节点（,leaf node,）或终节点（,terminal node,），恰有一条入边，但没有出边,。,在,决策树中，每个叶节点都赋予一个类标号。非终,节点（,包括根节点和内部节点）包含属性测试条件，用以分开具有不同特性的记录。这棵决策树对销售记录进行分类，指出一个电子产品消费者是否会购买一台计算机。每个内部节点（方形框）代表对某个属性的一次检测。每个叶节点（椭圆框）代表一个,类,。,of,56,10,3.2,决策树,第三章 分类,1010 上图表示了一个关心电子产品的用户是否会购买电,11,11,决策树,分类算法应用的完整流程应包含建树和应用。建树是从经验数据中获取知识，进行机器学习，建立模型或者构造分类器，是决策树算法的工作重点，通常又将其分为建树和剪枝两个部分,。,决策树,构建的基本,步骤,如下：,1,.,开始，所有记录看作一个节点,。,2,.,遍历每个变量的每一种分割方式，找到最好的分割点,。,3,.,分割成多个节点,N,1,，,N,2,，,N,m,（,m,的数量与当前的属性相关）,。,4,.,对,N,1,，,N,2,，,N,m,分别继续执行,2,3,步，直到每个节点足够“纯”为止。（“纯”的含义是要么全部是“是”，要么全部是“否”）,。,3.2.4,决策树,构建步骤,of,56,11,3.2,决策树,第三章 分类,1111 决策树分类算法应用的完整流程应包含建树和应用,12,12,12,树,的主体建好后，接下来便是对其剪枝,。,决策树,的剪枝一般通过极小化决策树整体的损失函数或代价函数来,实现。,决策树,剪枝常用的方法有两种：预,剪枝和,后,剪枝。,预,剪枝是根据一些原则尽早停止树的增长，如树的深度达到用户所要的深度、节点中样本个数少于用户指定个数等。预剪枝在建立树的过程中决定是否需要继续划分或分裂训练样本来实现提前停止树的构造，一旦决定停止分枝，就将当前节点标记为叶节点,。,后,剪枝是通过在完全生长的树上剪去分枝实现的，通过删除节点的分支来剪去树,节点。,of,56,12,3.2,决策树,第三章 分类,121212 树的主体建好后，接下来便是对其剪枝。of,13,13,13,1.,认识决策树,1,）决策树的生成过程,一,棵决策树的生成过程主要分为以下,3,个部分,：,（,1,）特征选择：特征选择是指从训练数据众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着很多不同量化评估标准，从而衍生出不同的决策树算法,。,（,2,）决策树生成：根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则决策树停止生长,。,（,3,）剪枝：决策树容易过拟合，一般都需要剪枝，缩小树结构规模、缓解过拟合,。,3.2.5,决策,树算法原理,of,56,13,3.2,决策树,第三章 分类,131313 1.认识决策树3.2.5 决策树算法原理,14,14,14,14,基于,信息论的决策树算法有,ID3,、,CART,和,C4.5,等算法，其中,C4.5,和,CART,两种算法从,ID3,算法中衍生而来。,CART,和,C4.5,支持数据特征为连续分布时的处理，主要通过使用二元切分来处理连续型变量，即求一个特定的值分裂值：特征值大于分裂值就走左子树，或者就走右子树,。,ID3,算法建立,在“奥卡姆剃刀”的基础上，越是小型的决策树越优于大的决策树。,ID3,算法中根据信息论的信息增益评估和选择特征，每次选择信息增益最大的特征来做判断模块,。,C4.5,是,ID3,的一个改进算法，继承了,ID3,算法的优点。,C4.5,算法用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足，在树构造过程中进行剪枝；能够完成对连续属性的离散化处理；能够对不完整数据进行处理,。,CART,算法采用的是基尼（,Gini,）指数（选,Gini,指数最小的特征,s,）作为分裂标准，同时它也是包含后剪枝操作,。,of,56,14,3.2,决策树,第三章 分类,14141414 基于信息论的决策树算法有ID3、CA,15,15,15,15,2,.ID3,算法,1）ID3,算法的信息论基础,（,1,）,信息熵,信息熵,：在概率论中，信息熵给了一种度量不确定性的方式，是用来衡量随机变量不确定性的，熵就是信息的期望值。若待分类的事物可能划分在,N,类中，分别是,x,1,，,x,2,，,x,n,，每一种取到的概率分别是,p,1,，,p,2,，,p,n,，,那么,X,的熵就定义为,：,从,定义中可知：,当,随机变量只取两个值时，即,X,的分布,则,熵为,：,of,56,15,3.2,决策树,第三章 分类,15151515 2.ID3算法of56153.2,16,16,16,16,16,16,（,2,）,条件熵,假设,有随机变量,（,X,Y,）,其联合概率分布为：,P(X=x,i,Y=y,i,)=p,ij,i=1,2,n;j=1,2,m,。,则条件熵,H(Y|X),表示在已知随机变量,X,的条件下随机变量,Y,的不确定性，其定义为,X,在给定条件下,Y,的条件概率分布的熵对,X,的数学期望,：,若是,样本的特征只有两个值,(X,1,=0,，,X,2,=1),对应,(,出现，不出现,),，如文本分类中某一个单词的出现与否。那么对于特征二值的情况，用,T,代表特征，用,t,代表,T,出现,，,表示,该特征不出现。那么,：,与,前面的公式对比一下，,P(t),就是,T,出现的概率，,P(),就是,T,不,出现的概率,，,结合信息熵的计算公式，可得,：,of,56,17,3.2,决策树,第三章 分类,161616161616 （2）条件熵of56173.,17,17,17,17,17,（,3,）信息,增益,信息,增益（,Information Gain,）表示得知特征,X,的信息后，而使得,Y,的不确定性减少的程度。定义为：,信息,增益是针对一个一个的特征而言的，就是看一个特征,X,，系统有它和没它的时候信息量各是多少，两者的差值就是这个特征给系统带来的信息增益,。,对于,特征取值为二值的情况，特征,T,给系统带来的信息增益就可以写成系统原本的熵与固定特征,T,后的条件熵之差,：,of,56,17,3.2,决策树,第三章 分类,1717171717 （3）信息增益of56173.2,18,18,18,18,18,18,3,.C4.5算法,C4.5,算法同样以“信