（计算机软件与理论专业论文）使用贝叶斯方法的数据挖掘及应用研究.pdf

山东科技大学硕士学位论文摘要 摘要 数据挖掘( d a t am i n i n g ) 技术是人们长期对数据库技术进行研究和开发的结果。数据挖掘所得 到的知识应具有先前未知、有效和实刚三个特征，其中先前术知的知识是指该知识是预先未曾 预料到的，即数据挖掘是要发现那些不能靠直觉发现的信息或知识，甚至是违背直觉的信息或 知识，挖掘出的知识越是出乎意料，就可能越有价值。而贝叶斯( b a y e s ) 方法的一个显著特点， 就是它可以通过看结果来了解假设，也就是说， 下，贝叶斯方法具有其它方法不可比拟的长处。 当对先验知识知之甚少，或者毫不知情的情况 本文主要针对数据挖掘的特点和本质，充分利 用贝叶斯方法的特点，将贝叶斯理论及其思想方法融入到聚类、分类、关联规则挖掘以及偏差 分析和异常检测等数据挖掘各方法中，提出将贝叶斯方法应用于数据挖掘的算法，并对提出的 算法进行了验证和讨论。文章最后对自己所做的工作做了总结，并陈述了数据挖掘的研究方向 及发展前景。 关键词：数据挖掘；贝叶斯理论：聚类；分类：关联规则：偏差分析 山东科技犬擎硕士学位论文摘要 a b s t r a c t d a t am i n i n gi st h ec o n s e q u e n c eo ft h ec o n s t a n ts t u d ya n dd e v e l o p m e n ta i m i n ga t d a t a b a s e e c h n o l o g i e s t h ek l o w l e d g ea c q u i r e df r o md a t am i n i n gh a st h ec h a r a c t e d s t j c t h a tt h e1 ( 1 1 0 w l e d g ei su n k i l o w np r e v i o u s l y 、e m c i e n ta n du t i l i z a b l e a m o n gt h et h r e e c h a r a c t e r i s t i c st h ef i r s to n em e a n st h a tt h ek n o w l e d g ei su n e x p e c t e d ，t h a ti st os a y ，d a t a m i n i n gi st on n do u tt h o s ek n o w l e d g et 1 1 a tc 锄o tb ef o u n do u td i r e c t l y ，e v e nt h o s em a t m i g h tv i o l a t et h ei n s t i n c t t h em o r eu n e x p e c t e dt h ek n o w l e d g em i n e d ，m em o r e v a l u a b l e t h en o t a b l ec h a r a c t e r i s t i ct t l a tb a y e sm e t h o dh a si st h a tt h eh y p o t h e s i sc a nb e r c n e c t e db ym er e s u l t i fm ep r e v i o u sk r l o w l e d g ei sk n o w n1 i t t l e ，o re v e nu 1 1 l ( 1 1 0 w n ， b a y e sm e t h o dh a si t sp e c u l i a rm e r i l i nm i sp a p e r ，a c c o r d i n gt ot l l ec h a r a c t e r i s t i ca n d e s s e n c eo fd a t am i n i n ga 1 1 db a y e sm e t h o d ，b a y e st h e o r ya r e 印p l i e dt ot h em e t h o d so f d a t am i n i n gs u c ha sc l u s t e r i n g 、c l a s s i f i c a t i o n 、a s s o c i a t i o nr u i ea n da b n o m i t ya n a l y s i s s o m ea l g o r i t h m sa r eb r o u g h tf o n a r da n dv e r i f i e da n dd i s c u s s e d i nm ee n do f t h ep 印c r ： s o m ep r o p o s i t i o na n do p i n i o n sa b o u tt h er e s e a r c hd i r e c t i o na 1 1 dp r o s p e c to fd a t am i n i n g a r ed u tf 0 r w a r d k e y w o r d s ：d a t am i n i n g ；b a y e st h e o r y ；c l u s t e r i n g ；c l a s s i 矗c a t i o n ；a s s o c i a t i o nn 1 1 e ； a b n or i 咀i t ya n a l y s i s 声明 本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所公 认的文献外，全部是本人在导师指导下的研究成果。该论文尚没有呈交于其它任 何学术机关作鉴定。 研究生繇豫繇、 日期：。；石乡 a f f i r m a t i o n id e c l a r et h a tt h i sd i s s e r t a t i o ，s u b m i t t e di nf u 墒l i m e n to ft h er e q u i r e m e n t s f b r t h ea w a r do fm a s t e ro fe g i e e r i n g ，i ns h a n d o n gu n j v e r s i t yo fs c i e n c ea n d t e c h o l o g y ， i s w h o l i ym yo w nw o r ku l e s sr e f 毛r e c eo fa c k o w l e d g e t h e d o c u m e th a so tb e e ns u b m i t t e df b r q u a l i n c a t i o n a t a n yo t h e ra c a d e m i c i n s t i t u t i o n s i g n a t u r e ：f j 汛叩 d a t e ：2 口口j 6 与 u 山东科技大学硕士学位论文数据挖掘概速 第一章数据挖掘概述 1 1 数据挖掘简介 近十几年来，人们利用信息技术生产和搜集数据的能力大幅度提高，千万 个数据库被用于商业管理、政府办公、科学研究和工程开发等等，并且这一势 头仍将持续发展下去。于是，一个新的挑战被提了出来：在这被称之为信息爆 炸的时代，信息过量几乎成为人人需要面对的问题。如何才能不被信息的汪洋 大海所淹没，从中及时发现有用的知识，提高信息利用率呢? 要想使数据真正 成为一个组织的资源，只有充分利用它为公司自身的业务决策和战略发展服务 才行，否则大量的数据可能成为包袱，甚至成为垃圾。因此，面对人们被数据 淹没，人们却饥饿于知识的挑战，数据挖掘和知识发现技术应运而生，并得以 蓬勃发展，越来越显示出其强大的生命力。作为一个学术领域，数据挖掘和知 识发现有很大的重合度，甚至有人把数据挖掘和知识发现等同起来；另有一种 观点是发现知识的过程在人工智能领域称为知识发现，而数据库领域习惯称为 数据挖掘：还有一种观点是把知识发现看作发现知识的完整过程，而数据挖掘 只是这个过程中的一部分口2 1 。本文采用最后一种观点，即把数据挖掘作为知识 发现的一个核心环节，而且在本文主要讨论这一环节。 数据挖掘就是从大型数据集的数据中提取人们感兴趣的知识。这些数据是 大量的、不完全的、有噪声的、模糊的、随机的，要提取的知识是隐含的、事 先未知的潜在有用信息，这些知识表示为概念、规则、规律、模式等形式【3 9 】。 还有很多和这一术语相近似的术语，如从数据库中发现知识、数据分析、数据 融合以及决策支持等。人们把原始数据看作是形成知识的源泉，就像从矿石中 采矿一样。原始数据可以是结构化的，如关系数据库中的数据，也可以是半结 构化的，如文本、图形、图像数据，甚至是分布在网络上的异构型数据。发现 知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。 山东科技大学硕士学位论文数据挖掘概述 发现了的知识可以被用于信息管理、查询优化、决策支持、过程控制等，还可 以用于数据自身的维护。因此，数据挖掘是一门广义的交叉学科，它汇聚了不 同领域的研究者，尤其是数据库、人工智能、数理统计、可视化、并行计算等 方面的学者和工程技术人员。 特别要指出的是，数据挖掘技术从一开始就是面向应用的。它不仅是面向 特定数据库的简单检索查询调用，而且要对这些数据进行微观、中观乃至宏观 的统计、分析、综合和推理，以指导实际问题的求解，企图发现事件间的相互 关联，甚至利用已有的数据对未来的活动进行预测。如加拿大b r i t i s hc o l u m b i a 省电话公司要求加拿大s i m o n f r a s e r 大学k d d 研究组，根据其拥有的十多年的 客户数据，总结、分析并提出新的电话收费和管理办法，制定既有利于公司又 有利于客户的优惠政策。这样一来，就把人们对数据的应用，从低层次的查询 操作，提高到为各级经营决策者提供决策支持。这种需求驱动力，比数据库查 询更为强大。同时需要指出的是，这里所说的知识发现，不是要求发现放之四 海而皆准的真理，也不是要去发现崭新的自然科学定理和纯数学公式，更不是 什么机器定理证明。所有发现的知识都是相对的，是有特定前提和约束条件、 面向特定领域的，同时还要能够易于被用户理解，最好能用自然语言表达发现 结果。因此数据挖掘的研究成果是很讲求实际的。 随着数据挖掘研究逐步走向深入，人们越来越清楚地认识到：数据挖掘的 研究主要有3 个技术支柱，即数据库、人工智能和数理统计【3 5 】。 数据库技术在经历了2 0 世纪8 0 年代的迅速发展之后，已经在各行各业成 为一种基础。数据库最实质的应用不仅仅是查询，而是在于发现，从数据库中 主动发现知识。并且随着数据库的迅速普及用数据库作为知识源具有坚实的基 础。 人工智能( a i ，a r t i f i c i a li n t e l l i g e n c e ) ，是一门由计算机科学、控制 论、信息论、语言学、神经生理学、心理学、数学、哲学等多种学科相互渗透 而发展起来的综合性新学科。自问世以来a i 经过许多波折，但终于作为一门边 缘新学科得到世界的承认并且日益引起人们的兴趣和关注。不仅许多其它学科 开始引入或借用a i 技术，而且a i 中的专家系统、自然语言处理和图像识别已 成为新兴的知识产业的三大突破口。 山东科技大学硕士学位论文 数据挖掘概述 数理统计是应用科学中最重要、最活跃的学科之一。它的应用范围十分广 泛，也是对数据进行分析和处理最常用的一门学科。所谓数理统计并非独立于 统计学的新学科，确切地说它是在统计学基础上形成的所有收集和分析数据的 新方法的一个综合性名词，概率论是数理统计方法的理论基础，这样就逐渐形 成了概率论理论框架。在概率论进一步发展的基础上，到十九世纪初，数学家 们逐渐建立了观察误差理论、正态分布理论和最小平方法则，数理统计方法也 逐步成熟【3 6 】。 1 2 数据挖掘的内容及技术口2 ，3 5 ，3 钔 数据挖掘所发现的知识有以下几种：概化型知识，反映同类事物共同性质 的知识：特征型知识，反映事物各方面的特征知识；差异型知识，反映不同事 物之间属性差别的知识；关联型知识，反映事物之间关联或依赖的知识；预测 型知识，根据历史的和当前的数据推测未来数据；偏离型知识，揭示事物偏离 常规的异常现象。 数据挖掘可以发现基于以上类型的知识，归根到底集于一点就是，通过预 测未来趋势及行为，做出前瞻的、基于知识的决策。 数据挖掘的目标是从数据集中发现隐含的、有意义的知识，主要有以下几 类功能。 ( 1 ) 自动预测趋势和行为 数据挖掘自动在大型数据库中寻找预测性信息，以往需要进行大量手工分 析的问题如今可以迅速直接由数据本身得出结论。一个典型的例子是市场预测 问题，数据挖掘使用过去有关促销的数据来寻找未来投资中回报最大的用户， 其它可预测的问题包括预报破产以及认定对指定事件最可能作出反应的群体。 ( 2 ) 关联分析 数据关联是数据集中存在的一类重要的可被发现的知识。若两个或多个变 量的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、 因果关联。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数据 库中数据的关联函数，即使知道也是不确定的，因此关联分析生成的规则带有 可信度。 3 一 山东科技大学硕士学位论文数据挖掘概述 例如，如果客户购买了产品，在x 的情况下，他也可能购买产品占。 p ( bl 彳) = p ( 彳口) p ( 爿) ，其中两个关键的阈值指标分别是支持度p ( 爿口) 和可信 度j p ( 占i 爿) 。 ( 3 ) 分类 分类的目的是根据事先建立好的一个分类函数或分类模型( 也称作分类 器) ，该分类器能把数据集中的数据项映射到给定类别中的某一个。分类是有指 导的学习。根据设定的分组，将不同的数据分配到不同的分组，然后研究每个 组的特点。 ( 4 ) 聚类 数据集中的数据可被化分为一系列有意义的子集，即，聚类。聚类是将数 据分为几组，其目的是要将组与组之间的差异找出来，同时也要将一个组之中 的成员的相似性找出来。聚类分析帮助我们决定那些数据组合成一类更有意义。 聚类是把一组个体按照相似性分成若干类别，即”物以类聚”。它的目的是 使属于同一类别的个体之间的距离尽可能地小，而不同类别的个体间的距离尽 可能地大。聚类增强了人们对客观现实的认识，是概念描述和偏差分析的先决 条件。聚类技术主要包括传统的模式识别方法和数学分类学。分类与聚类不同 的是，聚类事先不知道以何种方式或根据什么来分类。 ( 5 ) 概念描述 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。 概念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者 描述不同的类对象之间的区别。生成一个类的特征性描述只涉及该类对象中所 有对象的共性。生成区别性描述的方法很多，如决策树方法、遗传算法等。 ( 6 ) 偏差分析 数据库中的数据常有一些异常记录，从数据库中检测这些偏差很有意义。 偏差包括很多潜在的知识，如分类中的反常实例、不满足规则的特例、观测结 果与模型预测值的偏差、量值随时间的变化等。偏差检测的基本方法是，寻找 观测结果与参照值之间有意义的差别。 目前数据挖掘通常被认为是一门边缘学科，涉及到多个领域。但从广义上 来说，只要能够从数据集中发现有价值的知识，就可以称之为数据挖掘。到目 一d 一 山东科技大学硕士学位论文 数据挖掘概述 前为止，通常用到的数据挖掘常用技术有： ( 1 ) 人工神经网络 神经网络近年来越来越受到人们的关注，因为它为解决复杂度很大的问题 提供了一种相对来说比较有效的简单方法。神经网络可以很容易地解决具有上 百个参数的问题。神经网络常用于两类问题：分类和回归。神经网络是建立在 可以自学习的数学模型的基础之上的。它可以对大量复杂的数据进行分析，并 可以完成对人脑或其他计算机来说极为复杂的模式抽取及趋势分析。神经网络 系统由一系列类似于人脑神经元一样的处理单元组成，称之为节点( n o d e ) 。这 些节点通过网络彼此互连，如果有数据输入，它们便可以进行确定数据模式的 工作。 ( 2 ) 决策树 决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法。 决策树是通过一系列规则对数据进行分类的过程。采用决策树，可以将数据规 则可视化，其输出结果也容易理解。决策树方法精确度比较高，不像神经网络 那样不易理解，同时系统也不需要长时间的构造过程，因此比较常用。比如， 在贷款申请中，要对申请的风险大小做出判断，图1 1 是为了解决这个问题而 建立的一棵决策树。 图1 1 一棵对贷款申请进行决策分析的决策树 f 3 1 遗传算法 遗传算法是一种基于生物进化过程的组合优化方法。其基本思想是：随着 时间的更替，只有适合的物种才得以进化。将这种思想用于数据挖掘就是根据 遗传算法获得最适合的模型，并据此对数据模型进行优化。这是一种基于进化 理论，并采用遗传结合、遗传变异以及自然选择等设计方法的优化技术。 山东科技大学硕士学位论文 数据挖掘概述 ( 4 ) 最近邻居方法 将数据集合中每一个记录进行分类的方法。它的基本思想是在给定数据后， 考虑在训练数据集中与该新数据距离最近( 最相似) 的所有数据，根据这些数 据所属的类别判定新数据所属的类别 ( 5 ) 统计分析法 在数据库或其它数据集的各项之间建立两种关系，即能用函数公式表示确 定关系的函数关系和不能用函数公式表示但有相关确定关系的相关关系，对它 们的分析可采用回归分析、相关分析、主成分分析等。 ( 6 ) 可视化技术 数据集中包含大量的数据，并且在数据集背后也暗含着各种数据模型，将 如此大量的数据可视化需要复杂的数据可视化工具。数据挖掘和数据可视化可 以很好地协作。就数据可视化系统本身而言，由于数据集中的数据量很大，很 容易使分析人员变得不知所措，数据挖掘工具可以通过可视化技术，并且根据 用户的需要来表示数据，为数据分析人员提供很好的帮助。拓宽了传统的图表 功能，使用户对数据剖析更清楚。 1 3 数据挖掘的过程 完整的数据挖掘过程一般可以分成以下5 个步骤，如图1 2 ： 图1 2 完整的数据挖掘过程的流程概图 山东科技大学硕士学位论文数据挖掘概述 具体工作流程如图1 3 豳1 3 数据挖掘的具体工作流程 图1 2 中各步骤解释如下： ( 1 ) 问题定义：了解相关领域的有关情况，熟悉背景知识，弄清用户要求。定 义要挖掘的目标。 ( 2 ) 数据提取：根据要求从数据库中提取相关的数据。 ( 3 ) 数据预处理：主要对前阶段产生的数据进行再加工，检查数据的完整性 及数据的一致性，对其中的噪音数据进行处理，对丢失的数据进行填补。 ( 4 ) 知识获取：运用选定的数据挖掘算法，从数据中提取用户所需要的知识， 这些知识可以用一种特定的方式表示或使用一些常用的表示方式。 ( 5 ) 评估：将发现的知识以用户能理解的方式呈现，例如某种规则，再根据 实际执行情况对知识发现过程中的具体处理阶段进行优化，直到满足用户要求。 山东科技大学硕士学位论文 贝叶斯理论概述 第二章贝叶斯理论概述 2 1 贝叶斯方法的基本观点 托马斯贝叶斯( t h o m a sb a y e s ) 是英国数学家，他对贝叶斯方法奠基性 的工作是他的论文“关于几率性问题求解的评论” 3 0 】。由于当时贝叶斯方法在 理论和应用中还存在很多不完善的地方，因此在很长一段时间并未被普遍接受。 后来随着统计决策理论、信息论和经验贝叶斯方法等理论和方法的创立和应用， 贝叶斯方法很快显示出它的优点，成为十分活跃的个方向。随着人工智能的 发展尤其是机器学习、数据挖掘的兴起，贝叶斯理论的发展和应用也获得了更 为广阔的空间。近年来，贝叶斯学习理论方面的文章更是层出不穷，内容涉及 到人工智能的大部分领域，如因果推理、不确定性知识表达、模式识别和聚类 分析等，同时出现了专门研究贝叶斯理论的组织i s b a ( i n t e n l a t i o n a ls o c i e t yo f b a y e s i a na n a l y s i s ) 。 贝叶斯方法的特点是使用概率去表示所有形式的不确定性，学习或其他形 式的推理都用概率规则来实现。贝叶斯理论在数据挖掘中的应用主要包括贝叶 斯方法用于分类及回归分析、因果推理和不确定知识表达以及聚类模式发现等。 贝叶斯方法正在以其独特的不确定性知识表达形式、丰富的概率表达能力、 综合先验知识的增量学习特性等成为当前数据挖掘众多方法中最为引人注目的 焦点之一。 贝叶斯统计是贝叶斯理论和方法的应用之一，其基本思想是：假定对所研 究的对象在抽样前已有一定的认识，常用先验分布来描述这种认识，然后基于 抽取的样本再对先验认识作修j 下，得到后验分布，而各种统计推断都基于后验 分布进行。经典统计学的出发点是根据样本，在一定的统计模型下做出统计推 断。在取得样本观测值之前，往往对参数统计模型中的参数护有某些先验知 识，关于矽的先验知识的数学描述就是先验分布。贝叶斯统计的主要特点是使 山东科技大学硕士学位论文贝叶斯理论概述 用先验分布，而在得到样本观测值x = ( 一，x ：，“) 7 后，由x 与先验分稚提供 的信息，经过计算和处理，组成较完整的后验信息3 0 】。这一后验分布是贝叶斯 统计推断的基础。 2 1 贝叶斯统计模型 1 概率论中的贝叶斯公式 设事件爿，爿：，4 构成互不相容的完备事件组，则b a y e s 公式是 p ( 一，ib ) ：1 ：! 皇_ 兰盟，f ：1 ，2 ，七( 2 1 ) p ( bl 一，) p ( 4 ) 在上式中，先验信息以 p ( 爿a - ，= 1 ，2 ，_ 】 这一概率分布的形式给出，即 先验分布。由于事件b 的发生，可以对一，：，4 发生的概率提供新的信息。 根据这些信息以及先验分布，可得出后验分布( p ( 4i 曰) ，f = l ，2 ，七 。可以看 出，b a y e s 公式反映了从先验分布向后验分布的转化。 2 数据挖掘中常用的贝叶斯公式口2 将式( 2 1 ) 用随机变量的形式改写，引入随机变量目，它的取值是 舅，岛，只，其中b = 舐4 ) ，即当一，发生时，护取值易，口是离散型的( 取 有限值) ，具有先验分布万( 卯： _ ，r ( 哆) = p ( 曰= 够) = p ( 爿，) ，= 1 ，2 ，。一，七 b 是另一随机事件，定义一个随机变量工，使得x = z ( 曰) 。 式( 1 ) 中的p 1 4 ) 可以表示为 尸“i 够) = 尸0 i 口= 易) ，= 1 ，2 ，后 它代表一种样本分布。这样式( 1 ) 可改写为 山东科技大学硕士学位论文贝叶斯理论概述 p ( 研i 工) ：p ( 口：幺ix ) ：1 三羔型坦，i ：1 ，2 ，女( 2 2 ) j p ( xl 岛) 石( 够) 卢l 3 贝叶斯推断 定义( 贝叶斯推断) 获得样本信息之前的概率分布为先验分布；把样本信息 与先验信息相结合的概率分布称为后验分布，并且把由先验信息推导出后验信 息这一过程称为贝叶斯推断。 贝叶斯推断要用到先验信息，当进行推理而缺乏必要的条件或数据时，依 靠经验或者历史资料，来收集、挖掘和加工先验信息，形成先验分布进行推理， 以提高挖掘质量；由数据挖掘的过程和目的来看，对一个数据集进行挖掘，事 先并不知道能从数据集中挖掘出什么样的知识，如果用先验信息来弥补这样的 不足，就是说用贝叶斯推断来进行挖掘，那就有可能提高挖掘的质量。 2 2 统计学 前面提到了贝叶斯统计，而且由于数据挖掘与统计之间的某些联系，本文 介绍一下统计学，以及统计与数据挖掘之间的联系与区别。 统计学是一门收集数据、分析数据，并根据数据进行推断的艺术和科学【3 l 】。 描述统计是对所收集的数据资料进行加工整理、综合概括，通过图示、列表和 数据对资料进行分析和描述。推断统计是在搜集、整理观测样本数据的基础上， 对有关总体做出推断，其特点是根据随机性的观测样本数据以及问题的条件和 假定，对未知事物做出的以概率形式表述的推断。 现代统计学一个很重要的标志就是模型技术的运用，在分析数据、探索数 据规律性、研究现实问题中已形成许多各具特色的思想方法。现代统计学在企 业知识管理方向上的应用研究，为解决这些问题开辟了新的途径，知识管理不 仅有利于提高企业的核心竞争力，还能发展企业多年积累的宝贵经验；它也是 中国企业与国际电子商务管理接轨的重要一步。要更好的进行知识管理，就要 开发知识管理平台，而知识管理平台的核心技术之一是数据挖掘，它融合了计 算机技术和数据仓库技术，是现代统计学的一个亮点。 一l o 山东科技大学硕士学位论文贝叶斯理论概述 二十世纪九十年代对“复杂性”研究较为瞩目。这对这一时期的一些技术 性方法的研究起到了理论先导的作用。从二十世纪九十年代以来，很多应用问 题都存在着分析对象比较复杂与正确识别模型结构的困难。但是随着贝叶斯统 计得到了再度复兴，以往被认为不可能实施计算的统计方法变得是很轻而易举 了。 2 3 数据挖掘与统计学的比较 统计学是处理数据的科学。教科书中的记述统计侧重数据的收集加工整理， 而数理统计侧重数据处理的“科学性”。一般而言“科学”要求有客观性，再现 性，普遍性。为表现这种科学性，研究者常喜欢用数学模型。因为数学比较简 明，严谨，比较抽象。数理统计就运用数学工具，记述数据产生的过程，描述 概率分布，进行推定，作假定检验，形成了一个比较完整的理论体系。 但是如上所述，数理统计学的基本理论框架产生于2 0 世纪的2 0 3 0 年代。 当时所处理的数据也就是一张统计表上的少量数据。其目的在于如何从较少的 数据中得到反映现象的数量特征。其后数理统计学急速发展，愈加严谨系统， 愈加数学化了。但主要的作用还是处理数据。 计算机的发展使得比较复杂的数据计算变的简便了，成为统计计算的重要 工具。当今，微机的普及，英特网的使用，使社会产生了很大的变革，使信息 传递的质和量都发生了飞跃的变化。同时，由英特网所联接起来的计算机，使 得个人也能处理以往仅由国家和企业所控制的信息。计算机的功能已经大大超 出了计算，更重要的是可以广泛大量地进行各种数据信息的检索处理。 在这种状况下对统计学的应用而言，一个常见的问题就是可利用数据量的 显著增大。在有自动计测的计算机的地方，从工厂的流水线到超级市场的收款 机，都是直接连续地记录数据，数据量有时会超过兆亿，甚至兆兆亿。这与费 舍时代的数据处理量相比较，原有统计学教科书的理论框架就不太适用了。比 如在固定的模型中对超大样本条件下所进行的假设检验，都会得出被拒绝的结 果。 从计算机中出现的大量数据中取得有用的信息被称之为数据挖掘。在数据 采集阶段，具有尽可能简捷地记述现象本质这种功能的模型还尚未被开发。更 山东科技大学硕士学位论文贝叶斯理论概述 多的则是使用计算机运用各种手段进行大量的数据计算，从而取得有价值的信 息。但是按照计算机的信息处理能力，除去计算功能之外，应该是可以将各种 信息进行再分类的。这将是一个还有待开发的领域。 数据挖掘可认为是对迄今为止的非常精确化的统计模型的一个启示。作为 一种语言，数学语言的缺陷在于过于抽象，很难记述比较复杂的社会现象。对 用数学公式可以简捷地记述物理性的规律来说，处理人类社会这种较复杂的社 会科学则多使用带有丰富含意的自然语言来记述。现在我们看到的社会经济现 象的复杂性的因素越多，越是难以用数学模型近似描述，数学的用途是广泛有 效的，但绝不是万能的。 因此，数据挖掘既然也是数据处理，统计学也就应该积极借鉴。借鉴的形 式之一就是将以往的统计学数据处理的经验方法与数据挖掘相结合；另一种形 式就是将计算机作为统计学的新的工具来使用，就像在统计学中使用数学一样， 要将以往只作为超级算盘使用的计算机，更加注意发挥其作为模式化工具的作 用。 最近一些统计方法及数据挖掘的手法以算法形式明确得以表现，具备客观 性，再现性的特点。但还存在着普遍性的问题，以往的计算机程序并未考虑到 这一点。在最近的软件设计工程学中已经考虑到将文字信息与数据处理一体化， 力图使其具有普遍性的模式。通过这些新方法的研究使用，计算机在统计学中 将成为仅次于数学的基本工具。 在以计算机为主体的信息产业发展中特别值得统计学注目的方法技术有， 图形，画像的操作及人机对话，专家系统，i n t e r n e t 的使用等。这些与统计学 的研究有着密切的联系，对未来科学的发展与进步具有适应性。在以往的统计 软件包中，数据解析的程序，执行程序的控制装置( 如c p u 等) ，解析的数据都 是在同一计算机上实行。但现在由于i n t e r 兀e t 的使用，这些都是在不同的计算 机上执行，而且有时它们分布在世界各个地方。在这种环境下，统计解析的软 件包也要与英特网的使用相适应，要创造出积极利用英特网的统计解析环境。 在2 1 世纪的信息社会中，统计学将以新的形式得到更广泛的应用，而作为与信 息社会相适应的统计解析环境的研究，将以“数据处理科学”的形式成为统计 学的一个新的领域。 一1 2 一 山东科技大学硕士学位论文贝叶斯理论概述 统计也能获耿知识，但是它们之间有一些本质的联系和区别。 数据挖掘和统计学在很多方面有共同之处，它们都是为了找出大量数据之 后所隐藏的数据模型或结构。实际上，由于它们所使用的方法以及它们的目标 有很多是重叠的，因此有一些人甚至把数据挖掘当作统计学的一个子分支。这 是不正确的，这些人没有真正理解什么是数据挖掘。数据挖掘也使用了其它领 域的思想、工具和方法，如数据库技术、机器学习等。 数据挖掘是一个利用各种分析工具在海量数据中发现模型和数据间关系的 过程，这些模型和关系可以用来做出预测。数据挖掘的第一步是描述数据一 计算统计变量( 比如平均值、均方差等) ，再用图表或图片直观的表示出来，进 而可以看出一些变量之间的相关性( 比如有一些值经常同时出现) 。数据挖掘 利用了人工智能( a i ) 和统计分析的进步所带来的好处。这两门学科都致力于 模式发现和预测。 数据挖掘不是为了替代传统的统计分析技术。相反，它是统计分析方法学 的延伸和扩展。大多数的统计分析技术都基于完善的数学理论和高超的技巧， 预测的准确度还是令人满意的，但对使用者的要求很高。而随着计算机计算能 力的不断增强，有可能利用计算机强大的计算能力只通过相对简单和固定的方 法完成同样的功能。 在此阐明统计学与数据挖掘相对应的本质与属性，以及它们之间的联系与 区别。 首先，统计学是一门很严密的学科，它是以数学为基础的。这种数学的基 础和严密性也就要求在使用任何方法之前必须给出这种方法的证明，来证明这 种方法是正确的和可行的。而这与计算机科学和机器学习不同，它们倾向于试 验。但这并不意味着数据挖掘是不严格的。 其次，统计注重数学的严密性，同时它也注重“推理”。例如通过观察一组 人口统计的样本数据，就能描述出人口分布的基本情况。这种情况同样也是数 据挖掘所关注的一方面。所不同的是，用于数据挖掘的数据集是庞大的。 统计学的第三个特性是现代统计学中，“模型”起着中心作用，模型是把对 象实体通过适当的过滤，用适当的表现规则描绘出的简洁的模仿品。通过这个模 仿品，人们可以了解到所研究实体的本质，而且在形式上便于人们对实体进行分 1 3 山东科技大学硕士学位论文 贝叶斯理论概述 析和处理。而数据挖掘注重的是算法的研究，算法是在有限步骤内求解某一问 题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个 过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。解题思路 是分析和设计算法，编写程序是操作已设计好的算法。一个算法应该具有以下 五个重要的特征：有穷性、确切性、输入、输出、可行性。 另外，统计学产生于计算机的发明之前，因此通常的统计都是由手工来实 现的。对多数统计学家来说，具有1 0 0 0 个数的数据集已经是很大了。但这1 0 0 0 个数相对于具有几百万甚至上亿个数据的数据集来说简直是微不足道。由这一 点可知，数据挖掘要处理大量的数据，而要处理如此大量的数据，进行手工计 算是不可能的，这就需要计算机的介入，计算机在人与数据之间起到了桥梁的 作用。要用计算机处理数据，就需要高效的算法，否则面对庞大的数据，计算 机的效率将会很低，因此数据挖掘强调的是算法的研究和实现。这并不是说统 计根本用不到计算机，相反，现代统计学也越来越依赖于计算机，只不过由于 统计学传统的做法，更依赖于根据模型对数据进行处理，而不是非常强调对算 法的研究。 还有，就是对数据集中偏差分析和异常数据的检测，这些异常数据通常称 为孤立点。异常数据，顾名思义就是不正常的数据，如数据输入错误或噪声数 据等。这些异常数据如果处理不当，会影响数据的质量。输入数据库中的异常 数据、不相关的字段或互相冲突的字段、数据的编码方式等都会对数据挖掘输 出结果的质量产生影响。而数据挖掘可以很好的解决这类问题。 统计学很少会关注实时分析，然而数据挖掘问题常常需要这些。例如，银 行事务每天都会发生，没有人能等三个月得到一个可能的欺诈的分析。类似的 问题发生在总体随时间变化的情形。 当然，数据挖掘借用了统计学中的许多技术和方法。它们在很多方面是重 合的。 ，2 4 山东科技大学硕士学位论文使用贝叶斯方法的数据挖掘及算法实现 第三章使用贝叶斯方法的数据挖掘及其 算法实现 3 1 使用贝叶斯方法的数据挖掘算法综述 贝叶斯方法的一个显著特点是它可以通过看结果来了解假设，也就是说， 在对先验知识知之甚少，或者毫不知情的情况下，贝叶斯方法具有其它方法不 可比拟的长处。而数据挖掘技术的一个重要应用就是挖掘先前未知的知识，数 据挖掘与传统的数据分析( 如查询、报表、联机应用分析) 的本质区别之一是数 据挖掘是在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的 知识应具有先前未知，有效和可实用三个特征。其中先前未知的信息是指该信 息是预先未曾预料到的，既数据挖掘是要发现那些不能靠直觉发现的信息或知 识，甚至是违背直觉的信息或知识，挖掘出的信息越是出乎意料，就可能越有 价值。在商业应用中最典型的例子就是一家连锁店通过数据挖掘发现了小孩尿 布和啤酒之间有着惊人的联系。正因为此，本文提出将贝叶斯方法应用于数据 挖掘的算法，并对提出的算法进行了验证和讨论。 贝叶斯理论及方法在数据挖掘领域已有很多应用，且已有多种实现算法。 其中，比较著名的算法有以下几类f 5 ，2 6 ，3 2 1 。 在把贝叶斯方法用于分类规则的挖掘算法中，比较著名的是贝叶斯信念构 造算法a 贝叶斯信念网络就是给定一个随机变量集z= 置，x ：，以 ，其中 置是一个m 维向量。贝叶斯信念网络了说明z 上的一条联合条件概率分布。贝 叶斯信念网络定义如下： 口= 其中g 是一个有向无环图，其顶点对应于有限集z 中的随机变量，x ：，以。 1 5 山东科技大学硕士学位论文使用贝叶斯方法的数据挖掘及算法实现 其弧代表一个函数依赖关系；护代表用于量化网络的一组参数。实际上一个贝 叶斯信念网络给定了变量集合z 上的联合条件概率分御 b ( 五，x ：，。) = 兀b ( z ； 砌( 五) ) f 1 贝叶斯信念网络构造算法可以表示如下：给定一组训练样本 d = “，x ：，) ，t 是的实例，寻找一个最匹配该样本的贝叶斯信念网络。 常用的学习算法通常是引入一个评估函数s ( bj d ) ( 常用的评估函数如贝叶斯权 矩阵及最小描述长度函数等) ，使用该函数来评估每一个可能的网络结构与样本 之间的契合度，并从所有这些可能的网络结构中寻找一个最优解。 聚类分析的基本思想是在样品之间定义距离，在变量之间定义相似系数， 距离或相似系数代表样品或变量之间的相似程度，按相似程度的大小，将样品 或变量逐一归类，关系密切的类聚集到一个小的分类单位，然后逐步扩大，使 得关系疏远的聚合到一个大的分类单位，直到所有的样品或变量都聚集完毕， 形成一个表示亲属关系的谱系图，依次按照某些要求对某些样品或变量进行分 类。聚类和分类的主要区别是，在进行聚类分析以前，对总体到底有几种类型 并不知道，对已知数据分几类需在聚类的过程中探索调整，而分类是在事前已 知道分为哪些类。贝叶斯方法用于聚类的挖掘算法目前并不广泛，目前主要是 用简单贝叶斯学习模型来进行聚类。简单贝叶斯学习模型将训练实例1 分解成 特征向量x 和决策类别变量c 。简单贝叶斯模型假定特征向量的分量间相对于 决策变量是相对独立的，也就是说各分量独立的作用于决策变量。尽管这一假 定一定程度上限制了简单贝叶斯模型的适用范围，然而在实际应用中，不仅以 指数级降低了贝叶斯网络构建的复杂性，而且在许多领域，在违背这种假定的 条件下，简单贝叶斯也表现出相当的健壮性和高效性，它已经成功地应用到分 类、聚类及模型选择等数据挖掘的任务中。简单贝叶斯学习模型：贝叶斯定理 的应用之一就是如何通过给定的训练样本集预测未知样本的类别，预测依据就 是取后验概率 p ( c i i 爿) ：丛生2 ：型! 塑 p ( 彳) 1 6 山东科技大学硕士学位论文使用贝叶斯方法的数据挖掘及算法实现 最大的类别。设e 是测试样本，p ( y l x ) 是在给定x 情况下y 的条件概率。 等式右侧的概率都是从样本数据中估计得到的。设样本表示成属性向量，如果 属性对于给定的类别独立，那么p 即| g ) 分解成几个分量的积，即 p ( n 。ie ) p ( 口：ic ) - p ( 口。jg ) ，其中口，是样本e 的第1 个属性。从而后验 概率的计算公式为 粥= 器垂酬g ) 这个过程称为简单贝叶斯分类。 挖掘关联规则是近几年研究较多的数据挖掘方法，在数据挖掘的各种方法 中相比较也是应用的最为广泛，它的算法到目前也相对比较成熟。几个经典的 挖掘算法有a p r i o r i 算法、抽样算法、d i c 算法。著名的a p r i o r i 算法主要工作 在于寻找大物品集，它利用了大物品集的向下封闭性，即大物品集的子集必须 是大物品集，它是一个宽度优先算法。先计算所有的l 一项集( k 一项集是含有k 个项的项集) ，记为c 1 。找出所有的常用1 一项集，记为厶。然后根据常用1 项 集确定候选2 一项集的集合，记为c ，。从c 找出所有的常用2 项集，记为，。 如此下去直到三。o i ) ，即找到最终的n 项集，不再有候选项集为止。另外， 其它的关联规则挖掘方法还用到了模糊集、数组方法和并行挖掘方法等。贝叶 斯方法用于关联分析的算法。目前还没有贝叶斯方法用于发现关联规则的算法。 本文将在这方面加以研究和探讨。 偏差分析的基本思想是寻找观察结果与参照量之间的意义的差别。通过发 现异常，可以引起人们对特殊情况加倍注意。异常包括如下几种可能引起人们 兴趣的模式：不满足常规类的异常例子；出现在其它模式边缘的奇异点；在不 同时刻发生了显著变化的某个元素或集合；观察值与模型推测出的期望值之间 有显著差异的事例等。偏差分析的一个重要特征就是它可以有效的过滤大量的 不感兴趣的模式。 一1 7 山东科技大学硕士学位论文 使用贝叶斯方法的数据挖掘及算法实现 3 2 贝叶斯方法在聚类算法中的研究及其应用 1 聚类算法 聚类分析的基本思想是认为所研究的数据集中的数据或者属性之间存在着 程度不同的相似性。于是从数据集中取出一批数据，具体找出一些能够度量数 据值之间或者属性之问相似程度的量，以这些量为中心作为划分类型的依据， 把一些相似程度较大的数据或属性聚合为一类，把另外一些彼此之间相似程度 较大的样品又聚合为另一类，关系密切的聚合到一个小的分类单位，关系疏远 的聚合到一个大的分类单位，直到所有数据或属性都聚合完毕，把不同的类型 一一划分出来。 聚类的实质就是使属于同一类别的个体之间的距离尽可能地小，而不同类 别的个体间的距离尽可能地大。因此需要用到各种不同的距离度量测度来判定 类别。有多种距离公式，比较常用的距离。“有： 绝对值距离 办= k b ( 3 1 ) 欧氏距离 办= 【( 靠一) 2 r ( 3 2 ) 明斯基距离 r 。 ， 以( 工；，z ) = l h b 川 ( 3 3 ) l f = lj 聚类分析通常根据类对象的不同分为q 型和月型两大类。q 型是对数据集 中的数据值进行分类处理，r 型是属性进行分类处理。q 型聚类分析的优点主 要是： ( 1 ) 可以综合多个属性的信息对数据值进行分类； ( 2 ) 分类结果是直观的，用一个分类谱系图就能非常清楚的表现其数值分类结 果： ( 3 ) 聚类分析所得到的结果比传统的分类方法更细致、全面、合理。 】8 山东科技大学硕士学位论文 使用贝叶斯方法的数据挖掘及算法实现 本文也主要讨论q 型聚类问题，即直接对数据值进行聚类。 下图是一个简单的聚类直观的图形表示，其中聚类中心分别为( 1 ，2 ) 和 ( 5 ，3 ) 3手勺 中+ - + 7 孑 01 2 r 5x 图3 1 以( 1 ，2 ) 和( 5 ，3 ) 为中心的两类 由于贝叶斯方法的主要特点是通过先验信息来推得后验知识，如果将贝叶 斯方法进行聚类，其基本思想就是： 首先根据先验信息假定数据集中可能要聚为一类的数据服从某种分布，再 用某种距离测度检验先验信息给出的这种分布是否符合聚为一类的要求。如果 达不到聚类的要求，则根据计算概率找出不符合要求的原因，重新确定其分布， 或修正此分布的参数，以获得更准确的分布。 具体分析一下与聚类相关的问题：给定数据集，它满足以下两个条件 1 类的数目是未知的； 2 有哪些类是未知的。 与这两个条件相对应，聚类的目的是： 1 确定一些合适的聚类中心； 2 弄清类的数目尼； 3 发现合理的聚类方法； 4 把数据分类到七个类别中。 针对聚类的问题及其目的，设计完整的算法如下： s t e p l ：确定聚类中心数据，即围绕哪些数据进行聚类； s t e p 2 ：对每一确定的以聚类中心数据为聚类依据的类，根据先验信息假定其 分布厅( 们，作为贝叶斯公式的先验概率； 一1 9 山