《基于FP树的最大频繁模式挖掘算法研究》由会员分享，可在线阅读，更多相关《基于FP树的最大频繁模式挖掘算法研究（75页珍藏版）》请在金锄头文库上搜索。
1、广西大学硕士学位论文基于FP-树的最大频繁模式挖掘算法研究姓名：冯志新申请学位级别：硕士专业：控制理论与控制工程指导教师：钟诚2003.5.1基于F P - 树的最大频繁模式挖掘算法研究摘要f 从大型数据库中挖掘关联规则是数据挖掘领域中非常重要的研、究课题。其中，最大频繁模式挖掘问题在关联规则挖掘任务中扮演着重要的角色，具有广泛的应用前景。F P - 树是算法F P - g r o w t h 中提出的新的数据结构。借助于F 卜树结构，算法F P g r o Y r t h 采用不同于A p rio ri 系列算法的候选产生测试方法而采取模式增长方法挖掘频繁模式，取得了很好效果。、j 、， 本
2、文主要在以下几个方面对基于F P 一树的最大频繁模式挖掘问题进行研究：第一是提出了基于F P - 树的最大频繁模式挖掘算法F P - M a x 。在该算法中，我们首先介绍了F P - 树的定义和构造过程，并分析了基于F P - 树进行挖掘的可行性和完整性；然后我们提出基于F P - 树的最大频繁模式挖掘算法F P M a x 。试验表明算法F P - M a x 在挖掘密集型、频繁模式较长的大数据集时是有效的。第二是提出F P - 树驻留磁盘的最大频繁模式挖掘算法F P - M a x - Djs k 。算法F P _ M a x 运行的前提是构造的F P - 树能够驻留内存，但是当事务数据
3、库，船很大或者设置的最小支持度阀值r a i n _ s u p 很小时，那么构造驻留内存的F P 一树将是不现实的。为此，我们首先将原事务数据库T D B 划分为一系列投影数据库，然后将每个投影数据库构造为能够装入内存的条件F P 一树，最后基于这些条件F P _ 树挖掘最大频繁模式。第三是研究探讨了基于F P 一树的最大频繁模式并行挖掘问题。借助于多局部频繁模式树和并行投影技术，本文提出了两种基于共享内存计算模型的最大频繁模式并行挖掘算法根据理论分析，这两种并行算法在采用了新的数、据结构和简单的动态负载平衡技术后，可以实现各处理器独立异步运行、较小的I 0 开销以及良好的负载平衡。关键字数
4、据挖掘关联规则最大频繁模式频繁模式树共享内致并行挖掘I IS T U D YO NM A X I M A LF R E Q U E N TP A T T E R NM I N I N GA L G o R I T H M SB A S E Do NF P T R E EA B S T R A C TD i s c o v e r yo fa s s o c i a t i o nr u l e sf r o ml a r g ed a t a b a s e sh a sb e e nc o n s i d e r e da sav e r yi m p o r t a n tt a s ki
5、 nd a t am i n i n ga r e a ，a n dt h ep r o b l e mo fm i n i n gm a x i m a lf r e q u e n tp a t t e r np l a y sa ni m p o r t a n tr o l ei nm a n ya s s o c i a t i o nr u l e sm i n i n gt a s k sa n dh a sw i d ea p p l i c a t i o n sF P t r e ei san o v e ld a t as t r u c t u r ep r e s e
6、 n t e di na l g o r i t h mF P g r o w t hB yc o n s t r u c t i n gF P - t r e e ，a l g o r i t h mF P g r o w t hc a nd i s c o v e rf r e q u e n tp a t t e r nb yp a t t e r n g r o w t hm e t h o di n s t e a do fc a n d i d a t e g e n e r a t i o n t e s tm e t h o do ft h eA p r i o r ia l
7、g o r i t h m sT h i st h e s i ss t u d i e sm o s t l yt h ep r o b l e mo fm i n i n gm a x i m a lf r e q u e n tp a t t e r nb a s e do nF P t r e e F i r s t l y , w ep r e s e n tt h ea l g o r i t h mF P M a xf o rm i n i n gm a x i m a lf r e q u e n tp a t t e r nb a s e do nF P t r e e W
8、ei n t r o d u c et h ed e f i n i t i o na n dc o n s t r u c t i o no fF P t r e ea n da n a l y z et h ef e a s i b i l i t ya n dc o m p l e t e n e s so fF P - t r e e T h e n ，w ep r o p o s et h ea l g o r i t h mf o rm i n i n gm a x i m a lf r e q u e n tp a t t e r nF P M a x A tl a s t ，o
9、 u re x p e r i m e n t a lr e s u l ts h o w st h a tt h ea l g o r i t h mF P M a xi se f f i c i e n tw h e nm i n i n gt h el o n gf r e q u e n tp a t t e r n si nl a r g ed e n s ed a t a s e t s S e c o n d l y , w ep r e s e n ta na l g o r i t h mF P - M a x - D i s kf o rm i n i n gm a x i
10、 m a lf r e q u e n tp a t t e r nb a s e do nd i s k b a s e dU lF P t r e e T h ep r o p o s e dF P M a xi se s s e n t i a l l yam a i nm e m o r y 。b a s e dm a x i m a lf r e q u e n tp a t t e r nm i n i n gm e t h o d H o w e v e r ，w h e nt h et r a n s a c t i o nd a t a b a s eT D Bi sl a
11、r g e ，o rw h e nt h em i n i m u ms u p p o r tt h r e s h o l dr a i n _ s u pi sq u i t el o w ，i ti su n r e a l i s t i ct oa s s u m et h a tt h eF P t r e eo fad a t a b a s ec a nf i t si nm a i nm e m o r y T h e r e f o r e ，w ep a r t i t i o nt h eo r i g i n a lt r a n s a c t i o nd a
12、t a b a s eT D Bi n t oas e r i a lo f p r o j e c t i o nd a t a b a s e s ，c o n s t r u c tt h ec o n d i t i o nF P t r e ew h i c hc a nf i ti nm a i nm e m o r yb a s e do np r o j e c t i o nd a t a b a s e sa n dm i n em a x i m a lf r e q u e n tp a t t e r n sf r o mt h ec o n d i t i o nF
13、 P - t r e e F i n a l l y ，w es t u d yt h ep r o b l e mo fp a r a l l e lm i n i n gm a x i m a lf r e q u e n tp a t t e r nb a s e do nF P t r e e B a s e do nM u l t i p l eL o c a lF r e q u e n tP a t t e r nT r e e ( M L F P T ) a n dp a r a l l e lp r o j e c t i o n ，w ed e v e l o pt w o
14、a l g o r i t h m sf o rp a r a l l e lm i n i n gm a x i m a lf r e q u e n tp a t t e r nf r o mF P - t r e eo ns h a r e d m e m o r ys y s t e m sA c c o r d i n gt ot h et h e o r e t i c a la n a l y s i s ，t h et w op a r a l l e la l g o r i t h m sc a na c h i e v et h ep u r p o s eo fe a
15、c hp r o c e s s o rr u n n i n gi n d e p e n d e n t l y ，l e s sc o s to fd i s kI 0 ，a n dg o o dl o a db a l a n c i n gw h e nc a r r y i n go u tt h en e wd a t as t r u c t u r ea n ds i m p l ed y n a m i cl o a db a l a n c i n gK E YW O R D S ：d a t am i n i n g ；a s s o c i a t i o nr u
16、l e ；m a x i m a lf r e q u e n tp a t t e r n ；F P _ - t r e e ；s h a r e m e m o r y ；p a r a l l e lm i n i n g广西大学硕士学位论文基于F P - 树的最大频繁模式挖掘算法研究1 1 引言第一章绪论随着数据瘁技术以及相应的硬件技术、数据采集设备的快速发展，使得收集存储海量数据信息成为可能。企业数据库的数据量正以前所未有的速度增长。由于这些数据十分繁杂，要从中发现有价值的信息或知识，达到为决策服务的目的，就成为一项非常艰巨的任务。数据的丰富带来了对强有力的数据分析工具的需求，大量的数据被描述为“数据丰富，但信息贫乏”1 。没有强有力的分析工具，理解这些海量的、类型各异的数据已经远远超出了人的能力。数据挖掘方法的提出，让人们最终有能力认识到数据的真正价值，即蕴藏在数据中的信息和知识。数据挖掘( D a t aM i n i n g ) 指的是从大型数据库或数据仓库中提取人们感兴趣的知识，这
