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

数据挖掘高级大数据人才培养丛书之一，大数据挖掘技术与应用第三章分类分类是一种很重要的数据挖掘技术，也是数据挖掘研究的重点和热点之一。分类的目 的是分析输入数据，通过训练集中的数据表现出来的特性，为每一个类找到一种准确描 述或者模型，这种描述常常用谓词来表示。由此生成的类描述用来对未来的测试数据进 行分类。尽管这些未来测试数据的类标签是未知的，仍可以由此预测这些新数据所属的 类。也可以由此对数据中每一个类有更好的理解。高级大数据人才培养丛书之一，大数据挖掘技术与应用第三章分类.3.1 基本概念3：2决策树3.3 贝叶斯分类3.4 支持向量机3.5 实战：决策树算法在Weka中的实现 习题，3.1基本概念第三章分类3.1.1分类的基本概念分类(Classificat ion)是一种重要的数据分析形式，它提取刻画重要数据类的模型。这种模型称为分类器，预测分类的(离散的、无序的)类标号。这些类别可以用离散值 表示，其中值之间的次序没有意义。分类也可定义为：分类的任务就是通过学习得到一个目标函数(Tar get Funct ion)；，把每个属性集x映 射到一个预先定义的类标号y o图行天下 Ko.20150104020018208171)3.1基本概念第三章分类3.1.2分类的过程数据分类过程有两阶段：(1)学习阶段(构建分类模型)。(2)分类阶段(使用模型预测给定数据的类标号)o训练集I Tid属性1属性2属性3类1YesLarge125KNo2NoMedium100KNo3NoSmall70KNo4YesMedium120KNo5NoLarge95KYes6NoMedium60KNo7YesLarge220KNo8NoSmall85KYes9NoMedium75KNo10NoSmall90KYes测试集I Tid属性1属性2属性3类11NoSmall55K?12YesMedium80K?13YesLarge110K?14NoSmall95K?15NoLarge67K?建立分类模型的一般方法 3.1基本概念第三章分类3.1.3分类器性能的评估方法分类器的性能和所选择的训练集和测试集有着直接关系。一般情况下，先用一部分 数据建立模型,然后再用剩下的数据来测试和验证这个得到的模型。如果使用相同的训 练集和测试集，那么模型的准确度就很难使人信服。保持法和交叉验证是两种基于给定 数据随机选样划分的，是常用的评估分类方法准确率的技术。图片来源：拍信P高级大数据人才培养丛书之一，大数据挖掘技术与应用第三章分类3.1 基本概念3.2 决策树3.3 贝叶斯分类314 支持向量机3.5 实战：决策树算法在Weka中的实现 习题）32决策树第三章分类决策树是数据挖掘的有力工具之一，决策树学习算法是从一组样本数据集（一个样 本数据也可以称为实例）为基础的一种归纳学习算法，它着眼于从一组无次序、无规则 的样本数据（概念）中推理出决策树表示形式的分类规则。3.2.1 决策树概述决策树（Decision Tr ee）是一种类似于流程图的树结构,其中每个内部节点（非树 叶节点）表示在属性上的测试，每个分支表示该测试上的一个输出，而每个树叶节点存 放一个类标号，树的最顶层节点是根节点。决策树生成方式一般情况下都是由上而下的。每次不同的事件或决策都有可能引发至少两个以上的事件，形成不同的结果，这种决策 方法用图形表示出来很像一棵树，所以称之为决策树。决策树是一种简单且广泛使用的 分类器。通过训练数据来构建决策树，可高效地对未知的数据进行分类。)32决策树第三章分类3.2.2 决策树的用途和特性基于决策树的决策算法是属于实用性很好的总结预测算法之一，是一个趋近于非连 续型函数值的算法。决策树在各行各业有着非常多的广泛应用，如在医院的临床决策、人脸检测、故障诊断、故障预警、医疗数据挖掘、案例分析、分类预测的软件系统等方 面都有很大的用处。决策树的最佳用途是图解说明如何领会决策与相关事件的相互作用。）32决策树第三章分类3.2.3 决策树工作原理决策树是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得到 什么值的类似规则的方法。决策树分为分类树和回归树两种，分类树对离散变量做决策 树，回归树对连续变量做决策树。直观看，决策树分类器就像判断模块和终止块组成的流程图，终止块表示分类结果（也就是树的叶子）。判断模块表示对一个特征取值的判断（该特征有几个值，判断模 块就有几个分支）。年龄？:学生?；买二-A 尸，厂-Q买电脑的决策树45信用评级？1亡秀般买：C买二)32决策树第三章分类上图表示了一个关心电子产品的用户是否会购买电脑，用它可以预测某条记录(某 个人)的购买意向。树中包含了三种节点：根节点(r oot r ode),它没有入边，但有两条或多条出边。子节点(child node)，恰有一条入边和两条或多条出边。叶节点(leaf node)或终节点(t er minal node)，恰有一条入边，但没有出边。在决策树中，每个叶节点都赋予一个类标号。非终节点(包括根节点和内部节点)包含属性测试条件，用以分开具有不同特性的记录。这棵决策树对销售记录进行分类，指出一个电子产品消费者是否会购买一台计算机。每个内部节点(方形框)代表对某个 属性的一次检测。每个叶节点(椭圆框)代表一个类。）32决策树第三章分类3.2.4 决策树构建步骤决策树分类算法应用的完整流程应包含建树和应用。建树是从经验数据中获取知识，进行机器学习，建立模型或者构造分类器，是决策树算法的工作重点，通常又将其分为 建树和剪枝两个部分。决策树构建的基本步骤如下：1.开始，所有记录看作一个节点。2.遍历每个变量的每一种分割方式，找到最好的分割点。3.分割成多个节点Ni,N2，,Nm（m的数量与当前的属性相关）。4.对Ni,N2，,Nm分别继续执行23步，直到每个节点足够纯为止。（纯 的含义是要么全部是是，要么全部是否）。)32决策树第三章分类树的主体建好后，接下来便是对其剪枝。决策树的剪枝一般通过极小化决策树整体的损失函数或代价函数来实现。决策树剪枝常用的方法有两种：预剪枝和后剪枝。预剪枝是根据一些原则尽早停止树的增长，如树的深度达到用户所要的深度、节点 中样本个数少于用户指定个数等。预剪枝在建立树的过程中决定是否需要继续划分或分 裂训练样本来实现提前停止树的构造，一旦决定停止分枝，就将当前节点标记为叶节点。后剪枝是通过在完全生长的树上剪去分枝实现的，通过删除节点的分支来剪去树节)32决策树第三章分类3.2.5 决策树算法原理1.认识决策树1)决策树的生成过程一棵决策树的生成过程主要分为以下3个部分：(1)特征选择：特征选择是指从训练数据众多的特征中选择一个特征作为当前节点 的分裂标准，如何选择特征有着很多不同量化评估标准，从而衍生出不同的决策树算法。(2)决策树生成：根据选择的特征评估标准，从上至下递归地生成子节点，直到数 据集不可分则决策树停止生长。(3)剪枝：决策树容易过拟合，一般都需要剪枝，缩小树结构规模、缓解过拟合。）32决策树第三章分类基于信息论的决策树算法有ID3、CART和C4.5等算法,其中C4.5和CART两种算法 从ID3算法中衍生而来。CART和C4.5支持数据特征为连续分布时的处理，主要通过使用二元切分来处理连续 型变量，即求一个特定的值分裂值：特征值大于分裂值就走左子树，或者就走右 子树。ID3算法建立在奥卡姆剃刀的基础上，越是小型的决策树越优于大的决策树。ID3算法中根据信息论的信息增益评估和选择特征，每次选择信息增益最大的特征来做 判断模块。C4.5是ID3的一个改进算法，继承了ID3算法的优点。C4.5算法用信息增益率来选择 属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足，在树构造过程中进 行剪枝；能够完成对连续属性的离散化处理；能够对不完整数据进行处理。CART算法采用的是基尼（Gini）指数（选Gini指数最小的特征s）作为分裂标准，同 时它也是包含后剪枝操作。）32决策树第三章分类2.ID3算法1）ID3算法的信息论基础（1）信息精信息媒：港概率论中，信息焙给了一种度量不确定性的方式，是用来衡量随机变量不 确定性的，崎就是信息的期望值。若待分类的事物可能划分在N类中，分别是X,X2，,Xn,每一种取到的概率分别是内,p2，,Pn，那么X的精就定义为:nH（X）=-EpJogPii=l从定义中可知。W H（X）W log（小当随机变量只取两个值时,即X的分布尸（X=1）=p,尸（X=0）=1-,0 p 1则精为:H（X）=-plog2（p）-（1-/?）log2（1-p）32决策树第三章分类2）条件精假设看施机变量（X,Y），其联合概率分布为：P（X=Xi，Y=y）=pg,i=l,2，,n;j=l,2，,m。则条件精H（Y|X）表示在已知随机变量X的条件下随机变量Y的不确定性,其定义为X在给 定条件下Y的条件概率分布的嫡对X的数学期望：nH（YX）=YJPiH（YX=xi）Z=1若是样本的特征只有两个值（X1=O,X2=l）,对应（出现,不出现），如文本分类中某一 个单词的出现与否。那么对于特征二值的情况，用T代表特征，用t代表T出现；t表示该 特征不出现。那么：与前面的公式对比一下，P就是T出现的概率，P（i）就是T不出现的概率，结合信息 嫡的计算公式，可得：H（C|r）=-P（CJr）log2P（CJOZ=1_ n _ _“何卜p（G/og2 P（G）Z=1）32决策树第三章分类（3）信息增益信息增蔡i Infor mat ion Gain）表示得知特征X的信息后，而使得Y的不确定性减少 的程度。定义为：g（D,A）=H（D）-H（D|A）信息增益是针对一个一个的特征而言的，就是看一个特征X,系统有它和没它的时候 信息量各是多少，两者的差值就是这个特征给系统带来的信息增益。对于特征取值为二值的情况，特征T给系统带来的信息增益就可以写成系统原本的嫡与 固定特征T后的条件嫡之差：g（C,T）=H（C）-H（C|T）n n n=ZP（G）iog2 P（G）+P Z*Giog2 P。+网。2夕（。7）1叫（）i-l i-i-)32决策树第三章分类3.C4.5算法C4.5算法同样以信息嫡作为核心,是ID3基础上的优化改进,同时,也保持了 分类准确率高、速度快的特点。1)基本思想信息增薮35算法挑选具有最高信息增益率的属性为测试属性。对样本集T,假设 变量a有k个属性,属性取值a1，a2，,an,对应a取值为aj的样本个数分别为小，若n是 样本的总数,贝啦有+叫+.+%=n,Quinlan利用属性a的嫡值H(X,a),来定义为了获 取样本关于属性a的信息所需要付出的代价,即：i 7 H(X,a)信息增益率定义为平均互信息与获取a信息所付出代价的比值，即：k k 匕 匕H(X,)=(,.)10g2 P(生 卜10g2 z=l z=l n n)32决策树第三章分类4.CART算法CART算法生成的是一棵二叉树。它采用的是一种二分递归分割技术，每次都将当前 的数据集分为两个互不相交子集，使得所有非叶子节点都只有两个分支。1)分裂属性的选择标准CART算法分裂属性的选择标准为Gini指数。CART算法选择具有最小Gin指数的属 性为当前数据集的分裂属性。Gin指标分类方法适用于具有连续性或离散性属性的数 据集。设S为具有s个样本的数据集，所有样本总共包含m个不同的类别G,41,2，,m,那么Gin指标为：Gini(S)=l-ZPjZ=1其中Pi为样本属性类别C的概率。Input:age.gender,occupat ion,.Does t he per son like comput er games&3.2决策树第三章分类根据CART算法构造的是一棵二叉树,所以在CART算法中是用Gin指标进行二元划 分，对于数据集S的任何一个属性A的任何一种取值a,可以将数据集S划分成Si和S2两 个子集，对应属性A,Gin指标的计算公式如下：GiniA(S)=%Gini(Sj+J-Gini(S2)其中|S|表示数据集S的个数。当GiniA(S)最小时,属性A就为数据集S的最佳分裂属 性，Si和S2就是按属性A的取值a对数据集S的戈吩。2)CART算法建树过程CART算法建树过程见数据挖掘一书的第46页。高级大数据人才培养丛书之一，大数据挖掘技术与应用第三章分类3.1 基本概念3.2 决策树3.3 贝叶斯分类314 支持向量机3.5实战：决策树算法在Weka中的实现习题，3.3贝叶斯分类第三章分类贝叶斯分类是一类分类算法的总称,这类算法均以贝叶斯定理(Bayes t heor em)为基础，采用了概率推理方法。3.3.1 贝叶斯定理条件概率：表示事件B已经发生的前提下，事件A发生的概率，称为事件B发生下事 件A的条件概率。其基本求解公式为：器贝叶斯定理之所以有用，是因为在生活中经常遇到这种情况：可以很容易直接得出 P(A|B),PA)则很难直接得出，但人们往往更关ILPA),贝叶斯定理打通了从P(A|B)获 得PA)的道路。贝叶斯定理：P(BA)=尸，3.3贝叶斯分类第三章分类3.3.2 朴素贝叶斯分类原理与流程朴素贝叶斯分类是贝叶斯分类的一种，朴素贝叶斯分类与贝叶斯分类相比，后者需 要花很大的时间和空间复杂度去计算类条件概率。1.朴素贝叶斯分类原理朴素贝叶斯的思想基础是这样的：对于给出的待分类项，求解在此项出现的条件下 各个类别出现的概率，哪个最大，就认为此待分类项属于哪个类别。朴素贝叶斯分类的正式定义如下：(1)设)5:yest ime 2 5:yest ime 2:noscor e=bad:noscor e=gener albook=d:yesbook=e:nobook=f:nobook=g:no其中，scor e对应平时成绩，st udy对应上课学习情况，a、b、c分别对应好、一般和 差,book对应课本知识掌握情况,d、e、f、g分别对应完全掌握、基本掌握、一般和 不掌握，t ime对应平均上机时间。)3.5实战：决策树算法在Weka中的实现第三章分类根据学生成绩综合判定数据集J48(C4.5)算法生成的决策树如下图所示。是否为优的分类结果如下：总数为167,正确数为147,百分率为88.02%，错误数 为20,百分率为11.98%。高级大数据人才培养丛书之一，大数据挖掘技术与应用第三章分类3.1 基本概念3.2 决策树313贝叶斯分类3.4 支持向量机3.5 实战：决策树算法在Weka中的实现习题习题:1.数据分类一般分为哪两个阶段？请阐述。常用的评估分类方法准确率的技术有哪些？请阐述。2.什么是决策树？决策树的最佳用途是什么？决策树分为哪两种树？决策 树中一般包含哪几种节点？请阐述决策树构建的基本步骤。一棵决策树的生 成过程主要分为哪3个部分？请阐述决策树优缺点。3.ID3算法生成决策树的过程是什么？请阐述ID3算法的型良_94.5有哪两种基本 剪枝策略？请分别阐述它们的思包田整建树过程是什么？请阐述C4.5算法的优 缺点。请阐述CART算法建树过程皆赢Eart算法的优缺点。4.请阐述朴素贝叶斯分类的优缺点。整个朴素贝叶斯分类一般分为哪三个阶段？请阐 述。贝叶斯分析中的三要素是指哪三要素？贝叶斯决策主要包含哪四个部分？5,什么叫核函数?常用的核函数主要有以下哪几种?对偶问题与原始问题之间存在着哪 些关系？请阐述对偶理论。常用的损失函数有哪些？6.请阐述支持向量机的主要思想。支持向量机的理论有哪几个要点？请阐述 支持向量机（SVM）主要有哪几种情况？请阐述支持向量机的优点。48 of 48.感谢聆听