（计算机应用技术专业论文）基于滑动窗口的数据流关联规则挖掘研究.pdf

浙江大学硕士学位论文摘要 摘要 数据流作为信息化时代的产物，广泛应用于社会生活的各个领域。数据流中 蕴含着丰富的知识，特别是海量数据下存在的关联关系，在预测和在线分析系统 中都是重要的决策依据。现有对关联规则挖掘的研究，大多集中于事务模型，鲜 有在独立数据项粒度上的研究。而在特定应用环境中，独立数据之间总是存在一 定的相生关系。由于数据流的实时性特点，用户又往往对最新产生的数据所包含 的信息更感兴趣。 为了实时而全面地获取最近一段时间内数据项之间的关联规则，本文提出了 滑动窗口模型下，基于划分思想的m a r s w ( m i n i n ga s s o c i a t i o nr u l e s0 1 1s l i d i n g w i n d o w ) 算法。m a r s w 算法将滑动窗口分割为一系列子窗口，通过对子窗口的 操作维护整个窗口的概要数据结构。大量的仿真实验表明，m a r s w 算法在给定 的误差范围内，能以有限的空间代价实时挖掘滑动窗口下数据项之间存在的所有 关联规则，并具有较高的效率和优良的可扩展性。 考虑到实际应用环境下数据的多变性和流量的不可控性，关联规则算法需要 借助数据流管理系统提供预处理。由于数据流管理系统尚未形成一致认可的标 准，本文提出了基于多种数据流管理系统的f e d e r a t o r 结构。通过创建内置运算子 或接管系统的输入输出，在统一接口模型下，关联规则挖掘算法可以快速、高效 地融合于数据流管理系统中。 关键词：数据流，关联规则挖掘，滑动窗口，数据流管理系统。 浙江大学硕士学位论文 a b s t r a c t a b s t r a c t a sap r o d u c to ft h ei n f o r m a t i o na g e ，d a t as t r e a mi sw i d e l yu s e di nv a r i o u sf i e l d so f s o c i a ll i f e d a t as t r e a mc o n t a i n saw e a l t ho fk n o w l e d g e p a r t i c u l a r l y , t h ea s s o c i a t i o n r u l e sb e t w e e nm a s so fd a t ai sa l li m p o r t a n tb a s i sf o rd e c i s i o nm a k i n gi np r e d i c t i o na n d o n l i n ea n a l y s i ss y s t e m s m o s te x i s t i n gr e s e a r c h e sa r ef o c u s i n go nt r a n s a c t i o nd a t a m o d e l ；f e wa r em i n i n gt h ea s s o c i a t i o nr u l e sb e t w e e ne l e m e n t so c c u r r i n gi nd a t as t r e a m i ns p e c i a le n v i r o n m e n t s ，t h e r ea r ea l w a y sd e p e n d e n c i e sb e t w e e nt h ed a t a d u et ot h e c h a r a c t e r i s t i c so fr e a l - t i m ed a t a ，p e o p l ea r em o r ei n t e r e s t e di nt h ei n f o r m a t i o no fr e c e n t d a t at h a nt h a to ft h eo l d i no r d e rt om i n i n ga s s o c i a t i o nb e t w e e nt h em o s tr e c e n td a t ae l e m e n t s ，w ep r o p o s e a nm a r s w a l g o r i t h mt or e p o r tt h ea s s o c i a t i o nr u l e su n d e rt h es l i d i n gw i n d o w m o d e l t h ea l g o r i t h ms p l i t st h es l i d i n gw i n d o wi n t oas e r i e so fs u b - w i n d o w s ，m a i n t a i n st h e s y n o p s i sd a t as t r u c t u r eb yt h eo p e r a t i o n so fs u b w i n d o w s t h ee x p e r i m e n t a lr e s u l t s s h o wt h a tt h ep r o p o s e dm e t h o dc a nr e t r i e v ea l lt h ea s s o c i a t i o nr u l e sb e t w e e nl a r g e a m o u n t so fd a t au n d e rt h es l i d i n gw i n d o wa tl i m i t e ds p a c ec o s tw i t h i nt h eg i v e ne r r o r b a n d , a n dh a v eh i g he f f i c i e n c ya n de x c e l l e n ts c a l a b i l i t y t a k i n gi n t o a c c o u n tt h ed a t av a r i a b i l i t ya n df l o w o fn o n - c o n t r o l l a b l e ，t h e a l g o r i t h mn e e dd 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 ) t op r e - p r o c e s st h ed a t a s t r e a m s i n c et h ed s m sh a sn ow i d e l ya c c e p t e ds t a n d a r d ，w ep r o p o s eaf e d e r a t o r s t r u c t u r et os u p p o r tv a r i o u sd s m s s b yc r e a t i n gab u i l t i no p e r a t o ro rt a k i n go v e rt h e i n p u ta n do u t p u t , a s s o c i a t i o nr u l em i n i n ga l g o r i t h mc a nb eq u i c k l yi n t e g r a t e d i n t o d s m su n d e rt h eu n i f i e di n t e r f a c em o d e l k e y w o r d s ：d a t as t r e a m ，a s s o c i a t i o nr u l em i n i n g , s l i d i n gw i n d o w , d a t as t r e a m 浙江大学硕士学位论文图目录 图目录 图1 1 传统数据处理模型和数据流处理模型2 图1 2 基于数据流管理系统的关联规则挖掘示意图7 图2 1s t r e a m s u m m a r y 结构示意图1 4 图2 2s t r e a mr u l e 概要数据结构示意图l7 图3 1 可关联组计算模型示意图2 0 图3 2 概要数据结构的运行时间和空间性能3 l 图3 3n a t i v e 算法运行时间和空间性能3 3 图3 - 4n a t i v e 算法的误报率3 3 图3 5m a r s w 算法运行时间和空间性能。3 4 图3 - 6m a r s w 算法的误报率3 5 图4 1f e d e r a t o rf o rd s m s 3 9 图4 2 统一接口框架模型。4 0 图4 - 3 驱动器的基本操作4l 1 1 i 浙江大学硕士学位论文表目录 表目录 表1 1d b m s 与d s m s 3 i v 浙江大学硕士学位论文第1 章绪论 第l 章绪论 1 1 课题背景 随着信息化的普及，各种数据在大量应用领域里作为可共享、交换和存储的 资源，呈现出爆炸式的增长。同时，数据的传播和更替也变得异常迅速，并往往 以一种连续、潜在无限的形式出现。区别于传统的静态数据，这类新型的动态数 据模型被称之为数据流n 1 。 数据流在大量场景下有实际的应用：网络监控、交通工程、传感器网络【2 】、 射频辨识标签、电话通信、金融应用、网络日志、制造工艺过程等。在这一系列 应用中，通过对产生的数据流进行监控、管理、分类和挖掘，可以掌握数据的整 体信息及数据间可能存在的某些相关性，从而发现数据内部存在的规律，有效提 高对应用的控制和资源优化。 由于对数据操作管理方式的侧重点不同，传统的数据库技术和研究方法很难 直接应用于数据流的管理。例如，在数据流应用中，对数据项的删除、更新操作 很少甚至没有，很多情况下不对数据进行存储，查询处理的结果也往往是基于统 计意义的，并不要求完全精确。而传统数据库理论建立在有限存储的基础上，针 对的是数据集的精确操作，因此很难高效地处理数据流问题。 1 2 数据流概述 1 2 1 数据流模型 在数据流模型中，部分或全部可被操作的输入数据不能随机地从磁盘或内存 中访问，而是以单个或多个连续数据流的形式到达。数据流模型有别于传统关系 数据模型，主要表现在如下方面 1 】： 数据流中的数据项总是实时到达的。 应用系统无法控制数据流或数据流之间数据项到达的顺序。 数据流是潜在无限的。这就意味着，存储全部数据的代价十分昂贵。 浙江大学硕士学位论文第1 章绪论 数据流中的数据项被处理后，或被丢弃，或被存储。这也就是说，数据往 往只有一次处理的机会，再次获取的代价昂贵甚至不可能。 根据时序的不同，数据流模型又可以细分为一系列子模型：界标模型 ( 1 a n d m a r km o d e l ) ，滑动窗口模型( s l i d i n gw i n d o wm o d e l ) 和快照模型( s n a p s h o t m o d e l ) 。界标模型考虑从某个给定的时间点开始到当前时间点内的所有数据；滑 动窗口模型则考虑在一个给定大小的窗口范围内的所有数据，并且窗口会不断向 右滑动；快照模式则考虑在两个给定的时间点之间的所有数据。但不论从哪种模 型来看，对数据流的处理在技术上主要面临以下挑战： 要求时间复杂度低。数据流应用中，往往需要实时响应。当流速较快时， 高时间复杂度的算法将引起数据积累而导致服务质量下降。 要求空间复杂度低。由于数据流规模非常大，而存储空间毕竟有限，所以 算法需要尽可能低的空间复杂度。 误差控制。由于数据流的处理往往仅需要近似结果，因此对结果的误差控 制就非常重要，它是保证结果可信度的重要因素。 1 2 2 数据流处理模型 数据流模型在时间和空间上的要求与传统静态数据模型有较大差别，因此对 数据流的处理也有明显的不同。图1 1 给出了这两类数据的处理模型。 a ) 传统数据处理模型b ) 敷据流处理模型 图l - i 传统数据处理模型和数据流处理模型 传统数据处理模型中，由于所有数据信息都存储在不易失的低速介质中( 磁 盘、磁带等) ，所以用户的查询、变更操作都直接作用于全体数据集上。而对于数 2 浙江大学硕士学位论文第1 章绪论 据流处理模型来说，由于数据流具有实时、高速、海量的特性，无法完整地保存 所有数据信息，因此需要合适的数据流处理算法提取出概要数据结构( s y n o p s i s d a t as t r u c t u r e ) 来表征整个数据流。当然，这部分概要数据结构的规模必须远小于 整个数据流，并且要能够随着数据流的变化而不断更新。显然的，用户对于数据 流的查询、变更操作都将直接作用于当前的概要数据结构。由于概要数据结构往 往可以全部存储在内存等高速存储器中，所以数据处理和响应的速度将明显优于 传统数据处理模型。 1 2 3 数据流管理系统 数据流的一个重要方向是数据流管理系统的研究。鉴于数据流模型与传统数 据模型的差异，数据流管理系统( d s m s ) 与传统的数据库管理系统( d b m s ) 毛e 功能、 执行过程等方面也有较大的差别。表1 1 给出了d b m s 和d s m s 的主要差别。 表1 1d b m s 与d s m s 数据库管理系统( d b m s )数据流管理系统( d s m s ) 持久化的关系 短暂的数据流( 持久化的关系) 一次查询连续查询 随机访问顺序访问 查询处理器和数据库物理设计不可预测的数据特征和访问方式 决定访问计划 根据数据流的实时性、动态性以及数据分布变化等特点，许多学校、研究机 构都在独立从事数据流管理系统的研究。 学校研究方面，主要有斯坦福大学基于关系的通用数据流管理系统s t r e a m 项目，该项目提出了关于数据流的查询语言c q l ( c o n t i n u o u sq u e r yl a n g u a g e ) ； 加州伯克利分校推出了持续查询处理系统t e l e g r a p hc q 3 】项目，该项目建立在 p o s t g r e s q l 的基础上，可以为多种数据流提供自适应处理系统；布朗大学和麻省 理工学院合作提出了基于工作流的a u r o r a 4 1 系统，它的核心是大型的触发器网络， 专门用于处理数据流的监控。 浙江大学硕士学位论文 第1 章绪论 商用领域，较为突出的数据流管理系统有s t r e a m b a s e 、c o r a l 8 、a l e r i 等。 s t r e a m b a s e 在流处理和复杂事件处理( c e p ) 方面具有领先地位，它为高性能的实 时应用提供完整的开发和部署环境。s t r e a m b a s e 还独立提供了s t r e a m c q l 语言， 它和s t r e a m 的c q l 语言类似，都扩展了标准的s q l 语言，因此同时支持结构 化和非结构化的数据。c o r a l 8 也提供流处理和c e p 的解决方案，它的特色是提供 可配置的企业级聚类和保证应用的高可靠性。c o r a l 8 同样提供一类数据流处理语 言c c l ( c o n t i n u o u sc o m p u t a t i o nl a n g u a g e ) ，它支持如窗口操作、事件模式匹配等。 a l e r i 相对来说更侧重于c e p 技术，它的主要特色是提供丰富的可扩展输入输出 接口，包括s o c k e t 、j m s 、d a t a b a s e 、f i l e 等。当然，所有这些数据流管理系统都 对外提供了丰富的a p i 。 1 2 4 数据流挖掘 数据流知识挖掘是数据流研究的又一个重要方向。独立数据自身有一定的信 息价值，而当数据群集时则会产生额外有价值的信息。例如，在海量数据集中， 通过统计发掘频繁出现的数据项，分析其内在的原因，可以在未来解决方案中对 其进行针对性处理，从而提高应用的效率。 传统的数据挖掘往往基于一定的假设：a 1 数据集是静态存储的。这就是说， 数据挖掘的对象从操作开始后便不再发生变更。若存储的数据集允许发生变更， 则挖掘需要在原始数据集的副本上进行操作。b 1 可以对数据集进行随机和多次访 问。由于数据集存储在不易失的介质中，所以允许算法对数据集进行多次访问。 当然，应尽量减少访问的次数。 但是，基于数据流的挖掘不能满足这样的假设。数据流潜在无限和动态变化 的特点，不允许对数据流进行全部存储。因此在数据流的挖掘算法中，必须支持 对数据流的一次访问。同时，基于数据流的挖掘需要随时间连续不断地更新己挖 掘到的结果集，所以对任意数据项的处理时间都严格受限。数据流挖掘与传统数 据挖掘的另一个重要区别在于：数据流挖掘由于不保留原始数据集，仅能提供近 似的结果：而传统的数据挖掘则可以在考虑时间效率的基础上，提供近似或者精 4 浙江大学硕士学位论文 第1 章绪论 确的结果。 数据流挖掘的研究主要有基于数据流的查询( 频繁项、相异数据项个数等) 、 关联规则挖掘、分类和聚类等技术。其中，关联规则挖掘在选择性营销、决策分 析和业务管理上有明显的指导意义，因而受到研究者的广泛关注。 1 3 数据流关联规则挖掘 a g r a w a l 等最早提出了关联规则的定义同。在关联规则x 斗y 中，如果有s 的事务包含数据项x u y ，并且s 大于某个用户给定的矽值，则称j 为关联规则的 支持度；如果有c 包含数据项x 的事务也包含数据项y ，则称c 为关联规则的置 信度。关联规则挖掘最成功的应用是“尿布与啤酒 的故事：通过分析挖掘消费 者的购物习惯，超市将尿布和啤酒摆放在一起销售竟使得销量双双增加。 按照不同的标准，关联规则挖掘可以做如下分类：1 ) 根据数据类型的不同， 分为布尔型和数值型。布尔型的关联规则主要应用于离散数据域上，表征数据类 别等信息；而数值型的关联规则重点突出数据的数量关系。2 ) 根据数据抽象层次 的不同，分为单层关联规则和多层关联规则。在单层关联规则中，并不考虑数据 在现实中的层次关系；而在多层关联规则中，数据具有一定的抽象层次，处于同 一层次的不同数据可以应用于相同的关联规则。3 ) 根据数据的维度不同，可以分 为单维和多维关联规则。在单维关联规则中，仅仅考虑的是数据的一个维度；而 在多维中，数据的多个维度参与关联规则的构成。 传统关联规则挖掘的研究是基于有限存储的数据集，而数据流关联规则挖掘 研究是基于高速变化的无限数据集。当前，数据流关联规则挖掘研究主要集中于 事务数据类型，在数据流界标模型、滑动窗口模型和时间衰减模型下的讨论都取 得了很多优秀成果。这些研究方法主要借鉴于传统关联规则挖掘的思想，通过构 造合适的概要数据结构，在仅支持一次访问的情况下维护事务内部的频繁项集 ( f r e q u e n ti t e m s e t s ) ，进而根据支持度和置信度的约定得到关联规则。 由于数据流的来源广泛，在很多应用中其实并不存在明显的事务概念，如环 境监测中的各项指标、互联网上的点击流等。这类数据之间的关联关系同样可以 s 浙江大学硕士学位论文第l 章绪论 为应用系统提供分析、预测等重要信息。举例来说，在互联网上，成千上万用户 的点击汇聚成数据流。如果近段时间内某个u r l 地址总是相邻另一个u r l 地址 出现，则它们之间可然存在一定的相关性( 超链接等) 。挖掘这类信息有助于实时 发现网站盗链、广告欺骗等。当前这方面的研究很少，而基于事务模型的方法又 不能直接适用，因此独立数据项之间的关联规则挖掘研究非常紧迫。 1 4 本文主要研究内容 数据流中蕴含着丰富的知识，如某条交通线路的拥堵情况，某些股票的同步 涨落分析等，都有助于引导人们的科学决策，从而带来资源的优化和巨大的经济 效益。数据流信息又具有明显的时效性，近期时间内的数据信息往往是人们所真 正关心的。但是数据流高速动态变化以及时空无限性的特点，导致不可能简单地 移植传统数据库技术。 本文在数据流滑动窗口子模型下，重点研究数据流中最近一段时间内相邻数 据项间的关联规则挖掘。在给出问题的形式化定义后，本文将首先提出n a t i v e 算 法。n a t i v e 算法直观地模拟滑动窗口的行为，单独对数据流中的每个数据项进行 处理。它的缺点是必须依赖整个窗口数据序列能够存储在内存中的假设。由于在 真实应用环境中，滑动窗口往往非常庞大，为避免内存的限制，在n a t i v e 算法的 基础上，又提出了m a r s w ( m i n i n ga s s o c i a t i o nr u l e so i ls l i d i n gw i n d o w ) 算法。 眦s w 算法基于数据流频繁项挖掘框架，引入划分的思想，考虑将滑动窗口分 割为若干子窗口，通过对子窗口的操作维护整体概要数据结构。本文将对m a r s w 算法的误差性质以及时间、空间性能进行分析，并通过大量实验予以证明。 由于关联规则挖掘算法并未对数据的多变性和流量的不可控制性进行处理， 算法还缺乏实际应用的能力。考虑到数据流管理系统在数据流处理和流量控制上 已经取得的成果，并提供有丰富的编程接口，将算法融合于数据流管理系统中不 失为一种简单而行之有效的方案。但是，当前大量存在的数据流管理系统并不能 互相兼容。本文将讨论一种基于数据流管理系统的关联规则挖掘框架，如图1 - 2 所示。在此框架下，通过f e d e r a t o r 的方式实现对数据流管理系统的上层封装，从 6 浙江大学硕士学位论文第1 章绪论 而屏蔽底层数据流管理系统实现上的差异。 1 5 本文结构 图l - 2 基于数据流管理系统的关联规则挖掘示意图 第2 章回顾数据流挖掘领域相关的算法和研究进展。 第3 章提出一种新的基于滑动窗口模型的数据流关联规则挖掘算法。首先介 绍问题产生的应用背景，并给出问题的形式化定义。接着，根据滑动窗口模型的 特点，提出在内存可存储窗口数据序列假设下的n a t i v e 算法。在n a t i v e 算法的基 础上，去除内存的限制，进一步提出基于划分策略的m a r s w 算法的整体框架和 实现流程，并给出算法的误差分析和证明。最后，给出算法的各项对比实验，并 对实验数据进行分析，证明算法的高效、可靠性。 第4 章研究基于数据流管理系统的关联规则挖掘。首先介绍关联规则挖掘算 法和数据流管理系统之间融合的优势和可能性，然后给出两种可实现的方案，并 分析各自的特点。最后，为支持多种不同数据流管理系统下的关联规则挖掘，提 出了f e d e r a t o r 结构和具体的实现方案。 第5 章总结本文的工作，并对今后的研究方向进行展望。 浙江大学硕士学位论文第2 章数据流挖掘相关研究 第2 章数据流挖掘相关研究 2 1 数据流挖掘的基本思想及主要方法 从数据流的处理模型来看，用户对数据流的查询、更新操作都直接应用于概 要数据结构，而不是整个数据流。因此，数据流算法的核心思想就是如何构造合 适的概要数据结构【6 】，使得概要数据结构能够反映当前整个数据流的情况，并能 够支持快速查询、更新操作。 一般来说，当新数据项进入数据流时，更新概要数据结构必须在一二步操作 内完成。而在某些环境下，由数据项过期引起的概要数据结构变更也必须限制在 几步简单操作内完成。由于内存等存储空间有限，为保证概要数据结构能够完整 地被装载，设当前的数据流长度为，理想概要数据结构所占空间不应超过 p o b , o o g 忉l 。 概要数据结构的设计主要有以下几类方法：抽样( s 姗p l i n g ) 方法、直方图 ( h i s t o g r a m ) 方法、小波( w a v e l e t s ) 方法和哈希( h a s h ) 方法。 2 1 1 抽样方法 抽样在自然科学和社会科学的各个领域都有非常重要的应用。抽样的思想认 为，如果数据集的较小样本能够反映整个数据集的本质特征，那么该样本就可以 作为数据集的一个梗概。抽样是数据流中提取概要数据结构最简单的方式，而其 它复杂的概要数据结构也可以在抽样的基础上产生。 抽样可以分为两大类：概率抽样( p r o b a b i l i t ys a m p l i n g )非概率抽样 ( n o n p r o b a b i l i t ys a m p l i n g ) 。概率抽样是指数据集的每一个数据项在样本中被选中 的概率矽 0 ，并且p 的值可以被精确确定。而非概率抽样是指数据集中的某些数 据项被选中的概率p = 0 ，或者p 不能被精确确定。 概率抽样的优点在于可以计算抽样的误差，准确反映样本与数据集的相似 度。概率抽样的方法主要有：简单随机抽样( s i m p l er a n d o ms a m p l i r l g ) 、系统抽样 3 浙江大学硕士学位论文第2 章数据流挖掘相关研究 ( s y s t e m a t i cs a m p l i n g ) 和分层抽样( s t r a t i f i e ds a m p l i n g ) 等。在数据流中，主要采用的 是概率抽样及其变种。v i t t e r 提出了水库抽样( r e s e r v o i rs 踟p l i n g ) 【7 】方法：假定样 本容量为疗，将最初的刀个数据项加入样本。对于第t ( t 功个数据项，它被选中 的概率p = l 。若数据项被选中，则随机从样本中替换一个己存在的数据项， t + l 那么当前样本即为前f 个数据项的一个抽样。水库抽样在未知数据集大小的情 况下，仅需一遍扫描，非常适用于数据流模型。g i b b o n s 等提出了精确抽样( c o n c i s e s a m p l i n g ) t 8 】方法：样本中出现超过一次的数据项都以 ，需要构造分段常数函数v ( ，) 来 近似数据的分布，从而使得整个数据集的方差( ，一1 ，( f ) ) 2 最小化。 假定数据集的大小为，分段常数函数将其划分为召个区间。在静态数据模 型中，j a g a d i s h 等提出了o ( n 2 聊时间复杂度的动态规划算法【1 o 】。g u h a 等将该算 9 浙江大学硕士学位论文第2 章数据流挖掘相关研究 法改进为l + 占近似度、o ( n + ( b 8 1l o g 忉3 ) 的时间复杂度【1 。而在数据流模型中， g u h a 等在限定数据流排序的基础上，提出了伏口2l o g 忉空间复杂度和 o ( n b 2l o g n ) 时间复杂度的1 + 8 近似算法【1 2 】。g i l b e r t 等人则移除了对数据流排序 的约束，它将每一个数据项视为对长度为的向量的更新，并将概要数据结构限 制在即纱( e l o g n , 8 1 ) 的空间复杂度【1 3 】。 2 1 2 2 等宽直方图 等宽直方图的思想是，通过将整个数据域分割成一系列的数值桶，使得数据 集均匀地分布在这些数值桶中。在传统数据库中，等宽直方图被应用于优化选择 性估算。在数据流上，g r e e n w a l d 等提出了一种在线计算s 近似的分位数概要算 法1 9 。该算法的最差空间复杂度为0 ( 8 。l o g ( ) ，它改进了m a n k u 提出的 0 ( 2 1l 0 9 2 ( ) 空间复杂度算法【1 4 1 。此外，不同于先前的确定性算法，该算法不 需要有对输入流长度的先验知识。 2 1 2 3 端偏置直方图 端偏置直方图的想法是，为出现频率超过给定阈值的数据项维护精确计数， 而对其余数据以均匀分布的方式近似维护其计数。端偏置直方图用于对某个属性 上聚合值超过给定阈值的查询，类似于冰山查询( i c e b e r gq u e r y ) p s i 。如搜索引擎 也许对那些出现频率超过l 的搜索词感兴趣。m a n k u 提出了针对冰山查询和频 繁计数的随机和确定性算法【1 6 】，其主要思想是通过自适应的抽样保证超过一定频 率的数据项必然包含在样本中。确定性算法l o s s yc o u n t i n g 的空间复杂度为 0 ( 8 l o g ( 洲3 ) ，其概要数据结构中所有频繁数据项的计数误差不超过州。 2 1 3 小波方法 小波方法为分层分解提供了数学化的工具，并在信号和图像处理上有着大量 成功的应用。近些年的研究证明，小波方法也适用于选择性估算、大规模关系表 的近似查询处理和数据流等应用。小波方法的思想是通过分解输入，将其变换为 1 0 浙江大学硕士学位论文第2 章数据流挖掘相关研究 一系列小波系数，选择其中的部分构造概要数据结构。g i l b e r t 等给出了在单一或 多个数据流上进行点、区域和聚合查询的算法【1 7 1 。算法维护由b 个小波系数组成 的梗概和个小波基础向量，空间复杂度为o ( b + l o g 加。当新数据项到来时， 遍历个小波基础向量后对梗概进行更新，时间复杂度为g l ( n l o g 加。 2 1 4 哈希方法 单一的哈希算法在使用较少空间时，容易引起数据冲突而导致性能下降；若 增大空间则易产生空间浪费。哈希方法是指定义一组相互独立的哈希函数，将数 据映射到一定范围内。通过多个哈希函数的组合，可以在较小的空间内尽可能地 避免冲突。基于哈希方法的概要数据结构设计主要有：b l o o mf i l t e r 方法n 明、 s k e t c h 方法等。 2 1 4 1b l o o mf i l t e r b l o o mf i l t e r 方法早在1 9 7 0 年就被提出，主要应用于网络、数据库等领域。 在b l o o mf i l t e r 算法中，给定一个长度为m 的位向量和h 个相互独立的哈希函数。 初始时，向量的所有位被设置为0 。对于数据集中的任意数据项，使其通过计算 哈希函数映射到h 个【0 m 1 1 2 _ 间的数值，同时将向量的相应比特位设置为l 。 显然的，若这h 个数值所对应的向量位中至少有一个为0 ，则该数据项必然在之 前从未出现过。反之，则不能判断数据项是否已经出现，因为这h 个位置可能已 被先前某些数据项设置。b l o o mf i l t e r 算法在判定数据项重复时会存在误报( f a l s e p o s i t i v e ) ，但不会有漏报( f a l s en e g a t i v e ) ，并且随着位向量内存的增加和更科学的 哈希函数组合，误报率将下降到很小。c o h e n 等在b l o o mf i l t e r 模型的基础上， 通过采用计数器替换比特位的方法还可以有效地估计数据项出现的频率值【1 9 1 。 2 1 4 2s k e t c h s k e t c h 方法最早由a l o n 等人提出乜，随后就一直被广泛应用。s k e t c h 方法 利用哈希函数为数据集建立一个较小的数据概要，主要针对数据集上的“距离 查询。 浙江大学硕士学位论文第2 章数据流挖掘相关研究 设d - i ，2 ，d ，s = 五，恐，x n ，其中薯d 。令爿 j l x ，- - i ) i ，即职为 集合s 中包含数值f 的项数。对于任意k 0 ，数据集s 的七阶矩定义为 e = 。硝。特别的，e = n 姒，镌。显然，磊是集合s 中不同数据项的个数， e 是集合s 的长度，e 是集合s 自连接的大小，是集合s 中出现最频繁数据项 的次数。f l a j o l e t 等设计了o o o g n ) 空间复杂度的近似算法【2 1 】计算磊，r o b e r 给出 了o ( 1 0 9 l o g n ) 空间复杂度的近似算法【2 2 】计算互。a l o n 等证明了近似计算最的空 间复杂度下阶为d ( n h 膻1 0 9 n ：，并提出了使用线形哈希函数、空间复杂度为 o ( 1 0 9 d 近似计算磊以及d ( 1 0 9 d + 1 0 9 加空间复杂度近似计算五的算法【2 0 1 。算法 将d 中的数据项f 通过哈希函数均匀地映射到值弓 - 1 ，+ l 。定义随机变量 x = m i z t ，则x 2 即为五的近似值。此外，通过设置多组相互独立的哈希函数 及增加随机变量，并在所有估计值中取平均，可以有效地减少误差。 2 2 频繁项挖掘 数据流带来丰富信息的同时，也淹没了其中真正有价值的数据信息，如数据 流中频繁出现的数据项。设当前数据流s 的长度为，若数据项e 出现的次数疋超 过某个预先给定的值州( 矽( 0 ，1 ) ) ，则称e 为频繁项。频繁项往往能够代表数据流 的部分特性，较为典型的应用如数据流上的t o p k 查询。 频繁项挖掘是许多数据流挖掘算法的基础，当前有很多重要的研究成果。频 繁项挖掘算法大致可以分为基于计数和基于s k e t c h 两类。基于计数的算法为被监 督的每个数据项独立维护计数器。当数据项e 出现在数据流中时，若p 处于被监 督状态，则更新e 的计数器；反之，则丢弃e 或采用相关算法的处理手段。这类 算法主要有s t i c k ys a m p l i n g 16 】、l o s s yc o u n t i n g 、s p a c e s a v i n g 2 3 】等。基于s k e t c h 的算法采用位图的方式对所有数据进行监督，往往通过一组哈希函数将数据项映 射到一组计数器上。这类算法相比基于计数的算法在误差控制上略显不严格，主 要有h c o u n t l 2 4 ，g r o u p t e s t 2 5 等。 浙江大学硕士学位论文第2 章数据流挖掘相关研究 2 2 1l o s s yc o u n t i n g 算法 l o s s yc o u n t i n g 是一类确定性算法，算法接受两个用户指定参数：支持度 s ( o ，1 ) ，误差占( o ，1 ) ，并且s j 。假定为当前数据流的长度，则1 ) 所有出 现次数超过s n 的数据项都被输出，即没有漏报；2 ) 出现次数少于o 一6 ) n 的数据 项都不会被输出；3 1 数据项出现次数的估计值最多比实际出现次数少州。 广1 算法中，数据流在概念上被分割成一系列均匀的桶，桶的宽度w ml 二i 。每个 i si 桶都有唯一的标号，从l 开始计数。设当前桶的标号为屯，则6 。，= i 苦l 。 对于数据项e ，记当前数据流中实际己出现的次数为，。算法维护概要数据结构 d ，它是一系列元组( 巳f ，a ) 的集合，其中e 是数据项的值，厂是数据项e 出现次 数的估计值，是与z 之间的最大误差值。 初始时，概要数据结构d 被置为空。对于随后而来的数据流中的每一个数据 项e ，如果e 存在于d 中，则将数据项e 的计数厂( p ) 自增。若e 不存在于d 中，则 在d 中为e 新建一个入口，其中厂( g ) = 1 ，( p ) = 屯广l 。若当前桶中的数据项已 经到达桶的边界，则对于d 中的每一个入口( p ，f ，a ) ，如果满足厂+ 屯，就 将该入口从d 中移除。当用户发出查询请求时，只需要遍历d 的所有入口 ( p ，f ，) ，输出所有满足f o e ) n 的数据项p 即可。 不难证明，l o s s yc o u n t i n g 算法中概要数据结构d 有如下性质：1 ) 如果数据项 p 不在d 中出现，则有六f a r ；2 ) 如果( p ，六a ) e d ，则z s n ，则输出其所有儿子节点即可。 1 4 浙江大学硕士学位论文 第2 章数据流挖掘相关研究 s p a c e - s a v i n g 算法有如下性质：1 ) 对于用户给定的误差值占，若令聊= f ， 则所有实际出现次数z 州的数据项p 必然出现在s t r e a m s u m m a r y 中，其中n 是当前数据流的长度；2 ) s t r e a m s u m m a r y 中所有数据项的计数估计值大于等于实 际出现的次数，但误差不超过e a r 。 2 2 3h c o u n t 算法 h c o u n t 算法是基于s k e t c h 技术的。它使用哈希表研册】【剜和h 个哈希函数。 每一个哈希函数都将整数【1 m 】均匀、独立地映射到【o 聊1 】上。常用的一 组哈希函数如置( 七) = ( ( q k + b , ) m o dd r o o dm ，l f 厅，其中q 和包是随机数，尸 是一个很大的素数。对于任意数据项七，它有一系列关联的计数器 。当遇到数据项k 时，这些计数器同时 增加或减少。查询时，令k 从1 到m 遍历，g ：m i n i 1 ) 步，a ) 由厶叫自连接生成g ；b ) 然后扫描整个数据库，对于每一个事务， 若g 中某个k 元数据项包含于该事务，则该k 元数据项的计数自增1 。c ) 令厶等 于g 中所有计数超过最小支持度的k 元数据项的集合。当厶d = 时，算法结束， 所求的频繁项集即为u 厶。 ， a p r i o r i 算法的缺点在于，由厶一。自连接产生的候选集g 规模过大，并且在验 证候选集的过程中又需要遍历整个数据库，非常耗时。a p r i o r i t i d 算法提出了对 候选集g 验证的优化算法，避免了再次对数据库的访问。设g 为 l ，对应于事务t ， 1 6 浙江大学硕士学位论文 第2 章数据流挖掘相关研究 q - - i t d 。若事务t 不包含任何候选的k 元数 据项，则q 中将不包含该事务的入口。对于g q 的每一个入口e ( 数据库中某个事 务) ，若c g ，( c c 【明) e s e t o f i t e m si i ( c - c k - 1 ) e s e t o fi t e m s ，则c 必然 包含于事务p t i d 中。令c f 为这些候选项的集合，当e ，就在百中加入入口 。算法的其余部分与a p r i o r i 相同。 由于a p f i o r i 算法需要对数据进行多次访问，所以并不适用于数据流模型。但 是，a p r i o r i 算法的思想可以被借鉴应用于数据流的算法中。 2 3 2s t r e a m _ r u l e 算法 s t r e a m r u l e 是数据流界标模型下，数据项间前序和后序关联规则挖掘算法。 s t r e a m r u l e 算法的思想是首先利用s p a c e s a v i n g 算法在数据流中挖掘频繁项。与 此同时，对于当前已经挖掘到的频繁项x ，针对所有可以与其构成前序或后序关 系的数据项，再次独立采用s p a c e s