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

独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得重麽自g 电态堂或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意。 一魏投巾蛲撕期：妒7 一帅 学位论文版权使用授权书 本学位论文作者完全了解重麽邮电太堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权重麽囱e 电太堂可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 表一降 导师签名： 签字日期川7 年f 月杪日 签字日期：矽哆年r 肿咱 i f r 重庆邮电大学硕士论文 摘要 摘要 数据挖掘技术是解决数据丰富而知识贫乏的有效途径，当属信息科学领域的 前沿研究课题之一，有关研究和应用极大提高了决策支持的能力，它已被公认为 是数据库研究中一个极富应用前景的领域。 近年来，关联规则挖掘研究已经成为数据挖掘中的一个热点，它主要是发现 事务数据库中不同事务之间的联系。挖掘事务模式中的频繁项集是关联规则挖掘 中的关键问题，现在多数对关联规则算法的改进都是对挖掘频繁项集的改进。关 联规则被广泛应用于智能交通、电子商务、传感网络等应用领域。然而随着这些 领域的应用，出现了一种新的数据模型数据流。这些数据的信息量是巨大而 且内容是快速变化的。传统的关联规则挖掘算法需要多次扫描数据库和占用较多 的空间，不适合数据流的挖掘。因此，在数据流的环境下挖掘频繁项集变成了一 个具有挑战性的问题。 针对此问题，在已有数据流频繁模式挖掘算法f p d s l 5 c 订i n i n gf r e q u e n tp a t t 锄 i i ld a t as 仃e 舭i s ) 的基础上，本文改进得到了一种基于滑动窗口的数据流频繁模式挖 掘f p s d s ( m i i l i n gf r c q u e n tp a n 锄b 弱c do ns l i d m g w i i l d o wi i ld a t as 仃- e 锄s ) 算法， 并由产生的频繁模式得出关联规则。f p s d s 算法利用滑动窗口对数据流进行处理， 能够快速地挖掘最近的关联规则：采用字典树存储频繁项集，避免f p d s 算法中 采用基于频数序f p 讹e 而扫描两次，有效提高了算法的性能；考虑到增量式关联 规则中，增量数据加入到原数据的过程类似于滑动窗口中新数据流入的过程，把 增量式关联规则中的剪枝思想运用到滑动窗口中。 f p s d s 算法在几组数据集上进行了实验，对算法的正确性、稳定性进行了测 试，并与原有的f p d s 算法相比较。实验证明，f p s d s 算法具有较好的稳定性， 且时间复杂度也较低于f p d s 算法。 关键字：关联规则，数据流，滑动窗口，字典树，剪枝策略 a b s t r a c t d a t am i n i n gt e c h n o l o g yi s 趾e m c i e n tp a mo fm i n i n gk n o w l e d g ei np l e n t i 如l d a t a i t i so n eo fi n f o m a t i o ns c i e n c ed o m 越n s t h e r e l a t e dr e s e a r c h 趴dt l l e 印p l l c a t l o n i m p r o v e dt h es u p p o nd e c i s i o na b i l i t ) ，e n 0 肌o u s l y i th a s b e e nr e c o 印i z e d 鹪an l c e 叩p l i c a t i o np r o s p e c td o m a i ni nt h ed a t a b 嬲er e s e a r c h i n c e n ty e a r s ， 嬲s o c i a t i o nr u l e sm i n i n gs t u d yh 嬲b e c o m e ah o ts p o t n d i s c o v e r i e st h er e l a t i o n s h i pi nt l l e 仃 m s a c t i o nd 砌b a s e m i i l i n g 丘e q u e n ti t e m s e t s l st h e k e vi nt l l e弱s o c i a t i o nm l e sm i n i n g a tp r e s e n t ，m a i ：i y i m p r o v e da l g o n m m s m 勰s o c i a t i o nm l e sa r ei m p r o v i n gi nm i i l i n g 行e q u e n ti t e m s e t s a s s o c i a t i o nr u i e s h a v eb e e n 诵d e l v 、l s e di ni t s ，e c o 删n e r c e ，s e n s o rn e t 、o r ka n ds oo n w i t l lt l l e 印p l i c a t i o n ，d a t a s t r e 锄m o d e la p p e a r s d a t as 仃e 锄舭h u g e ，锄dm e 锄。吡o f i n f b r i l l a t l o nl sr a p l d l y c h a n 西n g b u tt l l et r a d i t i o n a la s s o c i a t i o nm l e sa l g o r i m m ss c 肌t l l ed a t a b 嬲em 锄y t l m e s 觚do c c u p yal a r g e 锄。眦to fs p a c e ，s oi ti s 眦丘tt 0m i n ei n 恤d a t a 妣锄m 眦n g f 沁q u e n ti t e m s e t sb e c o m e sac h a l l e n g ei nt l l ed a t as t r e 锄e n v i r 0 i l i i l e n t t bo v e r c o m em e s ep r o b l e m s ，an e wa l g o r i t h mw h i c hb a s e do nm i n i n gf r e q u e n t p a n e m si i ld a t as t r e 锄s ( f p d s ) ，n 锄e dm i n i n gf r e q u e n t pa ：呛mb 嬲e d 伽 s l i d i n g w i n d o w i nd a t as t r e a m s ( f p s d s ) ， i s p r o p o s e d t | l i sa l g o r i t i l i i l w m c h p r o c e s s e sd a t as 乜e a mb ys l i d i n g - 、i n d o wi sa b l et 0g e t 硒s o c i a t i o n r u l e sm l m n gr e c e n t l y a tt h es 锄et i m e ，m e 邯eo fl e x i c o 铲印| l i c 仃e es t o r i n g 丘e q u e n t i t e m s e t sa v o i d s s c a 胁i n gt i 觚s a c t i o nd a 讪硒et w 0t i m e sa 1 1 de 脏c t i v e l yi m p r o v e s t l l ep e r f o 肌a i l c eo t t h ea l g o r i t h m i i lt l l ei n c r e m e n t m 弱s o c i a t i o nm l e s ，t a k i n gi n t oa c c o u n t t l l a tt l l ep r o c e s s o fi n c r e m e n t a ld a t aa d d e dt ot i l eo r i g i n a ld a t ai ss i m i l 盯t 0t l l e i n n o wo fr 忙wd a t ai n s l i d i n g 、i n d o w m ep n m i n g o fl e x i c o g r a p h i ct r e ei su s e d i nm a j l yd a t as e t s ，f p s d sa l g o m l l t lt e s t s 恤c o r r e c 恤e s s 锄d 渤b l i 啊o tt n e a l g o r i n u n c o m p a r i n gw i m 妣f p d sa 1 9 0 棚m ，f p s d s 计i i c h i s 肌e 虢c t i v e 锚s o c i a t i o nm l e sm i n i n ga 1 9 0 r i t f o rd a t as t r e 锄h a sg o o ds 讪i l i t ya n d h i g l le m c i e n c y a tl 硒t f p s d si st e s t e di nt r a m ca c c i d e n td a t a b a s e k e yw o r d s ：弱s o c i a t i o nm l e s ，d a t as 仃e 锄s ，s l i d i n g 。、 ，i n d o w l e x i c o 掣印h i c 仃c e ， p n m m gs t r a t e g y -nrthp 重庆邮电大学硕士论文 目录 目录 摘要i a b s t r a c t ：i i 第一章绪论1 1 1 研究背景1 1 2 研究现状2 1 3 研究内容。4 1 4 本文结构5 第二章数据流分析6 2 1 数据流及其特点6 2 2 数据流模型及划分7 2 2 1 数据流模型的划分7 2 2 2 基于滑动窗口模型的方法8 2 2 3 数据流模型与传统数据模型的模型的区别l o 2 3 数据流挖掘技术l l 2 4 本章小结13 第三章关联规则挖掘。1 4 3 1 关联规则挖掘概述1 4 3 2 数据流的关联规则算法1 7 3 2 1l o s s yc o u n t i n g 算法1 7 3 2 2f p s t r e 锄算法18 3 2 3f p d s 算法2 l 3 3 本章小结2 3 第四章基于滑动窗口的数据流关联规则算法2 4 4 1 算法思路2 4 4 2 算法描述2 4 4 2 1 概要数据结构2 5 4 2 2 频繁项集的生成2 8 4 2 3 优化策略2 9 4 2 4 滑动窗口的更新3l 4 2 5f p s d s 算法3 2 4 3 算法分析3 3 4 3 1 时间复杂度分析3 3 4 3 2 空间复杂度分析3 4 4 4 本章小结3 5 第五章实验分析3 6 5 1 实验环境与数据集3 6 5 2 算法正确性测试3 7 5 3 实验结果及对比3 9 h i 重庆邮电大学硕士论文 目录 5 3 1 实验结果3 9 5 3 2 性能对比4 l 5 4 应用实例4 l 5 5 本章小结4 2 第六章结论及未来工作4 3 6 1 结论：4 3 6 2 未来工作4 3 致谢4 5 攻硕期间从事的科研工作及取得的研究成果4 6 参考文献4 7 i v 重庆邮电大学硕士论文 第一章绪论 1 1 研究背景 第一章绪论 自2 0 世纪7 0 年代以来，数据库技术得到了迅速发展和广泛应用，传统数据库 获得了巨大的成功。然而，随着数据库技术的迅速发展和广泛应用。一方面，数 据建模变得形式多样，从层次数据库、网状数据库、关系数据库、对象数据库， 直到关系对象数据库等等；另一方面，数据规模也越来越大，技术的进步使得系 统能够自动产生高细节数据并且具有持续的数据更新能力。这种能力在市场分析、 智能交通、传感器网络等行业或应用领域中已经得到极大的体现。例如：w 甜- m a n 公司每天要处理二千万个事务；美国航天局1 9 9 9 年发射的地球观测系统每小时要 产生5 0 g b 的图像数据等。有些科学数据的采集，特别是一些专用的网络系统正在 提供大量的不间断的数据：人造卫星提供的高分辨率地球测量数据；来自雷达的 大气数据；在光学、红外、雷达波长方面连续的大量天文测量数据；大气辐射测 量数据等等。这些数据非常庞大，因此尽管传统数据库获得了巨大的成功，但是 这个层次的数据对于数据的管理、分析和挖掘来说都带来一些有价值的新问题和 挑战。 这种新类型的数据应用使人们逐渐认识到：数据的模型不是建立在一种持续 稳定的关系上而是建立在短暂的数据流( d a t as t r e 锄) 上。这种称为数据流的应用模 型广泛出现在众多应用领域，例如金融市场、网络监控、电讯数据管理、传感器 网络等。这类数据的共同特点是不断地产生、在时间维度上严格有序、其数值不 断地变化，而且，这些数据一般都规模庞大、增长迅速。利用传统的数据库技术 管理这种数据，需要将数据全部保存在物理介质中，然后通过提交数据操纵语言 ( d a _ t am a n i p u l a t i o nl 锄g u a g e ，简称d m l ) 访问物理介质来获取查询结果。但是，由 于数据流数据源源不断，在有限的存储空间中无法保存数据流的全部数据，而且， 数据流应用对查询处理往往有着很高的实时性要求，这也决定了数据不能保存下 来进行处理。因此，已有的数据库技术无法对数据流数据进行有效地管理，必须 进行数据流管理新技术的研究【l 一钉。自2 0 0 0 年以来，数据流管理技术已经引起了 数据库界的广泛关注。许多著名的研究机构和大学都开始了这方面的研究，提出 了一系列的理论、方法和技术，有力地推动了数据库技术的发展。目前的研究工 作主要包括两个方面：数据流管理系统和数据流挖掘算法。前者侧重于数据流管 理系统的开发和相关技术的实现，如数据流的连续查询、内存管理和系统调度等， 重庆邮电大学硕士论文第一章绪论 已经有许多研究机构进行了研究，并构建出一些系统，如：s t r e a m 【i j ，a u r o r a l z 】 等：后者侧重于数据流的在线分析，从聚类、分类、关联规则的挖掘以及可视化 方面都做了大量的工作，如u i u c 的m a i d ( m i n i n ga l 姗i n gi n c i d e n t sf r o m d a t a s t r e 锄s ) 【3 】，这是一个集查询、聚类、分类、频繁项挖掘、处理结果可视化为一体 的数据流挖掘系统。 关联规则挖掘( a s s o c i a t i o nr u l e sm i n i n g ) 作为数据挖掘研究领域的重要分支， 是目前最为重要和应用最广泛的数据挖掘方法之一。最早是由a g r a w a l 等人提出 的。最初提出的动机是针对购物篮分析问题提出的，其目的是为了发现交易数据 库中不同商品之间的联系规则。通过对交易数据库中数据的智能分析，可以获得 有关顾客购买模式的一般性规则。这些规则刻画了顾客购买行为模式，可以用来 指导商家科学地安排进货、库存以及货架设计等。它的一个典型例子就是“9 0 的 客户在购买面包的同时也会购买牛奶”，其直接意义为顾客在购买某些商品的时候 有多大的倾向会购买另外一些商品。目前，关联规则挖掘技术的应用广泛，除了 市场分析、保险业务和电子商务等商业领域之外，人们又把它拓展应用到隐私保 护、交通数据流挖掘、遥感影像等方面，体现出了巨大的发展潜力和应用前景。 随着应用领域的不断扩大，继续开展关联规则挖掘的研究具有重要的理论意义和 实际价值，是一种有益尝试。 1 2 研究现状 a g r a w a l 等人早在1 9 9 3 年就提出了如何在大型的数据库中挖掘关联规则。在 过去十多年中，这个问题已经被广泛地研究和应用。大部分挖掘关联规则的算法 能够挖掘频繁项集的完全集合，例如：a p r i o r i 【5 。，f p g r o w t l l i 引，h - m i n e i7 j 和o p i 引。 随着关联规则研究的进一步深入，频繁闭项集和最大频繁项集的概念被相继提出。 然而他们的研究目的都是挖掘一个频繁项集的完全集合的简洁的表达。挖掘闭项 集和最大项集经典算法有a c l o s e 【9 】，c l o s e t 【1 们，c h a 砌“11 】和m a f i a 【1 2 】等等。 由于应用中的数据库都是极其庞大而且是经常更新变化的，因此研究增量式 的关联规则逐渐成为一个热点。增量式关联规则算法高效的关键在于尽可能利用 已有的挖掘结果来生成较少的候选项目集或较少次地扫描数据库。c h e u i l g 等人最 早提出了f u p 【1 3 】算法及f u p 2 【1 4 】算法，他们考虑的问题是当一个新增数据库彩添加 到原始数据库伽中时，生成新数据库伽u 如的关联规则，在此基础上有很多算 法对其进行了改进，如冯玉才等提出了i u “”j ，朱玉全等提出了n e wf u p 【1 6 】和 f i u a 【r 7 j 等关联规则的增量式更新算法，他们考虑的是数据集或数据仓库保持不 变，调整最小支持度与最小置信度而引起关联规则发生变化。随后，蒙韧等人提 2 重庆邮电大学硕士论文 第一章绪论 出了一种关联规则更新算法a i u a 【1 8 l ，该算法只须扫描原始数据库和新增数据库各 一遍，能大大降低运算时间。 而挖掘增量式的关联规则仍不能满足人们的需求。由于数据流的产生和发展， 数据流管理系统和数据流查询处理器的研究吸引了广大的研究注意力。除了管理 和查询数据流，另一个重要的研究任务是如何挖掘数据流中关联规则。然而，在 数据流的环境下挖掘关联规则却变成了一个具有挑战性的问题，特别是其中的关 键步骤：频繁模式的挖掘显得尤为重要。因为数据流中的信息量是巨大而且内容 是快速变化的，所以不能像传统的频繁项集挖掘算法那样，对数据库进行存储， 进行多次扫描，得到频繁项集。根据数据流的特性，能够得出如下结论：被设计 的数据挖掘算法只能够扫描原数据库一次来支持对其的各种操作。基于目前的讨 论，对原数据只扫描一遍实际是和传统的挖掘频繁项集是相冲突的。为了协调这 个冲突。许多数据流频繁模式挖掘算法被提出。其中有代表性的是m a n k u i i 州提出 的l o s s yc o 硼t i n g 算法和h 觚【2 0 】等人提出的f p s 们a m 算法。l o s s yc o u n t i n g 算法 采用数据分段的思想，通过扫描一次数据库，可以计算数据流中超过支持度阈值 的频繁项，且误差不超过用户定义的误差范围。但它假设模式是从流开始到目前 时刻这个前提下挖掘频繁模式，时间窗口的粒度较粗，查询精度较低。f p - s 恤锄 算法是在借鉴于f p g r o w t l l 算法的基础上，以一个基于频数序的f p 仃e e 来存储频 繁模式，并利用多时间标签窗记录事务模式的历史信息来回答用户对各个时间段 的询问。f p s t r e 锄时间效率较好，但由于采用批处理方式，不能实时处理数据流 和响应用户对当前数据的查询。随后有很多文章对其进行了改进，c h 趴9 1 2 l j 重点在 于发现数据流中最近的频繁项集。t e n g 【2 2 】研究了滑动窗口中时态频繁模式挖掘问 题，提出了f t p d s 算法，f t p d s 算法为每个频繁项集存储一个a t f 的压缩形式， 利用a t f 可以近似计算滑动窗口中的频繁项集。刘学军【z 3 j 等人提出了f p - d s 算法， 该算法采用数据分段的思想，逐段挖掘频繁项集，但由于采用了f p - 讹e ，必须扫 描数据库两次。王伟平1 2 4 1 等人在l o s s yc o u i 】【t i n g 算法的基础上，提出了一种确定 的误差值近似算法来挖掘数据流上的频繁项，此算法在较高的精度上，保证了较 低的时间复杂度和空间复杂度。t 0 0 n 【2 5 】等人在数据流频繁项集算法中，为了避免 生成大量的频繁项集，只挖掘出最大的频繁项集，此方法虽然节省了空间复杂度， 但是丢失了频繁项集相关信息而且时间复杂度较高。频繁闭项集的挖掘算法【2 h 7 j 虽然没有最大频繁项集挖掘算法节省空间，但是它不会丢失频繁项集相关信息。 为解决以上部分问题，在已有数据流频繁模式挖掘算法f p d s ( m i n i n g f 陀q u e n tp a t t e mi nd a t as t r e 锄s ) 的基础上，改进得到了算法f p s d s ( m i n i n g f r e q u e n tp a t t e mb 嬲e do ns l i d i n g 埘n d o wi nd a t as t r e 锄s ) ，该算法只需扫描数据库 一遍。同时运用剪枝策略，能够提高算法效率。此外，f p s d s 算法能够挖掘出最 3 重庆邮电大学硕士论文 第一章绪论 近用户感兴趣的关联规则。 1 3 研究内容 数据流实时、连续、有序、快速到达的特点以及在线分析的应用需求，对数 据流挖掘算法提出了诸多挑战。对数据流挖掘算法的典型要求如下； 单次线性扫描。即算法只能按数据的流入顺序依次读取数据一次。 低的时间复杂度。流算法是在线算法，为了跟上数据流的流速，算法处理每 个数据项的时间不能太长，最好能为常数时间。 低的空间复杂度。流算法是主存算法，其可用的空间是有限的，算法的空间 复杂度不能随数据量无限增长。 能在理论上保证计算结果具有好的近似程度。 能适应动态变化的数据与流速。产生数据的现象可能在不断变化，导致数据 内容与流速的改变。 能有效处理噪音与空值。这是一个具有健壮的算法所必须具有的能力。 能响应用户在线提出的任意时间段内的挖掘请求。 算法在任何时刻都能给出当前数据的挖掘结果。 建立的概要数据结构具有通用性。 在上述要求中，第l 至3 条是一个数据流挖掘算法所必须满足的。早期的数据 流挖掘算法都是以这三项为目标设计的，对于算法的空间复杂度，理想的情况是 它与数据流长度无关。算法的时间复杂度通常以每个数据项到来时，更新概要数 据结构或目标计算结果所需要的时间来衡量，理想的情况是算法处理每个数据项 的时间为常数。其中，概要数据结构是算法为支持目标计算而在内存中保存的数 据流数据的压缩信息对于构建概要数据结构的算法，通常没有对在概要数据结构 上计算目标函数所需要的时间做严格的要求。 本文分析了数据流挖掘算法所必须满足的要求，并对现有数据流关联规则算 法中存在的问题进行了思考，在已有f p d s 算法的基础上，改进得到了f p s - d s 算法，此算法能够更有效地处理高速的数据流。主要的改进方向有以下几种： 用滑动窗口代替界标模型 f p s d s 算法利用滑动窗口进行数据更新，不但能够得到用户感兴趣的最近频 繁项集，而且相对于界标窗口，算法相对稳定。 采用字典树模型存储频繁项集 f p s d s 算法采用字典树的形式存储事务数据库进行挖掘，只扫描一次数据库， 避免了f p d s 算法中为了按项集计数的降序建树，而扫描数据库两次。 4 重庆邮电大学硕士论文 第一章绪论 利用优化策略对树进行剪枝 f p d s 算法中运用了相关方法对f p d s 树进行了剪枝，并保证剪枝的误差不 超过占。但为了更进一步的节约时间和空间复杂度，适应数据流的挖掘，本文引入 了增量式关联规则中的剪枝策略。 1 4 本文结构 本论文组织结构如下： 第一章介绍了基于数据流的关联规则挖掘研究的意义、目的和挑战，并简要 介绍了研究数据流算法所需要满足的要求及研究内容。 第二章介绍了数据流的特点，阐述了几种数据流的处理模型，并把传统数据 处理模型和数据流处理模型进行了比较。最后列出了几种处理数据流常用的技术。 第三章概述了关联规则的相关知识，介绍了三个基于数据流关联规则的算 法，并分析了算法所存在的不足。 第四章得到了基于f p d s 算法的改进算法f p s d s ，详细阐述了f p s d s 算 法的基本原理及实现过程。 第五章实验分析。首先，对f p s d s 算法进行了正确性测试，并分析验证。 然后对f p d s 算法和f p s d s 算法在几组数据集上进行了性能测试，并对实验结 果比较分析。最后，f d s d s 算法在真实的交通事故数据集上进行了稳定性测试。 第六章对本文所做的工作进行了总结，提出了下一步的研究计划。 重庆邮电大学硕士论文 第二章数据流分析 第二章数据流分析 随着计算机网络应用的飞速发展，数据流处理逐渐成为当前数据库领域新的 研究热点。数据流是一种新的数据形式。在许多应用领域中处理的数据都是以数 据流的形式传输。例如：进行网络监测时获取的监测信息、股票分析系统接受的 实时的股票信息、自动取款机的取款记录、电信公司的通话记录、传感器监测的 各类数据等等。虽然数据流中数据的基本单位还是关系模型中的元组，但是与传 统数据库中的数据不同，这类数据不再是固定的存储形式，而是源源不断的到来、 随时间变化的。由于数据流中的数据是连续不断流入，并且数据产生的速度是惊 人的，数量是无限的。因此，在有限的存储空间中无法保存数据流的全部数据。 所以传统的数据挖掘技术无法完成对数据流中的数据进行有效的挖掘，越来越多 的研究人员开始进行新的基于数据流挖掘技术的研究。为了更好的研究基于数据 流的算法，首先，应该掌握数据流及其特点。然后，应该熟悉处理数据流的几种 常用模型及它和传统的数据模型的区别，从而选择一种较好的处理数据流的模型。 最后，应该了解处理数据流的相关技术。这三个方面将在以下做出介绍。 2 1 数据流及其特点 数据流形式的数据不同于传统的基于集合的相对静止的数据。数据流数据连 续到达，频繁变化，数据量事前是不确定的，也可能是无限的。数据流是一种持 续的、有序的、不断变化的、快速的、数据量巨大的数据形式。形式化表现形式 为： 令r 表示任一时间戳，口，表示在该时间戳到达的数据，数据流可以表示成 ，口f ，q ，q 小) 。这里要注意的是，数据流输入完全可以是多维数据或者同时有 多个流并行输入，但是在本文中为了更明确分析问题，暂时不考虑多个流并行的 情况。 归纳起来，数据流的共同特点是： 大量连续的、有可能是无穷的数据。 传统数据形式的数据量也可以是非常巨大的，但是数据流在数据量大的同时， 还强调了这些数据到来可能是无穷的，即你无法判断最终数据量的大小。 快速变化的，需要快速实时的反应。 数据流不但是连续到来，而且变化比较频繁，对于数据流上一些监控或者分 析操作来说，有许多应用是要求实时响应的。那么在快速变化的数据上实时响应 6 重庆邮电大学硕士论文 第二章数据流分析 比在平稳的数据上进行分析有更大的难度。 数据流很好地捕获了当前对数据处理的需求。 许多情况下，数据流不断到来正是可以表现出数据演化的过程。 随机存取的代价非常高，需要单一的线性扫描算法( 只能扫描一遍数据) 。 由于数据流数量大，到来速度快，因此数据有可能很快就被存储到外存当中 去，所以无法支持其上的算法回溯数据的要求。不断的回溯旧数据不但比较困难， 而且影响了对新到数据的处理，引起数据堆积，造成算法瘫痪。所以，数据流上 的数据处理就是一次扫描数据。在应用中，这个一次扫描数据可以放宽到在内存 中可以进行多次处理，但一旦被放入到外存中，就无法继续对它进行访问。 只能存储迄今为止的数据的汇总信息。 由于数据量特别巨大，所以系统无法存储所有的信息，只能存储数据的汇总 信息。这里不是说所有的原始数据要被丢弃，那些原始数据可以存储在磁盘、磁 带等存储介质中，但是它们已经不受数据流管理分析系统的控制，系统本身只保 留有用的汇总信息。 许多自然的数据流是具有相当低的级别或者有多个维度，需要多级和多维的处 理。多级和多维形式数据的存在，加大了数据流处理的难度。 2 2 数据流模型及划分 2 2 1 数据流模型的划分 目前，在数据流研究领域中存在多种数据流模型。不同的数据流模型具有不 同的适用范围，需要设计不同的处理算法。可以分别按照数据流中数据描述现象 的方式和算法处理数据流时所采用的时序范围对这些模型进行划分。 设数据流中的数据项x l 尥，依次按下标顺序到达，它们描述了一个信号彳。 按勋描述信号彳的方式，数据流模型邪l 可分为以下几类： 时间序列模型 每化，等于彳【f 】并以f 的增序出现，这是一个对时间序列数据适合的模型，例如： 你可以观察到每五分钟的i p 链接的通讯量，或者每分钟n a s d a q 的股票交易量。 收银机模型 这里x ，代表的黝d 1 的增量。铆严( _ ，却，念o ，彳，们利“们+ ，f 其中，彳f 是在得 到了数据流中的第f 个项之后函数的状态。这个模型几乎和现金的记录一样，随着 时间进行多个却能够增加一个给定的彳阴，就好比收银机里l o o 元的钞票会越来越多 一样。现今收银机模型或许是最广泛的数据流模型，它适用于监控访问一个w e b 服 7 重庆邮电大学硕士论文 第二章数据流分析 务的i p 地址，源i p 地址通过连接发送一个包。因为同一个i p 地址随时间进行 可以访问w e b 服务器多次或者发送多个包。 十字转门模型 这里x ，助阴的更新。铆，= ( ，蚴，彳，们利f 1 d 1 + u i ，彳i 是在得到了数据流中的 第f 个项之后函数的状态，u 可以是正的或者负的。此时，数据流中的多个数据项 表达一们们。彳们随着数据的流入，可能会增加，也可能会减小。例如：在数据 库中，某些用户只有删除自己插入纪录的权限。 由于数据流是一个长期、动态的过程，部分算法在处理数据流时并不是将所 有的数据流数据作为处理对象，而是根据应用需求选取某个时间范围内的数据进 行处理。按算法处理数据流时所选取的时序范围，数据流模型【l j 可分为以下几类： 快照模型( s n a p s h o tm o d e l ) 处理数据的范围限制在两个预定义的时间戳之间。 界标模型( 1 a n d m a r km o d e l ) 处理数据的范围从某一个已知的初始时间点到当前时间点为止。 滑动窗口模型( s l i d i n g 诵n d o wm o d e l ) 处理数据的范围由某个固定大小的滑动窗口确定，此滑动窗口的终点永远为 当前时刻。其中，滑动窗口的大小可以由一个时间区间定义，也可以由窗口所包 含的数据项数目定义。 在这三种模型中，通常采用的是界标模型和滑动窗口模型。界标模型通常将 数据流的起始点作为数据处理的初始时间点。此时，算法对数据流中所有数据进 行处理，数据流上只存在插入操作。在滑动窗口模型中，窗口随着数据的流入向 前滑动，窗口中存在数据的插入和删除，滑动窗口模型非常适用于只要求对最近 时间段内的数据进行处理的应用。 2 2 2 基于滑动窗口模型的方法 与传统的数据库中的数据不同，数据流无法被全部保存之后再对其进行处理。 多数情况下，数据流处理的数据对象只能是数据流的一部分，即数据流的样本。 同时，人们常常关心的是最近到达数据处理的结果。因此，基于“最新”数据的 数据流处理技术的研究是一项很有实际意义的工作。基于滑动窗口模型的方法能 够很好地实现最近到达的数据处理。数据流上的滑动窗口方法是指在处理数据流 中的数据时，开辟一块内存窗口存储数据流中的最新数据。数据依次流入窗口相 当于窗口逆向滑向数据流，随着数据的不断流入，最先流入的数据将移出窗口不 再保存。滑动窗口是对数据流进行查询操作、求得近似结果的一种常用的数据采 8 重庆邮电大学硕士论文第二章数据流分析 样方法。 数据流上的滑动窗口是指在数据流上设定一个区间，该区间只包含数据流中 最近到来的部分数据。当新的数据到来时，滑动窗口向前滑动，用最新的数据替 换滑动窗口中最旧的数据。与随机采样等其它采样技术相比，滑动窗口的近似语 义清楚明了。更重要的是，在许多应用中，用户最感兴趣的往往是数据流中最近 到来的那部分数据。因此滑动窗口是对数据流进行处理时使用的一种比较理想的 采样存储方法。滑动窗口通常只包含那些最近到达的数据。当最新数据到来的时 候，窗口将向前移动，将较旧的数据移出窗口。尽管基于滑动窗口的操作结果将 会丢失掉一些数据，但是，许多数据流处理操作只关注那些最近到达的数据所带 来的影响。同时考虑到数据流自身的特性，采用滑动窗口实现数据流处理是一种 较为理想的方式。根据滑动窗口具体实现方法的差异，滑动窗口方法分为基于序 列的滑动窗口方法和基于时间的滑动窗口方法。数据流通常与时间有着紧密联系。 假设窗口的大小是，在任一时间点甩，滑动窗口模型的查询范围是 口胍文0 ，胪附1 ) ，锄) 。时间点聊似( o ，胪阶1 ) 之前的数据全部忽略不计。在滑动窗 口模型下构造概要数据结构比在界面模型下更具挑战性的原因在于，不仅新数据 不断到达，而且旧数据会过期。因此如何处理过期数据，使得查询结果一直可靠， 就成为一大难题。目前的研究成果主要有指数直方图技术、基本窗口技术和链式 抽样技术。 指数直方图( e x p o n e n t i a l1 1 i s t o 伊锄) 指数直方图【2 9 】技术是最早用来生成基于滑动窗口模型的概要数据结构的方 法。传统的直方图技术将数据集划分成多个桶，相邻桶的元素值连续。而指数直 方图则是按照元素的到达次序构建桶。桶的容量按照不同级别呈指数递增，从小 到大分别是l ，2 ，4 ，8 ，各个级别桶的个数均不超过一个预定义的门槛值。每看到流 中的一个元素，由应用的需求就决定是否创建一个最低级别的桶。指数直方图能 够解决滑动窗口模型下的很多问题，例如：基本计数( b 懿i cc o 嘶i n g ) 问题、求和问 题【2 9 1 、方差问题【3 0 】等。文献【3 l 】提出的算法类似于指数直方图，并具有更高的效率。 基本窗口( b 嬲i c 谢n d o w ) 基本窗口技术【3 2 】将大小为的窗口按照时间次序划分成阶等宽的子窗口，称 为基本窗口，每个基本窗口包含晰元素，且由一个小结构表示基本窗口的特征。 如果窗口所包含的元素均已过期，则删除表征这个基本窗口的小结构。用户可以 基于这些未过期的小结构得到查询结果。文献 3 2 】采用这种方法，快速地从众多股 票中得到相关的几支股票。这种方法还可以用于获得数据集中的热门元素列表【3 3 1 。 链式抽样( c h a i n s 锄p l i n g ) 链式抽样方法【3 4 】能够获得在滑动窗口上均匀抽样的样本集合。假设窗口大小 9 重庆邮电大学硕士论文 第二章数据流分析 中的元素以概率l 砌加( 甩，被添加到样本集合中去。当是形，则在任何时间点 ，流 元素被选择到样本集合中去时，必须同时决定一个备选元素，以便于当这个元素 过期时，利用备选元素代替该元素。由于在数据流中不能够预测将来的数据，因 此实际上仅从【刀+ l ，刀+ 吲中随机选取一个数作为备选元素的时间戳，。当到达时间 点f 时，这个备选元素才最终被确定。备选元素以后也会过期，因此也需要为它选 择一个备选元素，方法同上。可以看出样本集合中的任一元素，均有一个备选元 素的“链 ，元素过期后，马上用“链”上的下一个元素取代它。 2 2 3 数据流模型与传统数据模型的模型的区别 传统的数据模型的特点是：数据存储在介质中，可以多次利用；用户提交数 据操纵语言( d m l ) 来获取查询结果。在传统的数据库管理系统中数据存储是有限 的、具有一定稳定性的数据集合。系统可以很好地解决它的传输、计算、存储( t c s ) 等问题。 在一般数据量的情况下，数据能够直接存储在文件中，这个时候数据量对于 系统的t c s 能力无法构成压力。比如说：在传输的时候，如果出现连接缓慢或者 通信错误可以延迟等待，但是最终正确的数据会到达正确的地方。如果计算能力 有限或者程序的复杂性比较高，可以通过延长计算和处理时间得到需要的响应， 但是原则上最终会得到相应的结果。 而对于上述所说的数据流，和传统的数据似乎有些不同，数据流除了数据量 巨大外它还具有输入数据的速度非常快速的特点，而且数据的变化也比较快速。 高速意味着它对通信和基础计算有很大的压力，于是它可能在处理t c s 问题时比 较困难。 为了更好的处理t c s 问题，区别于传统应用模型，数据流模型具有以下4 点 共性： 数据实时到达。 数据到达次序不受应用系统所控制。 数据规模宏大且不能预知其最大值。 数据一经处理，除非特意保存，否则不能被再次取出处理，或者再次提取数 据代价昂贵。利用传统技术处理这种模型，必须将数据全部存储到介质中，然后 通过提交d m l 语句访问存储介质来获取查询结果。但是，由于数据规模宏大且到 达速度很快，传统技术难以满足实时要求。 两种数据模型【2 j 比较如下图2 1 所示。 1 0 重庆邮电大学硕士论文 第二章数据流分析 ( a ) 传统数据处理模型 ( b ) 数据流处理模型 图2 1 数据模型比较 从图2 1 可以看出，传统的数据处理技术将所有数据存放到数据库或者数据仓 库中；系统响应用户提交的d m l 语句，搜索数据存储媒介，返回查询结果。当数 据规模很大时，数据往往以磁盘或者磁带为介质，因而执行查询操作需要大量的i o 交换，效率低下，不能适应实时系统的需求。相反，新的数据流处理技术并不保 存整个数据集，仅维护一个远小于其规模的概要数据结构，从而能够常驻内存。 数据流处理技术往往包含两部分算法，一部分监控流中的数据，更新概要数据结 构；另一部分响应用户查询请求，返回近似查询结果。 2 3 数据流挖掘技术 为了和数据流模型相适应，对应的数据挖掘算法要求单遍扫描数据库就能快 速有效地进行挖掘。现实中数据流还有一些不可以忽略的性质，例如数据分布可 能随时间变化而改变等，这就需要对一定时间内数据库挖掘的结果进行更新，这 样算法才能适应数据分布的变化。相对于普通的数据挖掘算法，数据流的算法时 空复杂度小，但是大多得到的是相对于普通算法的次优解，于是讨论数据流挖掘 算法和普通算法的差异也是必要的。在许多情况下，要求算法维持的数据结构能 够用来计算数据流上函数的值，然后在接下来的时间中，需要处理每一个这样的 查询，即处理连续的查询也是令人感兴趣的研究问题。 接下来将要介绍一些数据库相关的数据流上的处理方法。许多这样的结构已 经在传统数据库中被考虑过。改进这些技术【”1 使得它们适合数据流模型对于研究 来说是个挑战。 查询方式的研究 在数据流中的查询和在传统的数