（通信与信息系统专业论文）基于数据挖掘技术的智能信息处理.pdf

哈尔滨t 程大学硕十学佛论文 摘要 在全球性的网络化、信息化进程中，信息过量成为人人需要面对的问题， 也就为信息处理提出了新的要求。信息处理技术由查询、统计、分析方法学 延伸和扩展到数据挖掘技术。 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中， 提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过 程。数据挖掘是当今国际上人工智能和数据库研究方面最富活力的新兴领域， 其目标是为了满足用户需求，自动处理大量的原始数据，从中识别重要和有 意义的模式，并将其作为知识加以表达。 本文首先阐述了数据挖掘的基本概念及处理方法，论述了基于关联规则 的a p r i o r i 算法及其改进的相关算法，研究了分类方法中的贝叶斯网络分类方 法和判定树分类算法及聚类方法。然后将全国计算机等级考试、网络日志、 大型超市的数据库作为数据源，以b a y e s i a f l 网络的数据补全算法、基于关联 规则的a p r i o r i 并行算法、基于分类的判定树归纳算法和基于聚类的k 簇算法 为基础，重点研究以上数据挖掘算法的改进以及对上述数据源的智能信息处 理。成功地解决了信息处理中只能进行查询、统计等功能，面无法对数据中 潜在有用的信息和知识进行提取的弊端。 关键词：数据挖掘：智能信息处理；数据补全算法；a p r i o r i 并行算法 哈尔滨t 程大学硕十学位论文 a b s t r a c t d u r i n gt h ep r o c e s so fg l o b a ln e t w o r ka n di n f o r m a t i o nc h a n g e ，i n f o r m a t i o n o v e r a g eb e c o m e st h ep r o b l e mt h a te v e r y o n eh a st od e a lw i t h , w h i c hm a k et h en e w r e q u e s tt oi n f o r m a t i o nt r e a t m e n t i n f o r m a t i o nt r e a t m e n tt e c h n o l o g ye x t e n d sa n d e x p a n d sf r o me n q u i r y , s t a t i s t i c s ，a n a l y s i sm e t h o d o l o g yt od a t am i n i n gt e c h n o l o g y d a t em i n i n gi st h ep r o c e s so fg e t t i n gd o r m a n t ，u n k n o w l lb u tl a t e n tu s e f u l i n f o r m a t i o nf r o mt h ea b u n d a n t ，i n c o m p l e t e ，n o i s e ，f u z z ya n ds t o c h a s t i cd a t a t h e d a t am i n i n gi st h em o s tp o p u l a ra n dl a t e s tt e c h n o l o g yi nt h ec u r r e n ti n t e r n a t i o n a l a r t i f i c i a l i n t e l l i g e n c ea n dd a t a b a s er e s e a r c hf i e l d ，t h e a i mi st om e e tt h e e n l l , s l l m e r sr e q u i r e m e n ta n dm a n a g ev a s to r i e , i h a ld a t aa u t o m a t i c a l l y , i d e n t i f yt h e i m p o r t a n ta n dm e a n i n g f u lm o d e lf r o mi ta n de x p r e s si ta sak n o w l e d g e t h i sa r t i c l ef i r s te x p a t i a t e st h eb a s i cc o n c e p ta n dm a n a g i n gm e t h o do ft h e d a t am i n i n g ，d i s c u s st h ea p d o f ia r i t h m e t i ca n di t si m p r o v e dc o r r e l a t e da r i t h m e t i c o ft h ea s s o c i a t i o nr u l e s ；b e y e s i a nn e t w o r ks o r t i n gm e t h o da n dd e t e r m i n a n tt r e e c l a s s i f i c a t i o na r i t h m e t i c ，c l u s t e r i n gm e t h o da n dw e bm i n i n g t h e nu s i n gt h e d a t a b a s eo f n a t i o n a lc o m p u t e rr a n ke x a m ，n e t w o r kl o ga n ds u p e rm a r k e ta s t h ed a t al x ! s o u r c e ，b a s e do nd a t af i l ld e f a u l ta r i t h m e t i co fb a y e s i a nn e t w o r k ， a p f i o r ip a r a l l e l a r i t h m e t i co fa s s o c i a t i o nr u l e s ，d e t e r m i n a n tt r e ei n d u c t i o no f c l a s s i f i c a t i o nr u l e sa n dk c l u s t e ra r i t h m e t i co fc l u s t e r i n ga l g o r i t h m ，f o c u so nt h e i m p r o v e m e n to ft h ea b o v ea r i t h m e t i ca n di n t e l l i g e n ti n f o r m a t i o np r o c e s s i n go n t h ea b o v ed a t ar e s o u r c e s s u c c e e di nr e s o l v i n gt h ep r o b l e mo fs i n g l ef u n c t i o no f q u e r ya n ds t a t i s t i ci ni n f o r m a t i o np r o c e s s i n ga n dt h em a l p r a c t i c eo fd i s t i l ld a t ao f i a t e n tu s e f u li n f o r m a t i o n k e y w o r d s ：d a t am i n i n g ；i n t e l l i g e n ti n f o r m a t i o np r o c e s s i n g ；d a t af i l l d e f a u l t a r i t h m e t i c ；a p r i o r ip a r a l l e la r i t h m e t i c 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文的所有工作，是在导 师的指导下进行的研究工作及取得的研究成果。尽我所知， 除文中已注明的有关观点、方法、数据和文献的引用的内容 外，本论文不包含任何其他个人或集体已经公开发表的作品 成果。对本文的研究做出重要贡献的个人和集体，均己在文 中以明确方式标明。本人完全意识到本声明的法律结果由本 人承担。 作者( 签字) ：剧 日期：哼年i - 月；日 哈尔滨t 稃大学硕+ 学位论文 1 1 课题的目的和意义 第1 章绪论 在当今信息爆炸的时代，信息过量几乎成为人人需要面对的问题。如何 才能不被信息的汪洋大海所淹没，从中及时发现有用的知识，智能进行信息 地处理，提高信息利用率；如何从大量的数据中找到真正有用的信息成为人 们关注的焦点。数据挖掘技术也正是伴随着这种需求从研究走向应用。数据 挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机的数 据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知 识的过程。 人们把原始数据看作是形成知识的源泉，就像从矿石中采矿一样。原始 数据可以是结构化的，如关系型数据库中的数据，也可以是半结构化的，如 文本、图形、图像数据，甚至是分布在网络上的异构型数据。发现知识的方 法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。发 现了的知识可以被用于信息管理、查询优化、决策支持、过程控制等，还可 以用于数据自身的维护。因此，数据挖掘是- - n 广义的交叉学科，它汇聚了 不同领域的研究者。尤其是数据库、人工智能、信息处理、数理统计、可视 化、并行计算等方面的学者和工程技术人员。同时数据挖掘思想也为a i 的发 展指出了一个新的研究方向【“2 一l ，使智能信息处理有了新的技术和手段。 现有技术中的查询、统计、分析是在已有的假设基础上，从大量的数据 中得到验证。数据挖掘是在没有明确假设的前提下去挖掘信息，发现知识 ( k d d ) ，所得结果具有事先未知、有效和可实用三个特征。数据挖掘不是 为了替代传统的查询与分析技术，相反它是查询、统计、分析方法学的延伸 和扩展，是从大量的数据中得到崭新的模式、结论和假设( 发现数据间的关 系和规则) 。数据挖掘是要发现那些不能靠直觉发现的信息或知识，挖掘出的 信息越是出乎意料，就越有价值。 数据挖掘的核心部分是为数据集建立模型的过程，不同的数据挖掘方法 构造数据模型的方式也不相同，在进行数据挖掘时可采用许多不同的方法， 哈尔滨t 释大学硕十学何论文 例如关联规则发现、神经网络、判定树、遗传算法和可视化技术等，而且同 一方法下又有数以百计的派生方法。 1 2 数据挖掘的现状及应用领域 1 2 1 国内外研究现状及发展趋势 从数据库中发现知识( i d ) 一词首次出现在1 9 8 9 年举行的第十一届国 际联合人工智能学术会议上。1 9 9 5 年，在加拿大蒙特利尔召开的首届知识发 现k d d ( k n o w l e d g ed i s c o v e rd a t a b a s e ) 与数据挖掘国际学术会议上，数据挖 掘这一术语被学术界正式提出。 目前，国外数据挖掘技术的主要研究方面有：注重对b a y e s i a n ( 叶斯) 方法以及b o o s t i n g ( 布斯厅) 方法的研究和提高；传统的统计学回归法在k d d 中的应用；k d d 与数据库的紧密结合等。在i n t e m e t 上有不少k d d 电子出版物， 其中以半月刊k n o w l e d g e d i s c o v e r y n u g g e t s 最为权威，还可以下载各种各样的 数据挖掘工具软件和典型的样本数据仓库，供人们测试和评价【4 5 l 。k d d 成 为当前计算机科学界研究的一大热剧“7 i 。k d d 商业软件工具不断产生和完 善，注重建立解决问题的整体系统，而不是孤立的过程。用户主要集中在大 型银行、保险公司、电信公司和销售业。国外很多计算机公司非常重视数据 挖掘的开发应用，i b m 和微软都成立了相应的研究中心进行这方面的工作， 此外，一些公司的相关软件也开始在国内销售，如b o 以及i b m 。 与国外相比，国内对数据挖掘的研究起步稍晚，且没有形成整体力量。 1 9 9 3 年国家自然科学基金首次支持国内研究机构对该领域的研究项目。目前， 国内从事数据挖掘研究的人员主要在大学，也有部分在研究所或公司。所涉 及的研究领域很多，一般集中于学习算法的研究、数据挖掘的实际应用以及 有关数据挖掘理论方面的研究。目前进行的大多数研究项目是由政府资助进 行的，如国家自然科学基金、8 6 3 计划、“九五”计划等，但还没有关于国内 数据挖掘产品的报道。 当前，数据挖掘和知识发现的研究方兴未艾，其研究与开发的总体水平 相当于数据库技术在7 0 年代所处的地位，迫切需要类似于关系模式、d b m s 系统和s q l 查询语言等理论和方法的指导。鉴于数据、数据挖掘任务和数据 哈尔滨t 程大学硕十学位论文 挖掘方法的多样性，给数据挖掘技术提出了许多挑战性的课题l “9 o l ，如数 据挖掘应用的探索；可伸缩的方法：交互式发现：与数据库系统、数据仓库 系统和w e b 数据库系统的集成；数据挖掘语言的标准化；可视化数据挖掘； 复杂数据类型挖掘；w e b 挖掘；隐私保护和信息安全等。 1 2 2 应用领域 数据挖掘所要处理的问题，就是在庞大的数据库中找出有价值的隐藏事 件，并且加以分析，获取有意义的信息，归纳出有用的结构，作为企业进行 决策的依据。其应用非常广泛，只要该产业有分析价值与需求的数据库，皆 可利用m i n i n g i 具进行有目的的挖掘分析。数据挖掘工具的出现，己经让人 们意识到数据挖掘技术带来的有利的应用前景。它的应用主要体现在以下几 个方面： ( 1 ) 通信行业中的应用 随着市场竞争的日趋激烈，通信运营商的经营模式逐渐从“技术驱动” 向“市场驱动”和“客户驱动”转化。这就要求运营商要采取以客户为中心 的策略，根据客户的实际需求提供多样化、层次化、个性化的服务解决方案。 因此，客户关系管理( c r m ) 成了通信运营商增加收入和利润，提高客户满意 度、忠诚度的有效工具。在客户关系管理的流程中，为了准确、及时地进行 经营决策，必须充分获取并利用相关的数据信息对决策过程进行辅助支持。 数据挖掘技术就是实现这一目标的重要手段。数据挖掘技术在通信行业客户 关系管理的主要应用包括：客户消费模式分析、客户市场推广分析、客户欠 费分析和动态防欺诈、客户流失分析等。 ( 2 ) 科学研究领域 从科学研究方法学的角度看，随着先进的科学数据收集工具的使用，如 遥感遥测、天文观测、d n a 分子技术等，数据量非常大，传统的数据分析工 具己经无能为力，因此迫切需要一种强大的智能性自动数据分析工具。这种 需求推动了数据挖掘技术在科学研究领域的应用发展，并取得了一些重要的 成果。 ( 3 ) 商业零售业 零售业积累了大量的销售数据，顾客购买历史记录、货物进出、消费与 哈尔滨t 程大学硕十学佛论文 服务记录等。其数据量在不断地迅速膨胀，特别是由于日益增长的电子商务 上的商业方式的方便和流行，使得零售业成为数据挖掘的一个重要应用领域。 商场是以获得最大利润为目的的。那么销售什么样的商品、采用什么样的销 售策略就成为商家最关心的问题。通过数据挖掘( 如关联规则挖掘) 能够对 商场销售数据进行分析，从而得到顾客的购买特性，并据此采取有效的策略， 促进利润最大化的形成。 ( 4 ) 制造行业中的应用 许多公司不仅将基于数据挖掘的决策支持系统用于支持市场营销活动， 而且，由于市场竞争越演越烈，这些公司己使用决策支持系统来监视制造过 程，有制造商声称己经指示它的各个办事机构，在三年内把制造成本每年降 低2 5 。不言而喻，该制造商经常收集各部件供应商的情况。因为，它们也 必须遵循该制造商降低成本的战略。为了对付来自各方的挑战，该制造商已 拥有一套“成本”决策支持系统，可以监视各供应商提供的零部件成本，以 实现所制定的价格目标。 ( 5 ) 金融投资业 很多银行和金融机构都提供丰富多样的储蓄服务、信用服务和投资服务， 有些还提供保险服务和股票投资服务。在其中产生的数据通常相对比较完善、 可靠和高质量，这大大方便了系统化的数据分析和数据挖掘。如在银行业务 中，可以根据客户信用政策分析，尽量降低银行的贷款风险，同时对信用度 不同的客户调整贷款发放政策。对金融数据的分析还可以侦破洗黑钱和其他 金融犯罪活动。 当然，数据挖掘的应用领域还远远不止以上所提到的。对医药数据的挖 掘可用于病例、病人行为特征的分析，以及用于药方的管理；对司法数据的 挖掘可以用于案件调查、案例分析、犯罪监控；对生产加工数据的挖掘可用 于进行故障诊断、生产过程优化：对网络入侵检测数据的挖掘可以发现异常 的访问模式，从而有效地防止黑客的攻击。 1 3 论文的主要工作及章节安排 本课题以全国计算机等级考试、网络日志和大型超市等的数据库为数据 4 哈尔滨t 程大学硕十学位论文 源，重点研究数据挖掘算法在上述数据源状态下的应用与算法的改进。 本论文主要工作是： 1 对数据挖掘技术的产生、功能、可以发现的知识模式和实施步骤等 基本理论知识进行了简要的介绍。 2 对关联规则的定义给予了详细的描述，介绍了关联规则的种类和经典 关联规则挖掘算法a 嘶o r i 算法及其若干己有的改进算法。在此基础上给出改 进的a 面o r i 并行化的算法。 3 讨论了分类算法及贝叶斯网络( b a y e s i a nn e t w o r k ) 分类算法和判定树 算法。在此基础上提出b a y e s i a i l 网络的数据补全算法并改进了基于分类的判 定树归纳算法。 4 总结了聚类算法种类，在此基础上提出改进的基于聚类的k 簇算法。 5 将改进算法在智能信息处理系统中运行和测试。 本论文共分为6 章。第1 章绪论，介绍了本课题的研究目的和意义及本 课题目前国内国际的发展状况和应用领域。第2 章数据挖掘基础理论，介绍 了数据挖掘的相关理论与技术，包括数据挖掘的定义、数据挖掘的数据来源、 数据挖掘的分类与方法、数据挖掘的体系与步骤、数据挖掘的相关技术等。 第3 章关联规则挖掘，阐述关联规则的定义和方法分类，并给出经典关联规 则挖掘算法a p r i o r i 算法及其若干已有的改进算法。第4 章分类方法研究，介 绍了分类的基本概念和算法种类，具体研究了贝叶斯网络分类法、i d 3 和c 4 5 判定树算法。第5 章聚类的研究，主要介绍聚类的概念及几种聚类方法。第 6 章智能信息处理，提出了b a y e s i a n 网络的数据补全算法、基于关联规则的 a p r i o r i 并行算法、基于分类的判定树归纳算法和基于聚类的k 簇算法的改进 算法，并将几种算法应用到全国计算机等级考试、网络日志和大型超市的数 据库为数据源的数据挖掘过程，实现智能信息处理。最后给出的本课题研究 结论。 哈尔滨t 程大学硕十学位论文 第2 章数据挖掘理论 2 1 数据挖掘及有关概念 2 1 1 数据挖掘的概念 数据挖掘( d a t am i n i n g ) 是指从大型数据库或数据仓库中存储的大量的、 不完全的、有噪声的数据中，发现隐含在其中的、人们事先不知道的、但又 是潜在有用的信息和知识的过程。提取的知识一般可以表示为概念、规则、 规律、模式等形式。数据挖掘所研究的知识发现，不是要求发现放之四海皆 准的知识，也不是要去发现全新的科学定律。实际上，它所发现的知识都是 相对的，都具有特定前提和约束条件的。它必须面向特定的应用领域，同时 发现的知识还要易于被用户所理解。 2 1 2 数据挖掘的产生 随着计算机硬件和软件的飞速发展，尤其是数据库技术与应用的日益普 及，人们面l 临着快速扩张的数据海洋，如何有效利用这一丰富数据海洋的宝 藏为人类服务，业已成为广大信息技术工作者所重点关注的焦点之一。与日 趋成熟的数据管理技术和软件工具相比，人们所依赖的数据分析工具功能， 却无法有效地为决策者提供其决策支持所需要的相关知识，从而形成了一种 独特的现象一“丰富的数据，贫乏的知识”。为有效解决这一问题，自2 0 世纪8 0 年代开始，数据挖掘技术逐步发展起来，数据挖掘技术的迅速发展， 得益于目前全世界所拥有的巨大数据资源以及对将这些数据资源转换为信息 和知识资源的巨大需求，对信息和知识的需求来自各行各业，从商业管理、 生产控制、市场分析到工程设计、科学探索等。数据挖掘可以视为是数据管 理与分析技术的自然进化产物。 f 1 2 0 世纪6 0 年代开始，数据库及信息技术就逐步从基本的文件处理系统 发展为更复杂功能、更强大的数据库系统：7 0 年代的数据库系统的研究与发 展，最终导致了关系数据库系统、数据建模工具、索引与数据组织技术的迅 6 哈尔滨t 程大学硕十学何论文 速发展，这时用户获得了更方便灵活的数据存取语言和界面：此外在线事务 处理手段的出现也极大地推动了关系数据库技术的应用普及，尤其是在大数 据量存储、检索和管理的实际应用领域j 。 自2 0 世纪8 0 年代中期开始，关系数据库技术被普遍采用，新一轮研究与 开发新型与强大的数据库系统悄然兴起，并提出了许多先进的数据模型：扩 展关系模型、面向对象模型、演绎模型等；以及应用数据库系统：空间数据 库、时序数据库、多媒体数据库等；异构数据库系统和基于互联网的全球信 息系统也开始出现并在信息工业中开始扮演重要角色。目前数据库界除了关 注万维网数据库、分布式数据库、面向对象数据库、多媒体数据库、查询优 化和并行计算等技术外，已经在开始反思，数据库最实质的应用仅仅是查询 吗? 理论根基最深的关系数据库最本质的技术进步点，就是数据存放和数据使 用之间的相互分离。然而，人们越来越清楚的发现“查询是数据库的奴隶， 发现才是数据库的主人”1 1 2 , ”j 。 被收集并存储在众多数据库中且正在快速增长的庞大数据，己远远超过 人类的处理和分析理解能力( 在不借助功能强大的工具情况下) ，这样存储 在数据库中的数据就成为“数据坟墓”，即这些数据极少被访问，结果许多 重要的决策不是基于这些基础数据而是依赖决策者的直觉而制定的，其中的 原因很简单，这些决策的制定者没有合适的工具帮助其从数据中提取出所需 的信息知识。而数据挖掘工具可以帮助从大量数据中发现所存在的特定模式 规律，从而可以为商业活动、科学探索和医学研究等诸多领域提供所必需的 信息知识。数据与信息知识之间的巨大差距迫切需要系统地开发数据挖掘工 具，来帮助实现将“数据坟墓”中的数据转化为知识财富( f “。 2 1 3 数据挖掘的对象 从原则上讲，数据挖掘可以在任何类型的信息存储上进行，可以是结构 化的数据源，也可以是半结构化的，还可以是高级数据库系统和面向特殊应 用的数据库。结构化的数据源包括关系数据库、数据仓库、事务数据库等： 半结构化的数据源包括文本数据库等；高级数据库系统包括面向对象和对象 关系数据库；面向特殊应用的数据库系统包括空间数据库、时间序列数据 库、多媒体数据库以及w e b 数据库。在这些数据源中，由于关系数据库应用 7 哈尔滨t 耩! 大学硕十学佛论文 广泛，具有统一的组织结构，规范通用的查询语言，目前仍然是数据挖掘的 主要对象。 2 1 4 数据挖掘的功能 数据挖掘的功能用于指定数据挖掘任务中要寻找的模式类型。数据挖掘 的任务一般可以分两类：描述和预测。描述性挖掘任务刻画数据库中数据的 一般特性；预测性挖掘任务在当前数据上进行推断，以进行预测。 数据挖掘的功能有：概念，类描述、关联分析、分类和预测、聚类分析、 孤立点分析和演变分析。 1 概念类描述 数据可以和类或概念相关联。可以用汇总的、简洁的、精确的方式描述 概念和类，称为概念类描述。这种描述可以通过以下方法得到： ( 1 ) 数据特征化：目标类数据的一般特征或特征的汇总； ( 2 ) 数据区分：将目标对象的一般特征与一个或多个对比类对象的一般 特征比较； ( 3 ) 数据特征化和区分：同时应用数据特征化和数据区分来进行概念 类的描述。 2 关联分析 关联分析用于发现关联规则这些规则展示了给定数据集中数据项之间 的潜在的联系。关联分析广泛应用于购物篮或事务数据分析中。 3 分类和预测 分类找出描述并区分数据类或概念的模型，以便能够使用模型预测类、 标记未知的对象类。预测是构造和使用模型评估无标号样本类，或评估给定 样本可能具有的属性值或值区间。分类和预测的区别在于：分类是预测分类 标号( 或离散值) ：预测是建立连续值函数模型。 4 聚类分析 聚类就是将数据对象分组成为多个类或簇，在同一个簇中的对象之间有 较高的相似度，而不同簇中的对象差别较大。与分类不同的是，聚类要划分 的类是未知的。 5 孤立点分析 8 哈尔滨t 程大学硕十学位论文 孤立点可能是度量或执行错误所导致的，也可能是固有的数据变异性的 结果。许多数据挖掘算法试图使孤立点的影响最小化。但这可能导致重要信 息丢失，因为孤立点本身可能是非常重要的。 6 演变分析 数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模。 它包括时间序列数据分析、序列或周期模式匹配和基于类似性的数据分析。 2 1 5 数据挖掘模式 数据挖掘发现的知识模式有多种不同的类型，常见的模式有：分类模式、 聚类模式、关联模式、序列模式等。 1 分类模式 分类模式是反映同类事物间的共性以及异类事物间的差异的特征知识。 它可以提取数据类的特征模型，进而预测事物发展的趋势。分类模式往往表 现为一颗分类树，从树根开始搜索，沿着满足条件的分支走，走到树叶就能 确定类别。已经有许多数据分类的方法，如判定树、统计方法、神经网络等 等。其中判定树方法由于具有速度快、精度高、生成模式简单等优点而广泛 应用。 2 聚类模式 聚类模式与分类模式不同，它在事先不知道分组及如何分组的情况下。 根据一定的基本规则，把数据划分到不同的组中，组之间的差别应尽可能大， 而组内的差别则应尽可能小。聚类模式的挖掘可以采用统计方法、机器学习 方法等。 3 关联模式 关联模式也称为关联规则，是数据挖掘的一个重要课题。关联规则广泛 应用于购物篮或者事务数据的分析当中。例如，在无力偿还贷款的人当中， 6 0 的人的月收入在3 0 0 0 元以下。 4 序列模式 序列模式与关联模式相仿，而把数据之间的关联性与时间联系起来。序 列模式不仅需要考虑事件是否发生，而且需要考虑事件发生的时间因素。例 如，在购买彩电的人们当中，6 0 的人会在3 个月内购买影碟机。 9 哈尔滨t 程大学硕十学位论文 2 。1 6 挖掘的实施步骤 数据挖掘的实施包括：问题的理解和提出、数据准备、数据整理、建立 模型及评价和解释等步骤，如图2 1 所示。 图2 1 数据挖掘的实施步骤 l 问题的理解和提出 在开始数据挖掘之前最基础的就是理解数据和实际的业务问题，在这一 基础上提出问题，对目标有明确的定义。本课题选择了两部分数据进行了分 析和问题的提出，一是网上大型超市数据库，二是齐大学生全国计算机等级 考试数据库、三是网络日志等数据库为数据源进行了研究和分析，提出了系 统设计目标和实施步骤。 2 数据准备 在数据挖掘之前数据准备工作是非常重要的，数据挖掘的成功与否，数 据准备起到至关重要的作用。数据准备是对数据源进行处理，对缺损、不一 致的数据实施算法，以保证数据的综合性、易用性、准确性。本课题采用了 基于b a y e s i a n 网络的数据补全算法。 3 数据整理 由于数据可能是不完全的、有噪声的、随机的，有复杂的数据结构，就 要对数据进行初步的整理，清洗不完全的数据，做初步的描述分析，选择与 数据挖掘有关的变量，或者转变变量。 0 哈尔滨t 释大学硕十学佛论文 不完整数据的出现可能有多种原因l j 5 ”j ： ( 1 ) 有些数据无法获得。某些感兴趣的属性，如销售事务数据中顾客的 收入、年龄等信息，由于涉及到个人隐私等原因可能无法获得： ( 2 ) 数据输入时疏漏。有些数据在输入时可能认为是不重要的，或者由 于理解错误、设备故障等原因对原始数据进行了删除。这些缺损的数据，特 别是某些属性缺少值的元组可能需要推导； ( 3 ) 噪声数据。数据包含噪声( 具有不正确的属性值) 可能有多种原因。 数据采集的设备可能出现故障，人为的或计算机的错误，数据传输中的错误 ( 如用于数据传输同步的缓冲区大小的限制) 等都可能导致噪声数据产生； ( 4 ) 命名或编码不一致。在进行数据挖掘时往往要将几个不同的数据表 集成到一起，同一个属性在不同的数据表中可能会有不同的命名或编码。例 如，在零售商场的销售事务数据库中“顾客编号”在一个表中命名为 c u s t o m e ri d ，而在另外一个表中可能命名为c u s t o m e rn u m b e r ： ( 5 ) 重复元组也需要清理。多个数据表在集成时很可能会产生重复元组， 数据预处理时必须迸行清除。 4 建立模型 根据数据挖掘的目标和数据特征，选择合适的模型。 5 。评价和解释 对数据挖掘的结果进行评价，选择最优的模型，作出评价，运用于实际 问题，并且要和专业知识结合对结果进行解释。 2 。2 数据挖掘的研究工作 数据挖掘的研究工作主要是围绕如下几个方面展开的： 】挖掘法的效率和可扩展性。目前数据库数据量大，维数高。使得数据 挖掘的搜索空间增大，发现知识的盲目性提高。如何充分利用领域的知识， 剔除与发现任务无关的数据，有效地降低问题的维数，设计出高效率的知识 发现算法是下一步发展的重点，它包括领域知识对行业或企业知识挖掘的约 束与指导、商业逻辑有机嵌入数据挖掘过程等关键课题。 2 数据挖掘理论与算法研究。经过十几年的研究，数据挖掘己经在继承 哈尔滨丁程大学硕士学位论文 和发展相关基础学科f 如模式识别、机器学习、统计学等) 己有成果方面取得 了可喜的进步，探索出了许多独具特色的理论体系。但是，这决不意味着数 据挖掘理论的探索已经结束，恰恰相反它留给了研究者丰富的理论课题。一 方面，在这些大的理论框架下有许多面向实际应用目标的挖掘理论等待探索 和创新。另一方面，随着数据挖掘技术本身和相关技术的发展，新的挖掘理 论的诞生是必然的，而且可能对特定的应用产生推动作用。新理论的发展必 然促进新的挖掘算法的产生，这些算法可能扩展挖掘的有效性，如针对数据 挖掘的某些阶段、某些数据类型、大容量源数据集等更有效，可能提高挖掘 的精度或效率，可能融合特定的应用目标，如c r m 、电子商务等。因此，对 数据挖掘理论和算法的探讨将是长期而艰巨的任务。 3 数据的时序性。在应用领域的数据库中，数据在不断地更新，随着时 间的推移，原先发现知识的有用性将降低。我们需要随时间逐步修正发现模 式来指导新的发现过程。 4 数据挖掘系统的构架与交互式挖掘技术。虽然经过多年的探索，数据 挖掘系统的基本构架和过程己经趋于明朗，但是受应用领域、挖掘数据类型 以及知识表达模式等的影响，在具体的实现机制、技术路线以及各阶段或部 件( 如数据清洗、知识形成、模式评估等) 的功能定位等方面仍需细化和深入 研究。由于数据挖掘是在大量的数据源集中发现潜在的、事先并不知道的知 识，因此和用户交互式进行探索性挖掘是必然的。这种交互可能发生在数据 挖掘的各个不同阶段，从不同角度或不同粒度进行交互。所以良好的交互式 挖掘( i n t e r a c t i o nm i n i n g ) 也是数据挖掘系统成功的前提。 5 数据挖掘语言与系统的可视化问题。对o l t p ( o n l i n et r a n s a c t i o n p r o c e s s i n g ) 应用来说，结构化查询语言s q l 己经得到充分发展，并成为支持 数据库应用的重要基石。但是，对于数据挖掘技术而言，由于诞生的较晚， 加之它相比o l t p 应用的复杂性，开发相应的数据挖掘操作语言仍然是一件 极赋挑战性的工作。可视化要求已经成为目前信息处理系统的必不可少技术。 对于一个数据挖掘系统来说，它显得更为重要。可视化挖掘除了要和良好的 交互式技术结合外。还必须在挖掘结果或知识模式的可视化、挖掘过程的可 视化以及可视化指导用户挖掘等方面进行探索和实践。 哈尔滨t 程大学硕十学位论文 6 互联网上知识的发现。w w w 正日益普及，从中可以找到很多新的 知识，已有一些资源发现工具来发现含有关键字的文本。加拿大的h a r t 等人 提出利用多层次结构化的方法【l7 1 ，通过对原始数据的一般化，构造出多层次 的数据库。例如可将w w w 上的图象描述而不是图象本身存储在高层数据 库中，现在的问题是如何从复杂的数据( 例如多媒体数据) 中提取有用的信息。 对多层数据库的维护，及如何处理数据的异类性和自主性等等。 2 3 本章小结 本章主要介绍了数据挖掘的相关理论与技术包括数据挖掘的定义、数 据挖掘的功能、数据挖掘的模式和实施步骤等，并通过挖掘法的效率和可扩 展性、数据挖掘理论与算法研究、数据的时序性、数据挖掘系统的构架与交 互式挖掘技术、数据挖掘语言与系统的可视化问题及互联网上知识的发现等 六个方面总结了数据挖掘的研究工作。 哈尔滨t 程大学硕十学位论文 第3 章关联规则挖掘 3 1 关联规则基本概念 关联规则挖掘结果【1 4 】通常告诉人们类似这样的一条知识：。在购买面包 和黄油的顾客中，有9 0 的人同时也买了牛奶”( 购买面包十黄油j 购买牛 奶) 。 关联规则最早是用于超市客户的购物事务的分析，它可以帮助如何摆放 货架上的商品( 如把顾客经常同时买的商品放在一起) ，帮助如何规划市场( 怎 样相互搭配进货) 。因此用于关联规则发现的主要对象是事务型数据库，一个 事务一般由如下几个部分组成：事务处理时间，一组元素，事务标识号。 设卢i 2 ，) 是一组元素集，d 是一组事务集( 称之为事务数据库) 。 d 中的每个事务t 是一组元素，显然满足r j 。称事务t 支持物品集x ，如果 x t ，那么关联规则是如下形式的一种蕴含：x = y ，其中x ，y ， 且x n y = i 。如果d 中有s 的事务支持元素集x ，称物品集x 具有大小为s 的支 持度；如果元素集x o y 的支持度为s ，称关联规：j x = c y 在事务数据库d 中具 有大小为s 的支持度；如果d 中支持物品集x 的事务中有c 的事务同时也支持 物品集y ，称规则x _ y 在事务数据库d 中具有大小为c 的萱信度。 用形式化语言表示就是： 置信度c o n f i d e n c e ( a ： b ) ：p ( bia ) ：s u p _ c o u n t ( _ a _ u - b )( 3 1 ) s u p _ c o u n t ( a ) 支持度s u p ( a = b ) = p ( a ub )( 3 2 ) 同时满足最小支持度阈值和最小置信度闽值的规则称为强规则。给定 个事务集d ，挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的 最小支持度和最小可信度的关联规则，也就是产生强规则的f 司题。 挖掘关联规则问题可以分解为以下两个子问题 1 8 , 1 9 ： ( 1 ) 找出存在于事务数据库中的所有频繁项集。项集x 的支持度 s u p p o r t c x ) 不小于用户给定的最小支持度m i n s u p ，则称x 为频繁项集( 1 a r g e i t e ms e t ) 。 1 4 哈尔滨t 程大学硕十学位论文 ( 2 ) 利用频繁项集生成关联舰则。对于每个频繁项集a ，若b c a ，b ， 且竺旦旦竺! 尝r n i n c o n f , 则有关联规则b = 亭( a b ) 。 s u p p o r t t u ) 第( 2 ) 个子问题比较容易，其生成算法可参见文献【1 9 1 。目前大多数研究集 中在第一个子问题上。 r a g r a w a l 等人在文献【1 8 】中首先提出了关联规则的挖掘问题并给出解决 此问题最原始的算法a i s 之后，该问题得到了国际人工智能和数据库等领域 学者的密切关注，提出了多种的算法。所有的挖掘关联算法不论它是采用什 么数据结构，其复杂程度、效率如何，它们都可以分为如下几个步骤： ( 1 ) 预处理与挖掘任务有关的数据。根据具体问题的要求对数据库进行 相应的操作，从而构成规格化的数据库d 。 ( 2 ) 针对d ，求出所有满足最小支持度的项集，即频繁项集。由于一般 情况下我们所面临的数据库都比较大，所以此步是算法的核心。 ( 3 ) 生成满足最小置信度的规则，形成规则集r 。 ( 4 ) 解释并输出r 。 3 2 关联规则方法分类 现有的各种关联规则算法大致可分为搜索算法、层次算法、数据集划分 算法、抽样算法等1 2 0 l 。 1 搜索算法：搜索算法在读入数据集中的每条事务时，对该事务中包含 的所有项目集进行处理，因此搜索算法需计算数据集d 中所有项目集的支持 数。a i s 算法、s t e m 算法，以及以建格算法为主体的关联规则挖掘算法都是 这种搜索算法。 搜索算法只需对数据集一次扫描就可以找出所有的频繁项目集，对每一 条包含n 个项目的事务就将产生2 “个项目集，数据集d 中包含的项目数很大时， 所需计算和存储的候选项目集的数量往往非常庞大。因此，该类算法只适合 于项目集数量相对较小的数据集中的关联规则挖掘。 2 层次算法：a p r i o r i 算法【2 lj 为代表的层次算法是按含项目数自小而大的 顺序寻找频繁项目集。a p r i o r i 的算法在第k 次扫描数据集时找出所有的频繁k 项目集。第k + 1 次扫描数据集时的候选项目集由所有的频繁k 项目集通过连接 哈尔滨t 程大学硕十学位论文 运算产生。 3 数据集划分算法：数据集划分算法包括p a r t i t i o n 算法、d i c 算法等， 这些算法将整个数据集划分成可以存放在内存中进行处理的数据块，以节省 访问外存的i o 开销。 数据集划分算法的候选项目集的数量一般比a 岬o r i 算法的候选项目集的 数量大，增加各数据块的数据扭曲性可以减少候选项目集数量。数据集划分 算法是各种并行关联规则挖掘算法和分布式关联规则挖掘算法的基础。 4 抽样算法：抽样算法通过对数据集d 抽样产生抽样数据集d ，找出抽 样数据集d ，中的频繁项目集作为候选项目集，然后扫描数据集d 确定其中的 频繁项目集。 如何计算负边界以找回部分遗漏的频繁项目集是抽样算法的关键。抽样 算法适合于要求挖掘效率较高，而挖掘准确性不大高的环境下的关联规则挖 据。 3 3 a p r i 鲥算法 关于关联规则发现的算法相当多， 和改进。a p r i o r i 是一种宽度优先算法， 但绝大部分是经典算法a p f i o f i 的演绎 算法高效的关键在于生成较小的候选 项目集，也就是尽可能不生成和计算那些不可能成为频繁项目集的候选项目 集。它利用了这样一个基本性质：即一个频繁项目集的任一子集必定也是频 繁项目集。这个性质被目前的绝大部分关联规则算法所继承。 3 3 1a p r i o r i 算法的思想 a g r a w a l 等于1 9 9 4 年提出了一个挖掘顾客交易数据库中项集间关联规则 的算法一a p r i o r i 2 3 6 】，该关联规则在分类上属于单维、单层、布尔型关联 规则。时至今日，a 耐谢算法仍然是挖掘布尔型关联规则频繁项集最有影响 的方法，这里所有支持度大于最小支持度的项集被称为频繁项集。 a p r i 嘶算法核心是基于两阶段频繁项集的递推思想，使用一种称作逐层 搜索的迭代方法，k 项集用于探索( k + 1 ) 项集。首先，找出频繁1 项集的集合。 该集合记作l l 。l l 用于找频繁2 项集的集合l 2 ，而l 2 用于找l 3 ，如此下去，直 到不能找到频繁k 项集。找每个l k 需要一次数据库扫描。 6 哈尔滨丁程大学硕十学何论文 为了提高算法的效率，m a n n i t a 等弓i 入了修剪技术来减小候选集c k 的大小 【2 ，压缩搜索空间。算法中引入的修剪策略基于这样一个性质：频繁项集的 所有非空子集都必须也是频繁的。根据定义，如果项集i 不满足最小支持度闽 值r a i ns u p ，则i 不是频繁的，l i p p ( i ) m i n _ _ s u p 。如果项a 添加到