（计算机软件与理论专业论文）基于互信息的bayes网络分类器的构建.pdf

基于互信息的l t a y e s 网络分类器的构建 摘要 数据挖掘又称数据库中知识发现( k d d ) ，是从数据集中识别出有效的、新颖 的、潜在有用的，以及最终可解释的模式的非平凡过程，是一种从原始数据中获 取隐含信息的工具之一。它的主要功能包括分类预测、关联规则、聚类、时序分 析等。b a y c s 网络是分类预测的成功模型之一。本文讨论的是如何建构b a y e s 网 络分类器的问题，其主要研究内容和创新如下： 首先，本文从b a y e s 网络的基本理论出发，在国内外相关工作的基础上，发 现建构b a y e s 网络存在若干闯题。第一，要想得到准确的b a y e s 网络结构，即要 得到很好的符合数据库中数据信息的b a y e s 网络结构。需要用户指定参数，这对 用户来说是比较困难的：第二，耍自动找到一个最佳的网络结构是一个n p 难题。 第三，通过不断修改网络参数来建构b a y c s 网络结构，是一个漫长的过程。针对 这些问题，本文提出了在没有用户参与的情况下，仅仅根据数据库中数据信息， 以s h a n n o n 信息论为依据，用互信息作为衡量两个随机变量间的依赖程度的测 度，快速建构准确的b a y e s 网络结构的思想。 然后，分别针对不同的情况，提出三个建构算法： 1 ) 提出了当描述数据的属性均为离散取值时，用互信息衡量属性间的依赖关 系，建立b a y e s 网络结构的朴素b n c 算法。 2 ) 提出了e b n c 算法。e b n c 算法引进g i n i 系数，用它对连续取值的随机 变量的取值进行最优二分，使之离散化。然后再运用朴素b n c 算法对经 过预处理的属性集建构网络。 3 ) 提出了o s b n c 算法。o s b n c 算法用h b n - t r e c 记录数据流中的有用信 息。使得算法能够在只扫描一遍数据库的基础上，创建b a y c s 网络结构。 如果在数据流上开标记窗口，则o s b n c 算法可以用来处理数据流。 最后本文用u c i d a t a 测试数据对上述三种算法进行了实验和性能分析，和同 样不需要领域专家参与的决策树分类算法进行了比较，发现本文算法的准确性在 大多数情况下要好于决策树。且速度也较之要快。同时实验也证实了o s b n c 算法可以运用在数据流模型中。 关键词：数据挖掘，分类，b a y c s 网络，数据流，互信息 分类号：t p 3 1 1 复旦大学硕士学位论文 基于互信睡的b a y c s 网络分类嚣的构建 a b s t r a c t d a t am i n i n g , a l s ok n o w na sk n o w l e d g ed i s c o v e r yi nd a t a b a s e s ，i san o n t r i v i a l p r o c e s s e x t r a c t i n gv a l i d ，n o v e l ，p o t e n t i a l l yu s e f u la n df i n a l l ye x p l i c a b l ep a t t e r n sf r o mi a r g ea m o u n t so f d a t a i ti so n eo f t h et o o l sg e t t i n gi m p l i c i ti n f o r m a t i o nf r o mr a wd a t a ，n 他m a j o rf u n c t i o n so f d a t a m i n i n gi n c l u d ec l a s s i f i c a t i o na n dp r e d i c a t i o n ，a s s o c i a t i o nr u l e s ，c l u s t e r i n g 。t i m es e r i e sa n d s oo n ， a m o n g w h i c hb a y e s i a nn e t w o n ki so n eo ft h es u c c e s s f u lm o d e l si nc l a s s i f i c a t i o na n dp r e d i c a t i o n f i e l d s n l i sp a p e rf o c u s e so nh o wt ob u i l dt h eb a y e s i a nn e t w o r kc l a s s i f i e r t h em a i nr e s e a r c h w o r ka n di n n o v a t i o ni nt h ep a p e ra r ea sf o l l o w s ： f i r s t ，t h ep a p e rd i s c u s s e ss e v e r a le x i s t i n gp r o b l e m si nt h ec o n s t r u c t i o no f b a y e s i a nn e t w o r k s b a s e do nt h ef o u n d a t i o nt h e o r yo f b a y e s i a nn e t w o r k sa n dr e l e v a n tr e s e a r c hw o r k si nt h ef i e l d i ti s v e r yd i f f i c u l tf o rt h eu s e r st oa s s i g nt h e 脚a t e r s ，w h i c hi s o n eo ft h ei m p o r t a n ts t e p st o c o n s t r u c ta ne x a c tb a y e s i a nn e t w o r k i na d d i t i o n i ti san p - h a r dp r o b l e mt of i n dt h eb e s tb a y e s i a n n e t w o r ka u t o m a t i c a l l y m e a n w h i l ei tc o s t sal o n gt i m et os e tu pt h eb a y e s i a nn e t w o r kb y g r a d u a l l y m o d i f y i n gn e t w o r kp a r a m e t e r s t h u s 。w es u g g e s tt h eb a y e s i a nn e t w o r kt h a tc o u l db eb u i l tq u i c k l y a n da c c u r a t e l yb yu s i n gm u t u a li n f o r m a t i o nt om e a s u r et h ed e p e n d e n c eo ft w or a n d o mv a r i a b l e s a c c o r d i n g t os h a n n o n si n f o r m a t i o n t h e o r yi nt h i sp a p e r t h e d w ep r o p o s et h r e ea l g o h t h m st of i td i f i e r e n ts i t u a t i o n s ： 1 1t h en a t i v ea l g o r i t h mb n c w h e na l lv a l u e so ft h ea t t r i b u t e s d e s c r i b i n gt h ed a t aa r c d i s c r e t e , b n c w h i c hm e a s u r e st h ed a p c n d e n c eb e t w e e nt w or a n d o mv a r i a b l e st h r o u g h m u t u a li n f o r m a t i o n ，c a nh eu s e dt oc o n s t r u c tb a y e s i a nn e t w o r k s 2 ) t h e e x t e n d e da l g o r i t h me b n c i n t r o d u c i n g g i n ir a t i o ，e b n cf i r s tf i n d sab a s ts p l i tf o r e v e r yc o n s e c u t i v ea t t r i b u t e st od i a c r a t i z et h e m t h e ni ta d o p t sn a t i v ea l g o r i t h mb n c t o s e tu pt h en e t w o r kf o rt h e s ep r o - p r o c 船s e da t t r i b u t e s 3 1t h eo n c b - s g a r la l g o r i t h mo s b n c u t i l i z i n gh y p e rb a y e s i a nn e t w o r k ( h b n ) t r e et o r e c o r dt h eu s e f u l n f o r m a t i o no fd a t ai nd a t a b a s e o s b n cc 卸b u i l db a y e s i a nn e t w o r k s o n l ys c a n n i n gd a t a b a s eo n c e 1 na d d i t i o n 、0 s b n cc a r ld e a lw i t hd a t as t r e a mi f1 a n d m a r k w i n d o w so nd a t as t r e a ma r ci m p o s e d f i n a l l y , w ea n a l y z ea n de x p e r i m e n tt h e s et h r e ea l g o r i t h m st h r o u g ht h ed a t ai nu c i d a t a c o m p a r i n g t h er e s u l t so f a l g o r i t h m sp u tf o r w a r di nt h ep a p e r t ot h o s eo f d e c i s i o n 臼e em e t h o dt h a t a l s on e e d n 。tt h ea t t e n d a n c eo ff i e l de x p e r t s ，w ef i n dt h a ti nm o s tc a s e s 。o u ra l g o r i t h m sa r em o r o a o c u r a t ea n df a s t e rt h a nd e c i s i o nt r e e m e a n w h i l e t h ee x p e r i m e n t sa l s oc o n f i r mt h a to s b n cc a n b e u s e di nd a t as t r e a mm o d e l s k e yw o r d s ：d a t am i n i n g , c l a s s i f i c a t i o n ，b a y e s i a nn e t w o r k 。d a ms t r e a m ，m u t u a li n f o r m a t i o n 复旦大学硕士学位论文 基于互信息的b a y e s 网络分类器的构建 1 1 数据挖掘简介 第一章绪论 计算机和通讯技术的发展，使得我们这个社会越来越依赖信息，而大多的信 息都以最原始的方式数据存在。如果数据可以看作是人们记录的事实，则信 息就是数据中暗含的一组规则，或者说是期望。在过去的数十年中，随着网络和 存储技术的发展以及条形码在大部分商业产品中的广泛应用，我们产生、收集和 存储数据的能力已经迅速提高。这一切将我们淹没在数据的海洋中。而“丰富的 数据与贫乏的知识”问题也日益突出。不同领域的人们都期待着从这些数据中得 到自己想要的答案，将数据转化为信息，从数据的矿山中找到蕴涵的知识金矿。 例如，假设你是一位电话公司的地区销售经理，你负责处理与公司的蜂窝电 话客户之间的关系。你现在关心的问题是如何吸引客户的注意力，因为这问题已 经严重影响了一个公司的利润。你明白留住一个客户所花的代价比吸引一个离开 的客户重新回来的代价少的多，所以你必须想一个回报率比较高的方法。 传统的解决这一问题的方法是挑出那些付很多钱给公司的重要客户，说服他 们续签一年的服务合同。为了达到目的，可能要送某种礼物或提供电话费打折 的优惠政策。但这种办法很浪费，因为很多重要客户即使没有得到昂贵的礼物也 会继续留下来。要重视的是那些想要离开的重要客户。如果我们可以从用户数据 中得到那些想要离开的客户的信息，我们就可以给公司带来一大笔利润。 数据挖掘正是这样一种从数据中挖掘信息的工具，它集数据收集、数据清理、 降维、规则规约、模式识别、数据结果分析及评估、可视化输出等多种过程于一 身，是数据库技术、人工智能、机器学习、神经网络、统计学、模式识别、知识 库系统、知识获取、信息检索、高性能计算和数据可视化相结合的产物。它出现 予2 0 世纪8 0 年代后期，9 0 年代有了突飞猛进的发展，并可望在新千年中继续 繁荣。实际上，世界5 0 0 强企业中的8 0 都涉足数据挖掘的前瞻性研究或拥有 一个或多个数据挖掘产品系统。它们帮助企业进行客户关系管理，减少不必要的 投资，提高资金周转和回报：帮助人们迅速获取所需的知识和信息。提高工作效 率，改进服务质量。 数据挖掘通常又称数据库中知识发现( k d d ) 。该术语于1 9 8 9 年提出，f a y y a d 将其定义为“k d d 是从数据集中识别出有效的、新颖的、潜在有用的，以及最 终可解释的模式的非平凡过程”【l 】。数据挖掘过程一般包括以下七步： 复且大学硪：e 学位论文 基于王信息的b a y e s 网络分类器的构建 1 ) 数据清理：用于消除噪声或不一致数据： 2 ) 数据集成：可将多种数据源组合在起； 3 ) 数据选择：从数据库中检索、分析并选出与任务相关的数据； 4 ) 数据变换：将数据变换或统一成适合挖掘的形式： 5 ) 数据挖掘：这是基本步骤，即使用智能方法提取数据模式： 6 ) 模式估计：根据某种兴趣度度量，识别出表示知识的真正有趣的模式； 7 ) 知识表示：使用可视化和知识表示技术，向用户提供最终挖掘的知识。 数据挖掘可以在众多的数据库上进行，包括关系数据库、数据仓库、事务数 据库、面向对象的数据库、对象一关系数据库、空间数据库、文本数据库和多媒 体数据库、异种数据库和遗产数据库以及w w w 。 数据挖掘的任务一般可分为描述和预测两类，其中描述性数据挖掘任务刻划 数据库中数据的一般特性预测性数据挖掘任务在当前数据上进行推断，以进行 预测。而数据挖掘的功能指定了数据挖掘任务中要找的模式类型，包括； 1 ) 特征化和数据区分：数据特征化是指且标类数据的一般特征或特性的汇 总，而数据区分是将目标类对象的一般特性与一个或多个对比类对象的 一般特性比较。通过这两种方法可以获得类，概念描述。 2 ) 关联分析：关联分析发现关联规则，这些规则展示属性一值频繁的在给 定数据集中一起出现的条件。 3 ) 分类和预测：分类是找出描述并区分数据类或概念的模型，以便能够使 用模型预测类标签未知的对象类的过程。当被预测的值是数值数据时， 通常称之为预测。 4 ) 聚类分析：聚类分析数据对象，并根据最大化类内的相似性，最小化类 间的相似性的原则进行聚类或分组。 5 ) 孤立点分析：孤立点分析找出数据库中可能包括的与数据的一般行为或 模型不一致的数据对象。 6 ) 演变分析：数据演变分析描述行为随时间变化的对象的规律或趋势，并 对其建模。 数据挖掘系统可以按照如下的标准分类： i ) 根据挖掘的数据库类型分类：例如，根据数据模型分类，有关系的、事 务的、面向对象的、对象一关系的和数据仓库的数据挖掘系统；根据所 处理的数据的特定类型分类，有空问的、时间序列的、文本的、多媒体 的和w w w 数据挖掘系统。 2 ) 根据挖掘的知识类型分类：即根据数据挖掘的功能分类，可分为特征化、 区分、关联、分类、聚类、孤立点分析、演变分析、偏差分析、类似性 复旦大学颀t ：学位论文2 基于五信息的b a y e s 网络分类器的构建 分析以及它们的集成数据挖掘功能的数据挖掘系统。 3 ) 根据所用的技术分类；这些技术可以根据用户交互程度( 如自动系统、 交互探查系统、查询驱动系统) ，或所用的数据分析方法( 如面向数据库 或数据仓库的技术、机器学习、统计学、可视化、模式识别、神经网络 等) 描述。 4 ) 根据应用分类：例如适合金融、电信、d n a 、股票市场、e m a i l 等的数 据挖掘系统。 数据挖掘中的主要问题如下： 1 ) 数据方法和用户交互问题：它反映所挖掘的知识类型、在多粒度上挖掘 知识的能力、领域知识的使用、特定的挖掘和知识显示。 2 ) 性能问题：包括数据挖掘算法的有效性、可伸缩性和并行处理。 3 ) 关于数据库类型的多样性问题：包括关系的和复杂的数据类型处理，在 异种数据库和全球信息系统中挖掘信息等。 1 。2 分类简介 分类是数据挖掘的主要问题之一，是一种数据分析形式，可以用于提取描述 重要数据类的模型或预测未来的数据趋势。机器学习、专家系统、统计学和神经 生物学方面的研究者早已提出许多分类方法，但是，大部分算法通常只能处理少 量数据。最近数据库挖掘研究在这些工作之上，开发了能够处理大量数据的可伸 缩的分类方法。这些方法通常考虑并行和分布式处理。 数据分类是一个两步过程：第一步建立一个模型来描述预定的数据类集或概 念集；第二步使用模型进行分类。假设有一个由属性描述的数据库，其中有一个 属性称为类标签属性，它描述每一个元组属于的一个预定义的类，其它属性称为 决策属性。数据库中的每一个元组又称为样本、实例或对象。分类算法通过分析 数据库中的元组集合构造模型，这些被分析的元组组成训练数据集，而其中每一 个元组称作训练样本。 分类具有广泛的应用，包括信用证实、医疗诊断、性能预测和选择购物等。 分类的基本技术包括决策树规约、朴素b a y e s 分类和b a y e s 网络、神经网络。除 了这些基本的技术之外，其它的分类方法还有k 最近分类。基于案例的推理、遗 传算法、粗造集和模糊逻辑技术等等。在众多分类方法中，b a y e s 网络以其易于 理解、架构和准确性高的特点吸引很多研究人员的视线。 复且大学硕士学位论文 基于互信息的b a y e s 网络分类器的构建 1 3b a y e s 网络在数据挖掘中的应用 b a y e s 网络是用来表示向量间联合概率的图形模式，它提供了一种自然的表 示因果信息的方法，用来发现数据间的潜在关系。在这个网络中，用节点表示变 量，有向边表示变量间的依赖关系。b a y e s 理论给出了信任函数在数学上的计算 方法，具有稳固的数学基础，同时它刻画了信任度与证据的一致性以及信任度随 证据而变化的增量学习特性；在数据挖掘中，b a y e s 网络可以处理不完整和带有 噪声的数据集，它用概率测度的权重来描述数据间的相关性，从而解决了数据间 的不一致性，甚至是相互独立的问题；用图形的方法描述数据间的相互关系，语 义清晰、可理解性强，这有助于利用数据间的因果关系进行预测分析。 b a y e s 的“关于几率性问题求解的评论”的论文成为b a y e s 学派奠基性的工 作。著名数学家拉普拉斯用b a y e s 的方法导出了重要的“相继率”后，b a y e s 方 法和理论逐渐被人们理解和重视起来。但由于但是b a y e s 方法在理论和实际应用 中还存在很多不完善的地方因而在1 9 世纪并未被普遍接受。2 0 世纪初意大 利的b d ef i n e t t i 以及英国的j e f f r e y sh 对b a y e s 学派的理论作出重要贡献。二战 后，w a l d 提出了统计的决策理论，这一理论中，b a y e s 解占有重要地位；信息论 的发展也对b a y e s 学派作出新的贡献。1 9 5 8 年英国最悠久的统计杂志b i o m e t r i k a 重新全文刊登了b a y e s 的论文，2 0 世纪5 0 年代。以l b b b i n sh 为代表，提出了 经验b a y e s 方法和经典方法结合，引起统计界的广泛注意，这一方法很快就显示 出它的优点，成为很活跃的一个方向。 随着人工智能的发展，尤其是机器学习、数据挖掘的兴起，为b a y c s 理论的 发展和应用提供了更为广阔的空间。b a y e s 理论的内涵也比以前有了很大的变化。 2 0 世纪8 0 年代b a y e s 网络用于专家系统的知识表示，9 0 年代进一步研究可学习 的b a y c s 网络，用于数据挖掘和机器学习。近年来，b a y e s 学习理论方法的文章 更是层出不穷，内容涵盖了人工智能的大部分领域，包括因果推理、不确定性知 识表达、模式识别和聚类分析等。并且出现了专门研究b a y e s 理论的组织和学术 刊物i s b a 。 b a y e s 网络在数据挖掘中主要应用在分类及回归分析、因果推理和不确定知 识表达和聚类模式发现等。本文主要讨论的是b a y e s 方法在分类中的应用。分类 规则发现是根据客体的特征向量值及其它约束条件将其分到某个类别中，在数据 挖掘中，主要研究如何从数据或经验中学习这些分类规则。对于分类闯题，有些 情况下，输入特征向量唯一对应这一个类别，这种问题成为确定性的分类问题； 而有些情况下，这会出现类别的重叠现象，也就是说，来自于不同类别的样本从 外观特征上具有极大的相似性，这时我们只能说某一样本属于某一类别的概率有 复旦大学硕士学位论文 4 基于互信息的b a y e s 网络分类嚣的构建 多大，然而我们却必须为它选择个类别。b a y e s 学派采用两种方法处理这种情 况：一是选择后验概率最大的类别：二是选择效用函数最大( 或损失最小) 的类 别。 设特征向量x = ( x l ，x 2 ，x n ) ，类别向量c = ( c i c 2 ，c l i i ) ，分类的目的是要把特 征向量x 归入到某个类别c i ( i = l m ) 中。第一种方法选择后验概率最大的类别， 即：p ( e i l x ) p ( q l x ) o = i ，m ，此时取判别函数：r i ( x ) = p ( e i l x ) 。可以证明，这 种方法能够保证分类误差最小。 第二种方法，在决策理论中经常用到，它采用平均效益的大小来衡量决策风 险的大小这实际上与不确定性的程度密切相关。设把属于类别c i 的特征向量x 错误的划分到类别c i 中损失为l u ( ) ( ) ，它选择损失最小的类别，即：m i n i i ( x ) p ( q i x ) ，i = l ，m ) ，此时判别函数：r i 产岛傅) p ( c j l z ) 。当 l 辩) 的对角线元素取为0 ，非对角线元素取为l 。即正确分类的损失为0 。错误 分类的损失都相同时，风险损失最小与后验概率最大是等价的。 目前，b a y e s 分类方法已在文本分类、字母识别、经济预澜4 等领域获得了成 功的应用。 1 4 本文的主要内容和成果 本文讨论的是如何建构b a y e s 网络分类器的问题，其主要研究内容和成果如 下： 首先。本文从b a y e s 网络的基本理论出发，在国内外相关工作的基础上，发 现建构b a y e s 网络存在若干问题。第一，要想得到准确的b a y e s 网络结构，即要 得到很好的符合数据库中数据信息的b a y e s 网络结构，需要用户指定参数，这对 用户来说是比较困难的；第二，要自动找到一个最佳的网络结构是一个n p 难题。 第三，通过不断修改网络参数来建构b a y e s 网络结构，是一个漫长的过程。本文 提出了在没有用户参与的情况下，仅仅根据数据库中数据信息，以s h a n n o n 信息 论为依据，用互信息作为衡量两个随机变量间的依赖程度的测度，快速建构准确 的b a y e s 网络结构的思想。 然后。分别针对不同的情况，提出三个建构算法： 1 ) 提出了当描述数据的属性均为离散取值时，用互信息衡量属性间的依赖 关系，建立b a y e s 网络结构的朴素b n c 算法。 2 ) 提出了e b n c 算法。e b n c 算法引进g i i l i 系数，用它对连续取值的随机 变量的取值进行最优二分。使之离散化。然后再运用朴素b n c 算法对经 过预处理的属性集建构网络。 3 ) 提出了o s b n c 算法。o s b n c 算法用h b n t r e e 记录数据流中的有用信 复旦大学硕士学位论文 5 基于互信息的b a y c s 网络分类嚣的构建 息，使得算法能够在只扫描一遍数据库的基础上，创建b a y e s 网络结构。 如果在数据流上开标记窗口，则o s b n c 算法可以用来处理数据流。 最后，本文用u c i d a t a 测试数据对上述三种算法进行了实验和性能分析，和 同样不需要领域专家参与的决策树分类算法进行了比较，发现本文算法的准确性 在大多数情况下要好于决策树，且速度也较之要快。同时，实验也证实了o s b n c 算法可以运用在数据流模型中。 1 5 本文的组织安排 本文的组织如下： 第二章介绍b a y c s 网络和信息论的基本理论，给出建构b a y e s 网络的若干 问题，并简单介绍与互信息结合的b a y e s 网络建构方法。 第三章详细介绍了处理离散取值随机变量的朴素网络建构算法b n c ，处理混 有连续取值随机变量到的扩展网络建构算法e b n c 以及在只扫描一边数据库，且 只用有限存储空间的情况下，建构网络的d s b n c 算法。 第四章运用u e i d a t a 中的数据对三种算法算法进行实验和性能分析。 第五章是总结和展望。 复旦大学硕士学位论文 基于互信息的b a y e s 网络分类嚣的构建 第二章基于互信息的b a y e s 网络建构的理论基础 2 1 b a y e s 网络理论简介 2 1 1b a y e s 理论简介 首先，我们简单介绍一下b a y e s 理论中的几个基本概念。 ( 1 ) 先验概率。先验概率是指根据历史的资料或主观判断所确定的各事件 发生的概率，该类概率没能经过试验证实，属于检验前的概率，所以称之为先验 概率。先验概率一般分为两类，一是客观先验概率，是指利用过去的历史资料计 算得到的概率；另一是主观先验概率，是指在无历史资料或历史资料不全的时候， 只能凭借人们的主观经验来判断取得的概率。 ( 2 ) 后验概率。后验概率一般是指利用b a y e s 公式，结合调查等方式获取 了新的附加信息，对先验概率进行修正后得到的更符合实际的概率。 ( 3 ) 联合概率。联合概率也叫乘法公式，是指两个任意事件的乘积的概率， 或称之为交事件的概率。 ( 4 ) 全概率公式。如果影响事件a 的所有因素b ，b 。，满足：b 。b j = o ，( i j ) ，且p ( 4 ) = l ，p ( b 。) 0 ，i = l ，2 ，则必有： p ( a ) = p ( 骂) ，( 彳i 忍) ( 5 ) b a y e s 公式。b a y e s 公式也叫后验概率公式，还叫逆概率公式。设先验 概率为p ( b 。) ，调查所获得新附加信息p ( a j i b 。) ，其中i = l ，2 ，n ，j = l ，2 ，m 。 则b a y e s 公式计算的后验概率为： 。，。、e ( b , ) p ( a j l 耳) p ( ei 一，) = 1 - 旦 p ( 耳) 尸( 4i 骂) k = l 介绍完上述的几个基本概念后，我们来看看b a y e s 分析方法。b a y e s 分析方 法的特点是使用概率表示所有形式的不确定性，学习或其它形式的推理都用概率 规则来实现。b a y e s 学习的结果表示为随机变量的概率分布，它可以解释为我们 对不同可能性的信任程度。b a y e s 学派的起点是b a y e s 的两项工作：b a y e s 定理 和b a y e s 假设。b a y e s 定理将事件的先验概率与后验概率联系起来。假定随机向 复且大学硕士学位论文 7 基于互信息的b & y e s 网络分类嚣的构建 量x ，0 的联合分布密度是p ( x ，0 ) ，它们的边际密度分别是p ( x ) 。p ( 0 ) 。一般情况 下设x 是观测向量，0 是未知参数向量，通过观测向量获得未知参数向量的估计， b a y e s 定理记作： p l ) = 型警= t 系, r ( 可o ) 弓* p 石c x 丽i o ) ( 疗( 印是口的先验分布) 从上式可以看出。对未知参数向量的估计综合了它的先验信息和样本信息， 而传统的参数估计方法只从样本数据获取信息如最大似然估计。b a y e s 方法对未 知参数向量估计的一般过程如下： 1 ) 将未知参数看成随机向量。这是b a y e s 方法与传统的参数估计方法的最 大区别。 2 ) 根据以往对参数0 的知识，确定先验分布厅( 口) ，它是b a y e s 方法容易引 起争议的一步，因此而受到经典统计界的攻击。 3 ) 计算后验分布密度，做出对未知参数的推断。 在第二步，如果没有以往的知识来帮助确定，r ( 们，b a y c s 提出可以采用均匀 分布作为其分布。即参数在它的变化范围内，取到各个值的机会是相同的，称这 个假定为b a y e s 假设。b a y e s 假设在直觉上易于被人们所接受，然而它在处理无 信息先验分布，尤其是未知参数无界的情况时却遇到了困难。经验b a y c s 估计 e b 把经典的方法和b a y e s 方法结合在一起，用经典的方法获得样本的边际密度 p ( x ) ，然后通过下式来确定先验分布7 r ( o ) ： p ( x ) = i 万佃) p ( x i e ) d 8 2 1 2b a y e s 网络简介 简而言之，b a y e s 网络是一个带有概率注释的有向无环路图。这个有向图模 型能表示大的变量集合的联合概率分布( 物理的或b a y e s 的) ，可以分析大量变 量之间的相互关系利用b a y e s 定理揭示的学习和统计推理功能。实现预测、分 类，聚类、因果分析等数据挖掘任务。 对于组随机变量x ； x i ，x 2 。，x 。 的b a y e s 网络由以下两部分组成：( 1 ) 一个表示x 中的每一个随机变量以及它们之间因果联系的网络结构s ；( 2 ) 与每 一个随机变量相联系的局部条件概率分布表，简称c p t 。这两者共同定义了x 的联合分布。其中，s 是个有向无环图，图中每一个节点对应于x 中的一个随 机变量。s 的两个结点之间如果不存在连线，则表示它们条件独立；否则，表示 它们之间存在因果联系。假设有两个节点x i ，x j 之间存在一条弧线由x i 到x i ， 即x - x i ，则称x i 是x j 的一个双亲节点或直接先驱节点，x 称为x i 的一个子 复旦大学硕士学位论文 8 基于互信也的b a y e s 网络分类嚣酌构建 孙节点( i j = l ，n ) 。每一个节点可以有多个双亲节点，我们用p a 表示s 中x i 的双亲节点集合。每一个节点所对应的c p t ，就是条件概率p ( x i l p a i ) ( i = 1 ，n ) 的概率分布。则x 的联合概率分布表示为： p ( x ) = i - i p ( x ，l p a ，) ( 1 ) i f f i i p ( f 2 e m p t y ie ) 。0 0 一 p ( b = b a dj ) = o 0 2 一 、g a u g e p ( g = e m p t y b = g o o d ，f = n o te m p t y ，e ) = o0 4 p ( g = e m p t yib = g o o d f = e m p t y 。) = o 9 7 p ( g = e m p t y i b = b e d ，f = n o te m p t y 。) = o 1 0 p ( g = e m p t y ib = b a d ，f = e m p t y e ) = o 9 9 一t u r no v e rl 一 p ( t ；n o l b = g o o d 。e ) ：o ，0 3 p ( t = n oj b = b a d ，e ) ；0 9 8 p ( s = n oit = y e s ，f = n o te m p t y e ) = 0 0 1 p ( s f e ojt = y e s 。f = e m p t y 。；) = o 9 2 p ( s = n o i t = n o f = f l o te m p t y ，) = 1 0 p ( s = n o i t = d o f ；e m p t y ，e ) = i 0 圈l 一个b e y e s 同络实例 图l 为一个检测并修理一辆不能启动的汽车的b a y e s 网络的实例。有箭头的 弧线从原因指向结果。每一个节点的c p t 列在节点旁边。 如果用p 表示( 1 ) 式中的p ( x d p a o ( i = l ，2 ，n ) ，则二元组( s ，p ) 表示了联合概 率分布p 。当仅仅从先验信息出发建立b a y c s 网络时，该概率分布是b a y e s 的( 主观的) 。当从数据出发进行学习，进而建立b a y e s 网络时，该概率是物理 的( 客观的) 。 为了建立b a y e s 网络，第一步，必须确定为建立模型有关的变量及其解释。 为此，需要： ( 1 ) 确定模型的目标，即确定问题相关的解释：( 2 ) 确定与问题有关的许 多可能的观测值。并确定其中值得建立模型的子集；( 3 ) 将这些观测值组织成互 不相容的且穷尽所有状态的变量。这样做的结果不是唯一的。 第二步，建立一个表示因果联系的有向无环路图。根据概率乘法公式有： p ( ) = 兀p ( 置i x , ，五，置一。) ( 2 ) i - i 对于每个变量x l ，如果有某个子集n x b x 2 ，x 。) 使得x i 与 x i ，x 2 ，x 。 m i 是条件独立的，即对任何x i 有： p ( 五i 置，五，以) = p ( 置i n 。) ( 忙1 ，n ) ( 3 ) 则由( 2 ) 和( 3 ) 式可得： 复旦大学硕士学位论文 9 基于互信息的8 a y e s 网络分类嚣的构建 p ( 肖) = i - i p ( 一i i i 。) ( 4 ) f l i 变量集合( n l ，n 2 ，n 。) 对应于双亲节点( p a l ，p a 2 ，p a ) ，故又可写成： h p ( x ) = r j p ( z i 托) ( 5 ) - r 于是，为了决定b a y e s 网络的结构，需要将变量x l ，x 2 ，x 。按某种次序排序， 同时决定满足( 3 ) 式的变量集合 v i i ，2 n 。 。 从理论上说，如何从n 个变量中找到适合条件独立的顺序，是一个组合爆炸 问题。因为要比较n ! 种变量顺序。不过，通常可以在现实问题中决定因果关系， 而且因果关系一般都对应于条件独立的断言。因此，可以从原因变量到结果变量 画一个带箭头的弧来直观的表示变量之间的因果关系。 第三步，指派局部概率分布p ( x i l p a i ) 。在离散的情形，需要为每一个变量x i 的各个双亲节点的状态指派一个分布。 显然，以上各步可能交叉进行，而不是简单的顺序进行可以完成的。 现在考虑这样的闯题：给定b a y e s 网络的结构，如何利用给定样本数据去学 习网络的概率分布即更新网络变量原有的先验分布。这里使用的是b a y c s 方法， 即综合先验知识和数据去改进已有知识的技术，这些技术可用于数据挖掘。假设 变量组x = x l ，x 2 ，x 。) 的物理联合分布可以编码在某个网络结构s 中： p ( x l 岛，s 6 ) = li p ( zi p q ，岛，s 6 ) j i 其中e i 是分布p ( x i l p a i 。8 l s h ) 的参数向量，0 s 是参数组( e i ，e 2 ，9 n ) 的向量， 而s “表示物理联合分布可以按照s 被分解的假设。需要说明的是这个分解是不 交叉的。例如，绘定x - x l ，x 2 ) 。x 的任何联合分布可以被分解成对应于没有弧 的网络结构也可以被分解成对应于x i - x 2 的网络结构这就是交叉。此外， 假设从x 的物理联合概率分布得到一个随机样本d = f x j ，x 。，。d 的一个元素 x i 表示样本的一个观测值，称为一个案例。定义一个取向量值的变量 s 对应于 参数向量e s ，并用一个先验概率密度函数p ( e s i s “) 表示对o s 的不确定性于是 b a y c s 网络的学习概率问题可以简单地表示成：给定随机样本d ，计算后验分布 p ( 0 s l d ，s “) 。 下面用无约束多项分布来讨论学习概率的基本思想。假定每个变量x i ， i = l ，n 是离散的有r i 个可能的值x i l ，】【x 巾每个局部分布的函数是组多 项分布的集合，一个分布对应于p a i 的一个构成( 即一个分量) 。也就是说，假定 p ( hj p 呀，倪，s 6 ) = 如 0 ( i = i , 2 ，n j = 1 2 ，q l ；k = l 。2 ，r i ) 复旦大学硕士学位论文 0 基于互信息的b a y e s 网络分粪器的构建 其中p a l i ，p a l 2 ，p a i q i 表示p a l 的构成，q i = 兀。谚= ( ) ，( k = 2 ，r i ； j = l ，q i ) ，没有列入，因为。= 1 一锹，可以通过计算得到。为方便起见， 定义参数向量： 嚷= ( 岛2 ，巳 ，吼。) ( i _ 1 2 。，n ；j 2 1 2 q i ) 给定以上的局部分布函数后，需要由以下两个假设，才可以以封闭的形式计 算后验分布p ( 0 sld ，s “) ： ( 1 ) 在随机样本d 中没有缺损数据，这时又称d 是完全的： ( 2 ) 参数向量e i j 是相互独立的，a p p ( e 。i s 6 ) = 兀兀p ( 岛l ) 。这就是参数 独立假设。 在以上两个假设下，对于给定的随机样本d ，参数仍然保持独立； p ( b l d , s 6 ) = 兀n p 哆i d ，s 6 ) 于是可以相互独立地更新每一个参数向量。假设每个参数向置钆有先验 d i r i c h l e t 分布d i r ( 0 i j i a i j t ，a 0 2 ，a i i n ) ，得到后验分布为： p ( 岛f d ，s 6 ) = d 护( 岛i 气- + 也l ，嘞2 十2 ，+ ) 其中n i j k 是当x i - - - - - - - - - - - - - - - - - - - x i k j 主p a i 节。时d 中的案例数目。 现在可以求o s 可能构成的平均值来得到感兴趣的预测。例如，计算d 中第 n + 1 个案例p ( 乃+ j l d ，) 2 ，( 茄0 ) 町) 。利用参数对给定d 保持独立，可以 计算数学期望： p ( “+ j d ，) = 腑p 媳j d ，s 6 ) 卯= n n 豫p 幌jd ) 织 通过计算，可褥： p w ) 2 垂糟 其中乃= 且= 艺坛。由于无约束多项式分布属于指数家族，上面的计 算将变得错单。 “ 变量组x 的b a y e s 网络表示了x 的联合概率分布，所以，无论是从先验知 识、数据或两者的综舍建立的b a y e s 网络，贩则上都可以用它来推断任何感兴趣 的概率。不过，离散变量的任意b a y e s 网络的精确或近似推理都是n p 难题。目 复旦大学硕士学位论文 1 1 基于互信息酌8 a y e s 网络分类嚣的构建 前的解决办法是使用条件独立以简化计算，和面向特定的推断建立简单的网络拓 扑，或在不牺牲太多精确性的前提下，简化网络的结构等。虽然如此，一般仍然 需要可观的计算时间。对某些问题，简单b a y e s 分类器使用条件独立，则有明显 的效果。 但样本数据不完全时，除了少数特例外，一般要借助于近似方法，如 m o n t e c a r l o 方法、高斯逼近、以及e m ( 期望一极大化) 算法求m l ( 极大似然) 或 m a p ( 极大后验) 等。尽管有成熟的算法，其计算开销也是比较大的。 当不能确定b a y e s 网络结构时，用b a y e s 方法从给定的数据学习网络结构和 概率分布也