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

兰州大学硕士研究生毕业论文 摘要 频繁项集挖掘可以广泛应用在关联规则挖掘、相关性分析、入侵检测、序列 模式、分类和聚类等多种数据挖掘任务中。迄今为止已经提出了许多高效的频繁 项集挖掘算法。本文对大量频繁项集挖掘算法进行了深入的研究，重点分析了几 种经典模式增长算法中事务数据库在内存中的存储结构，以及各种有效的实现技 术，并在此基础之上提出了新的算法。 首先，对关联规则和频繁项集挖掘的相关概念、研究现状及所面临的问题进 行了分析研究。并对几种典型的频繁项集挖掘算法进行了详尽分析，比较了它们 各自的优缺点及适用环境。 其次，对大量已有算法中事务数据库在内存中的存储结构，以及各种有效的 实现技术进行了详细研究，重点分析了几种经典模式增长算法采用的数据结构和 挖掘策略。 最后，对三种采用的技术一f p - t r e e 、f p - a r r a y 以及b i t m a p c o u n t 进行了详尽 地探讨，并在此基础上设计出了一种新的频繁项集挖掘算法m s m i n e r 。 实验结果表明m s m i n e r 算法不仅在算法执行性能上更优，而且在内存消耗和 可扩展性上都有较好的表现，是一个高效的频繁项集挖掘算法。 关键词：频繁项集挖掘、m s - m i n e r 算法、f p - t r e e 、f p a r r a y 、b i t m a p c o u n t 兰州大学硕士研究生毕业论文 a b s t r a c t f r e q u e n t i t e m s e t s m i n i n g c a nb ew i d e l yu s e di n m i n i n ga s s o c i a t i o nr u l e s ， c o r r e l a t i o n a n a l y s i s ，i n t r u s i o nd e t e c t i o n ，s e q u e n c e m o d ea 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 ga n do t h e rd a t am i n i n gt a s k s s of a rt h e r eh a v eb e e nm a n ye f f i c i e n tf r e q u e n t i t e m s e t sm i n i n ga l g o r i t h m s i nt h i st h e s i s ，m 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 sa r e s t u d i e di nd e p t h e s p e c i a l l y , t r a n s a c t i o nd a t ab a s e ss t o r a g es t r u c t u r ea n ds o m ee f f e c t i v e t e c h n i q u e si nd i f f e r e n tg r o w t ha l g o r i t h m sa r ea n a l y z e ds y s t e m a t i c a l l y a n dt h e n ，an e w a l g o r i t h mi si n t r o d u c e d f i r s t l y , w ea n a l y z et h ec o n c e p t sr e l a t e da s s o c i a t i o nr u l e sa n df r e q u e n ti t e m s e t s m i n i n g ，t h ep r e s e n tr e s e a r c ha n dt h ef a c i n gp r o b l e m s ，s t u d ys e v e r a lt y p i c a lf r e q u e n t i t e m s e t sm i n i n ga l g o r i t h m sa n dc o m p a r et h e i rr e s p e c t i v ea d v a n t a g e sa n da p p l i c a t i o n c o n d i t i o n s s e c o n d l y , t h ed a t as t o r a g es t r u c t u r e sa n dt h ee f f e c t i v et e c h n i q u e so fal a r g en u m b e r o fa l g o r i t h m sh a v eb e e ns t u d i e dd e t a i l e d l y , a n dt h ed a t as t r u c t u r e sa n ds t r a t e g i e so ft h e v a r i o u sg r o w t ha l g o r i t h m sa r ea n a l y z e ds p e c i a l l y f i n a l l y , t h et h r e ea p p l i c a t i o n s f pt r e e ，f p - a r r a ya n db i t m a p - c o u n ta r ee x p l a i n e d i nd e t a i l b a s e do nt h et h r e et e c h n i q u e s ，an e wf 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 m s - m i n e ri sd e s i g n e d e x p e r i m e n t a lr e s u l t ss h o w t h a to u rm e t h o di sa ne f f i c i e n ta l g o r i t h m ，n o to n l yi nt h e w o r k i n ge f f i c i e n c yb u ta l s oi nt h em e m o r yc o n s u m p t i o na n ds c a l a b i l i t y 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 , m s m i n e r , f p - t r e e ，f p - a r r a y , b i t m a p c o u n t i i 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立 进行研究所取得的成果。学位论文中凡引用他人已经发表或未发表 的成果、数据、观点等，均已明确注明出处。除文中已经注明引用 的内容外，不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究成果做出重要贡献的个人和集体，均已在文中以明确方 式标明。 本声明的法律责任由本人承担。 论文作者签名：五驻 日期： 砝互里 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅：本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：i 塞导师签名：区4 = 琏! 选日期：论文作者签名：3 f 墨 导师签名：匕琏! 坠日期： 兰州大学硕士研究生毕业论文 第一章前言 1 1 研究工作背景 人类正在进入信息社会已是不争的事实。信息化给各国的社会经济发展带来 了新的机遇和挑战，并将对未来的社会发展产生深远的影响。随着信息技术的迅 猛发展使得信息采集和传播的速度以及规模达到空前的水平，技术上实现了全 球的信息共享。但与之而来的问题和“副作用”是：汹涌而来的信息有时使人无 所适从，从浩如烟海的信息海洋中迅速而准确地获取自己最需要的信息，变得非 常困难。这种现象被称为“信息爆炸”，又被称为“信息过剩”、“信息泛滥”。如 何改变“数据丰富但知识贫乏”的局面，使信息资源得到有效的利用，提高信息 的质量，已经成为一个世界性难题。 知识发现( 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 ，k d d ) 和数据挖掘( d a t am i n i n g ， d i v 0 技术正是在上述的应用要求下产生的。数据挖掘一词是在1 9 8 9 年于美国底特 律市召开的第1 1 界国际联合人工智能学术会议上首次提出的。许多人把数据挖掘 视为另一个常用的术语数据库中的k d d 的同义词，常常混用。而另一些人只是 把数据挖掘视为k d d 的一个基本步骤。1 9 9 5 年，第一届知识发现和数据挖掘国际 学术会议在加拿大蒙特利尔召开，从此，每年主办一次k d d 国际学术会议，将 k d d 和d m 方面的研究推向了高潮，于是“数据挖掘”一词开始流行。 数据挖掘是指从数据库或数据仓库的大量数据中揭示出隐含的、先前未知的、 潜在有用的信息的非平凡过程。它作为知识发现过程中一个特定的步骤，是一系 列技术及其应用，或者说是对大容量数据及数据之间关系进行考察和建模的方法 集。它的目标是将大容量数据转化为有用的知识和信息。目前，数据挖掘技术已 经在许多行业都得到应用并取得了一定的实效。它不但可以帮助人们从数据库， 特别是从数据仓库的相关数据中提取出感兴趣的知识、规律或更高层次的信息， 而且也可以帮助人们从不同程度上去分析它们，从而可以更有效地利用数据库或 数据仓库中的数据。它不仅可以用于描述过去数据的发展过程，而且还能进一步 预测未来的发展趋势。它是人们长期对信息技术尤其是数据库技术研究和开发的 自然演化结果。通过数据挖掘，有价值的知识、规则或高层次的信息就能从数据 库的相关数据集合中抽取出来，并从不同角度显示，从而使大型数据库作为一个 兰州大学硕士研究生毕业论文 丰富、可靠的资源为知识的提取服务。 数据挖掘功能大略可以归纳为6 种：概念描述( c o n c e p td e s c r i p t i o n ) ；关联分 析( a s s o c i a t i o n a n a l y s i s ) 分类和预测( c l a s s i f i c a t i o na n dp r e d i c a t i o n ) ；聚类分析 ( c l u s t e r i n g a n a l y s i s ) ；异类分析( o u t l i e r a n a l y s i s ) ：演化分析( e v o l u t i o n a n a l y s i s ) 。在数据挖掘的上述6 种功能中，当前研究较多也较为成熟的是关联分析，它 是由a g r a w a l 等【1 j 在1 9 9 3 年首先提出的。关联分析是指从给定的数据集中发现关 联规则，这些规则反映了大量数据中项集之间有趣的联系。 关联规则挖掘包含两个基本过程：一是找出满足最小支持度阈值的所有项集； 二是根据这些项集产生所有的强关联规则。其中第二个过程相对简单一些，可以 利用已知项集的支持度信息，直接通过计算置信度枚举出所有强关联规则，因此 挖掘关联规则过程的整体性能主要由第一步决定。所以关联规则挖掘问题的核心 是第一个过程，该过程称为频繁项集挖掘f i m ( 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 等【1 1 通过研究顾客交易数据库中项集间的关系提出关联规则分析问题 后，频繁项集挖掘问题的研究就一直是关联规则分析研究领域的核心，大部分的 研究工作都围绕频繁项集挖掘问题进行。同时，频繁项集挖掘方法并不只局限于 挖掘关联规则，还可以广泛应用于相关性分析、孤立点分析、分类和聚类等多种 数据挖掘任务和入侵检测、序列模式、w e b 挖掘等多种数据挖掘应用和数据分析 处理任务中l ，明。 因此频繁项集挖掘问题是一个具有重要理论意义和广阔应用前景的研究课 题，受到理论界和产业界的广泛重视。如今，在数据库研究和应用领域已经形成 了一个以频繁项集挖掘问题为重点的重要研究方向。 1 2 本文研究的内容和创新之处 本文研究的内容和创新之处有以下几点： 1 、本文对大量已有算法进行了详细研究，重点分析研究了几种有代表性的模 式增长算法采用的数据结构和挖掘策略。 2 、对采用的三种技术一f p - t r e e 、f p _ a r r a y 以及b i t m a p - c o u n t 进行了详尽的 探讨。 3 、提出了一种新的频繁项集挖掘算法埘s m i n e r 。该算法使用f 卜t r e e 数据 结构存储数据库，在挖掘f p t r e e 的过程中使用- r f p - a r r a y 以及b i t m a p - c o u n t 技 2 兰州大学硕士研究生毕业论文 术。构建新的子f p _ t r e e 时，它的项头表由父f p t r e e 的f p - a r r a y 直接得出，节约 了计算头表项的时间。当一个树头表里的项数小于等于设定常数b i t m a p c o u n t 时， 采用b i t m a p - c o u n t 技术。这样，用b i t m a p - c o u n t 技术代替了构造底层f p t r e e 树以 及用f p - g r o w t h 挖掘频繁项，不仅有效地提高了算法的性能，而且减少了内存的需 求。 1 3 本文的组织结构 第1 章：介绍了本文的研究工作的背景，阐述了本文的主要研究内容和创新之 处。 第2 章：相关概念及研究现状。首先对关联规则挖掘问题和频繁项集挖掘问题 进行了探讨，并给出了相关术语和概念。分析研究了几种典型的频繁项集挖掘算 法，比较了它们各自的优缺点及适用情况。 第3 章：m s m i n e r 的设计与实现。对大量频繁项集挖掘算法进行研究，重点分 析了几种典型模式增长算法采用的不同策略，分析了各自的特点。吸取已有数据 结构和挖掘策略的优点，对三种采用的技术f p - t r e e 、f p - a r r a y 以及b i t m 印c o u n t 进行了详细的探讨，并在此基础上设计出了一种新的高效的频繁项集挖掘算法一 m s m j n e r 算法。 第4 章：性能测评。通过实验对比的方式验证了m s m i n e r 算法具有较高的性能， 是一高效的频繁项集挖掘算法。 第5 章：总结和下一步研究工作展望。主要对本论文的研究工作进行总结，并 对下一步的工作进行展望。 3 兰州大学硕士研究生毕业论文 第二章相关概念及研究现状 2 1 关联规则综述 关联规则数据挖掘( 简称关联规则挖掘) 就是从大量的数据中挖掘出有价值 的描述数据项之间相互联系的有关知识。随着收集和存储在数据库中的数据规模 越来越大，人们对从这些数据中挖掘相应的关联知识越来越有兴趣。例如：从大 量的商业交易记录中发现有价值的关联知识就可以帮助进行商品目录的设计、交 叉营销或帮助进行其它有关的商业决策。挖掘关联知识的一个典型应用实例就是 市场购物分析，该过程主要通过分析顾客采购的不同商品间的联系，发现顾客的 购买行为模式，帮助零售商制定相应的营销策略，如商品货架设计、库存安排以 及根据购买模式对用户进行分类等。 自1 9 9 3 年a g r a w a l 等首先提出关联规则概念以来，关联规则挖掘便迅速受到数 据挖掘领域专家的广泛关注。在迄今十几年中，关联规则挖掘技术得到了深入的 发展。 2 1 1 关联规则相关概念 设i _ i l ，i 2 ，i 。) 是m 个不同项的集合。d 是所有事务的集合( 即事务数据库) ， 每个事务t 是一些项的集合，t 包含在i 中， z p t - - q i ，并且每个事务可以用唯一的标 识符t i d 来标识。 【定义2 1 】设x 为i 中某些项的集合，简称为项集( i t 。q 驴e t ) ，如果x - - t ，则称事务t 包含x 。 啦 关联规则表示为：x 穹y 的蕴涵式，这里x c l ，y c i ，并且x n y = o 。d 中的 规则x 辛y 是由支持度( s u p p o r t ) 和置信度( c o n f i d e n c e ) 来约束的。支持度表示规 则出现的频度，置信度表示规则的强度。具体描述是： s u p p o r t ( x 号y ) = p ( x u y ) c o n f i d e n c e ( x 番y 1 = p ( y i x ) 【定义2 2 】在进行关联规则挖掘时，要求用户预先设定支持度和置信度阈值，即 在挖掘过程中只产生满足这两个阈值要求的关联规则，对于这样的支持度和置信 度通常分别称为最小支持度( m i n i m u ms u p p o r t ) 和最小置信度( m i n i m u m 4 兰州大学硕士研究生毕业论文 c o n f i d e n c e ) ，对于满足最小支持度和最小置信度要求的关联规则称为强规则。 在本文中，为方便起见把支持度和置信度分别简记为s 和c ，最小支持度和最小 置信度分别简记为m i n s u p 和m i n c o n f ，它们的取值在0 到1 0 0 之间。另外d 中包 含的事务数表示为| d | ，x 中包含的项数表示为i x i 。 【定义2 3 】项集x 在d 中出现的频率，即d 中包含x 的事务t 的个数，称为x 在d 中 的支持数( s u p p o r tc o u n t ) ，简记为c o u n t 。 根据以上支持度和支持数的定义，可以得出某项集x 的支持数与支持度的关系 是c o u n t = s i d i ，另外与最小支持度相对应，把支持数阈值定义为最小支持数 ( m i n i m u ms u p p o r tc o u n o ，简记m i n c o u n t ，它和最小支持度的关系是m i n c o u n t = m i n s u p i d i 。 【定义2 4 】对于项集x ，如果x 中包含有k 个项，则x 称为k 项集。例如项集x = a ，b ) 就是一个2 项集。 2 1 2 挖掘关联规则的基本步骤 关联规则挖掘就是在事务数据库d 中找出满足用户给定的最小支持度m i n s u p 和最小置信度m i n c o n f 要求的关联规则，整个挖掘过程可分解为以下两步： ( 1 ) 找出事务数据库d 中所有支持度大于等于用户指定最小支持度的项集。支持 度不小于最小支持度的项集称为频繁项集。 ( 2 ) 利用频繁项集生成所需要的关联规则。对每一个频繁项集a ，找到a 的所有非 空子集a ，如果s u p p o r t ( a ) s u p p o r t ( a ) m i n c o n f ，就生成关联规则a 号( a - a ) ， s u p p o r t ( a ) s u p p o r t ( a ) l i p 规则a = 争( a - a ) 的置信度。 目前有很多产生频繁项集的算法，这些算法产生频繁k - 项集时，扫描数据库的 每个事务用以统计这些候选k 项集的支持度，并按照事务数确定的最小支持度在第 k 次迭代时找出所有频繁k _ 项集。然而，由于数据库的规模通常是非常大的，所以 在每次迭代时产生候选项集以统计其支持度是非常耗时的。因此，寻求频繁项集 的有效产生算法是问题的关键。事实上，在挖掘关联规则的整个执行过程中第一 个子问题是核心问题，而第二个子问题相对较为简单。因此挖掘关联规则过程的 整体性能主要由第一步决定。在后面的阐述中主要对第一个子问题进行详细分析， 该过程称为频繁项集挖掘。 5 兰州大学硕士研究生毕业论文 2 2 频繁项集挖掘问题描述 频繁项集挖掘问题的研究一直是关联规则分析研究领域的核心，大部分的研 究工作都围绕频繁项集挖掘问题进行。同时，频繁项集挖掘并不局限于挖掘关联 规则，还可以广泛应用在相关性分析、入侵检测、序列模式、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 等1 都设有频繁项集挖掘专题。 十多年来先后有多种有价值的频繁项集挖掘算法和研究成果。 2 2 1 频繁项集挖掘相关概念 【定义2 5 】给定事务数据库d 和最小支持度闽值m i n s u p ，如果s u p p o r t ( x ) 一 m i n s u p ， 则项集x 被称为频繁项集，如果i x f = k ，则x 被称为频繁k - 项集。事务数据库中所有 的频繁项集的集合记为f ，m i n s u p ) ，l l f f ( d ，m i n s u p ) = x - i s u p p o r t ( x ) 一 ；，m i n s u p ，则称项集x 为封闭频繁项集。 事务数据库d 中所有封闭频繁项集构成的集合记为c f i ，封闭频繁项集挖掘任 务的目的是找出d 中的c f i 。显然所有封闭频繁项集构成的集合c f i 是所有频繁项集 f ( d ，m i n s u p ) 的子集，c f i f ( d ，m i n s u p ) ，另外由定义可知所有最大频繁项集构成的 集合m f i 是所有封闭频繁项集构成的集合c f i 的子集，因此m f i 冬c f i f ( d ，m i n s u p ) 在一些中文参考文献中封闭频繁项集挖掘又被称为闭合频繁项集挖掘。本文 中统一使用术语封闭频繁项集挖掘。 封闭频繁项集挖掘的概念由p a s q u i c r 等嗍于1 9 9 9 年提出。由定义可知，任一频 繁项集合都是某个封闭频繁项集的子集，所以只要找到所有的封闭频繁项集，就 可以由它方便的找到所有的频繁项集。由于事务数据库d 中所有封闭频繁项集的规 模比频繁项集的规模要小几个数量级，因此可以将所有频繁项集的挖掘问题转化 为封闭频繁项集挖掘问题。另外，在挖掘过程中可以利用封闭频繁项集的一些特 7 兰州大学硕士研究生毕业论文 性进行搜索空间的剪枝，因此封闭频繁项集挖掘的效率远高于挖掘所有频繁项集。 与最大频繁项集挖掘方法相比，虽然事务数据库d 中封闭频繁项集的数目会大于最 大频繁项集的数日，但封闭频繁项集挖掘在找出事务数据库中所有的封闭频繁项 集的同时保持了项集所有的支持度信息，不会影响关联规则生成时规则置信度的 计算。因此，封闭频繁项集挖掘方法的研究受到数据挖掘研究和应用领域的高度 重视。 2 3 几种典型的频繁项集挖掘算法 因为本文只涉及到频繁项集挖掘算法，所以只介绍几种被公认的典型的频繁 项集挖掘算法。 2 3 1 两种经典的频繁项集挖掘算法 a p r i o r i 算法 最早的频繁项集挖掘算法是a j g r a w a l 等于1 9 9 3 年提出的算法t 1 1 ，：= ；k a g r a w a l 等人提出的a p r i 耐算法f 2 l ，该算法首次采用了一种基于频繁项集性质的广度优先逐 层搜索迭代方法。另外，m a n n i l a 等也在同一时期独立的提出了相同的技术方法【3 j 由于这种方法后来被理论研究领域广泛接受并采用，因此，a p r i o r i 算法是公认的解 决频繁项集挖掘问题最早的、最有影响的算法。 为了提高频繁项集逐层产生的效率，a p r i o r i 算法利用了两个重要的性质，用于 压缩搜索空间。 【性质2 1 】若x 为频繁项集，则x 的所有非空子集都是频繁的。 【性质2 2 】若x 为非频繁项集，则x 的所有超集都是非频繁的。 这两个性质是根据以下观察而得出的结论。根据频繁项集定义，若项集x 不满 足最小支持度阀值m i n s u p ， i p s u p p o r t ( x ) m i n s u p ，则x 不是频繁的。如果将项a 添 ：o n 至u x ，t i p s u p p o r t ( x 0 a ) m i n s u p ，则结果项集( b p x u a ) 不可能比x 更频繁出现，因 此，x u a 也不是频繁的。 算法：a p r i o r i 输入：事务数据库d ，最小支持度阈值m i n s u p 输出：d 所有频繁项集l 步骤： a p r i o r i 算法，根据候选产生逐层迭代找出所有频繁项集 8 兰塑盔堂堡主婴塞生望些堡塞一 1 ：l 1 ：s e a r c h _ f r e q u e n t _ 1 i t e m s e t s ( d ) ，找到d 中频繁l - 项集 “ 2 ：f o r 仪= 2 ；l b l d ；k + + ) 。 3 ： c i = a p d o d - g e n ( l k 1 ，m i n s u p ) 4 ： f o re a c ht r a n s a c t i o n st ed 。 5 ：c | = s u b s e t ( c k ，t ) 膈到候选项t 的子集 。 6 ：f o re a c hc a n d i d a t e sc ec , 子集检测 。 7 ：c c o u n t + + 0 8 ： 麓 9 ：l k 。 c e c i lc c o u n t m i n s u p ； 一1 0 ： ， ：n ：r e 细m l 。y j h 。，一。一；，。 岛，。，蠢 毪r 。 ? 。、i 。? o 一 & h 、 “5 一一 ”“” 。一 函数：s e a r c h _ f r e q u e n t1 i t e m s e t s ( d ) ，找到d 中频繁卜项集 箩i ：f o r c h t r a l l s a c t i o n s t d 。一一：5 冀。一。一“”：! ? ：2 ： f o r e a c hi t e m i k t 。 ； 。 ，3 ： i k c o u n t + + ； f 簟 14 ：l 1 = i e i i i c o u n t m i n s u p 4 ? 5 ： “ 。6 ：r e t u r nl 1 ： ； 。m 。自。j 。? m 。女一。一。一。j ? 一：c 一一一 函数：a p r i o r i g e n ( i a t ，m i n s u p ) 产生候选项集 。 。 il ：f o re a c h i t e m s e t l l e l i ， “ i 2 f o r e a c hi t e m s e t1 2 l k ； 。3 ： i f ( 1 1 【1 】= 1 2 【1 】) 八( 1 1 【2 】= 1 2 【2 】) 八a c h l k - 1 = i 2 k - t ) a ( 1 l 【k 】 1 2 【k 】) ，： i 。 2 “4 ：t h e n ； ；5 ： c = l l x l 2 ； ，连枝步，产生候选项 “ 16 ： i f i s _ i n e l u d e _ i n f r e q u e n ts u b s e t ( c ，功t h e n ! ，7 ：d e l e t ec ：剪枝步，删除无效的候选项 f、 + 8 ：e l s ea d d c t o c l + l ；， 9 ：， 1 0 ：r e t u r nc k l ； 兰州大学硕士研究生毕业论文 函数：i s _ i n c l u d e _ i n f r e q u e n t _ s u b s e t ( c ，l ) “1 ：f o r e a c hk - s u b s e tso f c 2 ： i f s 盛l kt h e n 判断是否是有效的候选项集 3 ： r e t u r nt r u e ； 4 ： r e t u r nf a l s e ；一 。： ， h ；。，：| ，、l ，# ，。z，、f 、。 i 。p t 。一二。# 图2 1a p r i o r i 算法 根据上面的算法描述可以看出，在a p r i o r i 算法中有两个关键的步骤，一是候选 项集的生成，二是候选项集的计数。对于前者采用的是拼接和剪枝的方法，即由 频繁低1 ) - 项集拼接生成候选k - 项集，然后再根据性质2 1 进行剪枝，删除候选l 【项 集那些子集不是频繁( k 1 ) 项集的候选集，得到剪枝后的候选k - 项集。然后对数据 库进行扫描，对剪枝后的候选k 项集进行计数，得到频繁l 【项集。 在数据库数据量不大的情况下，a p d o f i 算法的候选项产生检查的方法大幅度 压缩了候选项集的大小，取得了很好的性能。但该算法中存在的两个问题，在有 些情况下不能忽视。 ( 1 ) 该算法在计算的过程中需要产生大量的候选项集。这样当频繁1 项集的 数目很大或需查找的频繁模式很长时，需要产生的候选项集的数量就会剧增，从 而造成算法效率急剧降低。例如，当频繁1 项集有1 0 4 个时，需要产生的候选2 项 集将多达1 0 7 + ；当查找长度为1 0 0 的长频繁模式时，则需要产生多达2 瑚个候选项 集，若对如此大量的候选项集进行检查，算法的效率可想而知。 ( 2 ) 该算法需要对数据库进行多次扫描，并通过模式匹配检查候选项集。如 果数据库的容量很大或要进行匹配的模式很长时，算法效率会大大降低。 f p g r o w t h 算法 由于a p r i o d 算法的固有的缺陷无法克服，即使进行优化，其效率也仍然不能 令人满意。为此，许多学者提出了基于深度优先策略的不同算法，其中j i a w e ih a n 等人2 0 0 0 年提出的基于频繁模式树f p t r e e ( f r e q u e n t p a t t e r nt r e e ) 发现频繁项集 的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 ) 算法 9 1 最有影响。在f p g r o w t h 算法中，通 过两次扫描事务数据库，把每个事务所包含的频繁项按其支持度的降序存储到 f p - t r e e 中。在以后发现频繁项集的过程中，不需要再扫描数据库，而仅在f p t r e e 中进行查找即可，并通过递归调用f p g r o w t h 的方法来直接产生频繁项集，因此在 1 0 兰州大学硕士研究生毕业论文 整个发现过程中也不需要产生候选项集。该算法克服了a p r i o r i 算法中存在的问题， 并在执行效率上也明显好于a p r i o r i 算法。 下面将对与f p - 1 b e 相关的概念及f p g r o w t h 算法进行介绍。 ( 1 ) 频繁模式树( f p t r e e ) 由j i a w e ih a n 等人定义的f p - t r e e 中的每个节点由4 个域组成：n o d e n a m e ； n o d e - c o u n t ；n o d e - p a r e n t ；n o d e 1 i n k 。其中n o d e n a m e 域用于记录该节点的项名， n o d e c o u n t 域用于记录到达该节点的子路径所表示的事务数，n o d e - p a r e n t 域用于指 向父节点，如果父节点不存在，则值为n u l l ，n o d e 1 i n k 域用于链接树中同名节点， 如果不存在同名节点，则值为n u l l 。另外，为便于树遍历，创建一个项头表( h e a d t a b l e ，简称为h t a b l e ) ，项头表中的每个元素包含有两个域：i t e m n a m e ；i t e m - h e a d 。 其中i t e m n a m e 域用于存放频繁项，在整个h t a b l e 中频繁项按照支持度降序存放， i t e m - h e a d 域用于指向f p - t r 中与其i t e m - n a m e 同名的节点链中的第一个节点。 在以上所定义结构的基础上，f p - t r e e 的构造算法如下： 第一步扫描事务数据库d 一次，产生频繁1 项集及其支持数，并按支持数降 序对频繁1 项集进行排序，生成频繁项列表l 1 ； 第二步创建f p t r e e t 的根节点，标记为“n u l l ”，对于d 中的每个事务t 作如下 处理：按l 1 中的次序排列t 中的频繁项，忽略t 中非频繁项。假定排列后的结果为 p l p ，其中p 是第一个项，而p 是剩余项的列表；调用i n s e r t _ t r e e ( i v l p ，1 ) 。函数 i n s e r t _ t r e e ( p l p ，d 的执行过程为：如果哺子节点n 使得n n o d e n a m e - - p ，则n 的计 数加1 ，否则创建一个新节点n ，将其节点名称n o d e - n a m e 和节点计数n o d e c o u n t 分 别设置为p 和1 ，并f l j n o d e p a r e n t 链接到其父节点t ，由n o d e 1 i n k 将其链接到具有相 同名称n o d e - n a m e 的同名节点链中；若p 不为空，则递归调用i n s e r t _ t r e e ( p , n ) 。 该过程的伪代码如图2 2 所示。 【例2 1 】下面通过一个例子来分析f p - t r e e 的结构和它的生成过程。 表2 1 表示的事务数据库d 有6 个事务，1 1 个项， l i d 标记事务编号，项集 i _ a ，b ，e , d ，e ，f , g , h , i , j ，k ) ，设最小支持度m i n s u p = 2 。 根据上面介绍的构造算法，首先扫描数据库d ，找出其中包含的满足最小支持 数要求的频繁项，并按支持数降序排列，生成频繁项列表i d ，如表2 2 所示： 在找出l l 以后，进入算法的第二步。首先建立频繁模式树t 的根节点，并将其标记 为“n u l l ”，然后扫描事务数据库d ，对其中的每个事务做如下处理： 1 1 兰州大学硕士研究生毕业论文 函数：i n s e r t _ t r e e ( p i p , 1 3 输入：频繁项表为函阳，f p - t r e et 输出：f p - t r e e t 步骤： j7 ”，一，f、 一， 、“” ，1 ： i f 树f 茸子女n 使得n ，i t e m n a m e = p i t e m - n a m ct h e n 2 ：n c o u n t = n c o u n t + 1 ： 。 3 ：e l s e ， ；”4 ： 创建一个新节点n ，n c o u n t ：= 1 ； 。 ，5 ：将节点n 链接到它得父节点t ： 6 ：通过节点链结构将其节点n 链接到具有相同i t e m n a m e 的节点； i t t 7 ： ) ： 8 ：i fp ot h e n “ 。 震 c ! o 舅用i n i e 吐j r e c n 2 1 。一一一。一一。毫 图2 2f p - g r o w t h 算法中i n s e r t _ t 愀过程 t i d事务 1 0 0 a c ，d ，f 2 0 0 b ，c ，d ，e ，f ，i ，k 3 0 0 d ，e ，g 4 0 0 b ，f 5 0 0 c ，d ，f ，j 6 0 0 a ，b ，c e ，h 表2 1 事务数据库 项支持数 f 5 c4 d4 b3 e 3 a2 表2 2d 中m i n s u p = 2 时l l 1 2 兰州大学硕士研究生毕业论文 对于d 中的每个事务所包含的频繁项按照l l 的顺序进行排序，并忽略非频繁 的项。为了简化叙述，现把所有事务经处理后的结果在表2 3 中列出： 对每个排序后的事务调用i n s e r tt r e e 过程，把事务中包含的每个频繁项插入 到t 中的适当位置。对于排序后的事务 f c ，d ，a ) ，将其插入到t 中的过程为；首先调 用i n s e r t _ t r e c ( q c a a , t ) ，由于此时只有一个根节点，所以生成新的节点n ，使其节 点名为f ，节点计数为1 ，并作为根节点的子节点；然后判断事务中的频繁项是否全 面d排序后的事务 1 0 0 f ，c ，d ，a 2 0 0 f c d ，b ，e 3 0 0 f d ，e 4 0 0 f ，b 5 0 0 f ，c ，d 6 0 0 c ，b ，e ，a 表2 3 排序处理后的事务数据库 插入到t 中，此时因事务中还有项c 、d 、a 没有插入，所以再调用i n s o r t _ t r e e ( c l d a ， 插入项c ，作为n 的子节点。以此类推，再插入项d 和a 。经过上面的步骤构造的f p t r e e 如图2 3 所示： 图2 3m i n s u p = 2 时的f p t r e et 兰州大学硕士研究生毕业论文 ( 2 ) 条件模式基和条件频繁模式树 由以上构造算法可知，对于项头表h t a b l e 中任一频繁项a i ，其对应的i t e m h e a d 域指向f p - t r e e 中项a i 的同名节点链的第一个节点。同名节点链中每个节点的 i t e m - n a m e 都和项a i 同名，又称为a i 的同名节点。这样在项a i 的每个同名节点所在的 路径中，由其前面的所有节点构成的路径就称为a i 的一条前缀路径。为了发现所有 以a i 为后缀的频繁项集，需要把a i 的所有前缀路径取出，并且使每个前缀路径中所 有节点的计数都和该路径后缀的a i 的同名节点计数相同，这样取出的所有前缀路径 就构成了项a i 的条件模式基( c o n d i t i o n a lp a t t e r nb a s e ) ，由a i 的条件模式基所构造的 频繁模式树称为a i 的条件频繁模式树( c o n d i t i o n a lf p t r c e ) ，其构造方法与f p t r e e 的构造方法相同。 例如：在上例中为发现所有以项e 为后缀的频繁项集，则需取出e 的所有前缀路 径，并使路径中所有节点的计数都和各路径中包含的项e 的计数相同，这些路径如 下： f 1 ，c ：l ，d ：l ，b ：1 、 f 1 ，d ：1 、 c ：1 ，b ：1 ) ，这些前缀路径组成e 的条件模式基，相 当于一个带有项计数约束的数据库，数据库进行两次扫描，建立起一个频繁模式 树，该树就称为e 的条件频繁模式树。这时的最小支持数和前面相同， 1 i m i n s u p = 2 ， e 的条件模式基中包含的所有项计数都满足该m i n s u p 要求，如图2 4 所示： ( 3 ) f p g r o 叭h 算法 f p g r o w t h 算法充分利用了前面介绍的频繁模式树结构，能够快速地挖掘出数 1 4 兰州大学硕士研究生毕业论文 据库中所包含的频繁项集。在整个挖掘过程中，该算法不需产生候选项集，且只 需扫描数据库两次。该算法的主要思想如下：首先，在算法执行之前把数据库中 的每个事务包含的频繁项压缩存储到f p - t r e e 中，具体的方法见上面；然后执行算 法，针对项头表h t a b l 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 - t r e e 、事务数据库d 和最小支持度m i n s u p ； 输出：d 中包含的在m i n s u p 下的所有频繁项集 步骤：c a l lf p - g r o w t h ( f p - t r e e , n u l l ) 7 。4 “一“。“”7 ”# ”1 ”。i “、。燃 s l ：i f t r e e 含单个路径pt h e n i ? 2 ；f o r 路径p 中节点的每个组合1 3 ； 3 ；， 产生项集1 3ua ，其支持度等于b 中节点的最小支持度；，。 ： ” ；4 ： 诲 g i5 ：e l s ef o r t r e e 的头表每个项a lf 9