（计算机软件与理论专业论文）数据流中频繁项目集挖掘算法的研究.pdf

摘要 摘要 数据挖掘经过十几年的研究，特别是最近几年，一些基本概念和方法趋于清 晰，它的研究也向更深入的方向发展。随着信息技术的发展和互联网的兴起，数 据量急剧膨胀，而且数据的形式也多种多样。传统的数据挖掘方法往往都集中在 对静态数据的挖掘，他们可以高效地在静态数据中挖掘信息和知识，但是他们无 法适应在高速的，大量的，实时性很强的数据流，因此数据流挖掘成为最近数据 挖掘领域比较热的研究点。 在数据流挖掘领域中，频繁项集的挖掘是基础性的，比较关键的问题。同时。 对于挖掘数据流中的频繁项目集的研究也是数据流挖掘应用于实际所必需的基 础性研究，有着广泛的应用前景。在这个领域中，传统的研究方法大多关注于在 数据流中挖掘全部频繁项集。由于挖掘全部频繁项集存在数据和模式冗余问题， 所以对算法的时间和空间效率都具有更大的挑战性。因此，近年来人们开始关注 在数据流中挖掘频繁闭项集与最大频繁项集，其中一个典型的工作就是m o m e n t 算法。另外，在数据流中挖掘频繁项目集领域，挖掘算法所使用的窗口机制，数 据淘汰与剪枝策略也是比较关键的问题，近些年来也得到了广泛研究。 本文针对数据流挖掘中的窗口机制、数据淘汰与剪枝策略、频繁闭项集与最 大项集这三个需要解决的问题，主要完成了以下的研究工作： ( 1 ) 提出了一种数据流中挖掘频繁闭项集的近似挖掘算法a m o m e n t 。它采用 衰减窗口机制、近似计数估计方法和分布式更新信息策略来解决m o 咖m t 算法中 过度依赖于窗口和执行效率低等问题。 ( 2 ) 本文针对削减节点规模问题，提出了一种新型数据结构f d l c e t ，并且基 于该数据结构设计了数据流中挖掘频繁闭项集算法f m o m e l l t 和挖掘最大频繁项 集算法m m f i 。 ( 3 ) 对新算法与典型算法进行了详尽实验及比较，分析了每个算法的效率。实 验表明，这些新提出的算法在效率上要高于目前出现的同类典型算法。 关键词数据挖掘；数据流；频繁项目集；频繁闭项集；最大频繁项集 a b s t r a c t a b s l ：r a e t d a t am i n i n gh a sb e e ns t u d i e df o rd e c a d e s i n “骘y e a r s i t sb a s i cc o n c e p ta n d m e t h o d sg o tm o r ea n dm o r ec l a r i f i e d ，a n di tc a nb ep r e d i c t e dt h a tt h es t u d yo fd a t a m i n i n gw i l lg e tm o i r e ：i n t e m i v ei nt h ei l e a l f u r t t l l r e w i t ht h ed e v e l o p m e n to f t e c h n i q u e si ni n f o r m a t i o np r o c e s s i n ga n dl a i n - n e t , t h ev o l u m eo fd a t aw i l lb e i n c r e a s e di nah i g hs p e e d , a n dt h es t y l eo fd a t aw i l lb ed i v e r s i f i e d t h et r a d i t i o n a l m i n i n gm e t h o da l w a y sf o c u so ns t a t i cd a t a , s oi ti sd i f f i c u l tt 0a d a p tt ol l i g hs p c e , t , l l i g hv o l u m ea n dr e a l - t i m ed a t as t i e a l t l l s ，a n dd a t as t r e a mm i n i n gb e c o m et h eh o t s p o t i nr e c e n ty e a r s m i n i n gf r e q u e n ti t e m s e t sf r o md a t ag t l - e a n si st h eb a s i ca n dk e yp r o b l e m a tt h e s a m et i m e , m i n i n gf r e q u e n ti t e r n s e t sf i o md a t as l l c a m si st h eb a s i cs t u d yb e f o r ei tc a l l b ea p p l i e di nt h er e a lw o r l d i nt h i sa r e a , m o s to ft h e mf o c u s0 1 1f i n d i n gc o m p l e t es e t o f f r e q u e n ti t e m s e t si nad a t as l r e a m d u et ot h en l l m c r 0 1 i sr e d u n d a n td a t aa n dp a t t e r n s i nm a i nm e m o r y , t h e yc a n n o tg e tv e r y9 0 0 dp e r f o r m a n c ei nt i m ea n ds p a c e t h e r e f o r e , m i n i n gf r e q u e n tc l o s e di t e m s e t sa n dm a x i m a lf r e q u e n ti t e r n s e t si nd a t as t r e a m b c c o n l l e $ an e wi m p o r t a n tp r o b l e r r t , w h e r ea l g o r i t h mm o m e n tw a sr e g a r d e da sa t y p i c a lm e t h o do ft h e m i na d d i t i o n , t h ew i n d o wm o d e l ，t h ee l i m i n a t i o no fd a t aa n d t h ep r u n i n gm e t h o da l s ob e c o m et h ek e yp r o b l e m i nr e c e n t l yy e a r s ，t h e yh a v eb e e n g o te x t e n s i v es t u d i e d i nt h i st h e s i s ，w ew i l lf o c u s0 1 1t h ep r o b l e mo ft h ew i n d o wm o d e l ，e l i m i n a d o no f d a t aa n dt h ep r t m i n gm e t h o d ，m i n i n gf r e q u e n td o s e di t e m s e t sa n dm a x i m a lf r e q u e n t i t e m s e t si nd a t as l t e a m s a n dt h em a i n w o r ko f t h i st h e s i si sl i s t e d 嬲b e l o w ： ( 1 ) p r e s e n t sa i la l g o r i t l f l n l c a l l e da m o m e n t ，w h i c hu s e st h ed a m p e dw i n d o w t e c h n i q u e ，a p p r o x i m a t ec o u n tm e t h o da n dd i s t r i b u t e du p d a t i n gs t r a t e g yt og e th i g h e r m i n i n ge f f i c i e n c y ( 2 ) p r e s e n t san e wd a t as l a u c t u r e ，c a l l e df u l l c 耵，w h i c hc a nd e a lw i t ht h e p r u n i n gp r o b l e m t h e nw ep r e s e n t st w on e wa l g o r i t h mf - m o m e n ta n dm m f lw h i c h c a l ln l i n l 。f r e q u e n td o s e di t c m s e t sa n dm a x i m a lf i - e q u e n ti t e m s e t sf r o md a t as t r e a m ( 3 ) e x p e r i m e n t0 1 1t h e s ea l g o r i t h m , a n dc o m p a r et h e s ea l g o r i t h mw i t ht h et y p i c a l a l g o r i t h m ，t h e na n a l y z et h ee x p e r i m e n tr e s u l t e x p e r i m e n t a lr e s u l t ss h o wt h a tt h e s e n e wa l g o r i t h mp e r f o r m sm u c hb e t t e rt h a nt h et y p i c a la p p r o a c h e s k e y w o r c l sd a l am i n i n g ；d a t as t l e a m ；f r e q u e n ti t e r n s e t ；f r e q u e n td o s e di t e m s e t ； m a x i m a lf r e q u e n ti t e m s e t l g 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：剖日期：! ! 旦i ! 1 3 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：刘垫导师签名： 积丑 日飙塑 第1 章绪论 第1 章绪论 1 1 数据流挖掘技术简介 数据挖掘【1 _ 2 1 ( d a t am i n i n g ) 是一个多学科交叉研究领域【3 一，经过十几年的 研究，特别是最近几年，一些基本概念和方法趋于清晰，它的研究也向更深入的 方向发展。随着信息技术的发展和互联网的兴起，数据量急剧膨胀，而且数据的 形式也多种多样。为了能在大量数据中挖掘有用信息，人们已经发现了许多高效 的挖掘方法。传统的数据挖掘方法往往都集中在对静态数据的挖掘，他们可以高 效地在静态数据中挖掘信息和知识，但是他们无法适应在高速的，大量的，实时 性很强【5 ，6 ，7 1 的数据流数据i s , 9 1 。 数据 流【1 0 “l ( d a t as t r e a m ) 是指可能无限的、持续而快速到达的数据序列。事 实上，数据流1 1 2 ，1 3 】的概念无处不在的。许多公司和组织每天都在不断产生着交易 记录。当组织机构十分庞大的时候，每天都会产生上百万个交易记录。比如，沃 尔玛超市每天产生2 0 0 0 万条购买记录，g o o g l e ( 搜索引擎) 每天处理的查询量 达到7 0 0 0 万次，a t & t 公司每天产生2 亿多条呼叫记录。科学数据的收集( 比 如，地球探测卫星，天文台) 一般每天都会产生十亿字节的数据。这样的数据级 别对数据挖掘产生了重大影响。对于大多数传统挖掘算法，挖掘一天的数据将要 花费超过一天的c p u 处理时间，这就意味着数据的积累速度已经远远超过数据 挖掘的速度。因此，我们在静态算法伸缩性上的努力在数据流领域都付之东流。 要想解决这些问题就需要把我们的思想从在数据库中挖掘转移到挖掘数据流上 来。在传统的数据挖掘过程中，被挖掘的数据被预先导入一个静态的不经常更 新的数据库中，挖掘它们需要几个星期甚至几个月的时间，在这之后，挖掘结果 得到应用，新的一轮挖掘才会开始。而我们现在需要关注的是一种更适合挖掘大 容量的，无限的数据流的过程，其主要特点是，数据流挖掘系统应该不断的以数 据到来的速度处理数据，并把它们加入到正在构建的模型中去1 “”j 。 到目前为止，理论界比较公认的数据流挖掘方法应具备的特点有1 1 5 1 ： ( 1 ) 对于每条数据的处理都必须用很少的时间，否则，数据处理会落后于数 据的积累。 ( 2 ) 必须保证使用有限的内存。 ( 3 ) 必须保证一遍扫描【1 6 1 ，因为没有时问和空间再访问以前的数据。 ( 4 ) 必须保证在任何一个时刻都能够得到模式，而不是在所有处理都完成后 生成模式。 北京t 业 学- r 学硕f 学位论文 ( 5 ) 必须保证它建立了与数据库中的数据模型等价或近似等价的数据模型。 ( 6 ) 当数据产生随时间变化时，要保证模型在任何时候都是动态更新的，并 且能保留过去未过时的信息。 ( 7 ) 尽量保证算法能够在线挖掘数据流，也就是说尽量不采用先挖掘出中间 结果，再通过中阅结果挖掘频繁项目集的方法。丽是使算法尽量做到能够在需要 的时候直接输出挖掘结果。 为了满足数据流挖掘的特点，数据流挖掘方法就需要解决以下问题： ( 1 ) 在数据量比较大的情况下，频繁模式的生成速度。 ( 2 ) 如何在保持过去信息和保持模型更新之间做出平衡。 ( 3 ) 哪种数据挖掘算法适合挖掘高速数据流。 ( 4 ) 如何能够更快的适应数据流的变化。 由于传统的数据挖掘方法已经很难适应数据流挖掘的过程，这就需要许多新 方法专门处理数据流挖掘问题。传统的( 如分类，聚类，关联规则挖掘等挖掘方 法1 在数据流的环境中都要进行相应的改变。因而，数据流挖掘成为数据挖掘领 域比较新的研究热点，它也引起了越来越多的人的关注【1 7 1 3 9 1 。 1 。2 数据流中挖掘频繁项目集技术 在关联规则、序列模式挖掘等研究领域，挖掘频繁项集是最基础和最关键的 步骤挖掘频繁项集是数据挖掘中一个活跃的研究领域。1 9 9 4 年，r a g r a w a l 提出了a p r i o r i 算法1 2 0 1 ，这是一个最有影响的挖掘布尔关联规则频繁项集的算 法。在这之后又提出了a p r i o r i 算法的一些改进算法【2 i 矾玎j 。 但是，由于 a p r i o r i 算法需要产生庞大的候选项集和多次扫描数据库叫巧i ，因此导致较差的 时空效率。2 0 0 0 年，h a r t 等提出了f p t r e e 算法1 2 4 1 ，它不使用候选项集而是直接 将数据库的扫描结果存放到紧缩的频繁模式树中，是一个两次数据库扫描的频 繁项集挖掘算法。另一个有代表性的工作是频繁闭项集( f r e q u e n tc l o s e di m m s e = t ) 的挖掘方法。1 9 9 9 年，p a s q u i e r t i 首先提出了闭项集概念p j ，随后挖掘频繁闭项 集的问题被广泛研究1 7 6 , 2 t 2 甜。由于频繁闭项集只关注挖掘一些特殊的频繁项集。 并且不丢失项集支持度的信息，因而可以减少项集的存储空问与处理时间，进 而提高挖掘的效率。 同样，在数据流中发现频繁项目剁2 9 , 3 0 , 3 1 1 也是数据流挖掘中的一个基础性的 问题，正在得到越来越多研究人员的关注，它对数据流挖掘有着重要意义。数据 流中挖掘频繁项目集在许多领域都有着很大的需求，比如在搜索引擎领域，用户 的查询请求被不断的送到搜索引擎，这时，我们可能会比较关心一个时间段内最 频繁的查询模式是什么。因此，在数据流中发现频繁项目集有重要的研究价值。 2 1 2 1 数据流中挖掘频繁项目集简介 给定一个被讨论的项目全集i = i i ，i 2 ，i 。) 和定义在i 的一个事务数据库d = ( t i d l ，t d , - , ( t i c h ) ，其中t 匡i 衅l 2 ，舢被称为一个项目集( i t e m s e t ) ，表示数据 库的一个事务所包含的所有项目，并且t i d k 是这个事务的标识符。设i l i ，项目序 列1 1 在d 上的支持度是指d 中包含i 的事务在d 中所占的百分比。即 s u p p o r t ( 1 1 户忡d il l c - t 1 l i i d l l 给定一个最小支持度m i n s u p ，l l c ：l 被称为是一个 频繁项集当且仅当i l 的支持度s u p p o r t j l l ) 五n i n s u p 因此，在d 上挖掘频繁项集的 任务就是寻找i 的所有支持度不小于m i n s u p 的所有频繁子集。 数据流中挖掘频繁项目集的目标与在静态数据集中挖掘频繁项目集的目标 是一致的。但是，在数据流中挖掘频繁项目集面临着许多挑战。 ( 1 ) 数据流是持续的，高速的，无限的。所以，不可能用多次扫描的方法挖 掘频繁项目集。 ( 2 ) 数据流挖掘频繁项目集的算法要保证在有限的时间和有限的内存下完 成。 ( 3 ) 数据流的产生是随时间变化的。通常人们关心的是最近的模式，但过去 的模式对于挖掘结果也具有不同程度的影响。 由于上述的挑战，研究人员提出了许多新方法来解决在数据流中发现频繁项 目集的问题。 一种比较容易实现的方法就是对不断到来的数据进行缓冲，算法关注如何对 缓冲区中的数据进行挖掘，以及如何动态的更新模型以适应缓冲区中数据的变 化。另一种方法是不缓冲数据，直接将到来的数据动态更新到模型上。第一种方 法的主要特点是设计相对简单，但不容易反映整个数据流的全局模式。如果缓冲 区设置不合理，模型会发生比较大的震荡，影响挖掘效率。第二种方法的主要特 点是更加适应数据流的特点，不需要额外的存储数据，能够反映全局模式，模型 相对稳定不容易发生震荡，但由于该方法所处理的数据量比较大，因此，对算法 的伸缩性要求比较高。 目前，这两种方法，研究人员都做了一些有意义的研究，其中最早提出在数 据流中挖掘频繁项目集的方法是l o s s yc o u n t i n g j i g 算法，该算法的主要思想是 在高速数据流的环境中使用近似计数，来适应数据流的特殊环境。同时，这个算 法也为我们展示了处理数据流一般性的模型。该模型的核心部分是一个流处理器 和一个动态更新的数据结构。另外，根据需要可以在该模型中加入数据流的临时 缓冲区，用来缓冲到来的数据，以便处理。该框架的描述见图1 - 1 。 北京下业大学丁学硕卜学位论文 戴据流 粉悬漂， 图1 - 1 数据流中挖掘频繁项目集的基本模型 f i g u r e1 - 1t h em o d e lo f m i n i n gf 咖u ti t e m s e ti nd a t a s h o a l n 在该模型下，研究人员们相继提出了更多挖掘频繁项目集的方法，他们的共 同特点是。第一，利用有限的系统资源处理高速的，无限的数据流。第二，在资 源使用受到限制的情况下，通过牺牲一些精确度来实现对数据流的快速挖掘。 1 2 2 数据流挖掘中的窗口机制 根据数据流挖掘的窗口模型1 7 1 ，目前出现三种主要技术：里程碑( l a n d m a r k w i n d o w ) 窗口、滑动窗e l ( s l i d i n gw i n d o w ) 和衰减窗e l ( d a m p e dw i n d o w ) 。在里 程碑窗口处理模型中，它们总是关注整个数据流中的数据，并通过对整个历史数 据的分析得到全局性的频繁模式。的确，全局性的知识模式是许多数据流挖掘中 的期望结果。但是，由于数据流的大容量和不可预测的数据到达速度，近期的研 究表明里程碑窗口处理模型必须结合快速的近似归纳技术或合适的数据淘汰技 术才能真正适合数据流的挖掘吲。最有代表性的提出基于里程碑窗口的数据流 挖掘算法的方法是l o s s yc o u n t i n g 【l 町，它是基于a p r i o r i 算法思想，但是利用近似 归纳技术实现数据一次扫描。 在滑动窗口处理模型中，关注点总是被放在最近发生的若干事务上，因此， 它们的挖掘结果是某段时间内的局部频繁模式。在大多数的数据流环境中这种 局部模式是不适合的，这应该说是滑动窗口的固有缺陷。但是，滑动窗口处理模 型具有易于理解、设计简单等优点，因此在数据流挖掘中也得到广泛的研究和应 用。2 0 0 3 年，t e n g 等提出了一种称为f t p d s 算法田】，它是在滑动窗1 1 3 中使用统 计回归技术来挖掘频繁项集。2 0 0 4 年，c h i 等给出了m o m e n t 算、法1 1 9 1 ，它也是基 于滑动窗口技术的，但是m o m e n t 仅关注在数据流中挖掘频繁闭项集，因此它可 以被期望来减少内存数据结构的规模和获得较高的挖掘效率。 在衰减窗口处理模型中，每个事务都对应一个权值，而且这种权值随时间的 增加而减少。因此，它能在这些权值的控制下考虑历史数据相关信息的保存以 及裁减等工作。这种模型在数据流挖掘上具有可以期望的应用前景在衰减窗 口处理模型中，比较有代表性的方法是2 0 0 3 年c h a n g 等提出的e s t d e c 算法 3 4 , 3 5 。 4 第l 章绪论 它通过定义一个称为衰减因子的参数，使得较早到达数据流的事务的影响逐渐 减弱2 0 0 3 年。g i a n n e l l 等提出了一种传统的f p t r 【2 4 1 改造的处理数据流的算法 f p s t r e a m 3 2 1 ，该方法利用不同时间粒度来实现不同时间段的频繁项集的生成工 作。 因此，选择不同的窗口机制也是数据流挖掘算法设计中的一个重要组成部 分。 1 2 3 数据流挖掘中的数据淘汰与剪枝策略 数据流挖掘的主要特点是数据连续的，无限的到来。这就意味着数据量会随 着时间变化而变得越来越大，要想在有限的资源内完成对庞大数据的挖掘就需要 使用一系列数据淘汰和减枝策略。 挖掘频繁项目集的本质是在一个由项目集为节点组成的格中寻找频繁的节 点。因此，挖掘频繁项目集中的减枝策略实际上就是利用项目集之间的关系，减 少维护的节点数量，从而提高算法的时间和空间效率。其中比较有代表性的算 法是c h i 1 9 1 提出的m o m e n t ，其核心是在内存中维护一种称为c e t ( c l o s e d e n u m e r a t i o nt r e e ) 的数据结构。 图i - 2m o m e n t 节点示意图 f i g u r e1 - 2t h en o d e so f m o m e n ta l g o d t h m 从图中可以看出，该数据结构实际上就是项目集格 3 6 , 3 7 的一个子集，每个节 点代表一个项目集。( 该表示中后面数字表示前面的项目集的支持数) 。在数据结 构中定义了四种节点类型，通过频繁项目集之间的关系，保证某种类型的节点不 被扩展，大大减少了节点数量。比如，d l 是不频繁项目集，因此没有必要扩展 该节点，由于a b 3 和b 3 具有相同的支持数，由此可以保证b 与a b 总是同时出 现，因此，b 3 节点也不需要扩展。 在数据流挖掘中，另一个需要关注的方面是数据淘汰策略。数据流中的数据 量总是趋于无限大，为了保证在有限资源中挖掘频繁项目集。因此，算法不能保 存到来的全部数据，需要有选择的淘汰掉一些对挖掘结果影响比较小的数据，从 而能够适应数据流无限到来的特点。事实上窗口机制就是数据淘汰策略的一种， 在窗口机制里最直观和简单机制是滑动窗口机制，基于滑动窗口的算法总是保持 北京t 业大学t 学硕卜学位论文 最近某个时问段到来的数据，而不在窗口内的数据将不会被关注，这样的机制比 较容易实现，如果窗口设置的比较合适，局部模式也能够反映出全局模式的情况， 从而不会导致对模型更新过于频繁，但它不是数据流挖掘的全部解决方案。另一 种数据淘汰策略是使用衰减窗口机制，在该机制中，不同时期到来的数据对挖掘 结果的贡献是不同的。新到来的数据比以前到来的数据权重要更大。在这种机制 中充分地考虑到最近到来的数据对挖掘结果影响比较大，但也兼顾了以前到来的 数据。因此，这种方法也更有利于挖掘全局模式。另外，有些研究人员提出了对 数据流数据进行筛选淘汰的理论【3 8 3 9 , 4 0 ，其中c h i p 8 1 提出的l o a ds h e d d i n g 方法 也是处理大规模数据流时比较好的数据淘汰策略，其的主要思想是：在数据流挖 掘过程中，判决模块不断判断数据的价值，它总是倾向于保留对挖掘结果影响最 大的数据，而淘汰掉那些对挖掘结果影响比较小的数据，并不断为判决模块提供 反馈，从而提高数据流挖掘的效率。 综上所述，数据淘汰和减枝策略对于数据流挖掘有着重要影响。 1 2 4 数据流中挖掘频繁闭项集与最大频繁项集 挖掘频繁项目集已经得到了广泛的研究，但是挖掘频繁项目集的一个重大缺 陷是需要维护一个比较庞大的数据结构，因为一组项目可以组成的项目集个数可 以达到2 一个项目集，如果把这些项目集都存储在内存中，其数量会比较庞大。另 外，挖掘一般性的频繁项集存在相当多的重复信息( 例如，如果挖掘出的频繁集是 a b c ，a b ，a ，那么根据a p r i o r i 属性i l 刁a b 和a 是冗余的) 因此，自从1 9 9 9 年， p a 鲴u i e n i 提出挖掘频繁闭项集的思想后，许多文献讨论了这个问趔1 9 ，2 6 , 2 8 , 4 1 2 1 。 因此，研究人员开始关注挖掘另外两类频繁项目集。 ( 1 ) 最大频繁项目集f m i ：对于集合m ，集合中的任何频繁项目集都不是另 一个频繁项目集的子集。例如f l = a 3 ，b 3 ，c 3 ，a b 3 ，a c 2 ，b c 2 ，a b c 2 ) ， 其对应的f m i 是 a b c 2 l ，这是因为f i 中的其他元素都是a b c 的子集。 ( 2 ) 频繁闭项目集f c i ：定义在项目全集i 和事务数据库d 上的一个频繁闭 项集f c i 是d 上的频繁项集f i 的一个特殊子集：f c i 中的任何项集的支持度都 不能小于或等于它的超集的支持度。例如上面例子f i r a 3 ，b 3 ，c 3 ，a b 3 ，a c 2 ， b ( 2 2 ，a b ( 2 2 ，其对应得f c i - f ( 7 3 ，a b 3 ，a b c 2 ，因为a 3 ，b 3 和它的超集 a b 3 具有相同支持度，a c 2 ，b c 2 和它的超集a b c 2 具有相同支持度，所以它 们不是频繁闭项集。但a b 3 满足频繁闭项集的条件。 由这两种频繁项集可以很明显看出m f i c _ c f icf i ，因而需要维护的频繁项 目集数量将大大减少。这样可以通过挖掘这两类频繁项目集来提高算法的时间和 空间效率。其中最大频繁项集有最少的项集数量，它不能够保持支持计数的准确 6 第1 苹辫i 论 但在某些应用中可能并不太关注支持计数的准确性。频繁闭项集比最大频繁项集 数量要多，但保持了项目集的准确支持计数。到目前为止，在数据流环境下挖掘 最大项集和频繁闭项集的研究还不很多。最有代表性的频繁闭项集算法是c h i t l 9 1 提出的m o m e n t 。在挖掘频繁最大项集领域，虽然在传统数据挖掘领域已经有了 许多研究 4 3 , 4 4 , 4 5 l 。但在数据流挖掘方面，研究成果还比较少，最具有代表性的算 法是i n s t a n t l 4 6 算法。在该算法中，不同支持数的最大频繁项集被置于不同的窗口 中，当新有新的数据到来，使用亚交亚并的操作使最大频繁项目集升到高一级的 窗口。这种算法能够很好的适应支持度较小的情况。 在数据流中挖据最大频繁项集和频繁闭项集算法，由于其对频繁项目集数量 的压缩十分适应数据流挖掘的特点，近年来受到越来越多的关注。 1 3 研究内容 1 3 1 问题提出 在数据流挖掘频繁项目集领域里主要关注问题是如何能在有限的时间和空 间内快速地挖掘出数据流中存在的频繁模式。因此，可以把数据流中挖掘频繁项 目集领域里需要解决的主要问题分为五点： ( 1 ) 如何设计有效的算法来适应在不同支持度条件下从数据流中挖掘频繁项 目集。 ( 2 ) 如何设计具有伸缩性的算法在连续，无限到来的数据流中挖掘频繁项目 集。 ( 3 ) 如何设计有效的算法来尽量反映数据流的全局模式。 ( 4 ) 如何设计有效的算法来减少数据流中挖掘出的模型的规模。 ( 5 ) 如何设计能够在线挖掘频繁项目集的算法，也就是说该算法不使用先挖 掘中间结果，然后再从中间结果进行挖掘方法，或者让中间结果尽量接近最终的 挖掘结果，从而使算法能够在需要的时候直接输出频繁模式的情况。 1 3 2 研究方向 针对以上五个问题，本论文从以下三个方向进行研究： ( 1 ) 数据流挖掘中窗口机制的研究数据流挖掘频繁项目集所使用的窗口机 制对于挖掘数据流中的全局模式有很重要的影响，它也是减少挖掘模型规模的有 效方法，因而能够通过对窗口机制的改进，达到提高算法伸缩性的目的。 ( 2 ) 数据流挖掘中的数据淘汰与剪枝策略数据流挖掘中的数据淘汰与剪枝 7 北京t 业人学t 学硕 学位论文 策略是为了保证数据挖掘算法能够在有限的资源下挖掘频繁项目集，限制挖掘模 型规模，它对算法伸缩性有很大影响。另外，不同的数据淘汰和剪枝策略也影响 着算法在不同支持度下性能表现，并直接影响到算法的在线能力。 ( 3 ) 数据流中挖掘频繁闭项集与最大频繁项集算法在数据流中挖掘频繁项 目集时，由于数据庞大，在事务的项目比较多的情况下，将导致产生过多的频繁 项目集，使资源使用量过大，对算法的时间和空间效率都会造成不小影响。而通 过挖掘最大频繁项集和频繁闭项集将有利于减少挖掘结果的规模，从而实现对频 繁模式的压缩。同时，挖掘最大频繁项集和频繁闭项集需要维护项目集之间的关 系，因而对算法的时间效率会有部分损失。因此，需要找到一个平衡点，使频繁 模式压缩对算法效率的积极贡献大于频繁模式维护压缩对算法效率的消极贡献。 1 4 本论文组织 本文将按照以下结构进行组织： 第一章为绪论，主要介绍课题的基本概念，背景和研究现状，研究内容和研 究意义。 第二章将主要关注频繁闭项集的挖掘和窗口策略的设计，在这一章中将首先 介绍最有代表性的在数据流中挖掘频繁闭项集算法m o m e n t , 然后介绍通过结合 衰减窗口技术和估计计数机制对m o m e n t 算法进行改进的算法a - m o m e n t 。 第三章将主要介绍一种新的数据结构f u l l c e t ，以及基于该数据结构挖掘频 繁闭项集算法f - m o m e n t 算法和基于f - m o m e n t 流程的挖掘最大频繁项集的算法， 在这一章中将介绍一种新的算法f u l l c e t 算法，以及该算法在挖掘最大频繁项 集中的应用。 第四章是实验结果与分析，详细的分析和比较了不同的数据流挖掘算法在不 同数据集，支持度的条件下，算法时间效率，伸缩性，挖掘出的频繁项目集的数 量。 最后对全文进行小结，并对今后的研究工作进行展望。 8 第2 章摹于衰减窗口的挖掘频繁闭项集算法 第2 章基于衰减窗口的挖掘频繁闭项集算法 本章将从在数据流中挖掘频繁闭项集算法m o m e n t 入手，介绍m o m e n t 算法 在挖掘频繁闭项集方面的贡献和缺陷，然后介绍m o m e n t 算法的改进算法 a m o m e n t ，以及它是如何解决m o m e n t 算法存在的问题。 2 1m o m e n t 算法介绍 2 1 1m o m e n t 算法描述 m o m e n t 算法是一种基于滑动窗口的在数据流中挖掘闭项集的算法。算法的 核心是在内存中维护一种称为c e t ( c l o s e de n u m e r a t i o nt r e e ) 的数据结构。c e t 的任何节点的儿子节点一定是这个节点的超集，并且是该节点和其右面兄弟节 点的并集。实际上，m o m e n t 算法的c e t 的节点被划分成四种类型1 1 9 1 ，并根据这 四种类型的节点算法进行不同的处理，通过这些类型的节点之间的内在联系，限 制了一些节点的扩展，达到了对节点进行剪枝的目的。为了更严格地表述下面 的问题定义2 一l 给出了对应的定义。 定义2 1 ( m o m e n t 的c e t 中的节点类型) 按节点的项目集频度和关联，c e t 的节点被划分成4 类：( 1 ) 不频繁( i n f r e q u e n t ) 节点：该类节点是不频繁的，但是 其父节点是频繁的。( 2 ) 没有前途( u n p r o m i s i n g ) 节点：该类节点是频繁的，但是 有一个与该节点支持度相同的闭项集包含该节点并且它们不构成直接父子关系。 ( 3 ) 中问( i n t e r m e d i a t e ) 节点：该类节点是频繁的，并且存在一个与该节点支持度 相同的儿子节点，该节点不是u n p r o m i s i n g 节点。( 4 ) 闭( c l o s e d ) 节点：这些节点 是频繁闭项集，它们可以是叶子节点也可以是内部节点。 例子2 - 1 假如一颗c e t 树如图2 1 所示，并且m i n s u p = 5 0 ，则d 1 是 i n f r e q u e n t 节点；a c 2 和b 3 是u n p r o m i s i n g 节点；a 3 是i n t e r m e d i a t e ；a b c 2 、 a b 3 和c 3 是c l o s e d 节点。 9 北京工业大学t 学硕卜学位论文 图2 1 节点类型示意图 f i g u r e2 - 1t h en o d e ss t r u c t u r eo f c e t m o m e n t 算法的另一个特点是它使用滑动窗口机制。由于事务的到来离去， 滑动窗口的数据会发生变化所以相应的c e t 节点的性质和支持度等信恳可能 发生变化。因此，m o m e n t 有两个主要的操作来支持这种变化【1 9 1 ：( 1 ) 当一个新事 务。，加入滑动窗口时，遍历c e t 并且对于它的所有节点进行支持度和节点性 质的维护。它提供一个称为a d d i t i o n 伽，五。，d ，m i n s u p ) 的操作来实现。( 2 ) 当 一个旧事务厶址离开滑动窗口时，m o m e n t 调用一个称为d e l e t i o n ( 厶协d ， m i n s u p ) 的操作来实现相关节点的信息维护。由此也看出，m o m e n t 算法是一种动 态更新模型的算法，这种更新发生在滑动窗口的一次滑动。 m o m e n t 算法通过这种剪枝策略和窗口机制实现了对动态数据流的挖掘，是 现阶段解决在数据流中挖掘频繁闭项集问题的比较新也比较好的解决方案。 2 1 2m o m e n t 算法存在的问题 m o m e n t 算法虽然是解决在数据流中挖掘频繁闭项集问题的一个比较典型和 直观的方法，但它也存在两个主要问题： ( 1 ) m o m e n t 算法采用了滑动窗口机制，只能发现滑动窗口内的局部频集。仅 挖掘局部频集对一些应用而言是不够的。尽管通过窗口大小的调整，可以减轻 这种影响【伸l ，但是这种调整能力是有限的。因此，这样的方法很难用来实时挖掘 数据流的全局变化。 ( 2 ) m o m e n t 算法使用的是一种在窗口内的精确算法模型，要频繁地维护和更 新信息，影响其效率。另外，新旧事务在窗口的替换通过两个独立的操作 ( a d d i t i o n 和d e l e t i o n ) 的迭代调用来完成。这样的更新策略很明显的一个缺点就 是可能引起数据颠簸问题即一个旧事务离开窗口或者一个新事务进入窗口都 可能引起内存数据结构的大幅度更新。 1 0 第2 章摹于衰减窗口的挖掘频繁闭项集算法 2 2 频繁闭项集近似挖掘算法a - m o m e n t 针对m o m e n t 算法在数据流挖掘方面的主要问题，本文提出了m o m e n t 算法 的一个改进算法，它突破了滑动窗口的限制，通过使用衰减窗口机制和不精确的 估计支持计数的方法，以适应数据流挖掘对于全局模式挖掘的需要。 算法的主要过程是，当一个事务在数据流中出现时，a m o m e n t 算法将按照4 个步骤来处理它：( 1 ) 当前窗口评估阶段；( 2 ) 计数更新阶段；( 3 ) c e t 维护阶段； ( 4 ) 频繁闭项集选择阶段。一般地说，前3 个阶段对每个事务都要进行，但是最 后一个阶段是周期性进行或者是在用户需要的时候进行主函数的伪代码描述 在下面的图2 - 2 中。 2 2 1 当前窗口评估阶段 f i g u r e2 - 2a - m o m e n ta l g o r i t h m 这个阶段的主要任务是计算出当前窗口的大小。在衰减窗口处理模型聊钥 中。所谓的当前窗口是虚拟的。事实上，在不同时间内，一个节点的支持计数的 权重是不同的，越老的事务对支持计数的贡献越小，因此需要动态地评估窗口的 理论期望值以计算节点的支持度。这样做的意义在于，既保证了老事务的影响 逐渐减少( 但不是突然消失) ，又解决了m o m e n t 算法的过于依赖窗口而发生的数 北京下业丈掌1 ：掌硕f 。学位论文 据颠簸问题。当前窗口大小的估算通过下面的定义2 2 和2 - 3 给出。 定义2 - 2 ( 衰减率) 给定一个衰减基b l 和一个衰减基生命h l ，则衰减率 d = 6 卅7 ”。 实际上，一个衰减率反映了历史数据相对于当前到达数据应该衰减的比率。 定义2 - 3 ( 窗口衰减计算) 给定衰减率4 假如一个事务到达前的窗口大小为 i d k 1 m 话，则这个事务到达后的窗口大小i 风l 司以通过下面的公式来估计： f d k l i b 一 x d + 1 ( 1 ) 定理2 1 给定b 1 和h l ，当事务数刀，则窗口的大小会收敛于1 ( 1 一d ) 。 证明显然，当第一个事务到达时，窗口大d , i d l i 是1 依据定义2 - 3 ，对于 卢1 ，2 ，丘有： i d z l = i d ii d + 1 = d + 1 ， i 功f 刊岛f d + l = d 2 + d + l ， l d i i = d k i l + d + l = d 一+ d 一2 + + d + l = ( 1 - d ) ( 1 一d ) 根据定义2 2 有：b 1 兰d 1 ，所以，当五趋于无穷大的时候，i d k i 最终会收敛到 i ( 1 - & 。 该定理表明，通过调整衰减率正图2 2 中的w i n d o w _ e v a l u a t e ( 口 w i n d o ws i z e , 肋函数能保证当前窗口被控制在所期望的范围内。 2 2 2 计数更新阶段 这个阶段的主要任务就是更新c e t 中已有节点的支持计数。由于在每个事 务出现时都需要重新评估当前窗口的大小，所以理论上说，c e t 的每个节点的 支持计数都可能发生变化。假如在每个事务到来的时候对所有的节点信息都进 行更新，其维护开销将会是很大的。因此，a m o m e n t 算法采用分布式更新策略， 即仅对和当前到达事务相关的节点进行批量衰减，而其它节点等待以后再更新。 假如c e t 中的一个节点7 被当前到达的事务七所包含的话，则此节点的计数 需要更新，其的更新方法定义如下： e n t k ( 帕= c n t 。( n ) d t k - 删一+ 1 ( 2 ) 其中e n d ( n ) 代表事务k 处理后的节点n 的支持数，而c n t r , r c ( n ) 和m r ，磷。代表 最近一次节点1 7 的支持数和最近一次更新节点刀的事务编号。 图2 - 2 中的函数 第2 章摹于衰减窗口的挖掘频繁闭项集算法 c o u n tm a i n t a i n ( c e t , 七) 就是依据上面的公式，在一个事务k 从数据流中到达时， 来完成c e t 相关节点的支持数更新的。 在大多数情况下，a - m o m e n t 算法的分布式更新镱略不会导致信息的过多丢 失。但是，假如一些节点的更新时间间隔过长进而可能影响系统的挖掘精度的 话，那么就应该考虑调用相应的后台进程来进行强制更新，这一工作可以结合后 面的频繁闭项集选择阶段进行。 可以看出，以上更新方法是一种分布式更新的策略，也就是说当新到的事务 与节点相关时，才更新节点的支持度，这样的更新策略减少了衰减窗口模型中所 必须的进行支持度衰减操作所带来的开销。 2 2 3c e t 维护阶段 这个阶段的主要任务是完成c e t 节点的维护，主要包括可