（计算机软件与理论专业论文）基于贝叶斯理论的海量科学数据挖掘.pdf

基于叶斯理论的海量科学数据挖掘 摘要 随着数据库技术的成熟应用和i n t e r n e t 的迅速发展，人类积累的数据量 e 在以指数速度增长。对于这些数据，人们已经不满足于传统的查询、统 计分析手段，而需要发现更深层次的规律，对决策或科研工作提供更有效 的决策支持。正是为了满足这种要求，从大量数据中提取出隐藏在其中的 有用信息，将机器学习应用于大型数据库的数据挖掘( d a t a m i n i n g ) 技术得到 了长足的发展。 所谓数据挖掘( d a t am i n i n g ，d m ) ，也可以称为数据库中的知识发现 ( k n o w l e d g e d i s c o v e r d a t a b a s e ，k d d ) ，就是从大量的、不完全的、有噪声的、 模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是 潜在有用的信息和知识的过程。发现的知识可以被用于信息管理、查询优 化、决策支持、过程控制等，还可以用于数据自身的维护。因此，数据挖 掘是数据库研究中的一个很有应用价值的新领域，它又是一门广义的交叉 学科，融合了数据库、人工智能、机器学习、统计学等多个领域的理论和 技术。 基于贝叶斯技术的分类是当前数据挖掘领域的一个研究热点。本文主 要研究了以下几个主要内容： 1 综述了数据挖掘及分类的基本理论，介绍了数据挖掘及分类的一些 基本概念，讨论了几种主要的分类算法：决策树、神经网络及贝叶斯，并 对它们进行了分析比较。 2 讨论了贝叶斯分类的主要内容，包括贝叶斯定理以及朴素贝叶斯分 类和贝叶斯网络分类。 3 研究了贝叶斯网络的学习问题，包括贝叶斯网络结构学习和贝叶斯 网络参数学习。 4 介绍了我们开发的s d m 数据挖掘系统的系统框架以及功能实现。 并重点介绍了贝叶斯算法模块。 关键词：数据挖掘分类贝叶斯理论结构学习参数学习 茎王墨! 堑堡丝些墨量型堂墼塑丝塑 a b s t r a c t w i t ht h e a p p l i c a t i o n o f d a t a b a s ea n dt h e d e v e l o p m e n t o f i n t e r n e t ， a c c u m u l a t e dd a t aa r ee x p o n e n t i a li n c r e a s i n g f o rt h e s ed a t ap e o p l e a r en o t s a t i s f i e dw i t ht h et r a d i t i o n a lm e t h o d so fq u e r i e sa n ds t a t i s t i c s ，b u tw a n tt of i n d d e e p e rr e g u l a t i o n st op r o v i d ee f f e c t i v ed e c i s i o nt os c i e n c ea n dr e s e a r c hw o r k s s od a t am i n i n gt e c h n o l o g yt h a ta p p l ym a c h i n el e a r n i n gt ol a r g ed a t a b a s e t o a c q u i r eu s e f u li n f o r m a t i o nf r o m a g r e a td e a ld a t a i sd e v e l o p e d d a t am i n i n g ( d m ) o rk n o w l e d g ed i s c o v e rf r o md a t a b a s e ( k d d ) i st o d i s c o v e ru s e f u li n f o r m a t i o na n d p o t e n t i a lk n o w l e d g e f r o m p l e n t i f u l a n d i n c o m p l e t e a n df u z z ya n dr a n d o md a t aw h i c ha r eh i da n da r en o tk n o w nb y p e o p l e t h e s ed i s c o v e r e dk n o w l e d g em a y b eu s e dt om a n a g ei n f o r m a t i o na n d o p t i m i z eq u e r i e s a n dm a k ed e c i s i o na n dc o n t r o l p r o c e d u r e a n dm a i n t a i n d a t a b a s ea n ds oo n s od a t am i n i n gi sav e r yv a l u a b l en e wd a t a b a s er e s e a r c h a r e a ，a n di t i sac r o s s e ds u b j e c tt h a ta d o p t st h e o r ya n dt e c h n o l o g yo fd a t a b a s e a n da r t i f i c i a li n t e l l i g e n c ea n dm a c h i n el e a r n i n ga n ds t a t i s t i c sa n ds oo n c l a s s i f y i n gb a s e d o nb a y e st e c h n o l o g yh a sg o tm o r ea n dm o r ei n t e r e s t si n t h ef i e l do fd a t am i n i n g t h em a i nw o r ko f t h et h e s i s ： 1 t h ef u n d a m e n t a lt e c h n o l o g i e so fd a t am i n i n ga n dc l a s s i f i c a t i o na r e i n t r o d u c e d s e v e r a lt y p i c a lc l a s s i f i c a t i o na l g o r i t h m sa r ec o m p a r e di n c l u d i n g d e c i s i o n t r e ea n dn e u r a ln e t w o r ka l g o r i t h ma n db a y e s i a na l g o r i t h m 2 t h em a i nt h e o r i e so fb a y e s i a nc l a s s i f i c a t i o na r ed i s c u s s e d ，i n c l u d i n g b a y e s t h e o r e m 、n a i v e b a y e s i a n c l a s s i f i c a t i o na n d b a y e s i a n n e t w o r k s c l a s s i f i c a t i o n 3 t h el e a r n i n go fb a y e s i a nn e t w o r k s i s s t u d i e d ，i n c l u d i n g s t r u c t u r e l e a r n i n go fb a y e s i a n n e t w o r k sa n d p a r a m e t e rl e a r n i n go fb a y e s i a n n e t w o r k s 4 t h es y s t e mo fd a t am i n i n gi si n t r o d u c e da n dt h em o d u l eo fb a y e s i a n a l g o r i t h mi sm a i n l y i n t r o d u c e d k e y w 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 st h e o r y , s t r u c t u r el e a r n i n g ， p a r a m e t e rl e a r n i n g i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谓十的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：烂塑! !日期：沪呼年月汐日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：塑里! !导师签名： 日期：撕月卅日 基于贝叶斯理论的海量科学数据挖掘 1 1 项目概述 1 1 1 项目背景和意义 第一章引言 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积 累的数据越来越多。例如：商品条形码的广泛使用，企业的信息化程度的 提高，科学研究和政府部门中电子化事务处理技术的运甩，以及数据收集 工具和技术的多元化( 从文本扫描到卫星遥感) 等等。互联网的发展更是为我 们带来了海量的数据和信息。存储在各种数据媒介中的海量的数据，在缺 乏强有力的分析工具的情况下，已经远远的超出了人的理解和概括的能力。 为此，这种大量的原始数据和对功能强大的数据分析工具的需求共存的局 面，被有的人描述为“数据丰富，但信息贫乏”( d a t a r i c hb u t i n f o r m a t i o np o o r ) 。 许多的数据库也就成了“数据坟墓”( d a t a t o m b ) 一换句话说，这些数据很少 被再访问。 激增的数据背后隐藏着许多重要的信息，拥有这些数据库的决策者们， 在做决策时不是基于数据库中蕴含的大量信息，而是基于决策者的直觉。 因为决策者缺乏从海量数据中提取有价值知识的工具。传统的数据库管理 系统可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中 存在的关系和规则，无法根据现有的数据预测未来的发展趋势，缺乏发现 数据背后隐藏的知识的手段。数据与信息之间的鸿沟要求有更强用力的数 据分析工具，将数据坟墓转换成知识“金块”。 在数据库技术飞速发展的同时，人工智能领域的一个分支一机器学习 的研究自5 0 年代开始以来也取得了很大进展。用数据库管理系统来存储数 据，用机器学习的方法来分析数据，挖掘大量数据背后的知识，这两者的 结合促成了数据库中的知识发现( 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 s ，简记 k d d ) 的产生，k d d 亦称为数据挖掘( d a t am i n i n g ，简称d m ) 。 数据挖掘是信息技术自然演化的结果。信息技术的发展大致可以描述 为如下的过程：初期是简单的数据收集和数据库的构造；后来发展到对数 据的管理，这包括：数据存储、检索以及数据库事务处理；再后来发展到 对数据的分析和理解，这时候出现了数据仓库技术和数据挖掘技术。早期 的数据收集和数据库的建造为数据存储、检索和事务处理的技术的发展创 造了必要条件，随着查询、事务处理等成熟技术被频繁的应用在大量的数 基于贝叶斯理论的海量科学数据挖掘 据库系统上，数据的分析和理解也就当然的成为了信息技术发展的下一个 目标。 数据挖掘是涉及数据库和人工智能等学科的一个当前相当活跃的研究 领域，同时又由于有广泛可用的存在于各种数据库中的海量数据。因此， 从大量的数据中智能地、自动地提取出有价值的知识和信息的研究，即数 据挖掘，具有十分重要的理论及现实意义和广泛的应用前景。目前，数据 挖掘己成为一个具有迫切需要的很有前途的热点研究课题，国内外许多研 究工作者对此领域投入了极大的热情。 在科学研究领域，随着科学仿真实验数据的越来越多，且不同实验采 集的数据分散于不同的计算机中，科学家们几乎不可能通过手工的方式来 发现各数据源之间的内在联系。这迫切需要研究出与此对应的新的数据挖 掘技术及挖掘工具来解决此类问题。目前，国外对数据挖掘技术的研究比 较多，但专门针对科学数据的研究非常少。国内此领域的研究处于初步的 起始阶段，成熟的研究成果基本空白。 本项目的研究工作源于上述背景。我们的目的是对数据挖掘的核心算 法进行深入的研究，期望能在这些已有算法和理论的基础上，搭建起合理 且高效的科学数据挖掘架构，研究出科学高效的数据挖掘算法，并开发出 应用于实际的科学数据挖掘平台，以填补国内本研究领域和相关产品的空 白。 1 1 2 主要研究内容 我们在以前的研究成果上，以具体的科学仿真实验产生的数据作为挖 掘列象，主要利用p c a 、i c a 相结合的变换技术在特征空间分析和降维方 面的优势、自组织映射神经网络在图像处理方面的特点、前馈式递归聚类 算法在模式识别中的性能，同时结合已有的数据挖掘分类技术，开发出新 的基于科学仿真数据的智能挖掘平台。通过在实际应用中的观测与使用， 来检测我们研制的算法，并经过对其进行专门的优化，使研究出来的算法 成为数据挖掘的核心算法，使其应用在国防及国民经济的关键领域。 1 2 数据挖掘概述 本节主要介绍数据挖掘的相关知识，包括数据挖掘的定义、数据挖掘 的研究现状和发展趋势，并对数据挖掘过程进行了简单的介绍，最后，介 绍了数据挖掘的功能( 可以挖掘什么类型的模式) ，即概念类描述：特征化 和区分、关联分析、分类和预测、聚类分析、孤立点分析和演变分析。 基于贝叶斯理论的海量科学数据挖掘 1 2 1 数据挖掘的定义 所谓数据挖掘( d a t am i n i n g ，简记d m ) ，就是从大量的、不完全的、有 噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先 不知道的、但又是潜在有用的信息和知识的过程 】 。这个定义包括好几层含 义；数据源必须是真实的、大量的、含噪声的；发现的是用户感兴趣的知 识；发现的知识要可接受、可理解、可运用：并不要求发现放之四海皆准 的知识，仅支持特定的发现问题。 与数据挖掘相近的同义词有知识挖掘、知识获取、模式分析、数据考 古等。还有一个经常与之相混的术语：数据库中的知识发现f k n o w l e d g e d i s c o v e r yf r o md a t a b a s e ，简记k d d ) ，一般的看法是d m 只是k d d 的一个 步骤，但是由于d m 这个词的广泛使用，我们也可不对他们进行严格的区 分，而把他们看成同义词。 何为知识? 从广义上理解，数据、信息也是知识的表现形式，但是人 们更把概念、规则、模式、规律和约束等看作知识。人们把数据看作是形 成知识的源泉，好像从矿石中采矿或淘金一样。原始数据可以是结构化的， 如关系数据库中的数据：也可以是半结构化的，如文本、图形和图像数据； 甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的，也可 以是非数学的；可以是演绎的，也可以是归纳的。发现的知识可以被用于 信息管理、查询优化、决策支持和过程控制等，还可以用于数据自身的维 护。 因此，数据挖掘是一门交叉学科，它把人们对数据的应用从低层次的 简单查询，提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下， 汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、数理统计、 可视化技术、并行计算等方面的学者和工程技术人员，投身到数据挖掘这 一新兴的研究领域，形成新的技术热点。 1 2 2 数据挖掘的研究现状和发展趋势 k d d 一词首次出现在1 9 8 9 年8 月举行的第1 1 届国际联合人工智能学 术会议上。随着k d d 在学术界和工业界的影响越来越大，国际k d d 组委 会于1 9 9 5 年把专题讨论会更名为国际会议，在加拿大蒙特利尔市召开了第 一届k d d 国际学术会议，以后每年召开一次。1 9 9 7 年亚太地区在新加坡组 织了第一次规模较大的p a k d d 学术研讨会，以后每年召开一次。 此外，数据库、人工智能、信息处理、知识工程等领域的国际学术刊 物也纷纷开辟了k d d 专题或专刊。i e e e 的k n o w l e d g c a n dd a t ae n g i n e e r i n g 基于贝叶斯理论的海量科学数据挖掘 会刊首先在1 9 9 3 年出版了k d d 技术专刊，所发表的5 篇论文代表了当时 k d d 研究的最新成果和动态。随后，各类k d d 会议、研讨会纷纷涌现， 许多领域的国际会议也将k d d 列为专题讨论。1 9 9 9 年，i e e e 和a c m 再 次推出k d d 专刊，介绍数据挖掘在各个领域的应用成果。 不仅如此，在i n t e r n e t 上还有不少k d d 电子出版物，其中以半月刊 k n o w l e d g ed i s c o v e r yn u g g e t s 最为权威，在h t t p ：w w w k d n u g g e t s c o m 还可 以下载各种各样的数据挖掘工具软件和典型的样本数据仓库，供人们测试 和评价。另一份在线周刊为d s ( d s 代表决策支持) ，1 9 9 7 年1 0 月7 日开始 出版，可向d s t r i a l t g ec o m 提出免费订阅申请。在网上，还有个自由论 坛d me m a i lc l u b ，人们通过电子邮件相互讨论d m 的热点问题。 目前，国外数据挖掘的发展趋势及研究方向主要有：对知识发现方法 的研究和进一步发展，如近年来注重对b a y e s ( 贝叶斯) 方法以及b o o s t i n g 方 法的研究和提高；传统的统计学回归法在k d d 中的应用：k d d 与数据库 的紧密结合，人工神经网络应用于数据挖掘方面的研究。应用方面有：k d d 商业软件工具不断产生和完善，注重建立解决问题的整体系统，而不是孤 立的过程。用户主要集中在大型银行、保险公司、电信公司和销售业。国 外很多计算机公司非常重视数据挖掘的开发应用，i b m 和微软都成立了相 应的研究中心进行这方面的工作。许多著名的计算机公司开始尝试k d d 软 件的开发，比较典型的如s a s 公司的e n t e r p r i s e m i n e r ，i b m 公司的i n t e l l i g e n t m i n e r s g i 公司的s e tm i n e r ，s p s s 公司的c l e m e n t i n e ，还有k n o w l e d g e d i s c o v e r yw o r k b e n c h 、d bm i n e r 、q u e s t 等。w e b 数据挖掘产品有n e t p e r c e p t i o n s a c c r u ei n s i g h t 和a c c r u e h i tl i s t ，c o m m e r c et r e n d s 等。 与国外相比，国内对k d d 的研究稍晚，目前进行的大多数研究项目是 由政府资助进行的，如国家自然科学基金、8 6 3 计划、“九五”计划等。1 9 9 3 年国家自然科学基金开始对数据挖掘研究进行支持。1 9 9 9 年4 月在北京召 开的第三届亚太地区k d d 国际会议( p a k d d 9 9 ) 响应热烈，收到论文1 5 8 篇。 国内从事数据挖掘研究的人员主要在大学，也有部分在研究所或公司。所 涉及的研究领域很多，一般集中于学习算法的研究、数据挖掘的实际应用 以及有关数据挖掘理论方面的研究。如北京系统工程研究所对模糊方法在 数据挖掘中的应用研究、北京大学对数据立方体的研究、华中理工大学、 复旦大学、浙江大学等对关联规则的研究、电子科技大学从神经网络等方 面对数据挖掘进行的研究等。西安交通大学已知的有机械学院、电信学院、 工程学院和管理学院在从不同角度对数据挖掘进行研究。但是到目前为止， 国内还没有比较成熟的数据挖掘产品。 基于贝叶斯理论的海量科学数据挖掘 当前，d m 研究正方兴未艾，预计今后还会形成更大的高潮，研究焦点 可能会集中到以下几个方面； 1 ) 研究专门用于知识发现的数据挖掘语言，也许会像s q l 语言一样 走向形式化和标准化； 2 )寻求数据挖掘过程中的可视化方法，使得知识发现的过程能够被用 户理解，也便于在知识发现过程中的人机交互； 3 ) 研究在网络环境下的数据挖掘技术，特别是在i n t e r n e t 上建立d m 服务器，与数据库服务器配合，实现数据挖掘： 4 )加强对各种非结构化数据的挖掘，如文本数据、图形图像数据、多 媒体数据。 但是，d m 将首先满足信息时代用户的急需，因此，研制开发大量基于 d m 的决策支持软件工具产品将是首要的任务。 目前有很多通用的数据挖掘系统趋向于提供适用于各种商业应用的横 向解决方案( h o r i z o n t a ls o l u t i o n ) ，而不是针对某个特定的应用的解决方案。 对某个特定领域的一些数据或应用可能需要特定的算法来查找模式，而通 用的数据挖掘系统对这些特定领域的数据有其固有的局限性，有可能不能 满足要求。因此，研制某个特定领域的数据挖掘工具将显得尤为重要。专 用的数据挖掘系统能够提供纵向解决方案( v e r t i c a ls o l u t i o n ) ，把特殊领域的 业务逻辑和数据挖掘系统集成起来，将数据分析技术与特定领域知识结合 以完成特定的任务。目前的应用领域多集中于生物医学、d n a 分析、金融、 零售业和电信部门等。 1 2 3 数据挖掘过程简介 数据挖掘有以下主要的过程； 1 确定业务对象 清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘的重要一步。 挖掘的最后结构是不可预测的，但要探索的问题应是有预见的，为了数据 挖掘而数据挖掘则带有盲目性，是不会成功的。 2 数据准备 1 1 数据的选择 搜索所有与业务对象有关的内部和外部数据信息，并从中选择出适 用于数据挖掘应用的数据。 2 1 数据的预处理 研究数据的质量，为进一步的分析做准备。并确定将要进行的挖掘 基于贝叶斯理论的海量科学数据挖掘 操作的类型。 3 1 数据的转换 将数据转换成一个分析模型，这个分析模型是针对挖掘算法建立 的。建立一个真f 适合挖掘算法的分析模型是数据挖掘成功的关键。 3 数据挖掘 对所得到的经过转换的数据进行挖掘。除了选择合适的挖掘算法外， 其余一切工作都能自动地完成。 4 结果分析 解释并评估结果。其使用的分析方法一般应视数据挖掘操作而定，通 常会用到可视化技术。 5 知识的同化 将分析所得到的知识集成到业务信息系统的组织结构中去。 1 2 4 数据挖掘功能 数据挖掘功能是指可以挖掘什么类型的模式。数据挖掘通过预测未来 趋势及行为，做出前摄的、基于知识的决策。数据挖掘的目标是从数据库 中发现隐含的、有意义的知识。 主要有以下六类功能。 1 概念描述：定性与对比 2 关联分析 3 分类和预测 4 聚类分析 5 孤立点分析 6 演变分析 概念描述：定性与对比 通过对含有大量数据的数据集进行概述性的总结，可以获得简明、准 确的描述，这种描述就称为概念描述。获得概念描述的方法主要有以下三 种： 1 ) 利用更为广义的属性，对所分析的数据进行概要总结，被分析 的数据称为目标数据集； 2 ) 将所分析的两类数据的特点进行对比，并对对比结果进行概要 总结，这两类数据分别称为目标数据集和对比数据集。 3 ) 数据特征化和比较。 基于贝叶斯理论的海量科学数据挖掘 关联分析 关联分析发现关联规则，这些规则展示属性值频繁地在给定数据集中 一起出现的条件。关联分析广泛用于购物篮或事务数据分析。 关联规则的挖掘问题可形式化描述如下，设i = i l , i t ，f ，。 是数据项集 合，d 是与任务相关的数据集合，也就是一个交易数据库，其中每个交易， 是一个数据项子集，即t d ，t i ，每个交易均有一个识别编号t i d 。设 a 为一个数据项集合，当且仅当a ，时，称交易，包含a 。一个关联规则 就是具有a j b 形式的蕴涵式，这里a c l ，b c ，并且a n 3 = 西。关联规 则a b 在交易数据库d 中成立，并且具有s 支持度和c 信任度。这也就意 味着交易数据库_ d 中有s 比例的交易丁包含a t , j b 数据项，并且交易数据库 d 中有c 比例的交易r 满足“如果包含4 ，则包含曰”的条件。即 s u p p o r t uj 曰) = e ( a u b ) c o n f i d e n c e 叫= 口) = p ( al 助( 1 2 ) 如果不考虑关联规则的支持度和可信度，那么在事务数据库中存在无 穷多的关联规则。事实上，人们一般只对满足一定的支持度和可信度的关 联规则感兴趣。在文献中，一般称满足一定要求的( 如较大的支持度和可信 度) 的规则为强规则。因此，为了发现有意义的关联规则，需要给定两个阈 值：最小支持度和最小可信度。前者即用户规定的关联规则必须满足的最 小支持度，它表示了一组物品集在统计意义上的需满足的最低程度；后者 即用户规定的关联规则必须满足的最小可信度，它反应了关联规则的最低 可靠度。 分类和预测 分类在数据挖掘中是一项非常重要的任务，目前在商业上应用最多。 分类的目的是学会一个分类函数或分类模型( 也常常称作分类器1 ，该模型能 把数据库中的数据项映射到给定类别中的某一个。分类和回归都可用于预 测。预测的目的是从利用历史数据记录中自动推导出对给定数据的推广描 述，从而能对未来数据进行预测。和回归方法不同的是，分类的输出是离 散的类别值，而回归的输出则是连续数值。这里我们将不讨论回归方法。 要构造分类器，需要有个训练样本数据集作为输入。训练集由一组 数据库记录或元组构成，每个元组是一个由有关字段( 又称属性或特征) 值组 成的特征向量，此外，训练样本还有一个类别标记。一个具体样本的形式 基于贝叫斯理论的海量利学数据挖掘 可为：( v l ，v 2 ，”n ；c ) ；其中v ，表示字段值，c 表示类别。 分类器的构造方法有机器学习方法、神经网络方法、统计方法等等。 机器学习方法包括决策树法和规则归纳法，前者对应的表示为决策树或判 别树，后者则一般为产生式规则。神经网络方法主要是b p 算法，它的模型 表示是前向反馈神经网络模型( 由代表神经元的节点和代表连接权值的边组 成的一种体系结构) ，b p 算法本质上是一种非线性判别函数。统计方法包括 贝叶斯法和非参数法( 近邻学习或基于事例的学习) ，对应的知识表示则为判 别函数和原型事例。另外，最近又兴起了一种新的方法：粗糙集( r o u 曲s e t ) ， 其知识表示是产生式规则 本文主要针对数据挖掘中贝叶斯分类的方法展开研究。分别在第3 章 和第4 章进行详细的讨论。 聚类 聚类与分类和预测不同，在分类和预测中，对于目标数据库中存在哪 些类这一信息我们是知道的，在那里我们要做的就是将每一条记录分别属 于哪一类标记出来；但是，聚类是在预先不知道目标数据库到底有多少类 的情况下，希望将所有的记录组成不同的类或者说“聚类”( c l u s t e r ) ，并且 使得在这种分类情况下，以某种度量为标准的相似性，在同一聚类之间最 小化，而在不同聚类之间最大化。 聚类算法中一大类算法中的相似性是基于距离的，而且由于现实数据 库中数据类型的多样性，关于如何度量两个含有非数值型字段的记录之间 的距离的讨论有很多，并提出了相应的算法。在很多应用中，由聚类分析 得到的每一个聚类中的成员都可以被统一看待。聚类分析的算法可以分为 以下几大类：分裂法、层次法、基于密度的方法、基于网格的方法和基于 模型的方法等。 孤立点分析 数据库可能包含一些数据对象，它们与数据的一般行为或模型不一致。 这些数据对象是孤立点( o u t l i e r ) 。大部分数据挖掘的方法将孤立点视为噪声 或异常而丢弃。然而，在些应用中( 如欺骗检测) ，罕见的事件可能比正常 出现的那些更有价值。 孤立点可以使用统计试验检测。它假定一个数据分布或概率模型，并 使用距离度量，到其他聚类的距离很大的对象被视为孤立点。另有一种基 于偏差的方法通过考察一群对象主要特征上的差别识别孤立点。 演变分析 数据演变分析( e v o l u t i o na n a l y s i s ) 描述行为随时间变化的对象的规律或 基于贝叶斯理论的海量科学数据挖掘 趋势，并对其建模。这类分析除包括时间相关数据的特征化、区分、关联、 分类或聚类，还包括时间序列数据分析、序列或周期模式匹配和基于类似 性的数据分析。 1 3 贝叶斯理论的发展概况及应用研究状况 自从5 0 6 0 年代贝叶斯学派形成后，关于贝叶斯的研究久盛不衰。早在 8 0 年代，贝叶斯网络就成功的应用于专家系统。成为表示不确定性知识和 推理的一种流行的方法。9 0 年代以来，贝叶斯学习一直是机器学习研究的 重要方向。由于概率统计与数据挖掘的天然酰系，数据挖掘兴起后，贝叶 斯再次成为引人注目的热点。贝叶斯方法尤其是其中的贝叶斯网络由于它 自身所具有的优点，已在这方面开始表现出它的潜力。得到了广泛的应用。 近年来研究者研究了直接从数据中学习贝叶斯网络的方法，为贝叶斯网络 应用于数据挖掘和知识发现开辟了道路。 现在，贝叶斯在很多领域都得到了广泛的应用，也取得了很多令人鼓 舞的成果。概括说来，贝叶斯主要应用于以下方面： 1 ) 信息恢复、诊断与故障检测：微软开发的算法和评估方法已用 于o f f i c e 的产品中问题回答向导和打印故障自动检测功能，英 特尔公司用来诊断半导体芯片可能发生的失效问题。 2 ) 经济领域：用于预测使用杀菌剂计划后的冬小麦产量，以及预 测石油和股票价格。 3 ) 医学应用：应用于诊断睡眠混乱、某些皮肤病病状、外伤护理 和家庭健康评估等医疗专家系统。胸部疾病的贝叶斯网络模型 帮助医生形成诊断规则和计划进一步的诊断程序。 4 ) 工业方面：贝叶斯网络系统己应用于火车机车、飞行器、电力 生产的气轮机、空间飞船、办公设备，以及工程设计制造c a m 和产品质量控制。 5 ) 电讯通信业：检测欺骗的或不可收回的欠款情况、实时电信经 营的决策支持系统。 6 ) 交通管理：利用高峰期的交通状况信息来优化控制交通流量， 确认阻塞的车辆和事故，以及协助车辆自动控制器进行决策。 7 ) 文化教育：自动分类词条编辑系统、地理信息处理系统，以及 b k d 教育和解释系统，从数据库中提取信息建立知识库，用来 预测未来趋势、解释过去行为和提供正常的决策。 8 ) 国防系统：m i t r e 公司的武器限时反应系统和舰船的防卫系统， 基于贝叶斯理论的海量科学数据挖掘 能在2 秒之内处理武器故障。美国海军研究一种贝叶斯网络系 统，用于确定敌方来临的导弹、飞行器或船只，并推荐何种武 器能最有效地反击正来临的目标。 贝叶斯在经济和医学等领域越来越多的应用日益显示出其发展前途。 这些应用通过正在建成的许多应用模型用于预测石油和股票价格、控制太 空飞船和诊断疾病等等不断地渗人我们的社会和经济生活中。在解决许多 实际问题中，我们可以使用贝叶斯网络这样的概率推理技术从不完全的、 不精确的或不确定的知识和信息中做出推理。贝叶斯网络系统在计算机中 程序化后能够自动产生最优预测或决策，即使当某些主要信息片丢失了， 这就是贝叶斯技术不断受到人们重视的优越性所在。 1 4 论文研究内容 本文主要是对数据挖掘中的贝叶斯分类算法展开深入的研究，将其划 分为朴素贝叶斯分类和贝叶斯网络分类，重点在于贝叶斯网络分类。其中 着重研究了贝叶斯网络的学习。整个的研究围绕着这些内容展开。 首先讨论了数据挖掘分类的基本技术，包括数据分类的两大过程，分 类数据所需要的几种数据预处理，以及分类方法的比较和评估标准；比较 了几种典型的分类算法，包括决策树、神经网络和贝叶斯，并对这三种分 类算法进行对比研究；接着，引出本文的研究重点，即数据挖掘算法中的 贝叶斯分类。 在贝叶斯分类算法中，首先介绍了它的理论基础，即贝叶斯定理。然 后，分别对朴素贝叶斯和贝叶斯网络进行了探讨，分析了它们的原理及基 本概念，比较了它们的优缺点，得出贝叶斯网络算法的优越性，从而引出 贝叶斯网络分类中最关键的技术，也是本文所研究的重点，即贝叶斯网络 的学习。 在贝叶斯网络学习的研究一节中，重点研究了贝叶斯网络的结构学习 和参数学习，并提出了一种改进的用于贝叶斯网络结构学习的新的记分函 数，经过实验验证，这种记分函数是有效的并且在性能上是优越的。在此 基础上，提出了一种两阶段学习贝叶斯网络结构的方法，其中的第二阶段 采用上面所提出的记分函数作为测度。经过实验验证，本算法在结构学习 的精度和计算速度上都有很大的优势。 在第五章中，介绍了我们设计开发的一个数据挖掘应用原型系统。包 括系统的设计和实现的一些细节以及系统所实现的功能。此外着重介绍了 系统中贝叶斯分类模块的具体实现。 1 0 基于贝叶斯理论的海量科学数据挖掘 第二章数据挖掘中的分类 分类在数据挖掘中是一项非常重要的任务，目前在商业上应用最多。 分类的目的是学会一个分类函数或分类模型( 也常常称作分类器) ，该模型能 把数据库中的数据项映射到给定类别中的某一个。例如：可以建立一个分 类模型，对银行贷款的安全或风险进行分类。许多分类的方法己被机器学 习、专家系统、统计学和神经生物学方面的研究者提出。 本章将讨论分类的基本技术，然后介绍和分析比较几种典型的分类算 法。 2 1 分类的基本技术 本节主要介绍数据分类的两大过程，分类数据需要的数据预处理，以 及分类方法的比较和评估标准。 2 1 1 数据分类的过程 数据分类( d a t ac l a s s i f i c a t i o n ) 可分为两步进行( 如图2 1 1 。第一步，建立 一个模型，描述预定的数据类集或概念集。通过分析由属性描述的数据库 元组来构造模型。假定每个元组属于一个预定义的类，有一个类标号属性 ( c l a s sl a b e la t t r i b u t e ) 确定。对于分类，数据元组也称为样本、实例或对象。 为建立模型而被分析的数据元组形成训练数据集。训练数据集中的单个元 组称为训练样本，并随机的由样本集中选取。由于预先知道每个训练样本 的类标号，这个建立模型的学习过程属于有指导的学习f 即模型的学习在知 道每个训练样本属于哪个类的指导下进行) 。这不同于无指导的学习( 例如聚 类) ，无指导的学习中的每个训i 练样本的类标号事先是未知的，要学习的类 集合或数量也可能事先不知道，整个学习的过程是在无指导的情况下进行 的。 通常，通过第步的学习建立的模型用分类规则、决策树或数据公式 的形式表示。例如：给定一个顾客信用信息的数据库，通过分类算法学习 得出分类规则，根据这些规则，决定顾客的信誉的好坏( 如图2 1 a ) 。即这些 规则就是分类模型，可以利用这个模型为其他数据样本进行分类，同时也 能对数据库的内容提供更好的理解。 第二步( 如图2 1 b ) ，使用这些规则进行分类。首先要评估模型的预测准 确率。最常用的一种方法是保持( h o l d o u t ) 方法，该方法使用类标号样本测试 集，这些样本随机选取，并独立于训练样本集，即测试样本集完全不同于 幕于贝叶斯理论的海量科学数据挖掘 训练样本集。模型在测试样本集上的准确率是指正确被模型分类的测试样 本的百分比。对于每个测试样本，按照分类模型学习得出的预测类与已知 的类标号比较，如果相同，则表示分类成功，不相同，则表示分类不成功。 之所以使用完全不同于训练样本集的测试样本集，是因为学习模型倾向于 过分适合数据，即学习模型可能并入训练数据中某些特别的异常，而这些 异常不出现在总体样本集中。如果仍使用训练数据评估分类模型，则可能 评估总是乐观的。 如果认为模型的准确率可以接受，就可以利用这个模型对类标号未知 的数据元组或对象进行分类( 这种数据在机器学习的文献中也称为“未知的” 或“先前未见到的”数据) 。例如：通过分析现有顾客数据学习得到的分类 规则可以预测新的顾客的信誉的好坏( 如图2 1 ) 。 。奠 分类算j 击i 训练数据 k 。 分类j | l ij l j | |i 陋窖1 d年茜争收入水平信誉度 n 0 】( = = 3 0低一般 i f 二= “3 l 4 舻 n 0 2 1 4 0高优皇 日n dl i 5 入水平一高” n o 3 4 0r t一般 t , h = n n o 4 4 0 巾 一股 信誉度= “优良” h ( ) 53 1 4 u拍仇盔 a ) 学习：在训练数据上用分类算法学习，学习模型用分类规则的形式表示 匣 ( n o 2 0 l ，孙4 0 ，而) 信誉度 0 删l 良 b 1 分类：在测试数据上评估分类规则的准确率，如果准确率可以接受 则分类规则可用于新的数据元组的分类 图2 1 数据分类的过程 基于贝叶斯理论的海量科学数据挖掘 分类具有广泛的应用，包括信誉证实、医疗诊断、性能预测和选择购 物。 2 1 2 分类数据的预处理 为了提高分类的准确性、有效性和可伸缩性，需要对分类所用的数据 进行以下的预处理； 数据清理 数据清理的目的是消除或减少噪声数据以及处理空缺值。可采用平滑 技术消除或减少噪声数据；对于空缺值，可用该属性最常出现的值，或根 据统计，用最可能的值代替。尽管大部分的分类算法都有处理噪声和空缺 值的机制，但经过清理的数据将更有助于减少学习时的混乱。 相关性分析 数据中的许多属性可能与分类任务不相关。例如：记录银行贷款申请 是星期几提出的数据属性可能与申请成功不相关。此外，一些属性还可能 是冗余的，如果包含这些属性将减慢或可能误导学习步骤。因此，可以进 行相关分析，删除学习过程中不相关的或冗余的属性。在机器学习中，这 一过程称为特征选择。 理想情况下，用在相关分析上的时间，加上从压缩了的数据集上学习 的时间，应当少于在原来的数据集上学习所用的时间。这种分析就可以帮 助提高分类的有效性和可伸缩性。 数据变换 数据可以概化到较高层的概念。例如，对于连续值的属性，“收入”的 数字值可以概化到离散的区间，如“低，中，高”。类似地，对于离散值 的属性，如“街道”，可以概化到高层概念，如“城市”。由于概化压缩了 原来的训i 练数据集，学习的时间将会减少。数据也可以按某种规则进行规 范化处理等。这些必要的数据变换都将对分类是有用的。 2 1 3 分类方法的比较和评估标准 分类方法可以根据下列标准进行比较和评估： 1 预测准确度 预测准确度是用得最多的一种比较尺度，特别是对于预测型分类任务， 目前公认的方法是1 0 番分层交叉验证法。 2 计算复杂度 计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘中，由于 操作对象是巨量的数据库，因此空间和时间的复杂度问题将是非常重要的 基于贝叶斯理论的海量科学数据挖掘 一个环节。 3 强壮性 这涉及对于数据集中噪声数据或空缺值的处理，在有噪声数据或空缺 值的情况下模型是否具有正确预测的能力。 4 可伸缩性 大部分的分类算法是内存驻留算法，通常假定数据量很小。对于海量 的数据，算法是否具有有效的构造模型的能力，即算法的可伸缩性是很重 要的。 5 模型简洁度和可理解性 对于描述型的分类任务，模型描述越简洁越容易理解则越受欢迎。例 如，采用规则表示的分类器构造法比较有用，而神经网络方法产生的结果 就比较难以理解。 2 2 几种典型的分类算法 分类器的构造方法有机器学习方法、神经网络方法、统计方法等等。 机器学习方法包括决策树法和规则归纳法，前者对应的表示为决策树或判 别树，后者则一般为产生式规则。神经网络方法主要是b p 算法，它的模型 表示是前向反馈神经网络模型( 由代表神经元的节点和代表连接权值的边组 成的一种体系结构) ，b p 算法本质上是一种非线性判别函数。统计方法包括 贝叶斯法和非参数法( 近邻学习或基于事例的学习) ，对应的知识表示则为判 别函数和原型事例。 另外，还有一些其它的分类方法，包括k 一最近邻分类，遗传算法和粗 糙集方法等。与决策树、神经网络和贝叶斯分类相比，这些方法在商品化 的数据挖掘系统中较少应用于分类。像遗传算法和粗糙集方法分类还处于 原型阶段，然而这些方法正日趋流行。 本节将对决策树、神经网络、贝叶斯三种分类算法进行对比研究。 2 2 1 决策树 i d 3 和c 4 5 是最初的典型决策树算法，它们以自顶向下递归的各个击 破的方式构造决策树。决策树是一种类似于流程图的树结构，其顶层节点 是树的根节点，每个分枝代表一个测试输出，每个非叶节点表示一个属性 的测试，每个叶节点代表一个类或一个类的分布。决策树可以很容易地转 换成分类规则，即从根节点到叶节点的每条路径均可以转换成一条型为 “i f t h e n ”的分类规则，其中i f 部分是沿着某条路径上的每个内部节点 1 4 基于贝叶斯理论的海量科学数据挖掘 的属性值对形成的一个合取项，t h e n 部分是包含类预测的叶节点。 一个典型的决策树模型如图2 2 所示，它用来预测某地区“小麦产量” 的高低。 图2 2 预测某地区。小麦产量”的高低 用决策树进行分类分两步走。第一步是利用训练数据集建立一棵决策 树模型。这个过程实际上是一个从数据中获取知识，进行机器