《数据挖掘基础及其应用》课件第6章

第6章分类Ⅲ:概率分类与回归6.1引言6.2贝叶斯公式6.3贝叶斯分类算法6.4贝叶斯信念网络6.5回归分析本章小结

6.1引言

决策树是一种描述对实例进行分类的树形结构。决策树具有速度快、分类结果可解释性高等优势,但是决策树算法存在如下几个方面的缺陷:(1)过拟合导致剪枝问题。(2)算法鲁棒性低,导致决策树的结果可能是不稳定的,因为在数据中一个很小的变化可能导致生成一个完全不同的树,这个问题可以通过使用集成决策树来解决。

(3)NP难问题:学习一个最优决策树是NP难问题。

(4)一些概念是很难理解的:比如异或校验或复用的问题。

(5)准确性得不到保障。

决策树算法的缺陷如图6-1所示。图6-1决策树算法的缺陷

若要有效地避免决策树算法带来的缺陷,则需要构建全新的算法。通过提供图形化的方法来表示和运算概率知识,贝叶斯网络克服了基于规则的系统在概念和计算上的困难。

贝叶斯网络与统计方法相结合,使得其在数据分析方面拥有了许多优点,具体如下:

(1)图形方法描述数据间的相互关系,语义清晰,易于理解。

(2)易于处理不完备数据集。

(3)允许学习变量间的因果关系。

(4)充分利用领域知识和样本数据的信息。

6.2贝叶斯公式

6.2.1概率基础概率论具有坚实的数学理论基础,是数据挖掘领域中处理不确定性问题的基础理论之一,也是目前处理不确定性问题的方法之一。

定义6.1(条件概率)设A,B是两个基本事件,且P(A)>0,则称

为事件A发生的条件下事件B发生的条件概率。

定义6.2(先验概率)设B1,B2,…,Bn为样本空间S中的事件,P(Bi)可根据以前的数据分析得到,或根据先验知识估计获取,称P(Bi)为先验概率。

先验概率是根据历史资料或主观判断所确定的各种事件发生的概率,该概率没有经过实验证实,属于检验前的概率。先验概率一般分为两类:一类是客观先验概率,是指利用过去的历史资料计算得到的概率;另一类是主观先验概率,是指在无历史资料或者历史资料不全时,只凭借人们的主观经验来判断取得的概率。

定义6.3(后验概率)设B1,B2,…,Bn为样本空间S中的事件,则事件A发生的情况下,Bi发生的概率P(Bi

A)可根据先验概率P(Bi)和观测信息重新修正和调整后得到,通常将P(Bi

A)称为后验概率。

后验概率一般是指利用贝叶斯公式,结合调查等方式获取了新的附加信息,对先验概率加以修正的更符合实际的概率,即得到信息之后再重新修正的概率。

定义6.4(联合概率)设A,B为两个事件,且P(A)>0,则它们的联合概率为

联合概率也称为乘法公式,是指两个任意时间的乘积的概率,或称为交事件的概率。

定义6.5(全概率公式)如果影响事件A的所有因素B1,B2,…,Bn满足Bi·Bj=φ(i≠j),并且P(Bi)>0,则

定义6.6(贝叶斯概率)贝叶斯概率是观测者对某一事件发生的相信程度。观测者根据先验知识和现有的统计数据,用概率的方法来预测未知事件发生的可能性。贝叶斯概率

不同于事件的客观概率,客观概率是在多次重复实验中事件发生频率的近似值,而贝叶斯概率则是利用现有的知识对未知事件的预测。

定义6.7(贝叶斯公式)贝叶斯公式也称为后验概率公式,或者逆概率公式,其用途很广。设先验概率为P(Bi),调查所获得的新附加信息为P(A|Bi

),其中i=1,2,…,n,则后验概率为

定义6.8(条件独立)对概率模式M,A、B和C是U的三个互不相交的变量子集,如果对∀x∈A,∀y∈B和∀z∈C,都有p(x|y,z)=p(x|z),其中p(y,z)>0,称给定C时A和B条件独立,记为I(A,C,B)M。

条件独立性在某些文献中定义为p(x,y|z)=p(x|z)p(y|z),可以证明这两个定义是等价的。

定义6.9概率分类中{X1,X2,…,Xn,C}是样本空间T的属性集。其中,Xi(i=1,2,…,n)是特征属性,C是类属性。Xi

可能是离散变量,也可能是连续变量。xi和c分别表示属性Xi

和C的任意取值。

定义6.10P(•)表示离散的概率值,p(•)表示连续的概率密度函数值。Count(•)表示样本空间的大小。

6.2.2图论基础

定义6.11(有向图G)由节点集V、边集E表示的二元组G=G(V,E),若(x,y)∈E表示从节点x到节点y有一条有向边,我们也称节点x和节点y是邻接的或x和y相互为邻居。x也叫作y的父节点,y叫作x的子节点。通过父亲和孩子概念的递归定义,同时获得了祖先和后继两个概念。没有父节点的节点被称为根节点。

定义6.12(路径)在贝叶斯网络学习中,连接两个节点的路径不考虑这条路径中边的方向,这个定义对有向图、无向图和混合图都是适用的。

定义6.13(有向循环图)有向循环图(DirectedAcyclicGraph,DAG)也称有向无环图,即不包含环路的有向图,如图6-2所示。

定义6.14(汇聚节点)对于一条邻接路径中的任何一个节点v,如果有(x,v)∈E并且(y,v)∈E,则称v为汇聚节点或碰撞节点(Collider)。图6-2有向无环图

6.2.3信息理论

定义6.15(信息熵)设信源X为离散随机变量,则用来度量X的不确定性的信息熵为

定义6.16(联合信息熵)设X、Y为离散随机变量,则用来度量二元随机变量不确定性的联合信息熵H(X,Y)为

定义6.17(条件信息熵)用来度量在得到随机变量Y的信息后,随机变量X仍然存在的不确定性。条件信息熵H(X|Y)为

定义6.18(互信息)用来描述随机变量Y提供的关于X的信息量的大小,随机变量X、Y之间的互信息为

定义6.19(条件互信息)在已知Y的前提下,随机变量X和Z之间的条件互信息定义为

从条件互信息可以看出,在给定测试集的条件下,如果X和Z一致性条件独立时,即P(x;z|y)=P(x|y)P(z|y)成立,则X和Z之间的条件互信息为0。当I(X;Z)小于某个极限值ε时,称X和Z为边际独立;当I(X;Z|Y)小于某个极限值ε时,称X和Z为条件独立。X和Z之间的条件互信息越大,则说明在给定观测集的条件下,X和Z之间的概率依赖性越明显。反映在贝叶斯网络上,如果Y为X的父节点集合,则当X和Z之间的条件互信息较大时,说明Z也可能是X的父节点,其关系如图6-3所示。图6-3互信息与信息熵关系图

6.3贝叶斯分类算法

6.3.1算法原理贝叶斯网络的原理是利用贝叶斯公式构建依赖关联网络进行分类。通常,事件X在事件Y(发生)的条件下的概率,与事件Y在事件X的条件下的概率是不一样的。但这两者有确定的关系,贝叶斯法则就是这种关系的陈述。

贝叶斯法则是关于随机事件X和Y的条件概率和边缘概率,即

式中:P(X|Y)是在Y发生的情况下X发生的可能性。贝叶斯法则可描述为

其解释为后验概率=似然度×先验概率/标准化常量。也就是说,后验概率与先验概率和似然度的乘积成正比。P(

X|Y)/P(X)有时也被称作标准似然度(Standardized

Likelihood),贝叶斯法则又可表述为:后验概率=标准似然度×先验概率。

例如,如果事先已知脑膜炎导致斜颈的概率是0.5,一个病人患有脑膜炎的先验概率是1/50000,病人患有斜颈的先验概率是1/20,那么在已知一个病人患有斜颈的情况下,他患脑膜炎的概率是多少?

构建贝叶斯网络的关键在于如何分解任务,给定训练数据。如图6-4所示,预测一个贷款者是否会拖欠还款,其训练集有如下属性:是否有房、婚姻状况和年收入。拖欠还款的贷款者属于类“是”,还清贷款的贷款者属于类“否”。贝叶斯公式分类的关键问题是:随机变量是什么?目标变量是什么?目标是什么?先验概率如何计算?条件概率如何计算?图6-4贝叶斯网络构建的主要问题

从数据中估计后验概率是贝叶斯分类算法的一个难点,要估计后验概率,可利用贝叶斯网络将后验概率转化为先验概率与条件概率之积:

(1)变量确定问题:将属性(包括类别属性)都看成随机变量,其中属性变量可表示为(X1,X2,…,Xd),类别属性可表示为Y。

(2)目标确定问题:最大化后验概率P

(Y|X1,X2,…,Xd)。

(3)难点:如何从数据中估计后验概率P

(Y|X1,X2,…,Xd)。

贝叶斯网络推理过程如图6-5所示,假设给定已测试记录有如下属性集:X=(有房=否,婚姻状况=已婚,年收入=12万元)。要分类该记录,我们需要利用训练数据中的可用信息计算后验概率P(拖欠贷款=是|X)和P(拖欠贷款=否|X)。如果P(拖欠贷款=是|X)>P(拖欠贷款=否|X),那么记录分类为是;反之,分类为否。

要估计后验概率,可利用贝叶斯网络将后验概率转化为先验概率与条件概率之积,即

由于分母是固定值,所以上式等价于最大化图6-5贝叶斯网络推理过程

6.3.2朴素贝叶斯算法

朴素贝叶斯分类器在估计类条件概率时的前提假设是:属性之间条件独立,即

式中:每个属性集X={X1,X2,…,Xd}包含d个属性。

分类测试记录时,朴素贝叶斯分类器对每个类Y计算后验概率:

由于对于所有的Y,P(X)都是固定的,因此只要找出使分子

最大的类就足够了。下面描述几种估计分类属性和连续属性的条件概率P

(Xi|Y)的方法。规约朴素贝叶斯分类任务和目标为:

目标:主要目标是估计先验概率与条件概率P(Yj),P

(Xi|Yj

);

任务:新数据对象如何分类?只需计算P(Yj

)P

(Xi|Yj)。

例如,给定如下数据,对于图6-5给定的问题,构建朴素贝叶斯网络可分三步骤:首先利用贝叶斯公式进行转换(如图6-6所示),其次利用数据估计条件概率与先验概率(如图6-7所示),最后利用贝叶斯网络推理概率(如图6-8所示)。图6-6-朴素贝叶斯网络构建步骤1

对于分类属性Xi,根据类Yj

中属性值等于Xi的训练实例的比例来估计条件概率P(Xi|Y=Yj

)。例如,在图6-6中,还清贷款的7个人中3个人有房,因此条件概率P(有房=是|否)=3/7。同理,拖欠贷款的人中单身的条件概率P(婚姻状况=单身|是)=2/3。

注意:上述方法的缺陷在于只能针对离散的属性进行先验概率估计与条件概率估计,如果属性值是连续值,则通常采用两类方法:

一是离散化

二是概率密度函数估计图6-7朴素贝叶斯网络构建步骤2１

如何解决极端情况:即通常数据不完备、样本量少所造成的先验知识为0的情况,这时的后验概率难以预测,如图6-9所示。图6-9朴素贝叶斯在极端情况下不能有效预测

如何有效解决这类极端问题?可以通过以下方式重新估计先验概率

问题1:朴素贝叶斯分类器算法的优点和缺点是什么?

提示:从原理、推理方法等方面考虑。

朴素贝叶斯网络的特点是:一个中心、三大优势、四项缺点。

一个中心:条件独立性

三大优势:

•朴素贝叶斯模型发源于古典数学理论,有稳定的分类效率;

•对小规模的数据表现很好,能处理多分类任务,适合增量式训练,尤其是数据量超出内存时;

•对缺失数据不太敏感,算法简单。

四项缺点:

•理论上,与其他分类方法相比,朴素贝叶斯模型具有最小的误差率。

•需要知道先验概率,且先验概率很多时候取决于假设,而假设的模型可以有很多种。

•通过先验概率和数据来决定后验的概率从而决定分类,所以分类决策存在一定的错误率。

•对输入数据的表达形式很敏感。

6.3.3算法应用

1.第一阶段:确定特征属性及划分

确定分类随机变量:设C=0表示真实账号,C=1表示不真实账号。这一步要找出可区分真实账号与不真实账号的特征属性,在实际应用中,特征属性的数量是很多的,划分也会比较细致,但这里为了简单起见,我们使用少量的特征属性以及较粗的划分。

选择特征:选择如表6-1所示的三个特征属性。

获取训练样本:人工检测过的1万个账号作为训练样本。

2.第二阶段:模型构建

获取先验概率:用训练样本中真实账号和不真实账号的数量分别除以1万,即

获取条件概率:每个类别条件下各个特征属性划分的频率如图6-10所示。图6-10每个类别条件下各个特征属性划分的频率

3.第三阶段:分类应用

使用上面训练得到的分类器鉴别一个账号,这个账号日志数量与注册天数的比率a1为0.1,好友数与注册天数的比率a2为0.2,使用非真实头像a3=0。

朴素贝叶斯分类如下:

6.4贝叶斯信念网络

6.4.1定义与推理(1)真实账号比非真实账号平均具有更大的日志密度、更大的好友密度,以及更多地使用真实头像。(2)日志密度、好友密度和是否使用真实头像在账号真实性给定的条件下是独立的。

为了获取更准确的分类,可以将假设修改如下:

(1)真实账号比非真实账号平均具有更大的日志密度、更大的好友密度,以及更多的地使用真实头像。

(2)日志密度与好友密度、日志密度与是否使用真实头像在账号真实性给定的条件下是独立的。

(3)使用真实头像的用户比使用非真实头像的用户平均有更大的好友密度。

对于图6-11所示的两个数据集,利用朴素贝叶斯分类器都不能有效分类(图中点代表数据对象,同一形状的数据对象隶属于同一类),其原因在于条件概率假设的前提不能成立,因此需要更复杂、更有力的工具来刻画与描述数据之间的关系。图6-11非条件独立数据

贝叶斯网络有两个主要成分:有向无环图和概率表。

(1)有向无环图(DirectedAcyclicGraph,DAG)表示变量之间的依赖关系。考虑三个随机变量A、B和C,其中A和B相互独立,并且都直接影响第三个变量C。三个变量之间的关

系可以用图6-12(a)中的有向无环图概括。图中每个节点表示一个变量,每条弧表示两个变量之间的依赖关系。如果从X到Y有一条有向弧,则X是Y的父母,Y是X的子女。另外,如果网络中存在一条从X到Z的有向路经,则X是Z的祖先,而Z是X的后代。例如,在图6-12(b)中,A是D的后代,D是B的祖先,而且B和D都不是A的后代节点。图6-12使用DAG表示变量之间的依赖关系

贝叶斯网络的一个重要性质表述如下:

性质6.1(条件独立)贝叶斯网络中的一个节点,如果它的父母节点已知,则它条件独立于它的所有非后代节点。

(

2)每个属性一个条件概率表(ConditionalProbabilityTable,CPT),该表把各节点和它的直接父节点关联起来。DAG包含两类节点,一类是无父节点,一类是有父节点。第一类节点所对应的概率是先验概率,第二类节点对应的是条件概率,如图6-13所示。

给定贝叶斯信念网络,可采用联合概率推理方式进行推理,即图6-13DAG包含的两类节点

图6-14是贝叶斯网络的一个例子,用于对心脏病患者建模。假设图中每个变量都是二值的。心脏病节点(HD)的父母节点对应于影响该疾病的危险因素,如运动(E)和饮食(D)等。心脏病节点的子节点对应于该病的症状,如胸痛(CP)和高血压(BP)等。如图6-14所示,心脏病(HD)可能源于不健康的饮食,同时又可能导致胸痛。图6-14贝叶斯信念网络示意图

图6-15贝叶斯信念网络概率推理过程

6.4.2结构学习(网络构建)

贝叶斯信念网络的建模包括两个步骤:

①创建网络结构;

②估计每一个节点概率表中的概率值,可以通过最大化后验概率获取最佳的贝叶斯网络。

网络拓扑结构可以通过对主观的领域专家知识编码获得。

例如,考虑图6-14中的变量执行算法6.1的步骤1后,设变量次序为(E,D,HD,CP,BP)。从变量D开始,经过步骤2到步骤7,得到如下的条件概率:

当模型很复杂时,使用枚举式的方法来求解概率就会变得非常复杂且难以计算,因此必须使用其他的替代方法。一般来说,有以下几种求法:

(1)精确推理,包括枚举推理法、消元算法(VariableElimination)。

(2)近似推理,包括蒙特卡洛方法、直接取样算法、拒绝取样算法、概率加权算法。

一般而言,推估网络的结构会比推估节点上的参数要困难。依照对贝叶斯网络结构的了解和观测值的完整与否,分别讨论下面两种情况:

1.结构已知,观测值完整

此时可以用最大似然估计法(MaximumLikelihoodEstimation,MLE)来求得参数。其

对数概率函数为

以图6-16为例,假设有两个服务器(S1,S2),会传送数据包到用户端(以U表示),但是第二个服务器的数据包传送成功率与第一个服务器传送成功与否有关,因此贝叶斯网络的结构图可以表示成图6-16的形式。就每个数据包传送而言,只有两种可能值:T(成功)或F(失败)。我们可以求出节点U的最大似然估计式为

根据该式,就可以借观测值来估计出节点U的条件分配。当模型很复杂时,可能需要利用数值分析或其他最优化技巧来求出参数。图6-16-服务器与客户端传送贝叶斯网络的结构图

2.结构已知,观测值不完整(有遗漏数据)

EM算法的步骤如下:

(1)首先给定待估参数一个初始值,然后利用此初始值和其他的观测值,求出其他未观测到节点的条件期望值,接着将所估计出的值视为观测值,并将完整的观测值带入此模型的最大似然估计式中,如下所示(以图6-16为例):

式中:EN(x)代表在目前的估计参数下,事件x的条件概率期望值,即

(2)最大化此最大似然估计式,求出此参数最有可能的值,并重复步骤(1)与(2),直到参数收敛为止,即可得到最佳的参数估计值。

6.4.3贝叶斯信念网络的特点

贝叶斯信念网络模型的一般特点如下:

(1)贝叶斯信念网络提供了一种用图形模型来捕获特定领域的先验知识的方法。该网络还可以用来对变量间的因果依赖关系进行编码。

(2)构造网络可能既费时又费力,然而一旦网络结构确定下来,添加新变量则会十分容易。

(3)贝叶斯网络很适合处理不完整的数据。对于有属性遗漏的实例,可以通过对该属性的所有可能取值的概率求和或求积分来加以处理。

(4)因为数据和先验知识以概率的方式结合起来了,所以该方法对模型的过拟合问题是非常鲁棒的。

6.5回归分析

回归是一种预测建模技术,其中被估计的目标变量是连续的。回归应用的例子包括:使用其他经济学指标预测股市指数,基于高空气流特征预测一个地区的降水量,根据广告开销预测公司的总销售,按照有机物质中的碳14残留估计化石的年龄。

6.5.1预备知识

令D是包含N个观测的数据集,D={(xi,yi)|i=1,2,…,N}。xi对应于第i个观测的属性集,xi=(xi1,xi2,…,xid)是向量,又称说明变量(ExplanatoryVariable),而yi对应于目标变量(TargetVariable)或因变量。回归任务的说明属性可以是离散的或连续的。

定义6.20(回归,Regression)一个任务,它学习一个把每个属性集x映射到一个连续值输出y的目标函数f。

回归的目标是找到一个以最小误差拟合输入数据的目标函数。回归任务的误差函数(ErrorFunction)可以用绝对误差或平方误差和表示:

6.5.2线性回归

考虑表6-2和图6-17所示的生理学数据。该数据对应于热通量和一个人睡眠时皮肤温度的测量。假设我们希望根据热传感器收集的热通量测量值预测一个人的皮肤温度,二维散点图表明这两个变量之间存在很强的线性关系,即“线性回归”(Linear