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

张珊：数据流中频繁项挖掘算法的研究 摘要 随着信息技术的快速发展，流数据在很多领域的广泛应用呈现在我们面前， 对流数据的研究也成为目前国际数据库研究领域的一个热点。与传统的静态数 据不同，流数据是一个具有时间标记的有序的数据集，其特点是连续的、无限 的，通常以很高的速度到来，并且数据分布随着时间而改变。因此传统的对数 据进行挖掘的算法已经难以适用到流数据上。许多研究人员对数据流中频繁项 挖掘进行了研究，目前，在数据流中挖掘频繁项已经成为数据挖掘研究领域的 重要研究方向。 本文针对流数据特点，研究数据流中对频繁项进行挖掘的高效算法。我们 分析了当前国内外在流数据上的频繁项挖掘的各种算法，针对存在的问题，提 出了一些更为有效的算法。本论文的主要工作如下： 1 现有的大多数数据流频繁项挖掘算法并没有能强调当前数据的重要性。 为此，我们采用衰减系数的方法，给出强调近期数据而弱化“旧数据重要性 的时间衰减模型。我们提出了利用时间衰减模型来检测数据流的占一近似频繁项 挖掘的f e 算法。算法的存储空间复杂度为o b 一) ，时间复杂度为0 ( 矿1 ，其召回 率和精确度远大于同类算法，我们实验证明，该算法比其他类似方法有较高的 正确率，较快的处理速度以及较少的内存需求。 2 我们采用衰减系数的方法，另提出了利用哈希表和堆来对数据流中的频 繁项进行占一近似挖掘的f h h 算法，该算法利用一个哈希表和一个堆记录流数据 中的潜在频繁项。算法的存储空间复杂度为。忙- 1 ) ，时间复杂度为o ( i o g c 1 ，我 们的实验证明，该算法具有较高的精度，在时间和空间复杂度方面也优于其它 类似的算法。 3 滑动窗口是一种对最近一段时间内的数据进行挖掘的有效技术。因此， 我们提出了一种基于滑动窗口的流数据频繁项挖掘的s w 算法。算法采用了链表 队列策略大大简化了算法，提高了挖掘的效率。对于给定的阂值s 、误差占和窗 口长度n ，算法可以检测在滑动窗口内频度超过s n 的数据流频繁项，且使误差在 日l 以内。算法对每个数据项的处理时间为0 ( s 。1 ) ，对一个数据项的查询时间为 张珊：数据流中频繁项挖掘算法的研究 o ( 1 ) ，对所有数据项的查询时间为0 ( 6 j ) ，存储空间复杂度为o ( e 一) 。通过大量 的实验证明，本文算法比其它类似算法具有更好的精度以及时间和空间效率。 关键词：数据挖掘；数据流：频繁项；衰减系数；哈希表；堆。 张珊：数据流中频繁项挖掘算法的研究 a b s t r a c t i nr e c e n ty e a r s ，w i t ht h er a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y ，s t r e a m d a t aa r ew i d e l ya p p l i e do nm a n yf i e l d s t h e r e f o r e ，s t r e a md a t am i n i n gb e c o m e sa r e s e a r c hh o t s p o ti nt h ea r e ao fd a t am i n i n g u n l i k et h et r a d i t i o n a ls t a t i cd a t a ， s t r e a m i n gd a t ai sa no r d e r e ds e to fd a t aw i t ht i m es t a m p s t h e ya r ec o n t i n u o u s ， u n l i m i t e d ，a n da r r i v i n ga tav e r yh i g hs p e e d i nt h es t r e a m ，d a t ad i s t r i b u t i o nc h a n g e s o v e rt h et i m e t h e r e f o r e ，t r a d i t i o n a ld a t am i n i n ga l g o r i t h m sc a nn o tb ea p p l i e d d i r e c t l yo nt h es t r e a md a t a m a n yr e s e a r c h e r sh a v es t u d i e dt h em e t h o d sf o rm i n i n g t h ef r e q u e n td a t ai t e m si nt h es t r e a m ，w h i c hh a sb e c o m ea ni m p o r t a n ta r e ai nt h e r e s e a r c ho fd a t am i n i n g i nt h i st h e s i s ，w es t u d yt h ea l g o r i s mf o rm i n i n gt h ef r e q u e n td a t ai t e m si nt h e d a t as t r e a m s e v e r a le f f i c i e n ta l g o r i t h m sf o rm i n i n gt h ef r e q u e n td a t ai nt h es t r e a m a r ep r e s e n t e da f t e ra n a l y z i n gt h ee x i s t i n g a l g o r i t h m s i nt h i sa r e a t h em a i n c o n t r i b u t i o n so ft h ep a p e ra r ea sf o l l o w s ： 1 m o s to ft h ee x i s t i n ga l g o r i t h m so nm i n i n gf r e q u e n ts t r e a md a t ai t e m sd on o t e m p h a s i st h ei m p o r t a n c eo ft h er e c e n td a t ai t e m s w ei n t r o d u c ea t i m ef a d i n gm o d e l w h i c he m p h a s i z e st h er e c e n td a t ai t e m sa n dd e c r e a s e st h ei m p o r t a n c eo ft h eo l d o n e s b a s e do nt h i st i m ef a d i n gm o d e l ，w ep r e s e n tf ea l g o r i t h mf o rm i n i n gf r e q u e n t i t e m s t h ef ea l g o r i t h mc a l ld e t e c t - a p p r o x i m a t ef r e q u e n ti t e m so fd a t as t r e a m u s i n go ( 8 - t ) m e m o r ys p a c ea n dt h ep r o c e s s i n gt i m ef o re a c hd a t ai t e mi s0 ( 6 - 1 ) e x p e r i m e n t a lr e s u l t ss h o wt h a tf eh a sh i g h e rp r e c i s i o n ，r e q u i r el e s sm e m o r ya n d c o n s u m el e s sc o m p u t a t i o nt i m et h a no t h e rs i m i l a rm e t h o d s 2 b a s e do nt h et i m ef a d i n gm o d e l ，w ep r e s e n tf h ha l g o r i t h mf o rm i n i n gt h e 占- a p p r o x i m a t ef r e q u e n ti t e m so ns t r e a md a t a u s i n gah a s ht a b l ea n dah e a pt o r e c o r dt h e p o t e n t i a lf r e q u e n t d a t ai t e m s ，t h ef h ha l g o r i t h mc a nd e t e c t a p p r o x i m a t ef r e q u e n ti t e m so fd a t as t r e a mu s i n go ( c 一1 ) m e m o r ys p a c ea n dt h e 张珊：数据流中频繁项挖掘算法的研究 p r o c e s s i n gt i m ef o re a c hd a t ai t e mi so ( 1 0 9 占- t ) e x p e r i m e n t a lr e s u l t ss h o wt h a tf h h a l g o r i t h mo u t p e r f o r m so t h e rm e t h o d si nt e r m so ft h ea c c u r a c y ，m e m o r yr e q u i r e m e n t ， a n dp r o c e s s i n gs p e e d 3 t h es l i d i n gw i n d o wi sa na c c e p t e da n de f f e c t i v ea p p r o a c ht om i n ef r e q u e n t d a t ai t e m si nt h er e c e n tp e r i o do ft i m e w ep r o p o s ea na l g o r i t h mswf o rm i n i n g f r e q u e n td a t ai t e m si nas t r e a mb a s e do ns l i d i n gw i n d o w t h i sp a p e ra d o p t sl i n k e d q u e u es t r a t e g yw h i c hg r e a t l yi m p r o v e st h ee f f i c i e n c yo ft h ea l g o r i t h m g i v e n a t h r e s h o l ds ，a ne r r o rb o u n d 占a n dt h el e n g t ho ft h es l i d i n gw i n d o wn ，a l g o r i t h m s wc a nd e t e r m i n a t e l yd e t e c t t h ed a t a i t e m sw i t h i nt h ec u r r e n tw i n d o ww h o s e f r e q u e n c ye x c e e d ss nw i t ha ne r r o rl e s st h a n 翻u s i n go ( e 一) m e m o r ys p a c e ，a n d t h ep r o c e s s i n gt i m ef o re a c hd a t ai t e mi so ( e 。1 ) t h et i m ef o ra n s w e r i n gaq u e r yi s o ( 1 ) f o ro n ed a t ai t e m ，a n do ( e 。1 ) f o ra l lt h ed a t ai t e m s o u re x p e r i m e n t a lr e s u l t s s h o wt h a to u rf h ha l g o r i t h mo u t p e r f o r m so t h e rm e t h o d si nt e r m so ft h ea c c u r a c y ， m e m o r yr e q u i r e m e n t ，a n dp r o c e s s i n gs p e e d k e y w o r d s ：d a t am i n i n g ；s t r e a md a t a ；f r e q u e n ti t e m ；f a d d i n gf a c t o r ；h a s h t a b l e ；m - h e a p 张珊：数据流中频繁项挖掘算法的研究 6 7 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取得的 研究成果。除文中已经标明引用的内容外，本论文不包含其他个人或集体已经 发表的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律结果由本入承担。 学位论文作者签名：多长翮中 签字日期： 伽) d 年r 月i 中日 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并 向国家有关部门或机构送交学位论文的复印件和电子文档，允许论文被查阅和 借阅。本人授权扬州大学可以将学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授 权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 学位论文作者签名：戥附 签字日期： 伽d 年岁月f p 日 名：( ；1 季元菱 签字日期：切p 年岁月牛日 ( 本页为学位论文末页。如论文为密件可不授权，但论文原创必须声明。l 张珊：数据流中频繁项挖掘算法的研究 第一章绪论 1 1 研究背景 随着信息化技术的迅速发展，在各个领域中涌现出大量的数据，这些数据数 量很大，并且随时间源源不断的到来，例如在网络监控、入侵检测、情报分析、 金融服务、股票交易、电子商务、电信、卫星遥感( 气象、环境资源监控等) 、 w e b 页面访问和科学研究等众多领域中，数据以流的形式出现，这些数据的量巨 大，其增长速度超乎人们的想象，例如，沃尔玛超市的日交易量次数可达数十 万；g o o g l e 每天接受2 亿次的查询任务，a t & t 每天收集的网络流量数据多达 1 0 0 g b 。 在这些大量的流数据中利用数据挖掘的方法挖掘出蕴含在其中的丰富的知 识和有用的信息。因此，近年来，数据挖掘己经引起了信息产业界的极大关注， 并对获取的知识可以迅速地反馈到应用领域，使其更好的发挥指导作用。目前 数据挖掘的部分成果己经被广泛地应用于商务管理、生产控制、市场分析、工 程设计、科学探索和国家安全等领域。 近几年，提出了许多数据流挖掘算法，这些算法在解决特定的问题时，或 者在某个特定的领域内是有效的。总的来说，数据流挖掘算法可以分为数据流 的回归分析、分类分析、聚类分析和关联分析等。但是每个数据流挖掘算法具 有很大的局限性，往往只能解决某个特定条件或者特定领域的数据流挖掘问题。 不同的数据流或者数据流的不同时期对算法的要求也不一样，面对新的要求，又 需要开发新的算法，进行重复的实验，算法的可利用性低。怎样将众多的数据流挖 掘算法有机的结合，构建合理的数据流挖掘模型库，减少数据流挖掘算法的重复 开发，成为数据流挖掘技术发展的新要求。 上世纪9 0 年代早期，大部分数据挖掘研究者来自于数据库领域，他们主要 是为了给数据库系统建立有效的数据分析工具。随后，介于数据挖掘是一个多 学科领域，从多个学科汲取营养，这些学科自然包括数据库技术、机器学习、统 计学、模式识别、信息检索、神经网络、基于知识的系统、人工智能、高性能 计算和数据可视化。更多领域的专家加入到数据挖掘圈中，考虑问题的角度也 2 张珊：数据流中频繁项挖掘算法的研究 被极大的拓宽，提出了包括关联规则、聚类、分类、序列模式【1 , 6 8 挖掘等数据 挖掘方向，这些方向的建立也更好地推动了数据挖掘的前进。 以往传统的数据挖掘所面向的对象是静态的、有限的数据。挖掘算法通过 将数据从磁盘读入内存进行分析和处理来挖掘其中的有用知识。数据流中的数 据数量巨大且连续不断的到来，由于受到时间和内存、c p u 等资源的限制，传 统的数据挖掘方法不再适用。如何挖掘数据流中的频繁项，这给研究人员带来 了机遇和挑战。近年来，挖掘数据流中的频繁项成为数据挖掘领域中的研究热 点。 数据挖掘技术在传统的数据上的挖掘都有一个共同点，即数据源都存储在 永久性介质中，可以多次访问。然而，近几年来，一种新形式的数据处理应用 受到了相关领域研究者的关注。在许多实时应用领域，如金融管理f 2 叫、环境监 测管理1 5 ，6 1 、网络监控【7 9 1 、网络流量管理【1 0 1 2 】、事务日志【1 3 - 16 1 、股市波动异常 检测1 5 ，1 6 】等中出现了一类新的数据，这类数据不同于传统的静态的存储在数据 库中的数据，不适合持久稳定关系建模。适合用瞬态数据流建模。我们称这样 的数据形态为数据流( d a t as t r e a m i n g ) 。由于数据流中的数据源源不断，在有 限的存储空间中只能保存数据的概要信息而不是数据全体。这也决定了数据不 能保存下来进行处理。而且，数据流应用对查询处理往往有着很高的实时性要 求，所以就不能频繁地对数据进行访问。因此，传统的数据处理技术已不适合 数据流的处理，已有的数据库技术无法对流数据进行有效的管理，必须进行流 数据管理新技术的研究【1 7 。2 1 1 。这促使人们设计新的挖掘算法来适应新型流数据 模型。目前，越来越多的专家学者开始关注这方面的新应用和理论研究，并试 图利用突破以往在传统数据挖掘方面的经验和方法论来帮助解决新问题。而对 流数据中的频繁项挖掘方法就是本文所致力研究的问题。 1 2 流数据挖掘 1 2 1 流数据特点 流数据不同于传统的基于集合的相对静止的数据。流数据连续到达，频繁 变化，数据量事i j i 是不确定的，也可能是无限的。归纳起来，流数据的共同特 点是： 张珊：数据流中频繁项挖掘算法的研究 3 1 无限性。流数据是大量连续的、有可能是无穷的数据集合。传统数据形 式的数据量也可以是非常巨大的，但是流数据在数据量大的同时，还强调了这 些数据的到来可能是无穷的，即你无法判断最终的数据量的大小。数据流是不 断到来的，若要将其全部存储，需要的存储空间是无限的。 2 未知性。数据流的数据值是不断改变的，利用预测方法也不能准确地预 测下一时刻将到来的数据值。 3 快速变化性，需要快速实时的反应。流数据不但是连续地到来，而且变 化比较频繁，对于流数据上的一些监控或者分析操作来说，有许多应用是要求 实时响应的。那么在一个快速变化的数据上实时响应比在一个比较平稳的数据 上进行分析有更大的难度。 4 不可再现性。对于数据流上的数据，一旦流过处理节点就不会再次出现。 5 流数据很好地捕获了当前对数据处理的需求。许多情况下，流数据的不 断到来正是可以表现出数据演化的过程。 1 2 2 流数据挖掘的挑战 数据流挖掘就是在流式数据上发现提取隐含在其中的、人们事先不知道的、 但又是潜在有用的信息和知识的过程。由于流数据自身的特点，流数据上的数 据挖掘面临着一些挑战： 1 内存有限，单次扫描。数据流是不断产生的，而内存的大小是有限的。 我们无法把收集到的数据都放在内存中进行多次访问和挖掘，而只能实时地保 存数据的概要。所以流数据只能处理一次，不能再扫描历史记录。所以传统算 法不适用于处理流数据挖掘。 2 实时响应。储存在内存中的数据都是最新产生的数据，必须在这些数据 还没被后来的数据替代前，对它进行处理。这就要求我们在设计算法时要考虑 算法的效率，如何在最短的时间内完成对数据的处理。 3 结果的近似性。只能存储数据的汇总信息。由于数据流无法完全存储以 及再次扫描，所以只能得到近似的处理结果。而这种近似的特性可能会影响到 挖掘的最终精确度，所以必须严格控制近似度以保证挖掘的质量。 4 算法的自适应性。数据流挖掘算法必须能够根据特定类型的数据流做出 4 张珊：数据流中频繁项挖掘算法的研究 适应性的变化。比如说，随着时间的推进，数据中所挖掘出来的知识来自的模 型也是不断地变化的( 也可称为概念漂移或进化) ，算法需要对此进行准确预 测，并积极处理和响应。 1 2 3 流数据挖掘模型 建立数据模型是数据管理和分析的基础。传统的数据库处理模型是根据用 户的具体要求，通过d m l 访问数据库或者数据仓库中的数据后，返回较为精 确的查询结果。数据流处理的数据不再是从磁盘和内存中随机访问读取的数据， 而是一个或多个连续的、无穷的数据项组成的序列。因此数据流也不同于传统 的存储关系模型。而由于存储空间的有限性与数据流的无限性，使得存储数据 流中的全部数据以提供精确的查询结果是不实际的，为此，在数据流处理模型 中，数据流处理算法只存储数据流的概要( s y n o p s i s ) 。 图1 1 示出了数据流挖掘模型与传统数据库处理模型的区别 ( a ) 传统数据库处理模型( b ) 流数据挖掘模型 图1 1 据流挖掘模型与传统数据库处理模型的区别 在数据流模型中，部分或全部数据都以一种连续流的形式在线到达，与传 统的关系模型相比，具有以下不同： 1 数据流中的数据是实时到达的，而数据库中的数据是静态的并存储在磁 盘中。 2 在数据流模型中，处理的数据是一个或多个连续的、无穷的数据项组成 的时间序列，一般是顺序访问，而传统的数据库中的数据可以随机访问。 3 数据流中的数据是无限的，而数据库中的数据是有限的。 4 数据流中大部分的数据在处理后被丢弃了，不可再现，所以数据流上的 查询多数只能得到近似的查询结果，而数据库上的查询则可以得到精确的查询 结果。 张珊：数据流中频繁项挖掘算法的研究 5 5 系统只能保存数据流全部数据的一个有限子集或统计数据，并随着数据 流上新数据的到来进行更新，这种更新的频度取决于数据流中数据到达的速度。 显然，数据流的更新频度要远远高于数据库中数据更新的频度。 数据流可看作是一个不断增长的d 维元组集合两，z ， ，对任意的 f ( f 1 ) z = o ；一? ) ，各元组的时标为五。互。对数据流中的数据进行挖掘通常基 于某种特定的时间区问( 称为窗口) ，常用的窗口模型有四种： 1 界标窗口模型( l a n d m a r kw i n d o wm o d e l ) 。在该窗口模型下，被用来 挖掘的数据集为从数据流开始到当前到达的所有元组的集合，即两，z ( f 为 当前元组的时标) ，且窗口大小随数据流进行不断增加。 2 滑动窗i = 1 模型( s l i d i n gw i n d o wm o d e l ) 。在该窗口模型下，被用来挖 掘的数据集为从当前时标开始，最近到达的n 个元组的集合( 这里的n 为滑动 窗口的大小) ，即每i - n + l 。，。，石 ( j 为当前元组的时标) 。窗口位置在时间轴上 随着数据流进行不断滑动。 3 衰减窗口模型( d a m p e dw i n d o wm o d e l ) 。在该窗口模型下，被用来挖 掘的数据集为从数据流开始到当前到达的所有元组的集合，但各元组被赋予不 同的权重。较早到达的元组具有较小权重，较晚到达的元组具有较大权重。各 元组的权重根据某种衰减函数( 例如，指数衰减厂( f ) = 2 以，其中五 0 ) 随时 间，不断衰减。 4 倾斜时问框架( t i t l e dt i m ef r a m e ) 。滑动窗口和衰减函数都只能在单 一时间维的窗口上得到计算结果。然而，很多应用要求在不同的时间粒度层上 进行分析和挖掘。比如，用户通常对细粒度层上的当前变化感兴趣，而在粗粒 度层上对长期变化感兴趣【1 7 1 。h a n 和k a m b e r 在文献【1 】中介绍了三种倾斜时间 框架模型：自然倾斜时间框架模型( n a t u r a l ) 、对数尺度倾斜时间框架模型 ( 1 0 9 a r i t h m i cs c a l e ) 和渐进对数时间框架模型( p r o g r e s s i v el o g a r i t h m i c ) 。 6 张珊：数据流中频繁项挖掘算法的研究 如图1 2 所示： 1 2m o n t h s 3 1 d a y s 2 4h o ur s4 q t r s li ：l jl il ：ll jll ：ul jii li - 砌p ( a ) 自然倾斜时间框架模型 ( b ) 对数尺度倾斜时间框架模型 f r a m en o s n a p s h o t s ( b yc l o c kt i m e ) 06 96 76 5 16 66 25 8 26 86 05 2 35 64 02 4 44 81 6 56 43 2 ( c ) 渐进对数时间框架模型 图1 2 倾斜时间框架的三种模型 在实际应用中，这几种窗口模型的选取往往根据用户的需求而定。无论具 体采用哪一种或几种窗口模型，数据流挖掘都具有如图1 1 ( b ) 所示相同的挖掘 框架。 1 3 本文的主要研究工作 流数据挖掘技术作为数据挖掘中的新领域，当前对于数据流上的挖掘主要 集中在：数据流上的聚类、数据流上的频繁项( 集) 挖掘、分类分析、异常分 析等。本文在深入研究国内外各种数据流挖掘技术的基础上，讨论了目前国内 张珊：数据流中频繁项挖掘算法的研究 7 外数据流频繁项挖掘的研究现状。由于数据流中的频繁项挖掘是数据流的频繁 项集、频繁模式、关联规则、分类等挖掘的基础，而且在流数据挖掘中具有重 要的地位，在实际问题中有许多重要应用，我们在数据流中频繁项挖掘方面进 行了深入的研究，提出了更为有效的算法。本论文的主要贡献如下： 1 现有的大多数数据流频繁项挖掘算法并没有能强调当前数据的重要性。 我们采用衰减系数的方法，给出强调近期数据而弱化“旧 数据重要性的时间 衰减模型。我们提出了利用时间衰减模型来检测数据流的扣近似频繁项的f e 算法。算法的空间复杂度为d ( s 1 ) ，时间复杂度为0 ( 8 。1 ) ，其召回率和精确度 远大于同类算法，我们的实验证明，该算法比其他类似方法有较高的正确率， 较快的处理速度以及较少的内存需求。 2 我们采用衰减系数的方法，提出了利用哈希表和堆来对数据流中的频繁 项进行占近似挖掘的f h h 算法，该算法利用一个哈希表和一个堆记录流数据中 的潜在频繁项。算法的空间复杂度为0 ( 8 1 ) ，时间复杂度为o ( 1 0 9 矿 l ， 我们的 实验证明，该算法具有较高的精度，在时间和空间复杂度方面也优于其它类似 的算法。 3 滑动窗口是一种对最近一段时间内的数据进行挖掘的有效技术。因此， 我们提出了一种基于滑动窗口的流数据频繁项挖掘算法。算法采用了链表队列 策略大大简化了算法，提高了挖掘的效率。对于给定的阈值s 、误差占和窗口长 度门，算法可以检测在窗口内频度超过跏的数据流频繁项，且使误差在翻以内。 算法对每个数据项的处理时间为0 ( s 。) ，对每个数据项的查询时间为o ( 1 ) ，对所 有数据项的查询时间为o ( s 1 ) ，空间复杂度为0 ( 占。1 ) 。通过大量的实验证明，本 文算法比其它类似算法具有更好的精度以及时间和空间效率。 1 4 论文组织结构 论文以下章节的组织结构如下： 第二章介绍了流数据挖掘实现的相关技术，所用到的相关系统，以及当前 国内外在该领域上的研究方向及进展。 8 张珊：数据流中频繁项挖掘算法的研究 第三章研究了基于时间衰减模型的流数据频繁项挖掘算法。首先介绍了数 据项密度的概念，然后提出了一种加入时间衰减系数模型的f e 算法 ( f r e q u e n t e s t i m a t i n g ) 对其中的频繁项进行挖掘，并对算法的总体结构以及相 关技术和细节进行理论分析，给出了查询算法和复杂度分析。最后对提出的算 法进行了实验研究，证明算法的有效性和高效性。 第四章提出基于时问衰减模型并利用哈希表和堆的f h h 算法( h a s ht a b l e a n dh e a p ) 对数据流中的频繁项进行挖掘，接着给出了查询算法，并对算法的 复杂度进行分析。另用实验证明算法具有较好的时间空间复杂度； 第五章研究了基于滑动窗口的数据流频繁项挖掘问题。首先阐述了滑动窗 口的相关概念，然后提出了基于滑动窗口的数据流频繁项挖掘的s w 算法。概 述了s w 算法的总体结构，介绍了s w 算法中相关技术和数据结构，并给出s w 算法的具体细节和理论分析。接着给出了查询算法，并对算法的复杂度进行分 析。最后通过实验研究，证明算法具有较好的挖掘性能。 第六章总结了本文工作，并展望了今后的研究方向。 张珊：数据流中频繁项挖掘算法的研究 9 第二章流数据挖掘研究现状 随着信息技术的发展，流数据上的数据挖掘逐渐被众多学者所关注。本章 首先介绍当前流数据挖掘上的相关实现技术。接着列举出比较流行的流数据挖 掘系统。然后对流数据上频繁数据项挖掘方法的研究现状进行了分析阐述。最 后对本章内容进行了总结。 2 1 流数据挖掘相关实现技术 在当前数据流挖掘环境下，海量的流数据源源不断的到达，而数据流处理 系统的存储及计算资源却是有限的。+ 这就要求在保证算法精度的同时，尽量降 低算法的时间和空间开销。不同数据流挖掘算法的概要数据结构往往相差很大。 研究者往往会根据数据挖掘功能的实际需要，设计出一些新的概要数据结构。 一般而言，抽样、直方图、滑动窗口、小波、哈希、梗概技术以及近似算法等 都是各种数据流挖掘算法构造概要数据结构的常用基本技术。 1 随机抽样技术 随机抽样技术也称为水库抽样( r e s e r v i o rs a m p l i n g ) 技术，此技术是无放回 地选取s 个元素的无偏随机样本，其基本思想相对简单，维护一个大小至少为 s 的样本，称作“水库 ，可以从中产生大小为s 的随机样本。在水库中维护s 个候选的集合，形成流元素的真正随机样本。随着数据流的流动，每个新元素 都有一定的可能性取代水库中的旧元素。假定我们已经看到了六种的n 个元素。 随机选择，一个新元素取代旧元素的可能性为s n 。 2 滑动窗口 ，利用滑动窗口模型( s l i n d i n gw i n d o wm o d e l ) 对流数据进行分析，其基本思 想是：仅仅基于最近的数据作出决策，而不是对目前为止看到的所有数据或者 某个样本进行计算。更形式化，在每个时刻t ，一个新的数据元素到来，该元素 在时刻t + w “过期 ，其中w 为窗口的“大小”或长度。滑动窗口此性能对于 股票或传感器网络很有用，那里只有最近的事件才可能最重要的。由于只需要 存储小的数据窗口，所以可以减少对内存的要求。 1 0 张珊：数据流中频繁项挖掘算法的研究 3 直方图 直方图是一种大纲数据结构，可用来对近似数据流中元素值进行频率分布， 把数据划分为一系列相邻的桶，依照使用的划分规则，宽度( 桶的值域) 和深 度( 每桶罩的元素个数) 可以是不同的。等宽度划分是一种构造直方图的简单 方法，其中每个桶的值域是相同的，尽管这种方法容易实现，但是不能对概率 分布函数进行很好的抽样。较好的是使用v 最优直方图，其定义的桶的尺寸， 最小化每个桶的频率方差，可以较好的体现数据分布。 4 多分辨率方法 多分辨率方法处理大量数据的一种常用的方法是使用数据规约方法。一种 流行的数据规约方法是采用分之策略，如多分辨率数据结构。这些方法允许程 序在准确性和存储之间进行权衡，同时也提供在多层细节理解数据流的能力。 ( 1 ) 平衡二叉树是一个具体例子，当新数据到来时，努力保持树的平衡， 树的每一层提供不同的分辨率。离树的根部越远，这一层的分辨率就越细。一 种更复杂的形成多分辨率的方法是使用聚类方法将数据流组织成为一个层次结 构的树，在b i r c h 中的c f 树那样的典型的层次聚类数据结构来形成微簇的层 次结构。随着动态数据的进出，数据流的汇总统计量可以在微簇的层次结构中 增量地更新。根据应用的要求，可以将这些微簇中的信息聚集到较大的宏簇 ( m a c r o c l u s t e r ) 中，导出多分辨率的一般数据统计量。 ( 2 ) 小波是一种信号处理技术，在此情况下，。流数据可以用来构建输入信 号的多分辨率层次结构。给定一个输入信号，希望用简单的正交基函数分解或 重写它，最简单的基是哈尔小波，使用这种相当于在多分辨率上递归地取平均 和微分。哈尔小波易于理解和实现，尤其擅长处理空间和多媒体数据。对于查 询优化，小波己用作直方图的近似。此外，基于小波的直方图可以随时动态维 护。因此，小波是一种流行的数据流压缩的多分辨率方法。 5 梗概 大纲技术的主要不同点在于如何正确地在准确性和存储之间进行权衡。抽 样技术和滑动窗口模型关注小部分数据，而其他大纲方法试图对所有的数据进 张珊：数据流中频繁项挖掘算法的研究 行汇总，通常在多个细节层上，直方图和小波需要扫描数据多遍，而梗概方法 可以在扫描一遍后完成。 假设数据流的对象或元素的全域上维护完全的直方图，其中全域为 u 2 1 ，2 ，1 ，) ，数据流为a = q ，a 2 ，) 。也就是说，对全域中的每个值f ，维护f 在序列中a 出现的频率或次数。如果全域很大，这个结构也同样很大。因此， 需要更小的表述方式，让我们考虑到a 的频率距( f r e q u e n c ym o m e n t ) 。这些 是数最，定义为r = 罗所j ，其中，v 是全域或定义域的大小，m ，是f 在序列 “ ”一 f = l 中出现的频率，并且k 0 。特殊地，e 是序列中不同元素的个数。曩是序列的 长度( 也是n ) ，只是自连接的大小、重复率或同源的g i n i 指标。当可用内存 小于v 时，需要使用梗概大纲对频率距进行估计。其基本思想是，将每个元素均 匀随机地散列到乞 一1 ，+ l ，然后维护一个随机变量x = ，铂弓，x 2 是互的 个很好的估计。为了得到更好的估计，可以维护多个随机变量，然后，通过选 择这些变量的平方值的中位数，可以提高估计值的置信度接近只，从数据库角 度来看，梗概划分旨在改善数据流查询优化梗概的性能，其可以保证误差，使 用基本数据的粗略统计信息来智能地划分属性的定义域。 6 随机算法 随机算法以随机抽样和梗概的形式，常常用来处理海量、高维数据流。与 已知的确定算法性能相比，随机选择的使用常常导致更简单、更有效的算法。 如果一个随机算法总是返回正确的回答，但是运行时间不确定，则称它为 拉斯维加斯( l a sv e g a s ) 算法。相反，蒙特卡洛( m o n t eca r l o ) 算法的运行 时间有上界，但是可能无法返回正确的结果。假定一个随机算法的返回随机变 量作为结果，我们希望有该随机变量的尾概率界，这告诉我们的是随机变量偏 离它的期望值的概率很小。一个基本的工具是切比雪夫不等式。设x 为一个随 机变量，具有均值为，标准差盯( 方差仃2 ) 。对于任意给定的正实数k ，以 1 2 张珊：数据流中频繁项挖掘算法的研究 下切比雪夫不等式成立尸( i x 一i 七) 生k 2 ，这个不等式可用来限定随机变量的 方差的界。 在很多情况下，可使用大量随机变量来提升结果的置信水平。只要这些 随机变量是完全独立的，就可使用切尔诺夫界。设墨，五，以是独立的泊松实 验。在不同的泊松实验中，成功得概率是不同的。如果x 是五到e 的和，则 一个较弱的切尔诺夫界表明： p r x ( 1 + 万) p 其中万( 0 ，l 】。这表明随着偏离均值，该概率指数地递减，使得低质量的估计不 太可能。 7 小波 小波分析方法是一种通用的数字信号处理技术。类似于傅里叶变换，小波 变换可将输入的模拟量，变换成一系列的小波参数，根据内存大小提取顶端的刀 个高能量参数，近似还原原始信号 2 3 , 2 4 】。小波分析方法已被广泛应用到数据库 领域中，如用在数据流上生成直方图、估算数据立方体【2 5 】，多维聚集值2 6 1 和估 算选择率( s e l e c t i v i t y ) 2 7 】。小波的种类很多，其中最常见的是哈尔小波 ( h a r r w a v e l e t ) 。在文献 2 7 】中，作者提出了一种基于哈尔小波技术的直方图 生成算法，它将整个数据集变换成一系列小波参数，并保留有限个高能量的参 数来近似地模拟原始数据集。在文献 2 3 】中，作者证明如果数据流中的数据已 经排好序，只需o ( b + l o g n ) 的存储空间，就可获得b 个能量最大的小波参数。 文献【2 8 】提出的算法则能够以概率1 - d 保证结果的误差在一个小范围之内，其中， d 是一个接近于0 的用户定义参数。 8 哈希 利用哈希函数生成概要数据结构的方法是计算机领域的一个常用手段。其 b l o o mf i l t e r 方法【2 9 】是使用一小块远小于数据集范围的内存空间表示数据集。 假设所申请的内存大小为m 比特位，创建h 个相互独立的哈希函数，能将数据 集均匀映射到【1 埘】中去。对任何元素，利用哈希函数进行计算，得到h 个【1 朋】 张珊：数据流中频繁项挖掘算法的研究 1 3 之间的数，并将内存空间中这h 个对应比特位都置为l 。这样，就可以通过检查 一个元素经过h 次哈希操作后，是否所有对应的比特位都被置l 来判断该元素是 否存在。这种判断方法可能会产生错误，虽然某元素并不存在，但是它所对应 的h 个比特位都已经被其他元素所设置了。文献【3 0 】改进了上述方法，在每一个 位置上都用计数器代替比特位，从而不仅能够判断元素是否存在，而且能够估 算元素的值。 9 数据流管理系统和流查询 在传统的数据库系统中，数据存储在有限但持久的数据库中。然而，流数 据是无限的并且不可能完全存储在数据库中。在数据库管理系统( d s m s ) 中 可能有多个数据流。它们以联机的方式到达，并且是连续的、时序的和潜在无 限的。一旦数据流中的一个元素处理完，就会丢弃或存档，除非它显式地存储 在内存中，否则就不可能容易的检索它。 流数据的查询处理结构包括三个部分：终端用户、查询处理器和临时空间 ( 可能有主存和磁盘组成) 。终端用户对d s m s 发起一个查询，查询处理器接 受这个查询，使用存放在临时空问的信息处理它，并把结果返回给用户。 查询既可以是一次性查询，也可以是连续查询。一次性查询在数据集的一 个时间点的快照计算一次，把结果返回给用户。连续查询随数据流连续到达不 断地求值。连续查询的回答随着时间的推移产生，总是反应迄今为止看到的流 数据。查询可以是预定义的( 在相关的数据到来之前提供给数据流管理系统) ， 或者是即兴的( 当数据流开始之后联机提交) 。预定义查询通常是连续查询， 而即兴查询既可以是一次性查询，也可以是连续查询。 1 0 流查询的处理 流数据的特殊性对查询处理提出了新的挑战。特别是，数据流可以无限制 地增长，而且查询处理可能需要无界的内存来产生一个准确的回答。如何区分 使用有限内存即可得到准确回答的查询和必须给出近似结果的查询? 实际上， 不知道输入数据流的大小，除非查询涉及的属性的定义域是受限的，否则就不 可能对大多数常见查询( 如涉及连接的查询) 的内存需求设限。这是因为没有 1 4 张珊：数据流中频繁项挖掘算法的研究 定义域限制，必须记住的属性值个数是无界的，因为这些属性值可能会与即将 到来的元组连接。 提供对查询的准确回答可能需要内存量是无界的，因此更现实的解决方案 是提供查询的近似答案。近似的查询回答减轻了内存的需求并有助于处理系统 负荷，因为数据流到来得太快，不能精确处理。另外，即兴查询需要近似的历 史记录来返回查询答案。 综上所述，对流数据挖掘方法的研究是扩大数据挖掘领域的需要，也是对 数据挖掘方法、理论深化与完善的需要。 2 2 流数据挖掘系统 数据流管理系统的主要目的是为数据流上的各种连续查询提供支持。数据 流分析挖掘系统的主要目的为数据流应用提供各种分析和挖掘功能。根据不同 的系统目的可以划分为数据流分析挖掘系统【3 2 3 6 1 和数据流管理系统3 7 训】。下面 列举了几个目前较具代表性的数据流分析挖掘系统4 射。 1 d i a m o n de y e 系统f 3 2 1 代表了早期的数据流分析系统。它是i 刍b u r l 等人为美 国国家航空和宇宙航行局设计开发的。其目的是使得远程计算机和科学家们能 从空间对象的实时图像中提取各种模式。该项目的成功对此后宇宙飞船、。飞行 器以及传感器系统都具有重要的意义。 2 m o b i m i n e 系统【3 4 1 是第一个对无处不在的数据流( u b i q u i t o u sd a t as t r e a m ) 进行数据挖掘的系统。m o b i m i n e 基于p d a 采用客户一服务器( c l i e n v s e r v e r ) 系 统结构对股市中的数据流进行分布式挖掘。在该系统中，服务器实现主要的挖 掘处理工作，并在p d a 和服务器之间通过多次信息交互最终将挖掘分析结果显 示在p d a 的屏幕上。随着p d a 设备计算能力的不断增强，新一代的数据流分析 挖掘系统越来越倾向于将更多的分析和挖掘功能从服务器端移植至i j p d a 端，以 减少整个系统的通讯代价。 3 v e d a s ( v e h i c l ed a