（计算机应用技术专业论文）分布多库环境下的挖掘算法研究.pdf

摘要 网络技术和数据库技术的发展带动了企事业单位的信息化建设，日积月累。使得企事业数据库 和数据仓库中存储了大量的数据，且很多大型企事业数据库是分布架构的。如何从分布环境下的企 事业数据库中挖掘对企事业决策者有用的知识是个具有挑战性的研究课题。近十年来，人们对分 布多库环境下的数据挖掘技术进行了广泛而深入的研究，取得了许多研究成果，使其在商务管理、 生产控制、市场分析、工程设计和科学探索等方面得到广泛应用，正日益受到了广大研究者的高度 重视。本文就此领域从全局频繁项目集及全局最大频繁项目集挖掘与更新、数据库相似性度量及全 局属性约简方法三个方面入手，进行了较为深入的研究。 论文工作的主要成果表现在以下几个方面： ( 1 ) 改进了传统的全局频繁项目集挖掘方法，提出一种新的基于f p - t r e e 的全局频繁项目集挖掘 模型。在此模型中，f p - t r e e 可压缩存储各局部数据库，通过传送条件模式基或条件频繁模式树可减 少网络通讯量，因而可为分布多库环境下的全局频繁项目集挖掘提供一种新的框架。 ( 2 ) 引入条件概念格的概念，提出一种新的基于条件概念格的全局最大频繁项目集挖掘模型。在 此模型中，通过在各站点并行建立的条件概念格可获得所有的全局最大频繁项目集，为概念格在分 布多库环境下的数据挖掘技术研究提供了新的思路，也为数据挖掘的模式可视化表示提供新的途径。 ( 3 ) 提出基于f p - t r e e 的全局最大频繁项g t 集挖掘与更新模型，为在分布多库环境f 含有较模 式的全局频繁项目集挖掘与更新提供了新的方法。 ( 4 ) 提出基于f p t r e e 的全局频繁项目集更新方法。在该方法中，利用己挖掘的全局频繁项目集 和已建立的f p - t r e e 可有效提高全局频繁项目集的更新效率。 ( 5 ) 提出基于条件概念格的全局最大频繁项目集更新方法。在该方法中，利用已建立的条件概念 格可有效提高全局最大频繁项目集的更新效率。 ( 6 ) 提出基于最大加权频繁项目集的数据库相似性或相关性判别模型。在该模型中，不仅考虑项 目集的频度还考虑项目集中各项目的重要眭，确保挖掘出包含重要项目的项目集，从而提高数据库 相似性- i j n 准确度。 ( 7 ) 提出一种基于关联规则的单决策表属性约简模型，为单决策表的属性约简提供了一种新的框 架。该模型可借用高效的关联规则挖掘算法，算法的可扩展性好，可用于大型决策表的属性约简， 有效拓展了粗糙集的应用范围。 ( 8 ) 提出分布环境下的多决策表属性约简框架，将单机环境下的属性约简推广到分布环境，为分 布环境下的粗糙集应用研究提供新的途径，也使粗糙集在分布环境下的应用成为可能。 关键词数据挖掘，分布多库环境，全局频繁项目集，全局最大频繁项目集，更新，数据库相似性 最小属性约简 a b s t r a c t t h ei n c r e a s i n gu s eo f n e t w o r ka n dd a t a b a s et e c h n o l o g y , h a sl e d t ot h ed e v e l o p m e n to fm a n y m n l t 一d a t 曲a s es y s t e m sf o r r e a lw o r l da p p l i c a t i o n si nm a n ye n t e r p r i s e s f o rd e c i s i o n - m a k i n g ，l a r g e o r 仨a n i z a t i o n sn e n dt om i n et h em u l t i p l ed a t a b a s e sd i s t r i b u t e dt h r o u g h o u tt h e i rb r a n c h e s ，w h i c hi s ag r e a t c h a l l e n g et o p i c d u r i n gl a s t t e ny e a r s ，m a n yr e s e a r c h e r sh a v ed o n em u c hi nd a t am i n i n gf i e l d s i n d i s t r i b u t e de n v i r o n m e n t ，a n dp r o p o s e dl o t so fm i n i n gm e t h o d s n o w a d a y s ，d a t am i n i n gt e c h n o l o g yh a s b e e nw i d e l yu s e di nb u s i n e s sm a n a g e m e n t ，p r o d u c t i o nc o n t r o l ，m a r k e ta n a l y s i s ，e n g i n e e r i n gd e s i g n ，s c i e n c e e x p l o r a t i o n a n ds oo i l ，i n t h i sp a p e r , w em a d es y s t e m i ca n dd e e ps t u d yf r o mt h r e ea s p e c t s ：t h em i n i n g a n d u p d a t i n g f o r g l o b a l l yf r e q u e n t i t e m s e t sa n d g l o b a l l y m a x i m u mf r e q u e n ti t e m s e t s ，m e t h o df o r m e a s u r i n g d a t a b a s es i m i l a r i t ya n dg l n b a l l ya t t r i b u t e sr e d u c t i o nf o rm u l t i p l ed e c i s i o nt a b l e s t h em a i nc o n t r i b u t i o n so f t h ep a p e ra r el i s t e da sf o l l o w s ( 1 ) i m p r o v et h et r a d i t i o n a lm e t h o d sf o rm i n i n gg t o b a l i yf r e q u e n ti t e m s e t sa n dp r o p o s ean e wm o d e l b a s e do nf p t r e es t r u c t u r ei nn e wm o d e l ，e a c hl o c a ld a t a b a s ei sc o m p r e s s e di n t oe a c hl o c a lf p - g e e ，b y t r a n s m i t t i n gc o n d i t i o n a lp a t t e r nb a s e so rc o n d i t i o n a l l yf r e q u e n tp a t t e r n t r e e si n s t e a do f t r a n s f e r r i n gf r e q u e n t c a n d i d a t ei t e m s e t s t h en e wf r a m e w o r ku s e sf 打l e s sc o m m u n i c a t i o no v e r h e a da n di m p r o v e se f f i c i e n c yo f m 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 s ( 2 ) i n t r o d u c eac o n c e p to fc o n d i t i o nc o n c e p tl a t t i c ea n dp r e s e n tan e wm e t h o db a s e do nc o n d i t i o n c o n c e p tl a t t i c e f o rm i n i n gg l o b a l l ym a x i m u mf r e q u e n ti t e m s e t si nn e wm o d e l ，e v e r yc o n d i t i o nc o n c e p t l a t t i c ec a nb ec r e a t e da te a c hs i t ei n p a r a l l e l ，a n dt h eg l o b a l l ym a x i m u mf r e q u e n ti t e m s e t sc a na l s ob e a c q u i r e di np a r a l l e l ，s oi ti san e wi d e at or e s e a r c ho nd a t am i n i n gb a s e do nc o n c e p tl a t t i c ei nd i s t r i b u t e d e n v i r o n m e n ta n da l s op r o v i d e san e wm e a n st ov i s u a l i z et h e p a t t e r n sm i n e d ( 3 ) p r e s e n tan e wf r a m e w o r kf o rm i n i n ga n du p d a t i n gg l o b a l l ym a x i m u mf r e q u e n ti t e m s e t sb a s e do n f p t r e e s t r u c t u r e ，e s p e c i a l l y w h i c hi sa ne f f i c i e n tm e t h o df o r m i n i n ga n du p d a t i n gg l o b a l l yf r e q u e n t i t e m s e t sw i t hl o n gp a t t e r n s ( 4 ) p r o p o s ean e wm e t h o df o ru p d a l i n eg l o b a l l yf r e q u e n ti t e m s e t sb a s e do nf p - t r e es t r u c t u r e , w h i c h c a ne f f e c t i v e l yu s et h eg l o b a l l yf r e q u e n ti t e m s e t sm i n e da n de v e r yl o c a lf p t r e e c r e a t e d ，h e n c et h en e w f r a m e w o r ki se f f i c i e n ta n de f f e c t i v e ( 5 ) i n t r o d u c ean e wm o d e lf o ru p d a t i n gg l o b a l l ym a x i m u mf r e q u e n ti t e m s e t sb a s e do nc o n d i t i o n c o n c e p tl a t t i c e ，w h i c hc a ne f f e c t i v e l yu t i l i z et h ec o n d i t i o nc o n c e p tl a t i c e sc r e a t e d ，h e n c ei m p r o v e st h e u p d a t i n ge f f i c i e n c y ( 6 ) p r e s e n tan e wm o d e lf o rm e a s u r i n gd a t a b a s es i m i l a r i t yb a s e do nm a x i m u mw e i g h t e df r o q u e n t i t e m s e t s ，t h ea c c u r a c yo f d a t a b a s es i m i l a r i t ye s t i m a t i o ni si m p r o v e db y c o n s i d e r i n gt h ef r e q u e n c yo f i t e m s e t a n dt h es i g n i f i c a n c eo f e a c hi t e r nj nt h ei t e m s e t ( 7 ) p r o p o s ea n e w m e t h o d f o r a t t r i b u t e sr e d u c t i o n 。f as i n g l e d e c i s i o n t a b l eb a s e d o n a s s o c i a t f o nr u e s b yu s i n gt h ep r e v i o u s l ye f f i c i e n ta l g o r i t h mf o rm i n i n ga s s o c i a t i o nr u l e s ，n e wf r a m e w o r ki s f e a s i b l ef o r a t t r i b u t e sr e d u c t i o no f t h e l a r g ed e c i s i o nt a b l e ，s oa p p l i c a t i o n so fr o u g hs e tc a nb ee x t e n d e de 毹c h v e l ( 8 ) p r e s e n tan e wi d e af o ra t t r i b u t e sr e d u c t i o no fm u l t i p l ed e c i s i o nt a b l e si nd i s t r i b u t e de n v i r o n i n e n l w h i e hi se x t e n s i o no ft h em o d e li ns e q u e n t i a le n v i r o n m e n t ，a n da l s op r o v i d e s an e wm e t h o df o rs o i v i n 窟t h e a p p l i c a t i o n so f r o u g hs e ti nd i s t r i b u t e de n v i r 0 i t m e n t k o y w o d sd a t am i n i n g ，m u l t i - d a t a b a s ei n d i s t r i b u t e d e n v i r o n m e n t ，g l o b a l l yf r e q u e n ti t e m s e t s ，gj o b a l l y m a x l m “m t 。q u e n ti t e m s e t s - u p d a t i n g ，d a t a b a s e ss i m i l a r i t y , m i n i m u ma t t r i b u t e sr e d u c t i o n 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。 研究生签名 日期： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研 究生院办理。 研究生签名 导师签名： 日期： 整二童坚垄一 1 1 选题依据及意义 第一章概述 数据挖掘是近年来信息技术领域讨论和研究的热点之一，也是数据库系统应用研究的一 个重要方向。随着数据库技术和网络技术的快速发展，备类企事业单位十分重视信息化建设， 相继构建了本单位的i n t r a n e t e x t r a n e t 环境和数据库应用系统，日积月累，这些企事业单位 的数据库系统均存储了大量的历史数据和运行数据，从而构成了分布式环境下的多数据库 ( 本文简称分布多库) 系统；进而由于计算机技术深入应用的需要，企事业单位的决策层迫 切需要将这些分布数据转换成为有用的信息和知识，为诸如商务管理、生产控制、市场分析、 1 ：程设计、科学探索和网络安全检测等提供决策依据，这就使得进行分布多库环境下的挖掘 技术研究具有重要的实际意义。 从已构建的大型分布多库中高效地提取并发现隐含的、未知的、有潜在应用价值的模式 或规则，为企事业进行前瞻性的、基于知识的决策提供科学依据是分布多库挖掘的最终目标。 分布多库挖掘年| 1 单机环境下的数据挖掘一样，是一种智能分析和预测技术，但它不同于联机 事务处理，也不同于静态的统计分析方法。它实质上是综台利用数据库技术、人工智能、机 器学习、神经网络、统计学、模式识别、知识库系统、知识获取、信息检索、高性能计算机 和数据库可视化等的新应用技术。 因数据挖掘( d a t a m i n i n g , ，d m ) 可为决策者提供重要并有价值的信息和知识，产生不可 估量的收益，故基于数据挖掘技术的产品市场需求日益增长。至今，已出现了一些用于支持 企业决策的挖掘软件：( 具，如i b m 的企业智能软件可为金融、制造、电信、保险及运输业 提供决策管理的解决方案；但这些数据挖掘软件工具大多局限于单机环境，专门针对分布多 库的数据挖掘工具或系统尚不多见，因而迫切需要进行分布多库环境下的挖掘技术研究。 下面，我们举2 个实例来说明这种分布多库环境下数据挖掘技术应用的迫切性： 其一，网络技术的发展带动了企业和政府信息化建设。越来越多的企业有了与i n t e r n e t 相连接的网站。企业决策者和政府领导面对海量分布多库数据无所适从：与此同时，网络也 给企事业单位带来了严重的安全隐患。通常而言，对网络安全的威胁主要表现在：未授权的 非法访问、冒充合法用户、破坏数据的完整性、干扰系统正常运行、利用网络传播病毒、线 路侦听笥。为克服网络带来的安全问题，并针对目前网络安全产品( 如防火墙、v p n 、c a 及扫描器等) 存在的不足，研究者们提出了基于网络的入侵检测系统( n e t w o r ki n t r u s i o n d e t e c t i o ns y s t e m ) ，其中基于用户模式的网络异常检测是网络入侵检测的重要研究技术，也 是分布多库环境下的挖掘技术的研究内容之一。 其二，p e e r - t o p e e “p 2 p ) 和g r i d 计算作为一种新兴的分布式技术，正逐步应用于文件 共享、网络协同计算、实时信息传递等领域。p 2 p 技术为连接在i n t e m e t 及i n t r a n e t 上的人 量计算机共享自身的c p u 计算能力、存储空间、网络带宽等资源提供了一个有效的途径。 在p 2 p 网络中，所有参与者的地位相互平等、互相协作。在利用整个网络资源和服务的同 时，每个站点也为系统中的其他站点提供服务，在此背景下，基于p 2 p 的多库挖掘算法研 究对数据挖掘的研究者来说也将是一个新的课题。 本论文在广泛调研的基础上，根据分布多库环境f 的挖掘技术研究的潜在应用背景，结 合国家自然科学基金项目“面向企业风险管理的数据挖掘技术及其应用研究，( 基金立项编 号：7 9 9 7 0 0 9 2 ) 、安徽省自然科学基金项目“面向分布式数据库的数据挖掘技术研究，( 基金 立项编号：0 3 0 4 2 2 0 5 ) 及国家中小型企业刨新基金项目“企业商务智能决策导航器- e b i d n ” ( 基金立项编号：0 2 c 2 6 2 1 3 2 1 0 0 7 0 ) 的研究工作，通过对概念格理论和f p t r e e 存储结构等 查壹奎兰竖圭兰焦丝兰一 的深入应用研究，力图在一定程度上解决分布多库环境下的全局频繁项目集及全局最大频繁 项目集挖掘与动态更新算法存在的低效率问题；提出基于最大加权频繁项目集的数据库相似 性度量准则。以此改进目前数据库相似性度量存在的不足；提出分布环境下的属性约筒求解 模型，拓展和推广经典的粗糙集属性约简方法，为分布多决策表环境下的决策规则挖掘提供 了新的思路和技术。 1 2 国内外研究现状 1 9 8 9 年8 月在美国底特津召开的第1 1 届国际人工智能会议上首次出现数据库知识发现 ( 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 ) 这个术语，随后引起了国际人工智能和数据库等 领域专家的广泛关注。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 国际学术会议每年召开 一次，经过十多年的努力，数据挖掘技术的研究已经取得了丰硕的成果。 数据挖掘的研究内容主要分为：相关性分组或关联规则或关联模式( a f f i n i t yg r o u p i n g o r a s s o c i a t i o nr u l eo ra s s o c i a t i o np a t t e m ) 、分类( c l a s s i f i c a t i o n ) 、估值( e s t i m a t i o n ) 、预测 ( p r e d i c t i o n ) 、聚集( c l u s t e r i n g ) 、描述和可视化( d e s c r i p t i o na n dv i s u a l i z a t i o n ) 以及序列 规则等，其中，关联规则、分类规则是数据挖掘的主要内容“j 。自a g r a w a lr1 9 9 3 年提出布 尔弛关联规则问题及相应的a p r i o r i 算法以来口，】，数据挖掘领域的研究者在关联规则与分类 规则挖掘上做了大量的工作1 4 - 2 9 。 关联规则挖掘的研究工作主要包括：a p r r ) r i 算法框架的扩展”j 川、关联规则的扩展i 1 、 量化关联规则的挖掘口1 、关联规则的增量式更新1 6 , 7 , 1 1 , 2 2 - 2 4 、无须生成候选项目集的关联规则 挖掘【2 0 2 l 】阻及最大频繁项目集的挖掘b 2 - t g l 等，其中快速挖掘与更新频繁项目集是关联规则挖 掘研究的重点，也是多种数据挖掘应用中的技术关键，已用于网络入侵检测口“”1 和分类规则 挖掘1 2 5 - 2 9 等方面的研究。同时，研究者还对数据挖掘的理论进行了有益的探索，并将概念格 和粗糙集应用于关联规则和分类规则的挖掘中1 3 6 - 6 1 1 “o ”j ，获得了显著的效果，但这些研究 一| 二作目前主要针对单机环境，国内外学者对分布多库挖掘技术研究主要集中在集成和查询优 化方面”“，针对分布多库环境下的挖掘技术研究得不多，虽取得了一定的进展 6 5 - 7 2 u 2 - 1 2 s 】， 但还处在起步阶段，迫切需要在分布多库的高效挖掘算法及数据库相关性度量等方面进行深 入研究。 现有的一些关于全局频繁项目集挖掘算法。”( 如比较著名的算法有：p o m 、c d 、f c i d 、 d d d m 等) 可以挖掘出分布多库环境下的关联规则。但这些算法大多基于a p r i o r i 算法框架， 在白底向上的搜索过程中将产生和传送大量的候选项目集，因而存在着网络通讯代价高，算 法效率低等缺点；同时，这些算法假定各局部数据库间的模式相同且具有相似的特征，各局 部数据库可看成一个虚拟全局数据库的水平划分，不考虑数据库的相关性，因而在有些情况 下会挖掘出一些无用的规则而使一些重要的规则被忽略，不能满足具体应用的需求。 为有效地进行分布多库环境下的挖掘技术研究，首先应判别各局部数据库间的相似性或 相关性，然后将相关或相似的局部数据库组合在一起，最后再进行规则挖掘。目前，数据库 相关性研究成为数据挖掘的另一个热点，受到数据挖掘研究者的重视，已提出一些判别数据 库相关或相似的方法”“”1 ，其中比较典型的有基于最大频繁项目集的数据库相似性或相关 性判别方法”“”，该方法可减少网络通讯量，且可有效进行数据库相似度量，是文献 1 2 5 方法的改进。但该方法未考虑项目的重要性，使得在挖掘晟大频繁项目集及数据库相似性判 别中忽略了重要项目的作用，因而影响数据库相似性的判别准确性。 粗糙集为决策表的分类规则挖掘提供了有效的数学方法，而在基于粗糙集的分类规则挖 掘研究中，属性约简的求解起着关键的作用陋1 0 ”。目前，国内外现有的属性约简的求解算 2 笙二兰塑垄 一 法均是基于主存的，不少算法还是不完备的，难以适用于大型高维决策表的属性约简求解。 同时，已有的属性约简算法主要是基于单决策表，针对分布多决策表环境下的属性约简求解 算法的报道尚不多见a 1 3 论文研究工作的主要内容 根据国内外在分布多库环境下的挖掘技术研究现状及其最新发展动态，论文工作主要在 全局频繁项目集及全局最大频繁项目集挖掘与更新、数据库相似性度量及分布环境下的属性 约简方面展开了深入研究。具体而言，论文将在以下几个方面介绍论文研究工作的进展和相 应成果。 1 3 1 全局频繁项目集及全局最大频繁项目集挖掘与更新技术研究 主要包括如下几个方面： 1 ) 基于f p t r e e 的全局频繁项目集挖掘 已有的全局频繁项目集算法大多采用a p r i o r i 框架，须传送大量的局部频繁项目集，虽 然可通过一些策略来修剪局部频繁项目集，但也只能在一定程度降低网络通讯量。在单机环 境下，基于频繁模式树( f r e q u e n t p a t t e r nt r e e ，f p t r e e ) 的f p g r o w t h 算法无须生成候选项 目集，可有效地提高频繁项目集的挖掘效率。 本文在分布环境下应用f p t r e e 存储结构进行全局频繁项目集挖掘，首先通过扫描各局 部数据库，得到各项目的全局频度；其次依据全局频度建立各局部f p t r e e ，使各局部数据 库信息压缩存储在局部f p t r e e 的相应路径中；最后依据各局部f p t r e e ，通过传送条件模式 基或条件频繁模式树建立全局条件频繁模式树，再对建立的全局条件频繁模式树进行全局频 繁项目集挖掘。由于数据库信息压缩存放在f p - t r e e 的各路径上，因而采用传送条件模式基 或条件频繁模式树建立全局频繁模式树的策略可有效地降低网络通讯量，提高全局频繁项目 集的挖掘效率。 2 ) 基于f p - t r e e 的全局频繁项目集更新 基于f p - t r e e 的全局频繁项目集更新主要考虑以下两种情况： ( 1 ) 各局部数据库不变，而最小支持度阈值发生改变； ( 2 ) 最小支持度闽值不变，某些局部数据库的记录增加。 本文对上述2 种情况下的全局频繁项目集更新分别进行讨论。 对第( 1 ) 种情况，当最小支持度闽值变小时，若有新增的频繁项目出现，则首先通过 一遍扫描各局部数据库对各局部f p - t r e e 进行修改，然后对新增的频繁项目建立相应的全局 条件频繁模式树并进行全局频繁项目集挖掘。 对第( 2 ) 种情况，本文引入强频繁项目集的概念，建立新增局部数据库的局部f p t r e e 并挖掘出相应的局部频繁项目集，调整原局部数据库对应的局部f p t r e e ；利用原各局部 f p t r e e 、新增局部数据库对应的局部f p - t r e e 及已挖掘出的全局频繁项目集，采用挖掘出各 站点上的强频繁项目集来得到全局频繁项目集。 3 ) 基于f p - t r e e 的全局昂大频繁项目集挖掘 最大频繁项目集的任何非空子集均为频繁项目集，对含有较长频繁模式的情况，通过挖 掘最大频繁项目集来减少频繁项目集的数目。本文在f p - t r e e 结构中增加指向父结点的指针， 查堕查堂苎主兰垡丝苎 确保可从局部f p - t r e e 的相应路径中快速得到任一项目集的频度。设计的全局最大频繁项目 集挖掘算法首先挖掘出各局部最大频繁项目集；然后采用自顶向下的搜索策略挖掘出全局最 大频繁项目集。 4 ) 基于f p - t r e e 的全局最大频繁项目集更新 类似于基于f p t r e e 的全局频繁项目集更新，基于f p - t r e e 的全局最大频繁项目集更新主 要考虑以下两种情况： ( 1 ) 各局部数据库不变，而壤小支持度阀值发生改变： ( 2 ) 最小支持度阈值不变，某些局部数据库的记录增加。 本文对上述2 种情况下的全局最大频繁项目集更新分别进行讨论。 对第( 1 ) 种情况，当最小支持度阈值变小时，若有新增的频繁项目出现，则首先通过 一遍扫描各局部数据库并对各局部f p t r e e 进行修改，然后对新增的频繁项目建立相应的全 局条件频繁模式树并进行全局最大频繁项目集挖掘。 对第( 2 ) 种情况，建立新增局部数据库的局部f p 。t r e e 并挖掘出相应的局部昂大频繁项 目集，调整原局部数据库对应的局部f p - t r e e ：利用原备局部f p - t r e e 、新增局部数据库对应 的局部f p t r e e 、已挖掘出的全局最大频繁项目集及各站点上新增局部数据库的局部最大频 繁项目集来得到全局最大频繁项目集。 5 ) 基于条件概念格的全局最大频繁项目集挖掘 概念格作为数据挖掘的理论基础之一，其技术和应用研究倍受关注，研究者己将概念格 用于关联规则和分类规则挖掘，但研究工作均局限于单机。虽然可通过概念格的台并操作来 挖掘全局最大频繁项目集，但挖掘的效率不高。 我们在研究全局最大频繁项目集挖掘的过程中，引入了条件概念格的概念，将全局最大 频繁项目集的挖掘任务转化为对各个条件概念格进行挖掘，并证明通过各个条件概念格的挖 掘可获得所有的全局最大频繁项目集。由于条件概念格的建立和挖掘均可并行实现，因而在 减少内存压力的同时，可有效提高全局最大频繁项目集挖掘效率。 6 ) 基于条件概念格的全局最大频繁项目集更新 全局最大频繁项目集的更新主要分为两种情况： ( 1 ) 各局部数据库不变，而最小支持度闽值发生改变： ( 2 ) 最小支持度阂值不变，某些局部数据库的记录增加。 第( 1 ) 种情况是一种比较简单的情况，本文仅对第( 2 ) 种情况进行讨论。利用全局屉 大频繁项目集可由各个条件概念格生成得到这一性质更新任务被分为原条件概念格的调箍 和新增频繁项目的条件概念格建立或调整。 3 2 数据库相似性度量技术 通过挖掘各局部数据库的最大频繁项目集，然后通过挖掘得到的最大频繁项目集来度量 局部数据库间的相 娃性或相关性，可降低网络通讯量，提高效率和度量准确度。但其缺点是 未考虑局部数据库中属性的重要性。 本文引入最大加权频繁项目集的概念，通过挖掘出的最大加权频繁项目集来度量局部数 据库间的相似性或相关性使得在减低网络通讯量的同时，可克服已有算法存在的不足。 4 苎二重竖垄一一 1 3 ，3 分布环境下的属性约简求解技术 属性约简是基于粗糙集的分类规则挖掘的首要任务。传统的属性约简主要针对单机，且 已有属性约简算法是基于主存的，有些算法还不完备，且存在可扩展性差等缺点。 本文引入了分类关联规则、相容性分类关联规则和分类关联规则集核等概念，提出了基 于关联规则的属性约简框架，该框架主要通过挖掘置信度为1 的某类关联规则集合，并通过 该类关联规则集合所确定的对象来构造属性约简的等价模型。 对给定的单决策表，依次分析了下近似求解、正区域求解及属性约简求解的等价模型， 并提出了通过属性格求解分类关联规则集核的方法。 在得到单决策表的属性约简模型后，提出了分布多决策表环境下的属性约简的一些基本 概念，并将单决策表的属性约简模型推广到分布环境。 1 4 论文研究工作的主要成果 论文研究工作的主要成果反映在以下方面： ( 1 ) 改进了传统的全局频繁项目集挖掘方法，提出了一种新的基于f p - w e e 的全局频繁 项目集挖掘模型。在此模型中，f p t r e e 可压缩存储各局部数据库，传送条件模式 基或条件频繁模式树可减少网络通讯量，因而为分布多库环境下的全局频繁项目集 挖掘提供了一种新的框架。 ( 2 ) 提出了祭件概念格的概念，拓展了概念格的应用，提出了一种新的基于条什概念 格的全局最大频繁项目集挖掘模型。在此模型中，通过在各站点并行建立的条件概 念格可获得所有的全局最大频繁项目集，为概念格在分布多库环境下的数据挖掘技 术研究提供了新的思路，也为数据挖掘的模式可视化表示提供新的途径。 ( 3 ) 提出了基于f p t e 的全局最大频繁项目集挖掘与更新模型，为在分布多库环境下 含有较长模式的频繁项目集挖掘与更新提供了新的方法。 ( 4 ) 提出了基于f p - t r e e 的全局频繁项目集更新方法。在该方法中，利用已挖掘的全局 频繁项目集和已建立的f p t l e e 可有效提高全局频繁项目集的更新效率。 ( 5 ) 提出了基于条件概念格的全局最大频繁项目集更新方法。在该方法中，利用已建 立的条件概念格可有效提高全局最大频繁项目集的更新效率。 ( 6 ) 提出基于最大加权频繁项目集的数据库相似性或相关性判别模型。在该模型中， 不仅考虑项目集的频度还考虑项目集中各项目的重要性，确保挖掘出包含重要项目 的项目集，从而提高了数据库相似性判别准确度。 ( 7 ) 提出了一种基于关联规则的单决策表属性约简模型，为单决策表的属性约简提供 了一种新的框架。该模型可借用高效的关联规则挖掘算法，算法的可扩展性好，可 用于大型决策表的属性约简，有效拓展了粗糙集的应用范围。 ( 8 ) 提出了分布多决策表环境下的属性约简框架，将单机环境下的属性约简推广到分 布多决策表环境，为分布环境下的粗糙集应用研究提供新的途径，也使粗糙集在分 布环境下的应用成为可能。 1 5 论文的组织和结构 论文主要由三部分组成：第一部分是分布多库环境下的全局频繁项目集及全局最大频繁 项目集挖掘与更新技术研究，包括第二章、第三章及第四章，这部分是论文的重点；第二部 查壹盔堂堡主兰垡丝塞 一一一 分是数据库相似性度量技术研究，即论文的第五章：第三部分是分布环境下的属性约简求解 技术研究，即论文的第六章。各章节摘要如下： 第一章作为论文的概述，从分布多库环境下进行挖掘的应用需求及国内发展现状等方面 来分析研究课题的来源和背景，介绍现有的解决方案、发展趋势和仍存在的不足；描述论文 的研究方案，在给出论文工作的研究内容和方法后，简要地介绍研究成果和论文结构。 第二章为基于f p 4 r e e 的全局频繁项目集挖掘与更新技术研究，介绍相应的研究现状、 关键技术及有关关联规则、频繁项目集、f p - t r e e 等概念。在深入分析现有全局频繁项目集 挖掘算法存在的不足后，对如何利用f p t r e e 进行全局频繁项目集挖掘进行了原理性分析， 从而建立新的基于f p t r e e 的全局频繁项目集挖掘模型。在此基础上，对各局部数据库记录 发生改变或塌小支持度阈值发生改变情况下的全局频繁项目集更新进行了理论分析，提出了 强频繁项目集和f p t r e e 动态调整等概念和方法，以实现对全局频繁项目集的动态更新。 第三章讨论基于f p - t r e e 的全局最大频繁项目集挖掘与更新技术研究，首先介绍相关概 念和研究现状，提出了基于f p - t r e e 的全局最大频繁项目集挖掘模型，该模型旨在避免挖掘 出大量的全局频繁项目集，应用丁含有较氏频繁模式的情况。此外，还对各局部数据库记录 发生改变或最小支持度闽值发生改变情况下的全局最大频繁项目集更新进行了理论分析，提 出了快速实现全局最大频繁项目集的动态更新算法。 第四章讨论基于条件概念格的全局最大频繁项目集挖掘与更新技术研究，首先介绍概念 格的基本概念和研究状况，提出了条件概念格的概念及相关性质。建立一种新的基于条件概 念格的全局最大频繁项目集挖掘模型。在此模型中，将全局最大频繁项目集的挖掘划分为各 个条件概念格上全局最大频繁项目集的挖掘。在此基础上，对各局部数据库记录发生改变情 况下的全局最大频繁项目集更新进行了理论分析，提出了条件概念格的修改策略，以实现对 全局最大频繁项目集的动态更新。 第五章研究了数据库相似性度量方法，对基于最大频繁项目集的数据库相似性度量方法 进行了改进，建立了一种基于最大加权频繁项目集的数据库相似性度角模型。在该模型中， 综合考虑项目集的频度和各项目的重要性，提出晟大加权频繁项目集挖掘算法。以此为基础， 提出基于最大加权频繁项目集的数据库相似性度量模型，可确保提高数据库相似性度量的准 确性。 第六章为分布环境下的属性约简技术研究，首先介绍粗糙集的基本概念、属性约简的现 状及关键技术，提出了分类关联规则、相容性关联规则、分类关联规则集核及属性格等概念， 建立了单决策表的下近似、i x n 域及属性约简求解的等价模型，给出了求解最小属性约简算 法。进而，将单决策表的属性约简模型推广到分布多决策表环境，提出了基于关联规则的多 决策表属性约简模型，并给出了分布多决策表环境下的最小属性约简算法。 第七章是对整个论文研究的总结，综述我们在分布多库环境下的挖掘研究领域取得的成 果，以及在其他相关领域所做的研究工作，并指出现有研究工作的局限性和有待提高和改进 的方面，阐述我们正在进行或将要深入进行研究工作的要点。 6 苎三主苎王! ! ：壁! 塑垒旦塑茎堡! 叁垫塑兰里堑苎鲨一 第二章基于f p - t r e e 的全局频繁项目集挖掘与更新算法 本章将要讨论的全局频繁项目集挖掘与更新技术是基于f p t r e e 的方法，该方法与传统 方法f 如：c h e u n gdw 提出的f d m 算法) 的不同点在于：传统方法大都采用传送全局频 繁候选项目集进行全局频繁项目集的挖掘，其算法框架是a p r i o r i l i k e ，尽管可通过一些修剪 策略来减少全局候选项目集的数目，相应提高算法的效率，但不能从本质上减d , n 络通讯量。 基于f p - t r e e 的方法采用在各站点上建立局部频繁模式树，压缩存储局部数据库。并通过传 送条件频繁模式树或条件模式基建立全局条件频繁模式树，对建立的各个全局条件频繁模式 树进行挖掘来得到全局频繁项目集，可有效减少网络通讯量，提高全局频繁项目集挖掘效率。 本章首先提出了基于f p t r e e 的快速挖掘全局频繁项目集算法f a m g f i ( f s s ta l g o r i t h m f o r m 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 s ) ；在此基础上，提出了基于f p - t r e e 的更新全局频繁项目 集算法a u g f i ( a l g o r i t h m f o r u p d a t i n g g l o b a l l y f r e q u e n t i t e m s e t s ) ，考虑最小支持度闽值改变 而局部数据库记录不变情况下的全局频繁项目集更新：提出了基于f p t r e e 的快速更新全局 频繁项目集算法f a u g f i ( f a s ta l g o r i t h mf o ru p d a t i n gg l o b a l l yf r e q u e n tl t e m s e t s ) ，考虑最小 支持度阈值不变而部分局部数据库记录增加情况一f 的全局频繁项目集更新。 2 1 相关研究及关键技术问题 前已述及，数据挖掘是一个从数据集中析取潜在有用的、先前未知的和最终可理解的知 识的过程。自a g r a w a lr 提出布尔型关联规则问题及相应的a p r i o r i 算法以来1 2 , 3 1 ，数据挖掘 领域的研究者在关联规则挖掘上做了大量的工作【4 ”】，其中，快速挖掘频繁项目集成为研究 的重点，也是多种数据挖掘应用中的技术关键。但这些算法大多局限于单机环境，有关分布 多库环境下的数据挖掘技术研究工作的报道尚不多见。 网络技术和数据库技术的发展带动了企事业单位的信息化建设，日积月累，使得其数据 库和数据仓库中存储了大量的数据，且很多大型数据库是分布架构的，如超市、连锁店等。 如何从分布多库环境下的数据库中挖掘用户有用的知识是一个具有挑战性的研究课题。同 时，单个数据库也可按照某种策略划分为分布在不同站点上的各局部数据库，因而分布多库 环境下的数据挖掘算法的研究方法和策略对单个数据库的并行或分布挖掘研究也具有重要 的指导作用。为此，分布多库环境下的全局频繁项目集挖掘算法研究正逐