商务智能分类算法

1、第4章 分类Chapter 4: Classification信息管理理学院数据挖掘掘十大算算法Thek-meansalgorithmTheApriorialgorithmExpectationMaximizationPageRankAdaBoost分类算法法C4.5CARTNaiveBayesk-nearestneighborclassificationSupport vectormachinesC4.5CARTNaiveBayesk-nearestneighborclassificationSupport vectormachinesC4.5CARTNaiveBayesk-nearestn

2、eighborclassificationSupport vectormachines决策树分分类算法法主要内容容4.1概念4.2决策树分分类方法4.3朴素贝叶叶斯分类类方法4.4k近邻分类类方法4.5分类性能能的度量4.1基本概念念信息管理理学院分类（classification）：总结已有有类别的对象的特特点并进进而进行行未知类类别对象象的类别别预测的过程用给定的的训练集集用来建建立一个个分类模模型（或或称分类类器），所建立立的分类类模型用用来预测测数据库库中类标标号未知知的数据据元组的的类别。训练数据据集由一一组数据库元元组（称为训练样本本、实例例或对象象）构成样本形式为（v1，v2，v

3、n；c），其中vi表示属性性值，c表示类标号。分类及其其相关的的基本概概念分类及其其相关的的基本概概念分类器（classifier)训练数据据集（trainingdataset）分类属性性（classlabelattribute），每个个取值称称为一个个类别（classlabel）属性，用于描描述一个个对象的的某个特特性或性性质测试数据据集（testing dataset）信息管理理学院分类属于于有监督督学习还还是无监监督学习习？有监督学学习（classification）训练集是是带有类类标签的的；新新的数据据是基于于训练集集进行分分类的无监督学学习（clustering）训练集是是没有类类

4、标签的的；提供供一组属属性，然然后寻找找出训练练集中存存在的类类别或者者聚集信息管理理学院人口、收收入、信信用购买力性别、年年龄、婚姻状况况、收入入信用等级级地点、产产品、折折扣促销效果果性别、收收入、兴兴趣偏好产品品类型信用评分营销策略市场预测CRM分类算法法的应用用领域分类及其其相关的的基本概概念客户编号年龄性别年收入（万）婚姻豪华车130女86已婚否230男65单身否330男90离异否450女96离异否1150女80单身否1250男50单身是1350女80离异否1450男92离异是分类属性性类别训练数据据集属性分类方法法LazyEager构建模型型测试、使使用模型型分类：构构建模型型Tr

5、ainingDataClassificationAlgorithmsIF rank = professorOR years 6THEN tenured = yes Classifier(Model)TestingDataUnseen Data(Jeff, Professor, 4)ClassifierTenured?分类：测测试分类类模型并并预测If age=“30-40” and income=High then credit_rating=excellentnameageincomecredit_ratingli=30Lowfairwang40Medexcellentzhao24-35Hi

6、ghexcellentnameageincomecredit_ratingxin40High？wu=30Low？hu30-40High？分类规则未知数据incomeincomeage?exfexfex40 30-40highlow，medlow，medhigh决策树检验集训练集学习算法 学习算法训练集检验集模型未知数据分类的概概念与过过程分类技术术决策树（decisiontree）朴素贝叶叶斯（NaveBayes）K近邻（K nearestNeighbors）基于关联联的分类类支持向量量机（Support VectorMachines）人工神经经网络LogisticRegression4.2决

7、策树分分类方法4.2决策树分分类方法4.2.1决策树的的构建过过程4.2.2属性的类类型及分分裂条件件4.2.3决策树的的剪枝决策树的概念决策树叶子节点点：类别别其余节点点：测试试属性树的层次次根结点的层层次为1根结点的子子女结点点的层次次为2边：一种基于此此结点属属性的判判断（分分裂）条条件根节点叶子节点点双亲节点点子女节点点决策树（decisiontree）是一个类类似于流流程图的的树结构构。树的最顶顶层节点点是根节点，根节点与每个内部节点点表示数据据集合在在某个属属性上的的测试，每个分枝代表一个个数据子子集的输输出，而而每个树叶节点点代表类或或类分布布。信息管理理学院40yesnoexc

8、ellentfair例:预测顾客客是否可可能购买买计算机机的决策策树agestudentcredit_ratingbuys_computer30nofairno30-40noexcellentyesyesage？ nonoyesyescredit-rating？ student？ 信息管理理学院categoricalcategoricalcontinuousclassRefundMarStTaxIncYESNONONOYesNoMarriedSingle, Divorced 80KSplittingAttributes训练数据据模型:决策树决策树分分类实例例信息管理理学院应用决策策树进行行分类

9、RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80K测试数据据Startfrom theroot of tree.信息管理理学院应用决策策树进行行分类RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80K测试数据据信息管理理学院应用决策策树进行行分类RefundMarStTaxIncYESNONONOYesNoMarriedSingle, Divorced 80K测试数据据信息管理理学院应用决策策树进行行分类RefundMarStTaxIncYESNONONOYes

10、NoMarriedSingle, Divorced 80K测试数据据信息管理理学院应用决策策树进行行分类RefundMarStTaxIncYESNONONOYesNoMarriedSingle, Divorced 80K测试数据据信息管理理学院应用决策策树进行行分类RefundMarStTaxIncYESNONONOYesNoMarriedSingle, Divorced 80K测试数据据AssignCheatto“No”信息管理理学院构造决策策树的方方法采用用自上而下下递归的方式，如果：一个节点点（训练集集的子集集合）上的数据据都是属属于同一一个类别别没有属性性可以再再用于对对数据进进行分割

11、割就将其作作为一个个叶子节节点。否则，根据某种种策略选选择一个个分裂属属性，并按该该属性的的取值把把实例集集合划分分为若干干个子集集合。并并继续递递归处理理各子集集。可基于启启发式规规则或者者统计的的度量，ID3算法选用用最大信信息增益益法选择择分裂属属性决策树的的构建过过程决策树生生成算法分成成两个步步骤：树的生成成起始时,数据都在在根节点点；采用用递归方方式进行行数据分分片树的修剪剪去掉一些些可能是是噪音或或者异常常的数据据决策树的的构建过过程主要步骤骤：训练数据据集D，类别集合C=c1, c2, , ck创建一个个结点t，初始情情况下训训练数据据集中的的所有样样本与根根结点关关联，记记为

12、Dt。将t设为当前前结点。如果当前前结点t所关联的的数据集集Dt中所有样样本的类类别相同同（假设设为ci）,则将该结结点标记记为叶子子节点，记录类类别为ci，停止对对该结点点所关联联的数据据集的进进一步分分裂。接接着处理理其他非非叶子节节点。否否则，进进入下一一步。为数据集集Dt选择分裂裂属性和和分裂条条件。根根据分裂裂条件将将数据集集Dt分裂为m个子集，为结点点t创建m个子女结结点，将将这m个数据集集分别与与之关联联。依次次将每个个结点设设为当前前结点，转至步步骤2进行处理理，直至至所有结结点都标标记为叶叶子结点点。决策树的的构建奥卡姆剃剃刀（Occams Razor）原理：“如无必要要，勿

13、增增实体”（Entitiesshouldnot be multipliedunnecessarily）一棵小的的树的预预测能力力更好采用分而治之的思想，利用贪贪心策略略从局部部出发来来构造一一棵大小小紧凑的的决策树树。Hunt、ID3、C4.5、CART信息管理理学院决策树的的构建过过程算法：Generate_decision_tree由给定的的训练数数据产生生一棵决决策树树输入：训练样本本samples，由离散散值属性性表示；侯选属属性的集集合attribute_list输出：一棵决策策树方法： 创建建节点N；ifsamples都在同一一个类C then返回N作为叶节节点，以以类C标记；if

14、attribute_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加上一个个由Genera

15、te_decision_tree（si，attribute-list -test -attribute）返回的的节点决策树的的构建过过程信息管理理学院决策树分分类原理理ProcedureBuildTree(S，A)(S：训练样样本集，A：分类属属性集合合）用用样本集集S创建节点点NifA为空then返回N，标记为为S中最普遍遍的类ifN purethen返回Nelsefor每一个属属性A估计该节节点在A上的信息息增益选出最佳佳的属性性A*，将S分裂为Si，N长出分支支foreach SiifSi为空then返回叶节节点，标标记为S中最普遍遍的类elseBuildTree(Si,A-A*)决策树

16、的的构建过过程信息管理理学院分裂属性性选择在树的每每个节点点上使用用信息增益益度量选择择测试属属性。这这种度量量称作属性选择择度量。选择具具有最高高信息增增益的属属性作为为当前节节点的测试属性性。该属性性使得对对结果划划分中的的样本分分类所需需的信息息量最小小，并反反映划分分的最小随机机性或不纯性。这种信信息论的的方法使使得对一一个对象象分类所所需的期期望测试试数目达达到最小小，并确确保找到到一棵简简单（不不必最简简单）的的树第二节决决策策树分类类信息管理理学院gendergpatypehand_in papersmalelowfull-timenofemalehighpart-timeyes

17、类1类246例题：样样本个数数10；类属性为为hand_in papers,取值为c1=yes,c2=no.分裂属性性选择信息管理理学院类1类246类1类241类25类1类246类1类224类1类222highlowfemalemale属性 gender?例题：样样本个数数10；类属性为为hand_in papers,取值为c1=yes,c2=no.属性 gpa?类1类223类1类223决策树的的构建过过程分裂属性性和分裂裂条件的的选择分裂属性性的选择择通常利利用类别别纯度的的衡量作作为标准准，信息熵和和gini指数两种种ABclasscount00-5001-5010+011+100A+-0

18、1B-01A+-01信息管理理学院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

19、)=count(ci)/|D|D|代表D中的数据据行数若两个类类别均匀匀分布(0.5,0.5)Entropy=?1-+-1+1-+111信息熵若所有行行属于同同一类别别:Entropy=?信息管理理学院类1类233类1类215类26Info(D)=1最高不纯纯性实现完全全划分的的信息需需求最大大Info(D)=0零不纯性性已经实现现完全划划分信息息需求为为0Info(D)=0.65不纯性=实现完全全划分的的信息需需求=0.65信息管理理学院类1类233类1类215类26Info(D)=1Gini=0.5Error=0.5最高不纯纯性实现完全全划分的的信息需需求最大大Info(D)=0Gini=

20、0Error=0零不纯性性已经实现现完全划划分信息息需求为为0Info(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)初始样本本集合类1

21、类241类25类1类246某个分裂裂属性确确定的样样本子集集类1类241类25类1类246类1类224类1类222highlowfemalemalegender?gpa?接上例信息管理理学院类1类241类25highlowgendergpatypehand_in papersmalelowfull-timenofemalehighpart-timeyesgendertypehand_in papersmalefull-timenofemalepart-timeyes类1类246？信息管理理学院第二节决决策策树分类类作业：训训练样本本集合D,样本个数数14；类属性为为buys_computer,

22、取值为c1=yes,c2=no.ridageincomestudentcredit_ratingbuys_computer130highnofairno230highnoexcellentno330-40highnofairyes440mediumnofairyes540lowyesfairyes640lowyesexcellentno730-40lowyesexcellentyes830mediumnofairno930lowyesfairyes1040mediumyesfairyes1130mediumyesexcellentyes1230-40mediumnoexcellentyes13

23、30-40highyesfairyes1440mediumnoexcellentno信息管理理学院buys_computernonoyesyesyesnoyesnoyesyesyesyesyesno作业：训训练样本本集合D,样本个数数14；类属性为为buys_computer,取值为c1=yes,c2=no.集合D分类所需的期望信息（不纯性）信息管理理学院age？ridincomestudentCredit_ratingBuys_computer1highnofairno2highnoexcellentno3mediumnofairno4lowyesfairyes5mediumyesexcel

24、lentyesridincomestudentCredit_ratingBuys_computer1highnofairyes2lowyesexcellentyes3mediumnoexcellentyes4highyesfairyesRidincomestudentCredit_ratingBuys_computer1mediumnofairyes2lowyesfairyes3lowyesexcellentno4mediumyesfairyes5mediumnoexcellentno304030-40使用属性性A（age）将训练样样本集合合D划分为D1，D2，D3属性A集合D1集合D2集合D

25、3信息管理理学院ridincomestudentCredit_ratingBuys_computer1highnofairno2highnoexcellentno3mediumnofairno4lowyesfairyes5mediumyesexcellentyesridincomestudentCredit_ratingBuys_computer1highnofairyes2lowyesexcellentyes3mediumnoexcellentyes4highyesfairyesRidincomestudentCredit_ratingBuys_computer1mediumnofairye

26、s2lowyesfairyes3lowyesexcellentno4mediumyesfairyes5mediumnoexcellentno集合D3集合D1集合D2使用age划分后，分类的期望信息（不纯性）使用age划分的信息增益为信息管理理学院同样可以以计算其它它属性信信息增益益，得到age信息增益益最大并并选作分分裂属性性。用age来标记节节点，并并对每个个属性值值引出分分枝?40yesage？50基尼指数数（Gini Index）如果集合合T分成两部部分N1andN2。那么这个个分割的的Gini就是提供最小小Ginisplit就被选择择作为分分割的标标准.Gini指标在CART中使用，并

27、考虑虑每个属属性的二二元划分分其他分裂裂方法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属性的类

28、类型及分分裂条件件为了减少少信息增增益，需需要确定定根据属性A对数据集集的分裂裂方法属性的分分类定量（quantitative）和定性性（qualitative）定量属性性又称为为数值（numerical）属性，每个取取值为数数值，既既可以比比较大小小，又可可以进行行数值运运算，如如加、减减、乘、除等。如：“年收入入”定性属性性又称为为类别（categorical）属性，其取值值不具有有数的特特点。定定性属性性又可以以分为标称（nominal）属性和序数（ordinal）属性属性从另另一个角角度又可可以分为为离散（discrete）属性和和连续（continuous）属性定性属性性的分裂裂条件

29、一个数据据集D若根据一一个定性性属性A进行分裂裂，假设设A在D中的取值值由集合合VA表示，VA=a1，a1，am，则分裂裂条件为为A=ai例如若按属性性“婚姻姻”进行行数据集集分裂，则分裂裂条件为为婚姻=单身、婚婚姻=已婚和婚婚姻=离异entropy(D,年龄)=0.69，entropy(D,性别)=0.89按属性“婚姻”进行数数据集分分裂客户编号年龄性别年收入（万）婚姻豪华车250女80单身否1250男50单身是客户编号年龄性别年收入（万）婚姻豪华车130女86已婚否430女75已婚否530-50女82已婚是630-50男91已婚是客户编号年龄性别年收入（万）婚姻豪华车350女96离异否13

30、50女80离异否1450男92离异是定量属性的分分裂条件件（1）属性及分分类属性性抽出并并按年收收入升序序排序对于定量量属性A，设A在数据集集D中有m个不同的的取值，a1a1ai，其中1i0，(i1，n)，则对任何何事件BS，有称为贝叶斯公公式。贝叶斯定定律回顾顾信息管理理学院朴素贝叶叶斯分类类：假定一个个属性值值对给定定类的影影响独立立于其他他属性的的值，这这一假定定称作类类条件件独立。做此假假定是为为了简化化计算，并在此此意义下下被称为为“朴素素的”贝叶斯信信念网络络：是图形模模型，可可以表示示属性子子集间的的依赖贝叶斯分分类主要要包括：朴素贝叶叶斯分类类给定一个个样本变变量X的一个观观察

31、到的的样本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的样本所所占比例例来近似似对于定量量属性，有两种种方法。一种方法法是先将将该属性性取值离离散化假设变

32、量量服从某某种概率率分布，通过训训练数据据集估计计分布的的参数概率计算算对于定量量属性，有两种种方法。假设变量量服从正正态分布布N（，2）。计算算P(xj|ci)时，在类类别为ci的样本中中为属性性Aj（xj是属性Aj的取值）的取值值计算均均值ij和标准差差ij，然后利利用下面面的公式式进行近近似估计计x=（年龄30，男，年年收入30万，单身身），要要预测其其是否购购买豪华华车客户编号年龄性别年收入（万）婚姻豪华车130女86已婚否230男65单身否330男90离异否450女96离异否1150女80单身否1250男50单身是1350女80离异否1450男92离异是P(是)=5/14, P(否)

33、=9/14P(年龄=30-50|是)=3/5P(年龄50|是)=2/5P(性别=女|是)=2/5P(性别=男|是)=3/5P(婚姻=已婚|是)=2/5P(婚姻=离异|是)=2/5P(婚姻=单身|是)=1/5P(年龄50|否)=3/9P(性别=女|否)=6/9P(性别=男|否)=3/9P(婚姻=已婚|否)=2/9P(婚姻=离异|否)=4/9P(婚姻=单身|否)=3/9类别=“是”时，年收入的均值为103，标准差为56.8类别=“否”时，年收入的均值为70，标准差为25平滑处理理在计算P(是|x)时，由于于年龄P(X|Cj) P(Cj)，1jm，ji，换言之之，X被指派到到其P(X|Ci) P(C

34、i)最大的类类CiDayOutlookTemperatureHumidityWindPlayTennis1SunnyHotHighWeakNo2SunnyHotHighStrongNo3OvercastHotHighWeakYes4RainMildHighWeakYes5RainCoolNormalWeakYes6RainCoolNormalStrongNo7OvercastCoolNormalStrongYes8SunnyMildHighWeakNo9SunnyCoolNormalWeakYes10RainMildNormalWeakYes11SunnyMildNormalStrongYes

35、12OvercastMildHighStrongYes13OvercastHotNormalWeakYes14RainMildHighStrongNoP(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=?给定:(Outloo

36、k=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个样本。希望分分类的

37、未未知样本本为：X=（age=“=30”，income=“medium”，student=“yes”，credit_rating=“fair”）贝叶斯分分类信息管理理学院示例：训训练样本本集合D,样本个数数14；类属性为为buys_computer,取值为c1=yes,c2=no.ridageincomestudentcredit_ratingbuys_computer130highnofairno230highnoexcellentno330-40highnofairyes440mediumnofairyes540lowyesfairyes640lowyesexcellentno730-40

38、lowyesexcellentyes830mediumnofairno930lowyesfairyes1040mediumyesfairyes1130mediumyesexcellentyes1230-40mediumnoexcellentyes1330-40highyesfairyes1440mediumnoexcellentno贝叶斯分分类信息管理理学院示例：求最大化化P(X|Ci)P(Ci)，i=1，2。需要根根据训练练样本计计算每个个类的先先验概率率P(Ci)有：P(buys_computer=“yes”)=9/14=0.643P(buys_computer=“no”)=5/14=0.

39、357贝叶斯分分类信息管理理学院示例：为计算P(X|Ci)，i=1，2。需要计计算条件件概率：P(age=“30”|buys_computer=“yes”)=2/9=0.222P(age=“P(X|是)P(是)所以：P(否|X) P(是|X)=逃税=否示例：A:（胎生是，会会飞否否，水中生活活是，有腿否）M:哺乳动物物N:非哺乳动动物P(A|M)P(M) P(A|N)P(N)=哺乳动物物名称胎生会飞水中生活有腿类别Human是否否是哺乳python否否否否非哺乳salmon否否是否非哺乳whale是否是否哺乳frog否否有时是非哺乳komodo否否否是非哺乳bat是是否是哺乳pigeon否是否

40、是非哺乳cat是否否是哺乳leopard_shark是否是否非哺乳turtle否否有时是非哺乳penguin否否有时是非哺乳porcupine是否否是哺乳eel否否是否非哺乳salamander否否有时是非哺乳gila_monster否否否是非哺乳platypus否否否是哺乳owl否是否是非哺乳dolphin是否是否哺乳eagle否是否是非哺乳胎生会飞水中生活有腿类别是否是否？示例：信息管理理学院朴素贝叶叶斯分类类是以一一个较强强的假设设：“数数据中的的属性相相对于类类标号是是相互独独立的”为基础础的。这这个假设设条件在在现实世世界的任任务中很很少能满满足。因因此，研研究人员员采用新新的基于于

41、统计理理论的方方法：具具有较强强理论根根基、采采用图解解方式简简洁易懂懂的表达达概率分分布的方方法。这这个结构构称为贝叶斯信信念网。贝叶斯信信念网络络信息管理理学院贝叶斯信信念网络络其画出的的图形像像是节点点结构图图，每一一个节点点代表一一个属性性，节点点间用有有向连接接线连接接，但不不能成环环。其工工作原理理为：基于统计计学中的的条件独独立，即即给定父父辈节点点属性，每个节节点对于于他的祖祖辈、曾曾祖辈等等都是条条件独立立的根据概概率理论论中链规规则，n个属性ai的联合概概率可以以分解为为如下乘乘积：贝叶斯信信念网络络信息管理理学院贝叶斯信信念网络络是一个个无环图图，因此此，可以以对网络络节

42、点进进行排序序，使节节点ai的所有先先辈节点点序号小小于i。然后，由于条条件独立立假设，贝叶斯信信念网络络信息管理理学院贝叶斯信信念网络络：变量之间间存在依依赖关系系，提供供了一种种因果关关系的图图形，可可以在其其上进行行学习主要由两两部分定定义：有向无环环图（dag）：表示变变量之间间的依赖赖关系；每个属性性条件概率率表（cpt）：把各结结点和其其直接父父结点关关联起来来。贝叶斯信信念网络络信息管理理学院有向无环环图（directedacyclinepraph）其中的每每一个结结点代表表一个随随机变量量；每一一条弧（两个结结点间连连线）代代表一个个概率依依赖。若一条弧弧从结点点Y到结点Z，那

43、么Y就是Z的一个父父结点，Z就是Y的一个子子结点。给定父父结点，每个变变量有条条件地独独立于图图中非子子结点。变量既可可取离散散值，也也可取连连续值。它们既既可对应应数据集集中实际际的变量量，也可可对应数数据集中中的“隐隐含变量量”，以以构成一一个关系系。贝叶斯信信念网络络ABCCADByx1x2x3x4xd(a)(c)(b)信息管理理学院图使使用有向向无环图图表示概概率关系系包含所有有变量的的条件概概率表（ConditionalProbabilityTable,CPT）对于一个个变量Z，CPT定义了一一个条件件分布P (Z|parent(Z) )；其中，parent(Z)表示Z的父结点点。除

44、了了网络拓拓扑结构构要求的的条件独独立性外外，每个个结点还还关联一一个概率率表：（1）如果结结点X没有父母母结点，则表中中只包含含先验概概率P(X);（2）如果结结点X只有一个个父母结结点Y，则表中中包含条条件概率率P(XY)（3）如果结结点X有多个父父母结点点Y1，Y2，,YK，则表中中包含条条件概率率P(X Y1，Y2，,YK)性质：条条件独立立贝贝叶斯网网络中的的一个结结点，如如果它的的父母结结点已知知，则该该结点条条件独立立于它的的所有非非后代结结点。信息管理理学院BayesianBeliefNetworksBayesianbeliefnetworkallowsasubsetofthe

45、variables conditionallyindependentA graphicalmodelofcausalrelationshipsRepresentsdependencyamongthevariablesGivesa specificationofjointprobabilitydistributionXYZPNodes:random variablesLinks:dependencyX,Yarethe parentsofZ, andYistheparent ofPNodependency betweenZandPHasnoloopsorcycles信息管理理学院贝叶斯信信信念网网

46、络的有向无环环图和每个属属性条件概率率表FamilyHistorySmokeLung CancerFH，SFH，SFH，SFH，SLC0.80.50.70.1LC0.20.50.30.9贝叶斯信信念网络络信息管理理学院BayesianBeliefNetwork:AnExampleFamilyHistoryLungCancerPositiveXRaySmokerEmphysemaDyspneaLCLC(FH, S)(FH, S)(FH,S)(FH,S)0.80.20.50.50.70.30.10.9BayesianBeliefNetworksTheconditionalprobabilityta

47、blefor thevariableLungCancer:Showstheconditionalprobabilityfor eachpossiblecombinationofits parents信息管理理学院参加晚会会后，第第二天早早晨呼吸吸中有酒酒精味的的可能性性有多大大？如果头疼疼，患脑脑瘤的概概率有多多大？如果参加加了晚会会，并且且头疼，那么患患脑瘤的的概率有有多大？PartyHangoverBrainTumorHeadacheSmellAlcoholPosXray信息管理理学院锻炼心口痛饮食心脏病血压胸痛HD=YesE=YesD=健康 0.25E=YesD=不健康 0.45E=No

48、D=健康 0.55E=NoD=不健康 0.75CP=YesHD=YesHb=Yes 0.8HD=YesHb=No 0.6HD=NoHb=Yes 0.4HD=NoHb=No 0.1Hb=YesD=健康 0.2D=不健康 0.85BP=高HD=Yes 0.85HD=No 0.2 E=Yes 0.7D=健康 0.25发现心脏脏病和心心口痛病病人的贝贝叶斯网网络图信息管理理学院【例】我们使用用以上BBN来诊断一一个人是是否患有有心脏病病对于一个个没有任任何先验验信息的的人，我我们可以以通过计计算先验验概率来来确定一一个人是是否可能能患心脏脏病设：Yes,No表示锻炼炼的两个个值；健康，不不健康表示饮食

49、食的两个个值；信息管理理学院【例】我们使用用以上BBN来诊断一一个人是是否患有有心脏病病对于一个个有高血血压的人人，我们们可以通通过计算算后验概概率来确确定一个个人是否否可能患患心脏病病因此，此此人患心心脏病的的后验概概率是：=0.85*0.49+0.2*0.51=0.5185=0.85*0.49/0.5185=0.8033信息管理理学院【例】我们使用用以上BBN来诊断一一个人是是否患有有心脏病病对于一个个患高血血压、常常锻炼、饮食健健康的人人，我们们可以通通过比较较后验概概率来确确定一个个人是否否可能患患心脏病病此人患心心脏病的的后验概概率是：此人不患患心脏病病的后验验概率是是：0.4138

50、信息管理理学院提供了一一种用图图形模型型来捕获获特定领领域的先先验知识识的方法法，网络络还可以以用来对对变量间间的因果果关系进进行编码码；构造网络络会费时时费力；然而，网络结结构一旦旦确定下下来，添添加新变变量十分分容易；贝叶斯信信念网络络适合处处理不完完整数据据。对有有属性遗遗漏的实实例可以以通过对对该属性性的所有有可能取取值的概概率求和和或求积积分来加加以处理理；因为，数数据和先先验知识识以概率率的方式式结合起起来了，所以，该方法法对模型型的过分分拟合问问题是非非常鲁棒棒的。贝叶斯信信念网络络特点4.4K近邻分类类方法K近邻积极方法法（eagermethod）决策树，贝叶斯斯懒惰方法法（l

51、azy method）K近邻对于一个个预测样样本，从从训练数数据集中中找到与与其最相相似的K个样本，利用这这K个样本的的类别来来决定此此样本的的类别K由用户指指定。相相似样本本的选择择方法取取决于样样本之间间相似度度的衡量量方法，多种相相似度衡衡量方法法的介绍绍详见第第6章为一个测测试样本本选取了了K个与其距距离最小小的样本本之后，可以利利用投票票法（voting），统计计各个类类别的样样本个数数，将K个类别中中占大多多数的类类别赋予予测试样样本._+_xq+_+_+相似性度度量欧式距离离：给定样本本a和样本b，分别由由n个属性A1,A2, ,An描述，两两个样本本分别表表示为a=(xa1,x

52、a2,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-val