（计算机科学与技术专业论文）基于贝叶斯网络的有向图生成森林算法研究.pdf

中文摘要 摘要：随着数据库应用的不断深化，数据库的规模急剧膨胀，数据挖掘已成为当 今研究的热点。数据挖掘的算法有：关联分析、分类和预测、聚类分析。特别是 其中的分类问题，是数据挖掘重要的部分之一。由于其使用的广泛性，现己引起 了越来越多的关注。 鉴于分类问题在数据挖掘中的特殊重要性，引起了广泛的关注和学者们的兴 趣。也就出现了很多分类算法，而且近来不断出现很多新的算法用于构建分类器。 特别是基于贝叶斯网络的算法。 本文首先介绍了数据挖掘技术的基本概念、背景、方法及其中的分类技术。 随后阐述了贝叶斯网络的结构定义和构造的一般过程，利用贝叶斯网络模型分类 的原理。在综合研究几种贝叶斯分类模型特点的基础上，分析和评价了这些分类 模型的优点以及缺点。最后，提出了基于结点排序的有向图生成森林模型和基于 边选择的有向图生成森林模型。由于两种模型本身的着眼点不同使得对具有不同 特点的数据集的分类效果会有差别。所以，在分类之前应对数据进行简单分析， 按照数据集的特点选择适合的分类模型。实验结果表明：基于模型实现的算法在 一些数据集上的结果优于其它算法，在大部分数据集上不亚于其它算法。 关键词：数据挖掘；贝叶斯分类；有向图生成森林模型；分类算法 分类号：t p 3 们6 j e 鏖銮道丕堂亟堂位论塞旦至b ! a bs t r a c t a b s t r a c t ：w i t ht h ew i d e s p r e a da p p l i c a t i o no fd a t a b a s e s ，t h es c a l eo fd a t a b a s e s e x p a n d sd r a m a t i c a l l y , a n dd a t am i n i n gh a sb e c o m eaf o c u so fr e s e a r c h t h ea l g o r i t h m s o fd a t am i n i n gi n c l u d ea s s o c i a t i o na n a l y s i s ，c l a s s i f y i n ga n df o r e c a s t i n g ，a n dc l u s t e r i n g a n a l y s i s c l a s s i f i c a t i o ni so n eo ft h em a j o rp a r t so fd a t am i n i n gw h i c hh a sa r o u s e d g e n e r a lc o n c e r nd u et oi t se x t e n s i v eu s a g e r e s e a r c h e r sb e c o m ei n t e r e s t e di nc l a s s i f i c a t i o nb e c a u s ei t so fg r e a ti m p o r t a n c ei n d a t am i n i n g m a n yn e wc l a s s i f i c a t i o na l g o r i t h m s ，e s p e c i a l l ya l g o r i t h m sb a s e do n b a y e s i a nn e t w o r k ，h a v eb e e nu s e dt oc o n s t r u c tc l a s s i f i e r f i r s t l y , t h i sp a p e ri n t r o d u c e sb a s i cc o n c e p t ，b a c k g r o u n d ，m e t h o d sa n dc l a s s i f i c a t i o n t e c h n i q u e so fd a t am i n i n gt e c h n o l o g y t h e nt h ep a p e rd e f i n e sc o n s t r u c t i o no fb a y e s i a n n e t w o r k ，a n di l l u s t r a t e st h ep r i n c i p l e so fc l a s s i f i c a t i o nu s i n gab a y e s i a nn e t w o r km o d e l o nt h eb a s i so fc o m p r e h e n s i v es t u d yo fs e v e r a lb a y e s i a nn e t w o r km o d e l s ，t h ep a p e r a n a l y z e sa n de s t i m a t e st h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h e s ec l a s s i f i c a t i o nm o d e l s l a s t l y , t h ep a p e rp r e s e n t st w ok i n d so fd i r e c t e df o r e s t - a u g m e n t e dc l a s s i f i c a t i o n m o d e l s - - d i r e c t e df o r e s t e d - a u g m e n t e dm o d e lb a s e do nn o d e ss o r t i n ga n dd i r e c t e d f o r e s t a u g m e n t e dm o d e lb a s e do ne d g e ss e l e c t i o n t h ee f f e c t i v e n e s so fc l a s s i f i c a t i o n m a y d i f f e rf o rd a t as e t sw i t hd i f f e r e n tc h a r a c t e r i s t i c sb e c a u s et h em o d e l sh a v ed i f f e r e n t f o c u s e s t h e r e f o r e ，t h ed a t as h o u l db ea n a l y z e dr o u g h l yb e f o r ec l a s s i f i c a t i o na n dp r o p e r c l a s s i f i c a t i o nm o d e ls h o u l db es e l e c t e da c c o r d i n gt ot h ec h a r a c t e r i s t i c so fd a t as e t s e x p e r i m e n t ss h o wt h a tt h ea l g o r i t h mi nt h i sp a p e ri ss u p e r i o rt oo t h e r si ns o m ed a t as e t s ， a n dn o ti n f e r i o rt oo t h e r si nm o s td a t as e t s k e y w o r d s ：d a t a m i n i n g ；b a y e s i a nc l a s s i f i c a t i o n ；d i r e c t e df o r e s t - a u g m e n t e dm o d e l ； c l a s s i f i c a t i o na l g o r i t h m c i 。a s s n 0 ：t p 3 0 1 6 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。 同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：马定 导师签名： 毫基醪乙忒) 签字日期：20 0 7 年多月矽r 签字日期：2 一? 年石月彩自 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：与健 签字同期： 2 口p 7 年占月矽日 5 6 致谢 本论文的工作是在我的导师胡俊副教授的悉心指导下完成的，胡俊副教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢两年来 胡俊老师对我的关心和指导。 王志海教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都给 予了我很大的关心和帮助，在此向王志海老师表示衷心的谢意。 瞿有利老师对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷 心的感谢。 在实验室工作及撰写论文期间，赵君霞、邵鲁杰等同学对我论文中的数据挖 掘研究工作给予了热情帮助，在此向他们表达我的感激之情。 另外也感谢家人我的父母，他们的理解和支持使我能够在学校专心完成我的 学k 。 1 引言 本章主要介绍本课题的研究背景、数据挖掘及其中的重要方面分类，以 及本论文的主要工作和组织安排。 1 1论文背景 随着计算机技术的飞速发展，人类收集数据、存储数据的能力得到了极大的 提高，无论是科学研究还是社会生活的各个领域中都积累了大量的数据，对这些 数据进行分析以发掘数据中蕴含的有用信息，成为几乎所有领域的共同需求。正 是在这样的大趋势下，数据挖掘的作用同渐重要，受到了广泛的关注。 在数据挖掘中，分类是一项非常重要的任务。分类方法是最广泛使用的方法， 也是研究得最多的方法。分类方法从过去的已分类的经验数据中学习各个类别的 区别，并建立模型描述这种区别，可以用来对数据进行描述，或者对未知的数据 进行分类。 由于分类问题在数据挖掘中的重要性，引起了广泛的关注和学者们的兴趣， 因而涌现出了很多种算法，常见的有决策树方法、规则归纳方法、神经网络方法、 贝叶斯方法、支持向量机、卜最近邻方法等。这些算法均基于不同的假设而发展 起来的。 其中的贝叶斯方法，由于其坚实的数学背景，使得成为数据挖掘有效的工具 之一。n 2 0 世纪3 0 年代形成了贝叶斯学派，五六十年代发展成一个有影响力的统 计学派。在数据挖掘中，主要使用两种贝叶斯方法。朴素贝叶斯方法和贝叶斯网 络。 朴素贝叶斯分类算法在许多场合可以与决策树和神经网络分类算法相媲美。 但贝叶斯定理假设一个属性对给定类的影响独立于其它属性，此假设在实际情况 中经常不成立。 贝叶斯网络是一个带有概率注释的有向无环图。这个图模型能有效地表示大 的变量集合的联合概率分布，从而适合用来分析大量变量之间的相互关系，利用 b a y e s 公式的学习和推理功能，实现预测、分类等数据采掘任务。因为关于变量组 的贝叶斯网络表示了该变量组的联合概率分布，所以一旦网络确立下来，原则上 可以用它来推断任何感兴趣的概率。贝叶斯网络也是一种适合处理不确定性知识 问题的知识表示方法，因为它可以从部分概率中进行推导。但贝叶斯分类算法学 习是很困难的，有些研究已经证明其学习属于n p c o m p l e t e l b - 题。 所以，研究人员的改进通常致力于通过属性对之间的依赖关系来降低独立性 假设。在研究的过程中，一种贝叶斯网络树形( 或森林) 贝叶斯网络。由于 其结构简单和在分类预测中的良好表现。这种有向树( 或有向森林) 得到了广大 学者们的研究。 1 2 数据挖掘及分类介绍 1 2 1数据挖掘 数据挖掘( d a t am i n i n g ) ，关于其定义有很多种，其中一种比较公认的描述方式 是：数据挖掘就是从海量的数据之中提取隐含的、目前未知的、最终可理解的、 有效的、新颖的、对于决策过程有用的知识的非平凡过程【3 】，在很多文献中，数据 挖掘也被称为数据库中知识的发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，简称k d d ) 、 知识提取( k n o w l e d g ee x t r a c t i o n ) 等。 数据挖掘以人工智能、统计学、机器学习等技术为基础，涉及多个学科领域。 其中人工智能是以自动机为手段，通过模拟人类宏观外显的思维行动，从而高效 解决现实世界问题的技术。数据挖掘利用了人工智能中一些较成熟的算法和技术， 如人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ) 、遗传算法( g e n e t i ca l g o r i t h m s ) 、决策 树( d e c i s i o nt r e e s ) 等。 国际上第一次关于数据挖掘与知识发现的研讨会于1 9 8 9 年8 月在美国底特律 召开，知识发现一词是在此学术会议上正式形成的，当时仅有数十人参加，此后 发展很快，19 9 5 年提升为国际学术大会( i n t e r n a t i o n a lc o n f e r e n c eo nd a t am i n i n g & k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) ，即在加拿大召开的第一届知识发现和数据挖掘 国际学术会议。这次会议上明确定义了知识发现的概念，并确定了知识发现过程 和数据挖掘的关系。此后，数据挖掘开始流行，它是知识发现概念的深化，知识 发现与数据挖掘是人工智能、机器学习与数据库技术相结合的产物。此外，还有 这一主题的地区性国际大会，包括相关的学科领域，特别是机器学习、归纳逻辑 程序设计( i l p ) 、医药数据处理、分布式人工智能、基于实例的推理( c b r ) 等。目前， 数据库中的知识发现和数据挖掘技术己成为研究热点和焦点。机器学习和数据分 析的理论及实践成为知识发现研究的铺垫。广阔的商业应用前景则是推动知识发 现和数据挖掘研究的又一主要因素。知识发现是把数据库作为知识源，综合统计 学、数据库、机器学习、可视化、数据分析等技术进行从数据库中发现知识的研 究。 数据挖掘方法的提出，让人们有能力最终认识数据的真正价值，即蕴藏在数 2 据中的信息和知识。数据挖掘引起了学术界和工业界的广泛关注，一些国际上高 级别的工业研究实验室，例如i b ma l m a d e n 和g t e 等众多的学术单位都在这个领 域开展了各种各样的研究计划。研究的主要目标是发展有关的方法论、理论和工 具，以支持从大量数据中提取有用的和让人感兴趣的知识和模式。 当今，数据挖掘技术方兴未艾，数据挖掘技术所表现出的广阔应用前景吸引 了众多的研究人员和商业机构。一批数据挖掘系统被开发出来，并在商业、经济、 金融、管理等领域都取得了应用性成果，其中比较有代表性的有q u e s t ，k d w ， e x p l o r e ，i m a c s ，1 n l e n ，d b m i n e r 。这些系统基本上代表了自2 0 世纪8 0 年代以来 的数据挖掘技术的发展。采用的发现方法综合了数据库、专家系统、模式识别、 机器学习、统计学、科学发现和数据分析等领域的研究成果。但总的来说，这些 系统基本上还停留在实验阶段，在适用性，系统效率方面还不尽人意。 1 2 2分类 能够学习如何把一个对象划分到预定义的类被认为是智能的一个重要特征， 在人工智能、机器学习和神经网络等方面都有广泛的应用，这类任务被称作分类。 分类是一种有指导的学习，即学习过程是在被告知每一个训练样本属于哪个类的 “指导”下进行的。 分类数据集可以描述为：数据是一张标准关系表，它包含个记录，这些记 录通常称作实例( i n s t a n c e ) 或样本( e x a m p l e ) ，每一个实例用固定数目的度量标准描 述，这种度量标准称作属。 生( a t t r i b u t e ) 。每一个属性都有一个合法的取值范围，称 作该属性的域( d o m a i n ) 。如果属性域是实数域，那么则称该属性为数值属性 ( n u m e r i c a la t t r i b u t e ) 或连续属性( c o n t i n u o u sa t t r i b u t e ) 。如果属性域是有限的，那么则 称该属性为分类属。l 生( c a t e g o r i c a la t t r i b u t e ) 或离散属性( d i s c r e t ea t t r i b u t e ) 。这些属性 中有一个区别于其他的称作类标号( c l a s sl a b e l ) ，类标号指示元组所属的类。除了类 标号之外的其他属性是预测未知样本类型的依据，因此也称作预测属。i 生( p r e d i c t o r a t t r i b u t e s ) 。 在分类研究中，数据集通常被分成训练集和测试集。训练集用来构造分类器， 测试集用来评估分类器的预测准确度。因为学习算法可能对数据的过分特化，所 以使用训练数据构造分类模型，然后用同样的数据集评估分类模型可能导致过于 乐观的估计。因此，通常采用测试集来评估分类模型。在分类研究中，通常采用 u c i 机器学习库【3 8 】( u c im a c h i n el e a r n i n gr e p o s i t o r y ) 中的数据集评估不同的分类 模型。这些数据集来自广泛的应用领域，并且不同数据集的规模、目标类的个数 和属性个数变化很大，能够比较全面的反映算法的分类性能。 分类过程可以描述为如下两个步骤： 第一步，是建立一个模型，描述预定的数据类或概念集。 训练阶段的目的是建立分类器，即从训练数据集中获取可以进一步指导未知 数据分类的专家知识。不同的分类模型可能用不同的形式描述用于指导分类的知 识，如分类规则、决策树或数学公式等。这些分类模型以不同的形式描述了某个 类区别其他类的特征概念集。从另一个角度来看，也可以认为分类模型是以某种 特定的形式描述了训练集的数据分布特征。如果训练集能够代表整体数据分布特 征，那么由训练集获得的特征概念集就可以用来指导对未知数据的预测。 第二步，使用模型进行分类。 在使用分类模型对未知类标号的实例或对象分类之前，首先要使用测试集评 估分类模型的分类准确率。如果分类准确率是可以接受的，那么我们才可以真正 把该模型用于指导未知元组的分类。有多种技术用来评估分类模型的准确性，关 于模型的评估的问题有后续描述。 由于分类技术在不同领域的广泛应用，统计学、机器学习、神经网络等领域 的研究者提出了很多分类方法。这些算法来自不同的领域、工作原理差别很大， 但是都在相应的领域取得了很大的成功。现有的分类技术主要有：贝叶斯分类、 基于决策树的分类、源自关联规则挖掘概念分类、神经网络、遗传算法、模糊集 和粗糙集方法等【3 6 】。 1 3 本文的主要工作和组织安排 本文的主要工作是在分析和评价朴素贝叶斯分类模型和树增强分类模型的基 础上。提出自己的有向图生成森林分类模型，并在此基础上实现模型的分类算法。 最后，通过实验得到的实验结果来评价分类器。 1 生成贝叶斯有向图的森林模型。包括学习模型结构，实现森林模型。通过 衡量网络质量和网络空间的搜索的方式确定模型的结构。 2 选择一个网络质量衡量标准。该衡量标准是评价模型对于给定的数据集的 适应程度。 3 在所有可能网络结构的网络空间中进行搜索并且利用质量标准来衡量两个 结点之间是否应该加边。 第1 章为本文的引言部分。介绍了本文的研究背景，数据挖掘和数据挖掘中 分类的相关概念，并论述了本文的研究内容及论文的组织结构。 第2 章首先详细地介绍了贝叶斯定理、贝叶斯假设、贝叶斯网络结构与依赖 模型以及数据挖掘中贝叶斯分类的基本概念、原理。贝叶斯网络学习和贝叶斯网 4 络的建立。介绍了几种树( 或森林) 分类模型和它们的优缺点。最后，介绍了用 于数据挖掘的软件w e k a 。 第3 章详细论述了基于结点排序的有向图生成森林分类模型。对该模型实现 的算法做了详尽的描述、分析了算法性能。 第4 章详细论述了基于边选择的有向图生成森林分类模型。对该模型实现的 算法做了详尽的描述、分析了算法性能。 第5 章阐明了两种模型本身的着眼点不同使得对具有不同特点的数据集的分 类效果会有差别。进一步分析了两种模型的特点和数据集的特点。将数据集按照 模型的特点分为两类，使得具有相同特点的数据集能够运用适合该数据集特点的 分类算法。接下来说明了实验的实验环境、实验数据和实验方法，并得出了实验 结果。最后，对实验结果进行了分析。 第6 章结论。总结论文所作的工作。 2 贝叶斯网络分类 工程的实际问题一般都比较复杂，存在着许多不确定性因素。这就给准确推理 带来了很大的困难。很早以前，不确定性推理就是人工智能的一个重要研究领域。 为了提高推理的准确性，人们引入了概率理论。最早由j u d e ap e a r l 于1 9 8 8 年 提出的贝叶斯网络( b a y e s i a nn e t w o r k ) 实质上就是一种基于概率的不确定性推理网 络。为了介绍贝叶斯网络，首先要说明贝叶斯定理。 2 1贝叶斯定理 贝叶斯定理是贝叶斯理论中最重要的一个公式，是贝叶斯学习方法的理论基 础。它将事件的先验概率、后验概率以及训练样本数据巧妙地联系起来。贝叶斯 方法使用概率表示所有形式的不确定性，学习或推理都用概率规则来实现，学习 的结果也表示为随机变量的概率分布，学习结果的概率表示可以解释为观测者对 不同事件的信任程度。 设d = - x l = x 1x 2 = x 2 , - m 魂) 为其中x 为事件变量，z 为变量值，设只晟) 代表在 没有训练数据前假设h 拥有的初始概率。p ( j i z ) 常被称为h 的先验概率( p r i o r p r o b a b i l i t y ) ，它反映了我们所拥有的关于h 是一j 下确假设的机会的背景知识。尸( d ) 代表将要观察的训练数据d 的先验概率。尸( d ) 表示假设h 成立的情形下观察到 数据d 的概率。我们需要得到给定训练数据集d 时h 成立的概率e ( h l o ) ，即h 的 后验概率( p o s t e r i o rp r o b a b i l i t y ) 。后验概率e ( h l d ) 反映了训练数据d 对假设h 的影 响，而先验概率以 ) 是独立于d 的。 嘲驴警 ( 2 1 ) 贝叶斯公式也叫后验概率公式或逆概率公式。直观上可以看出，后验概率 p ( h l d ) 随着先验概率以j 1 1 ) 和概率p ( dl ) 的增长而增加，随着概率只d ) 的增加而减 少。如果d 独立于h 时被观察到的可能性越大，那么d 对h 的支持度就越小。 在数据挖掘中，通常人们感兴趣的是在给定训练数据d 时，如何确定假设空 间日中的最佳假设。所谓最佳假设定义为，在给定数据d 及日中不同假设的先验 概率的条件下的最可能的假设【5 1 。 2 2贝叶斯网络的结构 贝叶斯网与依赖模型 6 定义：贝叶斯网是一个有向无环图( d a g ) ，它可以表示为一个三元组g = ( 丘p ) 。其中是一组结点的集合，= 仁i 抛，, x n ) ，每个结点代表一个变量( 属 性) 。e 是一组有向边的集合，e = q 厶力 lx i 嘲并且札力奶，每条边瓴而 表 示粕而具有依赖关系而。p 是一组条件概率的集合，尸= p 似i 乃) ) ，p 瓴i 砀) 表示 劫的父节点集乃对面的影响) 。 设某个系统有个属性结点 x i 抛，, x n ) 由联合概率公式可得： p ( x b x 2 , 而) = 兀p ( x iix i ，x 2 ，而) ( 2 2 ) f = i 现在假如对每个结点x ，己知存在某个子集兀f 属于抛，, x n ) ，在给出兀f 时，而 和扛l 抛，而) h i 是条件独立的，即有： p ( x i x l , x 2 , 而) = 兀p ( x , lx f ) ( 2 3 ) i = 1 由上式，( 2 3 ) 式可等价为： p ( x b x 2 , 而) = 兀p ( x , lx r )( 2 4 ) i f f i l 由上式可知，贝叶斯网实质上就是一个联合概率分布p ( x l 力，而) 所有条件独 立性的图形化表示，其中砺为x i 父节点集。 依赖模型m 中，设置y , z 是全集u 的三个不相交的子集，胙 心z y ) ) 。其 中，魍z 功表示在给定z 的条件下，x 独立于】，即：p ( x i y , z ) = p ( x i z ) 和p 佣y ，z ) = p ( 1 1 z ) 。 2 3贝叶斯网络学习 贝叶斯网最初是作为一种处理专家系统中不确定的工具而被提出的。近年来， 它越来越多地被用于数据分析，以揭示和刻画数据中所蕴含的规律。贝叶斯网学 习指的是通过分析数据而获得贝叶斯网的过程。它包括参数学习和结构学习两种 情况。参数学习指的是己知网络结构，确定网络参数的问题；结构学习则是既要 确定网络结构，又要确定网络参数。 用贝叶斯网来分析一组数据d ，就是要从这组数据出发，找出一个相对于数 据在某种意义下最优的贝叶斯网。所得的结果是关于数据d 的一个统计模型，称 为贝叶斯网模型。 正如前面所述，一个贝叶斯网b 有定性和定量两个方面的内容：定性内容包 括变量之间的网络结构，记为协。定量内容则包括各变量的概率分布，记为口。 所以，曰又可以写成二元组 的形式。在讨论数据分析事，西被称为模型结 构( m o d e ls t r u c t u r e ) ，有时简称模型；而秒则称为模型参数( m o d e lp a r a m e t e r s ) 。 7 通过数据分析获得贝叶斯模型的过程称为贝叶斯学习( b a y e s i a nn e y w o r k l e a r n i n g ) 。当模型结构已知时，贝叶斯网学习又简称为参数学 - - j ( p a r a m e t e rl e a r n i n g ) ； 而当模型结构未知时，它称为结构学( s t r u c t u r el e a r n i n g ) 。 2 3 1一般网络最大似然估计 给定秒，数据d 的条件概率尸i 口) 称为是秒的似然度( 1 i k e l i h o o d ) ，记为口的似 然函数( 1 i k e l i h o o df u n c t i o n ) 。 在介绍一般网络最大似然估计之前，先介绍两个假设。 设数据d 由样本( d l p 2 ，岛) 组成。为了计算上的方便，需要做两个假设。 第一个假设是，d 中各样本在给定参数秒时相互独立，即 l ( oi d ) = p ( d 1 秒) = l i p ( d io )( 2 5 ) i = 1 第二个假设是，每个样本d f 的条件概率分布e ( o f i9 ) 相同。 这两个假设是统计学中的基本假设，统称为独立同分布( i n d e p e n d e n ta n d i d e n t i c a l l yd i s t r i b u t e d ) 假设，简称i i d 假设。 下面讨论由多个变量组成的一般贝叶斯网的参数估计。 考虑一个由n 个变量炸 蜀如，疋) 组成的贝叶斯网b 。设是x 中的一个 变量。而表示的父亲集合。不失一般性，设其中的结点共有n 个取值l ，2 ，n ， 其父结点而的取值共有q i 个组合1 ，2 ，缈。若示咒无父节点，则q i = l 。那么，网 络的参数为 锹= 以x i = k7 i = - ) ， ( 2 6 ) 其中i 的取值范围是l n ，而对一个固定的f ，_ ，和k 的取值范围分别是从1 g f 及从 l n 。用9 记所有锹组成的向量。这些参数不是相互独立的，由于概率分布的规范 性，有 r ir i 锨= 尸( m = 后i7 r ，= - ，) = l v i ，j ( 2 7 ) 七= i七= i 所以，b 的独立参数的个数是g ，( r l - - 1 ) 。 i f f i i 设数据d = p l a ，p m ) 是一组关于b 的i i d 数据，则秒的对数似然函数为 ( 口i d ) = l o g 兀p ( d , io ) = l o g p ( d ，io ) ( 2 8 ) i = 1 l = 1 l ( oi d ) ：窆兰兰聊独1 。g 饥 i = 1j = tk = l 其中，脚耻是数据中满足x , - - k ，r c i = j 的样本的数量。当岛t 取如下值时 秒幸社= 孚坠 z m i # n 1 移n k 2 一 r ，若m o k 0 七= l 一 ，若m o k = 0 k = i ( 2 9 ) ( 2 1 0 ) ( 2 1 1 ) ，f 表达式m u k l 0 9 0 u k 的值达到最大，从而三( 伊i d ) 达到最大。所以，式( 2 1 0 ) 给 f = l 出的0 * u k 是0 0 4 的最大似然估计。直观上有 = 堕d 糕 g t 芮篓l 糕筹 亿，2 ， 。 足卢，的样本的数目 “纠 2 3 2似然函数与模型选择 参数学习假设已知变量间的定性关系，通过数据分析揭示变量间的定量关系； 而结构学习则是要同时揭示变量问的定性和定量关系。结构学习一般分两步讨论， 即模型选择( m o d e ls e l e c t i o n ) 和模型优化( m o d e lo p t i m i z a t i o n ) 。模型选择要回答的问 题是用什么样的准则来评判不同模型结构之优劣，而模型优化则是要把最优的模 型结构找出来。 设活托，疋) 为一组随机变量，9 = - ( 9 ld 2 , - - p 册) 是关于这些变量的一组 数据。本章所关心的问题是如何找出个相对于d 在某种意义下最优的贝叶斯网。 设d 是一个以涵垃，, x n ) 为结点的贝叶斯网结构。d 相对于x 的优劣可以用 一个评分函数( s c o r i n gf u n c t i o n ) 来度量。本节介绍一个基于似然函数的评分准则， 称为最优参数对数似然函数( p a r a m e t e rm a x i m i z e dl o g l i k e l i h o o df u n c t i o n ) ，简称优参 9 对数似然函数。 结构曰于相应的参数集合伊b 组成贝叶斯网仍，秒b ) 。这里我们给秒曰加下标是 因为不同的网络结构对应不同的参数集合。 在贝叶斯网( b ，秒曰) 中，可以计算每一个样本d ，的概率p ( d ，i b ，护曰) ，从而在i i d 的假设下，可以计算p ( d t i b ，口口) 。可以计算l o g p ( d ，i b ，0 8 ) 。在参数学习中，网 络结构b 已知，这就是参数向量0 占的对数似然函数。根据最大似然估计原则，相 对于数据d 最优的参数值口口应使l o g e ( d t l b ，0 b ) 达到最大值，即 s l l n l o g p ( d b ，0 书口) = 。l o g ( d i b ，o b )( 2 1 3 ) f - - 厅 在结构学习中，网络结构b 和网络参数9 占都是需要确定的对象。于是l o g p ( d b ， 口口) 视为二元组( b ，0 8 ) 的对数似然函数，记为 l ( b lo s ，d ) = i o g p ( d i b ，目力 ( 2 1 4 ) 将最大似然估计原则加以推广，得到如下结论：相对于数据d 最优的贝叶斯网l 旧事 0 牛日) 应该使对数似然函数达到最大，即 m a x 刚l n l 木，仉i d ) 2b 目：l 尸( 曰，口引d ) ( 2 1 5 ) 在概念上，寻找最优贝叶斯网的过程可以分成两步：第一步寻找最优结构b 掌，第 二步优化参数如。为刻画第一步所使用的准则，对任一网络结构口，定义 l 木( b i d ) = 。1 叫b ，8 b i d ) 占 作为网络结构b 的函数，l * ( b i d ) 称为优参对数似然函数。 应该使优参对数似然函数达到最大，即 l 木宰i d ) 2 曰 l 木只曰id ) ( 2 1 6 ) 根据式，最优结构b 奉 ( 2 1 7 ) 这就是介绍的模型选择标准，称为最大优参似然标准。下面再介绍一个关于优参 对数似然函数的引理。 对数据集x 的任一取值z p = 堕譬嚣挲塑 亿 则尸是基于数据集d 的经验分布( e m p i r i c a ld i s t r i b u t i o n ) 。 引理：设数据d 是完整的，p 是d 的经验分布，则有 l o l 木i o ) = 一m 胁( 石 ( 2 1 9 ) i = i 以i ) 是基于分布p 、给定而时的条件熵。 根据条件熵的性质，可以得出，使优参似然函数达到最大的网络结构b 宰是完 全的【4 1 。 2 4贝叶斯分类 贝叶斯分类是统计学分类方法，它基于贝叶斯定理，使用后验概率预测类成 员关系的可能性，如给定样本属于某一特定类的概率。 基于贝叶斯的分类过程可以这样描述：假定有k 个类c l ，c 2 ，q ，给定未知 数据样本x 可以用一个维向量描述为胙坦，, a n ) ，分类器将预测未知样本 石属于在各属性取值为条件下的后验概率最高的类。即选择能够使p ( g i 最大 化的g 作为未知样本所属的类 尸( c f 尸( ( ：，囟甄f ( 2 2 0 ) 依据贝叶斯定理 p ( c j = 坠焉掣 ( 2 2 1 ) 其中，尸对于所有的类都是常数，只需p 闲c ) p ( g ) 最大，而如果类的先验 概率未知，通常假定这些类是等概率的，即p ( c 1 ) = 以c 2 ) = = 尸( g ) 。类的先验概率 也可以用p ( c 3 = l s r q s i ，其中i s i 是训练集中g 类的样本数，l s l 是训练集的样本总 数。因此，如何获得p ( 圈c f ) 成为基于贝叶斯的分类算法的关键问题。 与数据挖掘中的其他知识表示的方法如规则表示、决策树、人工神经网络等 相比，贝叶斯网络在知识表示方面具有以下优点：贝叶斯网络能够很方便地处理 不完全数据。贝叶斯网络能够学习变量间的因果关系。贝叶斯分类与其他模型相 结合，通常可以有效的避免了数据的过分拟合。 分类有规则分类和非规则分类，贝叶斯分类是非规则分类，它通过训练集训 练而归纳出分类器，并利用分类器对没有分类的数据进行分类。 贝叶斯分类具有如下特点： 1 能充分利用领域知识和其他先验信息，能够显示地计算假设概率，分类结 果是领域知识与数据样本信息的综合体现； 2 利用有向图的表示方式，用弧表示变量之间的依赖关系，用概率分布表示 依赖关系的强弱。表示方法非常直观，有利于对领域知识的理解； 3 一般情况下，所有的属性都参与分类，并在分类中潜在地起作用。 4 能进行增量学习，数据样本都可以增量地提高或降低某种假设的估计概 率； 5 贝叶斯分类一般处理的是离散属性的对象； 在数据挖掘中，对贝叶斯分类方法的研究主要集中在如何从数据集中在学习 特征变量的分布，确定最好的反映变量关系的贝叶斯网络模型。目前，贝叶斯分 类方法已经在文本分类、模式识别、经济预测等领域获得了成功应用。 2 5贝叶斯有向树( 或森林) 分类模型介绍 2 5 1朴素贝叶斯分类模型 朴素贝叶斯分类模型( n a i v e b a y e s m o d e l ) ，又称朴素贝叶斯分类器 ( n a i v e b a y e s c l a s s i f i e r ) ，是一个包含一个根结点、多个叶结点的树状贝叶斯网如图 2 1 。其中叶结点a 1 4 2 ，4 ，l 是属性变量，描述待分类对象的属性，根结点c 是类 别变量，描述对象的类别。用朴素贝叶斯模型进行分类就是给定一个数据点，即 各属性的取值爿l 龟l ，4 。- q f t 月，计算后验分布e ( c l a l 司l ，4 盯龟。) ，然后选择概率 最大的那个c 值作为这个数据点所属的类别。 朴素算法的分类模型是基于b a y e s 定理的。 作为一种贝叶斯网络的代表，一个朴素贝叶斯分类器具有结构简单， a 1a 2 o a n 图2 1 朴素贝叶斯分类模型 f i g u r e 2 1n a i v e - b a y e sc l a s s i f i e r s 尽管朴素贝叶斯分类算法很简单，但是在很多应用领域取得了巨大的成功， 分类准确度可以与决策树和神经网络等复杂的算法媲美。应用于大型数据库，贝 叶斯分类表现出了高准确度与高速度。当条件独立性假设成立时，朴素贝叶斯分 类是最精确的，然而朴素贝叶斯分类算法的条件独立性假设在现实数据集上通常 1 2 是不成立的【6 1 。 2 5 2 树增强型分类模型 学习扩大的贝叶斯网络也是一个n p 问题，具有较高的复杂度。算法树增强朴 素贝叶斯模型( t a n ) 的发现者提出了种树扩大朴素贝叶斯网络( t r e e a u g m e n t e d n a i v eb a y e s i a nn e t w o r k ，t a n ) 的概念。在这种网络结构中，类变量没有双亲节点， 每一个非类变量都以类变量为一个双亲节点，另外这些非类变量最多还可以有其 它一个非类节点为双亲节点。这个限制可以让相应的网络结构学习变得非常有效 率。用t a n 网络结构学习是基于c h o w 和l i u 的方法。此方法的描述如下文述。 设g 是建立在变量集汹，疋) 上的一个有向无环图，设眦表示石的双亲节 点集，如果除了其中的一个特殊的节点没有双亲节点以外，几x 中只包含的一 个双亲节点，那么g 就是一棵树( t r e e ) ，此特殊节点成为根( r o o t ) 。设函数 厩 1 ，甩) - 0 ，) 满足如下条件，那么它就在蜀，疋上定义了一棵树：只有一 个f 使得顽炉：o ( 即树的根节点) ；并且没有序列f ， ，“使得i s _ j 0 时孵隅( i ) ，如果积f ) = o 时，噼o ， 则称这个函数定义了一棵树。 c h o w 和l i u 描述了一个从数据中建立树型贝叶斯网络( t r e eb a y e s i a n n e t w o r k ) 的算法。这个算法将建造最大似然树( m a x i m u ml i k e l i h o o dt r e e ) 变成 一个在图中建立最大加权生成树( m a x i m a lw 葫曲t e ds p a n n i n gt r e e ) 的问题。找这 样的树也就是从图中找到弧的一个子集，使得这个子集能组成一棵树，并且树上 附加的权值最大化。 对每一对游时的变量计算值如公式( 2 2 2 ) 所述。 ( 墨；x j ) ( 2 2 2 ) 在这里，具体值由公式( 2 3 2 ) 计算。 ( x ；y ) = 善p ( 工，y ) 。gj 专妻量；：善万 2 2 3 ) 此公式的函数就是互信息函数( m u t u a li n f o r m a t i o nf u n c t i o n ) ，其中x 表示变 量x 的具体取值，y 表示y 的具体取值。它度量的是y 提供了多少关于x 的信息。 建造一个t a n 分类器包括以下五个步骤： ( 1 ) 对每一对嘭时的变量计算公式( 2 2 2 ) 所述值。 ( 2 ) 建造一个完全无向图，其中的顶点就是所有非类属性。用公式( 2 2 3 ) 计算 出来的值作为相应边的权值。 1 3 ( 3 ) 建造图的一棵最大生成树。 ( 4 ) 将建成的无向树转化成一个有向树，方法就是选择一个根节点，然后将所 有边的方向设置为背离该节点。 ( 5 ) 向图中加入一个节点c ，从它到每一个属性a f 都加一条弧，建成t a n 模 型。 算法的时间复杂度为o ( n n 2 ) 。时间复杂度为多项式时间复杂度。t a n 较之 朴素贝叶斯模型考虑了行个属性间的关联性，对属性之间独立性假设有了一定程 度的降低，但没有考虑属性之间可能存在更多的其他关联性，因此，其适用范围 仍然受到限制【5 】。 2 5 3h c s 模型 模型每个属性结点最多有一个父结点( 非类结点) ，所以最多可增) b h n - 1 条相关 联的弧，这里是属性结点个数；最少可增加o 条弧( 即n b c ) 。扩展朴素贝叶斯分 类器是在n b c 分类器基础上的一种扩展的贝叶斯网络，为了更好地理解这个网络 结构，先给出一个定义。 定义1 在扩展贝叶斯网络中，除了类结点以外没有父结点的属性结点称为孤点。 爬山搜索算法( h c s ) ： ( 1 ) 初始化网络为一个n b c 网络： ( 2 ) 估当前的分类器； ( 3 ) 在当前分类器中添加每条合法的弧： ( 4 ) 假如存在能够提高分类器性能的弧，那么就选择使分类器性能改进最大的 弧，添加到当前分类器中，转 f i - j ( 2 ) ； ( 5 ) 否则返回当前分类器。 初始化网络为一个n b c 网，评估当前的分类器，孤点集d 最初是属性点集 a i 一2 ，, a n 。评估眦f 到彳，的每条合法弧0 f 彳，4 ，o ) ，利用留一交叉验