（计算机应用技术专业论文）数据流上的频繁项集挖掘算法研究.pdf

中文摘要 摘要：数据流是目前的一个新兴的热门领域，国内外学者都纷纷提出各种数 据流处理的技术、算法和各种具体应用项目。数据流是一个按时问到来的有序的 项集。和传统静态数据库中的数据不同的是，数据流是连续的、无限的、通常以 很高的速度到来的并且数据分布随着时间而改变。数据流频繁模式挖掘是数据流 挖掘基本问题之一，已经引起国内外研究者的广泛关注，提出了许多有效的数据 流频繁模式挖掘算法。 针对数据流的特点，论文对数据流处理技术和数据流挖掘中的关键问题进行 了研究和总结。论文对一些关键问题的解决技术进行了研究。论文对经典的频繁 项集挖掘算法进行了介绍和分析。分析可以看出数据流的无限性、高速性使得经 典的频繁项集挖掘算法难以适用到数据流中。此外，论文对于当前现存的一些数 据流中频繁项集挖掘算法进行了介绍，比较分析和总结，并且设计实现了数据流 中挖掘频繁项集的算法f p - s u e a m 和t i m e - s e n s i t i v es l i d i n gw i n d o w 本文在上述工作的基础上提出了f p f t 算法，用户通过它可以快速获取最近 一个时期内的频繁项集。该算法采用了嵌入了时间窗口的前缀树的结构来存储频 繁项集，方便了对数据块中数据项的操作，节约了一定的空间。分析和实验表明， 与传统算法相比该算法具有较好的空间和时间效率，适合数据流中频繁项集的挖 掘。 关键词：数据挖掘；频繁模式；频繁项集；数据流；前缀树 分类号：t p l 8 2 a g r o w i n gn u m b e ro fe m e r g i n ga p p l i c a t i o n sh a v et oh a n d l ev a t i o t t sd a t l t 鲥r 衄s s o i l l t ：i n t e r e s t i n gr e s u l t sh a v eb e e n 碍p 埘。df o rt e c h n i q u e sa n da l g o r i t h m so fh a d i g d a t as t r e a m s ，a n ds o m e $ l l e s n lp r o j e c t sh a v e b e e np r o p o s e d ad a t as l l e a mi s 锄o r d e r e d s e q u e n c eo fi t e m st h a ta r r i v e si nt i m e l yo r d e r d i f f e r e n tf r o md a t ai nt r a d i t i o n a ls t a t i c d a t a b 鹤姻，d a t as t r c a l 瑚黜c o l l t i n u o u s ，u n b o u n d e d , u s u a l l yc o n l ew i t hh i g hs p e e da n d h a v ead a t ad i s t r i b u t i o nt h a t0 f l 呛* l le i m g e sw i t ht i m e f r e q u e n tp a t t e mm i n i n gi so n eo f t h ef u n d a m e n t a lp r o b l e m si nd a t as l r c a mm i n i n g i th a sr e c e i v e de o m i d c r a b l ea t t t i o n i nt h ep a s tf e wy e a r s s o m ee f f e c t i v e a l g o r i t h m sh a v eb e e np r o p o s e d a c c o r d i n g t ot h ee l l a r a 嘶i s t i e so f d a t as t r e a m , t h e p a p e rr e s e a r e l a e sa a ds 衄t m a r i z e s t l a et e e l m i q mo fd a t as t e a m n 鹞i n 岛i s s u e si nd a t as 岫锄m i m g t h ep a p e r r e s e a r c h e ss o l n ct e c t m i q , e 8o fs o l v i n gt h ei s s u e s t h ep l l p o ri n t r o d u c e ss o l n em i n i n g a l g o r i t h m so f c l a s s i c a lf r e q 哑i t e m s e t s8 r i dd o e ss o l n cc x l l c t - i m e n t s n 哪a n a l y s i s , i ti sd i f f i c u l tt om a k ec l a s s i c a l 丘e q u 衄ti t e m s e t sm i n i n ga j g o r i t h m st oe x t e n dt od a t a 曲啪b e c a n s eo ft h el i m i t l e s sn n dh i 曲s p e c do fd a t as t r e a m t h ep a p e ri n t r o d u c e s , a n a l y z 髓a n ds u m m a r i z e s 瓢，m ee x i s t e n td a t as h 蛐m i n i n ga l g o r i t l m 墟b 酷i d e s t h e p a p e rd e s i g n sa n dr e a l i z e sf p - s 加瞄ma n dt i m o - s e m i t i v es l i d i n gw m d o wa l g o r i t i 衄o f 拙s l r c a mf r e q - e n ti t e m s 出m i n i n 吕 o nt h eb a s i so ft h ea b o v ew o r k , t h ep a p e rp r o p o s e 8f 1 3 - f ta l g o r i t l 皿t l a ea l g o r i t h m s t o r e sf r o q u e a tp a t m mb a s e do n 埘_ e 丘xl l - o ew i t ht i m ew i n d o w sw l a i c h 锄s a v es o m l ， s p a c e t h ea n a l y s i sa n de x p e r i m 伽tr e s u l t ss h o wt h a tt h i sa j g o r i t h mh a sag o o d p c r t o r m o ei ns p 鲥a n ds p l 七o i k e y w o r d $ ：d a t a m i i gf r e e a tp a n m l ；f r e q u e n ti t e m 喊；d a t as l r c a m ；呻t r o c c l a s s n o ；t p l 8 2 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：楫 导师签名： 签字日期：二嘲年陟月夕f 日 稗醐可棚圹 f 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意 学位论文作者签名夕奎掳挈 签字日期：工卯7 年伊月2 - 日 5 1 致谢 本论文的工作是在我的导师黄厚宽教授的悉心指导下完成的，黄厚宽教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢三年来 黄厚宽老师对我的关心和指导。 黄厚宽教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都给 予了我很大的关心和帮助，在此向黄厚宽老师表示衷心的谢意。 林友芳副教授对于我的科研工作和论文都提出了许多的宝贵意见，在此表示 衷心的感谢。 在实验室工作及撰写论文期间，师兄郑学双、师弟武志吴等对我论文的研究 工作给予了热情帮助，在此向他们表达我的感激之情。 另外也感谢我的父母和姐姐，他们的理解和支持使我能够在学校专心完成我 的学业 1 引言 1 1 研究背景与意义 在最近几年涌现出的一些应用中，数据是以成倍的、快速的、随时间变动的、 可能是不可预测和无限的流的方式连续到达，即数据以流的形式出现。一些比较 常见的应用包括：电子商务、金融应用、电信呼叫记录、制造业、网络监控和流 量分析、w e b 应用和w e b 点击流、能量消耗管理、传感器网络数据分析、股票市场 联机分析和动态跟踪股票的涨落等等。这些数据数量巨大，而且增长迅速超出人 们的想象。例如，一天之中w a l m a r t 有0 2 亿销售记录，g o o g l e 处理2 亿个查询，a t & t 产生2 7 5 亿通话记录。 在这些流数据中蕴含着大量的知识和有用的信息。通过获取这些流数据中的 信息和知识，我们可以提高系统的性能、获取更多的价值。例如在一些网络中， 通过网络流量监控能够发现网络上的瓶颈，从而进行负载均衡提高网络的效率。 另外通过网络监控发现网络上的异常来进行入侵检测除此以外，在金融应用中 还可以通过分析交易的流数据进行欺骗检测。 数据流的特点使得传统的数据挖掘算法不能直接应用于数据流，因为数据量 很大，而且是持续的，与数据流的规模相比，内存或缓存等存储空间是极其有限 的，只能对数据进行一次顺序扫描，因此需要一种动态的增量式的算法来处理数 据流。并且，多数应用要求在数据到来的同时进行分析决策，这对处理时间提出 了更高的要求。如何在数据流上进行数据挖掘，这就给研究人员带来了机遇和挑 战近年来，挖掘数据流中的频繁项集成为数据挖掘领域中的研究热点许多研 究人员和组织对数据流中的频繁项集的挖掘进行了研究 1 2 国内外研究现状 本节主要是对国内外数据流挖据方面的研究现状进行简单的介绍。 1 2 1 国外研究现状 国外在数据流挖掘方面的研究开展的较早，取得的科研成果较多、研究的进 展比较快。 目前，国外在数据流挖掘方面有两个比较有影响的小组：一个是s t a n f o r d 大 学的r m o t w a n i 教授领导的研究小组，另一个是u i u c 的c a g g a r w a l 和j h a r t 教 授领导的研究小组。前者的研究侧重在数据流管理、数据流的连续查询和数据流 的聚类方面，提出了不同于传统d b m s 的d s m s ( d a t a s t r e a m m a n a g e m e n t s y s t e m ) 概念，他们的研究得到了美国国家自然科学基金的资助。后者的研究侧重在数据 流分析方面，对于数据流的在线分析，从聚类、分类、频繁项集挖掘以及可视化 等角度做了大量研究工作，提出了倾斜时间窗口( t i l t e d t i m ew i n d o w ) 策略，采用不 同时间粒度保存数据流的信息，他们的研究得到了美国军方和国家自然科学基金 的资助。 在数据流中频繁项集的挖掘方面，许多国外的学者进行了深入的研究并提出 了自己的算法。g u r m e e ts m g hm a n k u 和r a j e e vm o t w a n i 提出了s t i c k ys a m p l i n g 算 法和l o s s yc o u n t i n g 算法挖掘数据流中的频繁项，并且扩展l o s s yc o u n t i n g 算法来 挖掘数据流中的频繁项集【i 】。m o s e sc h a r i k a r 等借助于c o u n ts k e t c h 的数据结构提 出一个通过扫描一遍数据流来挖掘数据流中频繁项的算法i 习g r a h 锄c o r m o d e 和 s m u t h u l a i s h n a n 提出了c o u m - m i ns k e t c h 数据结构n 该结构可以快速的进行 点查询。r i c h a r dm k a r p 和s c o t ts h c n k e r 提出了一种两遍的扫描算法来挖掘频繁 项 4 1 。c g i a n n e u a 等提出了一种f p s t r e m n 模型挖掘数据流中的频繁项集嘲还有 一些研究人员提出了许多重要的算法。 一些国外的研究人员还对数据流中频繁项集挖掘的关键技术进行了总结和探 讨 1 2 2 国内的研究现状 国内在数据流挖掘方面的研究开展的较晚，但是已经有一些学者发表了数据 流中频繁项集挖掘的论文。 复旦大学的周傲英等提出并实现了o - 6 算法嘲。该算法能够有效的控制内存的 消耗问题。东北大学的张昕等提出了一种新的启发式算法f p i l - s t r e a m l 7 。该算法 结合了倾斜窗口策略，在及时处理数据流的前提下，降低了数据的平均处理时间， 提供了更细粒度的查询。东南大学的刘学军等在借鉴f p g r o w t h 算法的基础上，提 出了f p - d s 算法俐。算法采用分段的思想，逐段挖掘频繁项集。该算法可以有效 的挖掘所有频繁项集，尤其适合长频繁项集的挖掘。浙江大学的王金龙、徐从富 对数据流中频繁项集挖掘进行研究和分类，并提出了一些研究方向【1 0 1 。 另外，一些其他研究单位的研究人员也在对数据流中的频繁项集挖掘技术进 行研究 2 1 3 本文的贡献 本文系统的介绍了数据流挖掘的概念以及介绍和实现了数据流频繁项集挖掘 的一些常见算法。在此基础上提出了一种有效的挖掘数据流中频繁项集的算法 f p f t 。f p f r 算法是一种挖掘数据流中最近频繁项集的算法。该算法采用了嵌入 时间窗口的前缀树的结构来存储频繁项集，节约了一定的空间。实验表明，与传 统算法相比该算法具有较好的空问和时间效率，适合数据流中频繁项集的挖掘。 1 4 本文的组织结构 本章主要给出了本课题研究的背景与意义，介绍了国内外在数据流处理技术 以及数据流挖掘方面研究的发展方向和研究成果。本章后面的内容组织结构如下： 第2 章，数据流挖掘与数据流综述在此章中，首先介绍了数据挖掘的基本 概念，然后介绍了数据流的基本概念和特点，以及与数据流相关的技术和研究热 点最后介绍了数据流挖掘的一些相关概念和特点，并且总结出数据流频繁项集 挖据中的一些关键性问题。 第3 章，频繁相集挖掘算法。在此章中，首先介绍了一些经典的频繁项集挖 掘算法，然后对现存的一些数据流中频繁项集挖掘的算法进行了介绍和总结最 后实验和分析了f p s t r e a m 算法和t n n e - s e n s i t i v es l i d i n g w m d o w 算法。 第4 章f p f t 算法。在此章中，提出了了f p f t 算法是一种挖掘数据流 中最近频繁项集的算法。通过实验分析，算法具有较好的时间和空间效率。 第5 章，总结和展望。在此章中，对本文的内容进行总结并对今后的研究进 行展望 3 2 数据挖掘与数据流综述 由于我们的算法中涉及到数据挖掘和数据流的概念，所以本章首先介绍数据 挖掘的基本概念，然后介绍数据流的基本概念和特点，以及与数据流相关的技术 和研究热点。最后介绍数据流挖掘的一些相关概念和特点，并且总结出数据流频 繁项集挖据中的一些关键性问题。 2 1 数据挖掘 数据挖掘( d a t am i n i n g ) 是在大型数据存储库中，自动地发现有用信息的过程。 数据挖掘是数据库中知识发现( k n o w l e d g ed i s c o v e r y i nd a t a b v q e , k d d ) 不可缺少的 一部分，而k d d 是将未加工的数据转换为有用信息的整个过程【1 6 1 。数据挖掘技术 用来探查大型数据库，发现先前未知的有用模式数据挖据还具有预测未来观测 结果的能力 与数据挖掘相近的同义词有数据融合、数据分析和决策支持等。数据挖掘是 多学科交叉的产物，结合了数据库、人工智能、统计学、机器学习、可视化等技 术。数据挖掘通过发现有用的新规律和新概念，提高了数据拥有者对大量原始数 据的深层次理解、认识和应用，解决了。数据丰富，知识贫乏”的问题。数据挖 掘具有广泛的应用前景。 数据挖掘能从大量数据中抽取出隐藏在数据之中的有用信息从而为决策者 进行决策提供重要的依据，大大提高决策的科学性和减小决策的盲目性。数据挖 掘系统可以帮助商业管理者更好地理解用户的行为，制订相应的用户服务政策， 从而增加商业机会例如电信公司通过发现用户通话的规律，制定更合理的优惠 政策。 2 2 数据流 在我们的现实生活中，很多应用都产生数据流。数据流具有它自身的一些特 点。与数据流相关的一些技术也如雨后春笋般地出现，这些技术在本节中有详细 的介绍。 4 2 2 1 数据流的概念及特点 数据流是指大量连续到达的、无限的、快速的、随时间变化的数据的有序序 列。它的形式定义是：数据流是指一个数据项的序列l l ，k ，k ，这些数据项 按下标递增的顺序排列，它们以成倍的、高速的、连续不断的、随时间变化、不 可预测和无限的方式到达。 数据流和传统的数据库中保存的数据不同，通常具有以下特点： 连续性数据流中的数据连续不断的到来； 无限性数据流中的数据是无限的； 高速性数据流中的数据高速到来； 数据分布随时间改变数据流中数据的分布随着时间不断的改变。 数据流的上述特征使得数据流的处理与传统的数据处理方法有很大不同数 据流处理算法有如下特征： 算法不能随机访问数据，而且只能一遍扫描或很少次数扫描数据； 算法执行过程中不可能存储所有的数据，算法只能利用概要数据结构存放 数据的信息，并且可以根据可利用的资源自动调整相应的参数进行处理； 算法必须适应数据分布的改变，分析结果也相应得随着数据分布的改变而 改变； 数据流处理具有实时性，算法必须快速处理数据和输出结果 一些大公司的日常生产、应用过程中会产生很大数量的数据。这些数据数量 巨大，而且增长迅速超出人们的想象例如，6 0 0 9 l e 每天接受2 亿次的查询任务， a t & t 每天收集的网络流量数据多达1 0 0 g b 。另外科学数据的采集( 如通过地球传 摩卫星或宇航观测系统等1 一般每天会产生上g 字节的记录。上述这些数据的数据 量非常庞大，无法全部存放在内存里，只能保存在二级以上存储器中。这样获取 特别是随机获取这些数据需要花费很高的代价。因此把这些数据建成数据流的模 型进行处理更为合适。 2 2 2 数据流技术 现在已经有一些技术通过计算和统计理论来解决数据流挖掘过程中产生的问 题和挑战。这些处理技术可以总结为基于数据的和基于任务的处理技术。在基于 数据的处理技术中，主要思想是通过概括整个数据集或者选择到来的数据流的一 个子集进行分析。在基于任务的处理技术中，采用计算理论来得到时间和空间有 效地解决方案。 s 一、基于数据的技术 基于数据的技术通过概括整个数据集或者选择到来的数据流的一个子集进行 分析。概要数据结构( s y n o p s i sd a t ag 呻c t 嘲) 和聚集( a g g r e g a t i o n ) 技术代表了 前者，采样( s a m p l i n g ) 、降载( l o a ds h e d d i n g ) 、略图( s k e t c h ) 技术代表了后者 这一小节主要介绍这些技术 概要数据结构( s y n o p s i sd a t as t r u c t u r e s ) 概要数据结构的创建借助于总结技术的应用。总结技术总结到来的数据流以 供将来的分析使用。已经提出的概要数据结构有直方图( h i s t o g r a m s ) 、小波分析 ( w a v e l e t 锄a l y s i s ) 由于概要数据结构不能代表数据集的所有特性，所以当使用 概要数据结构时产生的结果是近似的。 直方图是一种常用的概要结构表示方法，用于简洁地表达一个数据集合的数 据值分布情况( 如：一个库表中的一列) 。直方图可用于多重目的，如查询大小估计、 近似查询结果以及数据挖掘等。可以通过直方图来研究数据流的概要。直方图可 以用来解决那些在宽度和深度上变化的分布不同的连续桶的问题。传统的直方图 包括等宽直方图、等深直方图和v 优化直方图等。等宽直方图最简单，它把整个 值域分成等宽长度的桶：等深直方图每个存储桶中的元组数据相同：v ：优化直方图 使存储桶中的差分最小，每个桶的宽度可以是不相等的。数据流环境中使用比较 有效的直方图是等深直方图和v 二优化直方图。 小波变换是函数，信号分层分解的数学工具。其中h a a r 小波变换是最简单的小 波变换，易于理解和实现。小波变换可用t 范围查询的选择性估计，另外小渡变 换可以提高随机采样和直方图的效率 聚集( a g g r e g a f i o m ) 聚集是一个计算统计过程的方法。例如利用平均致( m e a n s ) 和方差( v a r i a n c e ) 来总结到来的数据流。挖掘算法通过使用这些聚集的数据来进行挖掘。聚集所产 生的一个问题是，它不能很好的代表数据分布高废变化的数据集一些算法已经 对合并在线聚集进行离线挖掘进行了研究。 采样( s a m p l i n g ) 为了避免存储整个数据流，可以以某个间歇性的周期对数据流进行随机采样。 如果事先知道数据流的长度的话，就可以直接选择无偏采样方法。然而，不可能 每次都能事先知道数据流的长度。这样的话，必须改变这种方法。它的基本思想 比较简单。样本的大小至少为n ，称作存储池。当新的数据到来的时候，新元素以 某个特定的概率代替存储池中的旧元素。当想得到一个无偏的随机样本的时候， 就可以在这个存储池中产生出来。假如从n 个元素的存储池中取大小为r l 的随 机样本，目前为止所见的元素个数为t 那么，在选择样本时，新元素代替旧元素 6 的概率就为r l t 。这也是很容易理解的。因为，我们是从到目前为止的t 个元素 中选取大小为n 的随机样本。 使用采样技术来进行数据流分析的一个问题是数据集的大小是未知的。因此 数据流的处理必须遵循特殊的分析才能够得到误差的范围。此外，在对数据流进 行不规则或者监督分析时使用采样技术将会出现问题。采样技术不能解决数据分 布变化的情况。对于采样技术中数据速率、采样率和误差范围三个参数之间关系 的很值得研究。 降载( l o a ds h e d d i n g ) 由于数据流经常是爆发性的且数据特征可能随时交化，因此要求数据流管理 系统具有很好的自适应性。当输入速率超过系统处理能力时，系统会产生过载且 性能下降。为了解决这一问题，降载技术是有效的途径之一。降载技术是丢弃数 据流中的一系列数据的处理过程。它成功的应用于数据流的查询中。 降载技术与采样技术有着相同的问题。降载技术丢弃了一些将来可能用于构 建模型或者是代表一个感兴趣的模式的数据。因此，它很难被应用到数据流挖掘 中。 略图( s k e t c h ) 略图技术使用很小的空间来描述数据的分布。它将数据流中的数据映射到建 立的数据结构中假设数据流取值有n 个不同的值，那么建立向量币) 的分布概要 数据结构其中1 3 的项目集组成2 频繁项目集也= a b ，a c ，a d - a e ，b c ，b d ， b e ，c d ，c e 。 生成：由工2 生成3 侯选集并通过扫描数据库得到它们的支持数 c 3 = ( a b c ，4 ) ( a b d ，3 ) ，( a b e ，2 ) ，( a c d ，3 ) ，( a c e ，2 ) ，( b c d 3 ) ，( b c e 2 ) ) ；挑选 m n s u p _ c o u n 仑_ 3 的项目集组成3 一频繁项目集三3 = a b c ，a b d ，a c d ，b c d 。 从生成：由3 生成4 侯选集并通过扫描数据库得到它们的支持数 c 扣( c d ，3 ) ) ；挑选m i n s u p c o u n 郾的项目集组成4 频繁项目集l 4 = a b c d ) 。 巧生成：由上4 生成5 侯选集c 5 = o ，工5 = o ，算法停止。 于是频繁大项集为 a b c d l 。 a p f i 面算法有两个致命的性能瓶颈： 它可能产生很大的候选项集例如，如果有l o 个频繁1 项集，则a 口r i o r i 算 法可能产生接近1 0 7 个元素的2 侯选集这样的庞大的候选项集在时间和空问上 都是很难接受的。 它可能重复扫描数据库需要很大的f o 负载每产生一次候选项集都要扫 描一次数据库如果频繁项集包含很多项，就需要多次扫描数据库，这样f o 开销 十分庞大【1 6 朔 f p g 哪岫算法是h m 等人在2 0 0 0 年提出的一种挖掘频繁项集的算法该算 法不用产生候选项集就可以挖掘出全部的频繁项集。它将提供频繁项集的数据库 压缩到一颗频繁模式树。并且保留项集关联信息。通过频繁模式树挖掘出频繁项 集。该算法只需两次扫描数据库。 构造一颗频繁模式树的过程如下： 扫描事务数据库d 一遍，生成频繁1 项集将频繁项集降序捧序，放入频繁 项表l 。 创建f p - 1 b c 的根节点，以“n i i i l ”标记它。对于d 中的事务t 选择其中的频 繁项并按l 中的次序捧序然后递归调用f p 伊、v 山来实现f p t i 增长 下面的算法给出了f p 朗刑也的描述。 算法p r o c e d mf p - g r o w t h ( 酬 1 ) 盯t r e e 含单个路径p 血印 2 ) f o r 路径p 中节点的每个组合( 记作， 3 )产生模式算u 口，其支持度乳肇弦r 产夕中节点的最小支持度； 4 ) e k 如r 鼯c h 啦在t r e e 的头部 1 7 产生一个模式，= qt ja ，其支持度s u p p o r t - - o a s u p t 加r t ；, 构造声的条件模式基，然后构造芦的条件f p 树t r e e 7 ) t r e e j t h e m , 8 )调用f p - g r o w t h ( t r e e ，刃； 9 ) ： 下面通过一个具体的实例来说明它的执行过程。对于表3 5 所给出的样本数据 库，我们实施f p g r o w t h 的算法，图3 1 给出了执行过程 表3 5 样本事务数据库 1 1 di t e m s e t lb ，c ，e 2a ，b ，c ，d 3a ，b 。c ，e 4b ，d ，e 5a ，b ，c ，d 首先，扫描数据库对每个项目生成支持度并按降序排列。简单i g 为 b 5 ，c a ， a 3 ，d 3 ，e 3 。然后递归调用f p - g r o w t h ，生成频繁模式树 n u l l o b - 6 c ：1 0 e = 6 ( i 读入t k 卜i 后 b ：4 c ：3 e = i ( 2 读入盯d | 2 后 t ，： b ：， c i e ：l o ) 耋, x r n 3 - 3 后 ( 喇i 入t 1 d _ 后母读入n d 弓后 图3 1f p - g r o w t h 算法的执行过程 f t g m e3 1t h ep r o c e s so f f p - g r o w t ha “山妇 1 8 f p - g r o w t h 算法只有两次数据库扫描，的确在减少挖掘所需的i o 代价方面进 行了有益的探索。而且它不会有庞大的侯选项集产生，减少了对内存临时空间的 占用。但是，该算法存在的问题是随着频繁模式树的增长可能使效率变得很差。 我们看一个例子，对于表3 6 给出的事务数据库，它最后生成的树为图3 2 的样子 表3 6 样本事务数据库 t a b l e3 6s a m p l eo f a n s 栅d m a b a t i d n a 叩- s d l a ，b ，c 。d ，f 2b ，c ，e 3 a ，b ，d 4 a ，b ，f 5 c ，d ，f 6e ，f 图3 2 f p 4 r e e 示意图 f i g u r e3 2f p - 缸x e 在这棵辫中，共有一个表、1 5 个节点和2 8 个链接需要存储和管理。而数据库 也不过只有6 个项目集( 每个项目集平均3 个多项目) 组成。因此，f p t 慨算法 在一些情况下的内存存储空间是不可低估的，而且这种树结构是一种非线性结构， 一般需要链表等形式存储本身就增加了存储链接信息的额外代价r 9 , 1 t i 3 3 数据流中频繁项集挖掘算法 数据流中频繁项集的挖掘是当前数据挖掘领域中的热点。近几年，一些研究 人员进行了深入地的研究并提出了一些有效的算法。这一节主要介绍总结了当前 1 9 文献中的一些算法 3 3 1 采样算法 采样是利用较小的数据集代表全部的数据集，通过采样数据集反映整体数据 的特征。由于数据流的无限性和高速性，不能将数据存储起来进行挖掘。采样算 法是通过采样数据流中的数据来获得近似的结果。这- - , j , 节主要介绍s a c k , s a m p l i n g 和l o s s y c o u n t i n g 两个采样算法 1 ) s t i c k ys a m p l i n g 算法 s a c k ys a m p l i n g 是一个基于采样的算法。它计算数据流中具有乒误差的频繁 项。该算法接受用户输入的三个参数：支持度j ( 0 ，1 ) 、误差参数麟，、失败的概 率尻 算法采用的数据结构d s 是一个形如 ，- ) 的条目的集合。其中f 是数据流中项 e 的频率的近似估计。初始时，数据结构d s 是空的，采样率f 设置为1 。对一个 元素以采样率t 进行采样的意思是以概率l ，r 选择该元素。对每一个到来的元素e ， 如果p 已经在d s 中存在一个条目，则增加该元素的相应频度：否则以采样率f 来 对该元素进行采样。如果该元素被采样选择，就添加一个新的条i i ( e ，1 ) 到d s 中； 否则，忽略元素e 并且移动到数据流中的下一个元素。 采样率r 会随着数据流的生命周期做如下改变：假设t = j 占如g i s 。艿。l ，最开 始的2 f 个元素以采样率r = 2 进行采样，接着的4 f 个元素以采样率r - - 4 进行采样， 一直这样进行下去。当采样率改变的时候，算法扫描d s 中的条目并且做如下更新： 对于每一个条目( e 乃，重复投掷一枚无偏置的硬币直到投掷成功，对不成功的投掷， 对f 减1 ：如果f 在这个过程中变为0 ，就从d s 中删除这个条目。其中不成功的 投掷次数服从几何分布 最后算法输出d s 中质有的f g 一) n 的条目。s d c k y s a m p l i n g 算法以至少 为1 巧的概率计算争误差的频繁项，且使用至多2 s z 曙b 。艿。) 个条目。算法的空 问复杂度独立于数据流当前长度n 。 s t i c k ys a m p l i n g 算法在采样的过程中可能丢弃了一些重要的数据。此外，当数 据流中数据分布改变时，可能对挖掘的结果产生重要的影响。 2 ) 【棚町c o u n t i n g 算法 l o s s yc o u n t i n g 算法是一个计算数据流中单一项计数的确定性算法。它使用最 多为l d o g ( e n ) 的空间( 是数据漉当前长度) 。算法接受用户输入两个参数：支持 度s ( 0 ，1 ) 、误差参数f j 在l o s s yc o u n t i n g 算法中数据流被分成宽度为包含w = n 占1 个事务的桶。桶 用从1 开始的桶i d 来标识。当前桶的i d 被标识为矗。值为l n w i 。对于元素e ， 我们标记他在数据流中到目前为止的频度为石。这其中和w 是确定的，6 。 和五是随着数据流的进行而改变的变量。 算法采用的数据结构d 是一个形如以z4 ) 的条目集合。其中e 是数据流中的 一个元素。厂是一个代表估计频率的整数，是频率f 可能出现的最大误差 算法的具体描述如下： 初始时，d 为空。当一个新元素e 到来时，首先查找d 中是否存在一个元 素e 的条目若查找成功，对e 的条目中的频率f 增加一。否则，创建一个新 的条目以l ，i ) 。 当到达桶的边界时，对d 进行修剪。对于d 中的条目k z4 ) ，如果 ，+ a s 则删除该条目 当用户请求满足阈值为s 的项时，输出d 中所有厂6 一占) 的条目。 l o s s yc o u n e m g 算法是一个挖掘数据流中频繁一项集的近似算法。它使用的空 问与数据流的长度n 成对数增长 3 ) l o u yc o u n t i n g 算法扩展 l o s s yc o u n t i n g 算法可以扩展为计算数据流中频繁项集的算法。算法的输入是 一个事务集合的数据流其中每一个事务都是一个项的集合。记数据流当前的长 度为算法接受用户输入的两个参数：支持度j 和误差参数e 。算法的关键之处 在于处理变长的事务和避免显示的列举出事务的所有子集。 该算法的数据结构d 是一个形如( s e t , f , 4 ) 的条目集合。其中耐是所有项的集 合的一个子集，厂是一个代表估计频率的整数，4 是频率，可能出现的最大误差。 初始对，数据结构为空。 将到来的事务流分成桶，每个桶包括，= n b 1 个事务桶用从1 开始的桶i d 来标识当前桶的i d 被标识为6 。 首先，将尽可能多的事务读入到内存中。然后一起处理这批事务。随着时间 的推移，可用内存的数量可能增加或减少我们用，来标记在内存中正在被处理 的当前一批事务的桶的个数 接着更新集合d ： 更新集合：对于d 中的每一个条目o e 工4 ，计算s e t 在当前这批事务中 出现的次数并更新f o 如果更新的条目满足，+ 4 s 6 删，则删除该条目 产生新条目：如果在当前批中的一个项集s e t 的频率启芦并且s e t 未出现在 d 中，则创建一个新的条( s e t , f , 卅) 。 对于任意一个频率a 的项集s e t 都在d 中有一个条目。并且如果一个条目 ( s e t , f , 4 ) d ，s e t 的真实频率丘r 满足盎丘匹j 物。当用户请求阈值为j 的项集时， 输出d 中所有饼，咕) 的条目。 该算法的实现主要有三个模块：b u f f e r 、t r i e 、s e t g e n 。其中b u f f e r 重复读取一批事务到可用内存。t r i e 维护数据结构d 。s e t g e n 对当前批的事务 进行操作，列举事务的子集和频率。并且和t r i e 一起完成更新d 和产生新条目 的操作 3 3 2 略图算法 略图技术使用很小的空间来描述数据的分布。它将数据流中的数据映射到建 立的数据结构中。略图算法的优点是高效快速。算法通过简单的哈希操作将数据 项映射到s k e t c h 结构中进行统计但是，算法的误差相对较大并且目前的算法主 要是针对1 项集的挖掘。 1 ) c o u a ts k e t c h 算法 c o u n ts k e t c h 算法用c o u n ts k e t c h 数据结构来可靠的估计数据流中频繁项 集的频率。算法一遍扫描数据流并且是在能够达到很好的空间范围内。 算法需要确定t 和b 两个参数。设h i 一，h ，是从对象到 l ，6 映射的哈希函 数，j l ，毋是对象到 + l ，1 的哈希函数。s l 是两两独立的并且所有的哈希函数都 独立于其它函数。c o u n ts k e t c h 数据结构包括这些哈希函数和一个t b 的计 数器数组。t b 的数组可以被解释成为一个有t 个哈希表的数组，其中每个数组包 含b 个桶( 计数器) 。哈希函数h t 映射对象q 到第f 个哈希表中b 个计数器中的一 个。用定义所m 来代表这个计数器 数据结构c 支持两种操作： a d d ( c ，叮) ：f o r f 【l ，f 】，h i m 忙却m e s t 】呻l t e ( c ，叮) ：r e t m um e d i 柚( 鬼【g 】却【g 】) 操作a d d 对于新项g 根据川们的值增加或减少每个哈希表中相应计数器的 值。操作e s t i m a t e 返回一个项计数的估计值估计值取所有与项目相关的计数 值与s i 【们乘积的值的中值 算法最终的估计是t 个哈希表的估计的中值，而不是平均值。这是因为即使到 了最后也没有完全消除高频率元素的碰撞问题，并且仍然会对估计的一些子集引 入大量的误差。均值对于例外非常敏感，然而中值足够健壮。 建立了这样的数据结构后，算法就能直接并且简单的实现。对于每一个元素， 我们使用c o u n ts k e t c h 数据结构来估计它的计数，并且保持一个到目前为止 最多的k 个元素的堆。 给定一个数据流叮i ，霉mf o re a c h j = 1 ，l ： 1 ) a d d ( c ，积 2 ) i f q 在堆中，增加它的计数。e l s e ，如果e s t m a t e ( c ，q j ) 比堆中最小的估 计计数大则将缶加到堆中，并将最小估计计数元素从堆中移除。 c o u n ts k e t c h 算法在内存中维护一个大小为k 的堆，并利用c o u n ts k e t c h 数据 结构来对项集进行统计。算法不断调整堆中的项集，最后得到最频繁的k 个项集。 2 ) c o n n t - m i ns k e t c h 假设向量a 是一个严格递增的模式。向量的维度为厚，在时间t 的状态是 口( 沪【口l ( 琐，a g o a g o 。为方便当说到当前状态时忽略t ，初始时a 是一个零向 量。向量中每一个分量的更新以数据对的流的形式呈现第t 个更新是a b 曲，也 就是：口o ) = 口( f 一) + q ；a i o ) = a ( f j ) f i 。 c o u n t - m i ns k e t c h 进行基本的点查询操作时，先计数然后计算出最小的值。用 e 表示自然对数的基。一个参数为o ，国的c m m t - m i n s k e t c h 代表一个两维的计数器， 宽度为w 深度为d ：c o u n t 1 ，1 】c o u , u d , w 给定参数忙，回，设置 - = k 一，d = 陬1 6 1 。每一个计数器的初始值都是零此外还包括d 个哈希函 数h 1 h a ： l 。j i 卜， l 。w j ，这些函数从相互独立的簇中随机选择的。 当一个更新以c f ) 到来时，用c ，更4 i 。将c t 加到每一行的一个计数器中；所选 的计数器由| 5 1 ，来确定。v i s j s d 设，。d 堋l 阢岛( 伽一研彤，姒咖+ 白。更新过程 的图如3 3 所示 + c - 、 ， j ，一 l e = ：= 一 _ _ 一 - e 下 + c - + c 图3 3c o u n t - m i ns k e t c h 的更新 f i g u r e3 3u p d a t i n go f c o t m t - m i ns k e t c h c o u n t - m i ns k e t c h 使用的空间是一个为w d 个计数器的数组( 使用w d 个字) 和d 个h a s h 函数( 每个函数使用两个字) 对于点查询蚴给出的值为e f n f u 知c o u n t l 姒1 ) 】其中估计值口 e i ，且以概 率至少为1 - 6 ，使得巳口+ 删， 3 3 3 滑动窗口算法 滑动窗口算法是对数据流中窗口范围内的数据进行挖掘。通过滑动窗口可以 对数据流中进行多时间粒度的挖掘，例如f p s t r e f l m 算法。还可以只挖掘窗口范围 内的频繁项集，饲如s l i d i n gw i n d o w 方法。还可以利用其挖掘全局范围内的频繁 项集，例如d sc f i 算法。滑动窗口