《一种基于FPtree的最大频繁项目集挖掘算法》由会员分享，可在线阅读，更多相关《一种基于FPtree的最大频繁项目集挖掘算法（3页珍藏版）》请在金锄头文库上搜索。
1、计算机科学2 0 0 2 V 0 1 2 9 N 9 8一种基于F P t r e e 的最大频繁项目集挖掘算法A nA l g o r i t h mB a s e d0 nF r e q u e n tP a t t e r nT r e ef o rM i n i n gM a x i m u mF r e q u e n th e m s e t s朱玉全孙志挥宋余庆陈耿 ( 东南大学计算机科学与工程系南京2 1 0 0 9 6 )A b s t r a c tM i n i n gm a x i m u mf r e q u e n ti t e m s e t si Sak e y
2、p r o b l e mi ni m p o r t a n td a t am i n i n ga p p l i c a t i o n ，s u c ha st h ed i s c o v e r yo fa s s o c i a t i o nr u l e s ，s t r o n gr u l e s ，e p i s o d e s ，a n dm i n i m a lk e y s M o s to f t h ep r e v i o u ss t u d i e sa d o p ta nA p r i o r i l i k ec a n d i d a t e
3、s e tg e n e r a t i o n a n d t e s ta p p r o a c h H o w e v e r ， c a n d i d a t es e tg e n e r a t i o ni Ss t i l lc o s t l y ，e s p e c i a l l yw h e nt h e r ee x i s tp r o l i f i cp a t t e r n sa n d o rl o n g p a t t e r n s I nt h i sp a p e r ，an e wa l g o r i t h mf o rm i n i
4、n gm a x i m u mf r e q u e n ti t e m s e t si sp r o p o s e d ， w h i c hi Sb a s e do nan o v e lf r e q u e n tp a t t e r nt r e e ( F P t r e e ) s t r u c t u r et h a ti Sa ne x t e n d e dp r e f i x t r e es t r u c t u r ef o rs t o r i n gc o m p r e s s e da n dc r u c i a li n f o r m
5、 a t i o na b o u tf r e q u e n tp a t t e r n s K e y w o r d sD a t am i n i n g ，M a x i m u mf r e q u e n ti t e m s e t s ，F P t r e e1引言关联规则是由A g r a w a l 等人首先提出的个 重要的K D D 研究课题 1 3 ，它反映了大量数据中项目集之间有趣的关联或相关联系。发现频繁项目集是关联规则挖掘应用中的关键技术和步骤。近年来，在频繁项目集的算法研究中先后出现了A p r i o r i 、A I S 引、S E T M 引、P A
6、 R T I T I O N 引、M L T 2 L 1 7 等数据挖掘算法，在众多算法中以A g r a w a l 等人提出的A p r i o r i 算法 1 3 最为著名，其后的数据频繁项目集， 因而发现最大频繁项目集对数据挖掘具有重大意义。目前已经提出的可用于发现最大频繁项目集的算法有M a x M i n e r c 引、P i n c e r S e a r c h c 9 3 及D M F I c l 0 等。M a x M i n e r 突破了传统的自底向上的搜索策略，尽可能早地对项目集进行修剪，其缺陷如下： 未利用自顶向下的信息进行修剪；未对M F C S 进 行适当排
7、序，产生了多余的最大频繁候选项目集。P i n c e r S e a r c h 采用了自底向上和自顶向下的双向 搜索策略，但其第k 次的M F C S 是由k 一1 次的M F C S 中的非频繁项挖掘算法大多数建立在A p r i o r i 算法基础上，或进行改进，或衍生变种，诸如A p r i o r i T i d 、A p r i o r i H y b i r d 2 4 3 等。在如上诸多算法 中，计算项目集的支持数是发现频繁项目集中最耗时的工作，占据整个计算量的大部分，因此，降低候* ) 本文得到国家自然科学基金项目( 7 9 9 7 0 0 9 2 ) 的资助选项目集的数
8、量是减小开销的最好手段。由于最大频繁项目集( 见2 1 节) 中已经隐含了所有频繁项目 集，所以可把发现频繁项目集的问题转化为发现最大频繁项目集的问题。另外，某些数据挖掘应用仅需 发现最大频繁项目集，而不必发现所有的项目集去掉一个元素来生成的，产生了过多的无用候选项目集，对海量数据库来讲，算法P i n c e r S e a r c h 将陷入N P 难度的陷阱。D M F I 有效地把自底向上和自顶向下的搜索策略进行了合并，该算法为海量数据库中 发现最大频繁项目集和仅需要发现最大频繁项目集的数据挖掘应用提供了一种有效而快速的算法，但 该算法还有如下不足：算法必须耗费大量时间处 理规模较大的
9、最大频繁候选项目集M F C S ；算法 必须多次重复扫描数据库D ，计算M F C S 中各项目 集的支持数。我们在企业风险管理数据挖掘技术研 究中发现，造成该现象的主要原因是整个挖掘过程 必须一步一步地产生规模较大的最大频繁候选项目 集M F C S 。为此，本文提出了一种快速的基于F P t r e e E t 1 的最大频繁项目集挖掘算法D M I A ，该算法 只需扫描数据库D 一次，从而大大提高了算法的执行效率。2 问题描述2 1 频繁项目集和最大频繁项目集设I = ( i 。，i 。，i 。 是m 个不同项目的集合。给S y s t e mB a s e do nw e bU s
10、 a g eM i n i n g h t t p ：f a c w e b c s d e p a u l e d u r e s e a r c h t e c h r e p o n s T R 0 1 0 0 4 p d f ，2 0 0 1 35S D e r t u $ E 。S t e i nL 。AH y p e r l i n k B a s e dR e c o m m e n d e rS y s t e mW r i t t e ni nS q u e a l W o r k s h o po nW e bI n f o r m a t i o na n dD a t
11、aM a n a g e m e n t 1 9 9 8 h t t p ：W W W m i l l s e d u A C A D - I N F O M C S S P E R T U S w i d m 9 8 p d f6H a nJ F uY E x p l o r a t i o no fT h eP o w e ro fA t t r i b u t e 一0 r i e n t e dI n d u c t i o nD a t aM i n i n g A d v a n c e si nK n o w l e d g eD i s c o v e r ya n dD a
12、t aM i n i n g 。A A A l l M I TP r e s s ，1 9 9 6 ：3 9 9 4 Z I7H a nJ C a iY ，C e r c o n eN 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 s ：A nA t t r i b u t e O r i e n t e dA p p r o a c h I n ：P r o c o ft h el8 t hV L D BC o n f 1 9 9 2 5 4 7 5 5 98 3 定事务数据库D ，对于项目集x I 。X 在D 中的支 持数是指D
13、中包含x 的事务数，记为X c o u n t 。X 在D 中的支持度是指D 中包含x 事务的百分比，记为X s u p 。如果X 的支持度不小于用户给定的最小支持度阈值S ，则称X 为频繁项目集，项目集中项目 的个数叫做项目集的维数或长度，频繁1 一项目集简称频繁项目。定义1对于项目集X 曼I ，如果X s u p s ，并且对于任意Y 3 X ，均有Y s u p s ，则称X 为最大频繁项目集。显然，任何频繁项目集都是最大频繁项目集的子集，所以发现所有频繁项目集的问题可以转化为 发现所有最大频繁项目集的问题。2 2 频繁模式树F P t r e e 在F P t r e e 中，每个节点
14、有四个域组成：节点名称n o d e n a m e 、节点计数n o d e c o u n t 、节点链n o d e l i n k 及父节点指针n o d e p a r e n t 。另外，为方便树遍 历，创建一个频繁项目头表H t a b l e ，它由两个域组成：项目名称i t e m n a m e 、项目链头i t e m h e a d ，其中 项目链头指向F P t r e e 中与之名称相同的第一节点。频繁模式树F P t r e e 的构造算法如下： ( 1 ) 扫描D 一次，产生频繁项目集合F 及其支持数。按其支持数降序排列F ，生成频繁项目列表L F ；( 2 )
15、 创建F P t r e e 的根节点，标号为“n u l l ”。对于 D 中的每个事务T r a n s 作如下处理：按L r 中的次 序排列T r a n s 中的频繁项目，设排列后的结果为 p j P ，其中P 是第一个项目，而P 是剩余项目的列表；调用i n s e r t t r e e ( E p l P ，T ) ；如果P 非空，递归调用i n s e r t t r e e ( P ，N ) 。过程i n s e r t t r e e ( p1 P ，T ) 的执行情况如下：如果T 有子女N 使得N n o d e n a m e = P n o d e n a m e ，
16、则N 的计数增加1 ；否则创建一个新节点N ，将其名称n o d e n a m e 、计数n o d e - c o u n t 分别设置为P 、1 ，由父节点指针n o d e p a r e n t 链接到它的父节点T ，并通过节点链n o d e l i n k 将其链接到具有相同名称n o d e n a m e 的节点。5 挖掘最大频繁项目集算法D M I A性质1如果X 为最大频繁项目集，那么X 的任何子集都是频繁项目集，并且任何最大频繁项目集均为L r ( L F 见2 2 节) 的子集。性质2 设X = x ，X 2 ，一，x 。“ x 。 为菲频繁项目集，那么X i 一 x ，lX j X ，j i ) 均有可能成为频繁项目集。对于任何最大频繁候选项目集X
