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

北塞奎盈太凳甄茔位监塞生塞撞墨 中文摘要 数据流是一个按时间到来的有序的项集。和传统静态数据库中的数据不同的 是，数据流是连续的、无限的、通常以很高的速度到来的并且数据分布随着时间 而改变【由于数据流的特点使得传统的频繁项集挖掘算法难以适用许多研究人 员对数据流中频繁项集挖掘进行了研究目前。数据流中频繁项集挖掘已成为数 据挖掘中的基本问题之一 针对数据流的特点，论文对数据流处理技术和数据流挖掘中的关键问题进行 了研究和总结。论文对一些关键问题的解决技术进行了研究。论文对经典的频繁 项集挖掘算法进行了介绍和实验通过实验和分析可以看出数据流的无限性、高 速性使得经典的频繁项集挖掘算法难以适用到数据流中此外，论文对于当前现 存的一些数据流中频繁项集算法进行了介绍，分析和总结。 本文最后提出了f p - c o u n t m i n 算法该算法将数据流分段并利用改进的 f p g r o w t h 算法挖掘分段中的频繁项集然后，利用c o u n tm i l ls k e t c h 进行项集计 数。算法解决了压缩统计和计算快速高效的问题。通过和f p - d s 算法的实验对比， f p - c o u n t m i n 算法具有较好的时间效率。 关键词：数据流；数据挖掘；数据流挖掘；频繁项集 分类号：t p l 8 2 a d a t a 硎瑚m i s a n o r d e r e ds e q u e n c e o f i t e m s l h 砒础髓m t i m e l y o i x 慨o d i f f e r e n t f r o md a t ai ni r a d i t i o n a ls t a t i cd a t a l 脚, d a t am 陀锄明玳c o n f i n u o m 。u n b o u n d e d , u s u a l l yc 咄w i t hm g hs p e e da n d h a v ead a t ad i s 臼i b u t i o nt h a to 自mc h a n g e sw i t ht i m e 【1 1 t r a d i t i o m lm i n i l 略a l g o r i t h n a md i f f i c u l tt oc o p cw i t hd a t a 破r md u et oi t s c k 哦蝌 e 】僦c m a n yl 船e m - c h c n mh a v e 蚰t i e dm i n i n g 自。q 珊斌i t i m l 缸i nd a t as t r e a m a n dn o w , m i n i n gf r e q u e n ti t e m s e t si nd a t as t r e a mi so 嘶o f t h em o s tb a s i cl x o b l e m si n d a t am i n i n g a c c o r d i n gt o t h ec h a n 吣把洲co fd a t a 捌r 崩l m t h ep a p e rr e s e a l h e sa n d s u m m a r i z e st h et e c h n i q u eo fd a t as t e a mp r o c e s 她i s s u e si nd a t as t r e a mm i n i n g m p a p e rr e s e a r c h e ss o m et e c h n i q u eo fs o l v i n 8t h ei s s u e s t h ep a p e ri n m x i u c e ss o m o c l a s s i c a l 白阄u 咖诹知5 啦a n dd o e ss e x l 埘 i m e n t a l i o n 1 1 1 r o u g be x p e r i m e n t a t i o n a n da 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 _ i i c n ti t e m s e t sm i n i 玎ga l g o r i t h m st o e x t e n dt od a t as 由mh 蛾m 辩o f t b el i m i t l e s sa n dh i g hs p e e do f d a t as t r e a m b e s i d e s ， t h ep a p e ri n u o d u c e s 。a n a l y z e sa n d 矾蛐衄m f i z e s 默n ee x i s t e n td a ms e 咖m i n i n g a l g o r i t h 札 f i n a l l y t h ep a p e rp r o p o s e sf p - c o u m m i na l g o r i t h nt h ea l g o r i t h mp a r t i t i 啷t h e d a ms 咖ma n du s e sm o d i f i e df p - g r o w t ha l g o r i t h mt om i n i n gf r e q u e n t “眦s e t si n e v e r ys e g m e n la n dt h e n , hc o u n t si t 嘲n 鼹临i nc o u n tm i ns k e t c h t h ea l g o r i t h ms o l v e s t h e p r o b l e m o fc 伽p 硎s t a d 蛳ca n de f f e c t i v e c o m p u t a t i o n t 协u g h e x p e r i m e n t a t i o n a n dc o m p a r i s i o nw i t hf p - d sa l g o r i t h m , w ef i n df p - c o u n t m i n a l g o r i t l u n h a s a g o o d t i m e e f f i c i e n c y k e y w o r d s ：d a t as t r e a m ；d a t am i n i n g ；d a t as t r e a mm i n i n g ；f i e q u e n ti t e m s e t s c l a s s n o ：t p l 9 2 致谢 本论文的工作是在我的导师黄厚宽教授的悉，f i , 指导下完成的，黄厚宽教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响在此衷心感谢三年来 黄厚宽老师对我的关心和指导 黄厚宽教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都给 予了我很大的关心和帮助，在此向黄厚宽老师表示衷心的谢意 林友芳副教授对于我的科研工作和论文都提出了许多的宝贵意见，在此表未 衷心的感谢。 在实验室工作及撰写论文期间，贺志博士、韩升老师等对我研究工作给予了 热情帮助，在此向他们表达我的感激之情。 另外也感谢我的父母，他们的理解和支持使我能够在学校专心完成我的学业。 1 1 研究背景 l 综述 现在越来越多的应用产生的数据以流的形式出现。这些数据数量巨大，而且 随时问源源不断的到来。例如，传感器网络、网络监控、w e b 服务器日志、电信呼 叫记录、股票交易联机分析等等这些数据数量巨大，而且增长迅速超出人们的 想象。例如，g o o g l e 每天接受2 亿次的查询任务，a t & t 每天收集的网络流量数 据多达1 0 0 g b 。 在这些流数据中蕴含着大量的知识和有用的信息。通过获取这些流数据中的 信息和知识，我们可以提高系统的性能、获取更多的价值。例如在一些网络中j 通过网络流量监控能够发现网络上的瓶颈，从而进行负载均衡提高网络的效率。 另外通过网络监控还可以发现网络上的异常来进行入侵检测。另外，在金融应用 中还可以通过分析交易的流数据进行欺骗检测 数据挖掘是获取大量数据中有用知识和信息的方法。在数据上进行适合、有 效的挖掘才能获取我们需要的知识和信息关联规则挖掘是数据挖掘的一种重要 方法。这种方法挖掘数据集中的频繁项集，通过对频繁项集的分析来生成关联规 则获取知识。 传统的数据挖掘所面向的对象是静态的、有限的数据挖掘算法通过将数据 从磁盘读入内存进行分析和处理来挖掘其中的有用知识数据流中的数据数量巨 大且连续不断的到来。由于受到时间和内存、c p u 等资源的限制，传统的数据挖 掘方法不再适用如何挖掘数据流中频繁项集，这就给研究人员带来了机遇和挑 战近年来，挖掘数据流中的频繁项集成为数据挖掘领域中的研究热点许多研 究人员和组织对数据流中的频繁项集的挖掘进行了研究。 1 2 国内外研究现状 1 2 1 国外研究现状 国外在数据流挖掘方面的研究开展的较早，取得的科研成果较多、研究的进 展比较快 目前，国外在数据流挖掘方面有两个比较有影响的小组：一个是s t a n f o r d 大 学的r m o t w a n i 教授领导的研究小组，另一个是u 1 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 as t r e a mm a n a g e m e n ts y s t e m ) 概念，他们的研究得到了美国国家自然科学基金的资助。后者的研究侧重在数据 流分析方面，对于数据流的在线分析，从聚类、分类、频繁项集挖掘以及可视化 等角度做了大量研究工作，提出了倾斜时间窗i i ( t i l t e d - l i m ew i n d o w ) 策略，采用不 同时间粒度保存数据流的信息，他们的研究得到了美国军方和国家自然科学基金 的资助田。 在数据流中频繁项集的挖掘方面，许多国外的学者进行了深入的研究并提出 了自己的算法。g u r m e e = ts i n g hm a n k u 和r a j e e vm o t w a n i 提出了s t i c k ys m p l i n g 算 法和l d s s yc o u n t i n g 算法挖掘数据流中的频繁项，并且扩展l 0 s s yc o u n t i n g 算法来 挖掘数据流中的频繁项集【3 】m o s e sc h a - i l 盥等借助于c o u n ts k e t c h 的数据结构提 出一个一遍扫描数据流来挖掘数据流中频繁项的算法 4 1 g r a h a mc o r m o d e 和 s m u t h u k r i s h n a n 提出了c o u n t - m i ns k e t c h 数据结构嘲。该结构可以快速的进行 点查询r i c h a r d1 v l k a r p 和s c o t ts h e n k e r 提出了一种两遍的扫描算法来挖掘频繁 项1 6 。c g i a n n e l l a 等提出了一种f p s t r e a m 模型挖掘数据流中的频繁项集川。还有 一些研究人员提出了许多重要的算法。 一些国外的研究人员还对数据流中频繁项挖掘的关键技术进行了总结和探 讨。 1 2 2 国内研究现状 国内在数据流挖掘方面的研究开展的较晚，但是已经有一些学者发表了数据 流中频繁项集挖掘的论文。 复旦大学的周傲英等提出并实现了0 - 8 算法嘲该算法能够有效的控制内存的 消耗问题。东北大学的张听等提出了一种新的启发式算法f p i l - s 1 r e a m 9 1 。该算法 结合了倾斜窗口策略，在及时处理数据流的前提下，降低了数据的平均处理时间， 提供了更细粒度的查询。东南大学的刘学军等在借鉴f p g r o w t h 算法的基础上，提 出了f p - d s 算法【i 川。算法采用分段的思想，逐段挖掘频繁项集。该算法可以有效 的挖掘所有频繁项集，尤其适合长频繁项集的挖掘。浙江大学的王金龙、徐从富 对数据流中频繁项集挖掘进行研究和分类，并提出了一些研究方向【l i l 。 另外，一些其他研究单位的研究人员也在对数据流中的频繁项挖掘技术进行 研究。 2 1 3 本文主要工作 本文对数据流中频繁项集挖掘中的关键问题和技术进行了总结、探讨。并介 绍了当前挖掘数据流中频繁项集的主要算法以及所作相关工作 对以上内容，本文分为6 个章节分别进行详细分析和介绍 第2 章，数据流处理技术和挖掘的关键问题。在此章中，介绍了数据流的处 理技术和进行数据流中频繁项集挖掘的关键问题并对一些关键问题探讨了解决的 技术 第3 章，经典的频繁项集挖掘。在此章中，介绍了一些传统的频繁项集挖掘 算法并进行了实验和分析。 第4 章，数据流中频繁项集挖掘算法在此章中，对现存的一些数据流中频 繁项集挖掘的算法进行了介绍和总结。 第5 章，f p - c o u n t m i n 算法。在此章中，提出了了f p - c o u n t m i n 算法。该算法 解决了数据流挖掘中的压缩统计和计算高效的问题。通过实验分析，算法具有较 好的时间效率。 第6 章，总结和展望。在此章中，对本文的内容进行总结并对今后的研究进 行展望。 2 数据流处理技术和挖掘的关键问题 2 1 数据流及处理的特点 数据流是一个随着时间连续不断数据序列它的形式定义是：数据流是指一 个数据项的序列i l 丑，k ，这些数据项按下标递增的顺序捧列，它们以成倍 的、高速的，连续不断的、随时间变化、不可预测和无限的方式到达 随着信息技术的发展，现在越来越多的应用中数据以流的形式出现，例如， 网络监控、股票交易、w e b 日至记录、传感器网络等。 数据流和传统的数据库中保存的数据不同，通常具有以下特点： 连续性数据流中的数据连续不断的到来； 无限性数据流中的数据是无限的； 高速性数据流中的数据高速到来； 数据分布随时问改变数据流中数据的分布随着时间不断的改变。 对数据流中的频繁项集挖掘时找出数据流中的频繁项集。由于数据流的上述 特点，在进行数据流挖掘算法设计时必须考虑： 由于数据流的无限性、连续性、高速性的特点，算法不能随机访问数据，而 且只能一遍扫描或很少次数扫描数据； 由于数据流中数据的无限性和可利用空间的有限性，不可能存储所有的数据。 算法只能利用概要数据结构存放数据的信息，并且能够根据可利用的资源自动调 整挖掘参数进行挖掘 由于数据流的高速性，算法必须快速处理数据和输出挖掘结果； 由于数据流中数据分布随时间不断改变，算法必须适应数据分布的改变、分 析结果随着数据分布的改变而改变。 一些大公司的日常生产、应用过程中会产生很大数量的数据这些数据数量 巨大，而且增长迅速超出人们的想象例如，o o o g l e 每天接受2 亿次的查询任务， 朋1 & t 每天收集的网络流量数据多达i o o g b 。另外科学数据的采集( 如通过地球传 感卫星或宇航观测系统等) 一般每天会产生上g 字节的记录。上述这些数据的数据 量非常庞大，无法全部存放在内存里，只能保存在二级以上存储器中这样获取 特别是随机获取这些数据要花费很高的代价。因此把这些数据建成数据流的模型 进行处理更为合适。 2 2 数据流处理技术 现在已经有一些技术通过计算和统计理论来解决数据流挖掘过程中产生的问 题和挑战这些处理技术可以总结为基于数据的和基于任务的处理技术在基于 数据的处理技术中，主要思想是通过检测整个数据集的一个子集或者将数据变换 成一个合适大小的代表性的数据集在基于任务的处理技术中，采用计算理论来 得到时间和空间有效地解决方案 2 2 1 基于数据的技术 基于数据的技术通过概括整个数据集或者选择到来的数据流的一个子集进行 分析概要数据结构( s y n o p s i sd a t as t r u c t u r e s ) 和聚集( 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 ta n a l y s i s ) 由于概要数据结构不能代表数据集的所有特性，所以当使用 概要数据结构时产生的结果是近似的。 直方图用来估计一个数据流中元组取值的频数分布，是一种简单描述总体分 布的方法。一般一个直方图由两部分组成：一个将元组的值域分成若干个存储桶的 分割方式，和一个从存储桶序号到自然数的映射。该映射实际表示的是该存储桶 中元素的个数传统的直方图包括等宽直方图、等深直方图和v 优化直方图等。 等宽直方图最简单，它把整个值域分成等宽长度的桶；等深直方图每个存储桶中的 元组数据相同；v 优化直方图使存储桶中的差分最小，每个桶的宽度可以是不相等 的数据流环境中使用比较有效的直方图是等深直方图和v - c t 化直方图 小波变换是函数信号分层分解的数学工具其中h a a r 小波交换是最简单的小 波变换，易于理解和实现。小波变换可用t 范围查询的选择性估计，另外小波变 换可以提高随机采样和直方图的效率。 聚集( a g g r e g a t i o n ) 聚集是一个计算统计过程的方法。例如利用中位数( m e a n s ) 和方差( v a r i a n c e ) 来总结到来的数据流。挖掘算法通过使用这些聚集的数据来进行挖掘。聚集所产 生的一个问题是，它不能很好的代表数据分布高度变化的数据集一些算法已经 对合并在线的聚集进行离线挖掘进行了研究 采样( 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 ) 略图技术使用很小的空间来描述数据的分布。它将数据流中的数据映射到建 立的数据结构中。假设数据流取值有n 个不同的值，那么建立向量砸) 的分布概 要数据结构，其中l - i 2 的项目集组成2 - 频繁项目集l 2 - a b ，a c ，a d ，b c ，b d ，b e ， c d , c e 。 三3 生成：由忱生成3 侯选集并通过扫描数据库得到它们的支持数 c 3 = ( a b c ，3 ) ，( a b d , 2 ) ，( a c d j ) ，( b c d , 2 ) ，( b c e , 2 ) ) ；挑选m i n s u p _ c o u n t _ 2 的项目 集组成3 频繁项目集l 3 = a b c ，a b d ，a c d ，b c d ，b c e 。 “生成：由上3 生成4 - 侯选集并通过扫描数据库得到它们的支持数 c 4 = ( a b c d , 2 ) ；挑选m i n s u p _ c o u 咖_ 2 的项目集组成乒频繁项目集l 4 = a b c d ) 。 上5 生成：由伪生成5 侯选集c 5 = o ，l s = o ，算法停止 于是频繁大项集为 a b c d ，b c e a m i o r i 算法有两个致命的性能瓶颈： 它可能产生很大的候选项集。例如，如果有1 0 个频繁1 项集，则a m i o n 算 法可能产生接近1 0 7 个元素的2 侯选集。这样的庞大的候选项集在时间和空间上 都是很难接受的 它可能重复扫描数据库，需要很大的i o 负载。每产生一次候选项集都要扫 描一次数据库。如果频繁项集包含的项很多的话就需要多次扫描数据库。这样i o 1 4 开销十分庞大【噬堋 2 2 2a p r i o r i 算法的改进 为了提高a p r i o r i 算法的效率，研究人员在a p r i o l i 算法基础上提出了一些变形 算法这些变形主要有： 基于h a s h 的项集计数；如果一个k 项集在h a s h - u e e 的路径上的一个计数值 低于阈值，那它本身也不可能是频繁的该算法由p a r k 等提出来，通过实验我们 可以发现寻找频繁集主要的计算是在生成频繁2 - 项集h 上，p a r k 等就是利用了这 个性质引入杂凑技术来改进产生频繁2 项集的方法 事务压缩：不包含任何频繁k 项集的交易也不可能包含任何大于k 的频繁集。 从而我们可以将这些事物移去，这样在下一遍的扫描中就可得要进行扫描的事物 集的个数。这就是a p r i o r i t i d 的基本思想。 分割：一个项集要想在整个数据库中是频繁的，那么他至少在数据库的一个 分割上是频繁的。s a v a s e r e 等设计了一个基于分割( p a r t i t i o n ) 的算法，先把数据库从 逻辑上分成几个互不相交的块，每次单独考虑一个分块并生成该块上所有的频繁 项集，然后把产生的频繁集合并，用来生成所有可能的频繁集，最后计算这些项 集的支持度 采样：采样方法的核心就是随机从数据集d 中采集s 样本集：然后搜索s 中 频繁项集而不是d 中的。这样就以效率换取准确性。样本集合s 大小以能够在内 存中完成频繁项集挖掘为准，因此整个值需要扫描一遍数据库，由于只搜索s 中 的频繁项集而不是d 中的，因此有可能漏掉一些全局频繁项集。 动态项集计数：动态项集计数技术将数据库划分为标记开始点的块不像 a p r i o r i 仅在每次完整数据库扫描之前确定新的候选，这种变形可以在任何开始点 添加新的候选项集。该技术动态地评估以被计数的所有项集的支持度，如果一个 项集的所有子集以被确定为频繁的，则添加它作为新的候选。结果算法需要的数 据库扫描比a 皿o r i 少1 1 2 ，1 3 1 3 2 3c l o s e 算法 1 9 9 9 年p a s q u i e r 等人提出关闭项目集挖掘理论，并给出了基于这种理论的 c l o s e 算法。他们给出了关闭项目集的概念，并讨论了这个关闭项目集格空间上的 基本操作算予c l o s e 算法是基于这样原理的：一个频繁关闭项目集的所有关闭子 集一定是频繁的，一个非频繁关闭项目集的所有关闭超集一定是非频繁的因此， 可以在关闭项目集空间格上讨论频繁问题实验证明，它对特殊数据是可以减少 数据库扫描次数的 下面是c l o s e 算法作用到表3 1 数据集的执行过程( 假如r a i n s u p+_coun卢3) 扫描数据库得到三l = 3 ) ，5 ) ( c ，4 ) ，3 ) ，3 ) ；相应关闭项目集为a ( a 产 a b c ，3 ) ，c i 户 b ，5 ，c l 纾 b c ，4 ，c i ( d 产 b d ，3 ，c l ( e ) = ( b e ，3 ； l 2 = c a b ，3 ) ，( a c 渤，c ，4 ) ，d ，3 ) ，t a e , 3 ) 相应关闭集为c 2 衅 a b c 3 ； 工3 ，“，上5 不用测，于是频繁大项集为( a b c c l o s e 算法仍然沿用a p r i o r i 算法递增测试项目集的方法来寻找频繁项目集的， 但是它是在关闭项目集格空间上测试，提高了生成频繁项目集的效率，并且可能 减少扫描数据库的次数。 c l o s e 算法存在的主要问题是：( 1 ) 当最小支持度较小时，每个层次上的关 闭频繁项目集的数目仍很大，因此不可能大幅度提高效率；( 2 ) 事先很难确定具 体的数据库扫描次数；( 3 ) 为形成关闭项目集需要额外的代价【埘 2 0 0 0 年h a l l 等提出了一种f p - g r o w t h 算法该算法挖掘全部的频繁项集而不 用产生候选项集它将提供频繁项集的数据库压缩到一颗频繁模式树，但仍保留 项集关联信息。通过频繁模式树挖掘出频繁项集。该算法只需两次扫描数据库。 构造一颗频繁模式树的过程如下： 扫描事务数据库d 一遍，生成频繁l 一项集将频繁项集降序排序，放入频繁 项表l 。 创建f p - t r e e 的根节点，以。n u l l ”标记它。对于d 中的事务进择其中的频 繁项并按l 中的次序捧序然后递归调用f p _ _ g r o w t h 来实现f p _ t r e e 增长 下面的算法给出了f p 卫r o w t h 的描述。 算法p r o c e d u r ef p - g r e w t h ( t r e e , a ) 1 ) i ft r e e 含单个路径pt h e a 2 ) f o r 路径p 中节点的每个组合( 记作夕 3 )产生模式卢u 口，其支持度s u p p o r t = 夕中节点的最小支持度； 4 ) e l s e f o r 住吐a i 在t r e e 的头部 产生一个模式胞j u a ，其支持度s u p p o 慨s u p p o r