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

r e s e a r c ho n a l g o r i t h mf o rm i n i n gf r e q u e n tc l o s e di t e m s e t s o v e rd a t as t r e a m s l a is h e n g b e ( j i a n g x ia g r i c u l t u r a lu n i v e r s i t y ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g 1 n c o m p u t e ra p p l i c a t i o nt e c h n o l o g y i nt h e g r a d u a t es c h o o l o f l a n z h o uu n i v e r s i t yo f t e c h n o l o g y s u p e r v i s o r a s s o c i a t ep r o f e s s o rw a n gy a n m a y ，2 0 1 1 i 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：桢跳 日期：弦，1 年占月占日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权兰州理工大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同 时授权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据 库，并通过网络向社会公众提供信息服务。 作者签名：颓醚 导师签名：立五 日期：- 1 年舌月8 日 b 觏：劲i | 辱6 旯罗e l 硕【j 学位论文 目录 摘宴耍i a b s t r a c t i i 插图索引w 附表索引v 第1 章绪论1 1 1 研究背景及意义l 1 2 国内外研究现状2 1 3 本文所做的工作。3 1 4 论文组织结构。4 第2 章数据流挖掘综述5 2 1 数据流。5 2 1 1 数据流特点。5 2 1 2 数据流处理模型6 2 2 数据流处理技术。7 2 2 1 概要数据结构7 2 2 2 聚集。7 2 2 3 抽样一7 2 2 4 降载8 2 2 5 近似计算8 2 3 数据流挖掘8 2 3 1 数据流挖掘的特点8 2 3 2 数据流挖掘模型9 2 3 3 数据流挖掘方法1 0 2 4 本章小结1 2 第3 章数据流频繁项集挖掘的研究1 4 3 1 问题描述1 4 3 2 数据流频繁项集挖掘的关键问题15 3 2 1 数据处理模型1 5 3 2 2 压缩数据存储结构1 5 3 2 3 概念漂移16 3 2 4 项集计算1 6 3 2 5 数据预处理1 7 3 2 6 实时查询1 7 3 3 数据流频繁项集挖掘算法1 8 3 3 1l o s s yc o u n t i n g 算法18 3 3 2f p s t r e a m 算法18 3 4 本章小结2 2 第4 章数据流频繁闭项集挖掘2 3 4 1 相关定义2 3 4 2m c f i d s 算法2 4 4 2 1m c f i d s 算法的窗口处理模型2 4 4 2 2m c f l d s t r e e 结构2 5 4 2 3m c f i d s t r e e 的生成2 6 4 2 4m c f i d s t r e e 的增量更新。2 9 数据流频繁闭项集挖掘箅法研究 曼曼曼曼曼皇曼曼曼曼曼曼曼曼曼皇曼曼ii i ii 曼曼皇曼皇曼皇曼曼曼量曼曼皇曼曼! 皇曼曼! 量曼曼曼曼曼曼皇曼曼曼曼曼曼鼍曼曼曼量曼曼量笪量曼曼詈曼曼曼! 曼曼曼曼曼曼量曼曼 4 2 5 频繁闭项集的输出3 1 4 3 实验分析3 2 4 4 本章小结3 4 第5 章总结与展望一3 6 5 1 本文总结3 6 5 2 今后工作展望3 7 参考文献3 8 致谢z l ：! 附录a 攻读硕士学位期间发表的学术论文目录4 3 i i 硕卜学位论文 摘要 数据流的出现给传统的数据挖掘技术带来了巨大的挑战。由于数据流连续不 断的到来，已有的数据处理技术难以对这些潜在无限的、变化的数据进行有效的 管理和挖掘。随着移动终端设备的广泛应用，数据流应用领域不断增多，因此， 必须对数据流环境下的数据处理技术进行研究。目前，数据流挖掘技术引起了国 内外学者的广泛关注，成为当前的一个研究热点。 频繁项集挖掘是数据流挖掘的主要研究内容，被广泛应用于关联规则发现、 冰山查询、分类和聚类等问题。针对传统的方法大多关注于在数据流中挖掘全部 频繁项集，存在数据和模式冗余问题，近年来人们开始关注在数据流中挖掘频繁 闭项集。 本文在对数据流挖掘领域若干问题进行探讨的同时，主要研究了数据流中频 繁闭项集的挖掘问题，提出了新的算法并结合实验结果做了必要的分析。概括地 说，本文主要涉及到如下几方面内容： 1 与传统的关系型数据库相比，分析了数据流的特点。按照算法处理数据 流时所采用的不同时序范围对数据流处理模型进行了介绍，并对目前常用的数据 流处理技术进行归纳总结。 2 对数据流挖掘算法的特点及其模型进行了分析和总结，对当前数据流挖 掘算法作了介绍。对数据流频繁项集挖掘的经典算法作了详细的分析，了解数据 流挖掘过程中的存储结构和存储方法，以及概要数据结构的生成、维护和实时查 询结果等方面的内容。 3 频繁闭项集不仅包含了频繁项集的全部信息，而且在数量上远小于频繁 项集，在实际应用中更容易被人们理解。本文研究了数据流环境下的频繁闭项集 挖掘问题，提出了一种新的基于滑动窗口处理模型的频繁闭项集挖掘算法，来挖 掘最近一段时间内用户感兴趣的信息。并将它们存储到一种新的数据结构中，随 着滑动窗口的不断滑动以基本窗口为更新单位实时更新和维护该结构，利用该结 构可以快速地挖掘出滑动窗口中所有频繁闭项集。 关键词：数据流；数据流挖掘；频繁项集；频繁闭项集；滑动窗口；基本窗口 数据流频繁闭项集挖掘算法研究 a bs t r a c t t h ee m e r g e n c eo ft h ed a t as t r e a mb r i n g st r e m e n d o u sc h a l l e n g e st ot h et r a d i t i o n a l t e c h n o l o g yi nd a t am i n i n g b e c a u s et h ed a t as t r e a mi sa r r i v i n gc o n t i n u o u s l y , t om a n a g ea n d e m i n et h e s ep o t e n t i a l l yu n l i m i t e da n dd y n a m i cd a t as t r e a mi sd i f f i c u l tf o re x i s t i n gd a t a p r o c e s s i n gt e c h n i q u e s w i t ht h ew i d ea p p l i c a t i o no fm o b i l et e r m i n a le q u i p m e n t ，t h ed a t a s t r e a ma p p l i c a t i o n sc o n t i n u et o i n c r e a s e t h e r e f o r e ，p e o p l em u s tm a k eas t u d yo fm i n i n g s k i l l ss u i t a b l ef o rt h ee n v i r o n m e n to fd a t as t r e a m i th a sa t t r a c t e de x t e n s i v ea r e n t i o nf r o m s c h o l a r sa th o m ea n da b r o a d ，a n dh a sb e c o m ear e s e a r c hh o t s p o t i nt h ef i e l do fr e s e a r c ho nd a t as t r e a mm i n i n ga l g o r i t h m ，f r e q u e n ti t e m s e t sm i n i n gi sa n i m p o r t a n tr e s e a r c hc o n t e n t i ti sw i d e l yu s e di na s s o c i a t i o nr u l e s ，i c e b e r gq u e r y , c l a s s i f i c a t i o n s a n dc l u s t e r i n g t h em o s to ft h et r a d i t i o n a lm e t h o d sf o c u so nm i n i n ga l lo ff r e q u e n ti t e m s e t s o v e rd a t as t r e a m st oe x i s td a t aa n dm o d e lr e d u n d a n c y t h ef r e q u e n tc l o s e di t e m s e t sp r e s e r v e c o m p l e t e l yi n f o r m a t i o no fa l lf r e q u e n ti t e m s e t sa n dt h es c a l ei sm u c hs m a l l e rt h a nt h e f r e q u e n ti t e m s e t s t h e r e f o r e ，i nr e c e n ty e a r s ，p e o p l es t a r t st of o c u so nm i n i n gf r e q u e n tc l o s e d i t e m s e t so v e rd a t as t r e a m s i nt h i st h e s i s ，w ee x p l o r es e r i a lk e yi s s u e so v e rd a t as t r e a mm i n i n g w ep r i m a r i l y r e s e a r c ht h ep r o b l e mo fm i n i n gt h ef r e q u e n tc l o s e di t e m s e t so v e rd a t as t r e a m m e a n w h i l ew e p r o p o s e d an e wa l g o r i t h ma n dm a d et h e n e c e s s a r ya n a l y s i sw i t ht h ec o r r e s p o n d i n g e x p e r i m e n t a lr e s u l t s i ns u m m a r y , t h i sa r t i c l em a i n l yr e l a t e dt ot h ef o l l o w i n ga s p e c t s ： 1 c o m p a r e dt ot r a d i t i o n a lr e l a t i o n a ld a t a b a s e ，w ea n a l y z et h ec h a r a c t e r i s t i c so fd a t a s t r e a m s ，a n dt h e ni n t r o d u c es e v e r a ld a t as t r e a m sp r o c e s s i n gm o d e l ，a n dt h ec o m m o n l yu s e d d a t as t r e a mp r o c e s s i n gt e c h n o l o g ya r es u m m a r i z e d 2 w ea n a l y z e da n ds u m m a r i z e dt h ec h a r a c t e r i s t i c so fd a t as t r e a mm i n i n ga l g o r i t h m s a n dm o d e l s a n dw ei n t r o d u c e dt h ec u r r e n td a t as t r e a mm i n i n ga l g o r i t m n s w ea n a l y z e ds o m e c l a s s i c a lf 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 so v e rd a t as t r e a m ，a n dt h e nu n d e r s t a n do u r s e l v e s w i t hf o l l o w i n ga s p e c t si n v o l v e di nt h ed a t as t r e a mm i n i n gp r o c e d u r e ，s u c ha st h es t o r a g e s t r u c t u r e sa n ds t o r a g em e t h o d s ，a n ds u m m a r yd a t as t r u c t u r eg e n e r a t i o n ，m a i n t e n a n c ea n d r e a l t i m es e a r c hr e s u l t sa n ds oo n 3 f r e q u e n tc l o s e di t e m s e t sc o n t a i n sc o m p l e t ei n f o r m a t i o na b o u ta l lf r e q u e n ti t e m s e t s ，t h a t i s ，t h en u m b e ri ss m a l l e rt h a nf r e q u e n ti t e m s e t s t h i sp a p e rs t u d i e st h ep r o b l e mo ff r e q u e n t c l o s e di t e m s e t sm i n i n go v e rd a t as t r e a m s t h e nw ep r o p o s ea na l g o r i t h mo ff r e q u e n tc l o s e d i t e m s e t s m i n i n gb a s e do ns l i d i n gw i n d o wp r o c e s s i n gm o d e lt o m i n et h em o s tr e c e n t i n f o r m a t i o no fi n t e r e s tt ot h eu s e r , a n ds t o r et h e mt oan e wc o m p r e s ss t o r a g es t r u c t u r e ，w h i c h u 硕十学位论文 c a nn o to n l yg e tai n c r e m e n t a lu p d a t ea n dm a i n t a i nt h et h i ss t r u c t u r e ，b u ta l s oh a v eaf a s t m i n i n go fa l lf r e q u e n tc l o s e di t e m s e t so v e rt h es l i d i n gw i n d o w t h ee x p e r i m e n t a lr e s u l ts h o w s t h a t t h i sa l g o r i t h mi se f f e c t i v e k e y w o r d s ：d a t as t r e a m s ；d a t as t r e a mm i n i n g ；f r e q u e n ti t e m s e t s ；f r e q u e n tc l o s e d i t e m s e t s ；s l i d i n gw i n d o w ；b a s i cw i n d o w i i i 数据流频繁闭项集挖掘算法研究 插图索引 图2 i 数据流频繁模式处理模型：1 0 图3 1f p t r e e 结构：16 图3 2 自然倾斜时间窗框架1 9 图3 3 对数倾斜时间窗框架1 9 图3 4 频繁模式树结构2 0 图3 5 嵌入倾斜时间窗口的频繁模式树2 1 图4 1 滑动窗口模型2 5 图4 2m c f i d s t r e e 结构2 6 图4 3 数据集t 1 0 1 4 d 1 0 0 0 k 的运行时间3 3 图4 4m c f i d s 算法的内存消耗3 3 图4 5s = 0 0 0 15 时的运行时间比较3 4 图4 6s = 0 0 0 1 5 时的内存消耗比较3 4 i v 硕f ：学位论文 附表索引 表3 1 频繁项集2 0 表4 1 临界频繁1 项集排序表f - l i s t 2 7 表4 2 频繁闭项集输出表3 l v ， 硕士学位论文 1 i 研究背景及意义 第1 章绪论 随着全球信息化的发展，信息量按指数增长，出现了大量的以数据流为承载 形式的信息，如电信领域中的通话记录数据流、环境监测中的数据包流、股票市 场的交易数据流、w e b 用户点击数据流以及零售业务中的购物数据流等。在这些 数据流中蕴含着大量的知识和有用的信息，人们迫切需要获取这些知识和信息， 因此，数据流的挖掘和分析日益成为一个研究热点。 数据流是一种无限的、连续的、高速到达的、动态变化的有序序列，这些特 性使得对数据流的挖掘变得异常困难。由于计算机的存储空间是有限的，不可能 把数据流中的数据全部存储到计算机中，然后再进行处理，并且对于快速到达的 数据流还要满足用户实时查询的要求。传统的对静态数据集的挖掘算法在空间复 杂度和时间复杂度方面都不能满足数据流环境下挖掘算法的要求。数据流挖掘的 相关算法必须是时间和空间都是高效的，而且算法对数据只能进行单遍扫描和顺 序访问。目前，数据流挖掘的方法主要包括数据流上的分类【1 4 】、聚类【 l 、频繁 项集挖掘【8 1 和时序分析1 9 - l o 】等。 挖掘数据流中的频繁项集是数据流挖掘的重要研究内容，在许多应用领域都 有着非常重要的意义，通常用于进一步产生关联规则，或直接作为决策支持的辅 助信息。例如在网络监控中，频繁项集可能意味着网络堵塞，而这也可能就是网 络受到攻击的征兆；频繁项集应用最典型的例子是购物篮分析，通过了解哪些商 品频繁地被顾客同时购买，可以帮助零售商制订营销策略以及货物上架等。随着 办公自动化进程的加快，现在几乎所有的公司都采用计算机来记录他们的数据， 随着公司规模的扩大这些数据也在以惊人的速度剧增，如何快速的从这些数据中 得到实时的查询结果，依靠传统的处理方法是不可能实现的，必须用适合于数据 流特点的挖掘方法来解决。 由于频繁项集的子集也是频繁项集，挖掘频繁项集的一个不足之处在于可能 产生组合爆炸问题，严重影响算法的时间和空间效率。此外，对于数量众多的频 繁项集用户也难以理解和利用。频繁闭项集作为频繁项集的一个子集，不仅保存 了频繁项集的完整信息，并且其规模远小于频繁项集。因此在数据流中挖掘频繁 闭项集，不仅可以节约大量的内存空间，而且也可以提高挖掘效率，尤其对于存 在大量强模式、长模式和要求阈值较低的应用，可以考虑挖掘频繁闭项集。因此， 对于数据流频繁闭项集挖掘算法的研究具有重要的意义。 数据流频繁闭项集挖掘算法研究 1 2 国内外研究现状 由于众多应用领域的需求，数据流处理问题，特别是对数据流挖掘问题的研 究受到了广泛的关注。1 9 9 8 年，h e n z i n g e r 等在文【1 l 】中，首次提出了数据流模型 的概念，此后数据流作为一种新的数据形式，得到了广泛的应用。从2 0 0 0 年开 始，在v l d b 、s i g m o d 、s i g k d d 、i c d e 、i c d m 等有关数据挖掘与数据库领 域的世界顶级学术会议中，每年都有多篇与数据流处理相关的论文发表。近年来， 随着网络和通信技术的迅猛发展，移动终端设备的广泛使用，数据流应用的新领 域不断涌现，国内外许多著名的大学和研究机构都对数据流方面的问题开展了深 入的研究，并提出了一系列的方法、技术及理论。 当前对数据流的相关研究主要侧重于三个方面【1 2 】：一是对数据流管理系统 的研究和开发，二是开发能够提供多种挖掘功能的数据流挖掘系统，三是设计适 合于数据流环境下的挖掘算法。在线实时查询是数据流管理系统的主要研究内 容，这方面的研究已引起了许多研究机构和研究人员的关注，并且已经开发出了 一些相当成熟的数据流管理系统，如斯坦福大学开发的s t r e a m 系统【l3 ，加州 大学伯克利分校开发的t e l e g r a p h 系统【1 4 】，此外还有麻省理工学院与布朗大学合 作研发的a u r o r a 系统【1 5 】等。对数据流挖掘算法的研究主要侧重于数据的在线分 析，为决策提供依据，主要包括聚类分析、分类与预测、频繁项集挖掘等。目前 已有许多研究机构和软件公司推出了适合于数据流环境下的挖掘系统。其中，一 个典型的代表就是u i u c 开发的m a i d s t l 6 】挖掘系统，它是一个具有聚类、分类、 频繁项集挖掘功能，并且能够提供实时查询以及结果可视化的数据流挖掘系统。 i b m 公司开发的数据挖掘产品i n t e l l i g e n tm i n e r ，它提供了很多数据挖掘算法，如 关联、分类、回归、预测模型、偏离检测、序列模式分析和预测。它也提供了一 个应用工具集，包括神经网络算法、统计方法、数据准备模型和数据可视化工具， i n t e l l i g e n tm i n e r 的主要特点是数据挖掘算法可伸缩。此外，还有s a s 公司开发的 e n t e r p r i s em i n e r ，它提供了多种数据挖掘功能，包括回归，分类和统计分析。s g i 公司开发的m i n e s e t ，它也是多功能挖掘系统，具有关联和分类，高级统计和可 视化工具，其最主要的特点是具有强大的图形工具，包括：规则可视化工具，树 可视化工具，地图可视化工具和多维数据分散可视化工具，它们用于实现数据和 数据挖掘结果的可视化功能。 对数据流挖掘算法的研究，主要集中在分类、聚类和频繁项集上。对数据流 环境下的频繁项集挖掘算法，国外许多学者进行了深入的研究并提出了自己的解 决方法。如m a n k u 等提出了两个具有代表性的数据流频繁项集挖掘算法s t i c k y s a m p l i n g 算法和l o s s yc o u n t i n g 算法【1 7 】。利用c o u n ts k e t c h 概要数据结构，m o s e s c h a r i k a r a 等提了出一种新的数据流频繁项集挖掘算法【i 引，该方法只需利用有限 2 硕卜掌位论文 的存储空间通过单遍扫描数据流，就能得到误差可控的近似结果。在文 1 9 】中， g r a h a mc o r m o d e 等利用了一种新的数据结构c o u n t m i ns k e t c h 来存储数据流中 的数据，借助于该结构可以快速的进行数据流查询，而不需要扫描整个数据流， 提高了算法的效率。在许多应用领域，人们对不同历史时间的数据查询粒度不同， 在文 2 0 中，c h r i sg i a n n e l l a 等根据数据流这一应用特征提出了f p s t r e a m 算法， 该方法利用倾斜时间窗口技术以较细的时间粒度保存数据流中最近的频繁项集 信息，而以粗糙的时间粒度保存历史数据中的频繁项集，f p s t r e a m 算法能够挖 掘数据流环境下多个时间粒度的频繁项集，满足人们对不同历史数据的查询要 求。在文【2 l 】中，c h a n g 等提出了e s t d e c 算法，该方法采用时间衰减机制逐步减少 历史模式的支持度计数来区分最近事务中的频繁项集和历史事务中的频繁项集， e s t d e c 算法能够挖掘数据流上最近的频繁项集。另外一些研究人员提出了许多改 进的算法，并对数据流中频繁项集挖掘的关键技术和理论进行了总结和探讨。 对数据流挖掘算法的研究工作，与国外相比国内起步较晚，但目前许多研究 人员已经取得了一定的成果，并提出了许多有效的数据流频繁项集挖掘算法或在 现有算法的基础上进行了改进。 在文【2 2 】中，复旦大学的周傲英教授等提出了0 一万算法，该算法能够快速有 效的挖掘出数据流中的频繁项集，并且该算法能够将内存消耗控制在很小的范围 内。在文【2 3 中，东北大学的张昕等在f p s t r e a m 算法的基础上进行了改进，并提 出了一种新的数据流频繁项集挖掘算法，f p i l s t r e a m 算法，该算法是一种启发 式算法，并利用倾斜时间窗口技术来压缩存储历史数据，f p i l s t r e a m 算法能够 满足数据流频繁项集挖掘的低时间复杂度的要求，并且能够提供了较细粒度的实 时查询结果。在文 2 4 】中，东南大学的刘学军等提出了f p d s 算法，该算法是在 f p - g r o w t h 算法的基础上进行了改进，并采取了分段的思想策略，将数据流进行 了分段，采用逐段挖掘数据流中的频繁项集的方法，f p d s 算法能够快速有效的 挖掘出数据流中的所有频繁项集。在此基础上，同样利用分段的思想，在文【2 5 】 中，他们还提出了d s c f i 算法，该算法是基于滑动窗口处理模型的数据流频繁 闭合项集挖掘算法。在文 2 6 】中，华中科技大学的李国徽教授等提出了m s w 算法， 该算法也采用滑动窗口处理模型，m s w 算法能够在数据流环境下，挖掘任意滑 动窗口内的频繁项集。在文 2 7 】中，浙江大学的潘云鹤教授等对数据流中的频繁 项集挖掘进行了深入的分析，并对其特点进行了归纳和总结，对现有的数据流频 繁项集挖掘算法进行了全面的总结和分类，并对在数据流环境下的频繁项集挖掘 算法中存在的主要问题进行了讨论，提出了相关的研究方向。 1 3 本文所做的工作 本文首先对数据流频繁项集挖掘的研究意义及背景进行了介绍，并对研究现 3 数据流频繁闭项集挖掘募法研究 状进行了简述。然后对数据流挖掘进行综述，分析和归纳了数据流的特点，并介 绍了数据流处理模型，对模型的组成以及各个组件功能进行了详细的说明。对数 据流处理过程中的一些常用技术进行了归纳总结。在了解数据流挖掘的特点和挖 掘模型的基础上，介绍了当前数据流环境下相关的挖掘方法。然后对数据流频繁 项集挖掘进行了详细的分析和研究，通过以上的工作，熟悉和理解数据流频繁项 集挖掘算法所涉及的处理策略、概要数据结构、挖掘步骤以及实时查询和结果输 出等方面的内容。另外，由于频繁闭项集不仅保存了频繁项集的完整信息，而且 在规模上比频繁项集小得多，在实际应用中往往更容易被用户理解和使用。在现 有研究成果基础上，本文提出了一种新的数据流频繁闭项集挖掘算法：m c f i d s 算法。 1 4 论文组织结构 本文共分五章，各章的主要内容如下： 第一章，绪论。主要介绍了本课题的研究背景及意义，对国内外在数据流处 理技术及数据流挖掘方面的研究成果和发展方向进行了介绍，明确了本文研究的 具体目标和任务。 第二章，数据流挖掘综述。在此章中，首先介绍了数据流的概念以及特点， 并根据数据处理所采用的不同时序范围对处理模型进行划分，对数据流处理的常 用技术进行了归纳总结，以及介绍了数据流挖掘的一些相关概念和特点，并对了 数据流环境下的挖据算法进行了介绍。 第三章，数据流频繁项集挖掘的研究。在本章中，首先对数据流频繁项集挖 掘问题进行了描述，归纳总结了一些数据流频繁项集挖掘的关键问题，然后对当 前一些经典的数据流频繁项集挖掘算法进行了详细的介绍和分析 第四章，数据流频繁闭项集挖掘算法。在此章中，根据现有数据流频繁项 集挖掘算法中的不足，提出了一种新的数据流频繁闭项集挖掘算法m c f i d s 算 法。通过实验分析，该算法具有较好的时间和空间效率。 第五章，总结和展望。在本章中，对本文的内容进行总结，并对今后的研究 工作进行展望。 4 硕l j 学位论文 第2 章数据流挖掘综述 数据挖掘就是从大量数据中提取或发现有用的知识的过程。数据挖掘就是从 大量的、不完全的、有噪声的、模糊的、随机的数据集中，提取隐含在其中的、 人们事先不知道的、但又是潜在有用的信息和知识的过程。数据挖掘涉及多学科 技术的集成，主要包括数据库技术、统计、机器学习、高性能计算、模式识别、 神经网络、数据可视化、信息提取、图像与信号处理和空间数据分析等。数据挖 掘通过发现人们感兴趣的知识和模式，使数据拥有者更容易理解和使用规模庞大 的原始数据。 随着移动终端设备的广泛使用，出现了一种新的海量、动态和高速的数据。 这种连续到达、潜在无限、随时间不断变化、严格有序的数据模型称之为数据流。 与传统的关系型数据库相比，有其独特的特点，这对数据流环境下进行的数据挖 掘算法提出了新的要求，这些要求是传统的数据挖掘方法所不能满足的。为了从 数据流中快速的挖掘出入们感兴趣的知识和信息，必须开发适合数据流特点的、 高效的数据处理方法。 2 1 数据流 在我们的现实生活中，数据流的应用非常广泛，如证券市场的有价证券价格 信息，温度实时监测数据，电信通话记录等。数据流是连续的、高速的、无限的、 不断变化的有序序列。令f 表示任一时刻，在t 时刻到达的数据项记为a ，则数 据流d s 可以表示成d s = 扛。，口：，a ，a ， 。数据流中的数据项是严格有序的， 并且是相互独立的，因此数据流中的数据项只能按时间t 的递增顺序到达。数据 流中的数据规模巨大，将数据流完整地存储到内存中是不可能实现的。 2 1 1 数据流特点 数据流中的数据是高速到达的，并且数据量是潜在无限的，通过对比传统的关系型 数据，数据流具有以下几个特点： 1 、数据实时连续产生：数据流中的数据连续不断的到来，与传统数据库中保存的 静态数据不同，数据流处理系统中处理的数据主要是从外部数据源获取，并且数据不是 一次性提供，而是随时间不断地到达。 2 、数据高速到达：数据流是在实际的应用环境中连续生成的，并高速流入处理系 统。但是数据流的到达速度并不是固定不变的，是随着实际应用中生成数据流的速度而 变化的。 3 、数据规模宏大：数据流中的数据是大量的甚至是无限的。传统形式的数据量也 5 数据流频繁闭项集挖掘算泫研冗 可以是非常巨大的，但大小是可知的；而数据流形式的数据在量大的同时，还强调了这 些数据的到来可能是无穷的，即在数据流全部到来之前，无法判断最终数据量的大小。 4 、数据不断变化：数据流中的数据随时间不断的变化，采用预测方法也不能准确 地预测下一时刻将到来的数据。 5 、数据严格有序且相互独立：数据流中的数据随时间连续不断的生成，并以数据 的生成顺序连续到达，系统无法控制数据的到达顺序只能依次处理。 由于数据流具有上述特点，数据流中的海量数据无法完整的存储在计算机有限的存 储空间中，并且不可能对这些数据进行多次扫描。因此数据流中的大部分数据在处理后 被丢弃，除非特意保存，否则不能被再次读取，或者再次读取的代价昂贵。所以对数据 流中的数据处理是不完整的，只能得出满足允许误差范围内的近似结果，而在传统的静 态数据集上的查询，由于系统可以多次扫描数据则可以得到精确的结果。 2 1 2 数据流处理模型 数据流在现实世界中有着广泛的应用，对于不同的数据流应用领域，关注的时间范 围不同，处理数据的方式也不相同。由于数据流中的数据项是严格有序且相互独立，研 究者根据不同的应用领域，在处理数据流时采用的时序范围来划分数据流处理模型。 1 、快照窗口处理模型：数据流中的数据是连续到达的，在计算机内存中，开辟一 个存储空间，存储给定的两个时间戳间的数据，所有的数据处理操作都限定在这个数据 范围之内。快照窗口处理模型解决了数据流中数据规模巨大，处理系统无法对整个数据 流进行全局处理的问题。但是快照窗口处理模型也有自身的缺陷，由于数据流是随时间 不断变化的，数据流的特征也并不是一层不变的，快照窗口处理模型无法实时反映数据 流的当前特征。 2 、界标窗口处理模型：在计算机内存中，开辟一个存储空间，存储从某个己知的 初始时间点到当前时间点为止的数据，数据处理操作也只限定在这个范围之内。 界标窗口处理模型能够实时反映数据流的特征，但是随着数据流的连续快速到 来，窗口中需要存储和维护的数据也在不断的增多，严重影响算法的时间效率和 空间效率。 3 、滑动窗口处理模型：在计算机内存中，开辟一个存储空间，存储长度固定的最 近一段时间范围内的数据，只对这个时间范围内的数据进行处理操作。滑动窗口处 理模型的时间终点永远为当前时刻。在许多数据流的应用领域，人们只对最近一 段时间内的数据感兴趣，滑动窗口处理模型能够满足人们的这一要求，因此被广 泛的应用于数据流挖掘。滑动窗口处理模型可以分为两类：一类是以时间区间来 定义的，窗口中的数据是最近一段时间范围内到达的。因此，滑动窗口处理模型 中的数据量是可变化的，不变的只是滑动窗口的时间长度。二类是以数据量来定 义的，即滑动窗口处理模型中的数据量是固定的。 6 硕f j 学位论文 在这3 种窗口处理模型中，由于快照窗口处理模型只能处理两个给定的时 间范围内的数据，不能实时反映数据流的特征，因此在现实应用领域，很少采用 快照窗口处理模型。界标窗口处理模型克服了上述缺点，能反映数据流的全局特 征，但是界标窗口处理模型通常将数据流的起始点作为数据处理的初始时间点， 随着数据的连续快速到达，需要在计算机内存中维护的数据量也越来越大，算法 需要对所有数据进行处理，严重影响算法的时空效率。现有的数据流挖掘算法， 大多数采用滑动窗口处理模型，在滑动窗口处理模型中，随着数据流不断到来窗 口向前滑动，将过时的数据滑出窗口，并将新到来的数据滑入窗口，窗口中存在 数据的插入和删除两种操作。滑动窗口处理模型非常适合用于只要求对最近一段 时间内的数据进行处理的应用，并且能实时反映数据流的特征，因此在现实应用 领域得到了广泛的应用。 2 2 数据流处理技术 由于数据流的特点，传统的数据处理技术很难解决数据流挖掘过程中所面临的一系 列问题和挑战。对此，研究人员提出了许多适合于数据流处理的技术。这些技术可以归 纳如下。 2 2 1 概要数据结构 概要数据结构是按照某种给定的近似原则有选择地在数据流中抽取数据，来近似替 代数据流的处理方法。概要数据结构中存储了数据流的概要信息，是对数据流的一种压 缩。利用概要数据结构能够有效的减少挖掘算法处理数据的规模，不需要扫描整个数据 流，用户就可以进行实时查询并且能够得到查询结果。由于概要数据结构是对数据流的 一种概要提取，不能代表数据流的所有特征，所以使用概要数据结构进行数据流挖掘得 到的结果是近似的。概要数据结构的创建借助于总结技术的应用，总结技术总结到来的 数据流以供将来的分析使用。研究人员进行了深入研究，提出了很多方法来构造该 要数据结构，如采样技术【2 8 ，2 9 1 、小波变换【3 0 32 1 、直方图技术3 3 - 3 5 1 、哈希方法【3 6 ， 3 7 1 、梗概技术【3 8 。3 9 1 和字典树结构等各种高效的树型存储结构。 2 2 2 聚集 聚集是一个计算统计过程的方法。例如利用平均值( m e a n s ) 和方差( v a r i a n c e ) 来总结 到来的数据流。挖掘算法通过使用这些聚集的数据来进行挖掘。聚集所产生的一个问题 是，它不能很好的代表数据分布快速变化的数据流。数据流上的聚集查询要解决资源共 享问题，力求只需进行少量更新和比较就可求得每个新的值。 2 2 3 抽样 抽样是一种常用的统计技术。常用的抽样方法有：随机抽样、分层抽样和系统抽样。 7 数据流频繁闭项集挖掘算法珂f 究 随机抽样就是从个含有n 个个体的总体中，不放回地抽取n 个个体作为样 本来概括总体分布的方法( n n ，每个个体被抽到的概率相等均为n n ) 。分 层抽样就是在抽样时，将总体分成互不交叉的层，然后按照一定的比例，从 各层中独立地抽取一定数量的个体，将各层取出的个体合在一起作为样本。系统 抽样就是当总体中的个体数较多时，采用简单随机抽样显得较为费事。这时，可 将总体平均分成的几个部分，然后按照预先给定的规则，从每一部分抽