（计算机软件与理论专业论文）用于挖掘频繁项集的剪枝策略（ntep）.pdf

用于挖搠频繁项熊的剪授策略 摘要 频繁项集挖掘在数据挖掘的应用诸如关联规则1 - 2 1 、相关分析【3 】、强规则、 多维模式和许多其它重要的知识发现中是一个基本和重要的问题。频繁项集挖 掘的问题可以表示如下：给定一个事务数据库，其中每个事务用一个项集来表 示，我们要在其中找出所有的频繁项集即发生频率高于或等于用户定义的百分 比的项的集合。 大量现有的频繁项集挖掘算法是一p r f d ，f 【l 】算法的变种。而a p r i o r i 算法是一 个至底向上，宽度优先搜索的算法，a p r i o r i 首先列举出所有的频繁1 项集，然 后产生频繁2 。项集，就这样一直递归由频繁k 项集产生频繁k + l 一项集。但是在 许多模式较长的应用中，列举出一个长为m 的模式的所有从2 2 “长度的子集 由于计算代价太高是很难实现的。所以，近来研究的热点主要集中在如何缩小 搜索空间使得频繁项集挖掘算法更有效。 在这篇文章中提出了一种新的搜索空间剪枝技术n t e p ，这种剪枝技术可 以被应用在多种类a p r i o r i 算法。我们选择m a f i a 算法将n t e p 应用进去，以便 获得n t e p 的性能。我们用了几种类型的数据集来进行性能测试。最后，我们 给出了采用了n t e p 的m a f i a 和原m a f i a 之间的性能比较。结果显示，n t e p 可以有效地减小搜索空间，并且对比原m a f i a 采用了n t e p 的m a f i a 算法性能 可以很大地提高算法所需时间。 关键词：最大频繁项集、a p r i o r i 算法、关联规则、搜索空间 用于挖掘频繁项集的剪枝策略 a b s t r a c t m i n i n gf r e q u e n ti t e m s e t si sa f u n d a m e n t a la n de s s e n t i a lp r o b l e mi nm a n yd a t a m i n i n ga p p l i c a t i o n ss u c ha st h ed i s c o v e r yo f a s s o c i a t i o nr u l e s ，a s s o c i a t i o na n a l y s i s s t r o n gr u l e s ，c o r r e l a t i o n s ，m u l t i d i m e n s i o n a lp a t t e r n s ，a n dm a n yo t h e ri m p o r t a n t d i s c o v e r yt a s k s t h ep r o b l e m i sf o r m u l a t e da sf o l l o w s ：g i v e nal a r g ed a t a b a s eo f s e t o fi t e m st r a n s a c t i o n s ，f m da l lf r e q u e n ti t e m s e t s ，w h e r eaf r e q u e n ti t e m s e ti so n et h a t o c c u r si na tl e a s ta u s e r - s p e c i f i e dp e r c e n t a g eo f t h e d a t a b a s e m a n yo ft h ep r o p o s e df r e q u e n ti t e m s e tm i n i n ga l g o r i t h m s a l eav a r i a n to f a p r i o r i 哆w h i c he m p l o y sab o s o m - u p ，b r e a t h f i r s ts e a r c ht h a te n u m e r a t e se v e r y s i n g l ef r e q u e n ti t e m s e t ，t h e ng e n e r a t e s t h es e to fc a n d i d a t ep a r e m so f l e n g t h2 s oi t i t e r a t i v e l yg e n e r a t e st h e s e to fc a n d i d a t ep a t t e r n so fl e n g t h ( k + 1 ) b u t ，i nm a n y a p p l i c a t i o n sw i t hl o n gf r e q u e n tp a t t e r n se n u m e r a t i n g a l lp o s s i b l e2 i 一2s u b s e t so fa m l e n g t hp a t t e r n i s c o m p u t a t i o n a l l yu n f e a s i b l e t h u s ，t h e r e h a v eb e e nr e c e n t i n t e r e s t si nr e d u c i n gt h es e a r c h i n gs p a c et om a k et h ea l g o r i t h mf o rm i n i n gf r e q u e n t i t e m s e t sm o l ee f f i c i e n t t h i sp a p e r p r e s e n t sas e a r c hs p a c ep r u n i n gs t r a t e g yn t e p t h a tc a ne f f i c i e n t l y r e d u c et h es e a r c h i n gs p a c ef o rm i n i n gm a x i m a lf r e q u e n ti t e m s e t ，w h i c hc a l lb eu s e d i nm o s to f a p r i o r i - l i k ea l g o r i t h m w ec h o o s em a f i a t o a d a p tn t e p t og e tt h e p e r f o r m a n c es t u d y w eu s es e v e r a lt y p e so fd a t a s e tt ot e s t f i n a l l yw ep r e s e n tt h e e x p e r i m e n tr e s u l t so ft h ec o m p a r i s o nb e t w e e nm a f i aa n dm a f i a w i t hn t e p w h i c hs h o w sn t e pc a ne f f i c i e n t l yr e d u c et h es e a r c h i n gs p a c ea n dm a f i aw i t h n t e pc a nr e d u c eh a l f o f t i m e k e yw o r d s ：m f l ( m a x i m a lf r e q u e n ti t e m s e t s ) ，a p n o r ia l g o r i t h m ，a s s o c i a t i o n r u l e s ，s e a r c hs p a c e - i i i 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下 独立进行研究所取得的成果。学位论文中凡引用他人已经发表或 未发表的成果、数据、观点等，均已明确注明出处。除文中已经 注明引用的内容外，不包含任何其他个人或集体己经发表或撰写 过的科研成果。对本文的研究成果做出重要贡献的个人和集体， 均已在文中以明确方式标明。 本声明的法律责任由本人承担。 论文作者签名： 二 胄 日期：劢。岁、夕2 弓 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产 权归属兰州大学。本人完全了解兰州大学有关保存、使用学位论 文的规定，同意学校保存或向国家有关部门或机构送交论文的纸 质版和电子版，允许论文被查阅和借阅；本人授权兰州大学可以 将本学位论文的全部或部分内容编入有关数据库进行检索，可以 采用任何复制手段保存和汇编本学位论文。本人离校后发表、使 用学位论文或与该沦文赢接相关的学术论文或成果时，第一署名 单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：! ! ! 三一导师签名 挚蜴期：盟够 用于挖搠频繁项熊的剪授策略 第一章绪论和背景知识 1 1 研究背景 关联规则反映了大量数据中项目集之间有趣的或相关的联系。随着大量数 据不停地被收集和存储，许多业界人士对于从他们的数据库中挖掘关联规则越 来越感兴趣。从大量商务事务记录中发现有趣的关联关系，可以有助于许多商 务决策的制定，如分类设计、交叉购物和贱卖分析。关联规则模型和支持度框 架最早是1 扫a g r a w a l e ta 1 【1 ，4 】提出的而挖掘频繁项集是关联规则挖掘的一个基 础问题。 目前，现有的频繁项集挖掘算法主要分为两种： 1 ) 产生候选项集的频繁项集挖掘方法： 以a p r i o f i 算法为基础，这种方法是基于反单调的a p r i o f i 引理。a p r i o r i 引理的基本思想是反复地从长度为k 的频繁项集产生长度为( k + 1 ) 的候选项集， 然后检查候选项集在数据库中的发生频率。a 研o r i 算法在候选项集较小的时候 可以获得很好的性能，但是在频繁模式数量很大的时候或者支持度阈值很小的 时候，a p r i o r 算法就会出现如下两个方面较大的代价： 处理大量的候选项集会花费很大的代价，例如：当频繁1 一项集的大小 为1 0 4 时，那么候选频繁2 项集的大小将会大于1 0 7 。 当频繁扫描数据库，通过模式匹配来验证一个长模式是否为频繁的时 候将会花费大量时间。 2 ) 不产生候选项集的频繁项集挖掘方法： 以j i a w e ih a n 等提出的f p - g r o w t h 算法为代表，这种算法主要是将提供频 繁项集的数据库信息压缩为一棵频繁模式树( f p t r e e ) ，但仍保留项集关联信息。 然后将这种压缩后的数据库分成一组条件数据库( 一种特殊类型的投影数据 库) ，每个条件数据库关联一个频繁项，并分别挖掘每个条件数据库。然后将 结果插入到频繁项集合中去。 f p g r o w t h 算法将发现长频繁模式的问题转化为低代价地发现一些短模 式，然后连接后缀。它使用最不频繁的项作后缀，提供了好的选择性。该方法 大大降低了搜索开销。 其后的数据挖掘算法大多建立在这两种算法基础之上，或进行改进，或衍 用于挖搠频繁项熊的剪授策略 生变种，或将多种算法中精华部分进行抽取然后再结合。诸如a p r i o r i t i d ， a p r i o r i h y b i r d g e n m a x ，m a f i a 等。 其中，m a f i a 主要是将多种算法进行分割，抽取精华再进行组合，m a f i a 算法采用了a p r i o r i 算法的基本思想；而在剪枝策略上采用了p e p ，f h u t ，和 h u t m f i 等基本剪枝策略；在此基础上，采用了垂直位图来表示数据库并采用 了权衡位图压缩技术来降低空间占用率。经过在不同种类数据集上的测试发现 m a f i a 效率相对于现有的算法有大幅度的提高，尤其是在支持度较小时相对 于其它算法的优势更为明显。 在产生候选项集的频繁项集挖掘方法中，由于产生频繁模式的过程可以相 应地通过在构建的语法树上进行搜索的过程来表示，所以如何使算法变得更有 效的问题就转化为如何使得构建的语法树变得更小，即如何从语法树上剪掉多 余的分支。针对这个问题，目前已经提出了很多不同的剪枝策略，每一种剪枝 策略的提出都能进一步提高算法的效率，减小搜索空间。 1 2 本文的研究内容及目的 在这篇文章中提出了一种新的搜索空划剪枝技术，这种剪枝技术可以被应 用到多种类a p r o r i 算法中。为了对这种剪枝策略的效率进行验证，我们从多种 算法中选择m a f i a 算法将n t e p 应用进去，以便获得n t e p 的性能测试。我们选 用了几种不同类型的数据集，例如：稀疏型数据、稠密型数据、人工型数据以 及自然数据来进行性能测试。最后，我们给出了对采用了n t e p 的m a f i a 和原 m a f i a 之间的性能比较( 用图表表示) ，结果显示，n t e p 可以有效地减小搜索 空间，对比原m a f i a 采用了n t e p 的m a f i a 性能可以提高将近一半。 1 3 文章的组织 在第二章中，将主要介绍关联规则挖掘的背景知识，从而对本文要研究的 具体问题有明确的认识，第三章主要介绍m a f i a 算法的基本思想和其构成部 分以及m a f i a 算法的伪码表示。第四章将主要介绍本文所提供的剪枝策略的 基本思想、原理和伪码表示。在第五章中将通过实验对剪枝策略的效率进行验 证，给出实验结果的比较，最后在第六章中对全文进行总结，并为以后工作提 出建议。 1 4 关联规则的挖掘 用于挖掘频繁项集的剪枝策略 1 4 1 关联规则简介 关联规则挖掘是发现大量数据中项目之间有趣的关联或相关联系，它在数 据挖掘中是一个重要的课题，最近几年被业界广泛研究。关联规则挖掘的个 典型例子是购物篮分析。关联规则研究有助于发现交易数据库中不同商品( 项) 之间的联系，找出顾客购买行为模式，如购买了某一商品对购买其他商品的影 响。挖掘出来的关联规则可以应用于分类设计、交叉购物、贱卖分析、顾客分 类。 a g r a w a l 等人于1 9 9 3 年首先提出了挖掘顾客交易数据库中项目间的关联 规则算法，以后诸多研究人员对关联规则挖掘问题进行了大量的研究，他们的 工作主要是对原有算法进行优化，如引入随机采样、散列、划分、事务压缩等 思想，提高算法效率，并对关联规则的应用进行推广。 关联规则揭示项目间的相互关系，关联规则挖掘就是从一组给定的项目以 及交易集合( 每一笔交易都是项目的集合) 中，分析出项目在交易集合中出现 的频度关系。关联规则是如下形式的逻辑蕴涵：a j b ，其中a g i ，b i ，且a n b = a 。规则a j b 在事务集d 中成立，具有支持度s ，其中s 是d 中事务 包含a w b ( 即a 和b 二者) 的百分比。它是概率p ( a u b ) 。规则a j b 1 4 2 关联规则挖掘的过程 1 ) 找出所有频繁项集。 2 ) 由得到的频繁项集产生强关联规则。 6 ，7 急9 1 0 1 2 】 由此可知，频繁项集挖掘是关联规则挖掘中的基础问题。其中，时问主要 耗费在第一步中【“。 1 5 挖掘频繁项集 1 5 1 频繁项集的定义 挖掘频繁项集的问题可以陈述如下： 设i _ i l ，i 2 ，i m ) 是m 个不相同的项的集合。设d 代表一个事务数据库，其中 每一个事务都由一个独一无二的标志符事务号( t i d ) 来标记，并且每一个事务都 是一个项的集合，所有事务的集合被表示为t = t l ，t 2 t n ，集合x ( x g i ) 是- - 个 项集。若集合x 的势为k ，则称x 为一个k 项集。集合“x ) t 是由所有包含x 的 用于挖掘频繁项集的剪枝策略 事务的事务号所构成的集合，e p t ( x ) = y t i d y t a n dx c y ，称为x 的事务号 集合。一个项集x 的支持度表示为6 ( x ) ，是包含x 的事务的数量，所以 6 ( x ) ：i t ( x ) 。一个项集是频繁的当且仅当它的支持度大于或等于最小支持度阈 值( m i n s u p ) 。我们用f k 来表示频繁k 项集，用f i 来表示所有频繁项集的集合。如 果一个频繁项集的任何超集都不是频繁的，那么，就称这个频繁项集是最大频 繁项集，所有最大频繁项集的集合为m f i 。给出一个用户定义的最小支持度， 我们的目标就是高效地列举出所有f i 中的模式。 到目前为止已经有很多方法用来产生所有的频繁项集1 3 1 4 1 6 - n 1 8 ，1 92 0 2 1r 2 2 翘2 4 1 ，但是产生所有的频繁项集在时间上来说通常是不现实的尤其是在 模式很长的时候【2 5 】，所以在这篇文章中，所有频繁项集挖掘问题都指的是最大 频繁项集挖掘问题。所以，我们的问题就变为：给出一个用户定义的最小支持 度，我们的目标是高效地列举出所有m f i 中的模式。 1 5 2 现有的频繁项集挖掘算法 下面，将对现有的频繁项集挖掘算法作一个较为全面的介绍。 1 ) a p r i o d 算法： a p r i o r i 算法是基于反单调a 嘶o r i 定理：如果任何长度为k 的模式在数据 库中是不频繁的，它的长度为( k + 1 ) 的超集永远不可能是频繁的。a p r i o r i 算法 的基本思想是递归地从长度为k 的频繁模式集合产生长度为 k + 1 ) 候选频繁模 式集合，然后在数据库中查询这些候选频繁模式的实际发生频率。a p r i o r i 算法 在候选项集较小的时候可以获得很好的性能，但是在频繁模式数量很大的时候 或者支持度阈值很小的时候，a p r i o r 算法就会出现如下两个方面较大的代价： 处理大量的候选项集会花费很大的代价，例如：当频繁1 一项集为1 0 4 时，那么候选频繁2 项集将会大于1 0 7 。 在频繁扫描数据库，通过模式匹配来验证一个长模式是否为频繁的将 会花费大量时间。 2 ) 改进的a p d o r i 1 i k e 算法： 经典的a p r i o r i 算法是采用自底向上、宽度优先的搜索策略来生成频繁项 集。现有的很多算法都是采用了a p r i o r i 算法的基本思想，然后对a p r i o r i 加以 各种改进后得到的。这些改进包括： 用于挖搠频繁项熊的剪授策略 利用位图来表示事务数据库，这样可以提高在数据库中统计项集出现频 率时的效率。 构造各种树型结构来表示整个频繁项集的生成过程。其中，比较成熟并 为大多数人接受的为l e x i c o g r a p h i c t r e e ( 语法树) 。 针对第二步中树型结构，构造各种剪枝策略，来缩减a p r i o r i 算法的搜 索空间，提高算法效率。 对树结点进行排序，来进一步缩小算法查找f i 时间。如：动态节点排 序技术等。 采用压缩技术来压缩事务数据库，使它能够一次全部装载到内存中。 其它一些出现在某一算法中，但没有被广泛使用的技术。 3 ) 不产生候选项集的频繁项集挖掘方法： 以j i a w e ih a n 等提出的f p - g r o w t h 算法为代表，这种算法主要是将提供频 繁项集的数据库压缩为一棵频繁模式树( f p t r e e ) ，但仍保留项集关联信息。 然后将这种压缩后的数据库分成一组条件数据库( 一种特殊类型的投影数据 库) ，每个条件数据库关联一个频繁项，并分别挖掘每个条件数据库。然后将 结果插入到频繁项集合中去。f p - g r o w t h 算法如下： p r o c e d u r e f p - g r o w t h ( t r e e , o ) a i f t r e e 含单个路径pt h e n b r ) r 路径p 中节点的每个组合( 记作b ) c + 产生模式1 3 u ，其支持度s u p p o r t = 1 3 中节点的最小支持度； d e l s e f o r e a c ho , i 在t r e e 的头部 e 产生一个模式p = 俚i u a ，其支持度 s u p p o r t = c t is u p p o r t ； f 构造p 的条件模式基，然后构造p 的条件f p t r e e b ： g i f t r e e # g t h e n h 调用f p g r o w t h ( t r e e l l p ) ；) 由以上可以得出：f p - g r o w t h 算法将发现长频繁模式的问题转化为低代价 地发现一些短模式，然后再连接后缀。它使用最不频繁的项作后缀，提供了好 的选择性。该方法大大降低了搜索开销。 用于挖搠频繁项熊的剪授策略 1 5 3 现有的最大频繁项集挖掘算法 目前已经提出的可用于发现最大频繁项目集的算法有m a x m i n e r ， p i n c e r - s e a r c h 以及d m f i ，d m f i a 等。 m a x m i n e r 算法： m a x m i n e l 安破了传统的自底向上的搜索策略，尽可能早地对项目集进行 修剪，其缺陷是：未利用自顶向下的信息进行修剪；未对m f c s 进行适当 的排序，产生了多余的最大频繁候选项目集。 p i n e e r - s e a r c h l 2 8 1 算法： p i n c c r s e a r c h 采用了自底向上和自顶向下的双向搜索策略，但其第女次的 m f c s 是f l j k - 1 次的m f c s 中的非频繁项目集去掉一个元素来生成的，产生了过多 的无用候选项目集，对海量数据库来讲，算法p i n c e r s e a r c h 将陷入n p 难度的陷 阱。 d i v i f l l 2 9 | 算法： d m f i 有效地把自底向上和自顶向下的搜索策略进行了合并，该算法为海 量数据库中发现最大频繁项目集和仅需要发现最大频繁项目集的数据挖掘应 用提供了一种有效而快速的算法，但该算法仍需多次重复扫描数据库d ，计算 项目集的支持数。 d m f i a i a 3 i 算法： d m f i a 直接从频繁项目列表产生最大频繁候选项目集，这样的候选空间 一般是特别巨大，该算法从最长的频繁候选项目集开始进行穷举算法，可想而 知其时间和空间复杂度都很高。 1 6 语法树 对于如表1 6 1 所示的事务数据库，其语法树构造如图1 6 2 所示 t i di t e m sm f it i dt t e m sm f l t 1 0 0 i l ，1 2 ，1 51 2 ，i i ，i s t 6 0 0 1 2 ，1 3 t 2 0 0 1 2 ，1 41 2 ，1 4 t 7 0 0 1 1 ，1 3 t 3 0 0 1 2 ，1 31 2 ，1 3 t 8 0 0 i 】，1 2 ，1 3 ，1 51 2 , 1 1 ，1 3 t 4 0 0 i i 1 2 ，1 4 t 9 0 0 l i ，1 2 ，1 31 2 ，i i ，1 3 t 5 0 0 1 1 ，1 3 6 一 用于挖掘频繁项集的剪枝策略 由于我们挖掘的是最人频繁项集， 不是m f i ，所以我们对结果加以舍弃。 所以对于事务t 4 0 0 到事务t 7 0 0 由于他们产生的 表16 1 level 一。三三 = 1 2 i l ，1 3 , 1 4 ，1 5 ) 、 1 1 ( 1 3 , | l 4 , 1 5 ) 1 3 ( 1 4 , 1 5 ) i “卜 ( 1 2 , i t ) 1 3 ，1 4 ，1 5 ( 1 2 , 1 3 ) 1 4 ，1 5 ) ( 1 2 ，1 4 ) 1 5 ( 1 2 ，1 5 ) ( 1 1 ，1 3 ) ( 1 j ，1 4 ) ( i t ，1 5 ) ( 1 3 ，1 4 ) ( 1 3 ，1 5 ) ( 1 4 ，1 5 ) o 岁1 巡芝0 2 1 3 “b 2 x 1 1 絮“b h 1 4 1 州1 3 山。o ( 1 2 ，1 1 ，1 3 ，1 4 ) ( 1 2 ，i i ，1 3 ，i s ) ( 1 2 ，i i ，1 4 ，i s ) ( 1 2 ，1 3 ，1 4 ，i s ) ( 1 1 ，1 3 ，1 4 ，1 5 ) 图中每个节点，用圆括号括起的为节点的头( h e a d ) 表示f i 的前缀，用花括号括起的 为节点的尾( t a i l ) ，表示长度为( k + 1 ) 的f i 的候选项集。对于从节点( i “1 3 ) 开始，由于空 间关系，节点的尾没有给出，但是通过子节点头元素的合并得到。 图1 6 2 1 7 剪枝策略 1 7 1 什么是剪枝策略 对于每一个事务数据集，我们都可以构造如图1 6 2 所示的语法树，这种语 法树代表着在事务数据库中挖掘最大频繁模式的全部过程，但是，在这过程中， 有一些步骤实际上并没有必要执行，如图1 7 1 所示，在图中用黑体标记的节点 的头部所代表的项集已经不是频繁的，所以根据a p r i o r i 引理，该节点的任何子 树都不可能是频繁的。当空间搜索到这种节点时。它的任何子树都没有必要再 进行搜索，即我们可以将它的从搜索空问中除掉，称之为剪枝。 用于挖掘频繁项集的剪枝策略 level 一。 三三 = = 、 1 k 1 3 ，1 4 ，1 5 ) 1 3 0 4 ，i s ) 1 4 ( 1 5 x ) 1 5 l l ( 1 2 ，1 1 ) 1 3 ，1 4 ，1 5 ) ( 1 2 , 1 3 ) 1 4 ，i d ( 1 2 ，j 4 ) 1 5 ( 1 2 ，i s ) ( 1 1 ，1 3 ) ( 1 1 ，1 4 ) ( 1 l ，1 5 ) ( 1 3 ，1 4 ) ( 1 3 ，1 5 ) ( 1 4 ，1 5 ) u 岁1 她巡x 1 2 1 絮1 2 1 4 1 5 掣山山b 山1 5 ( 1 3 , 1 4 , 1 5 ) ( 1 2 , i l 1 3 ，1 4 ) ( 1 2 ，i i ，1 3 ，1 5 ) ( 1 2 ，i l ，1 4 ，i s ) ( i s ，1 3 ，1 4 ，i s ) ( 1 1 ，1 3 ，1 4 ，1 5 ) 幽1 7 1 1 7 2 现有的剪枝策略 p e p 2 7 l ：在语法树中，在节点n ，设x 是节点n 的头，y 是节点n 的尾，那么有 若t ( x ) g ( y ) ，则说明任何包含x 的事务也包含y 。由于我们所要找的是最大频繁项 集，因此，我们可以直接将x 从n 的尾部直接移出添加到n 的头中。 f h u t 2 5 】：在语法树中节点n ，我们检查节点n 的h u t ( 目p 节点n 的头部和尾 部的并集) ，如果节点n 的h u t 是频繁项集，那么对于h u t 的任何子集都不需要 检查，所以，我们可以将以r l 为根节点的所有予树全部剪掉。 h u t m f i l 2 6 】：在节点n ，我们检查节点n 的h u t 是否为当前m f i q p 某- 模式 的子集，如果n 的h u t 确实为当前m f i 中某一模式的子集，, b j n 的h u t 也是频繁 的，并且所有以n 为根节点的子树可以被全部剪掉。 m a x p s 3 1 1 7 l ：在节点n ，如果n h e a d u n t a i l 是频繁的，那么n 的所有右兄弟 以及以它们为根节点的子树全部可以被剪掉。 罐 用于挖搠频繁项熊的剪授策略 第二章m a f i a 算法原理、构成和伪码表示 m a f i a ( m a x i m a lf r e q u e n ti t e m s e ta l g o r i t h m ) 是一个把以前出现的算法中精华 部分加以提炼然后重新装配所构成的算法。 m a f i a 假设整个数据库可以全部装载在内存当中；m a f l a 用语法树束表 示整个m f i 的挖掘过程；在这个语法树上m a f i a 采用了深度优先【2 6 】遍历策略； 对于事务数据库m a f i a 采用了垂直列布局的位图表示，在这种位图中每一列代 表一个事务，如果事务j 中包含项i ，那么在项i 的位图中，对应事蜘的数据位被 置为1 ，否则置为o 。这种垂直位图布局使得在数据库中统计项集的支持度计 数比以前的水平位图布局变得更简单更有效；m a f i a 采用了三种剪枝技术来缩 减算法的搜索空间，这三种剪枝策略分别为：p e p ，f h u t 和h u t m f i ；同时， m a f i a 还采用了节点的动态排序策略：即对语法树中每个节点的孩子，采用根 据支持度的动态排序，而不再是根据词典序进行排列；m a f i a 还采用了自适应 的压缩策略来对表示事务数据库的位图进行压缩，所谓自适应是指在对位图进 行压缩前，要对压缩所用代价和使用压缩后的位图所能节省的时间代价进行权 衡，当使用压缩后的位图确实能节省时间时，才进行压缩，否则就不再进行压 缩。下面，将对m a f i a 的组成部分分别加以具体介绍。 2 1 m a f i a 算法基本思想 m a f i a 算法是一个简单的对语法树的深度优先搜索。在查找m f i 过程中， 不断递归调用算法，直到当前节点为叶子节点时，对节点的头部进行判断，若 其是频繁项集而且在m f i 中没有超集，就将其添j e l 至r j m f i 中。下面是对基本算 法的伪码说明。 p s e u d o c o d e ：s i m p l e ( c u r r e n t n o d ec ，m f i ) f o r e a c h i t e m i i n c t a i l n 州n o d e = c u i i fn e w n o d ei sf r e q u e n t s i m p l e ( n e w n o d e ，m f i ) ) i f ( c i sal e a f a n dc h e a di sn o ti nm f i ) a d dc h e a dt om f i 由以上伪码可以看出，m a f i a 算法的基本思想很简单，它实质上就是采 用于挖掘频繁项集的剪枝策略 用了深度优先i 拘a p r i o r i l i k e 算法。 2 2 m a f i a 算法的剪枝策略 p e p 2 0 ：在语法树中，在节点n ，设x 是节点n 的头，y 是节点n 的尾，那么 有若t ( x ) _ _ l - - t ( y ) ，则说明任何包含x 的事务也包含y 。由于我们所要找的是最大频繁 项集，因此，我们可以直接将x 从n 的尾移出直接添加到n 的头中。下面是对p e p 剪枝策略的伪码说明。 p s e u d o c o d e ：p e p ( c u r r e n t n o d ec ，m f i ) f o r e a c h i t e m i i n c t a i lf n e w n o d e = c u i i f ( n e w n o d e s u p p o r t 2 2 c s u p p o r t ) m o v eif r o mc t a i l t oc 1 l e a d e l s ei fn e w n o d ei sf r e q u e n t p e p ( n e w n o d e ，m f i ) ) i f ( ci sa l e a f a n dc h e a di sn o ti nm f i ) a d dc h e a dt om f i f h u t ：在语法树中节点n ，我们检查节点n 的h u t ( b p 节点n 的头部和尾部 的并集) ，如果节点n 的h u t 是频繁项集，那么对于节点n 的h u t 的任何子集都 不需要检查，所以，我们可以将以n 为根节点的所有子树全部剪掉。下面是对 f h u t 剪枝策略的伪码说明。 p s e u d o c o d e ：删l 盯( n o d ec ，m h ，b o o l e a ni s h u t ) f o r e a c h i t e m i i n c t a i lf n e w n o d e = c u i i s h u t = w h e t h e rii st h el e f t m o s tc h i l di nt h et a i l i f n e w n o d ei sf r e q u e n t 用奴刀( n e w n o d e ，m f i ，i s h u t ) i f ( ci sal e a f a n dc h e a di sn o ti nm f i ) a d dc h e a dt om f i i f ( i s h u t a n da l le x t e n s i o n sa r e f r e q u e n t ) s t o pe x p l o r i n g t h i ss u b t r e ea n d g o b a c ku pt r e et o 用于挖搠频繁项熊的剪援策略 w h e ni s h u tw a sc h a n g e dt ot r u e h u t m f i ：在节点n ，我们检查节点n 的h u t 是否为当日口m f i 中某模式的 子集，如果n 的h u t 确实为当前m f i 中某一模式的子集，则n 的h u t 也是频繁的， 并且所有以n 为根节点的子树可以被全部剪掉。下面是对h u t m f i 剪枝策略的 伪码说明。 p s e u d o c o d e ：h u t m f l ( c u r r e n t n o d ec ，m f i ) i l a m eh u t = c h e a du c t a i l ； i f h u t i s i n m f i s t o ps e a r c h i n g a n dr e t u r n f o re a c hi t e m “nc t a i lf n e w n o d e = cu i i fn e w n o d ei sf r e q u e n t h u t m f i ( n e w n o d e ，m f i ) ) i f f c h e a di sn o ti nm f i ) a d dc h e a dt om f l m a f i a 从多种剪枝策略中，选用了以上三种策略，事实证明，这三种策略 的使用能取得很不错的效果 2 3 m a f i a 算法的节点动态排序策略 所谓对节点的动态排序，是指对于语法树中节点的孩子们不再根据它的词 典序排列子树，而是根据这些孩子的头在数据库中发生的频率进行从小到大进 行排列。 使用节点的动态排序需要在对节点排序时，对项集在数据库中发生的频率 进行统计，这样可以在对节点进行排序的同时，找出不频繁的节点，这些节点 以及它们的子树可以被直接从搜索空间中剪掉从而避免搜索时问的浪费。 所以，节点的动态排序可以和剪枝策略同时使用来有效缩减搜索空间。 2 4 m a f i a 算法的位图压缩技术 对于事务数据库，m a f i a 采用垂直的位图表示，这种垂直的位图表示可以 使支持度技术更为简单，但是这种垂直的位图表示也有缺点：当数据集为稀疏 型数据集，特别是在最小支持度很低的时候，由于不论项在某一事务中是否出 用于挖掘频繁项集的剪枝策略 现，相应的数据位都要赋值，而其中的值为o 的数据位在进行支持度统计的时 候并没有意义，所以对空间浪费很大。 位图压缩技术是将位图中为0 的位去掉，即将某一项的位图压缩到和该项 的支持度一样的长度，且压缩后的位图中仅包含为l 的数据位。下面是位图压 缩技术的伪码表示。 p s e u d o c o d e ：p r o j e c t ( b i t m a px ，n o d e st a i l ) f o r ( e a c h i t e m i i n t a i l ) c r e a t ee m p t y b i t m a p i f o re a c ht r a n s a c t i o nt i f b i t t o f x i s o n a p p e n d b i t t o f i t o i 1 c r e a t ex 一a b i t m a p f i l l e dw i t ho n e sa n ds i z eo f s u p p o r t ( x ) r e t u r ns e to f p r o j c o t e db i t m a p si a n dx 1 2 5 m a f i a 算法的伪码表示 以下的伪码是对m a f i a 算法各个部分的综合并在其中加入了对树节点的 动态排序策略。 p s e u d o c o d e ：m a f i a ( c ，m f i ，b o o l e a ni s h u t ) n t m a _ eh u t = c 。h e a du c , t a i l ； i f h u t i s i n m f i s t o pg e n e r a t i o no f c h i l d r e na n dr e t u m c o u n ta l lc h i l d r e n ，r i s ep e pt ot r i mt h et a i l ，a n dr e o r d e r b yi n c r e a s i n gs u p p o r t f o re a c hi t e mii nc t r i m m e d _ t a i lf i s h u t = w h e t h e rii st h ef i r s ti t e mi nt h et a i l n e w n o d e = c u i m a f i a ( n e w n o d e ，m f i ，i s h u t ) ) i f ( i s h u ta n da l le x t e n s i o n sa r ef r e q u e n t ) s t o ps e a r c ha n dg ob a c ku ps u b t r e e i f ( ci sal e a f a n dc h e a di sn o ti nm f i ) a d dc h e a dt om f i 璺兰笙塑塑鍪堡蓬塑堕整笙堕 第三章新剪枝策略n t e p 3 1 新剪枝策略原理： 在这篇文章中提出了一个不同于以往的新的剪枝策略n t e p ( n o d et a i l e q u a l sp r u n i n g ) 。根据我们的观察，在语法树中的节点n ，假设 x i ，i j j 是节点n 的头部，y 是节点n 的尾部中任1 + 个元素( y g n t a i l ) 。对于节点y ，如果有t ( x ，y ) = t ( x ，i i ，y ) ，那就意味着任何包含x 和i i 的事务也必然包含y 。从另一方面说， 不存在这样的事务，它包含x 和i i 但是不包含y 。由此，我们可以剪掉所有的 以y 为根节点，头部为( x ，i j ，y ) 的子树，其中i j 可以是任何c ( x ) 中不等于i 。的元 素即i j m _ c ( x ) 且i j i i 。 例如，对于在表1 6 1 中的事务数据，我们构造如图1 6 2 的语法树。在节 点1 2 ，节点的头) b ( n u l l ，1 2 ) ，节点的尾部为 1 1 ，1 3 ，1 4 ，1 5 ) ，对于节点尾部中元素 1 4 ，有t ( n u l l ，1 2 ，1 4 ) = t ( n u l l ，1 4 ) 等于2 。所以，我们可以剪掉整个以1 4 为根节点 的子树和以( i l ，1 4 ) 和( 1 3 ，1 4 ) 为根节点的子树。这种剪枝策略同样也可以应用在其 它的节点。 如图1 6 2 所示的语法树在应用n t e p 剪枝策略进行剪枝后，结果如下图 3 1 1 所示： 1 2 1 1 ，i s ，1 4 ，1 5 ， 孓 ，level o 。睾三；= b “( i s , 1 4 i , i s ) b u “1 5 弋1 5i ( 1 2 ，1 0 1 3 ，1 4 ，1 5 ( 1 2 ，i s ) 1 4 ，1 5 ) 0 2 ，1 0 1 5 1 ( 1 2 ，l s ) ( 1 l ，i s ) ( 1 1 ，1 4 ) ( i i i s ) ( i s ，u ( i s ，i s ) ( 1 4 ，1 5 ) 岁1 1 憋= b 山攀x b 山1 5 h 絮“1 3 山1 1 1 4 1 5 ( i s , l t , l s ) ( 1 2 ，i i ，i s ，1 4 ) ( 1 2 ，i l ，i s ，l s ) ( 1 2 ，i t ，i “i s ) ( 1 2 ，i s ，1 4 ，i s )( 1 1 , 1 3 ，1 4 ，1 5 ) 所有可以用n t e p 策略剪掉的分枝都已用黑体表示。 图3 。1 1 用于挖搠频繁项熊的剪授策略 由图3 1 1 可以看出n t e p 可以有效地剪掉大