（应用数学专业论文）基于单向fp树的最大频繁项集挖掘.pdf

河南大学研究生硕士学位论文第1 页 摘要 数据挖掘是一门新兴的交叉学科，涉及到数据库技术、机器学习、 统计学、模式识剔、神经网络、人工智能、数据可视化等多令领域。目 前它已成为数据库研究中最活跃、最令人兴奋的领域之一。 关联规则是数据挖掘研究中一个重要的研究课题，其主要的研究目 的是从大型数据库中发现属性间存在的隐藏的、有趣的关系。频繁项集 挖掘是关联规刚挖掘的第一步，也是影响总体性能最关键的一步，因此， 本文的研究重点放在了频繁项集挖掘上，研究内容主要包括以下几个部 分： 1 深入研究了两个频繁项集挖掘算法。一个是经典f p g r o w t h 算法， 它是基于f p 树的无候选项集产生算法，开辟了有效挖掘频繁模式的新 途径。另一个是范明提出的基于单向f p 树的频繁项集挖掘算法，该算 法在挖掘过程中不生成条件模式树。本文对比分析了f p 树和单向f p 树两种树结构，总结了f p g r o w t h 算法存在的问题，以及单向f p 树及其 算法的优势。 2 在第一部分研究的基础上，参考最大频繁项集挖掘算法f p m a x ， 设计了基于单向f p 树的最大频繁项集挖掘算法u n i df p m a x 。该算法 是一个深度优先算法。从算法分析和实验比较显示：对于密集型数据， u n i df p m a x 算法在时间和空间开销上均小于f p m a x 算法。 3 参考频繁闭项集挖掘算法c l o s e t ，设计了基于单向f p 树的频 繁闭项集挖掘算法u n i df p f c i 。该算法是个深度优先算法。经初步 分撰可知：u n i df p f c i 算法妁效率会优于c l o s e t 算法。 关键词：数据挖掘；关联规则：频繁项集；最大频繁项集；频繁闭项集； f p 树；单向f p 。树 第1 i 页河南大学研究生硕士学位论文 a b s tr a c t d a t am i n i n gi say o u n gm u l t i d i s c i p l i n a r yf i e l d ，d r a w i n gw o r kf r o m a r e a si n c l u d i n gd a t a b a s et e c h n o l o g y ，m a c h i n el e a r n i n g ，s t a t i s t i c s ，p a t t e r n r e c o g n i t i o n ，n e u r a ln e t w o r k s ，a r t i f i c i a li n t e l l i g e n c e ，a n dd a t av i s u a l i z a t i o n e t e n o w a d a y s ，i t i so n eo ft h em o s ta c t i v ea n de x c i t i n ga r e a so ft h e d a t a b a s er e s e a r c hc o m m u n i t y a s s o c i a t i o nr u l ei so n eo ft h ei m p o r t a n tr e s e a r c ha r e a si nd a t am i n i n g i t sg o a ti st od i s c o v e rp r e v i o u s l yu n k n o w n ，i n t e r e s t i n gr e l a t i o n s h i p sa m o n g a t t r i b u t e sf r o ml a r g ed a t a b a s e s t h ef i r s ts t e pf o rm i n i n ga s s o c i a t i o nr u l e si s m i n i n gf r e q u e n ti t e m s e tw h i c hi sa l s ot h ek e ys t e pc a ni n f l u e n c et h et o t a l m i n i n gp e r f o r m a n c e ，t h e r e f o r e 。i nt h i sp a p e rw ep u tt h ee m p h a s i so n m i n i n gf r e q u e n ti t e m s e t t h em a i nr e s e a r c hi sa sf o i i o w s ： 1 t h et w oa l g o r i t h m sf o rm i n i n gf r e q u e n ti t e m s e ta r et h o r o u g h l y s t u d i e d o n ei st h ec l a s s i c a la l g o r i t h m ，f p g r o w t h ，w h i c hl e a d st h ew a yt o m i n i n gf r e q u e n tp a t t e r n sw i t h o u tc a n d i d a t eg e n e r a t i o n a n o t h e ri st h e a l g o r i t h mp r o p o s e db y f a n m i n g f o r m i n i n gf r e q u e n t i t e m s e ti na u n i d i r e c t i o n a lf p t r e e ，w h i c hd o e s n t g e n e r a t ec o n d i t i o n a l f p t r e e si n m i n i n gp r o c e s s w ec o m p a r a t i v e l ya n a l y z et h es i m i l i a r i t i e sa n dd i f f e r e n c e s o ff p t r e ea n du n i d i r e c t i o n a lf p - t r e e s u m m a r i z et h e p r o b l e m s o n f p g r o w t ha n dt h ea d v a n t a g e si nf a nm i n 9 1 sa l g o r i t h m 2 b a s e do nf o r e g o i n gr e s e a r c ha n dc o m p a r e dw i t ht h ea l g o r i t h m f p m a x ，w ep r o p o s et h ea l g o r i t h mu n i d f p m a xf o rm i n i n gm a x i m a l f r e q u e n t i t e m s e ti nau n i d i r e c t i o n a lf p t r e e ，t h e u n i d f p m a x i sa d e p t h f i r s ts e a r c ha l g o r i t h m a l g o r i t h ma n a l y s i sa n de x p e r i m e n t ss h o wt h a t t h eu n i d f p - m a xc o n s u m e sl e s ss p a c ea n dt i m et h a nt h ef p - m a xf o rt h e d e n s ed a t a 3 。r e f e r r e dt ot h ea l g o r i t h mc l o s e t , t h ea l g o r i t h mu n i d _ f p f c ! i s d e s i g n e df o rm i n i n gf r e q u e n tc l o s e di t e m s e ti nau n i d i r e c t i o n a lf p t r e e ， w h i c hi sa d e p t h f i r s ts e a r c ha l g o r i t h m r o u g ha n a l y s i si n d i c a t et h a tt h e u h i df p f c ii sm o r ee f f i c i e n tt h a nt h ec l o s e tf o rt h ed e n s ed a t a k e y w o r d ：d a t am i n i n g ；a s s o c i a t i o nr u l e ；矗e q u e n ti t e m s e t ；m a x i m a i f r e q u e n ti t e m s e t ；f r e q u e n tc l o s e di t e m s e t ；f p - t r e e ；u n i d i r e c t i o n a lf p - t r e e 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位中请。本人郑重声明：所呈交酌学位论文是 本人在导师的指导- f 独, a z 成的，对所研究的浑题有新酌见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过酌研究成果，也不包括其他人为获得任何教育、科研机构的学位或证书而 段保存、汇编学位论文( 纸质文本和电子文本) 。 ( 涉及保密内容的学位论文在解密后适用本授权书) 学位获得者( 学位论文作者) 鍪名：塞晶墨 2 0d _ 7 年月腮目 学位论文指导教师釜名： 是项目的集合，d = t l ，t 2 ，如 为事务数据 库，其中每个事务t j ( j = 1 ，2 一，行) 包含的项集都是，的子集，即f ， “有一个唯一的标识符t i d 。 定义2 1 i t l l 数据库d 中包含项集( 或模式谢的事务数称项集工的支持 数，记为s u p c o u n t ( x ) 。项集x 的支持度，记做：s u p p o r t ( x ) ， 第1 4 页河南大学研究生硕士学位论文 s u p p o r t ( x ) 2s u p _ c o u n t ( x ) l d i 其中 d f 是数据库d 的事务数。 若s u p p o r t ( x ) 不小于用户指定的最小支持度阈值r a i ns u p ，则称爿为频繁 项集( 或频繁模式) ，否则称x 为非频繁项集( 或非频繁模式) 。 通常，最小支持度阈值r a i ns u p 由用户或领域专家指定，而最小支持度 计数r a i n c o u n t = m i ns u p “i d i 。 在事务数据库中挖掘频繁项集的问题可以描述为：给定事务数据库d 和 最小支持度阈值r a i ns u p ，找到所有的频繁项集( f i ) 。 2 1 2a p r io r i 类算法挖掘频繁项集存在的问题 a p r i o r i 算法利用候选项集和频繁项集的相互作用，得到了全部频繁项 集，并通过对候选项集的剪枝，大大地减少了候选项集的尺寸，获得了令人 满意的结果。 然而，当面对挖掘对象具有大量的频繁模式、长模式或者用户给定的最 小支持度的阈值较低时，a p r i o r i 算法仍然有可能因为如下两个方面的巨大 开销而面临困境【6 ”。 ( 1 ) 在处理大量的候选项集方面，如果算法得到了大量的频繁1 一项集， 那么，在产生候选2 项集时，会遇到大量候选2 项集难以处理的情况。例如： 假设算法得到的频繁1 项集的数量是1 0 4 ，则根据a p r i o r i 算法，会产生超过 l o7 个候选2 项集，由于候选2 项集没有剪枝，因此所有这些候选项集都需 要检验。此外，在面对频繁模式的尺寸较大黠，同样会产生大量的候选项集 需要检验。如，为了发现长度为1 0 0 的频繁模式，那么需要产生大约1 0 3 0 个候选项集。在内存等其它条件都为理想状态的情况下，这种候选产生检 测方法所决定的开销，无论采用什么实现技术都无法回避。所以，在有大量 候选项集产生的情况下，类a p r i o r i 的算法基本无法运行。 ( 2 ) a p r i o r i 算法采用的模式匹配方式，在检测大量的候选项集，特别是 在挖掘长模式时，对数据库的重复扫描非常冗长，大量的时间消耗在内存与 数据库中的数据交换上。 由于上述两点原因，可以发现a p r i o r i 类算法的瓶颈就是候选项集的产 生和检测过程。由于依赖于候选项集产生理论所开发的算法具有先天的弱 点，使得基于a p r i o r i 算法开发的应用一直没有实质性突破。针对a p r i o r i 算 法框架的缺陷，h a r t 等人提出的一种新的算法理论，这就是所谓的无候选项 集产生算法f p g r o w t h 。该算法基于f p 树，无须生成候选项集，显著地缩 小了搜索空间，有效地避免了产生“知识的组合爆炸”，挖掘效率明显提高。 河南大学研究生硕士学位论文第1 5 页 2 1 3f p 一树 定义2 l 2 【2 钉频繁模式树( f r e q u e n tp a t t e r n t r e e ) 简称为f p 树( f p - t r e e ) ，是 满足下列条件的一个树结构。 1 它由一个根( 值为n u l l ) 、项目前缀子树( 作为子女) 和一个频繁项目头表组 成： 2 每个项目前缀子树中的结点包括三个域：i t e m n a m e 、c o u n t 和n o d e l i n k ， 其中：i t e m n a m e 记录结点表示的项目；c o u n t 记录到达该结点的子路径 所表示的事务数；n o d e 1 i n k 用于连接树中同名结点，如果不存在同名结 点，则值为“n u l l ”； 3 频繁项目头表的表项包括一个频繁项目名域：i t e m n a m e 和一个指向树 中对应的第一个频繁项目结点的头指针：h e a d o f n o d e 1 i n k 。 对于包含在f p 树中某个结点上的项口，将会有一个从根结点到达口的路 径，该路径中不包含口所在结点的部分路径称为口的前缀子路径( p r e f i x s u b p a t h ) ，秣为该路径的后缀。在一个f p 一树中，有可能有多个包含口的结点 存在，它们从频繁项头表中的硼出发，通过项头表中的h e a do fn o d e 1 i n k 和项前缀子树中的n o d el i n k 连接在一起。f p 树中每个包含口的结点可以形 成口的个不同的前缀子路径，所有的这些路径组成口的条件模式基 ( c o n d i t i o n a lp a t t e r nb a s e ) 。用口的条件模式基所构建的f p 树称为o l 的条件模式 树( c o n d i t i o n a lf p t r e e ) 。 一、f p 一树构造算法 算法2 1 。l ：构造f p 樾 输入：事务数据库d 和最小支持度阈值m i n _ s u p 。 输出：d 所对应的f p - 树。 方法：f p 树是按以下步骤构造的： 1 扫描事务库d ，获得d 中所包含钓全部频繁项，f 。，及它 f 3 各自的支持度。 对，l 中的频繁项按其支持度降序排序得到。 2 创建f p 树的根结点丁，以“n u l l ”标记。再次扫描事务库。对于口中每个 事务t r a n s ，将其中的频繁项选出并按l 中的次序排序。设排序后的频繁 项表为p l p 】，其中p 是第一个频繁项，而p 是剩余的频繁项。调用 i n s e r t _ t r e e ( p 尸】，乃。i n s e r t t r e e ( 陋i p 】，d 过程执行情况如下：如果哺 子女使得n i t e mn a m e = p i t e mn a m e ，则的计数增加1 ；否则创建一个 新结点，将其计数设置为1 ，链接到它的父结点死并且通过结点链结 构将其链接到具有相同i t e mn a m e 的结点。如果p 非空，递归地调用 i n s e r tt r e e ( p ， n 。 第1 6 页河南大学研究生硕士学位论文 f p 树是一个高度压缩的结构，它存储了用于挖掘频繁项集的全部信息。 f p 一树所占用的内存空间与树的深度和宽度成比例，树的深度一般是单个事 务中所含项目数量的最大值；树的宽度是平均每层所含项目的数量。由于在 事务处理中通常会存在着大量的共享频繁项，所以树的大小通常比源数据库 小很多。频繁项集中的项以支持度降序排列，支持度越高的项与f p 树的根 越近，因此有更多的机会共享结点。这进一步保证了f p 一树的高度压缩。 二、相关性质和定理【”】 性质2 1 1 ( 结点链性质) 对于任何频繁项目a f ，从f p ，树的项头表对应a f 项目的结点链( h e a d o f n o d e l i n k ) 开始，通过遍历a f 的结点链( n o d e l i n k ) 可以挖 掘出所有包含a ，的频繁模式。 性质2 1 2 ( 前缀路径性质) 为了计算以a i 为后缀的频繁模式，仅仅需要在 f p 一树中计算a 黯点的前缀路径，并且前缀路径中每个结点的频繁计数等于a f 结点的频繁计数。 引理2 1 1 给定事务数据库d 和支持度阂值m i ns u p ，通过事务数据库d 的f p - 树可以推导出每个频繁项集对应的支持度。 引理2 1 2 ( 分段增长) 设o t 为事务数据库d 中的一个项集，口是口的条件模 式基，而腥b 中的一个项集，那么在d 中口u 的支持度等于b 中卢的支持度。 推论2 1 1 ( 模式增长) 设项目口为事务数据d 中的一个项集，占是d 的条件 模式基，而口是占中的一个项集，那么g u 口为频繁项集的充分必要条件是鼻 也为频繁项集。 引理2 1 3 ( 单路径频繁项集产生) 如果f p 树孢含一条单路径p ，那么z 包 含的所有频繁项集的集合可以通过枚举路径p 中结点的所有可能组合得到， 其支持度计数为组合中结点的支持度计数的最小值。 根据f p 树的性质以及相关的引理和推论可以得到下面的频繁项集挖掘 算法。 2 1 4f p - g r o w t h 算法 算法2 1 2 ( s p g r o w t h ) 2 5 】：频繁模式增长 输入：由算法2 1 1 得到的f p 一树和最小支持度阈值r a i n _ s u p 。 输出：全部频繁项集的集合。 方法：调用f p g r o w t h ( f p - 树，n u l l ) 。 p r o c e d u r ef p g r o w t h ( t r e e ， ( 1 ) i ft r e e 含单个路径p 河南大学研究生硕士学位论文第1 7 页 ( 2 ) t h e nf o r 路径p 中结点的每个组合( 记作历d o ( 3 )产生频繁项集u 口，其支持度s u p p o r t = f l 中结点的最小支持度； ( 4 ) e l s ef o rt r e e 中每一个结点a i ( 从项头表的最后项开始) a o ( 5 )产生一个频繁项集伊a i u 口，其支持度s u p p o r t = a t s u p p o r t ； ( 6 )构造的条件模式基，然后构造的条件模式树t r e e p ； ( 7 ) i ft r e e f ：f 乃 ( 8 ) t h e n 调用f p g r o w t h ( t r e e p ，历 算法f p g r o w t h 采用最小项( 支持度最小) 优先的模式增长方式，将挖掘 长频繁模式的问题转换成递归挖掘一些短的频繁模式，然后连接后缀，进而 在挖掘过程中不产生候选项集。 2 1 5f p g r o w t h 算法的贡献 f p g r o w t h 算法通过如下三方面的改进与创新，彻底地脱离了必须产生 候选项集的传统方式，开辟了关联规则挖掘的新思路。 ( 1 ) 构造了一种新颖的、紧凑的数据结构f p 树。它是一种扩展的前缀树 结构，存储了挖掘所需的全部频繁信息。树中只包含长度为l 的频繁项作为 结点，并且那些频度高的结点更靠近树的根结点，因此，频度高的项比那些 频度低的项有更多的机会共享同一个结点。 ( 2 ) 开发了基于f p 树的模式片段增长算法，它从长度为1 的频繁模式开 始，只检查它的条件模式基构建它的条件模式树，并且在这个树上递归地执 行挖掘。模式的增长通过连接条件模式树新产生的后缀模式实现。因此f p 树算法不像类a p r i o r i 算法那样需要产生再测试，而是只需测试即可。挖掘的 主要操作是计算项集的支持度计数和调整前缀树，这种花费通常要远远小于 类a p r i o r i 算法中的候选项集的产生和模式匹配操作。 ( 3 ) 挖掘过程中采用的搜索技术基于分治思想，通过分割再解决的方法， 而不是类a p r i o r i 算法的自底向上的产生频繁项集的方法。它通过将发现长频 繁模式的问题转化成寻找短模式然后再与后缀连接的方法，避免了产生长候 选项集。 综上可见，以f p g r o w t h 算法为代表的无候选项集产生方法比r h a p r i o r i 算法为代表的需要产生候选项集方法有更好的表现。 ( 1 ) 它用一种高度压缩的结构存储了数据库中所有有意义的信息，把对 数据库的扫描限制在了两遍，将对数据库的扫描所消耗的i o 时间减到了最 少。 第1 5 页河南大学研究生硕士学位论文 ( 2 ) 它将长的频繁模式分割成多个长度为1 的频繁项，一步一步用模式增 长的方法产生较长的频繁项集，避免了大量候选项集的产生和测试过程，直 接产生了频繁模式。 ( 3 ) 它对条件模式基和条件模式树进行了分割，减小了它们的大小。 实验分析表明，f p g r o w t h 算法比类a p r i o r i 算法快一个数量级。 2 2 单向f p - 树与基于被约束子树的挖掘算法 2 0 0 2 年，在f p 树的基础上，范明等人改进了f p 树结构，提出了一种 基于被约束子树挖掘频繁项集的有效算法 7 0 1 。由于改进的f p 树是单向的， 本文称之为单向f p 。树。该算法在挖掘频繁项集时不生成条件模式树，从而 极大提高了频繁项集挖掘的时空效率，实验表明，与f p g r o w t h 算法相比， 挖掘速度提高了1 倍以上，而所需的存储空间减少了一半。 2 2 1 单向f p 一树 单向f p 树与f p 树具有类似的结构，不同之处在于【7 0 】： ( 1 ) f p 树是双向的，而单向f p 树是单向的。在单向f p 树中不存在从 树根到树叶的路径。这样，与f p 一树的结点相比，单向f p 树的结点包含较 少的指针。 ( 2 ) f p 树的结点用项标记并记录项的支持度计数，而单向f p 一树的结点 用项的序号标记并记录项的支持度计数。项的序号按项的支持度由大到小排 序确定。 与f p 树类似，为了便于访问所有具有相同序号标记的结点，单向f p 一 树也将具有相同标记的结点链接在一起，形成结点链，并用一个指针数组 h e a d 】存放每个结点链的头指针。此外，使用一个整型数组c o u n t 】，并 用c o u n t 】记录f p 树中具有序号，的结点的支持度计数和。 单向f p 树结点包含4 个字段：项的序号o r d e r 、支持度计数c o u n t 、 指向最左子女结点或父结点的指针a h e a d 和指向右兄弟结点或结点链中下一 结点的指针n e x t 。 一，单向f p - 树的构造 从空树出发，单向f p 树( o n i df p t r e e ) 可按如下步骤生成【7 0 】； ( 1 ) 扫描事务数据库d ，得到每个项的支持度计数。 ( 2 ) 将项按支持度计数降序排序，得到每个项的序号，并生成项- 序转换 表和序项转换表。 河南大学研究生硕士学位论文第1 9 页 ( 3 ) 扫描事务数据库d ，对于每个事务中的i t e m s e t ： 删除i t e m a e t 中支持度计数小于r a i nc o l i n t 的项，将剩下的项转换成序 号，并排序，得到o r d e r l i s t 。 将o r d e r l i s t 插入单向f p 树。 ( 4 ) 以先根次序遍历单向f p 一树，生成结点链，并翻转a h e a d 指针。 步骤( 3 ) 与f p 树的对应的构造过程【2 5 】类似，从略。需要指出的是， 在步骤( 3 ) ，我们使用a h e a d 指向结点的最左子女，而使用n e x t 指向结点的右 兄弟。在步骤( 4 ) 之后，a h e a d g 苷指向父结点，而n e x t 用于结点链拉链。此时， 单向f p 树中不再有由父结点到子结点和兄弟之间的路径。 二、偏序关系【7 0 】 为建立单向f p 树中的路径与项集之间的联系，定义了项目之间的偏序 关系“ ”。对于任意项a ，b e i ，口_ b 当且仅当a 对应的序号小于b 对应的 序号。由于任意项集总可以按项目之间的偏序关系，由小到大排序，以下我 们把项集视为有序序列。项集之间的偏序关系“ ”定义如下：设 a 1 ，a 2 ， ，卿) 和( b l ，b 2 ，巩) 是两个项集。( a l ，a 2 ，口i 6 i ，6 2 ， 巩 ，如果存在1 f 鲰，使得当lg f 时，a y = b j ，而a f - b i ；或者对于1g 敛， a j = 西，而后 n 。 引理2 2 1 - t o 设 i l ，2 ，泌为频繁项集。f 1 ，2 ，如的序号分 别为0 1 ，0 2 ，0 i 。 i l ，2 ，“) 的支持度计数等于c ，当且仅当 单向f p 一树中所有以根为起点，以巩为终点，包含o l ，0 2 ，吼的路径上以 以为标记的结点的计数和等于c 。 引理2 2 1 表明，单向f p 树蕴涵了事务数据库中的所有频繁模式信息。 2 2 2 基于被约束子树的频繁项集挖掘算法 一、被约束子树 定义2 2 1 t 7 0 1 设七f i 时，s ，( o k ，o k 一1 ，0 2 ) 将被 算法构造，并且s t ( o k ，o k l ，0 2 ) c o u n t 【o l 】= c 。然后，利用引理2 2 1 ， 2 2 2 和已证明的结论，对p a t t e r n 的长度进行归纳，可证h j p a t t e r n 将被算 法产生。 2 3f p - 树与单向f p - 树对比 2 3 1f p - g r o w t h 算法存在的问题 ( 1 ) 在挖掘频繁项集时，需要递归的生成大量的条件模式树。动态的生 成和释放这些条件模式树将耗费大量时间和空间。因此算法的时空效率仍然 不够高。 ( 2 ) 条件模式树的构造过程和f p 树的一样，即需要自顶向下生成；而频 繁项集的挖掘需要自底向上的处理，故而条件模式树和f p 树必须是双向可 第2 2 页河南大学研究生硕士学位论文 遍历的，这样，就需要更多的指针。从而需要更大的内存空间来维护f p - 树 和条件模式树。 2 3 ，2 单向f p - 树的优点 ( 1 ) 单向f p 一树是单向的，不存在从树根到树叶的路径，相对f p 一树用了 更少的指针，每个结点至多需要两个指针，一个指向父结点，一个指向下一 个同名结点。因此占用的存储空间比f p 树少。 ( 2 ) 单向f p 树比f p 树更容易实现，因为单向f p 一树有两个指针域，而f p 一 树的指针数目不固定。 在单向f p 树基础上，范明提出的基于被约束子树的频繁项集挖掘算法 在挖掘频繁项集过程中不生成条件模式树，只生成被约束子树，而被约束子 树是在单向f p 树的基础上通过3 个很小的数组表示的，因此不会增加额外的 时空开销。 2 4 本章小结 本章介绍了两个频繁项集挖掘算法，一个是经典的f p - g r o w t h 算法，它 是无候选项集产生算法的代表，分析了它之所以优于a p r i o r i 算法的原因以 及它为频繁项集挖掘研究作出的开创性贡献。另一个是范明提出的基于单向 f p 树的频繁项集挖掘算法，该算法是针对f p g r o w t h 存在的问题设计的， 着重对比了单向f p 树和f p 树结构的异同，分析了范明提出的单向f p 一树及 其算法的优势。本章是本文研究的理论基础和立足点。 河南大学研究生硕士学位论文第2 3 页 第3 章基于单向f p - 树的最大频繁项集挖掘算法 在诸多频繁项集生成算法中，计算项集的支持度是发现频繁项集最耗时 的工作；并且在较低的支持度要求下，产生的频繁项集飞快增长。对于现实 生活中的真实数据库而言，产生的频繁项集之多，已让人无法忍受。因此只 有减少生成的项集数才能降低算法开销。由于最大频繁项目集已经隐含了所 有频繁项集，故可把发现频繁项集的问题转化为挖掘最大频繁项集的问题。 此外，某些数据挖掘应用( 如生物序列检测【_ “1 ) 仅需挖掘最大频繁项集，而不 必挖掘所有的频繁项集，因而最大频繁项集挖掘具有十分重要的意义。 f p m a x 算法一种非常有效的基于f p 坤日挖掘最大频繁项集的深度优先 算法。然而该算法在挖掘过程中需要递归的生成大量的条件模式树，其时空 效率仍然不够高。本章借鉴范明提出的单向f p 树及其频繁项集挖掘算法， 提出了基于单向f p 树的最大频繁项集挖掘算法u n i df p m a x 。 3 1 基于i = p - 树的最大频繁项集挖掘算法 f p m a x 算法【4 9 1 采用分而治之的思想，在经过第二遍扫描后，把数据库 中所有的频繁信息压缩存储在f p - 和| 中，随后再将f p 树划分成一些条件模 式基，然后再对这些库分别进行挖掘。下面给出f p m a x 算法用到的定义和 定理。 3 1 1 基础理论 定义3 1 i t 4 5 】如果频繁项集x 的所有超集都是非频繁项集，那么称石 是一个最大频繁项集。所有最大频繁项集的集合记为m f i ( m a x i m a lf r e q u e n t i t e m s e t ) 。 引理3 1 1 ( 单路径f p - 树挖掘) 口8 】假设f p 一树包含单路径p = ，那么项集z = a la 2 巩为最大频繁项集，其支持 度计数为结点巩的支持度计数s l 。 证明：根据f p ，树的构造过程，很明显口l 眈巩为频繁项集，因为a la 2 a 包含了f p 树中所有的结点，所以m 砚巩组成最大频繁项集。又因为 f p - 树仅包含一条单路径，所以每个包含结点a i 的事务一定也包含结点a t ， a 2 ，a k l 。这样，s u p p o r t ( a l a z a k ) = s u p p o r t ( a k ) = s k _ m i n _ c o u n t ，其中 r a i nc o u n t 为最小支持度计数。证毕。 第2 4 页河南大学研究生硕士学位论文 在事务数据库中挖掘最大频繁项集的问题可以描述为：给定事务数据库 d 和最小支持度阈值m i n，找到所有的最大频繁项集 引理3 i 2 t 4 9 】给定一个事务数据库d 和最小支持度阈值m i ns u p ( 或最小 支持度计数r a i nc o u n t ) ，项头表l = 。挖掘最大频繁 项集的问题可以分解为n 个子问题：第，( 1 舸) 个子问题是找到所有包含f 川 但不包含i k ( n + 1 7 胚胛) 的最大频繁项集。 从引理3 1 2 可以看出，后挖掘到的最大频繁项集不可能包含先前找到 的最大频繁项集，相反它可能被已有的一个最大频繁项集所包含，因此在挖 掘过程中要进行超集检测 4 9 , 5 3 , 7 2 。如果刚得到的候选最大频繁项集y 不是已 有的一个最大频繁项集的子集，那么就说y 通过了超集检测，是一个最大频 繁项集。 推论3 1 1 t 5 8 1 如果后缀口( 可能包含多个项目) 的条件模式树仅包含单 路径口，那么可以直接得到以口为后缀的候选最大频繁项集制，其支持度等 于口c o u n t 。 这里以口为后缀的候选最大频繁项集是所有以后缀为口的频繁项集中的 最大频繁项集，但是又可能是己挖掘出来的最大频繁项集的子集。 上述的引理和推论是算法f p - m a x 的理论依据。 3 1 2 基于f p - 树的最大频繁项集挖掘算法 算法3 1 1r f p m a x l 【5 s 】：基于f p 树挖掘最大频繁项集 输入：由算法2 1 1 得到的f p 树和最小支持度阈值m i n _ s u p 。 输出：所有的最大频繁项集m f i 。 方法：调用f p m a x ( f p 一树，n u l l ，m f i ) 。 m f i = o ；用来保存己挖掘到最大频繁项集 p r o c e d u r ef p m a x ( t r e e ，口，m f i ) ( 1 ) i ft r e e 仅包含单路径t h e n ( 2 ) 产生候选最大频繁项集c m 。= 则，其中支持度为中结点支持度最小 值； ( 3 ) i f c 。通过了超集检测 ( 4 ) t h e nm f i = m f i u c 。； ( 5 ) e l s ef o rt r e e 中每一个结点a i ( 从项头表的最后项开始) d o ( 6 )= a i k ) ，支持度为a ，支持度； ( 7 )构造的条件模式基，然后构造的条件模式树t r e e p ； ( 8 ) i f t r e e p ot h e n 调用f p m a x ( t r e e p ，m f i ) ； 河南大学研究生硕士学位论文第2 5 页 ( 9 )e l s e ( 1 0 )产生候选最大频繁模式c 。产屈 ( 1 1 ) i f g 。通过了超集检测 ( 1 2 ) t h e nm f i = m f i u c k 。； ( 1 3 )尸a la 2 a t t k ) o j ； ( 1 4 )i f ，没有通过超集检测t h e nb r e a k ； 行( 1 3 ) 行( 1 4 ) 说明在进行以项目a f 为后缀的最大频繁项集搜索结束后检查 由剩下项目a la 2 口“u 组成的项集是否是已挖掘出的最大频繁项集的子 集。着口i 眈a t - i u d 是已挖掘出的最大频繁项集的子集，那么以后不可能会 有新的最大频繁模式了，挖掘过程终止。所有的最大频繁项集存储在集合 m f i 中。 可以清晰的看到影响f p m a x 算法效率的主要原因：在挖掘最大频繁项 集的过程中需要反复递归构造新的条件模式树，并将其存放在内存中直到递 归结束。构造条件模式树需要先产生条件模式基，然后重新对每一项进行支 持度计数、排序，因此是个时空开销很大的操作，增加了实现难度。 3 2 基于单向f p 一树的最大频繁项集挖掘算法 针对f p m a x 算法的缺陷，设计了基于单向f p 树的最大频繁项集挖掘 算法u n i df p m a x 。该算法是一个深度优先算法，在挖掘最大频繁项集过程 中不产生条件模式树，从而有效的减少了时间和空间的开销。实验表明，与 f p m a x 算法相比，算法的挖掘速度提高了1 倍以上。 本节首先举例说明最大频繁项集的挖掘过程，然后引出u n i df p m a x 算法，最后通过实验比较f p m a x 算法和u n i df p m a x 算法的性能。 3 2 1 基础理论 例3 2 1 考虑表3 1 所示的事务数据库d 。 表3 - 1 事务数据库d 理旦旦翌丛! 星g ! 鲤丝g 塑丛 1 0 0 1 , 1 2 ，1 3 ，i s1 ，2 ，3 ，4 2 0 0 ，1 3 ，42 ，3 ，5 3 0 0 1 2 ，1 3 d 41 ，3 ，5 4 0 0 1 1 ，最a t 51 ，2 ，4 5 0 0五d 3 l ，3 第2 6 页河南大学研究生硕士学位论文 6 0 0 ，l ，1 4 7 0 0 1 ，1 3 ，i s 8 0 0 i l ，1 1 9 0 0 2 1 2 2 ，3 ，4 1 2 1 若最小支持度计数m i nc o u n t = 2 ，扫描一次d ，得到频繁l 一项集，将其 按支持度计数降序排序，得到项序转换表( 如表3 2 ) 。为了方便起见，在单 向f p 树和被约束子树7 0 1 中用序号代表项目，表3 1 的第三列就是事务中的 项目按照序号转换后的序号集。生成的单向f p 一树如图3 1 所示。 表3 2 项序转换表 垦；z 玉； 垦；蠡；z l2345 c o u n th e a d 图! h e a d e rt a b l e 图3 1 单向f p - 树 单向f p 树将具有相同序号的结点链接在一起，形成结点链，并用h e a d e r t a b l e 中的h e a 讲 存放每个结点链的头指针，c o u n t i 记录树中具有序号为 的结点的支持度计数和。树中结点包含4 个宇段：项的序号，支持度计数， 指向父结点的指针a h e a d ，指向结点链中下一个结点的指针n e x t 。 对于序号k ，从k 的结点链中的每个结点出发，自底向上搜索单向f p 一 树，就可以构造被约束子树s 丁( 的。 例3 。2 2 图3 1 所示的单向f p 缸寸的被约束子树s 丁( 5 ) 如图3 - 2 所示。 s t ( 是单向f p - 榜l 的一个包含树根的特殊子树，可以用三个数组表示： 指针数组b r a n c h 】，指示每条被约束项 盼约束的子路径；整型数组 b a s e c o u n t 【】，记录每条被 目约束的子路径的基本频度计数；整型数组 c o u n t 】，记录st ( 妁中具有相同序号的结点的频度计数和。 河南大学研究生硕士学位论文第2 7 页 图3 2 图3 - l 所示单向f p 树的s t ( 5 ) 被约束子树s r ( 岛，1 ，) 可以由s r ( 七i ，k 1 ) 构造， 其中序号 1 是l ，构造过程与构造被约束子树sr ( 妨类似。 如果序号k k l 1 ) ，那么，k l 所对应的项集用“k ， 七1 ) 表示。 如果用大字写母足表示序号集 后l ，k m 1 ) ，那么s r ( 女l ，k 1 ) 可以表示为s t ( 秘；s t ( 露1 ，k m - i ，) 也可以表示为st ( k u ) 。 如果约束项x 所对应的项集( 2 0 为一个维数为k 的项集，那么就说s t 处于第k 层。 引理3 2 1 1 7 0 】如果具有序号为x 的结点在st 中出现，则i ( x u x ) 支持 度计数为st ( c o u n t i x 】。 由于项目和序号是一一对应的，因此项集和序号集也是对应的，在不会 引起混淆时，两者可以通用。 单向f p 树和被约束子树的详细构造过程可以参考文献【7 0 】。 下面通过实例演示算法u n i df p m a x 的挖掘过程。 例3 2 3 给定表3 - 1 中的事务数据库d 和r a i nc o u n t = 2 ，找到所有的最 大频繁项集( m f i ) 。 采用分而治之的策略，根据图3 - 1 的h e a d t a b l e 将m f i 划分为5 个不相 交的集合：( 1 ) 所有包含序号5 的最大频繁项集