基于贝叶斯网络的数据挖掘方法

文章编号:1006-9348(2008)02-0087-03

计　算　机　仿　真

2008年2月　　

基于贝叶斯网络的数据挖掘方法

李艳美,张卓奎

(西安电子科技大学理学院,陕西西安710071)

摘要:常用的数据挖掘方法有许多,贝叶斯网络(BayesianNetworks,BN)方法在数据挖掘中的应用是当前研究的热点问题。贝叶斯网络是一种进行不确定性推理和知识表示的有力工具,当与统计方法结合使用时,显示出许多关于数据处理的优势。首先介绍了BN的定义、方法的优点以及目前网络学习的各种算法,最后用一个实际中的案例进行试验,指出了在数据挖掘技术中的具体应用。得到了将贝叶斯网络应用于数据挖掘当中,充分挖掘数据的隐含信息和内在本质,具备良好地预测能力等优点,实验证明这种方法实用、有效。

关键词:贝叶斯网络;数据挖掘;条件概率分布;条件独立性中图分类号:TP181;TP301　　文献标识码:A

DataMiningBasedonBayesianNetworksLIYan-mei,ZHANGZhuo-kui(SchoolofScience,XidianUniv.XiπanShanxi710071,China)

ABSTRACT:Manymethodshavebeenusedindatamining,Bayesiannetworksbecomeafocuscurrently.

Itisa

powerfultoolandcanbeusedtodouncertaininference.Whenusedinconjunctionwithstatisticaltechniques,Bayes2iannetworkshaveseveraladvantagesfordatamodeling.ThispapermainlydiscussesthedefinitionofBayesiannet2works,theadvantagesofthemethodsandthealgorithmsoflearningnetworks.Aninstanceispresentedtoindicatetheapplicationsindataminingtechnologyfinally.Bayesiannetworkscanminethehiddeninformationandinherenthypostasis,andhavemanyadvantagessuchastheabilityoffavorableforecast.Theexperimentationprovesitspracti2calityandavailability.

KEYWORDS:Bayesiannetworks(BN);Datamining;Conditionalprobabilitydistribution;Conditionalindepend2ency

1　引言

随着计算机硬件和软件的飞速发展,尤其是数据库技术与应用的日益普及,人类正面临着“数据海洋”的困惑。如何有效地利用和处理大量的数据即通过分析数据对象之间关系提取隐含在数据中的知识,成为广大信息技术工作者所关注的焦点。正是在这种背景下,数据挖掘技术应运而生。

数据挖掘(DataMinine,DM)是一门新兴的交叉学科,涉及到数据库技术、人工智能、知识工程、统计学、机器学习、优化计算和专家系统等领域。从本质上来说,数据挖掘是智能信息处理的一种过程或技术,它在对大量数据实例全面而深刻认识的基础上,通过计算、归纳和推理等环节,从中抽取普

基金资助:国家自然科学基金资助课题(70371031),国家自然科学基金资助课题(70373046)

收稿日期:2006-12-12　修回日期:2007-01-07

遍的、一般的和本质的现象或特征。常用的方法有决策树、

遗传算法、贝叶斯网络、粗糙集、神经网络等。其中决策树的优点是可理解性,很直观,主要用于分类和归纳挖掘,但在数据量较大和数据复杂的情况下,该算法则显得力不从心;遗传算法擅长于数据聚类,在组合优化问题上具有独特的优势。粗糙集在数据挖掘中具有重要的作用,常用于处理含糊性和不确定性的问题,以及特征归纳和相关分析,运用粗糙集进行数据预处理可以提高知识发现的效率。神经网络能够对复杂问题进行预测,它在商业界得到广泛的应用,对于信贷客户识别、股票预测和证券市场分析等方面具有良好的效果。贝叶斯网络具有分类、聚类、预测和因果分析等功能,易于理解,预测效果较好,面对大规模数据时显示出它独特的优势。本文主要介绍贝叶斯网络方法、特点以及它在数据挖掘中的优势,然后用一个实例具体阐述其在数据挖掘中的应用。

—87—

表1　有关肺癌(LC)值的条件概率表(CPT)

2　贝叶斯网络

贝叶斯网络(Bayesiannetworks),是伴随着影响图(influ2

encediagram)而发展起来的一类决策分析工具,它提供了不确定性环境下的知识表示、推理、学习手段,可以完成决策、诊断、预测、分类等任务,已广泛应用于语音识别、工业控制、经济预测、医疗诊断等。近几年来,在数据挖掘中的应用则为贝叶斯网络开辟了一个新的研究空间。211　贝叶斯网络的定义

贝叶斯网络(BN)是一个有向图,其中每个节点都标注了定量的概率信息,其完整的详细描述为:①一个随机变量组成网络节点,变量可以是离散的或是连续的;②一个连接节点对的有向边或箭头集合,如果存在从节点X指向节点Y的有向边,则看成X是Y的父节点;③每个节点Xi都有一个条件概率分布P(Xiparents(Xi)),量化其父节点对该节点的影响;④图是一个有向无环图,缩写为DAG。

贝叶斯网是概率信息的载体,是联合概率分布的图形表现形式。一个贝叶斯网络通常有两部分组成:第一部分是有向无环图,其每一个节点代表一个随机变量,而每条弧代表一个概率依赖;第二部分是每个属性一个条件概率表(CPT).图1给出了6个布尔变量的简单贝叶斯网络[5],弧表示因果知识,例如,得肺癌受吸烟的影响,也受家族肺癌史的影响。此外,该弧还表明,给定其双亲家族肺癌史(FH)和吸烟(S),变量肺癌(LC)条件独立于肺气肿(E),这意味着,一旦家族肺癌史(FH)和吸烟(S)的值已知,变量肺气肿(E)并不提供关于肺癌(LC)的附加信息。表1则给出了肺癌(LC)的CPT,对于其双亲节点家族肺癌史(FH)和吸烟(S)的每个可能组合,表中给出了LC的每个值的条件概率,如表1所示。如:P(LC=\"no\"FH=\"no\",S=\"yes\")=0.5。

LC

FH,S　FH,～S～FH,S　015　015

～FH,～S　012　018

　017　013

　014　016

～LC

212　贝叶斯网络的学习

在近几年中,研究者们对于网络学习问题大致有两种方

法:一种是基于相关性分析的算法(DependencyAnalysisAp2

proach),另一种是基于搜索和评分的算法(Search&Scoringbasedalgorithm)

1)基于相关性分析的算法

这种算法主要是寻找变量之间的依赖关系,然后依据从数据中获得的这种依赖关系推导出贝叶斯网络的结构,这种依赖关系是通过条件独立性测试(CI)获得的。

2)基于搜索和评分的算法这类算法主要是搜索一个最适合原始数据的结构,一般采用启发式的搜索方法,为了减小搜索空间,一般要求首先对贝叶斯网络的结点进行排序。这类算法以一个没有边的图开始,通过某一种搜索方法找到一条边并加入到图中,然后运用一定的评分方法判断新图是否比旧图更符合数据。如果是,则将该边加入图中,并继续同样的步骤直到没有新的图比旧图更优。

213　贝叶斯网络方法优点:

1)贝叶斯网络的学习机制高效灵活,可以发现潜在有

用的模式或关系,实现对数据实例的分类、聚类和预测,还可以处理不完整和带有噪声的数据集。

2)贝叶斯网络用图形的方法描述数据间的相互关系,语义清晰,易于理解和接受,同时也具有良好的预测能力。

3)由于贝叶斯网络具有因果和概率性语义,可以有机地结合先验知识和样本数据,将主观和客观有机地结合起来,更加全面客观地反映数据对象内在的联系与本质。

4)贝叶斯网络可以有效的避免对数据的过渡拟合。

3　数据挖掘技术

311　贝叶斯网络的数据挖掘思想

1)确定需要哪些变量描述该领域,以及每个变量的确切

含义。

2)确定网络结构。根据先验知识,对于有n个变量的数据样本,可能组成的网络结构有n!种,要对每一个网络结构进行计算是不可能的.利用现有的专家知识,就可以排除

图1　一个贝叶斯网络的结构示意图

对应于属性或变量X1,X2,…,Xn的任意元组(X1,X2,…,Xn)的联合概率由下式计算P(X1,X2,…,Xn)=∏P(Xi

i=1n

大量的不合理的结构,获得该领域的网络结构。

3)确定条件概率分布函数。当数据集完整时,概率参数学习一般有两种方法:一是经典的样本统计法,二是贝叶斯统计法;当数据集不完备时,一般采用近似计算的方法,近似求出似然函数的极大值,并将该点的参数作为估计值,常用的有EM算法、梯度上升算法及蒙特卡洛方法、高斯等方法。通过由专家确定的网络结构中每个变量的条件概率分布函

parents(Xi))其中P(Xiparents(Xi))的值对应于Xi的CPT

中的值。

—88—

数,量化变量之间的依赖关系。

4)利用表中的数据,优化贝叶斯网络,经过计算和分析,调整贝叶斯网络的网络结构和各变量的条件概率分布函数。312　实验结果

通过对某地区的大学毕业生考研情况进行调查,找出以下几个变量因素对他们是否继续深造产生影响:

・性　　别(A):男、女・智　　商(B):低、中等偏下、中等偏上、高・家庭经济(C):差、中等偏下、中等偏上、优

・就业形势(D):坏、好

・是否打算上研究生(E):是、否

表2是对10000名大学生的统计结果,共计128个数据。表2中的第1行第1格数据表示A=男,B=低,C=差,D=坏,E=是的个数为3,第1行第2格数据表示A=男,B=低,C=差,D=坏,E=否的个数为331,…,依此类推,在表2的下半部分(即5～8行),A的取值都为女。

表2　对10000名大学生不同状况的人数统计结果

性别男

3176

3312411654646028316147

1327474939293640

6584915744617260

11765519137依据上述原则对大学生不同状况的统计人数

10520112047312236193743164741231447751086295110904788907812121798151213

119115924111616417445

3893148224206291123

649210065358510087

101761713212516

67794217961138149

351191984142872142348

4151684324457689

女41065

　　构造贝叶斯网络找出这些变量之间的因果关系用于数据挖掘,具体构造网络的过程如下:确定变量为性别(A),智商(B),家庭经济(C),就业形势(D),是否打算上研究生(E);根据现有的专家知识我们只选择了最有可能的a和b两种网络结构。它们的区别是学生的就业形势与家庭经济的因果关系不同,智商和家庭经济的因果关系不同.如图2所示。

313　结果分析

对于上案例,用决策树方法重新对数据进行分析,得到的结果与贝叶斯网络方法进行比较,如图3所示为贝叶斯网络方法与决策树方法应用于案例的学习曲线。从决策树方法学习曲线来看大约在人数5000人之前,在测试集上的比例数值总体是增大的,但超过5000人时正确的比例随着人数的增加而减少,表明决策树在数据量较大和数据复杂的情况下,该算法显得力不从心,性能也越来越差。而贝叶斯网络方法学习曲线随着人数的增加,正确的比例在一直加大,当到达7000人左右时,比例数值开始趋向于1,性能越来越好。得到在数据量较大时,贝叶斯网络方法要优于决策树方法。贝叶斯网络具有因果和概率性语义,可以有机地结合先验知识和样本数据,将主观和客观有机地结合起来,表达清晰,因此能更加全面客观地反映数据对象内在的联系与本质,便于实现对数据的挖掘。经过反复验证,该结论具有普遍适用性。

图2　两个最有可能的网络结构a和b

4　结束语

由于贝叶斯网络(BayesianNetworks,BN)具有诸多的优

点,近年来已经成为数据挖掘引人注目的研究方向,将贝叶斯网络应用于数据挖掘当中,充分挖掘数据的隐藏信息内在本质,应用前景非常广泛。目前,贝叶斯网络不仅在数据挖掘方面,而且在医学、金融、农业、环境科学、软件测试等众多领域显示出了它不可估量的作用。

(下转第161页)

对于本例而言,采用经典的样本统计法计算各个变量的概率参数,如:对于图2(a)中,计算p(BC),找出p(B,C)和

p(C),由p(BC)=p(B,C)/p(C)利用表中的数据,得到B

的条件概率分布函数,其他参数可由同样方法求出。经过计算和分析,调整贝叶斯网络的网络结构和各变量的条件概率分布函数,最终得出图2(a)为最优的贝叶斯网络。

—89—

Processing,2003,51(4):950-959.

4　结论和未来展望

基于特征的局部水印方法受到的关注比较少,一个很重要的原因是因为用于同步水印的重要特征必须要求能准确地重复,而来自模式识别邻域的特征的准确重复本身就是一个很有挑战性的研究问题。

本文基于ScaleSal检测出的显著区域来同步水印,提出了一种抗几何攻击的局部数字水印算法。实验数据表明,该算法除了对一般的信号处理攻击是鲁棒的,还对几何攻击,包括裁剪、旋转、缩放、平移和线性变换等都具有较好的鲁棒性。实验表明,特征的准确再现对水印系统的影响很大,那么今后的一个研究方向是从模式识别邻域中寻找一种精确重复率高的特征检测方法或者是设计一种专门用于同步水印的特征检测方法。另外,在不影响载体的视觉质量的前提下的大容量、鲁棒水印算法是今后的另一个研究方向。参考文献:

[1]　PBas,JMChasseryandBMacq.GeometricallyInvariantWater2

markingUsingFeaturePoints[J].Sep.2002,11(9):1014–1028.

[2]　CWTangandHMHang.AFeature-BasedRobustDigitalImageWatermarkingScheme[J].IEEETransactionsonSignalIEEETrans.

ImageProcess,

[3]　TKadirandJMBrady.Scale,saliencyandimagedescription

[J].Intl.J.ofComputerVision,2001,45(2):83-105.[4]　AReeves,RProkop,SAndresandFKuhl.Three-dimensional

ShapeAnalysisUsingMomentsandFourierDescriptors[J].IEEETrans.PatternAnal.Mach.-943.

[5]　SVoloshynovskiy,AHerrigel,NBaumgartnerandTPun.ASto2

chasticApproachtoContentAdaptiveDigitalImageWatermarking[C].Proc.Int.WorkshoponInformationHiding,1999,1768(LNCS):211–236.

Intell.,Nov.1988,10(6):937

[作者简介]

袁武钢(197516-),男(汉族),湖南株洲人,在读

博士,主要研究领域为视频处理、数字水印。

卢正鼎(194419-),男(汉族),湖北武汉人,硕

士,教授,博导,主要研究领域为信息安全、分布异构系统集成。

凌贺飞(1976111-),男(汉族),河南信阳人,博

士,副教授,主要研究领域为多媒体安全。余艳玮(1981112-),女(汉族),湖北孝感人,在读博士,主要研究

领域为数字水印、神经网络。(上接第89页)

[5]　朱明.数据挖掘[M].合肥:中国科学技术大学出版

社,2002.

[6]　陆玉昌.数据挖掘与知识发现[J].中国计算机用户,2000,

(18):29-32.

[7]　DavidHeckerman.BayesianNetworksforDataMining[J].Ma2

chineLearning,1997,(3):213-244.

[8]　林士敏,田凤占,陆玉昌.贝叶斯学习、贝叶斯网络与数据采掘

[J].计算机科学,2000,27(10):69-72.

[9]　闫志勇,等.贝叶斯网络在自适应教育超媒体中的应用[J].计

算机工程与应用,2002,(8):217-219.

[10]　薛万欣,等.Bayesian网中概率参数学习方法[J].电子学报,

2003,(11):1686-1689.

图3　基于上述案例两种不同方法的学习曲线比较

[作者简介]

参考文献:

[1]　蔡自兴,徐光祐.人工智能及其应用(第三版)[M].北京清华

李艳美(1979-),女(汉族),山东人,硕士研究

生,主要研究方向为随机优化与数据挖掘。

大学出版社,2004.

[2]　董琳,邱泉,于晓峰,吴韶群,孙立骏译.数据挖掘、实用机器

张卓奎(1962-),男(汉族),陕西人,博士,副教

授,主要研究方向为随机过程与随机系统。

学习技术[M].北京:机械工业出版社,2005.

[3]　姜哲,金奕江,张敏,杨磊,等译.人工智能—一种现代方法

(第二版)[M].北京:人民邮电出版社,2004.

[4]　NilsJNilsson著,郑扣根,庄越挺译.人工智能[M].北京:机

械工业出版社,2000.

—161—