商务智能分类算法.ppt

第4章分类Chapter4:Classification,数据挖掘十大算法,Thek-meansalgorithmTheApriorialgorithmExpectationMaximizationPageRankAdaBoost,分类算法,C4.5CARTNaiveBayesk-nearestneighborclassificationSupportvectormachines,C4.5CARTNaiveBayesk-nearestneighborclassificationSupportvectormachines,C4.5CARTNaiveBayesk-nearestneighborclassificationSupportvectormachines,决策树分类算法,主要内容,4.1概念4.2决策树分类方法4.3朴素贝叶斯分类方法4.4k近邻分类方法4.5分类性能的度量,4.1基本概念,分类（classification）：总结已有类别的对象的特点并进而进行未知类别对象的类别预测的过程用给定的训练集用来建立一个分类模型（或称分类器），所建立的分类模型用来预测数据库中类标号未知的数据元组的类别。训练数据集由一组数据库元组（称为训练样本、实例或对象）构成样本形式为（v1，v2，vn；c），其中vi表示属性值，c表示类标号。,分类及其相关的基本概念,分类及其相关的基本概念,分类器（classifier)训练数据集（trainingdataset）分类属性（classlabelattribute），每个取值称为一个类别（classlabel）属性，用于描述一个对象的某个特性或性质测试数据集（testingdataset）,分类属于有监督学习还是无监督学习？有监督学习（classification）训练集是带有类标签的；新的数据是基于训练集进行分类的无监督学习（clustering）训练集是没有类标签的；提供一组属性，然后寻找出训练集中存在的类别或者聚集,人口、收入、信用购买力,性别、年龄、婚姻状况、收入信用等级,地点、产品、折扣促销效果,性别、收入、兴趣偏好产品类型,分类算法的应用领域,分类及其相关的基本概念,分类属性,类别,训练数据集,属性,分类方法,LazyEager构建模型测试、使用模型,分类：构建模型,Tenured?,分类：测试分类模型并预测,分类的概念与过程,分类技术,决策树（decisiontree）朴素贝叶斯（NaveBayes）K近邻（KnearestNeighbors）基于关联的分类支持向量机（SupportVectorMachines）人工神经网络LogisticRegression,4.2决策树分类方法,4.2决策树分类方法,4.2.1决策树的构建过程4.2.2属性的类型及分裂条件4.2.3决策树的剪枝,决策树的概念,决策树叶子节点：类别其余节点：测试属性树的层次根结点的层次为1根结点的子女结点的层次为2边：一种基于此结点属性的判断（分裂）条件,根节点,叶子节点,双亲节点,子女节点,决策树（decisiontree）是一个类似于流程图的树结构。树的最顶层节点是根节点，根节点与每个内部节点表示数据集合在某个属性上的测试，每个分枝代表一个数据子集的输出，而每个树叶节点代表类或类分布。,40,yes,no,excellent,fair,例:预测顾客是否可能购买计算机的决策树,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,SplittingAttributes,训练数据,模型:决策树,决策树分类实例,应用决策树进行分类,测试数据,Startfromtherootoftree.,应用决策树进行分类,测试数据,应用决策树进行分类,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,测试数据,应用决策树进行分类,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,测试数据,应用决策树进行分类,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,测试数据,应用决策树进行分类,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,测试数据,AssignCheatto“No”,构造决策树的方法采用自上而下递归的方式，如果：一个节点（训练集的子集合）上的数据都是属于同一个类别没有属性可以再用于对数据进行分割就将其作为一个叶子节点。否则，根据某种策略选择一个分裂属性，并按该属性的取值把实例集合划分为若干个子集合。并继续递归处理各子集。可基于启发式规则或者统计的度量，ID3算法选用最大信息增益法选择分裂属性,决策树的构建过程,决策树生成算法分成两个步骤：树的生成起始时,数据都在根节点；采用递归方式进行数据分片树的修剪去掉一些可能是噪音或者异常的数据,决策树的构建过程,主要步骤：训练数据集D，类别集合C=c1,c2,ck创建一个结点t，初始情况下训练数据集中的所有样本与根结点关联，记为Dt。将t设为当前结点。如果当前结点t所关联的数据集Dt中所有样本的类别相同（假设为ci）,则将该结点标记为叶子节点，记录类别为ci，停止对该结点所关联的数据集的进一步分裂。接着处理其他非叶子节点。否则，进入下一步。为数据集Dt选择分裂属性和分裂条件。根据分裂条件将数据集Dt分裂为m个子集，为结点t创建m个子女结点，将这m个数据集分别与之关联。依次将每个结点设为当前结点，转至步骤2进行处理，直至所有结点都标记为叶子结点。,决策树的构建,奥卡姆剃刀（OccamsRazor）原理：“如无必要，勿增实体”（Entitiesshouldnotbemultipliedunnecessarily）一棵小的树的预测能力更好采用分而治之的思想，利用贪心策略从局部出发来构造一棵大小紧凑的决策树。Hunt、ID3、C4.5、CART,决策树的构建过程,算法：Generate_decision_tree由给定的训练数据产生一棵决策树输入：训练样本samples，由离散值属性表示；侯选属性的集合attribute_list输出：一棵决策树方法：创建节点N；ifsamples都在同一个类Cthen返回N作为叶节点，以类C标记；ifattribute_list为空then返回N作为叶节点，标记为samples中最普通的类：/多数表决,选择attribute_list中具有最高信息增益的属性test_attribute；标记节点N为test_attribute；foreachtest_attribute中的已知值ai/划分samples由节点N长出一个条件为test_attribute=ai的分枝；设si是samples中的test_attribute=ai的样本集合;/划分ifsi为空then加上一个树叶，标记为samples中最普通的类：else加上一个由Generate_decision_tree（si，attribute-list-test-attribute）返回的节点,决策树的构建过程,决策树分类原理ProcedureBuildTree(S，A)(S：训练样本集，A：分类属性集合）用样本集S创建节点NifA为空then返回N，标记为S中最普遍的类ifNpurethen返回Nelsefor每一个属性A估计该节点在A上的信息增益选出最佳的属性A*，将S分裂为Si，N长出分支foreachSiifSi为空then返回叶节点，标记为S中最普遍的类elseBuildTree(Si,A-A*),决策树的构建过程,分裂属性选择在树的每个节点上使用信息增益度量选择测试属性。这种度量称作属性选择度量。选择具有最高信息增益的属性作为当前节点的测试属性。该属性使得对结果划分中的样本分类所需的信息量最小，并反映划分的最小随机性或不纯性。这种信息论的方法使得对一个对象分类所需的期望测试数目达到最小，并确保找到一棵简单（不必最简单）的树,第二节决策树分类,例题：样本个数10；类属性为hand_inpapers,取值为c1=yes,c2=no.,分裂属性选择,high,low,female,male,例题：样本个数10；类属性为hand_inpapers,取值为c1=yes,c2=no.,决策树的构建过程,分裂属性和分裂条件的选择分裂属性的选择通常利用类别纯度的衡量作为标准，信息熵和gini指数两种,D是训练样本集合。假定类标号属性具有m个不同值ci(i=1，m)。设pi是D中任意元组属于类ci中的概率。对一个D中的元组分类所需的期望信息为（实现完全划分的信息需求、不纯性度量）：信息熵:消除不确定性所需的信息量(bit),1比特的信息量指含有两个独立均等概率状态的事件不确定性被全部消除所需的信息。,分裂属性选择,分类属性的选择,信息熵entropy(D)数据集D及类别集合C=c1,c2,ckcount(ci)：类别ci在D中出现的次数，p(ci)：ci在D中出现的相对频率p(ci)=count(ci)/|D|D|代表D中的数据行数,若两个类别均匀分布(0.5,0.5)Entropy=?,信息熵,若所有行属于同一类别:Entropy=?,Info(D)=1,最高不纯性实现完全划分的信息需求最大,Info(D)=0,零不纯性已经实现完全划分信息需求为0,Info(D)=0.65,不纯性=实现完全划分的信息需求=0.65,Info(D)=1Gini=0.5Error=0.5,最高不纯性实现完全划分的信息需求最大,Info(D)=0Gini=0Error=0,零不纯性已经实现完全划分信息需求为0,Info(D)=0.65Gini=0.278Error=0.167,不纯性=实现完全划分的信息需求,分类属性的选择,按属性A分裂的信息熵entropy(D,A)数据集D按照属性A的分裂条件分裂出的m个子数据集分别为D1,D2,Dm，则entropy(D,A)综合这m个子数据集的信息熵就可以作为衡量一个属性A优劣的度gain(D,A)：一个数据集D按属性A分裂前后信息熵的差值信息增益（informationgain）gain(D,A)=entropy(D)-entropy(D,A),初始样本集合,某个分裂属性确定的样本子集,high,low,female,male,gender?,gpa?,接上例,high,low,？,？,第二节决策树分类,作业：训练样本集合D,样本个数14；类属性为buys_computer,取值为c1=yes,c2=no.,作业：训练样本集合D,样本个数14；类属性为buys_computer,取值为c1=yes,c2=no.,集合D分类所需的期望信息（不纯性）,30,40,30-40,使用属性A（age）将训练样本集合D划分为D1，D2，D3,属性A,集合D1,集合D2,集合D3,集合D3,集合D1,集合D2,使用age划分后，分类的期望信息（不纯性）,使用age划分的信息增益为,同样可以计算其它属性信息增益，得到age信息增益最大并选作分裂属性。用age来标记节点，并对每个属性值引出分枝,?,?,40,基尼指数（GiniIndex）,如果集合T分成两部分N1andN2。那么这个分割的Gini就是提供最小Ginisplit就被选择作为分割的标准.,Gini指标在CART中使用，并考虑每个属性的二元划分,其他分裂方法,CART算法：限定每次对数据集的分裂都是二分的若属性有个不同的取值a、b和c，则组合有3种情况a和b，c、a，b和c及a，c和b,信息增益的调整-增益比率,以属性“年龄”为例，分成的3个数据集的大小分别为4、5、5属性“年龄”的增益比率则为0.24/1.58=0.15,增益率（gainratio）在C4.5中使用,增益率（gainratio）在C4.5中使用，pj为属性A取不同值的概率。SplitI（A）值越小，表明属性A取值越少，GainRatio就越大，分类效果越好。,4.2.2属性的类型及分裂条件,为了减少信息增益，需要确定根据属性A对数据集的分裂方法属性的分类定量（quantitative）和定性（qualitative）定量属性又称为数值（numerical）属性，每个取值为数值，既可以比较大小，又可以进行数值运算，如加、减、乘、除等。如：“年收入”定性属性又称为类别（categorical）属性，其取值不具有数的特点。定性属性又可以分为标称（nominal）属性和序数（ordinal）属性属性从另一个角度又可以分为离散（discrete）属性和连续（continuous）属性,定性属性的分裂条件,一个数据集D若根据一个定性属性A进行分裂，假设A在D中的取值由集合VA表示，VA=a1，a1，am，则分裂条件为A=ai例如若按属性“婚姻”进行数据集分裂，则分裂条件为婚姻=单身、婚姻=已婚和婚姻=离异entropy(D,年龄)=0.69，entropy(D,性别)=0.89,按属性“婚姻”进行数据集分裂,定量属性的分裂条件（1）,属性及分类属性抽出并按年收入升序排序对于定量属性A，设A在数据集D中有m个不同的取值，a1ai，其中1i0，(i1，n)，则对任何事件BS，有,称为贝叶斯公式。,贝叶斯定律回顾,朴素贝叶斯分类：假定一个属性值对给定类的影响独立于其他属性的值，这一假定称作类条件独立。做此假定是为了简化计算，并在此意义下被称为“朴素的”贝叶斯信念网络：是图形模型，可以表示属性子集间的依赖,贝叶斯分类主要包括：,朴素贝叶斯分类,给定一个样本变量X的一个观察到的样本x，由n个属性A1,A2,An描述，其属性取值分别为x1,x2,xn，即x=(x1,x2,xn)，要判断其所属的类别，即类别属性Y的取值，C=c1,c2,ck贝叶斯定理：,朴素贝叶斯分类,假设给定类别变量取值一定的情况下，各个属性取值之间互相独立，则,概率计算,P(ci)可以用训练数据集中类别ci出现的次数占训练数据集总行数的比例来近似对于定性属性，P(xj|ci)可以通过计算类别为ci的样本中属性Aj取值为xj的样本所占比例来近似对于定量属性，有两种方法。一种方法是先将该属性取值离散化假设变量服从某种概率分布，通过训练数据集估计分布的参数,概率计算,对于定量属性，有两种方法。假设变量服从正态分布N（，2）。计算P(xj|ci)时，在类别为ci的样本中为属性Aj（xj是属性Aj的取值）的取值计算均值ij和标准差ij，然后利用下面的公式进行近似估计,x=（年龄30，男，年收入30万，单身），要预测其是否购买豪华车,平滑处理,在计算P(是|x)时，由于年龄P(X|Cj)P(Cj)，1jm，ji，换言之，X被指派到其P(X|Ci)P(Ci)最大的类Ci,DayOutlookTemperatureHumidityWindPlayTennis,1SunnyHotHighWeakNo,2SunnyHotHighStrongNo,3OvercastHotHighWeakYes,4RainMildHighWeakYes,5RainCoolNormalWeakYes,6RainCoolNormalStrongNo,7OvercastCoolNormalStrongYes,8SunnyMildHighWeakNo,9SunnyCoolNormalWeakYes,10RainMildNormalWeakYes,11SunnyMildNormalStrongYes,12OvercastMildHighStrongYes,13OvercastHotNormalWeakYes,14RainMildHighStrongNo,P(PlayTennis=yes)=9/14=0.64P(outlook=sunny|yes)=2/9P(temp=cool|yes)=3/9P(humidity=hi|yes)=3/9P(wind=strong|yes)=3/9P(yes|X)0.0053,给定：X=(Outlook=sunny;Temperature=cool;Humidity=high;Wind=strong)预测:PlayTennis=?,给定:(Outlook=sunny;Temperature=cool;Humidity=high;Wind=strong)P(PlayTennis=no)=5/14=0.36P(outlook=sunny|no)=3/5P(temp=cool|no)=1/5P(humidity=hi|no)=4/5P(wind=strong|no)=3/5P(no|X)0.0206,示例：设有数据库数据元组训练集，如下表所示。类标号属性buys_computer有两个不同值yes，no，因此有两个不同的类C1和C2，分别对应于yes和no。分别有9个样本和5个样本。希望分类的未知样本为：X=（age=“=30”，income=“medium”，student=“yes”，credit_rating=“fair”）,贝叶斯分类,示例：训练样本集合D,样本个数14；类属性为buys_computer,取值为c1=yes,c2=no.,贝叶斯分类,示例：求最大化P(X|Ci)P(Ci)，i=1，2。需要根据训练样本计算每个类的先验概率P(Ci)有：P(buys_computer=“yes”)=9/14=0.643P(buys_computer=“no”)=5/14=0.357,贝叶斯分类,示例：为计算P(X|Ci)，i=1，2。需要计算条件概率：P(age=“P(是|X)=逃税=否,示例：,A:（胎生是，会飞否，水中生活是，有腿否）M:哺乳动物N:非哺乳动物,P(A|M)P(M)P(A|N)P(N)=哺乳动物,示例：,朴素贝叶斯分类是以一个较强的假设：“数据中的属性相对于类标号是相互独立的”为基础的。这个假设条件在现实世界的任务中很少能满足。因此，研究人员采用新的基于统计理论的方法：具有较强理论根基、采用图解方式简洁易懂的表达概率分布的方法。这个结构称为贝叶斯信念网。,贝叶斯信念网络,贝叶斯信念网络其画出的图形像是节点结构图，每一个节点代表一个属性，节点间用有向连接线连接，但不能成环。其工作原理为：基于统计学中的条件独立，即给定父辈节点属性，每个节点对于他的祖辈、曾祖辈等都是条件独立的根据概率理论中链规则，n个属性ai的联合概率可以分解为如下乘积：,贝叶斯信念网络,贝叶斯信念网络是一个无环图，因此，可以对网络节点进行排序，使节点ai的所有先辈节点序号小于i。然后，由于条件独立假设，,贝叶斯信念网络,贝叶斯信念网络：变量之间存在依赖关系，提供了一种因果关系的图形，可以在其上进行学习主要由两部分定义：有向无环图（dag）：表示变量之间的依赖关系；每个属性条件概率表（cpt）：把各结点和其直接父结点关联起来。,贝叶斯信念网络,有向无环图（directedacyclinepraph）其中的每一个结点代表一个随机变量；每一条弧（两个结点间连线）代表一个概率依赖。若一条弧从结点Y到结点Z，那么Y就是Z的一个父结点，Z就是Y的一个子结点。给定父结点，每个变量有条件地独立于图中非子结点。变量既可取离散值，也可取连续值。它们既可对应数据集中实际的变量，也可对应数据集中的“隐含变量”，以构成一个关系。,贝叶斯信念网络,A,B,C,C,A,D,B,y,x1,x2,x3,x4,xd,(a),(c),(b),图使用有向无环图表示概率关系,包含所有变量的条件概率表（ConditionalProbabilityTable,CPT）对于一个变量Z，CPT定义了一个条件分布P(Z|parent(Z)；其中，parent(Z)表示Z的父结点。除了网络拓扑结构要求的条件独立性外，每个结点还关联一个概率表：（1）如果结点X没有父母结点，则表中只包含先验概率P(X);（2）如果结点X只有一个父母结点Y，则表中包含条件概率P(XY)（3）如果结点X有多个父母结点Y1，Y2，,YK，则表中包含条件概率P(XY1，Y2，,YK),性质：条件独立贝叶斯网络中的一个结点，如果它的父母结点已知，则该结点条件独立于它的所有非后代结点。,BayesianBeliefNetworks,BayesianbeliefnetworkallowsasubsetofthevariablesconditionallyindependentAgraphicalmodelofcausalrelationshipsRepresentsdependencyamongthevariablesGivesaspecificationofjointprobabilitydistribution,Nodes:randomvariablesLinks:dependencyX,YaretheparentsofZ,andYistheparentofPNodependencybetweenZandPHasnoloopsorcycles,贝叶斯信信念网络的有向无环图和每个属性条件概率表,FamilyHistory,Smoke,LungCancer,贝叶斯信念网络,BayesianBeliefNetwork:AnExample,FamilyHistory,LungCancer,PositiveXRay,Smoker,Emphysema,Dyspnea,LC,LC,(FH,S),(FH,S),(FH,S),(FH,S),0.8,0.2,0.5,0.5,0.7,0.3,0.1,0.9,BayesianBeliefNetworks,TheconditionalprobabilitytableforthevariableLungCancer:Showstheconditionalprobabilityforeachpossiblecombinationofitsparents,参加晚会后，第二天早晨呼吸中有酒精味的可能性有多大？如果头疼，患脑瘤的概率有多大？如果参加了晚会，并且头疼，那么患脑瘤的概率有多大？,Party,Hangover,BrainTumor,Headache,SmellAlcohol,PosXray,发现心脏病和心口痛病人的贝叶斯网络图,【例】我们使用以上BBN来诊断一个人是否患有心脏病,对于一个没有任何先验信息的人，我们可以通过计算先验概率来确定一个人是否可能患心脏病,设：Yes,No表示锻炼的两个值；健康，不健康表示饮食的两个值；,【例】我们使用以上BBN来诊断一个人是否患有心脏病,对于一个有高血压的人，我们可以通过计算后验概率来确定一个人是否可能患心脏病,因此，此人患心脏病的后验概率是：,=0.85*0.49+0.2*0.51=0.5185,=0.85*0.49/0.5185=0.8033,【例】我们使用以上BBN来诊断一个人是否患有心脏病,对于一个患高血压、常锻炼、饮食健康的人，我们可以通过比较后验概率来确定一个人是否可能患心脏病,此人患心脏病的后验概率是：,此人不患心脏病的后验概率是：0.4138,提供了一种用图形模型来捕获特定领域的先验知识的方法，网络还可以用来对变量间的因果关系进行编码；构造网络会费时费力；然而，网络结构一旦确定下来，添加新变量十分容易；贝叶斯信念网络适合处理不完整数据。对有属性遗漏的实例可以通过对该属性的所有可能取值的概率求和或求积分来加以处理；因为，数据和先验知识以概率的方式结合起来了，所以，该方法对模型的过分拟合问题是非常鲁棒的。,贝叶斯信念网络特点,4.4K近邻分类方法,K近邻,积极方法（eagermethod）决策树，贝叶斯懒惰方法（lazymethod）K近邻对于一个预测样本，从训练数据集中找到与其最相似的K个样本，利用这K个样本的类别来决定此样本的类别K由用户指定。相似样本的选择方法取决于样本之间相似度的衡量方法，多种相似度衡量方法的介绍详见第6章为一个测试样本选取了K个与其距离最小的样本之后，可以利用投票法（voting），统计各个类别的样本个数，将K个类别中占大多数的类别赋予测试样本,.,_,+,_,xq,+,_,_,+,_,_,+,相似性度量,欧式距离：给定样本a和样本b，分别由n个属性A1,A2,An描述，两个样本分别表示为a=(xa1,xa2,xan)，b=(xb1,xb2,xbn)，两个样本之间欧式距离dab规范化（normalization）最小-最大值法（min-maxmethod）。假设属性A原来的最大值为max，最小值为min，规范化后的取值范围为min1,max1，则对于该属性的任意的一个取值v，规范化后的取值v1可以如下计算：,4.5分类性能的度量,4.5分类性能的度量,4.5.1测试数据集的构造4.5.2分类性能的度量指标4.5.3不同分类模型的比较,4.5.1测试数据集的构造,保持法（holdout）人为确定训练数据集和测试数据集的比例，常用的比例是2:1和1:1交叉验证法（