商务智能分类算法.ppt

第4章 分类Chapter 4:Classification,信息管理学院,数据挖掘十大算法,The k-means algorithm The Apriori algorithm ExpectationMaximization PageRank AdaBoost,分类算法,C4.5 CART Naive Bayes k-nearest neighbor classification Support vector machines,C4.5 CART Naive Bayes k-nearest neighbor classificationSupport vector machines,C4.5 CART Naive Bayes k-nearest neighbor classificationSupport vector machines,决策树分类算法,主要内容,4.1 概念4.2 决策树分类方法4.3 朴素贝叶斯分类方法4.4 k近邻分类方法4.5 分类性能的度量,4.1 基本概念,信息管理学院,分类（classification）：总结已有类别的对象的特点并进而进行未知类别对象的类别预测的过程用给定的训练集用来建立一个分类模型（或称分类器），所建立的分类模型用来预测数据库中类标号未知的数据元组的类别。训练数据集由一组数据库元组（称为训练样本、实例或对象）构成样本形式为（v1，v2，vn；c），其中vi表示属性值，c表示类标号。,分类及其相关的基本概念,分类及其相关的基本概念,分类器（classifier)训练数据集（training dataset）分类属性（class label attribute），每个取值称为一个类别（class label）属性，用于描述一个对象的某个特性或性质测试数据集（testing dataset）,信息管理学院,分类属于有监督学习还是无监督学习？有监督学习（classification）训练集是带有类标签的；新的数据是基于训练集进行分类的无监督学习（clustering）训练集是没有类标签的；提供一组属性，然后寻找出训练集中存在的类别或者聚集,信息管理学院,人口、收入、信用购买力,性别、年龄、婚姻状况、收入信用等级,地点、产品、折扣促销效果,性别、收入、兴趣偏好产品类型,分类算法的应用领域,分类及其相关的基本概念,分类属性,类别,训练数据集,属性,分类方法,LazyEager构建模型测试、使用模型,分类：构建模型,Tenured?,分类：测试分类模型并预测,分类的概念与过程,分类技术,决策树（decision tree）朴素贝叶斯（Nave Bayes）K近邻（K nearest Neighbors）基于关联的分类支持向量机（Support Vector Machines）人工神经网络Logistic Regression,4.2 决策树分类方法,4.2 决策树分类方法,4.2.1 决策树的构建过程4.2.2 属性的类型及分裂条件4.2.3 决策树的剪枝,决策树的概念,决策树叶子节点：类别其余节点：测试属性树的层次 根结点的层次为1 根结点的子女结点的层次为2 边：一种基于此结点属性的判断（分裂）条件,根节点,叶子节点,双亲节点,子女节点,决策树（decision tree）是一个类似于流程图的树结构。树的最顶层节点是根节点，根节点与每个内部节点表示数据集合在某个属性上的测试，每个分枝代表一个数据子集的输出，而每个树叶节点代表类或类分布。,信息管理学院,=30,3040,40,yes,no,excellent,fair,例:预测顾客是否可能购买计算机的决策树,信息管理学院,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,80K,Splitting Attributes,训练数据,模型:决策树,决策树分类实例,信息管理学院,应用决策树进行分类,测试数据,Start from the root of tree.,信息管理学院,应用决策树进行分类,测试数据,信息管理学院,应用决策树进行分类,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,80K,测试数据,信息管理学院,应用决策树进行分类,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,80K,测试数据,信息管理学院,应用决策树进行分类,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,80K,测试数据,信息管理学院,应用决策树进行分类,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,80K,测试数据,Assign Cheat to“No”,信息管理学院,构造决策树的方法采用自上而下递归的方式，如果：一个节点（训练集的子集合）上的数据都是属于同一个类别没有属性可以再用于对数据进行分割就将其作为一个叶子节点。否则，根据某种策略选择一个分裂属性，并按该属性的取值把实例集合划分为若干个子集合。并继续递归处理各子集。可基于启发式规则或者统计的度量，ID3算法选用最大信息增益法选择分裂属性,决策树的构建过程,决策树生成算法分成两个步骤：树的生成 起始时,数据都在根节点；采用递归方式进行数据分片 树的修剪 去掉一些可能是噪音或者异常的数据,决策树的构建过程,主要步骤：训练数据集D，类别集合C=c1,c2,ck创建一个结点t，初始情况下训练数据集中的所有样本与根结点关联，记为Dt。将t设为当前结点。如果当前结点t所关联的数据集Dt中所有样本的类别相同（假设为ci）,则将该结点标记为叶子节点，记录类别为ci，停止对该结点所关联的数据集的进一步分裂。接着处理其他非叶子节点。否则，进入下一步。为数据集Dt选择分裂属性和分裂条件。根据分裂条件将数据集Dt分裂为m个子集，为结点t创建m个子女结点，将这m个数据集分别与之关联。依次将每个结点设为当前结点，转至步骤2进行处理，直至所有结点都标记为叶子结点。,决策树的构建,奥卡姆剃刀（Occams Razor）原理：“如无必要，勿增实体”（Entities should not be multiplied unnecessarily）一棵小的树的预测能力更好采用分而治之的思想，利用贪心策略从局部出发来构造一棵大小紧凑的决策树。Hunt、ID3、C4.5、CART,信息管理学院,决策树的构建过程,算法：Generate_decision_tree由给定的训练数据产生一棵 决策树输入：训练样本samples，由离散值属性表示；侯选属性的集合attribute_list输出：一棵决策树方法：创建节点N；if samples都在同一个类 C then 返回N作为叶节点，以类C标记；if attribute_list 为空 then 返回N作为叶节点，标记为samples中最普通的类：/多数表决,信息管理学院,选择attribute_list 中具有最高信息增益的属性test_attribute；标记节点N为test_attribute；for each test_attribute中的已知值ai/划分samples 由节点N长出一个条件为test_attribute=ai的分枝；设si是samples中的test_attribute=ai的样本集合;/划分 if si为空 then 加上一个树叶，标记为samples中最普通的类：else 加上一个由Generate_decision_tree（si，attribute-list-test-attribute）返回的节点,决策树的构建过程,信息管理学院,决策树分类原理Procedure BuildTree(S，A)(S：训练样本集，A：分类属性集合）用样本集S创建节点N if A为空 then 返回N，标记为S中最普遍的类 if N pure then 返回N else for 每一个属性 A 估计该节点在A上的信息增益 选出最佳的属性A*，将S分裂为Si，N长出分支 for each Si if Si 为空 then 返回叶节点，标记为S中最普遍的类 else BuildTree(Si,A-A*),决策树的构建过程,信息管理学院,分裂属性选择在树的每个节点上使用信息增益度量选择测试属性。这种度量称作属性选择度量。选择具有最高信息增益的属性作为当前节点的测试属性。该属性使得对结果划分中的样本分类所需的信息量最小，并反映划分的最小随机性或不纯性。这种信息论的方法使得对一个对象分类所需的期望测试数目达到最小，并确保找到一棵简单（不必最简单）的树,第二节 决策树分类,信息管理学院,例题：样本个数10；类属性为hand_in papers,取值为c1=yes,c2=no.,分裂属性选择,信息管理学院,high,low,female,male,例题：样本个数10；类属性为hand_in papers,取值为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分裂前后信息熵的差值信息增益（information gain）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来标记节点，并对每个属性值引出分枝,?,?,=30,3040,40,50,基尼指数（Gini Index）,如果集合T分成两部分 N1 and N2。那么这个分割的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,增益率（gain ratio）在C4.5中使用,信息管理学院,增益率（gain ratio）在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个不同的取值，a1 ai，其中1im,定量属性的分裂条件（2）,以“年收入40万”为例可以证明不需要在每个取值处都计算信息熵，只需在类别发生变化的两个点处进行数据集的分裂并计算信息熵即可年收入50万”、“年收入65万”、“年收入80万”、“年收入86万”、“年收入91万”、“年收入96万”最小的是“年收入80万”,定量属性的分裂条件（3）,数据集的信息熵entropy(D)=0.94.gain(D,年龄)=0.24,gain(D,年收入)=0.15，gain(D,性别)=0.05，gain(D,婚姻)=0.03.属性年龄的信息增益最大，故在根结点的分裂属性为“年龄”,4.2.3 决策树的剪枝,过度拟合（overfitting）过度拟合了训练集中的样本特点，训练集的准确度高，但通常具有较低的概括（generalization）能力，在预测未知类别对象时的准确率较低拟合不足（underfitting）如果过早地停止对结点的进一步分裂也会导致拟合不足问题剪枝（pruning）优化先剪枝（pre-pruning）后剪枝（post-pruning）,子树替换（subtree replacement）方法,C4.5中所用的基于误差估计的剪枝方法,子树替换剪枝：概括误差估计,子树替换剪枝：概括误差估计,基于统计的误差上界估计将上式中的不等式改为等式，解出p的上限为下式，作为每个结点中分类误差的悲观估计通过查标准正态分布表格，当=25%时z=0.69。C4.5中的默认值为25%。,信息管理学院,思考问题：,对算法感兴趣的同学：ID3算法是选用最大信息增益作为选择分裂属性的标准，C4.5与CART两种方法是用什么度量选择分裂属性的？对编程、数据挖掘软件感兴趣的同学：使用程序编写ID3算法，并用例题检验程序；使用spss modeler（climentine）等数据挖掘软件求解例题。,4.3 朴素贝叶斯分类方法,信息管理学院,定义 事件组A1，A2，An(n可为)，称为样本空间 S的一个划分，若满足：,A1,A2,An,B,贝叶斯定律回顾,信息管理学院,定理 设A1，,An是S的一个划分，且P(Ai)0，(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)时，由于年龄30的情况在类别为是的训练数据集中没有出现，导致结果为0平滑（smoothing）方法count(xj,ci)代表训练数据集中类别为ci且属性Aj取值为xj的样本个数，count(ci)代表训练数据集中类别为ci的样本个数。m和p的取值有各种不同的方法，一种常用的取值为，p=1/|C|,m=|C|，C为类别集合，|C|为类别的个数,平滑处理,信息管理学院,每个数据样本用一个n维特征向量X(x1，x2，xn)表示，分别描述对n个属性 A1，A2，An样本的n个度量；假设有m个类C1，C2，Cn。给定一个未知的数据样本X(x1，x2，xn)(即没有类标号)，朴素贝叶斯分类将未知的样本分配给类Ci，当且仅当,贝叶斯分类主要过程,信息管理学院,根据贝叶斯定理 最大化P(Ci|X)即可进行分类。其中P(Ci|X)最大的类Ci称为最大后验假定。其中P(X)代表属性集(A1，A2，An)取值为(x1，x2，xn)时的联合概率，为常数。所以最大化时只需对P(Ci|X)P(Ci)最大化即可。类的先验概率可以用P(Ci)Si/S计算，其中Si是Ci中训练样本数，而S是训练样本总数,贝叶斯分类主要过程,信息管理学院,给定具有许多属性的数据集，计算P(X|Ci)，即 P(Aixi，,Anxi|Ci)的开销可能非常大。为了降低计算P(X|Ci)的开销，可以做类条件独立的朴素假定。给定样本的类标号，假定属性值互相条件独立，即在属性间不存在依赖关系。这样，概率P(X1|Ci)，P(X2|Ci)，,P(Xn|Ci)可以由训练样本估值,贝叶斯分类主要过程,对未知样本X分类的时候，对每个类Ci，计算P(X1|Ci)。样本X被指指派到类Ci当且仅当P(X|Ci)P(Ci)P(X|Cj)P(Cj)，1jm，j i，换言之，X被指派到其P(X|Ci)P(Ci)最大的类Ci,Day Outlook Temperature Humidity Wind PlayTennis,1 Sunny Hot High Weak No,2 Sunny Hot High Strong No,3 Overcast Hot High Weak Yes,4 Rain Mild High Weak Yes,5 Rain Cool Normal Weak Yes,6 Rain Cool Normal Strong No,7 Overcast Cool Normal Strong Yes,8 Sunny Mild High Weak No,9 Sunny Cool Normal Weak Yes,10 Rain Mild Normal Weak Yes,11 Sunny Mild Normal Strong Yes,12 Overcast Mild High Strong Yes,13 Overcast Hot Normal Weak Yes,14 Rain Mild High Strong No,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/5 P(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.643 P(buys_computer=“no”)=5/14=0.357,贝叶斯分类,信息管理学院,示例：为计算P(X|Ci)，i=1，2。需要计算条件概率：P(age=“30”|buys_computer=“yes”)=2/9=0.222P(age=“30”|buys_computer=“no”)=3/5=0.600P(income=“medium”|buys_computer=“yes”)=4/9=0.444P(income=“medium”|buys_computer=“no”)=2/5=0.400P(student=“yes”|buys_computer=“yes”)=6/9=0.667P(student=“yes”|buys_computer=“no”)=1/5=0.200P(credit_rating=“fair”|buys_computer=“yes”)=6/9=0.667P(credit_rating=“fair”|buys_computer=“no”)=2/5=0.400,第三节 贝叶斯分类,信息管理学院,示例：使用以上概率，可以得到：P(X|buys_computer=“yes”)=0.222*0.444*0.667*0.667=0.044P(X|buys_computer=“no”)=0.600*0.400*0.200*0.400=0.019P(X|buys_computer=“yes”)P(buys_computer=“yes”)=0.044*0.643=0.028P(X|buys_computer=“no”)P(buys_computer=“no”)=0.019*0.357=0.007因此，对于样本X，朴素贝叶斯分类预测：buys_computer=“yes”,贝叶斯分类,信息管理学院,对于连续属性？离散化 把属性的范围划分为许多段：每一段设定一个有序值 这样会违反独立性假设估计概率密度:假定属性服从正态分布 估计该属性分布的参数(例如,均值和标准差)在得到概率密度之后，我们可以使用它估计条件概率P(Ai|c),示例：,信息管理学院,每一对(Ai,ci)的正态分布:例如对于(收入,逃税=否):在逃税=否的情况下，可征税收入的 样本均值=110 样本方差=2975,示例：,信息管理学院,P(X|逃税=否)=P(去年退税=否|逃税=否)P(婚姻中|逃税=否)P(收入=120K|逃税=否)=4/7 4/7 0.0072=0.0024P(X|逃税=是)=P(去年退税=否|逃税=是)P(婚姻中|逃税=是)P(收入=120K|逃税=是)=1 0 1.2 10-9=0因为：P(X|否)P(否)P(X|是)P(是)所以：P(否|X)P(是|X)=逃税=否,示例：,A:（胎生是，会飞否，水中生活是，有腿否）M:哺乳动物N:非哺乳动物,P(A|M)P(M)P(A|N)P(N)=哺乳动物,示例：,信息管理学院,朴素贝叶斯分类是以一个较强的假设：“数据中的属性相对于类标号是相互独立的”为基础的。这个假设条件在现实世界的任务中很少能满足。因此，研究人员采用新的基于统计理论的方法：具有较强理论根基、采用图解方式简洁易懂的表达概率分布的方法。这个结构称为贝叶斯信念网。,贝叶斯信念网络,信息管理学院,贝叶斯信念网络其画出的图形像是节点结构图，每一个节点代表一个属性，节点间用有向连接线连接，但不能成环。其工作原理为：基于统计学中的条件独立，即给定父辈节点属性，每个节点对于他的祖辈、曾祖辈等都是条件独立的根据概率理论中链规则，n个属性ai的联合概率可以分解为如下乘积：,贝叶斯信念网络,信息管理学院,贝叶斯信念网络是一个无环图，因此，可以对网络节点进行排序，使节点ai的所有先辈节点序号小于i。然后，由于条件独立假设，,贝叶斯信念网络,信息管理学院,贝叶斯信念网络：变量之间存在依赖关系，提供了一种因果关系的图形，可以在其上进行学习 主要由两部分定义：有向无环图（dag）：表示变量之间的依赖关系；每个属性条件概率表（cpt）：把各结点和其直接父结点关联起来。,贝叶斯信念网络,信息管理学院,有向无环图（directed acycline praph）其中的每一个结点代表一个随机变量；每一条弧（两个结点间连线）代表一个概率依赖。若一条弧从结点Y到结点Z，那么Y就是Z的一个父结点，Z就是Y的一个子结点。给定父结点，每个变量有条件地独立于图中非子结点。变量既可取离散值，也可取连续值。它们既可对应数据集中实际的变量，也可对应数据集中的“隐含变量”，以构成一个关系。,贝叶斯信念网络,A,B,C,C,A,D,B,y,x1,x2,x3,x4,xd,(a),(c),(b),信息管理学院,图 使用有向无环图表示概率关系,包含所有变量的条件概率表（Conditional Probability Table,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(X Y1，Y2，,YK),性质：条件独立 贝叶斯网络中的一个结点，如果它的父母结点已知，则该结点条件独立于它的所有非后代结点。,信息管理学院,Bayesian Belief Networks,Bayesian belief network allows a subset of the variables conditionally independentA graphical model of causal relationshipsRepresents dependency among the variables Gives a specification of joint probability distribution,X,Nodes:random variablesLinks:dependencyX,Y are the parents of Z,and Y is the parent of PNo dependency between Z and PHas no loops or cycles,信息管理学院,贝叶斯信信念网络的有向无环图和每个属性条件概率表,Family History,Smoke,Lung Cancer,贝叶斯信念网络,信息管理学院,Bayesian Belief Network:An Example,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,Bayesian Belief Networks,The conditional probability table for the variable LungCancer:Shows the conditional probability for each possible combination of its parents,信息管理学院,参加晚会后，第二天早晨呼吸中有酒精味的可能性有多大？如果头疼，患脑瘤的概率有多大？如果参加了晚会，并且头疼，那么患脑瘤的概率有多大？,Party,Hangover,Brain Tumor,Headache,Smell Alcohol,Pos Xray,信息管理学院,发现心脏病和心口痛病人的贝叶斯网络图,信息管理学院,【例】我们使用以上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.4 k近邻分类方法,K近邻,积极方法（eager method）决策树，贝叶斯懒惰方法（lazy method）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-max method）。假设属性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交叉验证法（cross-validation）自助抽样法（bootstrap）,Cross-validation(交叉验证)每个样本都交替地用于训练集或测试集n折交叉验证 n-Folds cross-validation常用：10折交叉验证数据集分成10份，每次用9分作训练集，1份做测试集留一法（Leave-one-out）,4.5.1 测试数据集的构造（续）,交叉验证,3折交叉验证留一法n-fold cross-validation:n是总样本个数,自助抽样法,自助抽样法采用放回抽样来构造训练数据集从中随机选取一个样本放到训练数据集中，然后将此样本放回中，重新抽取下一个样本，假设|D|=N，则重复抽取N次，得到一个大小为N的训练数据集。在N次放回抽样中，一个样本一次都没被抽中的概率为(1-1/N)N，则一个样本被抽中的概率为1-(1-1/N)N。当N很大时，该值逼近1-(1-1/N)N 1-1/e=0.632训练集中包含约63.2%的不同的样本些不包含在训练集中的样本则构成了测试数据集，包含D的36.8%的样本,4.5.2 分类性能的度量指标,分类输出结果,性能度量,真正率（true positive rate）TP rate和假正率（false positive rate）FP rate，查准率(precision)和查全率(recall),4.5.3 不同分类模型的比较,增益图（gains chart）ROC 曲线,增益图,表4.9 测试数据集结果示例,表4.10甘特图示例数据,增益图,ROC 曲线,ROC：receiver operating characteristic(接收者操作特性）Y轴：样本中所含正例样本的个数在正例样本总数中的百分比X轴：所选样本中的负例样本占测试样本中总负例样本的比例，即假正率,ROC曲线,通常可以通过曲线下包围的面积来衡量模型的性能，面积越大，性能越好。直线下的面积为0.5，通常分类模型对应的曲线下的面积取值范围为0.51.,weka,Decision treeclassifiers-trees-J48 可以不必修改参数(unpruned:false)KNN Classifier-lazy-IB1(1 nearest neighbor)无参数 Classifier-lazy-IBk(k nearest neighbor)OPTIONSKNN-The number of neighbors to use.设置k值Associative ClassificationPreprocess-open file(note:Discretized attributes)Associate-choose-Appriori(参数