（计算机应用技术专业论文）基于corba的分布式关联规则挖掘系统的研究和实现.pdf

山东科技大学硕士学位论文 摘要 摘要 数据挖掘是指从大型数据库或数据仓库中提取隐含的、先前未知的、对决策有潜在 价值的知识和规则。它是人工智能和数据库发展相结合的产物，是目前国际上数据库和 信息决策系统最前沿的研究方向之一。 其中，关联规则挖掘是近几年研究较多的数据挖掘方法，应用也最为广泛。文中详 细介绍了关联规则的基本概念、性质及其经典算法。现有的关联规则挖掘算法和模型主 要是基于数据库或数据仓库的，采用集中式处理。随着分布式数据库和网络技术的发展， 它们不能满足分布式数据挖掘的需要。分布式关联规则的挖掘就是在这样的背景下提出 的。 本文详细介绍和分析了分布式关联规则挖掘f d m 算法。在分布式数据环境下，频 繁集计算和网络间的通讯代价是挖掘算法的瓶颈所在。从这个角度出发，文中给出了解 决方案。通过事务剪枝、采用数组链表相结合的数据结构存储候选数据集来改进频繁集 支持数的计算；增加挖掘服务器站点来完成各站点间的结果收集、计算和广播，候选集 的上界剪枝等任务，并控制整个挖掘过程中的同步运算，减少了网络间的信息传输量。 在改进f d m 算法的基础上，本文引入分布式对象技术，提出开发基于c o r b a 规范的 分布式关联规则挖掘系统。给出了系统总体设计框架，讨论了系统实现所涉及到的关键 技术。 关键词：数据挖掘、分布式数据库、关联规则、f d m 算法、c o r b a 规范 些查型苎查堂要主兰堡篓兰 塑墨 a b s t r a c t d a t am i n i n ga c q u i r e sk n o w l e d g ea n dr u l e st h a ti sc o n n o t a t i v e ，u n k n o w na n d h a v i n gp o t e n t i a lv a l u ef o rd e c i s i o n m a k i n gf r o ml a r g ed a t a b a s e so rd a t a w a r e h o u s e s i ti st h er e s u l tt h a tc o m b i n e sa r t i f i c i a li n t e l l i g e n c ea n dd a t a b a s e a tp r e s e n t ，d a t am i n i n gi so n eo ft h em o s ta d v a n c e dr e s e a r c hd i r e c t i o ni nt h e f i e l do fd a t a b a s ea n di n f o r m a t i o nd e c i s i o n a s s o c i a t i o nr u l em i n i n gi sa na c t i v ed a t am i n i n gr e s e a r c ha r e aa n da p p l y s m o r ew i d e l yt h a no t h e rm e t h o d s i nt h ed i s s e r t a t i o n ，i ti n t r o d u c e st h eb a s i c c o n c e p t s ，c h a r a c t e r sa n df a m o u sa l g o r i t h m so fa s s o c i a t i o nr u l em i n i n gi nd e t a i l e x i s t i n ga r ma l g o r i t h m sa n dm o d u l e sc a t e rt oac e n t r a l i z e de n v i r o n m e n t ，s u c ha s d a t a b a s eo rd a t aw a r e h o u s e w i t ht h ed e v e l o p m e n to fd i s t r i b u t e dd a t a b a s ea n d n e t w o r kt e c h n o l o g y ，t h e yd o n tm e e tt h en e e d so fm i n i n gr u l e sf r o md i s t r i b u t e d d a t as e t s t h ei n t e r e s ti nd i s t r i b u t e da s s o c i a t i o nr u l em i n i n ga r i s e sf r o mt h i s s i t u a t i o n t h ed i s s e r t a t i o ni n t r o d u c e sa n da n a l y s e st h ea l g o r i t h m so fd i s t r i b u t e d a s s o c i a t i o nr u l em i n i n g ，e s p e c i a l l yf d m ( f a s td i s t r i b u t e dm i n i n go fa s s o c i a t i o n r u l e ) a l g o r i t h m i nd i s t r i b u t e dd a t ae n v i r o n m e n t ，f r e q u e n ti t e m s e t sc o m p u t i n g a n dt h ec o s t so fc o m m u n i c a t i o na r et h eb o t t l e n e c k so fa l g o r i t h m s f r o mt h ep o i n t o fv i e w ，t h ed i s s e r t a t i o np r o p o s e sp r a c t i c a ls o l u t i o n st ot h e s ep r o b l e m s t h e a p p li c a t i o n so ft r a n s a c t i o n sp r u n i n ga n dan e wd a t as t r u c t u r ef o rs t o r a g eo ft h e c a n d i d a t es e t sh e l pt oc o m p u t et h es u p p o r tc o u n t so fc a n d i d a t es e t sf a s ta n d r e d u c et h ec o s to fs c a n n i n g d a t a b a s e a d d i n gas i t ea sd a t am i n i n gs e r v e ri s p r o p o s e dt og a t h e r ，c o m p u t ea n db r o a d c a s tt h er e s u l to fe a c hs i t e s ，t h ec a n d i d a t e s e t sp r u n i n g ，c o n t r o ls y n c h r o n i z a t i o no ft h ew h o l em i n i n gp r o c e s sa n ds oo n i t r e d u c e st h ec o s to fc o m m u n i c a t i o ni nn e t w o r k w i t ht h ei m p r o v e m e n to ff d m a l g o r i t h m ，t h et e c h n o l o g yo fd i s t r i b u t e do b j e c ti si n t r o d u c e d an e wa r c h i t e c t u r e f o rd i s t r i b u t e da s s o c i a t i o nr u l em i n i n gb a s e do nt h ec r i t e r i o no fc o r b ai s p r o p o s e d t h eo v e r a l ld e s i g no ft h es y s t e mi sg i v e na n dt h ep i v o t a lt e c h n i q u e s 山东科技大学硕士学位论文 i n v o l v e di ni m p l e m e n t a t i o na r ed i s c u s s e di nt h ed i s s e r t a t i o na tl a s t k e y w o r d s ：d a t am i n i n g ，d i s t r i b u t e dd a t a b a s e ，a s s o c i a t i o nr u l e s ，f d m a l g o r i t h m ，t h ec r i t e r i o no fc o r b a 声明 本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所 公知的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交 于其它任何学术机关作鉴定。 硕士生签名：寅1 ) 群 日期：卯r 岁、上 a f f i 砌舱t 1 0 n id e c l a r et h a t t h i sd i s s e r t a t i o n s u b m i t t e di nf u l f i l l m e n to ft h e r e q u i r e m e n t s f o r t h ea w a r do f m a s t e r o fp h il o s o p h yi ns h a n d o n g u n i v e r s i t yo fs c i e n c ea n dt e c h n o l o g y ，i sw h o l l ym yo w nw o r ku n l e s s r e f e r e n c e do fa c k n o w l e d g e t h ed o c u m e n th a sn o tb e e ns u b m i t t e df o r q u a l i f i c a t i o na ta n yo t h e ra c a d e m i ci n s t i t u t e s i g n a t u r 。：么钇胁 d a t e ： 劲匹、s 、2 6 山东科技大学硕士学位论文 1 绪论 1 1 数据挖掘技术 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据急剧 增加。在海量数据的背后隐藏着许多具有决策意义的信息，我们希望能够对其进行更高 层次的数据分析，从中发现有价值的信息或知识。目前的数据库系统作为强有力的事务 处理工具，所能做到的只是对数据进行存取和简单的操作，还无法发现数据中存在的关 系和规则，亦无法根据已有数据预测其发展趋势。这使得人们无法从“数据矿山”中找 到蕴藏的“知识金块”，因而导致了“数据爆炸但知识贫乏”的现象。 数据挖掘一从大量数据中用非平凡的方法发现有用的知识一就是为了解决这种矛盾 而迅速发展起来的，它是信息技术自然演化的结果。数据挖掘是指从大型数据库或数据 仓库中提取隐含的、先前未知的、对决策有潜在价值的知识和规则【l l 。作为一个多学科 交叉领域，它涉及到数据库技术、人工智能、机器学习、神经网络、统计学、模式识别、 知识获取、高性能计算和数据可视化等多个方面。它是人工智能和数据库发展相结合的 产物，是目前国际上数据库和信息决策系统最前沿的研究方向之一。 数据挖掘是一个完整的过程，利用各种分析工具从大型数据库中挖掘出先前未知的、 有效实用的知识，并以客户易于理解的形式呈现出来用以理解数据、辅助决策。其执行 过程示意图如下： 图1 1数据挖掘过程示意图 f i g 1 1 t h es k e t c h m a p o f d a t a m i n i n g p r o c e s s 数据挖掘功能用于发现指定挖掘任务中要找的模式类型。模式是表达式，它能简要 描述数据集中的某个子集特性。其按功能可分为两大类：预测型模式和描述型模式。描 述型模式以简洁概要的方式刻画数据的一般特性，并提供数据的有趣的一般的性质；而 预测型模式则是在当前数据上进行推断，建立一个或一组模型以预测数据未来发展趋势。 数据挖掘功能以及它们可以发现的模式类型介绍如下。 坐查型垫盔堂堡主堂垡堡苎 堕堡 1 概念类描述：特征化和区分 数据可以与类或概念相关联。概念描述产生数据的特征化和比较描述，当被描述的 概念涉及对象类时也称为类描述。 特征化提供给定数据汇集的一般特征或特性的简洁汇总。例如，某超市获取在一年 之内花费在1 0 0 0 元以上的顾客特征汇总的描述，得到的可能是顾客的一般轮廓，如年龄 在4 0 5 0 之间、有工作、有良好的信用等级等。概念( 或类) 的区分将目标类对象的一 般特性与一个或多个对比类的一般特性进行比较，提供两个或多个数据汇集的比较描述。 如你可能希望将长期顾客和偶尔购买某种商品的顾客进行比较，从而得到诸如年龄、地 域、职业等特性之间的区别。 2 关联分析 关联分析是发现交易数据库中不同商品( 项) 之间的联系，所发现的关联规则由频 繁出现的数据组成。此技术广泛应用在购物篮或事务数据分析中。关联规则形式举例说 明如下：“a g e ( x , “2 0 2 9 ”) a i n c o m e o ( ，“2 0 0 0 3 0 0 0 ”) j b u y s ( x ，“c d - p l a y e r ) ”， s u p p o r t = 2 ，c o n f i d e n c e = 6 0 。 3 聚类分析 聚类用于从数据集中找出相似的数据并组成不同的组，使得组之间的差别尽可能大 且组内的差别尽可能小。与预测模型不同。聚类中没有明显的目标变量作为数据的属性 存在。因此，在聚类之前并不知道将要划分成几个组和什么样的组，也不知道根据哪几 个数据项来定义。聚类分析可以在超市的顾客数据集上进行，以便识别顾客的同类购物 目标群。 4 孤立点分析 孤立点是指与数据的一般行为或模型不一致的数据对象。用距离的观点来看，它就 是那些距离密度较高的大部分较远的点。大部分数据挖掘方法将孤立点视为噪声或异常 而丢弃。然而，在一些实际应用中( 如信用卡欺骗检测，网络入侵检测等) ，这些数据 会变得更加有趣。它可以通过预先假定数据分布模型或考察对象主要特征上的差别来识 别孤立点。 5 演变分析 数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模，包括时间序 列模式、周期模式匹配和基于类似性的数据分析。它考虑了数据行为的时间因素，利用 2 生至型垫查兰堡圭兰垒兰茎 笪笙 现有数据随时间变化的一系列值才能更好地预测将来的发展趋势。例如超市会考虑节假 日、促销活动等可能会对购物造成的影响。 在实施数据挖掘解决实际问题时，经常要同时使用多种技术发现不同类型的模式。 而在其中，关联规则挖掘是近几年研究较多的数据挖掘方法，应用也最为广泛。因此， 本文将要讨论的问题主要集中在数据挖掘中的关联规则发现上。 1 2 分布式数据库及其特点 分布式数据库是一组数据集，逻辑上它们属于同一系统，而物理上它们分散在用计 算机网络连接的多个场地上，并统一由一个分布式数据库管理系统来管理。它按照逻辑 片段( 子关系) 分配在各个节点上，是计算机网络环境中各场地或节点上数据库物理片 段的逻辑集合【2 】。 从全局应用的角度和数据存放的实际情况出发，将数据库自下而上构成分布式数据 库系统，实现全局数据的完整性和一致性。在分布式数据库系统中，将关系分片，以有 利于用户需求为原则来组织数据的分布。目前数据分布的方式有水平划分、垂直划分、 混合划分和诱导分片。在实际环境中，人们多采用水平分片，例如在银行的总行分行之 间，大型超市各销售点及企业子公司之间的数据存储大多采用此方案。本文对分布式关 联规则挖掘的研究工作也主要集中在水平划分的分布式数据库上。 分布式数据库系统的特点主要是 2 】： 1 共享性与自治性 多个场地的局部数据在逻辑上是一个整体，并为分布式数据库系统的所有用户使用， 这种应用称为分布式数据库的全局应用；同时，它还允许局部用户只能使用本地的局部 数据库，这种局部独立于全局用户的特性即是局部数据库的自治性。 2 事务管理的分布性 由于数据的分布使得事务也具有了分布性，即一个事务( 全局事务) 的执行将划分 成在许多场地上执行的子事务( 局部事务) ，子事务的执行结果合并而成全局事务的结 果。这即为事务管理的分布性。 3 存取效率 在分布式数据库系统中，全局查询被分解成等效的子查询。它是根据系统的全局优 化策略产生的，而子查询计划又是在各场地上分布执行的。 化策略产生的，而子查询计划又是在各场地上分布执行的。 3 些查翌垫奎堂翌主鲎堡堡苎 堑笙 4 数据模型 在分布式数据库系统中，d d b ( d i s t r i b u t e dd a t a b a s e ) 是由一个逻辑的、虚拟的数 据库( 全局数据库g d b ) 和实际分布在各场地的局部数据库( 物理的、实际存储的数据 库l d b ) 两级数据库组成。全局数据模式描述了全局数据库；而局部数据模式描述的是 各场地的局部数据库，而这些是实际存储的。 5 数据独立性 数据独立性是建立数据库的目标，实现了系统的透明性。它的基本含意是应用程序 与实际的数据组织相分离。全局用户所看到的是全局数据模型的描述，对各场地的局部 数据模型描述并不关心或了解。对于数据的管理则是由各场地的数据自治性来保证的。 1 3 课题的提出 随着分布式数据库的发展，原有的集中式数据挖掘系统不能满足分布式数据挖掘的 需要，因而分布式数据挖掘系统的研究成为数据挖掘领域新的研究热点。数据挖掘技术 与分布式对象技术、w e b 技术相融合是数据挖掘软件未来发展的方向【4 】。本论文的选题 即在此基础上确定。 现有的数据挖掘算法和模型主要是基于数据库或数据仓库的，采用集中式处理。即 使在数据分布存储的情况下，也要求预先把这些分散数据收集到一个集中的地方( 如数 据仓库等) 。这就要求通过网络传输大量数据，导致算法响应的时间变长，数据的私有性 及安全性被破坏。而且由于网络的传输速度根本无法赶上数据的增长速度，这会导致欲 通过有限的网络带宽来移动大容量的数据。因而如何在基于w e b 的分布式数据环境下进 行安全有效的数据挖掘活动是值得注意和研究的。在数据挖掘的各种方法中，关联规则 挖掘旨在寻找给定数据集中项之间的有趣联系，它是近几年研究较多的数据挖掘方法， 应用也最为广泛。所以，分布式关联规则挖掘是非常值得研究的一个方向。 目前大部分数据挖掘工具不支持w e b 的挖掘事务，不能对分布式异构环境下的数据 库进行操作。随着i n t e r n e t 的迅速普及，计算模式己逐渐由传统的c s 、b s 结构向分布 式多层次的方向发展，客观上要求数据挖掘系统也应如此。分布式对象技术主要是在分 布式异构环境下建立应用系统框架和对象构件，在应用系统框架的支撑下，开发者可以 将软件功能包装为更易管理和使用的对象，这些对象可以跨越不同的软硬件平台进行互 操作。c o r b a 是由对象管理组织( o b j e c tm a n a g e m e n tg r o u p ，o m g ) 提出的应用软件 4 山东科技大学硕士学位论文绪论 体系结构和对象技术规范，其核心是一套标准的语言、接口和协议，以支持异构分布应 用程序间的互操作性及独立于平台和编程语言的对象重用。它基于软构件( s o f t w a r e c o m p o n e n t ) 技术，支持即插即用的嵌入式应用。软构件之间通过一定的接口进行通信， 可以组合对象形成一个灵活而有效的分布式计算环境。 基于以上分析，本文拟定在研究和改进分布式关联规则挖掘算法的基础上，提出基 于c o r b a 计算模型的关联规则分布式挖掘系统的体系结构，实现用户界面和挖掘事务 处理核心的分离，从而支持基于网络的挖掘事务应用，且具有良好的平台适应能力和可 扩展性。 1 4 课题的研究现状及意义 分布式数据挖掘( d i s t r i b u t e dd a t am i n i n g ，d d m ) 就是使用分布式计算，从分布式 数据库中发现知识的过程。虽然它是近几年提出来的新的研究领域，但由于其诱人的应 用前景，目前已有相当数量的研究人员投入到对该领域的研究当中，并且取得了一定的 成果。早期对分布式数据挖掘的研究工作主要集中在水平划分的分布式数据库，其中最 为突出的发展是多代理技术。 关联规则挖掘在数据挖掘的各种方法中应用最为广泛。在数据库或数据仓库中可能 存储相当大量的数据，在这样的数据环境下进行关联规则的挖掘可能需要充足的处理器 资源，而分布式系统是一个可能的解决方案1 3 】。同时许多大型数据库本来就是异地存储 的，例如连锁超市数以万计的交易数据都是存储在不同的站点。随着i n t e m e t i n t r a n e t 的 迅速普及和发展，基于w e b 的分布式数据库应用也越来越广泛。这种事实使得研究在数 据库中挖掘关联规则的高效分布式算法显得非常重要。它在挖掘过程中只传输中间结果， 不需移动大量数据从而减少了网络传输量，有效地保证了数据的私有性和安全性。在设 计分布式关联规则挖掘系统时采用c o r b a 计算模型，把数据挖掘算法封装成灵活的组 件，实现用户界面和挖掘事务处理核心的分离，且具有良好的平台适应能力和可扩展性。 由此延伸开来，把成熟的组件和分布式对象技术应用到数据挖掘领域中，把多种数据挖 掘算法封装成灵活的组件并集成系统，从而可以加快数据挖掘算法的开发、重组和工程 化。这是今后开发数据挖掘系统软件的一个解决方案。 本文内容的总体安排如下：第二章介绍关联规则有关概念和算法，分析分布式关联 规则经典的算法，回顾领域内的相关工作。第三章改进f d m 算法，给出了详细算法设 s 山东科技大学硕士学位论文 绪论 计，并举例说明算法执行过程。在改进算法的基础上，第四章提出了基于c o r b a 的分 布式关联规则挖掘系统的系统框架，并详细介绍其实现过程中涉及到的关键技术。最后， 总结本文工作，介绍今后课题的发展方向。 6 山东科技大学硕士学位论文 分布式关联规则挖掘的基本原理和相关工作 2 分布式关联规则挖掘的基本原理和相关工作 2 1 1 基本问题描述 2 1 关联规则的问题描述和相关概念 关联规则挖掘发现大量数据中项集之间有趣的联系。更确切地说，关联规则通过量 化的数字描述物品甲的出现对物品乙的出现有多大影响【3 】。它的一个经典应用就是购物 篮分析。该过程通过发现顾客放入其购物篮中不同商品之间的联系，分析顾客购买习惯。 例如，在同一次购物事件中，如果购买牛奶则会继续买面包的可能性有多大? 通过了解 哪些商品频繁地被顾客同时购买，可以帮助零售商制定营销策略，更好地引导销售。 随着大量数据的收集和存储，为实旌关联规则挖掘提供了必要的数据环境。有些数 据可能不像销售数据那样很容易就能看出一个事务是许多物品的集合，但稍微转换一下 思考角度，仍然可以像销售数据一样处理。通过从大量商务事务记录中发现有趣的相关 规则，有助于商务决策的制定，如分类设计、交叉购物、货架设计等。目前，关联规则 挖掘已经应用到企业的经营决策、市场分析、税务决策、金融欺诈的检测等多个领域。 随着对关联规则挖掘研究及其应用推广的深入，其重要性和实用性更加显现出来。 2 1 2 关联规则的形式及基本概念 设i - i l ，i 2 ，i m ) 是项的集合，其中的元素称为项( i t e m ) 。记d 为交易t 的集 合，这里交易t 是项的集合，并且t c _ i 。对应每一个交易有唯一的标识，如交易号( t i d ) 。 设x 是i 中项的一个集合，如果x t ，那么称交易t 包含x 。为方便计，假定事务或 项集中的项均按字典次序排列。 一个关联规则是形如x j y 的蕴涵式，这里x c _ i ，y c i ，并且x n y = o 。规则x j y 在事务数据库d 中的支持度( s u p p o r t ) 是事务集中包含x 和y 的事务数与所有事务数 之比，记为s u p p o r t ( x j y ) ，即 s u p p o r t ( x j y ) = | t ：x u y _ t ，t e d i d i ( 1 1 ) 7 当蔓型垫查堂堡主兰些堡壅 坌塑苎茎壁塑型丝塑些董查璺墨翌塑茎王堡 规则x 等y 在事务集中的置信度( c o n f i d e n c e ) 是指包含x 和y 的事务数与包含x 的事务数之比，记为c o n f i d e n c e ( x ；y ) ，即 c o n f i d e n c e ( x j y ) = i t ：x u y 三t ，t d i l l t , x c t ，t e d ) i( 1 2 ) 支持度和置信度是衡量关联规则的兴趣度的两个度量，它们分别反映了规则的重要 性和准确性。事实上，人们一般只对满足一定支持度和置信度的关联规则( 即强规则) 感兴趣。关联规则挖掘的任务就是要挖掘出d 中所有可能的强规则。因此为了发现有意 义的规则，需要设定两个阈值：最小支持度( m i n _ s u p ) 和晟小置信度( m i n _ c o n f ) 。前者表 示了一组物品集在统计意义上需满足的最低概率；后者反映了关联规则的最低准确度。 通常，这些阈值是由用户或领域专家来设定的。 2 2 关联规则挖掘算法 由于分布式关联规则挖掘算法是在集中式挖掘算法的基础上发展起来的，所以在此 首先简要介绍一下集中式关联规则的相关概念及挖掘方法，特别是其经典算法a p r i o r i 的基本原理和实现方法。大多数分布式或并行关联规则挖掘算法也都是基于此算法的。 2 2 1 经典频繁集算法 给定一个事务交易集d ，挖掘关联规则问题就是找出支持度和置信度分别大于用户 设定的最小支持度( m i n _ s u p ) 并d 最小置信度( i n i n _ c o n 0 的关联规则。a g r a w a l 等人在文献【7 】 中设计了一个基本算法基于两阶段频繁集思想的方法，其核心方法是基于频繁集理论 的递推方法。它将关联规则挖掘算法的设计划分为两个子问题： ( 1 ) 、找出存在于事务数据库中的所有支持度大于最小支持度的项集，这些项集称为 频繁集。此步是算法的核心。 ( 2 ) 、利用第1 步找到的频繁集产生关联规则。对于每个大项集a ，若bc a ，b m ， 且c o n f i d e n c e ( b j ( a - b ) ) m i n 第二个子问题比较容易。如给定一个频繁集y = 1 1 1 2 i k , k 2 ，i i e i ，产生只包含集合 ( i l ，1 2 ，i k ) 中的项的所有规则，其中每一条规则的右部只有一项，形如 y - i i j i i , 1 i k 。这里采用的是参考文献 8 中的规则定义。一旦这些规则被生成，那么只有那些大 于用户给定的最小置信度的规则才能作为有趣规则而保留下来。 实际上，挖掘关联规则算法的总体性能由第一步决定。因此目前大多数研究集中在 r 生至型垫查竺堡主兰竺丝壅 坌塑茎鲞壁塑墨! ! 竺塑塑兰查墨堡塑塑茎三堡 第一个子问题上。a p f i o f i 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。为 了生成所有频繁项集，a p f i o r i 使用递推的方法，其核心步骤描述见算法2 1 1 ”。 算法2 1 给出a p f i o f i 算法的具体实现过程如下： 算法：a p f i o f i 使用根据候选生成的逐层迭代找出频繁集。 输入：事务数据库d ；最小支持度阈值m i n _ s u p 。 输出：d 中的频繁项集l 。 ( 1 ) l l = l a r g e1 - i t e m s e t s ； ( 2 ) f o r ( k = 2 ；l k 1 中；i 卅) ( 3 )c k = a p r i o r i _ g e n ( l k 1 ) ；生成新的候选集 ( 4 ) f o re a c ht r a n s a c t i o nt d ，扫描数据库d 计算支持数 ( 5 )c t = s u b s e t ( c k ，t ) ；事务t 中包含的候选集，使用h a s h _ 仃e e 存储结构 ( 6 ) f o re a c hc a n d i d a t ec c t ( 7 ) c c o u n t 抖； ( 8 ) ( 9 ) l k = cc kc c o u n t i m i n _ s u p ) k 次迭代结束，得到k 项频繁集 ( 1 0 ) ) ( 1 1 ) r e t u r nl = u l ； a p f i o f i 算法候选产生函数a p r i o r i _ g e n 的参数为l k 1 ，即所有 - 1 ) 一项频繁集的集合，返 回所有频繁k 项集集合的一个超集( s u p e r s e t ) 。该函数分连接和剪枝两步实现，详见算法 2 2 。为方便计，假定事务或项集中的项目均按字典次序排列。 算法2 2 给出了a p f i o r i _ g e n 函数的具体实现过程如下： 函数：a p r i o r i _ g e n 生成新的候选集。 输入：( k - 1 ) - 项频繁集l k i 。 输出：k 项候选集c k 。 ( 1 ) i n s e r ti n t oc kl k 1o 。l k 1 联合运算 ( 2 ) s e l e c t “1 】，p 【2 】，p k - 1 ，q k 一1 】 ( 3 ) f r o m l k 1a s p ，l k 1a sq ( 4 ) w h e r ep 【1 = q 1 】a n dp 【2 】= q 2 】a n d a n dp k - 2 2 q k _ 2 】a n d p k - 1 】 2 ) 次遍历中包括两个阶段。 首先，使用在第( k 1 ) 次遍历中找到的频繁集l k 1 和a p r i o r i _ g e n 函数产生候选项集c k ( 包括对其进行剪枝的操作) 。接着扫描数据库，计算c k 中各候选集的支持度来决定是 否把其并入l k 。之后进入下次循环过程，直到l k 1 为空时，迭代结束。这里的验证过程 是算法性能的一个瓶颈。它要求多次扫描原始事务数据库以对候选项集的支持度进行计 数，这需要很大的i o 负载。 c k 是l k 的超集：即它的成员可能是也可能不是频繁的，但所有的频繁k 一项集都必 包含在c k 中。在文献 8 】中，a g r a w a l 等引入了剪技技术( p r u n i n g ) ：来修剪候选集c k 的大小。 这一技术缩小了待考察候选集的势，显著地改进生成所有频繁集算法的性能。它基于性 质：一个项集是频繁的当且仅当它的所有子集都是频繁的。因此，如果一个候选k 项集 存在某一( k - 1 ) 项子集不在l k 1 中，则该候选项集也不可能是频繁的。 这里特别值得注意的是，为了能够快速计算候选集支持数而引入哈希树( h a s ht r e e ) 技术。候选项目集c k 存储在一颗h a s h 树中。h a s h 树是一个多叉的无序树，它对候选集 进行了有效的划分，并把项目集都存储在叶子节点中。候选项集计数过程就是从树根到 树叶递归地搜索整个哈希树的过程，根据h a s h 函数进行路径选择，到达树叶结点时检 查其候选项目集是否在此事务t 中并更新相应的计数。我们将在后面的分布式关联规则 算法分析部分详细讨论h a s ht r e e 这一数据组织结构及其对算法的影响。 2 2 2 其他挖掘算法及改进 自从a g r a 、a l 等人于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规则问 题之后，大量人员投入到对关联规则挖掘问题的研究中。虽然a p r i o r i 算法自身已经进行 了一定的优化，但在实际应用中仍存在许多不令人满意的地方。基于a p r i o r i 算法，人们 相继提出了一些优化的方法，包括基于划分的方法、基于散列的d h p 算法、基于采样的 1 0 生查型垫查兰堡圭竺垡丝苎 坌查墨茎壁塑! ! 丝塑塑薹查璺里翌塑茎三堡 方法等。邵使进行优化之后，还是会存在a p f i o f i 算法本身无法解决的问题，如要求多次 扫描数据库( 特别是挖掘长模式时) 、每次迭代过程中可能会产生大量的候选集( 尤其是 2 项候选集c 2 的项目数) 等。 针对此问题，j i a n w e ih a r t 等人提出了一种新颖的数据结构f p - 仃e e 及基于此上的频 繁模式增长算法( 简称f p 增长) 【9 】。f p - t r e e 是一个压缩的数据结构，用较少的空间存 储了后继频繁集挖掘所需耍的全部信息，采用分而治之的策略挖掘全部频繁项集而不产 生候选。实验表明，f p g r o w t h 对不同长度的规则都有很好的适应性，同时在效率上较之 a d r i 耐算法有了很大的提高。更多关于关联规则的挖掘算法可以在其他文献【l o 】【1 l 】【1 2 】等中 找到。 2 2 3 分布式挖掘算法的发展 绝大多数分布式挖掘算法( 包括并行挖掘算法) 都是从相应的集中式算法中发展起 来的。集中式关联规则挖掘算法的代表主要有a p n o f i 算法、f p g r o w t h 算法等。 在分布式数据挖掘中，一般有两种解决方案。一种是从数据到规则，另一种就是从 规则到规则。对于从数据到规则，也即在挖掘过程中各站点必须在每次迭代过程中首先 进行本地并行挖掘计算各候选集的支持数，然后同步合计支持数计算出全局大项集并进 入下次循环。这种方法可以求出每个大项集的准确的支持数，并进而得出正确的规则。 显然这种方法要求在挖掘过程的每次循环中都要求各站点进行通讯并同步一次，从而在 一定程度上降低了其执行效率。对于从规则到规则来说，也即在挖掘过程中要求各站点 首先进行本地数据挖掘产生部分数据模式，然后各站点间进行通讯综合来自不同地方的 部分数据模式从而产生全局模式。这种方法的优点就在于整个挖掘过程中不需要各站点 进行同步，只在所有站点完成本地挖掘之后互相交换数据模式，减少了网络间的通讯量。 但对于某些候选集，它可能在一些站点上是非频繁的，所以在这些站点上会把其从大项 集中删除而没有统计出其的支持数。因此在综合数据模式的时候并不能得出准确的规则 形式及其支持度、置信度等衡量用户兴趣的指标。因此，在权衡之下，很多算法( 如c d 算法、d d 算法、f d m 算法、p e a r 算法等) 都是采用第一种思路来设计的。 由前面可知，为了生成关联规则涉及到的所有频繁项集，a p f i o f i 使用了递推的方法。 这种基于两阶段频繁集思想的算法稍加改进就比较适合应用在分布式数据挖掘过程中。 每次循环开始时各站点首先进行本地候选集支持数计算以得出局部候选集，这之后各站 生查型垫查堂堡圭堂垡丝苎 坌变茎鲞壁塑型丝塑塑量奎墨里塑塑茎三堡 点进行同步操作互交换支持数以算出各候选集的全局支持数，进而计算出全局大项集并 进入下一个迭代过程中。为了提高其执行效率，就要改进算法减少候选集的数目以减少 网络间的通讯量，并提高本地算法的性能。这将在本文后面相关地方进行介绍。 如前所示，虽然f p g r o w t h 算法在性能上要优于a p r i o r i ，但其基本思想并不适合于 应用在分布式的数据存储环境下。因为它在第一次扫描数据库时，就将提供频繁项集的数 据库压缩到一颗频繁模式树中，但仍保留项集关联关系：然后将这种压缩后的数据库分 成一组条件数据库( 一种特殊类型的投影数据库) ，每个关联一个频繁项，并分别挖掘每 个数据库。所以，在挖掘的过程中各站点不易进行同步计算。如果基于此算法设计分布 式关联规则挖掘算法，只能是在挖掘完本地局部模式之后才能进行各站点间的交换以得 出最终的不准确结果。因此，目前大多数分布式或并行关联规则挖掘算法都是在n p r i o r i 算法基础上发展起来的。 2 3 分布式关联规则挖掘算法 随着数据维、数据库大小的快速增长，在如此海量数据环境下进行挖掘需要充足的 处理器资源，集中式挖掘算法并不具有良好的可扩展性，而分布式系统是一个可能的解 决方案。同时许多大型数据库本来就是分布式的，例如，超市百货公司数以万计的交易 数据就很可能存储在不同的站点，这种事实使得研究在挖掘关联规则的高效分布式算法 显得非常必要，并同时带动并行算法的研究。因为分布式算法具有高度的适应性、可扩 展性、低性能损耗等特性，它可以作为挖掘关联规则的理想平台【”。分布式关联规则的 挖掘就是在这样的背景下提出的。 分布式数据库关联规则挖掘分为3 步：局部数据库频繁集挖掘：全局频繁集的 生成；由全局频繁集产生关联规则。 2 3 1 几种典型的算法介绍 a g r a w a l 等提出了基于a p r i o r i 的并行关联规则挖掘算法，比较流行的诸如数据分布 算法( d a t ad i s t r i b u t i o n ，d d 算法) 、记数分布算法( c o u n td i s t r i b u t i o n ，c d 算法) 等。 它们也能应用于分布式数据挖掘的过程中。快速分布式关联规则挖掘算法( f a s t d i s t r i b u t e d m i n i n g o f a s s o c i a t i o nr u l e s ，f d m 算法) 是由d w c h e u n g 等在1 9 9 6 年提出的 对c d 算法的一个改进算法。下面就对其进行简要介绍和分析1 。 1 2 当鲞兰! 垫查兰堡= 兰堂些堡苎 坌查兰叁壁塑型丝塑塑量查垦矍翌塑茎三堡 d d 算法用一种循环的方式将候选集划分到每个处理器中，然后由每个处理器负责 计算本地存储的候选子项集的支持计数。这个过程需要每个处理器既要扫描分配给该处 理器的数据库，还要扫描其他处理器上的数据库，从而导致了很高的通信负载。在算法 执行过程中，为了获得候选集的全局支持数要求每个处理器都必须扫描整个数据库，这 严重降低了算法的性能。因此，该算法不能直接应用在分布式数据环境而只限于并行环 境下。 c d 算法直接把a p r i o d 算法应用在并行环境中，并假设数据是水平分布在各站点上 的。它将生产候选集的的过程复制到所有处理器上。每个处理器生成一个完整的候选杂 凑树，根据本地数据库分块独立地计算出候选项的局部支持计数，然后通过在所有处理 器之间交换局部支持计数得到全局支持计数。因此，在处理器之间只需交换支持数，具 有较小的通信负载。事实上，c d 算法利用了一个简单的方法，即允许在各处理器上进 行冗余计算和冗余存储来尽量减少传输大量消息。但是此算法没有实现杂凑树生成过程 的并行化，随着处理器数量增加的情况下，这将成为算法执行的瓶颈。另外，在进行支 持数交换时要求每个站点都要向其他站点进行通信，在每次扫描结束后的通信量复杂性 为o ( n 2 ) 。因此，这使得c d 算法不能作为一种扩展性好的分布式算法。 f d m 算法是d w c h e u n g 于1 9 9 6 年在文献【1 3 】中提出的一个对c d 算法的改进算法。 它揭示了分散数据集与集中数据集之间的一些有趣关系，通过生成较少数量的候选数据 集，大大减少了在挖掘关联规则时需要处理的数据量。本文将详细介绍和分析f d m 算 法，并在此基础上对其进行改进。 2 3 2 基本概念和性质 设有一个分布式数据库系统s ，由n 个站点s i0 = 1 ，n ) 组成。d b = d b iu d b 2 u u d b 。，则d b 称为全局数据库，d b i 称为局部数据库。此时，数据库采用水平分片的方 式存储和管理数据。 定义2 1 设x s u p 和x s u p i 分别表示x 在d b 和d b i 上的支持数。如果x s u p i t r a i n _ s u p + i d o l ，则称x 为站点s i 上的局部频繁项目集；如果x s u p 一r a i n _ s u p + i d ，则x 为全局频繁项目集。 定义2 2 若x 既是站点s i 的局部频繁项目集，又是全局频繁项目集，则x 在站点 s 。上是全局大的。显然站点s i 的所有全局大的数据集将作为该站点生成下一轮候选数据 1 3 山东科技大学硕士学位论文 分布式关联规则挖掘的基本原理和相关工作 集的数据源。 引理2 1 如果一个数据集x 是全局大的，那么存在一个站点s i ( 1 i n ) ，x 以及 它的所有子集在站点s i 是全局大的。 证明：如果x 在任何站点都不是局部大的，即x s u p i m i n _ s u p + i d i l ，于是 x s u p l ， 所有全局大的k - 项集l 0 。是c g ( k ) 的子集，而c g ( k ) = u ：c g j ：m 。由此公式生成的候选 数据集要比直接在l 僻1 ) 上施行a p r i o r i _ g e n 算法生成的候选数据集量小很多。利用这种方 式，候选数据集的数据量要比c d 算法生成的数据量减少1 0