第7章-决策树与贝叶斯网络课件

第七章决策树与贝叶斯网络

1

决策树的形成与发展1.1简介决策树方法的起源是概念学习系统CLS，然后发展到ID3方法而为高潮，最后又演化为能处理连续属性的C4.5。有名的决策树方法还有CART是应用最广的归纳推理算法之一语义可表示性对噪声数据有很好的健壮性1.2决策树的表示法决策树通过把实例从根节点排列到某个叶子节点来分类实例，叶子节点即为实例所属的分类。树上的每一个节点说明了对实例的某个属性的测试，并且该节点的每一个后继分支对应于该属性的一个可能值。图1.3构造决策树决策树分类过程从根节点开始，首先对某一属性的取值提问•Color?与根节点相连的不同分支，对应这个属性的不同取值•green;yellow;red;根据不同的回答，转向相应的分支•green在新到达的节点处做同样的分支判断•Size?–big.这一过程持续，直到到达某个叶节点，输出该叶节点的类别标记•Watermelon

2

决策树的基本原理：

统计学角度2.1决策树的判决面2.2构造决策树•基本过程•从上到下，分而治之（divide-and-conquer），递归生长

•最初，所有的样本都在根节点•所有属性都是标称型的（如果是连续数值型的，则需要先离散化ID3)

•所有样本根据每次选择出的属性递归的逐渐划分开来

•满足如下条件之一时，划分操作停止

•所有落入某一节点的样本均属于同一类别•没有特征能够进一步用于划分样本集•没有任何样本落入某一节点属性选择构造好的决策树的关键在于如何选择好的逻辑判断或属性。对于同样一组例子，可以有很多决策树能符合这组例子。人们研究出，一般情况下或具有较大概率地说，树越小则树的预测能力越强。要构造尽可能小的决策树，关键在于选择恰当的逻辑判断或属性。由于构造最小的树是NP-难问题，因此只能采取用启发式策略选择好的逻辑判断或属性。

度量标准——熵熵(Entropy)信息论中广泛使用的一个度量标准刻画任意样例集的纯度（purity）一般计算公式为：对于二元分类：给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为：

Entropy(S)-plog2p-pΘlog2pΘ其中p是在S中正例的比例，pΘ是在S中负例的比例。在有关熵的所有计算中我们定义0log0为0。例子Entropy=1-(1/6)log(1/6)-(5/6)log(5/6)=0.650Entropy=1-(3/6)log(3/6)-(3/6)log(3/6)=1Entropy=-(0/6)log(0/6)-(6/6)log(6/6)=02.3性能度量——信息增益属性的信息增益使用这个属性分割样例而导致的期望熵降低的数量Values(A)是属性A所有可能值的集合

Sv

是S中属性A的值为v的子集，即Sv={sS|A(s)=v}当对S的一个任意成员的目标值编码时，Gain(S,A)值是在知道属性A的值后可以节省的二进制位数例子假设S是有关天气的训练样例集[9+,5-]其中：wind=weak的样例是[6+,2-]wind=strong的样例[+3,-3]问题:计算属性wind的信息增益S的熵：E(S)=-(9/14)log(9/14)–(5/14)log(9/14)=0.940选择最好的分类属性

3

决策树经典算法介绍ID3算法创建树的Root结点如果Examples都为正，那么返回label=+中的单结点Root如果Examples都为反，那么返回lable=-单结点树Root如果Attributes为空，那么返回单节点树Root，lable=Examples中最普遍的目标属性值否则开始

AAttributes中分类能力最好的属性

Root的决策属性A

对于每个可能值 在Root下加一个新的分支对应测试A=vi

令Example-vi为Examples中满足A属性值为vi的子集 如果Examples-vi为空 在这个新分支下加一个叶子结点，节点的lable=Examples中最普遍的 目标属性值 否则在这个新分支下加一个子树ID3(example-vi,target- attribute,attributes-|A|结束返回RootC4.5C4.5是对ID3的改进算法对连续值的处理对未知特征值的处理对决策树进行剪枝CARTCART是ClassificationAndRegressionTree的简称，可以处理高度倾斜或多态的数值型数据，也可处理顺序或无序的类属型数据。CART选择具有最小gini系数值的属性作为测试属性，gini值越小，样本的“纯净度”越高，划分效果越好。与C4.5算法类似，CART算法也是先建树后剪枝，但在具体实现上有所不同。由于二叉树不易产生数据碎片，精确度往往高于多叉树，因此CART算法采用2分递归划分，在分支节点上进行布尔测试，判断条件为真的划归左分支，否则划归右分支，最终形成一棵二叉决策树。对于连续属性A，判断A≤V是否成立(同C4.5算法)；对于离散型属性A，判断A∈S’是否成立，其中S’是属性A所有取值的子集，可用贪心算法或穷举法确定，SLIQ上述算法由于要求训练样本驻留内存，因此不适合处理大规模数据。为此，IBM研究人员提出了一种快速的、可伸缩的、适合处理较大规模数据的决策树分类算法SLIQ(SupervisedLearningInQuest)。该算法利用3种数据结构来构造树，分别是属性表、类表和类直方图。属性表含有两个字段：属性值和样本号。类表也含有两个字段：样本类别和样本所属叶节点。类表的第k条记录对应于训练集中第k个样本（样本号为k），所以属性表和类表之间可以建立关联。类表可以随时指示样本所属的划分，所以必须长驻内存。每个属性都有一张属性表，可以驻留磁盘。类直方图附属在叶节点上，用来描述节点上某个属性的类别分布。描述连续属性分布时，它由一组二元组<类别，该类别的样本数>组成；描述离散属性分布时，它由一组三元组<属性值，类别，该类别中取该属性值的样本数>组成。随着算法的执行，类直方图中的值不断更新。SPRINT与SLIQ算法不同，SPRINT算法采取传统的深度优先生成树策略，SLIQ算法要求类表驻留内存。当训练集增加导致类表放不进内存时，算法就无法进行，这限制了SLIQ处理数据的最大规模。为此，IBM研究人员提出可伸缩、可并行化的决策树算法SPRINT，它消除了所有内存限制，运行速度快，且允许多个处理器协同创建一个决策树模型。SPRINT定义了两种数据结构，分别是属性表和直方图。属性表由属性值、类别属性和样本号3个字段组成，它随节点的扩展而划分，并附属于相应的子节点。直方图附属在节点上，用来描述节点上某个属性的类别分布。当描述连续属性的类分布时，节点上关联两个直方图Cbelow和Cabove，前者描述已处理样本的类别分布，后者描述未处理样本的类别分布，两者的值皆随算法进行而更新；当描述离散属性的类分布时，节点上只关联一个直方图countmatrix。

4

决策树的应用4.1决策树的适用范围和应用前景决策树法作为一种决策技术，已被广泛地应用于企业的投资决策之中，它是随机决策模型中最常见、最普及的一种规策模式和方法此方法，有效地控制了决策带来的风险。所谓决策树法，就是运用树状图表示各决策的期望值，通过计算，最终优选出效益最大、成本最小的决策方法。决策树法属于风险型决策方法，不同于确定型决策方法，二者适用的条件也不同。应用决策树决策方法必须具备以下条件：①具有决策者期望达到的明确目标；

②存在决策者可以选择的两个以上的可行备选方案；

③存在着决策者无法控制的两种以上的自然状态（如气候变化、市场行情、经济发展动向等）；

④不同行动方案在不同自然状态下的收益值或损失值（简称损益值）可以计算出来；

⑤决策者能估计出不同的自然状态发生概率。决策树的应用举例问题及数据集根据其他属性，判断周六是否玩网球playTennis=Y/N?Step1:确定根节点分别计算4个属性的信息增益Outlook:0.246=Sunny[2+,3-]=Overcast[4+,0-]=Rain[3+,2-]Wind:0.048=weak的样例是[6+,2-]=strong的样例[+3,-3]Humidity:0.151Temperature:0.029因此：根节点为OutlookStep2:分枝选择哪个属性进行划分？Step3:循环选择哪个属性进行划分？

5

贝叶斯网络的形成与发展5.1贝叶斯网络贝叶斯网络是为了处理人工智能研究中的不确定性(uncertainty)问题而发展起来的。贝叶斯网络是将概率统计应用于复杂领域进行不确定性推理和数据分析的工具。用概率论处理不确定性的主要优点是保证推理结果的正确性。贝叶斯网络的发展历史1958年英国统计杂志

Biometrika

重新全文刊登了贝叶斯的论文。20世纪

50年代，以罗宾斯(RobbinsH.)为代表，提出了经验贝叶斯方法和经典方法相结合，引起统计界的广泛注意，这一方法很快就显示出它的优点，成为很活跃的一个方向。随着人工智能的发展，尤其是机器学习、数据挖掘等兴起，为贝叶斯理论的发展和应用提供了更为广阔的空间。贝叶斯理论的内涵也比以前有了很大的变化。20世纪

80年代贝叶斯网络用于专家系统的知识表示，90年代进一步研究可学习的贝叶斯网络，用于数据挖掘和机器学习。近年来，贝叶斯学习理论方面的文章更是层出不穷，内容涵盖了人工智能的大部分领域，包括因果推断、不确定性知识表达、模式识别和聚类分析等。并且出现了专门研究贝叶斯理论的组织和学术刊物ISBA。几个重要原理链规则(chainrule)贝叶斯定理(Bayes’theorem)利用变量间条件独立性

6

贝叶斯网络构造6.1贝叶斯网络的几个主要问题贝叶斯网络概率推理(ProbabilisticInference)结构学习(structurelearning)参数学习(Parameterlearning)隐变量及隐结构学习(Hiddenvariablesandhiddenstructurelearning)一个简单贝叶斯网络例子一个简单贝叶斯网络例子计算过程：P(y1)=P(y1|x1)P(x1)+P(y1|x2)P(x2)=0.9*0.4+0.8*0.6=0.84P(z1)=P(z1|y1)P(y1)+P(z1|y2)P(y2)=0.7*0.84+0.4*0.16=0.652P(w1)=P(w1|z1)P(z1)+P(w1|z2)P(z2)=0.5*0.652+0.6*0.348=0.5348P(w1|y1)=P(w1|z1)P(z1|y1)+P(w1|z2)P(z2|y1)=0.5*0.7+0.6*0.3=0.53P(w1|y2)=P(w1|z1)P(z1|y2)+P(w1|z2)P(z2|y2)=0.5*0.4+0.6*0.6=0.56P(w1|x1)=P(w1|y1)P(y1|x1)+P(w1|y2)P(y2|x1)=0.53*0.9+0.56*0.1=0.533

该计算利用向上概率传播及贝叶斯定理。

为什么要用贝叶斯网络进行概率推理？理论上，进行概率推理所需要的只是一个联合概率分布。但是联合概率分布的复杂度相对于变量个数成指数增长，所以当变量众多时不可行。贝叶斯网络的提出就是要解决这个问题。它把复杂的联合概率分布分解成一系列相对简单的模块，从而大大降低知识获取和概率推理的复杂度，使得可以把概率论应用于大型问题。统计学、系统工程、信息论以及模式识别等学科中贝叶斯网络特里的多元概率模型：朴素贝叶斯模型，隐类模型，混合模型，隐马尔科夫模型，卡尔曼滤波器等。动态贝叶斯网络主要用于对多维离散时间序列的监控和预测。多层隐类模型，能够揭示观测变量背后的隐结构。例子P(C,S,R,W)=P(C)P(S|C)P(R|S,C)P(W|S,R,C)chainrule=P(C)P(S|C)P(R|C)P(W|S,R,C)since=P(C)P(S|C)P(R|C)P(W|S,R)since贝叶斯网络学习1.结构学习：发现变量之间的图关系，2.参数学习：决定变量之间互相关联的量化关系。6.2结构学习算法算法：K2:通过为每个结点寻找父结点集合来学习贝叶斯网络结构。它不断往父结点集中添加结点，并选择能最大化数据和结构的联合概率的结点集。HillClimbing

(operators:edgeaddition,edgedeletion,edgereversion)从一个无边结构开始，在每一步，它添加能最大化BIC的边。算法在通过添加边不能再提高结构得分时停止。缺值数据结构学习：StructuralEMSEM不是每次迭代都同时优化模型结构和参数，而是先固定模型结构进行数次参数优化后，再进行一次结构加参数优化，如此交替进行。目的：减小计算复杂度。参数学习算法1.最大似然估计完全基于数据，不需要先验概率2.贝叶斯估计假定在考虑数据之前，网络参数服从某个先验分布。先验的主观概率,它的影响随着数据量的增大而减小。3.缺值数据最大似然估计：EM算法（迭代算法）a.对数据进行修补，使之完整(E-step)b.修补后的完整数据计算的最大似然估计(M-Step)隐结构模型学习隐变量是取值未被观察到的变量。通过数据分析：1隐变量的个数2隐结构3隐变量的势4模型参数方法：基于评分函数的爬山法G是一个隐变量模型，D是一组数据。θ是G的参数的某一个最大似然估计，是G的有效维数。隐变量势学习爬山算法隐结构学习双重爬山算法

7

典型贝叶斯网络学习方法及其扩展7.1贝叶斯网络应用医疗诊断，工业，金融分析，计算机（微软Windows,Office）模式识别：分类，语义理解军事（目标识别，多目标跟踪，战争身份识别等）生态学，生物信息学（贝叶斯网络在基因连锁分析中应用）编码学，分类聚类，时序数据和动态模型7.2贝叶斯网络模型的扩展1.在复杂关系数据中的扩展

关系数据是实际中最常见的数据存储形式之一,但是标准贝叶斯网络只能处理具有单一表的二维平面数据,而对于多表中的多维关系数据则无能为力.在贝叶斯网络的框架下,出现了能够处理多维关系数据的方法,其中最具代表性的为概率关系模型(PRMs).2.在迭代反馈过程中的扩展

很多实际问题中存在循环、反馈以及因素之间互为因果关系等现象.例如,商品的市场价格影响库存量,库存量影响供给量,反过来供给量又会影响市场价格.标准贝叶斯网络具有无环的限制,不能对这种具有迭代和反馈过程的领域进行建模.有环贝叶斯网络(CBN)突破了这个限制,继承了贝叶斯网络描述非确定性逻辑关系的能力,适于处理该类问题.3.在时变系统中的扩展

许多随机现象都涉及一些随时间变化的随机变量,如股票指数的变化、语音的产生以及连续变化的视觉图像等.标准贝叶斯网络只能对静态系统进行建模.为了能够对此类动态时变随机过程进行表达和推理,引入了动态贝叶斯网络(DBN).7.3未来的研究方向1.核方法能够处理高维特征空间,且有很强的泛化性,这与概率方法的特点互补.当前应用核方法对贝叶斯网络的研究限于如何提高贝叶斯网络的数据分析能力.利用核方法的特点,探索高效率的建模方法是值得进一步研究的问题.2.代数方法具有独特的理论优势,应用代数方法研究贝叶斯网络是对数值方法的补充和扩展.目前的研究主要包括贝叶斯网络等价类的代数特征和贝叶斯网络的代数表示.除了进一步研究构建贝叶斯网络更有效的代数方法,还可以应用代数方法探索贝叶斯网络中的概率推理问题.3.高效快速的实时推理算法.在有些计算量很大的贝叶斯网络的推理过程中,要求在任一截止时刻都能得到一个近似结果,鉴于这个实际应用的要求,产生了实时推理算法。基于搜索的算法和抽样算法等都属于这类算法,但这些算法都或多或少的存在收敛很慢,或者无法分析精度等问题,因而有必要研究有效的实时推理算法来解决上述问题.

总结与展望8总结与展望•

本章首先介绍了决策树算法，分析了它们目前主要的代表理论以及存在的问题，并举出了利用基于信息论的决策树算法应用实例。种决策树算法之间的主要区别就是对这个“差异”衡量方式的区别。•对具体衡量方式算法的讨论超出了本文的范围，在此我们只需要把切分看成是把一组数据分成几份，份与份之间尽量不同，而同一份内的数据尽量相同。这个切分的过程也可称为数据的“纯化”。

决策树常见的批评是说其在为一个节点选择怎样进行分割时使用“贪心”算法。此种算法在决定当前这个分割时根本不考虑此次选择会对将来的分割造成什么样的影响。换句话说，所有的分割都是顺序完成的，一个节点完成分割之后不可能以后再有机会回过头来再