（计算机应用技术专业论文）分布式数据库关联规则挖掘与更新研究.pdf

摘要 随着数据库和计算机网络技术的广泛应用，许多大型数据库都以分布形式存在。如何 从分布式数据库中挖掘有价值的知识是一个具有挑战性的研究课题。关联规则挖掘是数据 挖掘的核心任务之一，它在金融、电信、保险业、市场营销、异常检测、网络安全、科学 决策等方面具有十分重要的应用价值，因此受到研究人员的高度重视。本文就布尔关联规 则的分布式挖掘与更新、最优数量关联规则的分布式挖掘、约束性关联规则的分布式挖掘 与更新、基于关联规则的分类规则分布式挖掘等方面作了较深入的研究。取得的主要研究 成果如下： ( 1 ) 针对实际应用中存在着大量的全局局部站点模式的分布式数据库环境提出了基 于全局局部站点的分布式数据挖掘系统的体系结构d d m l n e r ，由局部站点和全部站点协 同完成关联规则的分布式挖掘任务，为分布式数据挖掘提供了新的框架。 ( 2 ) 提出了利用h a s h 树生成频繁项目集的有效方法，引入重频繁项目集的概念，提 出面向全局一局部站点模式d d m i n e r 的全局频繁项目集挖掘算法，为分布式关联规则挖掘 提供了新思路。 ( 3 ) 提出了面向全局一局部站点模式d d m i n e r 的频繁项目集分布式更新方法，该方 法能够实现数据库发生变化( 增加或删除) 和最小支持度发生变化后全局频繁项目集的高 效更新。 ( 4 ) 提出了一种利用凸包处理技术求解基于可信度最优的数量关联规则挖掘算法以及 一种支持度和兴趣度撮优的数量关联规则挖掘算法，提出分布式数据库环境下可信度最优 的数量芙联规则挖掘算法以及支持度和兴趣度最优的数量关联规则挖掘算法。 ( 5 ) 引入向导集的概念，提出了面向全局一局部模式d d m i n e r 的分布式约束性频繁 项目集挖掘算法，包括局部约束性频繁项集挖掘算法c l f 和全局约束性频繁项目集挖掘算 法c g f 。为用户在分布式数据库中挖掘感兴趣的关联规则提供了新方法。 ( 6 ) 提出了面向全局局部站点模式d d m i n e r 的约束性频繁项目集的分布式更新算 法，为分布式数据库更新情况下快速挖掘约束性关联规则提供了新的途径。 ( 7 ) 将关联规则分布式挖掘思想应用于分类规则的分布式挖掘，提出了基丁f p - t r e e 的分类规则分布式挖掘算法为分布式环境下分类规则挖掘技术研究作了有意义的探索， 是分布式环境下关联规则挖掘算法的有效应用。 ( 8 ) 研制了分布式数据挖掘原型系统d d m i n e r 验证了论文提出的各个算法的正确 性，测试了有关算法的性能，实验结果表明本文提出的各个算法是有效可行的，且具有较 高的效率。 关键词：数据挖掘，分布式数据库，分布式数据挖掘，分布式关联规则，分布式分类规则 全局频繁项目集约束项。更新 a b s t r a c t w i t ht h ei n c r e a s i n g a p p l i c a t i o no fd a t a b a s ea n dn e t w o r kt e c h n o l o g y , m a n yd i s t r i b u t e d d a t a b a s e sa r ep r o d u c e d i ti sag r e a tc h a l l e n g et o p i ct om i n et h eu s e f u lk n o w l e d g ef r o md i s t r i b u t e d d a t a b a s e sf o rd e c i s i o n m a k i n g d i s t r i b u t e dd a t am i n i n gi sp r a c t i c a lf o ru s ei nm a n yf i e l d ss u c ha s f i n a n c e ，t e l e c o m m u n i c a t i o n ，i n s u r a n c eb u s i n e s s ，m a r k e ta n a l y s i s ，a n o m a l yd e t e c t i o n ，n e t w o r k s e c u r i t y , s c i e n c ed e c i s i o n ，a n ds oo n a s s o c i a t i o nr u l em i n i n gi so n eo f c o r ed a t a - m i n i n gt a s k sa n d h a sa t t r a c t e dt r e m e n d o u si n t e r e s ta m o n gr e s e a r c h e r s 。t h i sp a p e rs t u d i e so nd i s t r i b u t e dm i n i n ga n d u p d a t i n go fb o o l e a na s s o c i a t i o nr u l e s ，d i s t r i b u t e dm i n i n go fo p t i m i z e da s s o c i a t i o nr u l e sf o r n u m e r i ca t t r i b u t e s ，d i s t r i b u t e dm i n i n ga n du p d a t i n go fa s s o c i a t i o nr u l e sw i t hi t e mc o n s t r a i n t s ， d i s t r i b u t e dm i n i n go f c l a s s i f i c a t i o nb a s e do na s s o c i a t i o nr u l e s t h em a i nc o n t r i b u t i o no f t h e p a p e r a r el i s t e da sf o l l o w s ( i ) i n t r o d u c ead a t am i n i n gs y s t e ma r c h i t e c t u r ed d m i n e rb a s e do ng l o b a l l o c a ls i t e i nt h e n e wm i n i n gm o d e l ，l o c a lr u l e sa r em i n e di nl o c a ls i t e sa n dg l o b a lr u l e sa r em i n e di ng l o b a ls i t e d i s t r i b u t e dd a t am i n i n gt a s k si sc o m p l e m e n t e di nc o o r d i n a t i o nw i t hg l o b a ls i t ea n dl o c a ls i t e s ( 2 ) p r e s e n tan e wh a s h - b a s e da l g o r i t h mf o rm i n i n gf r e q u e n ti t e m s e t s i n t r o d u c eac o n c e p to f h e a v yf r e q u e n ti t e m s e t s p r o p o s oan e wa l g o r i t h mf o rm i n i n gg l o b a l l yf r e q u e n ti t e m s e t si n d i s t r i b u t e de n v i r o n m e n tb a s e do nd d m i n e r ( 3 ) i n t r o d u c e u p d a t i n ga l g o r i t h m f o r m a i n t a i n i n gt h eg l o b a l l yf r e q u e n ti t e m s c t s d i s c o v e r e di nad i s t r i b u t e de n v i r o n m e n tb a s e do nd d m i n e r nt h ec a s e si n c l u d i n gi n s e r t i o n ， d e l e t i o ni nt h ed i s t r i b u t e dd a t a b a s e sa n dt h em i n i m u m s u p p o r tt h r e s h o l dc h a r i 西 ( 4 ) p r o p o s ea na l g o r i t h m f o rd i s t r i b u t e d m i n i n go p t i m i z e dc o n f i d e n c eq u a n t i t a t i v e a s s o c i a t i o nr u l e su s i n gc o n v e xh u l lp r o c e s s i n gt e c h n i q u ea n da na l g o r i t h m sf o rm i n i n go p t i m i z e d s u p p o r ta n di n t e r e s t i n g n e s sq u a n t i t a t i v ea s s o c i a t i o nr u l e si nd i s t r i b u t e de n v i r o n m e n tb a s e do n d d m t n e r ( 5 ) d i s c u s st e c h n i q u e sf o rd i s t r i b u t e dm i n i n gg l o b a l l yf r e q u e n ti t e m s e t sw i t hi t e mc o n s t r a i n t s i nd i s t r i b u t e de n v i r o n m e n tb a s e do nd d m l n e r i tp r o v i d e san e wm e t h o df o rm i n i n gi n t e r e s t i n g a s s o c i a t i o nr u l e si nd i s t r i b u t e de n v i r o n m e n t ( 6 ) p r o p o s ea na l g o r i t h mf o rd i s t r i b u t e du p d a t i n gg l o b a l l yf r e q u e n ti t e m s e t sw i t hi t e m c o n s t r a i n t si nd i s t r i b u t e de n v i r o n m e n tb a s e do nd d m i n e ri nt h ec a s e si n c l u d i n gi n s e r t i o n ， d e l e t i o ni nt h ed i s t r i b u t e dd a t a b a s e s ( 7 ) p r e s e n tan e wf r a m e w o r kf o rd i s t r i b u t e dm i n i n gc l a s s i f i c a t i o nr u l e sb a s e do nf p - t r e e s t r u c t u r eb yu s i n gt h ei d e ao fm i n i n ga s s o c i a t i o nr u l e s ，w h i c hc a ne f f i c i e n tm i n i n gc l a s s i f i c a t i o n r u l e si nd i s t r i b u t e de n v i r o n m e n tb a s e do nd d m i n e r e x t e n de f f e c t i v e l ya p p l i c a t i o n so f a s s o c i a t i o nr u l e s ( 8 ) d e v e l o pap r o t o t y p es y s t e md d m i n e rf o r d i s t r i b u t e dd a t am i n i n g a l g o r i t h m s p r e s e n t e di nt h i sp a p e ra r ei m p l e m e n t e da n dt e s t e d 。t h ee x p e r i m e n tr e s u l t ss h o wt h ea l g o r i t h m s a r ee f f e c t i v ea n de f f i c i e n t k e y w o r d s ：d 如m i n i n g ，d i s t r i b u t e dd a t a b a s e ，d i s t r i b u t e dd a t am i n i n g ，d i s t r i b u t e da s s o c i a t i o nr u l e ， d i s t r i b u t e dc l a s s i f i c a t i o nr u l e ，g l o b a l l yf r e q u e n ti t e m s e t s ，i t e mc o n s t r a i n t s ，u p d a t i n g 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人己经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机 构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示了谢意 研究生签名：日期：塑丝， 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文本人 电子文档的内容和纸质论文的内容相一致除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容论文的公布( 包 ： 括刊登) 授权东南大学研究生院办理 研究生签名：荔鼬雌名： 护勿儡 日期： 东南大学博士学位论文 1 1 研究背景及意义 第一章引言 最近十几年来，随着数据库和计算机网络的广泛应用，加上使用先进的数据自动生成 和采集工具，数据库中存储的数据量急剧增大。例如，n a n a 轨道卫星上的地球观测系统 e o s 每小时会向地面发回5 0 g b 的图象信息：世界上最大的数据仓库之一，美国的零售商 系统w a l m a r t 每天会产生约2 亿次的交易数据；人类基因组数据库项目已经收集了数以g b 计的人类基因编码数据等j 面对“堆积如山”的数据集合。无论在时间意义上还是在空间 意义上，传统的数据分析手段都难以应付，人们无法有效地理解并使用这些数据，由此导 致越来越严重的“数据灾难”，造成大量数据资源的浪费。传统的数据分析方法( 例如统计) ， 只能获得这些数据的表层信息，很难对数据进行深层次的处理，而且不能获得数据属性之 间的内在关系和隐禽的信息，即不能获得重要的有价值的知识。这样，海量数据的生成和 搜索技术与滞后的数据分析方法之间形成了鲜明的对照，这需要新的技术来“智能地”和 “自动地”分析海量的原始数据，以使消耗大量财力与物力收集与整理到的宝贵资源 数据得以充分利用，由此引发了一个新的研究方向：数据挖掘( d a t am i n i n g ) 与知识发现 ( k d d ：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 ) 的理论与技术研究。 k d d 包括数据预处理、数据挖掘、知识评价等处理过程。数据挖掘是k d d 过程中的 关键步骤，是指从大型数据库或数据仓库等数据源中提取人们感兴趣的知识，这些知识是 隐含的、事先未知的潜在有用信息，提取的知识一般可表示为概念( c o n c e p t s ) 、规则( r u l e s ) 、 规律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形式。用数据库管理系统来存储数据，用机器学 习的方法来分析数据，挖掘大量数据背后的知识，这两者的结合促成了数据挖掘技术的产 生。数据挖掘是一门交叉性学科，涉及到机器学习、神经网络、模式识别、归纳推理、统 计学、数据库、数据可视化、高性能并行等多个领域。数据挖掘是近年来数据库与人工智 能领域研究的热点课题之一。美国政府开发的s e q u o i a 2 0 0 0 项目把k d d 列为数据库研究领 域中的重要研究课题之一。 在现实环境中，许多大型数据库都是以分布的形式存在的。随着w w w 应j = j 的日趋普及， i n t e r n e t 已成为当今世界最大的分布数据源，i n t e r n e t 中的数据正以几何级数增长，而且 i n t e r n e t 本身就是一个巨大的分布式系统。如何应用i n t e r n e t 中的庞大数据资源，发现和 获取其中有价值的知识，已经成为人们必须正视的问题。而分布式数据挖掘是在i n t e r n e t 中发现和获取有用知识的最佳方法之一。分布式数据挖掘为从“数据海洋”中开采有用的 知识提供了有效途径，它将在金融投资、电信、市场营销、气象和灾难预报、科学决策、 i n t e r n e t 信息浏览等方面发挥巨大作用，具有广阔的应用前景。 数据挖掘技术在科学研究方面具有重大意义，在信息量极为庞大的天文、气象、生物 技术等领域中，大量的实验和观测数据靠传统的数据分析工具难以对付，如果借助数据挖 东南大学博士学位论文 掘技术分析这些海量数据，可以大幅度地提高科学家发现知识的效率。目前在此方面已获 得一些重要的应用成果u j 。例如美国加州理工学院喷气推进实验室与天文学家合作开发的 s k i c a t 系统通过对几百万个天体进行分类，帮助天文学家发现了1 6 个新的类星体；专家 系统d e n d r a l 根据质谱仪给出的数据能够发现己知或未知的高分子化合物分子结构： 机器学习系统b a c o n 根据已有实验和观测数据，能够重新发现欧姆定律、凯普勒定律等， 当然也可以从新的实验和观测数据中发现新的物理或天文定律。、 数据挖掘可为决策者提供重要并有价值的信息和知识，产生不可估量的收益，故基于 数据挖掘技术的产品市场需求日益增长。例如，在金融投资方面，由丁金融投资的风险很 大，因此，在进行投资决策之前，需要对各种投资方向的有关数据进行分析，以选择最佳 的投资方向数据挖掘可以通过对已有数据进行处理，利用学习得到的模式进行市场预测。 在保险业方面，保险是一项风险业务，保险公司的一个重要工作就是进行风险评估。可以 利用数据挖掘技术进行风险分析，在保险公司建立的保单及索赔信息数据库的基础上寻找 保单中风险较大的领域，从而得出一些实用的控制风险的规则，指导保险公司的业务工作。 例如，利用s g i 公司的m i n e s e t 系统提供的分类器就可以预测投保人在将来的索赔概率。 在制造业方面，制造业应用数据挖掘技术进行零件故障诊断、资源优化、生产过程分析等通 过对生产数据进行分析发现容易产生质量问题的工序以及相关的故障因素等。在这一方 面，a c k n o s o f t 公司开发的c a s s i o p e e 系统已用于诊断和预测在波音飞机制造过程中可能 出现的问题。在网络管理领域，在通信网络运行过程中。会产生一系列警告，这些警告有 的可以置之不理。而有的如果不及时采取措施则会带来不可挽回的损失。由于警告产生的 随机性很大，究竟哪些警告可以不予理睬，哪些警告必须迅速处理往往很难判断，一般需 要由人_ t 根据经验进行处理，因此工作效率很低。如果采用数据挖掘技术，可以通过分析 已有的警告信息的正确处理方法以及警告之间的前后关系，得到警告之间的关联规则，这 些有价值的信息可用于网络故障的定位检测和严重故障的预测。例如，芬兰h e l s i n k i 大学开 发了一个基于通信网络中警报数据库的知识发现系统t a s a ，用来寻找通信网络中警报序列 规则，从而进行故障预测。必须特别指出，上述这些数据挖掘技术研究和软件工具大多局 限于单机环境，专门针对分布式数据挖掘工具或系统尚不多见，因而，迫切需要进行分布 式环境下的数据挖掘技术研究。 分布式数据挖掘的研究是近几年才提出的一个新的研究领域，仍属起步阶段，其实现 的功能与数据挖掘的目标相差甚远。j a m 系统是美国哥伦比亚大学s a l v a t o r e s 教授和佛 罗里达理工学院p h i l i p c 教授等人设计的一个分布式数据挖掘系统。该系统可以从各个独 立金融机构的数据库中挖掘出关于诈骗的知识模式。但是，在我国成功的分布式数据挖掘 系统尚未见报道。 本论文根据分布式数据挖掘技术研究的潜在应用背景，结合国家自然科学基金项目“面 向企业风险管理的数据挖掘技术及其应用研究”( 编号：7 9 9 7 0 0 9 2 ) 、江苏省高校自然科学 基金项目“面向分布式数据库的数据挖掘关键技术研究”( 编号：0 1 k j b 5 2 0 0 0 8 ) 及江苏省 高校重点实验室开放基金项目“面向w e b 的分布式数据挖掘研究”( 编号：k j s 0 3 0 6 4 ) 的 研究工作，通过对关联规则挖掘与更新算法的深入分析研究，针对全局一局部站点模式的分 布式数据挖掘系统的体系结构，提出全局频繁项目集挖掘与更新算法，力图在一定程度上 2 东南人学博上学位论文 提高关联规则挖掘算法的效率：提出带约束条件的全局频繁项目集挖掘与更新算法，以挖 掘用户感兴趣的关联规则；提出全局最优数量关联规则挖掘算法，以拓展关联规则挖掘与 更新算法的应用领域。并将关联规则分布式挖掘思想应用于分类规则的分布式挖掘，提出 了基于f p t r e e 的分类规则分布式挖掘算法为分布式环境下分类规则挖掘技术研究作了有 益探索是分布式环境下关联规则挖掘算法的有效应用。 1 2 国内外研究现状 1 9 8 9 年8 月在美国底特律召开的第1 1 届国际人工智能会议上首先出现数据库中知识发 现( k d d ：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 ) 这个术语，随后引起了国际人工智能和数据 库等领域专家的广泛关注。1 9 9 5 年在加拿大蒙特利尔召开了首届k d d d a t am i n i n g 国际 学术会议，从此以后k d d d a t am i n i n g 国际学术会议每年召开一次。由k l u w e r a c a d e m i c p u b l i s h e r s 出版，1 9 9 7 创刊的 k n o w l e d g e d i s c o v e r ya n d d a t a m i n i n g ，, 是该领域中的第一本 学术刊物。经过十多年的努力。数据挖掘技术的研究已经取得了丰硕的成果，不少软件公 司研制出数据挖掘软件产品，并在北美、欧洲等国家得到应用l l j 。捌如，i b m 公司开发的 q u e s t 和i n t e l l i g e n tm i n e r a n g o s ss o f t w a r e 开发的基于规则和决策树的k n o w l e d g es e e k e r ， a d v a n c e ds o f t w a r ea p p l i c a t i o n 开发的基于人工神经网络的d b p r o f i l e ，加拿大s i m o nf r a s e r 大学开发的d b m i n n e r ，s g i 公司开发的m i n e s e t 等。在我国，数据挖掘技术的研究也引起 了学术界的高度重视，成为信息科学界的热点课题。国内许多科研单位和高等院校竞相开 展数据挖掘算法及其应用研究，这些单位包括清华大学、中科院计算技术研究所和数学研 究所、复旦大学、华中理工大学、东南大学、中国科技大学等。 数据挖掘研究具有广泛的应用前景数据挖掘产生的知识可以用于决策支持、信息管 理、科学研究等许多领域。k p a r s a y e 把决策支持空间从应用层次上分成4 个子空间”j ：数 据空间( d a t as p a c e ) 、聚合空间( a g g r e g a t i o ns p a c e ) 、影响空间( i n f l u e n c es p a c e ) 和变化 空间( v a r i a t i o ns p a c e ) ，如图1 - 1 所示。 数据空间处理基于关键字的决策查询，其 中最典型的是联机事务处理( o l t p ) 。对数据空 间中数据元素进行聚合运算( 如s u m ，a v e r a g e ， m a x ，m i n 等) 形成的空间就是聚合空间，它主 要用于联机分析处理( o l a p ) 。影响空间处理逻 辑性质的决策支持，比如同答“是什么因素影响 公司的销售情况? ”这样的问题，这些信息就是 通过数据挖掘得到的。变化空间负责回答某种变 化的过程和速度问题。在上述四个空间中数据 挖掘处于影响空间中，从中可以看出数据挖掘在 决策支持中所处的重要地位。 l 兰塑兰望b决 区三l 一 策 区三卜一 支 持 陌赢l 图1 - 1 决策支持窄间 数据挖掘的研究内容主要分为：关联规j j ( a s s o c i a t i o nr u l eo r a s s o c i a t i o np a t t e r n ) 挖掘、 分类( c l a s s i f i c a t i o n ) 挖掘、聚类( c l u s t e r i n g ) 分析、离群数据( o u t l i e o 挖掘、预测( p r e d i c t i o n ) 、 东南大学博士学位论文 序列模式分析、特征规则挖掘、趋势分析、偏差分析、回归分析等 4 1 。其中，关联规则是数 据挖掘的重要内容。自a g r a w a lr1 9 9 3 年提出布尔型关联规则问题及相应的a p r i o r i 算法以 来p “，数据挖掘领域的研究者在关联规则挖掘上做了大量的工作。 关联规则挖掘的研究r 作主要包括：a p r i o r i 算法的扩展【。”】、数量关联规则挖掘“1 、 关联规则增量式更新 1 7 - 2 3 】、无须生成候选项目集的关联规则挖掘”1 、最人频繁项目集的 挖掘p 6 3 ”、约束性关联规则挖掘口4 。3 7 以及并行及分布关联规则挖掘算法 3 s - 4 9 等，其中快速 挖掘与更新频繁项目集是关联规则挖掘研究的重点，也是多种数据挖掘应用中的技术关键， 已用于分类规则挖掘 5 “s s l 和网络入侵检测【5 6 删等方面的研究。研究者还对数据挖掘的理论 进行了有益的探索，将概念格和粗糙集应用于关联规则挖掘中1 6 “”，获得了显著的效果， 但这些研究工作目前主要针对单机环境，国内外学者针对分布式数据库环境下的挖掘技术 研究不多，虽取得了一定的进展但还处在起步阶段，迫切需要在分布式挖掘与更新算法 及系统实现等方面进行深入研究。 到目前为止，关联规则的挖掘已经取得了令人瞩目的成果，主要包括： ( 1 ) 单机环境下的关联规则挖掘算法p 1 1 2 3 w 这是关联规则挖掘的基本方法。其中比较著名的算法包括a g r a w a l 等人提出的a p r i o r l 4 j ， s a v a s e f e 等人提出的分割算法p a r t i t i o n i s l ，t o i v o n e n 提出的抽样算法s a m p l i n g ”以及 h a r tj w 等人提出的基于频繁模式树( f p - t r e e ) 的频繁项目集挖掘算法f p g r o w t h l 2 s l 等等。 其中，a p r i o r i 算法的基本思想是重复扫描数据库。在第k 次扫描时产生出长度为k 的频繁 项目集l k ，而在第k + 1 次扫描时，只考虑由l k 中的k 项集产生长度为k + 1 的候选集 c k 川p a r t i t i o n 算法是将数据库进行分割，减少挖掘过程中i ( 9 操作次数； s a m p l i n g 算法是首先对数据库进行抽样，然后对抽样数据库进行挖掘，从而提高挖掘效率。f p - g r o w t h 算法是通过构建f p - t r e e 来求解频繁项目集。研究人员还提出了一些a p r i o r 算法的改进算法。 ( 2 ) 多值属性关联规则挖掘【i 。”1 关联规则可分为布尔关联规则和多值属性关联规则。多值属性关联规则义可分为数量 关联规则和类别关联规则。数量关联规则是指同时包含布尔属性和连续属性的关联规则。j a g r a w a l 等人扩展布尔属性的关联规则算法，将其虑用于数量关联规则的挖掘，提出了基于 支持度的部分k 度完全方法：f u k u d a 提出了等深度划分的实现方法；苑森淼教授提出数量 关联规则的挖掘中的聚类方法p k c c a 。目前提出的类别属性关联规则的挖掘算法大多是将 类别属性关联规则挖掘问题转化为布尔型关联规则挖掘问题。即将类别属性中的每一个类 别当作一个属性。数量关联规则挖掘的关键问题是对连续属性进行离散化。 ( 3 ) 关联规则更新算法 1 7 叫 关联规则的更新问题主要有两种情况：在给定的摄小支持度和最小置信度条件p ， 当数据库变化后，如何生成数据库中的关联规则：给定一个数据库，在摄小支持度和最 小置信度发生变化时，如何生成数据库中的关联规则。针对集中式数据库系统，研究人员 提出了关联规则的更新算法，例如：用于数据库发生变化( 只考虑数据库中事务增加的情 况) 时关联规则更新的f u p 算法、用于支持度发生变化时关联规则更新的i u a 算法和 n e w i u a 算法。但这些算法不适用于分布式数据库系统。文献 2 2 ，2 3 探讨了分布式数据库 环境下关联规则更新问题。 4 东南大学博士学位论文 ( 4 ) 基于约束条件的关联规则挖掘p 4 ”】 基于约束条件的关联规则挖掘的主要目的是发现更有趣、更实用、更特别的关联规则。 文献 3 4 - 3 5 研究了在提供布尔表达式约束情况下的关联规则发现问题。文献 3 6 3 7 分布式 数据库环境下带有约束条件的关联规则挖掘，但更新问题尚未见报道。 ( 5 ) 关联规则并行及分布挖掘算法1 3 8 - 4 9 目前已经提山的关联规则并行挖掘算法有：a g r a w a l 等人提出的算法c d ( c o u n t d i s t r i b u t i o n ) 、c a d ( c a n d i d a t e d i s t r i b u t i o n ) 、d d ( d a m d i s t r i b u t i o n ) ，p a r k 等人提出的算法 p d m 等。用于分布式数据库系统中进行关联规则挖掘的比较著名的算法有：f d m 、d m a 、 d d d m 等。 1 3 本文主要研究内容 本论文的主要工作是根据国内外在分布式数据库环境下的挖掘技术研究现状及其最新 发展动态，研究分布式数据库中多种关联规则的挖掘与更新问题，研制分布式关联规则挖 掘原型系统。论文主要研究内容包括以下几个方面。 1 研究分布式数据挖掘系统的体系结构与数据通信代价优化问题 分布式数据库的特点是数据的分布性。面向分布式数据库的挖掘算法的特点在于，它 能将用户提出的全局挖掘要求处理成一系列对分布在不同站点上的不同数据库的挖掘要 求。在箨个不同站点进行数据挖掘产生本地知识，经过备站点问的协同产生全局知识。这 些工作对用户是透明的。现有的分布式关联规则挖掘算法基本都是面向对等结构的分布式 数据库环境而提出的，但实际应用中存在着大量的全局- 局部站点模式的分布式数据库环境， 因此本文提出了基于全局局部站点的分布式数据挖掘系统的体系结构d d m i n e r ，由局部 站点和全局站点协同完成关联规则的分布式挖掘任务。 挖捌关联规则最主要的代价是计算频繁项集，然而在分布式环境下挖掘关联规则会出 现一些新问题：相对而言，在一个局部数据库中可以较容易地计算出局部频繁项集，但局部 频繁项集不一定就是全局频繁项集，为了产生关联规则，分布式系统中的各个站点之间要进 行通信。因此如何解决分布式系统中数据挖掘的数据通信代价优化问题，以提高分布式数 据挖掘的效率是一个值得研究的问题。 2 研究布尔关联规则分布式挖掘与更新算法 根据不同的数据对象及应用需求，可以挖掘不同的关联规则例如布尔关联规则、数 量关联规则、约束性关联规则、最优关联规则等。本文对上述多种关联规则的挖掘与更新 问题均作了研究。 在关联规则的挖掘过程中，频繁项目集( f r e q u e n t l t e m s e t s ) 的生成是关键问题，也是算 法中运行时间最长的部分。通常频繁项目集的计算方法是将每个候选项目集( c a n d i d a t e i t e m s e t s ) 与每个事务进行匹配，以求得所有候选项目集的支持数，通过筛选得出频繁项目 集。本文利用h a s h 树生成频繁项目集的新方法，该方法首先建立h a s h 树，然后利用h a s h 树计算候选项目集支持数。d m a 算法是较著名的面向对等分布式数据库环境挖掘全局频繁项 东南大学博士学位论文 目集算法。爱d m a 算法的启发，提出面向全局- 局部站点模式d d m i n e r 的布尔型全局频繁 项目集挖掘算法g f m ，它基于a p r i o r i 算法的思想产生候选项集，引入重频繁项目集的概念， 利用局部频繁项集和全局频繁项集之间有趣的性质，在每次循环时通过重频繁项目集产生 较少的候选频繁项集，对局部候选项目集进行修剪，利用h a s h 树计算候选项目集支持数， 因此不仅降低了数据通信量，而且节省了计算候选项目集支持数所需时间，使得g f m 算法 的执行效率优于现有一些算法。 现有分布式环境下的全局关联规则挖掘算法很少考虑更新问题。为此，本文对基于全 局局部站点模式的分布式数据库环境d d m l n e r 的布尔关联规则分布式更新问题进行研 究。考虑两种情况：一是假定最小支持度和晟小可信度不变，当数据库发生变化( 增加或 删除) 时，关联规则如何高效更新；二是假定数据库和最小可信度不变，当虽小支持度发 生变化时，关联规则如何高效更新。提出了数据库发生变化( 增加或删除) 后局部频繁项 目集的更新算法u l f 和全局频繁项目集的更新算法u g f ；提出了最小支持度发生变化后局 部频繁项目集的更新算法u l f s 和全局频繁项目集的更新算法u g f s 。 3 研究最优数量关联规则的分布式挖掘算法 数量关联在银行存款分析，股市行情分析等众多领域都有重要应用价值。对现有成果 的考察表明，数量关联规则的研究较少，且研究工作局限于单机环境。本文讨论了数量关 联规则挖掘过程中连续属性的离散化问题，在此基础上提出利用凸包处理技术求解基于可 信度虽优的数量关联规则挖掘算法，将该方法应用于股市行情分析，首次提山分布式数据 库环境下可信度最优的数量关联规则的挖掘算法。 文章还讨论了数量关联规则的有趣性问题，给出数量关联规则的客观兴趣度的度量函 数，提出用模板匹配方法将用户感兴趣的规则和不感兴趣的规则区分开，以解决数虽关联规 则有趣性的主观评测。提出了一种挖掘支持度和兴趣度最优的数量芙联规则方法，将该方 法应用于股市行情分析，首次提出分布式数据库环境r 支持度和兴趣度最优的数量关联规 则的挖掘算法。 4 研究约束性关联规则分布式挖掘与更新算法 对分布式数据库系统中约束性关联规则挖掘研究具有重要意义，因为人多数情况下， 用户只对关联规则中的一部分感兴趣，有时用户只想知道包含某些特定项的规则。在现有 文献中，分布式数据库系统中约束性关联规则挖掘算法很少，而分布式数据库系统中约束 性关联规则更新算法尚未见报道。 本文引入向导集的概念，提出基于全局一局部模式d d m l n e r 的分布式局部约束性频繁 项集挖掘算法c l f 和全局约束性频繁项集挖掘算法c g f ，该算法首先根据布尔约束条件产 生向导集，然后通过向导集高效地产生分布式环境中满足约束条件的完备的候选项集。提 出基于全局局部模式d d m i n e r 的局部约束性频繁项集更新算法u l f c 和全局约束性频繁 项集更新算法u g f c 。 5 研究分布式数据库环境下利用关联规则分布式挖掘分类规则的算法。将关联规则分 布式挖掘思想应用于分类规则的分布式挖掘，提出基于f p - t r e e 的分类规则分布式挖掘算法。 该方法首先在局部站点上建立局部f p - t r e e ，压缩存储局部决策表并通过传送条件频繁模 6 东南大学博士学位论文 式树或条件模式基在全局站点建立全局条件频繁模式树，然后对建立的全局条件频繁模式 树进行挖掘得到全局分类规则。该方法为分布式环境下分类规则挖掘技术研究作了有益探 索，是分布式环境下关联规则挖掘算法的有效应用。 6 研制分布式数据挖掘原型系统d d m i n e r ，将本文提出的算法用j a v a 语言加以实现 验证各个算法的正确性，测试各个算法的性能，实验结果表明本文提出的各个算法是有效 可行的，且具有较高的效率。 1 4 本文主要研究成果 本文的主要研究成果体现在以下儿个方面： ( 1 ) 现有的分布式关联规则挖掘算法基本都是面向对等结构的分布式数据库环境而提 出的，但实际应用中存在着大量的全局局部站点模式的分布式数据库环境。因此提出了基 于全局局部站点的分布式数据挖掘系统的体系结构d d m i n e r ，由局部站点和全局站点协 同完成关联规则的分布式挖掘任务，为分布式数据挖掘提供了新的框架。 ( 2 ) 提出了利用h a s h 树生成频繁项目集的有效方法，该方法首先建立h a s h 树，然 后利用h a s h 树计算候选项目集支持数，从而提高了频繁项目集的生成效率。在此基础上提 出面向全局局部站点模式d d m i n e r 的全局分布式频繁项目集挖掘算法，该算法引入重频 繁项目集的概念，利用局部频繁项集和全局频繁项集之间有趣的性质，在每次循环时通过重 频繁项目集产生较少的候选频繁项集对局部候选项目集进行修剪，利用h a s h 树计算候选 项目集支持数，使得该算法的执行效率优于现有一些算法。 ( 3 ) 提出了面向全局局部站点模式d d m i n e r 的频繁项目集分布式更新算法，该更 新算法包括4 个模块：数据库发生变化( 增加或删除) 后局部频繁项目集的更新算法u l f 和全局频繁项目集的更新算法u g f ；最小支持度发生变化后局部频繁项目集的更新算法 u l f s 和全局频繁项目集的更新算法u g f s 。 ( 4 ) 提出了一种利用凸包处理技术求解基于可信度最优的数量关联规则挖掘算法以及 一种支持度和兴趣度最优的数量关联规则挖掘算法，在此基础上提出分布式数据库环境下 可信度最优的数量关联规则挖掘算法以及支持度和兴趣度最优的数量关联规则挖掘算法。 ( 5 ) 引入向导集的概念，提出了面向全局一局部模式d d m i n e r 的分布式约束性频繁 项集挖掘算法，包括局部约束性频繁项集挖掘算法c l f 和全局约束性频繁项集挖掘算法 c g f 。为用户在分布式数据库中挖掘感兴趣的关联规则提供了新方法。 ( 6 ) 提出了分布式数据库环境中约束性频繁项集的更新算法，包括局部约束性频繁项 集更新算法u l f c 和全局约束性频繁项集更新算法u g f c 。为分布式数据库更新情况下快 速挖掘约束性关联规则提供了新的途径。 ( 7 ) 将关联规则分布式挖掘思想应用于分类规则的分布式挖掘提出了基于f p t r e e 的分类规则分布式挖掘算法，为分布式环境下分类规则挖掘技术研究作了有意义的探索， 是分布式环境下关联规则挖掘算法的有效应用。 ( 8 ) 研制了分布式数据挖掘原型系统d d m i n e r ，验证了论文提出的各个算法的正确 7 东南大学博士学位论文 性，测试了有关算法的性能实验结果表明本文提出的各个算法是有效可行的，且具有较 高的效率。 1 5 本文的组织结构 本文主要上作研究分布式数据库中多种关联规则的挖掘与更新问题，论文共分六章， 具体组织结构如下。 第一章引言，介绍分布式数据挖掘研究的意义以及应用需求，说明本课题的研究背景 和来源，描述关联规则挖掘研究领域的国内外研究现状，介绍现有的解决方案、发展趋势 和存在的不足；概述论文的主要研究内容和方法，简要地介绍本文的主要研究成果。 第二章研究布尔型关联规则分布式挖掘与更新算法。介绍相应魄研究现状、关键技术 及有关关联规则、频繁项目集、重频繁项目集、h a s h 树等概念。针对实际应用中存在着大 量的全局局部站点模式的分布式数据库环境，提出基于全局一局部站点的分布式数据挖掘系 统的体系结构d d m i n e r 。论述利用h a s h 树生成频繁项目集的原理与算法，提出基于全局