（计算机软件与理论专业论文）贝叶斯网络学习方法和算法研究.pdf

摘要 贝叶斯网络由于具有图形化的 模型表示形式、 局部及分布式的学习机制、 直观 的推理:适用于表达和分析不确定性和概率性的事物;能够对不完全、不精确或不 确定的知识或信息中做出有效的推理等特性，而成为目 前不确定知识表达和推理领 域最有效的 模型之一。 如何通过有效的方法和算法利用现实数据学习贝叶斯网络， 并准确地表达蕴含在数据中有价值的信息是目 前图形模式与数据挖掘领域中的研究 的热点和难点。 贝叶斯网络的学习主要包括: 结构学习和参数学习， 通过网络结构与数据集可 以 确定参数，因此结构学习是贝叶斯网络学习的核心，有效的结构学习方法和算法 是构建最优网络结构的基础。 本文在对贝叶斯网络的起源与发展; 贝叶斯网络特点及在分类预测、 不确定性 推理、因 果 分 析等 方面的 应 用 情 况 进行 介绍的 基 础上， 着重 对贝 叶 斯网 络的 学习 理 论进行了 研究，阐述了贝叶斯网络学习的主要内 容，同时研究了贝叶斯网络的结构 学习机制。给出了一种基于预测能力的离散贝叶斯网络结构学习的新方法，由于预 测能力就是预测正确率，预测能力相同是条件独立性的充分必要，这样通过预测能 力的引入把变量之间弧的存在性与方向 有机地结合在一起。该方法有如下特点:学 习效率 及准确程度较高; 学习 得到的 结 构倾向 于简单 化， 能 够避免 对数 据的 过 度拟 合;能够处理不完整数据，不需要对变量进行排序，并且具有抗噪声数据功能。 在理论上， 贝叶斯网 络分类器与联合分类器具有相同的分类能力，由于具有概 率推断功能，根据条件独立性能够有效地降低维度，显著提高分类的效率，而实现 贝叶斯网络分类器的核心是贝叶斯网络结构学习，有效的贝叶斯网络结构学习机制 是建立贝叶斯网 络分类器的基础。 在基于预测能力的离散贝叶斯网络结构学习方法 的基础上给出了一种基于预测能力的贝叶斯网络分类器学习模型。数据实验表明， 使用该方法建立的贝叶斯网络分类模型具有较强的分类能力，是一种有效实用的贝 叶斯网络分类器的学习方法。 关键词:贝叶斯网络;依赖分析:结构学习;预测能力:贝叶斯网络分类器 ab s t r a c t b a y e s i a n n e t w o r k s i s o n e o f t h e m o s t e ff i c i e n t m o d e l s i n t h e f i e l d s o f u n c e r t a in k n o w l e d g e e x p r e s s i o n a n d i n f e re n c e .i t h a s t h e f o l l o w i n g c h a r a c t e r i s t i c s : t h e e x p r e s s i o n f o r m o f g r a p h m o d e l , p a rt i a l a n d d i s t r i b u t e d s t u d y m e c h a n i s m a n d d i r e c t l y p e r c e i v e d i n f e r e n c e; a p p l i c a b l e i n e x p re s s i n g a n d a n a l y z i n g u n c e r t a in a n d p r o b a b i l ity t h i n g s a n d e ff i c i e n t l y r e a s o n i n g p a r t i a l , i n a c c u r a t e a n d u n c e r t a i n k n o w l e d g e o r i n f o r m a t i o n . i n t h e f i e l d o f g r a p h m o d e l a n d d a t a m i n i n g , t h e c e n t r a l i s s u e a n d d i ffic u l t p o i n t i s h o w t o l e a rn b a y e s i a n n e t w o r k s a n d t o a c c u r a t e l y e x p re s s v a l u a b l e i n f o r m a t i o n i n t h e d a t a t h r o u g h t h e e f f i c i e n t m e t h o d s a n d a l g o r i t h m . t h e l e a rni n g b a y e s ia n n e t w o r k s m a i n l y i n c l u d e s : s t r u c t u r a l a n d p a r a m e t e r l e a r n i n g , p a r a m e t e r s c a n b e fi x e d t h r o u g h n e t w o r k s s t r u c t u r e a n d d a t a s e t s , s o s t r u c t u r a l l e a rn i n g i s t h e c o re o f l e a rn i n g b a y e s i a n n e t w o r k . t h e e ff i c i e n t s t r u c t u r a l l e a rn i n g i s t h e b as i s c o n s t r u c t i n g t h e m o s t e ff i c i e n t n e t w o r k s t r u c t u re . t h e p a p e r i l l u s t r a t e s t h e d e v e l o p m e n t a n d t h e o re t i c a l b a s i s o f b a y e s i a n n e t w o r k s a n d t h e a p p l i c a t i o n o f c l as s i fi c a t i o n a n d p r e d i c t i o n , u n c e r t a i n r e a s o n i n g p r o j e c t a n d c a u s e a n d e ff e c t d a t a m i n i n g , e m p h a t i c a l ly s t u d y i n g b a y e s i a n n e t w o r k s l e a r n i n g t h e o r i e s ; i l l u s t r a t i n g t h e m a i n c o n t e n t s o f b a y e s i a n n e t w o r k s l e a r n i n g a n d i t s s t r u c t u r a l l e a rn i n g m e c h a n i s m . t h i s p a p e r r a i s e s a n e w m e t h o d o f d i s c r e t e b a y e s i a n n e t w o r k s s t r u c t u r a l l e a r n i n g b as e d o n p re d i c t i o n a b i l ity . t h e p re d i c t i o n a b i li ty i s t o p r e d i c t a c c u r a c y r a t e , s o t h e s a m e p r e d i c t i o n a b i l i ty i s s u ff i c i e n t a n d e s s e n t i a l t o c o n d it i o n i n d e p e n d e n c e , t h u s t h e i n t r o d u c in g o f p re d i c t i o n a b i l i ty c o m b i n e s t h e e x i s t e n c e a n d d i r e c t i o n o f a r c s a m o n g v a r i a b l e s . t h e m e t h o d h a s t h e f o l l o w i n g s c h a r a c t e r i s t i c s : le a r n i n g e ff ic i e n c y a n d a c c u r a c y a r e h i g h , t h e l e a rn i n g s t r u c t u re t e n d s t o b e s i m p l i fi e d , a v o i d i n g e x c e s s i v e c o m b i n i n g o f d a t a , a b l e - t o d e a l w i t h i n c o m p l e t e d a t a , u n n e c e s s a r y t o o r d e r v a r i a b l e s a n d w i t h t h e f u n c t i o n s o f r e s i s t i n g n o i s e d a t a . t h e t y p i c a l a p p l i c a t i o n o f t h e b a y e s i a n t h e o ry i s t h e c l as s i f y i n g s t u d y . i t d o e s n o t c l as s i f y a n o b j e c t i n t o a c e r ta i n c l as s a b s o l u t e l y , b u t c a l c u l a t i n g i t s p r o b a b i l i ty a n d th e c l a s s w i t h t h e g r e a t e s t p r o b a b i l i ty i s t h e o n e t h a t t h e o b j e c t b e l o n g s t o ; i n m a n y c as e s a l l p ro p e r t i e s in t h e b a y e s i a n c l as s i fi c a ti o n f u n c t i o n p o t e n t i a l l y , t h a t i s , o n e o r s e v e r a l p r o p e r t i e s c a n n o t d e t e r m i n e c l a s s i fi c a ti o n b u t a l l t h e p r o p e rt ie s a re i n v o l v e d i n i t .t h e p ro p e r t i e s o f b a y e s i a n n e t w o r k c l as s i fi c a ti o n c a n b e d i s c r e t e , c o n t i n u o u s a n d mi x e d . t h i s c l ass i fi e r c l ass i fi e r c l a s s i f i e r s c l a s s i f i e r p a p e r f u r t h e r s t u d i e s t h e t y p i c a l b a y e s i a n c l a s s i f i e r s , t h a t i s , n d v e b a y e s i a n ,t a n c ( t re e a u g m e n t e d n a iv e b a y e s a n ) c l as s i f i e r a n d b a y e s i a n n e t w o r k b ase d h a v e on ram e m d l . t h e o re ti c a l l y , b a y e s i a n n e t w o r k c l a s s i fi e r s a n d u n i o n i s b 盯e s i a n c l as s i fi c a t i o n a b i l i ty , t h e c o re o f re a l i z i n g b a y e s i a n n e t w o r k s t r u c t u r a l le a rn i n g . t h e e ff i c i e n t b a y e s i a n l e a rn i n g 13 a y e s i a n c l a s s i f i e r l e a rni n g m e c h a n i s m i s t h e b a s i s o f c o n s t r u c t i n g b a y e s i a n n e t w o r k c l a s s i fi e r . s t r u c t u r a l l e a r n i n g m e t h o d b a s e d o n p re d i c t i o n a b i l i ty f o r m s b a y e s i a n l e a rn i n g m o d e l . a c o n t r a s t i s h o ws v e e x p e r i m e n t w a s c o n d u c t e d o n u c i n e t wo r k n e t wo r k di s c r e t e n e t wo r k ma c h i n e d a t a . t h e e x p e r i m e n tt h a t t h i s me t h o d n c a n b e e ff i c i e n t l y h e l p f u l f o r b a y e s i a n c l a s s i f i e r l e a r n i n g a n d h i g h c l a s s i fi c a t i o n a b i l i ty . k e y w o r d s : b a y e s i a n n e t w o r k s ; s t r u c t u r a l l e a r n i n g ; p r e d i c t i o n a b i l i ty ; b a y e s i a n n e t wo r k cl a s s i f i e r 一究致t目使己立叽人 一移昭果砚沂环眺习 -研和彭而均.学或本 -饭目成翎廿-梢拒浏 -的注孙书献-用门 -油趁究日难-鲜盯乳 一行标邢证贡1卜使部阅 一进以濒或何习、关借 一下加加位任之留有和 一导别乳学的女佳口保家阅 一葬钻写衅啪也士卜况拍邪 一指特黔的做业乙关国查 一弓师中以构所，滩有向被 一明却叶、或砷幼:己又拜郎沐 一日导文熟机究头塑扮学并文 一以内表戮矜期刚找豹幻 一在了石育研州用大留论 -声劫除眯豹勾。月彭危侧阳 -本，瑟他对意亡心师权允 一l是知饭其志谢”jj.沈北有， 一性峨诊人够端准j丰反翻哪卜 一六1文所蜘或同示川川再用东学盘 一论我针学的表办级.文解大磁 一吐计特其瑞铂浸脚j嘴到硒 一创准据俐认非拼勃样论汀碗净 一学。鲜范工明洲二.洲全师件 一叙的果刚师同说名场完北印 一才万交成阿北一的签从j者东复 一呈究沙东我确者作.的 -沂研卜粉得与明咋文却文 本人声 工作及取得 谢的地方外 也不包含为 用过的材料 在论文中作 学位论 本学位 论文的规定 构送交学位 授权 东北师 据库进行检 学位论文。 ( 保密 学位论 日 -1 li a 户叫巨乙 指导教师签名: 日期: 学位论文作者毕业后去向: 工作单位: 通讯地址: 电话: 由 r 编: 引言 在海量的数据中蕴藏着大量有价值的信息，如何利用采用有效技术手段从数据中 获取对生产实践有价值的信息模型是k d d 研究的一个重要方面，而贝叶斯网络由于具 有图形化的模型表示形式、局部及分布式的学习机制、直观的推理;适用于表达和分 析不确定性和概率性的事物;能够对不完全、不精确或不确定的知识或信息中做出有 效的推理等特性，而成为目 前不确定知识表达和推理领域最有效的理论之一。 自 从5 0 -6 0 年代贝叶斯学派形成后， 关于贝叶斯分析的研究久盛不衰， 其中贝叶 斯网 络模型从1 9 8 8 年由p e a r l 提出 后，己 经成为近十几年来研究的热点。二十世纪 9 0 年代后期h e c h e r m a n 把贝叶 斯网 络用于 数据挖掘2 1 (3 1 ， 很快引 起了 人们的 关 注， 成 为研究的热点之一，用贝叶斯网络够有效地进行多变量的联合预测、因果推理、不确 定性知识表达、模式识别 、图象处理及因果数据挖掘。但贝叶斯网络在动态与静态、 集中与分布式数据处理和因果数据挖掘中的 潜力还没有充分的开发，贝叶斯网络理论 与应用问 题仍需要进一步深入研究。 一般贝叶斯网络的构建是首先由 相关领域的专家根据事物间的关系来确定出结构 模型， 即有向无环图， 然后再利用其它方法确定每个结点的条件概率， 但这样构建的网 络模型无法保证其客观性和可靠性。近年来国内外的 研究者们尝试引入客观的观测数 据，希望通过将观测数据与专家知识相结合来共同构建贝叶斯网络，并进一步在没有 专家先验知识的情况下，尝试完全从观测数据中学习得到网络结构和参数，生成贝叶 斯网络的方法。从而运用贝叶斯网 络模型来帮助人类对纷繁错杂、 浩如烟海的 无序型 信息进行准确的检索、归类、储存以及分析等工作，并为用户提供客观的信息。如何 通过有效的方法和算法利用现实数据构建的贝叶斯网 络，以 准确地表达蕴含在数据中 有价值的信息是目 前图形模式与数据挖掘领域中的研究的热点和难点。 目 前国内外许多学者和研究机构都对贝叶斯网络进行了深入的研究主要集中 在以 下几个方面:基于贝叶斯网络的学习; 基于贝叶斯网 络的 推理;基于贝叶斯网络的 应 用。在国内，清华大学对贝叶斯网络推理及其在数据挖掘等方面的理论及应用进行了 研究;重庆大学在贝叶斯网络学习与推理方法方面进行了理论研究，并对基于贝叶斯 网络的不确定知识处理方法进行了一定的研究。吉林大学对贝叶斯网络的构建和在数 据挖掘中 应用进行了 研究。 在国外有许多数据挖掘的研究机构和学者对贝叶网 络的学 习机制和应用进行了广泛深入的研究，以m i c r o s o f t 公司为代表的许多商业企业，在 此领域己有大量的投入，并推出了相关的商业化产品。随着贝叶斯网络理论与应用问 题的进一步深入研究，贝 叶斯网 络将成为智能化数据分析与处理的 最有效工具之一。 本 文 主 要 针 对 完 整 数 据的 贝 叶 斯 网 络 学习 机 制 进 行 研 究 ， 贝 叶 斯网 络 学习 主 要 包 括:结构学习和参数学习，通过网络结构与数据集可以确定参数，因此结构学习是学 习贝叶斯网络的核心，有效的结构学习方法和算法是构建最优网络结构的基础。结构 学习主 要有两种方法:一种是打分一 搜索方法如基于m d l标准4 1 6 1 的打分一 搜索函数的 算 法， 另 一 种是 依 赖分 析 方 法如c h e n g 一 e 三 阶段 算 法e 1 。 打分 一 搜 索方 法过 程 简单 规 范，但打分函数的运算复杂性和结构搜索空间的大小均随变量增加指数增长，因此一 般要求变量有顺序并进行局部贪婪搜索，或适用于变盘少而且在一定范围内的结构学 习;依赖分析方法过程比较复杂， 在一些假设下可以得到最优的贝叶斯网络结构，并 且可具有多项式复杂度。本文在研究变量之间的有条件和无条件相对预测能力的基础 上，给出一种新的离散型贝叶斯网 络学习方法， 解决离散贝叶斯网 络结构学习算法复 杂性随变量增加指数增长问题，建立多项式复杂度的贝叶斯网 络结构学习算法，从而 使网络结构的学习具有更高的效率和简洁性， 并进一步将该结构学习方法应用于贝叶 斯网络分类器结构学习。对贝叶斯网络的学习机制研究特别是离散变量的贝叶斯网络 结构学习有积极的意义. 第 1 章 贝叶斯网络概述 贝叶斯网络是用来表示变量间概率分布的图形模式，具有稳固的数学基础，贝叶 斯网络与其他知识表示形式如规则库、决策树、人工神经网络相比，具有图形化的模 型表示形式、局部及分布式的学习机制、直观的推理，适用于表达和分析不确定性和 概率性的事物等优点， 是人工智能的大部分领域， 包括因果推理、 不确定性知识表达、 模式识别和分类、聚类分析等应用的有效工具。 1 . 1 贝叶斯网络理论的起源与发展 贝 叶斯理论奠基性工作是由 十八世纪数学家和神学家r e v e r e n d t h o m a s b a y e s 的 论文 “ 关于几率性问 题求解的评论” ， 文章在其死后由 其朋友在1 7 6 3 年第一次发表7 在图形方面， 人们很早以前曾经利用过有向无环图表示法。 最先， 1 9 3 0 s 遗传学家 s e w a l l w r i g h t 提出了一种叫路径分析的 表示因 果关系的图形化方法， 这后来成为了 经 济学、 社会学、 心理学方面对于因果模型的固定的表示。 g o o d 曾经用有向 无环图 来表 示有分布式原因的二值变量所组成的因果关系网。影响图则代表了为了 进行决策分析 而发展的另一类有向无环图的应用，他们包括了事件结点和决策结点.有向 无环图在 这些应用中的主要作用是提供一个对于概率函数有效的描述。一旦网络配置完成，随 后的所有计算都可以 通过概率表达式的符号操作来完成。 1 9 8 2 年， p e a r l 开始注意到有 向无环图可以作为一种计算结构，并因此可以 作为一种认知行为模型。他通过一个分 布 式 方 案 示 范 了 一 个 树 状 网 络 的 概 率 更 新 。 目 的 是 为 了 对 于 阅 读 理 解 的 分 布 处 理 进 行 建 噶 。 其 中 ， 自 上 而 下 和自 下 而 上 的 推 理 被 结 合 起 来 以 形 成 一 致 的 解 释 。 这 种 双 重 推 理模型是贝叶斯网络更新的核心， 这也是贝叶斯理论的中心思想。 “ 贝叶斯网络” 这一术语是在 1 9 8 8 年由p e a r l 在论文中提出的，奠定了贝叶斯网 络的理论基础，早期的应用主要在专家系统中用于不确定性知识表示和推理7 1 。二 二 十 世纪9 0 年代后期h e c h e r m a n 把贝叶 斯网 络用于数据挖掘， 由 于贝叶斯网 络具有独特的 不确定表达形式、丰富的概率表达能力、综合先验知识的增量学习特性成为数据挖掘 众多方法中研究的热点之一。 1 . 2 贝叶斯网络 1 . 2 . 1 贝叶斯网络的描述 贝叶斯网络是基于概率推理的数学模型，所谓概率推理，就是通过一些变量的信 息 来获 得 其它 变 量的 概 率 信息的 过 程。 假定 有随 机 变量 集合x= 戈, x 2 , . ., x n ， x ， 表 示x的取值。 表达式ax, = xx 2 = x z ,. ., x = x . ) 表示一个联合概率，即 变量 x 1 , x z ,., x的 值分 别 是xx 2 , . ., x o 时的 概率。 从 理 论 上 讲， 给定 一 个随 机 变量 集 合的 完全联合概率函数，就能计算所有的边缘概率和更低阶的联合概率。 但是当有一个很 大的随机变量集合时，指定所有的联合概率或更低阶联合概率的任务就难于处理了 ( n p难题) 。 幸运的是，在大多数应用中， 联合概率都满足一定的条件， 这些条件可 以简化运算量，使得对它们的指定和计算变得可行。 可 以按 照 一 个 条 件 概 率 链 表 达 一个 联 合 概 率 ，其 一 般 形 式 为 p ( x , , x 2 , . , x) 一 rl p ( x r i x., x ;_ , )通 常 将 其 称 为 链 规 则 ， 贝 叶 斯 网 络 采 y = 1 用图 形化的网络结构直观地表达变量的联合概率分布及其条件独立性，这对概率推理 是非常有用的，因为用贝叶斯网络表示的条件独立性能大量地节约概率推理计算。 一 个贝叶斯网 络是一个有向 无 环图( d i re c t e d a c y c l i c g r a p h , d a g ) ， 由 代表变量结 点及连接这些结点的有向边构成。 用符号b ( g , p ) 表示一个贝叶斯网 络， b ( g , p )由 两部分构成: (1 ) 一个具有n个结点的 有向 无环图， 图中的结点代表随机变量， 结点间的 有向 边代表了 结点间的相互关联关系。结点 变量可以 是任何问 题的 抽象用以 代表属性、 状 态、客体、命题或其它的实体，如测试值、观测现象等。 结点之问的有向 边( 弧) 反映了 变量间的依赖关系， 指向 结点x的所有结点称为x 的 父结点。 尽管 从结 点x指向 结 点y的 弧 频繁 地被 用 来表 示x引 起了y ， 但 在贝 叶 斯 网络里这不是对弧的唯一解释。 例如， y可能只与x有关联， 但是它不是由x引起的。 因此，虽然贝叶斯网络可以 表示因果关系，但它们并不局限于表示因果关系。除了被 称为贝叶斯网络外，它还有另一些术语通常认为有向 边表达了一种因果关系，故贝叶 斯网络有时叫做因果网 ( c a u s a l n e t w o r k ) 。重要的是， 有向图蕴涵了条件独立性假设， 贝 叶斯网 络 规定图中的 任一结点x 条 件独立于由x , 的 父结点 给定的 非x , 后代结点构 成的 任何结点 子集， 即 如果用a( 戈) 表示非x ， 后代结点构 成的 任何结点 子集， 用几 表 示 变量戈的 父 结点 集， )r , ( 或p a ; ) 表示n ， 的 配 置 情况， p a ; 表示 某一 具 体的 配置。 对 每一 个x将有 一 个子 集n , c : 戈， ., x ;- i 使得戈与a( x ; ) = 戈， ， 戈- , ) r i ， 在给 定 n的 前 提 下 是 条 件 独 立 的 。 那 么 ， 对 任 意 的 x 将 有 a x i i x ., x ,- , ) 一 a x i j 因此，有 p ( x ) = na x ; 民 ) 这 里 变 量 集( n. ., r l ) 对 应 着贝叶 斯网 络的 父 结点( p a . . . p a . ) . ( 2 ) 一 个与 每 个结点 相 关的 条 件 概 率 表( c o n d it io n a l p r o b a b i l it y t a b l e , c p t ) 。 条 件 概 率 表 可 以 用a x i 二 ， ) 来 描 述 ， 它 表 达 了 结 点 同 其 父 结 点 的 相 关 关 系 一 条 件 概 率 。 没有任何父结点的结点概率为其先验概率。因为有了结点及其相互关系、 条件概率表， 故贝叶斯网络可以表达网络中所有结点 ( 变量)的联合概率分布。 1 . 2 . 2 贝叶斯网络的构造实例 构造贝 叶 斯网 络 ( 先验贝 叶 斯网 络) 一 般分为 三个步 骤 ( 1 ) 确定 变量集和变量域， ( 2 ) 确定网 络结 构， ( 3 ) 确定局部 概率分布。 以 信 誉卡欺骗问 题为例说明 如何 构造贝叶斯 网络。 ( 1 ) 确定变量集和变量域 分别用f 表示是否当前的交易是欺骗性的， g表示是否在2 4 小时内 有一个汽油交 易， j 表示是否在2 4小时内 有一个珠宝交易， a表示信誉卡持有者的年龄，s 表示性 别。变量的状态如图1 . 1 所示。 ( 2 ) 确定网络结构 方法一:根据变量之间的条件独立性确定弧的存在性，根据变量之间条件相对预 测能力 ( 或条件相对互信息)确定弧的方向。比如 p ( a f ) = p (a ) ， p ( s f , a ) = p ( s ) p ( g f , a , s ) = p ( g ! f ) p ( .1 i f , a , s , g ) = p ( j ! f , a , s ) 方法二 方法三 用户根 据变量之间的因 果关 系( 根 据用户的已 有知识 ) 来建立网 络结构。 方法一与方法二结合使用。 ( 3 )确定局部概率分布 方法一:根据先验知识确定局部概率; 方法二:根据实验数据确定局部概率; 方法三:结合专家知识和实验数据确定局部概率等。 贝叶斯网络举例: 下面给出 信誉卡欺骗问题贝叶斯网 络例子。 分别用f , g s j , a , s 表示是否当前的交易 是欺骗性的，是否在2 4 小时内有一个汽油交易，是否在2 4 小时内有一个珠宝交易， 信誉卡持有者的年龄和性别。变量的状态如图1 . 1 所示。 p ( a _ 3 0 ) = 0 .4 0 p ( s 二 m a l e ) 二 0 . 5 p ( j = y e s i f = y e s , a = * , s = * ) = 0 .0 5 p ( .1 = y e s i f 二 n o , a -5 ; 3 0 , s = m a l e ) 二 0 .0 0 1 p ( i = y e s i f = n o , 3 0 5 a :5 5 0 , s = m a l e ) = 0 . 0 0 0 4 p ( i = y e s i f = n o , 5 0 5 a , s = m a l e ) = 0 . 0 0 0 2 p ( i = y e s i f = n o , a 5 3 0 , s = f e m a l e ) 二 0 .0 0 0 5 p ( g 二 y e s f = y e s ) = 0 .2 p ( i = y e s i f = n o , 3 0 5 a 5 5 0 , s = f e m a l e ) = 0 . 0 0 2 p ( g = y e s i f = n o ) = 0 .0 1 p ( j = y e s i f = n o , a 5 5 0 , s = f e m a l e ) 二 0 .0 0 1 图 1 . 1信誉卡欺骗问题贝叶斯网络 1 . 2 . 3贝叶斯网络的类型 1 . 离散型贝叶斯网络 如果构成贝叶斯网络的结点变量是离散的且取有限个值，那么，这种贝叶斯网络就称 为离散型贝叶斯网 络。目 前主要研究的 就是这种贝叶斯网 络a z . 连续型贝叶斯网络 如果构成贝叶斯网络的结点变量是连续的变量， 那么， 这种贝叶斯网络就称为连 续型贝叶斯网络。 3 . 混合型贝叶斯网络 如果构成贝叶斯网络的结点变量既有连续变量又有离散变量， 那么， 这种贝叶斯 网络就称为混合型贝叶斯网络。 1 . 2 . 4贝叶斯网络的优点 贝叶斯网络与数据挖掘中的其他知识表示的方法如规则表示、决策树、人工神经 网 络等相比，贝叶斯网 络在知识表示方面惧有下优点洲 。 1 . 贝叶斯网络能够真正有效的处理不完整数据。 例如考虑具有相关关系的多个输 入变量的分类或回归问题，对标准的监督学习算法而言，变量间的相关性并不是它们 处理的关键因素， 当这些变量中有某个缺值时， 它们的预测结果就会出现很大的偏差。 而贝叶斯网络则提供了较为直观的概率关联关系。 2 .贝叶斯网络和其它技术相结合能够进行因果分析。 在数据分析中， 因果关系有 利于对领域知识的理解;在干扰较多时，便于做出精确的预测。 3 . 贝叶斯网络能 够使先验知识和数据有机的结合。 任何从事过实际建模任务的 人 都 会知 道先 验信 息或 领 域知 识 在建 模方 面的 重 要 作 用， 尤 其 是 在样 本 数 据 稀 疏或 数 据 较难获得的时候。贝叶斯网络用弧表示变量间的依赖关系，用概率分布表示依赖关系 的强弱，将先验信息与样本有机结合起来。 4 .贝叶斯网络能够有效的避免对数据的过度拟合。 1 . 3贝叶斯网络的应用 1 . 3 . 1 贝叶斯网络用于分类和回归分析 分类规则发现是根据客体的特征向 量值及其他约束条件将其分到某个类别中。 在 数据挖掘中主要研究如何从数据或经验中学习这些分类规则。贝叶斯网络是解决不确 定分类问 题的 有效工具， 研究主要集中 在如何从数据中学习特征向 量的分布、特征向 量的相关性从而获得准确分类信息， 成功模型有: 朴素贝叶斯分类器、贝叶斯网 络分 类器、贝叶斯神经网络分类器等。目 前，这些分类方法已 经在文本分类、字母识别、 经济预测等领域获得了成功应用。 1 . 3 . 2 用于不确定知识表达和推理 贝叶斯网络是随机变量间的概率关系的图形表示。近年来，贝叶斯网络已经成为 专家系统中不确知识表示的主要方法，并且涌现出大批的从数据学习贝叶斯网络的算 法6 。利用已 知或学得贝叶斯网 络进行推理的过程，是指在给定一个贝叶斯网络的模 型的情况下，根据己知条件，利用贝叶斯概率中的条件概率的计算方法，计算出所感 兴趣的查询结点发生的概率、在贝叶斯网络推理中，主要有以下两种推理方式: 因果推理:是由原因推结论，也称为由顶向下的推理 ( c a u s a l o r t o p - d o w n i n f e r e n c e ) ，目 的是由原因推导出结果己 知一定的原因 ( 证据) ， 则用贝叶斯网络的推 理计算，求出在该原因的倩况下结果发生的概率。 诊断推理:结论推知原因，也称为由底向 上的推理 ( d i a g n o s t i c o r b o t t o m - u p i n f e r e n c e ) ，目 的是在己 知结果时，找出产生该结果的原因、己 知发生了某些结果， 根据贝叶斯网络推理计算，得到造成该结果发生的原因和发生的概率、该推理常用在 病理诊断、故障诊断中，目的是找到疾病发生、故障发生的原因。 1 . 3 . 3 在因果数据挖掘上的应用及展望 近年来， 研究人员利用因果贝叶斯网 络的理论， 研究因果关系的发现。 c o o p e r e 在 1 9 9 7年提出了一种简单易行的因果关系挖掘算法该算法通过假定己知一个非结果 结点，利用贝叶斯网 络结构的性质， 对数据集进行搜索，找出 满足条件的因果关系， s i l v e r s t e i n 在 1 9 9 8 年尝 试了 大型事物数据库的 挖掘。目 前因果 数据挖掘的 研究仍 然处于理论阶段， 仅有少 量实际 应用， 这是由 于贝 叶 斯网 络结构学习 理论的 发展是 在 一个相对单纯的数据背景下进行的，与数据挖掘所面临的情况不同，直接将这些算法 应用到环境复杂的数据挖掘应用中，往往难以得到有意义的结果;同时，数据挖掘本 身是一 个人机交互的多步过程，需要前处理、算法和后处理相结合才有可能得出 有意 义的结论。另一方面，因果关系挖掘是对于数据中比 统计关联规则更高层次的因果知 识的发现，因此，如果能够在统计关联挖掘结果的基础上进行因果关系的挖掘， 就能 借用前者的成果，在己经加工处理过的信息的基础上，进一步精炼，得到更深层次的 因果信息 ， 因此成功的因果数据挖掘应是以贝叶斯网络结构学习理论为核心， 将算法 根 据数据挖掘的要求进行改进， 并与前处理相结合， 同时将可控试验与后处理相结合， 并与操作人员进行合理恰当的交互，从而达到最终发现因果关系的目的，由于因果知 识能提供关于事物的本质的认识， 对干涉的结果作出预测， 因此因果挖掘有望在医学、 经济、网络领域中获得巨大的成功。 1 . 3 . 4 用于聚类模式发现 数据聚类分析是一个正在蓬勃发展的领域， 所涉及的领域包括: 数据挖掘、 统计学、 机器学习等。 根据应用所涉及的数据类型、 聚类的目的以 及具体应用要求来选择合适的 聚类方法。通常聚类分析方法有:划分方法、层次方法、基于密度方法、基于网络方法 和基于模型方法， 其中基于模型的方法是为每个聚类假设一个模型， 再去发现符合模型 的数据对象， 试图将给定数据与某个数学模型达成最佳拟合， 神经网络中的s o n、 统计 学聚类和l v q 属于此类方法， 一个基于模型的算法可以 通过构造一个描述数据点空间分 布的密度函数来确定具体聚类， 贝叶斯方法是一种通过综合先验模型知识和当前的数据 特点来构造最优的聚类模型。 a u t o c l a s s 0 z . 是利用贝叶斯方法进行聚类的一个典型系 统。 以_ l 是贝叶斯网络的几个典型应用， 然而其应用远不止这些，比如贝叶斯网络与神 经网络相结合的贝叶斯神经网 络，贝叶斯网络与统计学习相结合的贝叶斯点机等。 1 .4贝叶斯网络学习的 前提假设问魔 1 . 4 . 1 数据完整性假设 表明数据集中不存在缺失项， 对于存在缺失项的情况， 人们提出了三种解决方法第 一种是抛弃存在缺失项的数据，这样会造成两个问题，一是会引起数据集变小，可能造 成统计样本不够， 二是可能这些缺失项的出现不是随机的， 抛弃这些数据项会使得数据 集无法正确反映实际; 第二种方法是给缺失的值赋一个特定的值，如 “ 有” 或 “ 无” 这 样有可能改变底层的统计关系; 第三种方法是给缺失的值赋一个恰当的值， 最好与原值 近似， 有许 多方法来指派丢失 数据项f r i e d m a n 0 将e m 算法与 模型 选择相结合实 现了 缺失项估计和结构学习。 c h i c k e r i n g a 用近似评价函 数来处理缺失项。 1 . 4 . 2 无选择偏好假设 无选择偏好假设表明该数据集是对于实际总体的无偏采样。 匹兹堡大学的 g r e g o r y f . c o o p e r 在2 0 0 0 年提出了一种存在选择偏好情况下的贝叶斯网络学习算法该算法。通 过在有向图中引入一个新的变量结点s 来表示具体的数据点是否会被采样到， 并在那些 会影响采样的变量结点与 s之间建立有向边来表示他们对于采样的影响 。通过对于这 样一个修正网络的学习，从理论上就能避免选择偏好的影响。 1 . 4 . 3 变量离散化假设 许多算法都有变量离散化假设， 即假设所面临的变量都是离散变量，对于实际系统 中 存在连续变量的情况， 可以 直接采取离散化的方法， 如f r i e d m a n 和g o l d s z m i d t 在1 9 9 6 年提出根据评价函数来自 动确定离散化的门限值，并将此将连续变量离散化， 也有研究 人员尝试直接对于连续变量的贝叶斯网络或混合有连续变量和离散变量的网络结构进 行 学习h e c k e r m a n 和 g e i g e r 在 1 9 9 5 提出 的 贝 叶 斯 评 价标 准能 够 处 理离 散和 高 斯 连 续分布情况下网络结构的评价问题，从而能够对连续和混合贝叶斯网络结构进行学习 1 9 9 6 年 r . h o f m a n n 和 v . t r e p 利用非线性 条件密 度估计来学习 连续 变量的 条 件概率， 从而学习贝叶斯网络结构， 1 9 9 7 年 s m o n t i 和 g.f c o o p e r 提出 通过人工神经网 络 来估计条件密度以 学习 连续变量的贝叶斯网 络结构。 上面这些方法较好地处理了 连续变 量的贝叶斯网络结构的学习问题。 在贝叶斯网络结构学习中， 人们发现算法的许多假设在实际中 常常无法满足因此， 研究人员放松贝叶斯网 络结构学习的前提假设， 尝试在更一般的情况下进行贝叶斯网 络 结构的学习。 1 . 5 国内外研究现状 在国内， 清华大学对贝叶斯网 络推理及其在数据挖掘等方面的理论及应用进行了 研 究; 重庆大学在贝叶斯网络学习与推理方法方面进行了 理论研究， 并对基于贝叶斯网 络 的不确定知识处理方法进行了 一定的研究。 吉林大学对贝叶斯网 络的构建和在数据挖掘 中应用进行了研究。 目前国外许多学者和研究机构都对贝叶斯网络进行了深入的研究主要集中在以下 几个方面: ( 1 )基于贝叶斯网络的推理; ( 2 )基于贝叶斯网络的学习: ( 3 )基于贝叶斯网络的 应用; ( 吐 )数据挖掘中贝叶斯网络建造。 国际上许多的大的企事业在此领域也有大量的投入，如 m i c r o s o f t推出了基于 w 工 n d o w s的 b b n工具， 这个工具我们可以从 w e b上下载;r i g h t p o 工 n t公司开发和销售 d a t a c r u n c h e r ” 数据挖掘工具， 是其实时营销系统中的一个模块， 其中的一些算法也 基本上基于贝叶斯网络的。 i t 第2 章 贝叶斯网络学习 学习贝叶斯网就是要寻找一种网络，能按某种测度最好地与给定实例数据集拟合。 就一般意义而言，寻找一种网络包括寻找一种有向无环图( d a g ) 结构和获得与 d a g中每 个结点相关的条件概率表( c p t ) 。前者称为网络结构学习，后者称为网络参数学习。由 于通过网络结构与数据集可以 确定参数