（管理科学与工程专业论文）数据流闭频繁模式挖掘算法研究.pdf

合肥工业大学 i i ii ii ii iii l li iii iiil y 18 8 7110 本论文经答辩委员会全体委员审查，确认符合合肥工业大学硕士 学位论文质量要求。 答辩委员会签名 揣弘1 韬线知豸绯1 委员： 彳堋乞向阳y 妇秀 苏拯 鼽饥蛳吾副椰 刷玑气伽1 苏双j 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得 金起王些盔堂 或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签字：孰 签字日期：f f 年犀月2 2 日 学位论文版权使用授权书 本学位论文作者完全了解金胆王些太堂有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权金胆王些太 堂可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名：蒌落 撇名：( 锄 导师签名：iv ol 签字日期：) p 1 1 年4 月l z 日签字日期：l 年叩月y 咽 学位论文作者毕业后去向： 工作单位： 通讯地址： i i 电话： 邮编： 数据流闭频繁模式挖掘算法研究 摘要 由于数据流的流动性、无限增长的特点，传统的数据管理技术已经无法有 效的管理数据流中的数据，因此，有必要对数据流管理中的一些新技术做些研 究。整个数据库界已经开始关注数据流管理技术。 自动控制、计算机、图形图像、网络等多个领域的知识都涉及到系统仿真 技术。数据挖掘技术可以获取仿真数据中隐藏的知识。仿真系统复杂程度越高 和规模越大，仿真时间会越长，需要的空间也越大。可见，仿真数据具有数据 流的特征，可以用数据流挖掘技术处理仿真数据。关联规则是仿真系统常选择 的一类挖掘任务。研究生阶段，本人主要研究了频繁模式在数据流中的应用。 其中，重点研究如何在数据流上挖掘闭频繁集。 本文提出了一种挖掘数据流时间窗口中闭频繁项集的方法n e w t m o m e n t 。 在单遍扫描数据流各事务的情况下，该方法能完整地记录模式信息。同时， n e w t - m o m e n t 提出的减枝方法能很好地降低滑动窗口树f t r e e 的空间复杂度与 闭频繁模式树n e w t - t r e e 的维护代价。此外，该方法提出的时间衰减机制能区 分历史和最新模式对挖掘结果的影响。另外，n e w t - t r e e 直接存储闭频繁项集， 可随时快速读取闭频繁项集。和t - m o m e n t 算法相比，算法不需要删除历史数 据，不需要记录事务时标，不需要标记各节点，在一定程度上，可降低算法的 时间和空间复杂度。大量实验结果表明，n e w t - m o m e n t 有很好的效率和准确性。 关键词：系统仿真；数据流：频繁闭项集；时间窗体；衰减模式 i i i r e s e a r c ho na l g o r i t h m sf o rm i n i n gc l o s e df r e q u e n t p a t t e r n si nd a t as t r e a m s a b s t r a c t s i n c et h ec h a r a c t e r i s t i c so ft h ed a t as t r e a mf l o wi su n l i m i t e dg r o w i n g ，t h e t r a d i t i o n a ld a t am a n a g e m e n tt e c h n o l o g yh a sb e e nu n a b l et om a n a g ed a t ai na ne f f e c t i v e w a y t h e r e f o r e ，p e o p l e m u s t r e s e a r c hn e w t e c h n o l o g yf o r t h e m a n a g e m e n t o f d a t as t r e a m d a t as t r e a mm a n a g e m e n tt e c h n o l o g yh a sb e e nw i d e s p r e a dc o n c e r n i n gi nt h e d a t a b a s ew o r l d a u t o m a t i cc o n t r o lt e c h n o l o g y ，c o m p u t e rt e c h n o l o g y , g r a p h i c sa n dv i d e op r o c e s s i n g ， n e t w o r kt e c h n o l o g y , t e c h n o l o g y , i n f o r m a t i o np r o c e s s i n gt e c h n o l o g y , a n do t h e rf i e l d so f k n o w l e d g ea r ei n t e g r a t e di ns y s t e ms i m u l a t i o na n dt e c h n o l o g yw h i c hi sa ni m p o r t a n t m e a n ss y s t e m sa n a l y s i sa n dr e s e a r c h d a t am i n i n gt e c h n o l o g yi sh i d d e ni nt h es i m u l a t i o n d a t at oo b t a i nk n o w l e d g e w i t ht h ec o m p l e x i t yi n c r e a s e da n dt h es c a l ei n c r e a s e d ，m o r ea n d m o r et i m eo fs i m u l a t i o na n ds i m u l a t i o nb yi n c r e a s i n gt h ea m o u n to fd a t ag e n e r a t e d t h i s m a k e st h es i m u l a t i o nd a t ah a st h ec h a r a c t e r i s t i c so fd a t as t r e a m a i mt ot h es i m u l a t i o n o fd a t am i n i n gt a s k s ，t i m ea n ds p a c ee f f i c i e n c yi nm i n i n gd a t as t r e a m si sv e r yi m p o r t a n tt o t h ec o r r e s p o n d i n ge f f i c i e n ta l g o r i t h m s i m u l a t i o no fa s s o c i a t i o nr u l em i n i n gi so n eo ft h e m o s tc o m m o n l yu s e di nd a t am i n i n gt a s k s a tt h eg r a d u a t es c h o o ll e v e l ，is t u d yt h ef r e q u e n t p a t t e r n si nd a t as t r e a mm i n i n ga l g o r i t h m s ，w h i c hf o c u so nc l o s e df i e q u e n ti t e r n s e t s i nt h ep a p e r , n e w t - m o m e n th a sb e e nr e s e a r c h e do nm i n i n gc l o s e df 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 s t h ep a t t e r no fd a t as t r e a mc a nb ec o m p l e t e l yr e c o r d e db ys c a n n i n gt h e s t r e a mo n l yo n c e i tl e a d st oas l u m pi np e r f o r m a n c eb e c a u s eo fn o tt h i n k i n go v e rm o d e d e c a y i n ga st i m ep a s s e da n da d o p t i n gas t r u c t u r et om a r kt h et y p e so fc l o s e df r e q u e n t i t e r n s e t s t h ea r t i c l ep r o p o s e sam e t h o df o rm i n i n gt h ec l o s e df r e q u e n tp a t t e r n si nt h et i m e w i n d o wo fd a t as t r e a m a n dt h ep r u n i n gm e t h o do fn e w t - m o m e n tc a nr e d u c et h es p a c e c o m p l e x i t yo fs l i d i n gw i n d o wt r e ea n dt h em a i n t e n a n c ec o s to f t h ec l o s e df r e q u e n tp a t t e r n s t r e e t od i f f e r e n t i a t et h eh i s t o r i c a la n dt h el a t e s tp a t t e r n s ，at i m ed e c a y i n gm o d e li sa p p l i e d a d d i t i o n a l l y , n e w t - t r e es t o r e st h ec l o s e df r e q u e n ti t e m s e t sd i r e c t l y ，s om e yc a nb e q u i c k l yr e a d i nc o n t r a s t 丽mt - m o m e n t ，n e w t m o m e n tn o tn e e d st od e l e t et h eh i s t o r i c a l d a t a , t om a r kt r a n s a c t i o n ，t om a r kn o d e s ，w h i c hw i l ld e c r e a s et h et i m ec o m p l e x i t ya n dt h e s p a c ec o m p l e x i t y t h er e s u l t ss h o wt h ea l g o r i t h mh a sg o o de f f i c i e n c ya n da c c u r a c y k e yw o r d s ：d a t as t r e a m ；t i m ew i n d o w ；d o s e df r e q u e n t ；t i m ed e c a y i n g i v 致谢 值此论文即将完成之际，我怀着崇敬的心情深深地感谢我的导师倪志伟教 授，我的每一部份工作中都凝结着导师无私的关怀和指导。是他们用敏锐的眼 光和丰富的经验使我明确了前进的方向；是他用悉心的指导、渊博的学识和敏 捷跳脱的思维给我以深刻的启示，帮助我克服遇到的困难。他的治学严谨、求 真务实的精神永远值得我学习；他的兢兢业业、热情洋溢是我永远的榜样! 导 师的恩情是无法用语言表达的。 衷心感谢倪丽萍、李峰刚等数据挖掘组的老师。他们对我的学习和研究提 出了许多有益的建议。这里，特别感谢倪丽萍老师给了我很多深刻的启迪。 本文的工作离不开数据流课题组全体成员的支持。感谢高雅卓师姐、王超 师兄，也给了我很多帮助，一起讨论的岁月是快乐的，也是难以忘怀的。 感谢戴奇波、公维峰、孟金华、查春生、周之强等各位同窗，以及王圆圆、 赵裕啸、郭俊峰、李怀英、王世凯等各位同门。在几年的相处中，大家相互鼓 励、相互支持、相互学习，给我留下了难忘的回忆。 感谢合肥工业大学管理学院的领导和各位，是他们的支持和付出，使我有 更多的精力专心于学业。 感谢我的父母，他们的含辛茹苦，他们的勤劳和奉献一直激励着我，多年 来正是他们坚定的支持、帮助才使我走到了今天，我的每一步成长都凝结着他 们无私的奉献。 最后，感谢所有曾经给我以支持、帮助和关心的人们，衷心地道一声：谢 谢! v 作者：姜苗 2 0 11 年4 月 目录 第一章绪论1 1 1 研究背景与意义1 1 2 国内外研究现状2 1 2 1 国内研究现状2 1 2 2 国外研究现状。3 1 3 课题的研究内容和成果3 1 3 1 主要研究内容3 1 3 2 主要研究成果4 1 4 论文的组织结构4 第二章数据流和数据流挖掘6 2 1 数据流概念和特点6 2 2 数据流挖掘及模型k 。7 2 2 1 数据流挖掘7 2 2 2 数据流挖掘模型8 2 3 数据流挖掘技术9 2 3 1 抽样技术9 2 3 2 概要数据结构1 0 2 3 3 概率统计1 l 2 3 4 时间窗体1 1 2 4 本章小结1 5 第三章频繁项集和频繁模式挖掘算法1 6 3 1 频繁项集：1 6 3 1 1 频繁集。1 6 3 1 2 最大频繁集1 7 3 1 3 闭频繁集。1 8 3 2 经典的静态集合的频繁模式挖掘算法1 8 3 2 1a p r i o r i 算法1 9 3 2 2f p g r o w t h 算法2 1 3 3 数据流闭频繁模式挖掘算法2 3 3 3 1m o m e n t 算法2 3 3 3 2m o m e n t 算法分析2 6 3 3 3 基于闭频繁集改进算法2 7 3 4 本章小结2 8 第四章混合窗体的闭频繁集挖掘算法。2 9 4 1 相关知识2 9 v i 4 2f - t r e e 中窗体大小m 与支持度阙值，的定量分析2 9 4 3 频繁模式挖掘3 2 4 3 1 子窗口滑动树卜t r e e 3 2 4 3 2 闭频繁项集树n e w t - t r e e 3 3 4 3 2 1 添加个子窗体，更新权重支持度3 3 4 3 2 2 添加个子窗体3 3 4 3 3 读取闭频繁模式3 5 4 4 实验及分析3 5 4 4 1 实验环境介绍3 5 4 4 2 实验结果及分析3 7 4 5 本章小结3 8 第五章工作总结和展望3 9 5 1 工作总结3 9 5 2 工作展望4 0 参考文献4 1 攻读硕士学位期间发表的论文和科研项目。4 5 特别声明。4 6 v 插图清单 图1 - 1 论文的组织结构图5 图2 - 1 数据挖掘过程8 图2 - 2 快照式窗体模型1 2 图2 - 3 界标窗体模型1 2 图2 - 4 滑动窗口模型1 3 图2 - 5 衰减窗口模型1 4 图3 - 1 初始化的f p - t r e e 2 4 图3 - 2 初始化后的c e t 结构2 5 图3 - 3 删除一个事务后的c e t 结构。2 6 图3 - 4 添加一个事务后的c e t 结构2 6 图4 - 1 模拟数据流子窗体2 9 图4 - 2 更新前，各节点的加权支持度3 4 图4 - 3 更新后，各节点的加权支持度3 4 图4 - 4 在数据集t 2 0 1 4 d i o o k 运行时间的比较3 5 图4 - 5 在不同支持度下，在数据集【j s h r o o n 运行时间的比较3 6 图4 - 6 在不同个数子窗体的情况下，算法覆盖率的比较3 7 图4 - 7 在不同个数子窗体的情况下，算法覆盖率的比较3 7 v i 1 1 研究背景与意义 第一章绪论 上世纪7 0 年代起，人们开始关注数据库技术在数据库领域的应用，这种 传统数据库的技术获得了巨大的成功。2 0 世纪末，随着信息技术的飞速发展， 很多领域所产生和待解决的数据是动态的，比如金融市场、网络监控、电讯数 据管理、传感器网络等，这些数据是有别于传统数据库中的静态数据。这些数 据在时间维度上严格有序，在数值上不断变化且无限大小的，规模庞大，增长 速度很快。如果先把这些数据全部保存到物理介质中，利用传统的数据库技术 中提交数据操纵语言来访问物理介质来获取查询结果。这种数据具有快速流 动、无限大小的特点，不可能在有限的存储空间中保存全部数据信息；在查询 处理过程中对实时性要求比较高，所以不能先保存数据，再进行处理。可见， 对数据流进行有效的操作和管理，已无法再使用传统的数据库技术。为了有效 地对流数据进行有效的操作和管理，必须研究和开发出新的符合数据流特点的 处理技术。 在理论和应用方面，频繁模式挖掘算法的研究取得了很多的成果，出现了 许多经典算法。这些算法难以实现增量式地更新，不适用数据流挖掘的过程。 挖掘数据流中的频繁模式，需要获得所有过去或将来的数据，否则，采用计算 任何项集的方法都不可能准确地挖掘频繁集。与静态数据集的挖掘算法相比， 数据流挖掘算法较复杂，需要获取更多的信息。频繁项集随时间的变化而变化， 在某一个时刻，非频繁集可能成为频繁集，频繁集也可能成为非频繁集。数据 流是动态的，不断到来的，所以无法确定数据量的大小，需要动态调整存储结 构适应频繁项集的时间敏感问题。根据数据流中频繁模式挖掘的要求，许多相 关算法被陆续提出n 。1 刳。为解决数据流频繁项集挖掘过程中出现的问题， c g i a n n e l l a 和j 。h a n 等提出了f p - s t r e a m 数据结构，采用倾斜时间窗口解决 时间敏感问题，从而维护频繁模式。g s m a n k u 提出频繁模式挖掘算法s t i c k y s a m p l i n g ，r m o t w a n 提出频繁模式挖掘算法l o s s y c o u n t i n g ，两种算法都采用 数据分段的思想，设定支持度和错误因子阈值，并给出单个频繁项集的有效求 解方法，也给出求解频繁项集的实践方法。在数据流环境下，必须进行数据流 变化检测，是数据流区别于传统静态数据集的一个特征。在数据流的变化检测 方面，也做了相关的研究。例如文献n 3 1 4 1 综述在线挖掘数据流变化的重要意义， 其中n 们还提出相对差异度量方法，是一种新的距离度量方法，另外，还提出一 种非参数变化检测方法。近年来，也出现了一些有效的离群点检测算法，大都 是基于数据挖掘概念的检测研究。例如：k n o r r 等提出算法f i n d a l l o u t s d u ， 是基于距离的；y u 等提出算法f i n d o u t n 引，是面向高维数据离群点的检测； b e u n i n g 和p a p a d i m i t i r o u 提出的l o fc 1 7 3 和l o c 算法n 町等。在处理大规模数据 集时，上述算法的空间和时间复杂度均较大，需要多遍扫描数据流数据的情况 下，才能得到结果。目前，数据流中离群点检测问题也是研究的重点。为解决 时间序列中的离群点检测问题，j a g a d is h 等旺伽提出离群点的概念， m u t h u k r i s h n a n 等n 们首次提出了针对大规模数据流的异常检测算法。为了检测 分布式数据流中的离群点问题，p a l p a n a s 等心妇最先提出一个信号网络中异常检 测的框架，在分布环境中进行的，从总体角度讨论这个问题，并指出进一步要 解决的问题。不同于p a l p a n a s 等提出的层次型网络结构，杨宜东等比纠提出的 f i n d o u t s t r e a m s ，是基于核密度估计的，全局数据的子集主要是由不同的节点 的数据流组成的，设定相同的权重，重点讨论全局环境下离群点检测问题；也 进行了详细的讨论了分布环境下节点间的协调通信、统计维护信息以及离群点 检测等问题。 数据流中的频繁模式挖掘在许多领域有着非常重要的意义，例如：在商品 交易中，频繁模式对应着超市中几种最常一起被销售的物品，它们之间可能存 在的联系及概率，最典型的是啤酒和尿布之间的关系；在网络监控和通信工程 中，频繁模式可能意味着网络堵塞，可能是因为网络受到攻击的前兆；在传感 器网络数据流中发现频繁模式，可灵活组织传感器，发现最大量的有用数据； 在w e b 中发现频繁模式，可优化网站结构，提高网站性能等等。 目前，金融仿真系统、犯罪数据仿真系统等一些仿真系统中，数据量较大 且具有一定的动态性，这种仿真数据具有不断变化更新，并受多种因素影响等 特点，可以把它们当做数据流进行处理。如何更好地对这些仿真数据流进行分 析，得到有益的规则是目前研究的一个热点问题。 1 2 国内外研究现状 从上世纪9 0 年代起，闭频繁集的概念被提出，大量科研人员从各个不同 的层面和角度做了一定程度的研究，并提出了很多新的观点和改进算法。不断 涌现出大量不同思想的算法。 1 2 1 国内研究现状 目前，国内挖掘数据流中闭频繁项集的主要算法有心3 吨们等。刘学军等人提 出了闭频繁集挖掘算法是基于滑动子窗口的，挖掘每个基本窗口的临界闭频繁 集，采用数据结构d s c f i t r e e 存储频繁闭合项集，并更新结构，然后将这些 闭频繁集及其子集动态地压缩存储在这棵树上，并能增量更新，有效地挖掘所 2 有频繁闭合项集。程转流等人提出基于数据流分段的闭频繁集挖掘算法。该算 法先将数据流分段，利用局部d s f c i - t r e e 分段存储挖掘结果，并将存储结果 更新到全局d s f c i - t r e e 上。在允许的误差范围内，算法能求出动态数据流中 更多的闭频繁集，有效挖掘已来到的数据流中的所有闭频繁集。h u a f ul i 等 人提出一种运用二进制标记各事务所包含的项集来挖掘的闭频繁集的方法 n e w m o m e n t ，该算法在一遍读取数据流的情况下了，存储所有一阶频繁项集和 所有的闭频繁项集，维护一个简单的c e t 结构，并不需记录事务时标，通过遍 历一个哈希表来读取闭频繁项集。和m o m e n t 算法相比，算法节省了时间和存 储。但是它所挖掘的数据只是最近的w 条事务，忽略了历史模式。 1 2 2 国外研究现状 目前，国外挖掘数据流中闭频繁项集的主要算法有昭5 。3 2 1 等。c h a r m 通过双 向搜索项目集与事务标识集，快速地获取闭频繁集，并能快速识别不频繁项集， 将其删除。但是对于稠密的或包含特别长项集的数据集，可伸缩性较差。闭频 繁集挖掘算法c l o s e t + 需要反复递归构造新的条件f p t r e e ，是基于堆栈的。 m o m e n t 能在任意时刻输出当前窗口的闭频繁集，但需维护一个数据结构c e t 。 闭频繁合项集挖掘算法c f i - s t r e a m 是基于滑动窗口的，无需判断结点类型， 就能直接生成闭频繁项集，并更新之，还不需存储频繁闭合项集之外的其它项 集，能很大地提高方法的时间和空间效率，尤其是数据流事务之间高度关联时， 效率更高。还可以实时输出符合支持度阈值的当前的闭频繁集。这些数据流挖 掘算法大都基于滑动窗口，能很好地挖掘当前最有用的模式，但是这些算法大 都建立在固定大小的窗口上，窗口的最佳大小无法准确确定，同时也未考虑时 间的衰减对闭频繁模式挖掘的影响。近年来，在挖掘数据流最近的频繁模式中 取得了很多成就，挖掘数据流上多个时间粒度的频繁模式的f p s t r e a m 算法， 由g i a n n e ll a 等人提出的，应用倾斜时间窗口策略保存数据流上最近的频繁模 式。维护数据流历史时间窗口内的模式信息的d s t r e e 的模式树，由l e u n g 与 k h a n 提出的，每个节点上都使用多个计数器，分别记录最近的多个数据分段内 模式上各自的支持数，可以精确挖掘多个数据分段内的频繁模式。 1 3 课题的研究内容和成果 1 3 1 主要研究内容 基于数据流中挖掘数据流频繁模式的现状，本文提出了一种新的数据流闭 频繁模式挖掘算法n e w t m o m e n t ，是基于m o m e n t 算法的，主要用于处理仿真数 据。该方法首先将数据流分割为若干个基本窗口，以基本字窗口为单位，利用 3 f - t r e e 挖掘每个基本窗口的频繁项集，然后根据设定的支持度阈值对f - t r e e 进行剪枝，将得到的闭频繁模式存储到t t r e e 中，t - t r e e 以子窗体为单位实 现增量式地更新，快速挖掘滑动窗口中所有闭频繁模式。 1 3 2 主要研究成果 在单遍扫描数据流的条件下，n e w t - m o m e n t 能完整地记录模式信息。同时， n e w t - m o m e n t 提出的减枝方法能很好地降低滑动窗口树f t r e e 的空间复杂度与 闭频繁模式树t - t r e e 的维护代价。此外，该方法提出的时间衰减机制能区分 历史和最新模式，还可以随时响应查询需求，解决现实生活中许多复杂的关联 问题。算法既考虑了闭频繁模式的时间敏感性，又保存了历史模式，响应了查 询需求。 1 4 论文的组织结构 论文的主要研究工作及创新包括以下六个方面： 第一章：阐述课题的研究背景和意义、国内外研究现状以及主要研究内容 和成果； 第二章：介绍数据流及特点、数据流挖掘概念及模型、数据流挖掘技术等 基础知识； 第三章：介绍频繁项集和频繁模式挖掘算法。主要包含频繁集的相关概念 的定义、数据流频繁模式挖掘算法、经典的静态集合的频繁模式挖掘算法、数 据流闭频繁模式挖掘算法； 第四章：介绍混合窗体的闭频繁集挖掘算法。主要包含相关概念的定义， f t r e e 中窗体大小m 与支持度阙值，z 的定量分析，频繁模式挖掘，实验和结果 分析； 第五章：总结全文，并对未来的研究工作进行展望。 论文的组织结构图如图1 - 1 所示： 4 图1 - 1 论文的组织结构图 第二章数据流和数据流挖掘 2 1 数据流概念和特点 数据流是大量有序序列，具有顺序存取、连续到达、潜在、无限数据的特 点，这些数据或其摘要信息，暂时驻留在内存缓冲区中，所有的数据处理都在这 段时间内完成的。当内存缓冲区被填满之后，随着新数据的到达，内存缓冲区 中最先存入的数据将被依次删除，不能再被访问，并被读取一次或者有限次。 数据流不断到达，在有限的存储空间中无法保存全部数据，而且，数据流 查询处理过程中对实时性的要求较高，很难对数据流产生的速度和规模进行预 测和控制，将丢弃或者压缩存档一项处理过的数据，所以不能先保存全部数据， 也无法随机访问历史数据。因此，为了有效管理数据流数据，完全依靠已有的 数据库技术，已经完全不现实，必须对数据流管理新技术进行研究。数据流中 的数据与传统的相对静止的数据是完全不同的。 数据流的特点主要归纳为以下几条： ( 1 ) 无限性。数据流是不断到来的，若要将其，需要无限的存储空间才能存 储全部数据。所以，只能部分地保存数据流中的数据。数据流上的查询多数只 能是近似的查询结果，而非精确的查询结果。 ( 2 ) 不确定性。由于数据流中的数据是不断变化的，预测方法很难完全准确 地预测下一刻即将到来的数据值。 ( 3 ) 一次读取。因为数据流的数据量很大，所以不能完全保持数据流中的数 据，所以对于数据流上的数据，不能读取多次，只能边读取，边抛弃。 ( 4 ) 数据的动态性。在数据流模型中，不再从磁盘和内存中随机访问读取 需要被处理的数据，而是随机的，实时的，不确定大小的数据项组成的时间序 列。 ( 5 ) 按序读取数据。数据流中的数据是按序流过的，不受应用系统控制。由 于数据量很大，所以也不能把所有的数据先存储起来，然后再进行排序之类的 操作，所以，一般只能按照数据流到来的顺序对数据进行访问，不能随机访问。 传统数据库的设计已经不能适合连续、快速到达的数据流序列，不能直接 支持数据流应用中的“连续查询。因此，在数据流应用系统中，不能直接将 数据流存放到传统数据库中。近似性和适应性是在数据流的查询和分析过程中， 最重要的两个特点；而传统的数据库管理系统中，关键是能否提供精确的查询 结果，不要求快速响应查询要求。为了满足数据流的特殊要求，越来越多的数 据流挖掘算法接连被提出来。 6 2 2 数据流挖掘及模型 2 2 1 数据流挖掘 数据挖掘是个反复的过程，通常包含几个相互联系的步骤，如定义问题、 分析问题、数据预处理、选取算法、提取规则、评价和解释结果、将模式转化 为知识，最后，将知识应用到实际的现实中。并且随着应用需求和数据基础的 不同，数据挖掘处理的步骤可能也会有所不同。通常，数据挖掘基本步骤： ( 1 ) 定义问题。学习需要被分析的应用领域里的行业知识，包含：这个行 业的现状和遇到的问题，以及在这次数据挖掘过程中的挖掘目标。 ( 2 ) 建立目标数据集。选择一个数据集或多数据集的子集作为数据源。分 为两部分：训练数据集和测试数据集。 ( 3 ) e t l 。数据清洗、整理、合并，即去除噪声或无关数据，去除空白数据 域，考虑时间顺序和数据的变化，尽量减少无效变量的数目。 ( 4 ) 建立模型。确定数据挖掘的目的，用k d d 过程中的准则选择某一个特 定数据挖掘算法( 如分类、聚类、模式识别、回归等) 用于挖掘数据集中的模式， 结果可以是近似的。 ( 5 ) 数据挖掘。使用被选取的数据挖掘算法，利用数据挖掘算法在一个确 定的数据集上，挖掘一些特定的感兴趣的模式或规则。 ( 6 ) 知识表示。解释那些被发现的模式，并剔除重复的或不合实际的模式。 然后，将剩下的、有用的模式转换为可以被理解的、被接受的知识。 ( 7 ) 评价知识。将得到的这些知识运用到实际系统中，验证这些知识的作 用。用预先可信的知识检查和解决知识中可能存在的矛盾，一直到知识中存在 的错误降低到最低的、可以接受的程度为止，否则，从别的角度定义问题，继 续进行数据挖掘过程。 数据挖掘是个反复进行的过程，用户用数据挖掘语言来解决挖掘任务，得 到挖掘结构，即规则；也可能对挖掘到的知识提出意见，对已有的知识或规则 进行修正。在一定程度上，这些意见可被用来完善数据库挖掘的结果。 上面的处理步骤往往需要多次的反复完成，从而不断地完善挖掘结果，提 高数据挖掘效果。具体如下图2 - 1 所示： 7 2 2 2 数据流挖掘模型 图2 - 1 数据挖掘过程 在对数据集进行单边扫描和有限的存储空间的情况下，处理一个无限大小 的数据流序列时，处理模型要求算法可以快速完成计算，响应用户实时性的请 求。这样，只能用概要数据结构来替代规模较大的数据流，从而实现连续处理 数据流。 典型的数据流处理模型，由数据流输入接口、缓冲区、数据流处理机制、 结果输出接口等四部分构成。数据流算法的特点是要求算法在一遍读取数据流 的情况下，完成数据挖掘，得到较满意的近似结果。因此，这个模型中，处理 机制成为影响处理结果的关键因素，直接关系到模型的时间和空间复杂度。 当数据流上的部分或全部数据以一种连续流的形式在线达到，数据流处理 模型需及时处理这些新到达的数据，并在用户提出查询请求时，及时地把数据 流上最新的查询结果反馈给用户。所以，数据流挖掘算法必须满足以下几个条 件： ( 1 ) 实时处理性。由于数据流快速到达，要求算法高速处理数据元素，跟 上数据流的输入速度，并实时、连续地输出频繁模式挖掘结果。这不是偶然一 次行为，而应该是一个连续、在线的过程； ( 2 ) 结果的近似性。数据流中的数据是海量的，所以不可能在内存及硬盘 上将整个流数据集存储起来。在流数据速度很快的情况下，很难看到数据流中 的每一个数据元素，只能分析部分数据元素，然后做出决策，得到近似的处理 结果，来替代整体数据流所涵盖的规则。 ( 3 ) 低空间复杂度。用来存储动态变化的数据流的空间是很有限的，因此 空间复杂度也就相应比较低。但是为了能够对项集的支持数进行计数，不仅要 存储频繁项集，而且还应存储那些可能变成频繁项集的非频繁项集。此时，这 些特殊项集存储的数量大小取决于内存的容量和算法的空间复杂度。可见，算 法的空间复杂度在一定程度上影响挖掘结果的准确性。 ( 4 ) 处理的时序性。数据流是按照一定顺序到达的时序，所以对流中数据 元素的访问只能是单次线性的。即数据元素在一次读取的前提下，只能按其流 入顺序依次读取，不能像随机访问静态数据库中的数据一样，随机访问数据流。 ( 5 ) 适应性。根据可用资源的具体情况，动态地调整所用参数和存储内容， 随着当前各种传感器网络和手持设备的普及，这种特性显得越来越重要。 2 3 数据流挖掘技术 数据流是个快速流动、无限大小的数据序列。在一个可以接受的范围内， 降低挖掘结果的准确性，得到一个近似的结果，从而保证算法能快速读取所有 的数据流，也是以后各近似计算，拿准确度来换取效率的方法。所以在研究处 理技术时，根据数据流的特点，必须考虑资源分配、对系统负载的影响等问题， 基于统计学的概要信息提取方法被数据流系统广泛采用，这样才能使已成熟的 静态数据挖掘算法可以应用于数据流挖掘过程中，在近似挖掘的过程中，用到 的挖掘技术主要有抽样技术、概要数据结构、概率统计、时间窗体等。 2 3 1 抽样技术 抽样技术研究的目标是全体对象。但是由于全体的数目过多，或者得到全 体数据的总体比较困难，这个时候选取总体的一部分个体作为样本。通过研究 样本的某些特性，依据所获得的数据对总体的数量特征得出具有一定可靠性的 估计判断，从而达到对总体的认识。根据抽样的方式的不同，抽样方法分为简 单随机抽样、系统抽样、分层抽样、整群抽样四种。由于抽样方法以及选取的 样本存在不确定性等方面的原因，从样本得出的特性不一定和总体是一致的， 9 存在一定程度的误差。但是这种方法可以减少时间和空间复杂度，提高效率。 通过基于统计方法地选择数据流中已到达的数据元素，对这些被选中的部 分数据元素进行处理，然后得到处理结果，认为这些数据元素所涵盖的信息和 整体数据流所涵盖的信息是一致的。抽样技术分为均匀抽样和不均匀抽样两 种。其中均匀抽样是指以相同的概率选取数据流中的数据元素，而不均匀抽样 则是指按照数据元素的重要程度的不同而赋予不同的选取概率。 1 ) 水库抽样 水库抽样是指在单遍扫描的情况下，对数据流进行抽样的方法。这种方法 中，所有的数据元素都占用单独的存储空间。数据流维护一个固定大小的样本 集合，大小设定为s ，在某一时刻，以s n 的概率将数据流上的元素选入抽 样集合。抽样的过程中，各个元素被选中的概率是相同的。 2 ) 精确抽样 精确抽样通过合并相同数据元素为一个值次数对，减少重复数据所占用的 内存，从而在一定程度上提高存储效率。首先，以1 t 的概率选取抽样元素， 并加入到样本集合中。如果样本集合中存在这个元素，则将对应的计数器加1 ， 否则添加一个新的值次数记录。有些学者已经开始研究利用精确抽样方法来解 决决策树分类以及k 均值聚集过程中所遇到的问题。 3 ) 计数抽样 计数抽样方法是在精确抽样方法的基础上构建，但是当样本集合溢出的时 侯，他们的处理方法却不相同；精确抽样以相同概率1 t 决定是否将计数减1 ， 当计数为o ，将不再减小计数器的值，也不再对这个元素进行操作。虽然计数 抽样不是均匀抽样，但能高效地获取数据集中的活跃元素。研究的热点和重点 是如何设计种抽样方法，从数据到达速率、抽样率、误差限制三个角度，使 得到的近似结果能尽可能地接近精确值。 2 3 2 概要数据结构 概要数据结构是指用小空间来近似解决大规模数据集的一种思想。概要数 据结构是指构建概要技术对数据流进行处理的过程，这类概要技术能够从数据 流中提取出未来分析所需要的信息。在概要数据结构的构建中，主要方法有小 波分析、直方图方法等。 ( 1 ) 小波分析 小波分析技术是提取数据流概要数据结构表示的一种常用技术。特定信号 到基准向量正交集的投影值被定义为小波系数。通过几个较少数量的小波系数 来近似拟合原来的数据，并能得到最佳地效果，这也是概要数据结构构建成功 的主要原因。针对数据流处理模型，已有很多多人在小波系数的研究上做了很 多工作。最先的做法是运用简单的贪心算法来实现最优地表示小波。 1 0 ( 2 ) 直方图 直方图是指将一个关系中的一个或多个属性分类，并做一些标记，来标记 数据，从而近似地将数据分类。使用每个分类中所维护的概要统计信息来近似 地估计属性的值和出现的频率。直方图方法是实际中应用统计学处理数据最为 广泛的方法之一，因为对于真实世界中的数据库而言，大多会需要直方图来估 计产生的误差，并且占用空间不大。已有人在近似查询处理方面做了相关的研 究。 2 3 3 概率统计 概率的定义是指随机事件发生可能性大小的量，是事件本身所固有的不随 人的主观意愿而改变的一种属性，又机会率、机率、可能性，是数学概率论的 基本概念，是一个在0 到l 之间的实数，是对随机事件发生的可能性的度量。 概率统计是指研究自然界中随机现象统计规律的一种数学方法。即用概率 的思想去统计数据中所涵盖的信息存在的比例，或者按照一个可接受的值作为 选择标准，去选取符合条件的。得到的结果与真实结果之间的误差，也是在我 们的预算的范围内，是一个可接受的值，从质的角度来讲，是没有任何差别的。 数据流是大量连续到达、潜在、无限数据的有序序列，这些数据或其摘要 信息按照顺序存取，并暂时驻留在内存缓冲区中，所有的数据处理都在这段时 间内完成的。但是由于数据是无穷的，不可能全部存储起来，然后再进行处理， 在这个时候，很难得到精确的结果。就要求我们在为了响应数据流的快速流动 性，不得不以牺牲精度来换取速度。这样，就只能在一定的可接受的范围内得 到近似结果。 2 3 4 时间窗体 确定了数据流的结构特征，要想对这种结构化的数据流进行处理。根据处 理方法和结果要求的不同，可以将这些数据流划分为不同的数据梳模型。确定 数据流中的时间窗口需要三个要素：窗口的始末点、度量单位和更新间隔。 一般根据数据流处理时的