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

五邑大学硕士学位论文 摘要 数据流研究是目前一个新兴的热门领域，国内外学者提出了各种数据流处理的 技术、算法和具体应用。和传统静态数据库中的数据不同的是，数据流是连续的、 无限的、高速的、数据分布随着时间而改变的数据序列。数据流频繁项集挖掘是数 据流挖掘领域的基本问题之一，已经引起国内外研究者的广泛关注，提出了许多有 效的数据流频繁项集挖掘算法。 针对数据流的特点，论文对数据流处理模型和数据流挖掘中的关键问题做了介 绍，对当前的一些数据流频繁项集挖掘算法进行了分析，比较和总结。 本文在此基础上，提出了一种实时的挖掘数据流近似频繁项的算法( n e c 算法) 和基于滑动窗口的数据流频繁项集挖掘算法( s w f p t - m i n e r 算法) 。n e c 算法在允许 的偏差范围内，能有效地挖掘数据流中的所有频繁项。在有限的存储空间和及时处 理数据流的前提下，降低了数据项的最坏处理时间，满足在线实时分析处理要求， 提高了输出结果的精确率。理论分析和实验验证了这种方法的有效性。s w f p t - m i n e r 算法采用分段的思想，逐段挖掘频繁项集，通过挖掘局部频繁项集，可以有效地挖 掘所有的频繁项集。通过滑动窗口技术，可以快速获取最近一个时期内的频繁项集。 分析和实验表明算法有较好的性能。 最后，在研究数据流频繁项挖掘的基础上，实现了一个基于数据流挖掘的网站 排名应用系统。 关键词：数据流挖掘；关联规则；滑动窗口；频繁项；频繁项集 五邑大学硕士学位论文 a b s t r a c t t h er e s e a r c ho fd a t as t r e a mi sa ne m e r g i n gh o td o m a i ni nr e c e n ty e a r s d o m e s t i ca n df o r e i g n s c h o l a r sh a v ep u tf o r t hav a r i e t yo fd a t as t r e a mp r o c e s s i n g t e c h n o l o g y ，a 1 9 0 r i t h m sa n ds p e c i f i c a p p l i c a t i o n s 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 cd a t a b a s e s ，d a t as t r e a mi sc o n t i n u o u s ，u n b o u n d e d ， h i g h - s p e e da n dad a t ad i s t r i b u t i o nt h a to f t e nc h a n g e sw i t ht i m e f r e q u e n ti t e m s e tm i n i n gi so n eo ft h e f u n d a m e n t a lp r o b l e m si nd a t as t r e a mm i n i n g i th a sr e c e i v e dc o n s i d e r a b l ea t t e n t i o ni nt h ep a s tf e w y e a r sa n dm a n ye f f e c t i v ea 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 gt ot h e c h a r a c t e r i s t i c so fd a t as t r e a m ，t h ep a p e ri n t r o d u c e st h em o d e lo fd a t as t r e a m p r o c e s s i n ga n dt h ek e yi s s u e si nd a t as t r e a mm i n i n g t h ep a p e ra n a l y z e s ，c o m p a r e sa n ds u m m a r i z e s s o m ee x i s t i n gd a t as t r e a mm i n i n ga l g o r i t h m s 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 sar e a lt i m ea l g o r i t h mf o rm i n i n ga p p r o x i m a t e f r e q u e n ti t e mo v e rd a t as t r e a m f n e ca l g o r i t h m ) a n daf r e q u e n ti t e m s e tm i n i n ga l g o r i t h mo v e rd a t a s t r e a mb a s eo ns l i d i n gw i n d o w s ( s w f p t - m i n e ra l g o r i t h m ) w i t h i nt h ea l l o w a n c eb o u n do fe r r o r s ， n e ca l g o r i t h mc a nm i n ea l lt h ef r e q u e n ti t e m sf r o md a t as t r e a me f f e c t i v e l y i tc a nd e c r e a s et h et i m e o fd e a l i n gw i t he a c ha a t ai t e mo nt h ew o r s tc o n d i t i o n f u l f i lt h er e q u i r e m e n to fr e a lt i m ea n a l y s ea n d d i s p o s a lo n l i n e ，a n de n h a n c et h ep r e c i s eo fr e s u l t sr e t u r n e db a s eo nt h e l i m i t eo ft i m ea n ds p a c e a t l a s t ，t h ea n a l y s eo ft h e o r ya n de x p e r i m e n tv e r i f yt h a tt h ea p p r o a c hi se f f e c t i v e t h es w f p m i n e r a l g o r i t h mp a r t i t i o n st h ed a t as t r e a ma n dm i n et h ef r e q u e n ti t e m ss t e pb ys t e p i tc a nm i n ea l l t h e f r e q u e n ti t e m s e t se f f e c t i v e l yb ym i n i n gp a r to ff r e q u e n ti t e m s e t s f r e q u e n ti t e m s e td u r i n gr e c e n t p e r i o dc a l lb eg o tw i t ht h es l i d i n gw i n d o w st e c h n i q u eq u i c k l y t h ee x p e r i m e n t sa n da n a l y s i ss h o w t h a tt h ea l g o r i t h mh a sg o o dp e r f o r m a n c e f i n a l l y , o nt h eb a s i so ft h e r e s e a r c ho ff r e q u e n ti t e m s e tm i n i n go v e rd a t as t r e a m ，w ed e v e l o pa n w e b s i t ev a l u i n gs y s t e mb yt h em e a n so fd a t as t r e a mm i n i n g k e yw o r d s ：d a t as t r e a mm i n i n g ；a s s o c i a t i o nr u l e ；f r e q u e n ti t e m ；f r e q u e n ti t e m s e t s ；s l i d i n gw i n d o w i l 本人声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由作者本人独立完成 的。有关观点、方法、数据和文献的引用都已在文中指出，并与参考文献相对应。 除文中已注明引用的内容外，本论文不包含任何其他个人或集体己经公丌发表的作 品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 作者：张小彬 签字：利，彬 2 0 0 9 年4 月15 日 五邑大学硕士学位论文 1 1 课题研究背景 第一章绪论 现在越来越多的应用产生的数据以流的形式出现。这些数据数量巨大，而且随 时间源源不断的到来。例如，传感器网络、网络监控、w e b 服务器同志、电信呼叫 记录、股票交易联机分析等应用系统。这些系统中的数据数量不但巨大，而且增长 迅速，超出人们的想象。 在这些流数据中蕴含着大量的知识和有用的信息。通过获取这些流数据中的信 息和知识，可以提高系统的性能、获取更多的价值。例如在网络应用中，通过网络 流量监控能够发现网络上的瓶颈，从而进行负载均衡，提高网络的效率；同时通过 网络监控，还可以发现网络上的异常，来进行入侵检测，从而增强网络安全。在金 融应用中，可以通过分析交易的流数据进行欺骗检测。 数据流是实时的、连续的、有序的项的序列。数据流中的项是由到达时间隐含 表示或者由时间戳显式指定，并按照数据项到达的顺序加以控制。当数据流是不可 预测和随时间变化时，数据流到达的频率不能被处理系统所控制。由于数据流源源 不断到达的这种无界性特点，完整地将数据流实时存储到传统的数据库管理系统中， 并在其中进行操作是不可行的。由于只能对数据流中的项进行一次顺序扫描，因此， 需要一种动态的增量式的算法来处理数据流。并且，多数应用要求在数据到来的同 时进行决策分析，这对处理时间提出了更高的要求。如何在数据流上进行数据挖掘， 这就给研究人员带来了机遇和挑战。 数据流频繁项集挖掘是一类重要的数据挖掘问题，可以广泛应用在关联规则挖 掘、相关性分析、入侵检测、序列模式、分类和聚类等多种数据挖掘任务中。如何 挖掘数据流中频繁项集，成为数据挖掘领域中的研究热点。例如，在网络监控和通 信工程中，通过挖掘频繁模式，能够检测网络异常( 如网络拥塞) 并找出原因( 诸 如硬件错误、黑客入侵) 以实现快速自主式修复；在w e b 中发现频繁模式，可优化 网站结构，提高网站性能；在传感器网络数据流中发现频繁模式，可灵活组织传感 器，以发现最大量的有用数据。 综上所述，数据流中频繁项集挖掘算法及其应用研究具有重大的理论和现实意 义。 五邑大学硕士学位论文 1 2 国内外的研究现状 对数据流的研究包括两个方面：数据流管理技术和数据流挖掘技术。数据流管 理技术主要研究开发数据流管理系统所需要的技术，主要包括：数据流连续查询语 言的设计、查询优化、资源管理( 主要是内存) 、近似查询操作、流系统的调度等。 数据流挖掘技术主要研究数据流上的聚类、分类、频繁模式和时序分析等数据挖掘 技术。 数据流中频繁项集挖掘作为一个新兴的研究领域引起国内外专家和学者的关 注，很多大学和研究机构在这方面进行了大量的研究工作。 1 2 1 国外研究状况 国外在数据流挖掘方面的研究开展得较早，取得的科研成果较多、研究的进展 比较快。 目前，国外已经出现了多种数据流管理系统原型，例如，斯坦福大学的s t r e a m 系统、布朗大学和麻省理工学院的a u r o r a 系统、s t a t s t r e a m 系统、加少 i 大学伯克里 分校的t e l e g r a p h c q 系统、c o u g a r 及乔治亚州工学院研制的o p e n c q 系统、维斯 康新迈迪讯实验室的n i a g a r a c q 系统等【1 1 。 在数据流中频繁项集的挖掘方面，许多国外学者进行了深入的研究并提出了自 己的算法。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 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 算法来挖掘数 据流中的频繁项集【2 1 。m o s e sc h a r i k a r 等借助于c o u n ts k e t c h 的数据结构提出一个一 遍扫描数据流来挖掘数据流中频繁项的算法【3 】。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 数据结构4 1 。r i c h a r dm k a r p 和s c o t ts h e n k e r 提出了一 种两遍的扫描算法来挖掘频繁项【5 1 。c g i a n n e l l a 等提出了一种f p s t r e a m 模型挖掘 数据流中的频繁项集【6 j 。还有一些研究人员提出了许多重要的算法。 1 2 2 国内研究状况 国内在数据流挖掘方面的研究开展得较晚，但是已经有一些学者发表了数据流 中频繁项集挖掘的论文。 复旦大学的周傲英等提出并实现了0 6 算法【7 1 。该算法能够有效的控制内存的 消耗问题。东北大学的张听等提出了一种新的启发式算法f p i l s t r e a m i 引。该算法结 合了倾斜窗口策略，在及时处理数据流的前提下，降低了数据的平均处理时间，提 2 五邑大学硕士学位论文 供了更细粒度的查询。东南大学的刘学军等在借鉴f p g r o w t h 算法9 1 的基础上，提出 了f p d s 算法【10 1 。算法采用分段的思想，逐段挖掘频繁项集。该算法可以有效的挖 掘所有频繁项集，尤其适合长频繁项集的挖掘。王伟平等提出的一种有效的挖掘数 据流近似频繁项算法【1 1 1 ，可以保证算法结果满足s 一近似的要求，算法的空问复杂度 为o ( s 。1 ) ，流数据每个数据项的平均处理时间为d ( 1 ) 。 1 3 本文的主要工作 本文主要对数据流中频繁项集挖掘算法及其应用进行了研究，主要工作包括以 下几个方面： 第一：分析数据流的特点，对比传统数据挖掘与数据流挖掘的不同，理解数据 流挖掘模型。研究了一些高效的数据流中频繁项集挖掘算法，分析了它们的优缺点。 第二：提出了一种实时的挖掘数据流近似频繁项的算法( n e c 算法) 。该算法 在允许的偏差范围内，能有效地挖掘数据流中的所有频繁项。在有限存储空间和及 时处理数据流的前提下，降低了数据项的最坏处理时间，满足在线实时分析处理要 求，提高了输出结果的精确率。 第三：改进l o s s yc o u n t i n g 算法，使其适用于滑动窗口中的频繁项挖掘。本文 用来存储数据流概要信息的数据结构s w f p - t r e e ( s l i d i n gw i n d o wf r e q u e n tp a t t e r n t r e e ) ，类似于前缀树，在此基础上提出了基于滑动窗口的数据流频繁项集挖掘算法 ( s w f p t - m i n e r 算法) ，对过期数据进行适当处理，可以快速获取最近一个时期内的 频繁项集。 第四：在研究数据流频繁项挖掘的基础上，设计实现了一个基于数据流挖掘的 网站排名应用系统。该系统使用了本文提出的一种实时的挖掘数据流近似频繁项的 算法，实现网站的排名，实时响应用户的查询请求。 本文所有的实验均在p c 机上进行，c p u 主频为2 6 6 g h z ，内存为2 5 6 m b ， w i n d o w sx p 操作系统为测试平台，算法使用j a v a 语言实现。 1 4 论文结构和内容安排 本文共分6 章，内容包括： 第一章首先阐明了课题的背景和意义，国内外研究现状，本文的主要工作和论 文组织结构。 五邑大学硕士学位论文 第二章首先介绍了数据挖掘、数据流的基本概念和特点，以及介绍了基于数据 流模型的挖掘与传统数据挖掘的不同。然后介绍了数据流挖掘的一些相关概念和特 点，并且总结出数据流频繁项集挖掘中的一些关键性问题。最后介绍了现有的一些 数据流中频繁项集挖掘的算法。 第三章提出了一种实时的挖掘数据流近似频繁项的算法。该算法是一种挖掘数 据流中频繁项的算法。通过实验分析，算法具有较好的时间和空间效率。 第四章提出了一种基于滑动窗口的数据流频繁项集挖掘算法。根据数据流的特 点，将数据流分段，采用s w f p t r e e 结构存储数据流中的频繁项集，随着数据流的 流入不断更新s w f p t r e e 结构，并对其进行剪枝，从而有效地挖掘整个数据流中的 频繁项集。 第五章实现了一个基于数据流挖掘的网站排名应用系统。该系统包括网络数据 包的捕捉、h t t p 数据包的过滤、h t t p 数据包的预处理、频繁项挖掘算法和查询结 果显示等几部分。 第六章对本文的工作进行总结，并对进一步的研究进行分析和展望。 4 五邑大学硕士学位论文 2 1 数据挖掘 第二章数据流和数据流挖掘 数据挖掘( d a t am i n i n g ，简称d m ) 1 2 1 是在大型数据存储库中，自动地发现有 用信息的过程。数据挖掘是数据库中知识发现( k n o w l e d g ed i s c o v e r yi nd a t ab a s e ， k d d ) 不可缺少的一部分，而k d d 是将未加工的数据转换为有用信息的整个过程。 数据挖掘技术用来探查大型数据库，发现先前未知的有用模式。数据挖掘还具有预 测未来观测结果的能力。 与数据挖掘相近的同义词有数据融合、数据分析和决策支持等。数据挖掘是多 学科交叉的产物，结合了数据库、人工智能、统计学、机器学习、可视化等技术。 数据挖掘通过发现有用的新规律和新概念，提高了数据拥有者对大量原始数据的深 层次理解、认识和应用，解决了“数据丰富，知识贫乏的问题。数据挖掘具有广 泛的应用前景。 数据挖掘能从大量数据中抽取出隐藏在数据之中的有用信息，从而为决策者进 行决策提供重要的依据，大大提高决策的科学性和减小决策的盲目性。数据挖掘系 统可以帮助商业管理者更好地理解用户的行为，制订相应的用户服务政策，从而增 加商业机会。例如，电信公司通过发现用户通话的规律，制定更合理的优惠政策。 2 2 数据流 2 2 1 数据流的概念及特点 数据流是指大量连续到达的、无限的、快速的、随时间变化的数据的有序序列 1 3 - 1 6 j 。也就是说，数据流是一个数据项的序列( s 1 ，s z ，岛，) ，这些数据 项按下标递增的顺序随时间变化出现，它们以成倍的、高速的、连续不断的、随时 间变化的、不可预测和无限的方式到达。 自2 0 世纪7 0 年代以来，数据库技术得到了迅速的发展和广泛的应用，传统数 据库获得了巨大的成功。但是，在2 0 世纪末，随着信息技术的飞速发展，一种新的 应用模型却对它提出了有力的挑战。这种称为数据流( d a t as t r e a m ) 的应用模型广泛 出现在众多应用领域，例如，金融市场、网络监控、电讯数据管理、传感器网络等 1 6 - 2 3 】。这类数据的共同特点是，不断地产生、在时间维度上严格有序、其数值不断 五邑大学硕士学位论文 地变化，而且，这些数据一般都规模庞大、增长迅速。利用传统的数据库技术管理 这种数据，需要将数据全部保存在物理介质中，然后通过提交数据操纵语言( d a t a m a n i p u l a t i o nl a n g u a g e ，简称d m l ) 访问物理介质来获取查询结果。但是，由于数据 流的数据源源不断，在有限的存储空间中无法保存数据流的全部数据，而且，数据 流应用对查询处理往往有着很高的实时性要求，这也决定了数据不能保存下来进行 处理。因此，已有的数据库技术无法对数据流数据进行有效的管理，必须进行数据 流管理新技术的研究【1 6 , 1 7 。 数据流形式的数据不同于传统的基于集合的相对静止的数据。数据流数据连续 到达，频繁变化，数据量事前是不确定的，也可能是无限的。归纳起来，数据流的 共同特点是： ( 1 ) 无限性。数据流是不断到来的，若要将其全部存储，需要的存储空间是 无限的。 ( 2 ) 未知性。数据流的数据值是不断改变的，利用预测方法也不能准确地预 测下一时刻将到来的数据值。 ( 3 ) 不可再现性。对于数据流上的数据，一旦流过处理节点就不会再次出现。 在现实世界中，数据流应用非常广泛，例如，网络监控和交通工程、电信通信 纪录、网络安全、金融业务流、传感器网络、网络同志和网页点击流等。在数据流 模型中，部分或全部数据都以一种连续流的形式在线到达，与传统的关系模型相比， 具有以下不同： ( 1 ) 在数据流模型中，处理的数据不再是从磁盘和内存中随机访问读取的数 据，而是一个或多个连续的、无穷的数据项组成的时间序列。 ( 2 )数据流中的数据是实时到达的，而数据库中的数据存储在磁盘中。 。 ( 3 ) 数据流中的数据是按序流过的，不受应用系统所控制，一般只能对数据 进行顺序访问，而磁盘中的数据可以随机访问。 ( 4 ) 数据流中的数据是无限的，而数据库中的数据是有限的。 ( 5 ) 由于在有限的存储空间内无法存储无限数据流的全部数据，因此数据流 中大部分的数据在处理后被丢弃了，除非特意保存，否则不能被再次取出处理，或 者再次提取数据代价昂贵。所以，数据流上的查询多数只能得到近似的查询结果， 而数据库上的查询则可以得到精确的查询结果。 ( 6 ) 系统只能保存数据流全部数据的一个有限子集或统计数据，并随着数据 6 五邑大学硕士学位论文 流上新数据的到来进行更新，这种更新的频度取决于数据流数据到达的速度。显然， 数据流的更新频度要远远高于数据库中数据更新的频度。 因此，在数据流应用系统中，不能简单地将数据流存放到传统的数据库中再进 行查询。因为，传统的数据库并不是为不断快速到达的连续数据流而设计的，不能 直接支持数据流应用中典型的“连续查询”。而且，在对数据流的查询和分析中，近 似性和适应性也是两个重要特点，而传统的数据库管理系统所注重的却是通过静态 的执行计划，提供精确的查询结果，不支持近似性和适应性操作。应对数据流管理的 特殊要求，数据流管理系统( d a t as t r e a mm a n a g e m e n ts y s t e m ，简称d s m s ) 应运而生 了。 2 2 2 数据流管理系统模型 由于数据流管理系统处理的数据流是一种潜在无限的、连续快速的、随时间不 断变化的数据序列，而且在实际处理过程中，这种数据序列具有信息到达顺序不可 控、单位时间数据到达量不均匀、数据量庞大的特点。这就要求d s m s 应当具有以 下的功能： ( 1 ) 在一定的时间内，对信息能够进行重组并处理。 ( 2 ) 由于物理存储空间的限制和处理效率的要求，对数据流进行在线处理时， 一般只能对数据进行一遍扫描。 ( 3 ) 一般不采用阻塞方式处理数据流，以保证数据处理的效率。 ( 4 )能对数据进行提炼，并采取随机的或有选择地丢包等减负措施，保证在 突发流量情况下系统的整体性能。 ( 5 ) 对异常数据有足够迅速( 接近于实时) 的反应能力。 图2 1 【1 3 】描述了d s m s 的一般功能结构，用于支持长期运行，连续的、标准的、 持久的查询。主要由3 部分组成：输入部分，处理部分和输出部分。输入部分主要 对输入的数据流进行初步的过滤，并兼有应付突发流量的基本功能。处理部分是整 个系统的主干，由3 部分组成：( 1 ) 暂存子系统，数据分为3 部分暂存：静态暂存 部分存储元数据( 例如d s m s 各部分的物理位置等) ，允许用户自定义相关的设置； 工作暂存部分存储当前处理的数据流；如果遇到突发流量而没有足够的物理存储空 问，可以对数据进行归纳，将获得的纲要( s y n p o s e s ) 或摘要存储在纲要暂存中。( 2 ) 查询缓存，主要存储用户定义的查询条件，一般的d s m s 系统支持用户在线修改查 询条件。( 3 ) 查询处理子系统，主要功能是从查询缓存中提取用户定义的查询，根 7 五邑大学硕士学位论文 据优化需要对其进行分组，并将其作用于从输入部分获得的数据流。查询处理子系 统还具有自适应功能，能根据当前数据流量和查询条件调整系统查询策略。输出部 分主要的功能是保证处理所得的结果能够平稳地输出，一般都包含临时存储的功能。 - 输 查询缓存 用户修改查询 入八 - 部 查 分 询 处 静态暂存 理数据更新 子 ：暂 输f 系 ；- lj ：作暂存 存 统 一 ：一j 上阡一竹 子 如 系 邵 - i 纲要暂存 统 分 一 一i ”引 图2 1 数据流管理系统结构 2 2 3 数据流模型特点 数据流系统处理的数据允许一些或者所有数据都以连续的数据流的形式出现， 数据流管理系统既可以管理常规存储的数据，又可以处理多维的、连续的、无限制 的、快速的、随时间变化的数据流，它支持长时间的连续查询，并且产生连续的时 序的结果。综合来说，数据流系统模型( d s m s ) 与关系数据库管理系统( d b m s ) 有以下不同之处： ( 1 ) 关于数据源的前提假设方面，传统的数据库是限定的、静态的数据集合， 它们具有限定的大小、可控制的操作，是持久的、结构详细定义的记录( 关系) 。数 据流则是无限的、在线的数据序列，它们的大小是不确定的，具有不可预知的动作， 是非持久的、无结构或半结构化的数据项。 ( 2 ) 在计算方面，传统的数据库对数据集合进行计算，这种计算是多次的或 无限次的，具有较高时间复杂度和空间复杂度，可看作事务处理。而数据流管理系 统则是对数据流进行计算，这种计算是一次性的，要求即时响应，其控制或查询大 多为只读式查询。 ( 3 )在查询处理方面，传统数据库查询处理为单次查询，其查询计划为静态 的，。在执行之前要进行优化，且只运行一次，最终生成确定的查询结果。对流式数 据的查询处理则是连续的，它们的查询计划是动态的，需要长期的不断的运行，随 时间的变化不断进行优化，其结果是无限的数据流和近似的结果。 8 五邑大学硕士学位论文 2 3 数据流挖掘 数据流中蕴含了大量的有用信息，因此，从数据流中挖掘出未知的、有价值的 模式或规律，是数据流控制的主要任务。数据流挖掘技术的潜在应用是十分广泛的， 从政府管理决策、商业经营决策和信息安全等很多领域，都可以找到数据流挖掘技 术的应用。下面举出一些数据流挖掘技术的应用领域： 通讯记录：提取关于客户的分类模型、欺诈用户行为模型等； 网上交易数据：潜在的客户和潜在的利润增长点； 股票交易数据：股票走势模式及预测； 网络f 1 志：攻击类型分析、入侵检测等； 传感器数据：分析地理和环境的变化，进行预测。 2 3 1 数据流挖掘的特点 如果把传统的存储于数据库中的数据称为静止的数据，那么流数据就是动态的 数据。对于静止的数据，它的挖掘过程可以分成两个部分：先把数据收集起来存储 在数据库中，然后在数据库上应用各种挖掘技术进行挖掘。而对于流数据，它的收 集过程和挖掘过程是同时进行的，必须以最快的速度，从不断到来的数据中挖掘出 感兴趣的模式( i n t e r e s t i n gp a t t e m ) ，来响应用户的实时查询。基于数据库的传统数据 挖掘都要求数据分析处理结果的精确性，但是对于流数据，由于数据收集时间的有 限性，分析处理速度的有限性，无法在精确度上做过多要求，使得挖掘结果的近似 性( a p p r o x i m a t i o n ) 成了不同于传统数据挖掘的一个特点。 数据流的特殊要求使得传统的静态数据挖掘算法难以直接应用1 9 , 2 4 1 ，虽有一些 算法可用于增量数据处理【2 5 1 ，但它们只能处理离线数据，而在线数据流对算法的实 时性、自适应性和空间复杂度等都提出了更高的要求。具体地说，数据流频繁项集 挖掘具有如下不同于传统挖掘方法的特剧15 , 2 6 】： ( 1 ) 实时响应性。由于数据流快速到达，为了能够跟上数据流的输入速度， 要求算法高速处理数据元素，并实时、连续地输出频繁项( 项集) 挖掘结果。 ( 2 ) 结果的近似性。数据流无法完全存储和再次扫描，故只能得到近似的处 理结果。 ( 3 ) 低空间复杂度。由于只能利用有限的空间来存储动态变化的数据流，因 此，必须设计空间复杂度更低的挖掘算法。特别是，为了能够对项( 项集) 进行支 9 五邑大学硕士学位论文 持数计数，不仅应存储频繁项( 项集) ，而且应存储那些随着时间的变化可能变成频 繁的非频繁项( 项集) 。此时，内存的容量和算法的空间复杂度直接决定项集存储的 数量，从而影响挖掘结果的准确性。 ( 4 )自适应性。根据可用的资源动态调整存储内容和所用参数，随着当前各 种手持设备和传感器网络的普及，这种特性越发重要。 2 3 2 数据流频繁项集挖掘模型 目前数据流挖掘方面的研究主要集中在数据流的聚类、分类和频繁项集挖掘方 面。 频繁项集挖掘是找出支持度大于给定支持度的所有项集，这些项集被称为频繁 项集。由于数据流的连续性、无限性、高速性及数据分布随时间不断改变这些特性， 传统的频繁项集挖掘方法不再完全适用。这就使得在进行数据流中频繁项集的挖掘 时，需要考虑比传统的数据库中频繁项集挖掘更多的问题。 文献 15 ，2 7 中分别给出了通用的数据流处理模型。在通用数据流处理模型的基 础上，分析一些已有的数据流频繁项集挖掘算法的处理方式，可以概括出关于数据 流频繁项集挖掘的数据流处理模型，如图2 2 【2 8 j 所示。 图2 2 数据流频繁项集挖掘的数据流处理模型 该模型主要由三个模块组成：预处理模块、数据流挖掘引擎和结果显示模块。 对于到达的数据流，首先由预处理模块处理，并将处理过的事务数据放在临时 缓冲区中。为了保证后续挖掘算法能够及时处理缓冲区中的数据，这期间可能会利 用采样技术等进行近似处理。 数据流挖掘引擎负责处理查询请求和数据的挖掘。为了辅助数据挖掘和提高查 询速度，算法通常需要在内存中维护一些数据结构。可以将这些数据结构分成三类： 数据集压缩结构，用于挖掘过程的数据结构和结果集压缩结构。数据集压缩结构以 1 0 五邑大学硕士学位论文 紧缩的方式存放数据流中的事务数据，当数据到达缓冲区时，由数据流挖掘引擎将 数据压缩到数据集压缩结构中；用于挖掘过程的数据结构是挖掘过程中需要应用到 的一些数据结构；结果集压缩结构存放挖掘的结果。一般的数据流频繁项集挖掘算 法都具有前面两种结构。另外，为了加速查询速度，有些算法还在内存中维护结果 集压缩结构，当查询请求到达时，直接从结果集中获得相应的答案，但并不是每个 算法都在内存中维护结果集。维护结果集的好处是能够加速查询速度，但不足之处 是会牺牲算法的空间效率和时间效率。 结果显示模块以用户易理解的形式输出所挖掘的频繁项集。 另外，在挖掘时机上，存在两种方式：一种方式是，当每一事务到达时，数据 流挖掘引擎除了将其压缩到压缩数据集结构之外，并立即求出当前考察窗口中的结 果集；另一种方式是，当事务到达时，只是将其压缩到压缩数据集结构中，只有当 用户请求挖掘时，才对当前考察窗口中的事务数据进行挖掘，或者周期地对考察窗 口中的数据进行挖掘。第一种方式的好处是能够立即了解结果的变化，文 2 9 ，3 0 中的算法采用了第一种方式。但当数据较稠密，结果集变化较频繁时，该方式的算 法效率通常比第二种方式低。当用户请求获得结果的频率较低时，第二种方式比较 适合。大多数算法采用第二种方式。 2 3 3 数据流频繁项集挖掘及其关键问题 由于数据流的特点，在对数据流进行频繁项集挖掘时，我们需要考虑以下问题： ( 1 ) 数据处理模型建立进行挖掘的数据流中数据的处理模型； ( 2 ) 压缩数据结构 建立压缩的数据结构存储无限的数据中的有用数据； ( 3 ) 计算高效的一遍扫描算法高速处理数据流； ( 4 ) 概念漂移适应数据分布的变化； ( 5 ) 自适应性根据资源和数据流进行自我调整。 一、数据处理模型 在进行数据流挖掘算法设计时，首先要考虑的问题是要对数据流中哪些数据进 行哪些挖掘。数据处理模型便是对数据流中数据进行处理、挖掘的模型。当前的数 据流挖掘算法中主要存在三中数据模型：l a n d m a r kw i n d o w s 、d a m p e dw i n d o w s 、 s l i d i n gw i n d o w s 。 l a n d m a r kw i n d o w s 模型挖掘从某一叫做l a n d m a r k 的时间点到现在的所有历史 数据中的频繁项集。无限的窗口是这一模型的特殊情况。它挖掘从数据流丌始到当 五邑大学硕士学位论文 前所有的数据中的频繁项集。但是，这一模型不适合于人们只对数据流中最近的信 息感兴趣的应用。 d a m p e dw i n d o w s 模型也叫做时间衰退( t i m e f a d i n g ) 模型。在这种模型中，数 据流中每一个项集都有一个权值。该权值随时间逐渐减小，即新出现的项集对该项 集的频度影响大于原来的项集。这种模型考虑对新旧数据赋予不同的权值。这适合 于旧的数据对挖掘结果产生影响会随着时间减弱的应用。 s l i d i n gw i n d o w s 模型挖掘和维护当前窗口中的频繁项集。窗口的大小根据具体 应用和资源来确定。在金融和股票交易中，使用滑动窗口模型更合适。 一个l a n d m a r k 模型可以转变成其它两种模型。在其上加上时间衰退函数就能使 其转变为d a m p e d 模型。在其上跟踪、处理一个滑动的窗口中的数据就能使该模型 变为一个s l i d i n gw i n d o w s 模型。 不同的数据模型适用于不同的具体应用。在进行数据流挖掘算法设计时，具体 使用哪种模型根据具体的应用对象而定【3 。 二、压缩的数据结构 静态数据上的频繁项集挖掘是在多遍扫描数据库之后，收集所有项集的计数信 息，并且丢弃非频繁项集和它们的计数信息。但是，在数据流上进行频繁项集挖掘 时这种方法是不可行的。第一，当巨大的数据流连续不断地到来时，不可能在内存 中存储所有的项集和它们的计数。第二，项集计数随新到来的数据而改变。 一种算法是存储最频繁的项集和它们的计数。这种算法存储了最重要的信息， 但是，丢弃了非频繁项集的计数和将来有可能成为频繁项集的项集。可以看到，为 了收集更多的资源来获得更精确的结果，就会使用更多的内存空间和需要更多的处 理时间。 。 这就需要一个有效的压缩的数据结构来存储、更新和检索收集的信息。由于内 存空间有限和巨大的数据流又是连续不断地到来，如果不能建立这样一种数据结构， 将会很大程度的降低挖掘算法的性能。因为，即使我们在磁盘上存储了这些信息， 附加的i o 操作将会增加处理时间。由于巨大的数据量，不可能通过重新扫描整个 输入数据来满足在线查询高度响应的要求，因此，数据结构必须增量维护。能否建 立一个好的压缩数据结构是一个数据流挖掘算法性能好坏，甚至是否可行的重要基 础【3 1 1 。 现存的一些算法使用的压缩数据结构有f p - 树、前缀树。树形结构压缩程度较 五邑大学硕士学位论文 高，是常用的数据结构。略图是进行频繁项集统计的一种有效的压缩数据结构。它 将计数映射到一个s k e t c h 数据结构中进行压缩统计。在设计算法时，需要选择适合 的项集压缩数据结构和项集计数的统计压缩数据结构。此外，还有一些其它的概要 数据结构。 三、计算高效的一遍扫描 由于数据流的无限性和高速性的特点，在进行频繁项集挖掘时，不可能像传统 频繁项集挖掘那样多次扫描数据来进行计算。这就要求算法必须一遍或者很少次数 的扫描输入数据。 虽然一遍扫描算法能够比传统的算法更快更有效，但是当面对高速的数据流时， 如果算法的计算比较复杂，则可能导致算法的失败。这就要求在算法设计时，必须 设计一种高效的计算方法，这样才能快速处理高速到来的数据流【3 1 1 。 c o u n ts k e t c h 算法和c o u n t m i ns k e t c h 算法中利用快速的哈希操作将项映射到 s k e t c h 中去。哈希操作简单、快速，能够适应数据流高速的特点。在设计数据流挖 掘算法时，必须考虑计算的操作简单、快速。 四、概念漂移 数据流中的数据分布随着时间不断的改变。这些变化经常使在旧的数据上建立 的模型与新的数据产生不一致，而且需要频繁的更新模型。在某一时间段内出现的 频繁项集可能在下一个时间段内变成非频繁的项集。同样，在某一时间段非频繁的 项集在下一时间段可能变成频繁的项集。如果只在数据结构中存储频繁项集的计数， 当我们需要一些潜在的、稍后变为频繁项集的非频繁项集的计数时，得不到这些信 息。因此需要考虑处理概念漂移的技术1 3 1 1 。 滑动窗口技术能够针对窗口大小的数据流进行挖掘，不会受到以前挖掘结果的 影响。f p s t r e a m 算法中在频繁模式树中嵌入时间窗口，可以挖掘不同时间粒度的频 繁项集。在设计针对数据分布不断变化的挖掘算法时，可以考虑使用滑动窗口技术 挖掘不同范围和不同时间粒度的数据。 五、自适应性 在数据挖掘中，内存和c p u 等资源十分珍贵。如何有效利用这些资源，是设计 数据流挖掘算法时需要考虑的又一问题。 当可用资源较少时，流数据高速到来很快就会耗尽资源。如果在算法中不考虑 资源的使用情况，则很可能导致大量数据的丢失，甚至挖掘产生错误和失败。当可 五邑大学硕士学位论文 用资源较多时，如果算法能够根据可用资源来进行调整，则可以提高挖掘的精度和 速度。另外，当前各种手持设备和传感器网络的普及也要求算法能够根据不同的设 备和资源来自行调整。 所以，根据资源来自行调整挖掘参数进行有效的挖掘，是算法设计时要考虑的 问题之一【3 。 降载技术在一定程度上可以解决数据流爆发或者数据流输入超过系统处理能力 的情况。但是降载技术丢弃了一些比较重要的数据。因此，在使用降载技术解决数 据流挖掘算法的自适应性问题时，要慎重考虑。此外，数据流挖掘算法还可以考虑 在处理能力有限的情况下，使用一些概要的数据结构代表数据进行粗粒度的数据处 理。 六、项集计算 在进行数据流中频繁项集挖掘时，如何计算需要进行统计的项集是需要考虑的 重要问题之一。数据流中的数据量巨大，不能对数据流中的事务一一列举其子集进 行统计。首先，事务的子集可能很大。一个长度为1 0 的事务的子集有2 1 0 个子集。 其次，事务子集的计算操作比较复杂和消耗资源。此外，也没有必要对事务的所有 子集进行统计。 f p g r o w t h 算法【9 】是一种挖掘频繁项集的较好算法。该算法扫描两次数据产生数 据的频繁模式树。如何找到一个很好的算法来计算数据流中事务的项集是一个非常 重要的问题。同时，这也是关联规则挖掘中的重要问题。 2 4 数据流中经典频繁项集挖掘算法 频繁项集挖掘的关键步骤就是如何快速准确地对项( 项集) 进行支持数计数，以 获得满足最小支持度要求的频繁项( 项集) 。对于数据流，这个问题更加突出，内存 的限制导致只能选择可能成为频繁的项( 项集) 来进行快速近似的支持数计数。算法 设计的首要目标就是控制空间复杂度，只有降低空间复杂度，才能在有限的内存空 间中多对一些项集进行计数，从而更好地控制误差。 由于在大量数据流快速到达时，无法用有限的内存来精确发现频繁项集，迫使 我们必须放弃一些数据项或数据包，只对最可能频繁的数据项进行计数，从而得到 近似结果，这其实就是一个对不完全样本进行统计计数的问题。查询结果虽然只是 真实结果的近似，但数据流频繁项集挖掘算法可以保证，近似查询结果与真实结果 五邑大学硕士学位论文 之间的误差不超过用户指定的区间范围。下面，给出挖掘数据流中频繁项( 项集) 近 似算法的相关概念。 定义2 1 设s ( 0 ，1 ) 和s ( 0 ，1 ) 分别是用户指定的支持度和误差度( s l 。当第+ 1 个桶正在被 处理时，这个条目被插入。之前存在的关于e 的条目最迟可能在第个桶的边界处被 删除。通过归纳，当删除发生时，e 的真正频率计数不超过。进一步，厂是自从e 的条目被插入以来e 真正的支持数。可以得出后，即在第1 个至第6 。个桶中e 的 真正频率计数，至多是f + a 。结合条目删除规则厂+ 6 。，得到乒6 “一，r 。 引理2 3 如果e 不出现在s 中，那么压s n 。 证明：如果对于一个元素e ，当它被删除时( 被w 整除) ，该引理正确，那么 它适用于所有其它的取值，从引理2 1 和引理2 2 ，我们推断出当元素e 被删除时 e , n 。 引理2 4 如果( e ，f ，a ) s ，那么f 乒+ s 。 证明：如果a = 0 ，f = 乒，否则e 在前个桶的事务处理过程中被删除。由引理 2 2 可知，当最近一次对e 的删除发生时，e 的真正频率计数至多为，因此乒厂+ 。 既然6 。一l e n ，得出结论f 乒f + e n 。 那些支持数超过e n 的元素至多有1 个。引理2 3 表明它们在s 中都有相关条 目存在。引理2 4 进一步表明，所有这些元素的估计频率的误差必