（计算机软件与理论专业论文）fminer：一种新的频繁项集挖掘算法.pdf

搠钾rj 尢掌f m i n e 。：一种新的频繁项集挖掘算法 兰州大学硕士学位论文 摘要 频繁项集挖掘是一类重要的数据挖掘问题，可以广泛应用在关联规则挖掘、 相关性分析、入侵检测、序列模式、分类和聚类等多种数据挖掘任务中。本文对 大量频繁项集挖掘算法进行了深入的研究与分析，主要分析了不同算法中事务数 据库在内存中的存储形式，以及各种有效的实现技巧。特别对多种前缀树型结构 进行了分析比较，分析了各自的特点以及内存占用情况。 本文提出了一种新的频繁项集挖掘算法f m i n e r ，该算法使用了两种新 的数据结构：f p f o r e s t 以及a f p t r e e 。a f p t r e e 构建时，频繁1 项集按支持 度递增的顺序排列，遍历方式采用自顶向下深度优先的策略。a f p t r e e 的根 是一个可以标识这一棵树的具体的项。一个事务数据库在内存中要用多棵 a f p t r e e 存储，这些a f p - t r e e 构成f p f o r e s t 。 在f m i n e r 算法的执行的过程中，每一次递归都要牵涉到a f p t r e e 的构建 与释放，在这一过程中要频繁地申请与释放内存，造成程序效率的下降。为了解 决这一问题，本文设计了高效内存管理器( 玎，m m ) 来负责内存单元的申请与释 放。 实验结果表明a f p t r e e 和f p f o r e s t 是两种有效的数据结构，f - m i n e r 算法 是一个高效的频繁项集挖掘算法。 关键词：频繁项集挖掘、f m i n e r 算法、a f p t r e e 、f p f o r e s t 、内存管理器 皙- 叶虫害f 埘i n 。，：一种新的频繁项集挖掘算法 兰卅大学硕士学位论文 a b s t r a c t f r e q u e n ti t e m s e t sm i n i n gi saf 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 nd a t am i n i n g a n dc a r lb e u s e di n m a n yd a t am i n i n ga p p l i c a t i o n s t h e s ea p p l i c a t i o n si n c l u d e a s s o c i a t i o nr u l e s a n a l y s i s ，c o r r e l a t i o n sa n a l y s i s ，c l a s s i f i c a t i o n ，c l u s t e r i n g ，o u t l i e r a n a l y s i sa n dm a n yo t h e ri m p o r t a n td i s c o v e r yt a s k s i nt h i sp a p e r ，w et a k ea ni n d e p t h s t u d yo nm a n yf r e q u e n ti t e m s e t sm i n i n ga l g o r i t h m s w ea n a l y z e dt h em e m o r y s 仃l l c t l l r eo ft r a n s a c t i o nd a t a b a s ei nd i f f e r e n ta l g o r i t h m s a sw e l la se a c he f f e c t i v e r e a l i z a t i o ns k i l l e s p e c i a l l y ，w ea n a l y z e dm a n yk i n d so fp r e f i x - t r e e ss t r u c t u r e s ，h a s c o m p a r e dt h ec h a r a c t e r i s t i ca n dt h eu s a g eo f m e m o r yo f e a c ho t h e r i nt h i sp a p e r ，w ep r e s e n tan e wa l g o r i t h m ，c a l l e df - m i n e r ，t om i n et h ec o m p l e t e s e to ff r e q u e n ti t e m s e t sb yp a t t e r ng r o w t h t h ef - m i n e ra l g o r i t h mu s e st w on e wd a t a s 仃u e t u r e s ，a f p - t r e ea n df p - f o r e s t , t or e p r e s e n tt h ec o n d i t i o n a ld a t a b a s e s w h e nw e c o n s t r u c ta na f p - t r e e t h ei t e m si nf r e q u e n t1 - i t e m s e ta r eo r d e r e di n f r e q u e n c y a s c e n d i n go r d e r t h ea f p t r e es 仰c t u r ei st r a v e r s e di nt o p - d o w nd e p t h - f i r s to r d e r t h er o o to f t h ea f p t r e ei sa l li t e mw h i c hc a ni d e n t i f yt h i st r e e i nf - m i n e r ，w en e e d m a n ya f p t r e e st os t o r eac o n d i t i o n a ld a t a b a s e ；t h e s et r e e sc o n s t r u c to n ef o r e s t ， c a l l e df p - f 0 r e s t t h ea l l o c a t i o na n dd e a l l o c a t i o no ft h ed y n a m i cm e m o r yh a v et ob er e a l i z e d t h r o u g ho p e r a t i o ns y s t e m i f t h ed y n a m i cm e m o r ym a n a g e m e n ti su s e df r e q u e n t l y , t h e r u n n i n gs p e e do ft h ep r o g r a mw i l ld e c r e a s e i no r d e rt os o l v et h i sp r o b l e mw e d e s i g n e dt h eh i 曲p e r f o r m a n c em e m o r ym a n a g e r 饵t h a ti sr e s p o n s i b l ef o rt h e a l l o c a t i o na n dd e a l l o c a t i o no f t h em e m o r yi nf - m i n e ra l g o r i t h m w et e s to u ra l g o r i t h mv e r s u ss e v e r a lo t h e ra l g o r i t h m so ns e v e r a ld a t a s e t s t h e e x p e r i m e n t a lr e s u l t ss h o wt h a to u ra l g o r i t h mi sa ne f f i c i e n ta l g o r i t h m k e yw o r d s ：f r e q u e n ti t e m s e t sm i n i n g ，f - m i n e r , a f p - t r e e ，f p f o r e s t , m e m o r y m a n a g e r i i 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立 进行研究所取得的成果。学位论文中凡引用他人已经发表或未发 表的成果、数据、观点等，均已明确注明出处。除文中已经注明 引用的内容外，不包含任何其他个人或集体已经发表或撰写过的科研 成果。对本文的研究成果做出重要贡献的个人和集体，均已在文中以 明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：鸯益叁 日期： 哪# 6 箩 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 敝储签导师繇李翌日期：趔6 f ：啕州= k 搴f _ m i n 。，：一种新的频繁项集挖掘算法兰州大学硕士学位论文 1 1 研究工作背景 第一章前言 数据挖掘是指从大量数据中挖掘出隐含的、先前未知的、对决策有潜在价值 的知识和规则的高级处理过程。它是人们长期对信息技术尤其是数据库技术研究 和开发的自然演化结果。通过数据挖掘，有价值的知识、规则或高层次的信息就 能从数据库的相关数据集合中抽取出来，并从不同角度显示，从而使大型数据库 作为一个丰富、可靠的资源为知识的提取服务。 数据挖掘的基本功能和它们可以发现的模式类型有：概念类描述、分类、 聚类、孤立点分析、关联规则分析、演变分析等。其中关联规则分析又称为关联 规则挖掘，它寻找给定数据记录集中数据项之间隐藏的关联关系，描述数据之间 的密切度。通过关联规则分析可以发现大量数据中项集之间有趣的关联规则或相 关联系。关联规则挖掘可以广泛的应用于购买行为分析、w e b 挖掘、入侵检测 等各种应用领域。 关联规则挖掘包含两个基本过程：一是找出满足最小支持度阈值的所有项 集：二是根据这些项集产生所有的强关联规则。其中第二个过程相对简单一些， 可以利用已知项集的支持度信息，直接通过计算置信度枚举出所有强关联规则， 因此挖掘关联规则过程的整体性能主要由第一步决定。所以关联规则挖掘问题的 核心是第一个过程，该过程称为频繁项集挖掘( f r e q u e n ti t e m s e t sm i n i n g ) 。自 从a g r a w a l 等【l 】于1 9 9 3 年通过研究顾客交易数据库中项集间的关系提出关联规 则分析问题后，频繁项集挖掘问题的研究就一直是关联规则分析研究领域的核 心，大部分的研究工作都围绕频繁项集挖掘问题进行。同时，频繁项集挖掘方法 并不只局限于挖掘关联规则，还可以广泛应用于相关性分析、孤立点分析、分类 和聚类等多种数据挖掘任务和入侵检测、序列模式、w e b 挖掘等多种数据挖掘 应用和数据分析处理任务中【4 6 】。 因此频繁项集挖掘问题是一个具有重要理论意义和广阔应用前景的研究课 题，受到理论界和产业界的广泛重视。如今，在数据库研究和应用领域已经形成 了一个以频繁项集挖掘问题为重点的重要研究方向。 1 ：萄甜r = 天霉 f 刈i 。：一种新的频繁项集挖掘算法兰州大学硕士学位论文 1 2 本文研究的内容和创新之处 本文的研究工作主要围绕三个主题展开：事务数据库在内存中的存储形式； 高效的频繁项集挖掘算法的设计与实现；高效内存管理程序的设计。本文的研究 主要成果和创新之处包括以下几个方面： 1 、设计了两种新的数据结构a f p t r e e ( a s c e n d i n gf p t r e e ) 和f p f o r e s t ( f r e q u e n tp a t t e mf o r e s t ) ，其中f p f o r e s t 结构是由多棵a f p t r e e 构成的， a f p t r e e 是基于f p t r e e 的一个变种。在f p f o r e s t 结构基础上找到了一种新的 频繁项集挖掘算法f m i n e r 。该算法使用深度优先的搜索策略，采用模式增长的 方式，以a f p t r e e 为单位进行频繁项集挖掘。 2 、gg r a h n e 和j z h u l l 4 】在2 0 0 3 年n f p - t r e e 进行了改造，添加了一个二维数 组存储频繁2 项集的支持度，新的数组技术改进了f p t r e e 的操作性能。利用 这项数组技术，使得每次递归时只需要扫描一遍f p t r e e ，这样就提高了 f p g r o w t h 算法的效率。并在这一数组技术的基础上对f p g r o w t h 算法进行了改 进，提出了新的频繁项集挖掘算法f p g r o w t h * 。在a f p t r e e 结构中采用了这一数 组技术，但是这里将二维数组改成了一维数组，存储一棵a f p t r e e 中除根节点以 外的节点项的支持度，维数组与f p t r e e 结构相结合，操作起来十分方便，效 果改进明显。 3 、在程序实现中，对内存空间的频繁申请与释放将会耗费大量的时间，为 了节约这些开销，本文设计了高性能的内存管理程序( h i i g h p e r f o r m a n c e m e m o r y m a n a g e r , i - i p m m ) ，实现了申请到的内存空间的高效利用，这样就可以避免每次 节点空间的申请与释放都要通过操作系统与硬件通讯，使程序的效率有了很大的 提高。 实验结果表明a f p t r e e 和f p - f o r e s t 是两种有效的数据结构，h p m m 起到 了高效内存管理的作用，f m i n e r 算法是一种高效的频繁项集挖掘算法。 1 3 本文的组织结构 第1 章：首先介绍了本文的研究工作的背景，接着阐述了本文的主要研究内 容、研究成果和创新之处。 ：菊州虫害 f - h i 。，：一种新的频繁项集挖掘算法兰州大学硕士学位论文 第2 章：频繁项集挖掘问题综述。首先简单介绍了数据挖掘技术的进展和主 要的数据挖掘任务；其次，认真分析了关联规则挖掘问题和基本过程；在此基础 上，详细描述了频繁项集挖掘问题，给出了相关术语的定义，探讨了基本的频繁 项集挖掘算法，介绍相关研究工作进展：对最大频繁项集挖掘问题和封闭频繁项 集挖掘问题进行了简单描述，并介绍了相关研究工作进展。 第3 章：f m i n e r 的设计与实现。对大量频繁项集挖掘算法进行研究，详细 分析了不同算法之问事务数据库在内存中的存储形式，特别对多种前缀树型结构 进行了比较，分析了各自的特点。在本章，吸取已有数据结构的优点，找到了两 种新的数据结构a f p t r e e 和f p f o r e s t ，在两种结构的基础上，提出了一种新的 高效的频繁项集挖掘算法一f m i n e r 算法。然后给出f m i n e r 算法描述、实现 与性能分析。 第4 章：性能测评。在这一章通过实验对比的方式验证了f m i n e r 算法具有 较高的性能，是一高效的频繁项集挖掘算法。 第5 章：总结和下一步研究工作展望。主要对本论文的研究工作进行总结， 并对下一步的工作进行展望。 鹄贷r ，：譬 f 州i n e 。：一种新的频繁项集挖掘算法兰州大学硕士学位论文 第二章频繁项集挖掘问题综述 频繁项集挖掘是一类重要的数据挖掘问题，可以广泛应用在关联规则挖掘、 相关性分析、入侵检测、序列模式、w e b 挖掘、分类和聚类等多种数据挖掘任 务中【2 l 】【2 4 】口5 1 4 6 1 。a g r a w a l 等1 1 】于1 9 9 3 年通过研究顾客交易数据库中项集间的关 系提出关联规则分析问题，同时研究结果表明，解决关联规则分析问题的核心是 挖掘出可以产生强关联规则的频繁项集合，因此，从1 9 9 3 年开始，频繁项集挖 掘问胚一直受到计算机科学理论研究的广泛重视，十多年来先后提出了多种有价 值的频繁项集挖掘算法和研究成果。 本章首先对数据挖掘技术进行探讨，并在此基础上结合关联规则分析对频繁 项集挖掘问题进行详细描述。然后对两种有重要影响的频繁项集挖掘方法进行了 详细的分析，接下来，介绍了目前现有的几种高效频繁项集挖掘算法。最后对最 大频繁项集挖掘问题和封闭频繁项集挖掘问题进行了简单描述，并介绍了相关研 究工作进展 2 1 关联规则分析和频繁项集挖掘问题描述 关联规则分析又称为关联规则挖掘，是发现大量数据中项目之间有趣的关联 或相关联系，是一类重要的数据挖掘任务。a g r a w a l 等1 1 于1 9 9 3 年首先研究了顾 客交易数据库中项集间的关联规则，进而提出了关联规则分析问题和频繁项集挖 掘问题。关联规则分析寻找给定数据记录集中数据项之间隐藏的关联关系，描述 数据之间的密切度，是数据挖掘中的重要功能之一。通过关联分析可以发现大量 数据中项集之间有趣的关联规则或相关联系。关联规则用于描述在同一个事件中 出现的不同项的相关性，更确切的说，关联规则是通过量化的描述对象x 的出 现对对象y 的出现有多大的影响。关联规则挖掘可以广泛的应用于购买行为分 析、w e b 挖掘、入侵检测等各种应用领域，受到广泛关注。关联规则挖掘的典 型例子是购物篮分析，该过程主要通过分析顾客采购的不同商品间的联系，发现 顾客的购买行为模式，帮助零售商制定相应的营销策略，如商品货架设计、库存 安排以及根据购买模式对用户进行分类等。 田埘j 走害 f m i 。：一种新的频繁项集挖掘算法兰州大学硕士学位论文 关联规则挖掘问题相关描述如下： 定义1 ：项目集合i = i 1 ，i 2 ，li m ) ，其中i k ( k = 1 ，2 ，lm ) 表示一个项目。集合 x 被称为项集，如果x i 。如果i x k ，则x 被称为k 项集。 定义2 ：事务t 是一个二元组：t = ( t i d ，x ) ，其中，t i d 称为事务号，是该事 务唯一的标识，x i 是一个项集。 定义3 ：事务数据库d 是i 上事务的集合：d = t t ，lt 。 其中t k ( k = l ，2 ，ln ) 是一个事务。d 中所有事务的事务号组成的集合称为事务号集合，记为：t i d s e t 。 定义4 ：项集x 的支持数是事务数据库d 中包含x 的所有事务数，记为： s u p p o r t ( x ) ，即s u p p o r t ( x ) = i t i d i ( t i d ，i ) d ，x i ) 1 。项集x 的支持度是d 中 包含x 的事务数占所有事务数的百分比，它是概率p ( x ) ，记为：s ( x ) ，即 s = p ( ) ( ) = 警。 如果事务数据库确定，支持度和支持数的概念具有相同的度量意义。因此本 文并不明确区分支持度和支持数，文中此后出现的支持度都具有支持数的意义， 并且本文统一使用s u p p o r t ( x ) 来表示支持度的概念。 定义5 ：一个关联规则是形如x j y 的蕴含式，这里x d ，y d ，并且 x n y = a 。规则x j y 在事务数据库d 中成立，具有支持度s ，则s 是d 中项 集x u y的支持度，记为 s u p p o r t ( x 辛n ， 即 ： s u p p o r t ( x j3 0 2 s u p p o n ( ) ( u - p ( ) ( uy ) 2 选产型； 规则x ；y 在事务数据库d 中具有置信度c ，其中c 是d 中同时包含x u y 的事务数占包含x 的所有事务数的百分比，它是条件概率p ( y i x ) ，记为 c o n f i d e n c e ( x j y ) 棚：c 砌妇( x j 驴3 篙 定义6 ：同时满足用户给定的最小支持度闽值和最小置信度阈值的关联规则 称为强关联规则。给定项目集合i 和事务数据库d ，以及最小支持度闽值九和最 胡计，j ：害 f m 。e r ：一种新的频繁项集挖掘算法兰州大学硕士学位论文 小置信度阈值6 ，d 中所有强关联规则构成的集合记为r ( d ，兄，j ) ，即： r ( d ，旯，5 ) = ( x = y i x ，y i a xn y = 囝as u p p o r t ( xu y ) a a c o n f i d e n c e ( xjy ) 占 关联规则挖掘就是在事务数据库d 中发现所有强关联规则的过程。 由上述定义可知，关联规则挖掘应当包含两个过程：一是找出支持度满足最 小支持度闽值的所有项集；二是根据这些项集产生所有的强关联规则。 在这两个过程中，第二步相对简单一些，一旦在事务数据库中找出支持度满 足最小支持度闽值的所有项集，由它们可以直接产生所有强关联规则。具体过程 为：对于每个支持度满足最小支持度阈值的项集x ，产生x 的所有非空子集； 对于x 的每个非空子集y ，给定最小置信度阈值6 ，如果：竺塑! ! ! 婴6 ，则输 s u p p o r t ( y ) 出规则“y j ( x - y ) ”。由于这些规则由满足最小支持度阈值的项集产生，每个规 则都满足最小支持度，同时这些又满足最小置信度，因此这些规则都是强关联规 则。 综上所述，由于在关联规则挖掘过程的第一步中已经计算了所有频繁项集的 支持度，第二步过程是一个利用已知支持度结果直接枚举所有强关联规则的过 程，因此挖掘关联规则过程的整体性能主要由第一步决定。所以关联规则挖掘的 核心是第一个过程，该过程称为频繁项集挖掘。 定义7 ：给定事务数据库d 和最小支持度闽值九，如果s u p p o r t ( x ) 九，则项 集x 被称为频繁项集，如果i x k ，则x 被称为频繁l 【- 项集。事务数据库中所 有的频繁项集的集合记为f ( d ，兄) ，即f ( d ，九) = x i ls u p p o r t ( x ) 九) 。 定义8 ：给定事务数据库d ，以及最小支持度阈值九，频繁项集挖掘是在事 务数据库d 中发现所有支持度满足晟小支持度阂值九的所有频繁项集的过程。 从以上定义和分析可知，频繁项集挖掘问题产生于关联规则分析问题，是关 联规则分析过程的重要组成部分，它的执行效率决定了关联规则分析过程的主要 效率。自从1 9 9 3 年提出关联规则分析问题后，频繁项集挖掘问题的研究就一直 是关联规则分析研究领域的核心，大部分的研究工作都围绕频繁项集挖掘问题进 萄计r 矢害 f m 1 n e ，：一种新的频繁项集挖掘算法兰州大学硕士学位论文 行。同时，频繁项集挖掘并不局限于挖掘关联规则，还可以广泛应用于相关性分 析、孤立点分析、分类和聚类等多种数据挖掘任务和入侵监测、序列模式、w e b 挖掘等多种数据挖掘应用和数据分析处理任务中。因此频繁项集挖掘问题的研究 也受到其他数据库研究领域的广泛重视，并逐渐在数据库研究领域形成了一个以 频繁项集挖掘问题为重点的研究方向。近年来，大多数重要的数据库、知识发现 和数据挖掘国际学术会( 如a c ms i g m o d 、a c ms i g k d d 、v l d b 、i c d e 等) 都设有频繁项集挖掘专题。 2 2 频繁项集挖掘的基本方法 频繁项集挖掘的主要问题是如何高效的找出事务数据库中所有频繁项集，它 是关联规则挖掘任务的核心。本节详细分析两种最有影响的频繁项集挖掘算法 a p r i o r i 算法和f p g r o w t h 算法。 2 2 1a p r i o r i 算法 最早的频繁项集挖掘算法是a g r a w a l 等于1 9 9 3 年提出的a i s t l l 算法，不久， a g r a w a l 等人又提出了a p r i o r i l 2 1 算法，该算法首次采用了一种基于频繁项集性质 的广度优先逐层搜索迭代方法。由于这种方法后来被理论研究领域广泛接受并采 用，因此，a p f i o r i 算法是公认的解决频繁项集挖掘问题最早的、最有影响的算 法。 a p r i o f i 算法主要基于频繁项集的两个性质，它们分别为： 性质l ：频繁项集的所有非空子集都是频繁的。 性质2 ：非频繁项集的所有超集都是非频繁的。 这两个性质实际上反映的是同一个事实的两个不同侧面，它们是频繁项集固 有的特性。因此两个性质可以统称为a p f i o r i 性质，a p d o r i 性质基于如下观察： 根据频繁项集定义，如果项集x 不满足最小支持度阀值九，则x 不是频繁的， 即s u p p o r t ( x ) a 。如果将项a 添加到x ，则结果项集( 即x ua ) 不可能比x 更频 繁出现。因此，x u a 也不是频繁的，即s u p p o r t ( x ua ) 九。 a p r i o d 性质是反单调( a n t i m o n o t o n e ) 的，意指如果一个集合不能通过测试， 则它的所有超集也都不能通过相同的测试。称它为反单调，是因为在通不过测试 的意义下，该性质是单调的。 鹄竹r ，：害f m i n e r ：一种新的频繁项集挖掘算法 兰州大学硕士学位论文 算法 输入 输出 方法 1 ： 2 ： 3 ： 4 ： 5 ： 6 ： 7 ： 8 ： 9 ： 1 0 ： 1 1 ： a p r i o r i 使用根据候选生成的逐层迭代找出频繁项集 事务数据库d ，项目集合i ，最小支持度阈值九 d 所有频繁项集上 工= f i n d _ _ f r e q u e n t _ l i t e m s e t s ( d ) ； f o r ( k = 2 ；l t - o ；抖+ ) = a p r i o r i _ g e n ( l k 4 ；九) ； f o re a c ht r a n s a c t i o nr df # s c a ndf o rc o u n t s c f = s u b s e t ( c k ，f ) ；g e tt h es u b s e t so f t t h a ta r ec a t l d i d a t e s f b re a c hc 弧d 诩【a t ec c t c c o u n t + 十： l k = c c 剐c ，c o u n t 九) ) r e t u r nl = u k l k ； p r o c e d u r ea p r i o r i _ g e n ( l k - _ ，：f r e q u e n t ( k - i ) 一i t e m s e t s ；m i n s u p ：m i n i m u m s u p p o m 1 f o re a c hi t e m s e th l k - i 2 ：f o re a c hi t e m s e t 2 e l k - i 3 ： i f ( f ，【1 = j 2 【1 】) ( z j 2 1 = 1 2 1 2 ) ( f j 陆2 】= t 2 k - 2 1 ) ( h k - 1 1 2 k 一1 】) 4 ：t h e n 5 ： c = h x l 2 ；j o i ns t e p ：g e n e r a t ec a n d i d a t e s 6 ： i f h a s _ i n f r e q u e n ts u b s e t ( c ，l - t ) t h e n 7：delete c ： r u n es t e p ：r e l n o v eu n f r u i t f u lc a n d i d a t e 8 ： e b e a d d c t oc k ； 9 ：， 1 0 ：r e t u r nc t ； p r o c e d u r eh a si n f r e q u e n t _ s u b s e t ( c ：c a n d i d a t ek - i t e m s e t ；l k - ：f f e q u e m ( k - i ) i t e m s e t s ) ； 1 ：f o re a c h 陋1 ) - s u b s e tso f c 2 ：i f s 芒厶1t h e nr e t u r nt r u e ； 3 ：r e t u r nf a l s e ； 图1a p r i o r i 算法中挖掘所有频繁项集的伪代码 8 ， ；暂- 叶虫害 f m i n e 。：一种新的频繁项集挖掘算法兰州大学硕士学位论文 a 研o r i 算法采用逐层搜索迭代的方法，即频繁( 缸1 ) - 项集上k 1 用于搜索频繁 肛项集厶。首先，找出所有的频繁1 项集，该集合记为。三，用于找频繁2 - 项 集幻，而幻用于找厶。如此下去，直到找到所有的频繁项集。找每个厶需要 扫描一次数据库。 图1 给出了a p r i o r i 算法中挖掘所有频繁项集的伪代码。 在主程序中，第一步首先扫描整个交易数据库d ，统计每个项目( i t e m ) 的支 持数，计算其支持度，支持度大于等于最小支持度九的，将此项目构成的集合 放入到三，中；从第2 步到第1 0 步，用( k - 1 ) 频繁项集构成的上川生成候选集的集 合( c a n d i d a t ei t e m s e t s ) c k ，以便从中生成“，其中a p r i o r ig e l l 函数用来从l k - i 中 生成，然后对数据库进行扫描( 第3 步) ，对于数据库中的每一个事务，s u b s e t 函 数用来发现此事务包含的所有的候选集( 第5 步) ，并为这些候选集的计数器加1 ( 第 6 7 步) 。最后满足九的候选集被放入至1 l k 中。 a p r l o r i g e n 过程完成两种操作，连接( j o i n ) 和剪枝( p r u n e ) 。在连接运算步骤 中，l k - i 与l k 一1 进行连接运算生成潜在的候选集( 1 5 步) ，条件l l k - 1 1 2 k - 1 保证 不会有重复的候选集生成( 第3 步) 。在剪除步骤中( 6 7 步) ，a p r i o r i 性质，删除那 些存在子集不是频繁项目集的候选集，测试子集是否为频繁项目集由过程 h a s _ i n f r e q u e n t _ s u b s e t 完成。 2 2 2f p g r o w t h 算法 在数据量很小的情况下，a p f i o r i 算法的候选产生- 检查的方法大幅度压缩了 候选项集的大小，取得了很好的性能。但是当频繁项集数量很大的时候，a p d o r i 算法的如下两种开销将会是十分庞大。 产生大量的候选项集。例如，如果有1 0 4 个频繁1 项集，则算法会产生 多达1 0 7 个候选2 项集合，并对它们进行频度计算。 频繁扫描数据库。对于长度为m 的频繁项集需要枚举出所有可能的2 m - 2 个子集并逐一检测，当m 较大时，会出现组合爆炸，而导致算法效率底 下或无法计算。 为此，一些学者提出了深度优先产生候选项集的策略，利用这种策略可以有 效的减少候选项集的数量，在一定程度上可以解决上述存在问题。因此受到广泛 的关注。 鹄州虫害 f m i 。e r ：一种新的频繁项集挖掘算法兰州大学硕士学位论文 最早的深度优先算法是由z a k i 等于2 0 0 0 年提出的e c l a t 6 】算法，其后许多 学者提出了基于深度优先策略的不同算法，其中j i a w e ih a n 等人2 0 0 0 年提出的 f p g r o w t h 算法】最有影响。 f p g r o w t h 算法的全称为频繁模式增长算法( f r e q u e n t p a t t e r ng r o w t h ) ，采 取如下分治策略：将提供频繁项集的数据库压缩到一棵频繁模式树( f p t r e e ) 中，但仍保留项集之间的关联信息；然后，将这种压缩后的数据库分成一组条件 数据库( 一种特殊类型的投影数据库) ，每个关联一组频繁项，并分别挖掘每个 数据库。同时该算法基于深度优先的思想，在将压缩后的数据库分成一组条件数 据库时，选用支持度最小的频繁项对数据库进行划分( 首先生成这些频繁项的条 件f p t r e e ) ，提供了良好的选择性，大幅度降低了算法的搜索开销。 f p t r e e ( f r e q u e n t p a t t e r nt r e e ) 是一种特殊的数据存储结构，它的生成步骤 如下： 】、扫描事务数据库】次，产生所有的频繁】一项集，并得到它们的支持度计 数，由这些频繁l 一项集构成的集合计为l ，l 中的项集按支持度递减的顺序排列。 2 、创建f p t r e e 的根节点，用 n u l l 标记。第二次扫描数据库d 。对于每个 事务，取出它的所有频繁项构成频繁项表( 按l 中的次序排序，即按支持度递减 次序排序) ，同时对频繁项表创建一个分支。在创建新分支的过程中，如果该分 支与已存在的某些分支具有相同的前缀，则找到具有最大共同前缀的分支，并进 行合并，具体的方法是：沿共同最大前缀上的每个节点的计数增加1 ，对跟随在 共同最大前缀之后的项创建节点并链接到共同最大前缀分支后。如此以至，直到 访问完数据库d 中所有的事务。 为方便进行树的遍历，创建一个项头表，使得每个项通过一个节点链指向它 在树中的出现位置。 r i d 项集 l o o a ，b ，c ，e ，g ) 2 0 0 a ，b ，c ，d ，e ) 3 0 0 a ，d ) 4 0 0 b ，d ，f 5 0 0 b ，c ，e ，f ) 表1 倒1 的事务数据库 鞠计r 虫掌 f m i 。r ：一种新的频繁项集挖掘算法兰州大学硕士学位论文 下面通过一个例子来分析f p t r e e 的结构和它的生成过程。 例1 ：表1 表示的事务数据库d 有5 个事务，7 个项目，t i d 标记事务编号， 项目集i = a ，b ，c ，d ，e ，f ，g ) ，设最小支持度阈值为3 ，则第一次扫描数据库产生 频繁1 - 项集合l = a ，b ，e ，d ，e ，f ) ，因为项目g 的支持度为l ，不是频繁项，所以 不在l 中。 然后，f p t r e e 构造如下：首先，创建树的根节点，用“n u l l ”标记。第二次 扫描数据库d 。对于每个事务，取出它的所有频繁项构成频繁项表( 按l 中的次 序排序，即按支持度递减次序排序) ，同时对频繁项表创建一个分支。例如，对 于第一个事务“t 1 0 0 ： a ，b ，c ，e ，f ，g ) ”，它的频繁项表为 a ，b ，c ，e ，f ) ，构造 f p t r e e 的第一个分支 。该分支具有5 个节 点，其中，a 作为根的子女链接，b 链接到a ，c 链接到b ，。然后访问第二个 事务“t 2 0 0 ： a ，b ，c ，d ，e ) ”，t 2 0 0 的频繁项表为 a ，b ，c ，d ，e ) ，形成f p - t r e e 的一个新分支 ，其中，a 链接到根，b 链接到 a ，。然而，该分支与已存在的分支 共享 前缀 。这样，我们将节点a 、b 、c 的计数分别增加1 ，并创 建一个新分支 ，将它作为分支 的子女分支。 如此以至，生成如图2 所示的f p t r e e 。 图2 表1 所示事务数据库的f p - t r e e 蔺钾r 虫害 f m i n e 。：一种新的频繁项集挖掘算法兰州大学硕士学位论文 在f p t r e e 上进行频繁项集挖掘的过程如下：由长度为l 的频繁项集( 初始 后缀模式) 开始，构造它的条件模式基( 一个“子数据库”，由f p t r e e 中与后缀 模式一起出现的前缀路径集组成) 。然后，构造它的( 条件) f p - t 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 的过程为： l 、扫描事务数据库d 一次。生成所有频繁项的集合f 和这些频繁项的支持 度。对f 中的频繁项按支持度降序排序，结果为频繁项表l 。 2 、创建f p t r e e 的根节点，以“n u l l ”标记它。对于d 中每个事务t r a n s ，执 行：选择t r a n s 中的频繁项，并按l 中的次序排序。设排序后的频繁项表为 p i p ， 其中p 是第一个元素，而p 是剩余元素的表。调用过程i n s e r t _ t r e e ( p i p ，1 ) 。该 过程的伪代码如图3 所示。 过程：i n s e r t _ t r e e ( p i p ，乃 输入：频繁项表为 p i p 】，f p t r e et 输出：f p t r e et 方法： l ：i f 树丁有子女n 使得n i t e m n a n l e = p i t e m - l - l a m e t h e n 2 ：n c o u n t = n c o u n t + l ： 3 ：e l s e 4 ： 创建一个新节点n ，n c o u n t ：= l ： 5 ：将节点n 链接到它得父节点死 6 ：通过节点链结构将其节点n 链接到具有相同i t e m - n a m e 的节点； 7 ： ) 8 ：i fp 0 t h e n 1 0 ：调用i n s e r t _ t r e e ( p , n ) ； 图3f p - g r o w t h 算法中i n s e r t _ t r e e 过程的伪代码 f p g r o w t h 算法中，在f p - t r e e 上进行频繁项集挖掘主要是通过调用 蔺押r 虫害 f - m i 。e r ：一种新的频繁项集挖掘算法 兰州大学顶士学位论文 f p - g r o w t h ( f p t r e e ，n u l l ) 来实现。该过程的伪代码如图4 所示。 过程：f p - g r o w t h ( t r e e ，) 使用f p t r e e ，通过模式增长挖掘频繁项集。 输入：f p t r e et r e e ，节点c 输出：所有频繁项集f ( d ，五) 方法： 1 ：i f t r e e 含单个路径p t h e n 2 ： f o r 路径p 中节点的每个组合p 3 ： 产生项集p u a ，其支持度等于d 中节点的最小支持度； 4 ： f ( d ，五) = f ( d ，2 ) u p u 口) 5 ：e l s e f o r 在t r e e 的头部的a 6 ： 产生一个项集p = a ；u ，s u p p o r t ( 3 ) = s u p p o r t ( a j ) ； 7 ： 构造b 的条件模式基； 8 ： 构造p 的条件f p t r e et r e e 口： 9 ： i f t r e e 口o l o ： 调用f p g r o w t h ( t r e e 口，) ； 1 1 ：) 图4f p ，g r o w t h 过程的伪代码 f p - g r o w t h 算法将发现长频繁项集的问题转换成递归地发现一些短的项集， 然后连接后缀。它使用最不频繁的项作后缀，提供了好的选择性。该方法大大降 低了搜索开销。 f p g r o w t h 算法采用f p t r e e 存储结构，将事务数据库进行有效压缩，提高 了算法的空间效率。当数据库较小时，f p ，t r e e 可以基于内存实现，省去了多次 访问数据库带的i o 时间开销，大幅度提高了算法的时间效率。当数据库很大时， 构造基于内存的f p - t r e e 是不现实的。一种有效的改进是：首先将数据库划分成 投影数据库的集合，然后在每个投影数据库上构造f p t r e e 并挖掘它。该过程可 ：钨w l 矢孽f m i 。i 一种新的频繁项集挖掘算法兰州大学硕士学位论文 以递归使用，直到投影数据库的f p t r e e 可以在内存中存储。 对f p g r o w t h 方法的性能研究表明：对于挖掘长的和短的频繁项集，它都是 有效的和可伸缩的，执行效率大约比a p r i o r i 算法快一个数量级。 f p g r o w t h 算法的不足之处是：构造条件f p t r e e 的c p u 开销和存储开销很 大。另外，f p g r o u c h 算法的作者申明该算法不会产生任何的候选项集，但学术 界对此存在不同的看法，认为条件f p t r e e 生成的过程中产生了大量的候选项集， 并对这些候选项集进行了频度计算，所以不会产生任何的候选项集的说法是不确 切的