（计算机应用技术专业论文）数据流查询和数据流挖掘在油田中应用的研究.pdf

数据流查询和数据流挖掘在油田中应用的研究 摘要 在数据挖掘和数据分析研究领域中，最近出现了一个新的研究方向，即数据流的挖掘 与分析。在网络监控、入侵检测、情报分析、金融服务、股票交易、电子商务、电信、w e b 页面访问和科学研究等众多领域中，数据以流的形式出现。由于数据流的特殊性，短时间 内有大量数据连续到达，这些数据具有随时间动态变化的趋势，怎样对这些数据流使用有 限存储空间进行快速处理以获取有用信息，为数据挖掘及其应用研究带来了新的机遇和挑 战，也具有很重要的意义。 油田计算机网络建设正日趋完善，油田开发和生产科研工作中的大量信息已经实现网 上传输，信息共享的数量和质量得到大幅度提高，开发基于多服务器、大信息量的数据库 信息网络监控系统，提供多方位监控信息建设质量和管理过程的手段，及时全面准确地了 解掌握每天用户对数据库的使用情况，使网上服务器中的数据信息管理变得可视和透明， 通过计算机程序运行取代传统的人工信息管理模式，是迫切需要解决的问题。 本论文主要研究了以下几个方面的内容： ( 1 ) 通过对国内外数据流技术系统的研究，总结出关于数据流、数据流查询、数据流 挖掘以及数据流管理系统( d s m s ) 的基本特点、模型以及关键技术等。 ( 2 ) 大庆油田采油二厂各生产部门每天用p d p m i s 系统连续的向网络中心传送大量生 产数据，本论文把流动的数据集看做一个特殊的数据流，把数据流管理系统( d s m s ) 做 为传统数据库系统的扩展。提出了一个基于数据流挖掘的油田网络监控系统模型，模型添 加了用户接口、数据监控、查询处理器、存储区等系统模块，其中在数据流挖掘模块里通 过o p e r a t o r s 的连接，系统能够通过过滤、聚集、分类，或者忽略某些特定的数据元素。 ( 3 ) 油田生产中，更为感兴趣的问题是近来哪些模式反映较为异常，本论文研究了数 据流异常模式的提取。设定的域值条件为采油厂多年的经验值，采用x m l 结合数据流系 统的方式增强系统的可扩展性。同时介绍了一个数据挖掘环境y a l e ( y e ta n o t h e rl e a r n i n g e n v i r o n m e n t ) 和针对时间序列数据流处理实时和模拟的概念漂移的一个插件工具c o n c e p t d r i f t p l u g i n 。并给出了一个集成学习器k b s 数据流( b a y e s i a n b o o s t i n g f o rs t r e a m s ) 实验的 样例以及一个数据流可适应的时间窗口配置文件。 ( 4 ) 介绍了油田网络监控系统的设计与实现，系统将报警条件设定的域值保存到x m l 文件里，采用d o m 访问x m l 文件；利用了o r a c l e 的审计、触发器、j o b 等功能结合 j a v a 程序对网络中数据库操作情况、生产数据质量等进行全面的监控，并对异常情况进 行报警提示，为兼顾时间和速率以及实际的需求，结合了实时和延时的方式，采用分层报 警。以实际项目为依托，对流数据管理系统和流数据挖掘研究提供了一些经验和思考。 关键词：数据流，数据流查询，数据流挖掘，d s m s ，油田网络监控系统模型，数据流异 常模式，y a l e ，c o n c e p td r i l l 插件 u r e s e a r c ho na na p p l i c a t i o no fd a t as t r e a mq u e r ya n dd a t a s t r e a mm i n i n gi no i lf i e l d a b s t r a c t t h er e s e a r c ho fd a t as t r e a r nm i n i n ga n d a n a l y s i si sn e wa n dh o ti nt h ef i e l d so fd a t am i n i n g a n da n a l y s i s t h e r ea r em a n ya p p l i c a t i o n so fd a t as t r e a mi nm a n yf i e l d s ，s u c ha sp e r f o r m a n c e m e a s u r e m e n t si nn e t w o r km o n i t o r i n ga n dt r a f f i cm a n a g e m e n t ；c a l ld e t a i lr e c o r d si nt e l e c o m m u n i c a t i o n s ；t r a n s a c t i o n si nr e t a i lc h a i n s a t mo p e r a t i o n si nb a n k sa n ds e n s o rn e t w o r k d a t a b e c a u s eo f t h ep a r t i c u l a r i t yo f d a t as t r e a m ：t h et r e n do f v a r y i n gw i t ht i m e ，r a p i da r r i v a lo f m a s s i v ed a t ai ns h o r tt i m e ，i ti sv e r yi m p o r t a n t ，a tt h es a m et i m eac h a n c ea n d c h a l l e n g ef o rd a t a m i n i n gh o w t od e a lw i t hm e s em a s s i v ed a t at oc a p t u r et h eu s e f u li n f o r m a t i o nu s i n gt h el i m i t e d s t o r a g eo v e rt h e s ed a t as t r e a m 。 w i t ht h ec o n s t a n td e v e l o p m e n to f 廿1 eo i lf i e l di n f o r m a t i o n i z a t i o n al a r g en u m b e ro fd a t ao f o i lf i e l dh a v er e a l i z e dp r o g r e s s i v e l yt h a tt h en e t w o r ku p l o a d i ti su r g e n tt h i n gt od e v e l o pt h e n e t w o r k m o n i t o r i n gs y s t e mw i t hm u t i s e r v e ra n dm a s t i v ed a t a ，w h i c hc a np r o v i d et h em e t h o do f m o n i t o r i n gt h ei n f o r m a t i o nq u a l i t ya n dm a n a g e m e n ta n dc a nk n o wc o m p r e h e n s i v l yt h eu s e r s u s a g eo f d a t a b a s et h r o u g hr e p l a c i n gp a t t e mo f m a n u a li n f o r m a t i o nm a n a g e m e n to f p r o g r a m m e t h ef o l l o w i n gi st h em a i nr e s e a r c hw o r ko f t h i sp a d e r ： ( 1 ) t h i sp a p e rc o n c l u d et h eb a s i cc h a r a c t e r 、m o d e la n dk e yt e c h n o l o g ye ta b o u td a t as t r e a m 、 d a t as t r e a m q u e r y 、d a t as f f e a mm i n i n ga n dd s m st h r o u g ht h er e s e a r c ho fd a t as t r e a m t e c h n o l o g y ( 2 ) t h i sp a p e re x p l a i nt h ed e s i g na n dr e a l i z a t i o no fn e t w o r km o n i t o r i n gs y s t e mo fn o 2 f a c t o r yo fo i lf i e l d ，w h i c hs a v et h ea l a r m i n gc o n d i t i o ni n t ox m ld o c u m e n t ：m o n i t o r i n ga n d a l a r m i n go v e rt h eu n s u a lc o n d i t i o no f d a t a b a s ew i t ho r a c l ea u d i t 、t r i g g e r 、i o bf u n c t i o n a t t h es a m et i m e ，t h i sp a d e ra d o p tt h ed i f f e r e n tl e v e la l a r m i n gc o m b i n i n gw i t hr e a lt i m ea n d t i m e d e l a y e db e c a u s eo f t h ec o n t r a d i c t i o n so f t i m ea n d r a t e ( 3 ) t h i sp a p e rt a k e se m p h a s i so ne x t r a c i n gu n s u a lp a t t e r n ，i nw h i c ht h ec o n d i t i o no ft h r e s h o l d i se x p e r i e n t i a lo fo i lf i e l da n dt h ee x p a n s i b i l i t yo fs y s t e mi si n c r e a s e dw i t hx m lc o m b i n i n gw i t h d a t as t r e a ms y s t e m t h i sp a p e ri n t r o d u c e dal e a r n i n ge n v i r o n m e n t 一1 y - a l ea n dc o n e 印td r i f t p l u g i nw h i c he x t e n d sy a l eb vo p e r a t o r sf o rh a n d l i n gr e a la n ds i m u l a t e dc o n c e p td r i f ti n t i m e v a r y i n gd a t as t r c a m s ac o n c e p td r i f te x p e r i m e n t si ss t r u c t u r e ds i m u l a t i n gat i m e l yo r d e r a n dc o n c e p td r i f to nad a t as e ti nt h i sp a d e r ( 4 ) t h i sp a p e re x p l a i nt h ed e s i g na n dr e a l i z a t i o no fn e t w o r km o n i t o r i n gs y s t e mo fn o 2 f a c t o r yo fo i lf i e l d 。w h i c hs a v et h ea l a r m i n gc o n d i t i o ni n t ox m ld o c u m e n t ；m o n i t o r i n ga n d a l a r m i n go v e rt h eu n s u a lc o n d i t i o no f d a t a b a s ew i t ho r a c l ea u d i t 、t r i g g e r 、 o bf u n c t i o n a t t h es a m et i m e t h i sp a d e ra d o p tt h ed i f i e r e n tl e v e la l a r m i n gc o m b i n i n g 谢也r e a lt i m ea n d t i m e d e l a y e db e c a u s eo ft i l ec o n t r a d i c t i o n so ft i m ea n dr a t e t h i sp a p e rp r o v i d e dt h ee x p e r i e n c e a n dt h i n k i n go v e rd s m sa n dd a t am i l l i n gt h r o u g ht h et e a lp r o j e c t k e y w o r d s ：d a t as t r e a m ，d a t as t r e a mq u e r y , d a t as t r e a mm i n i n g ，d s m s ，n e t w o r km o n i t o r i n g s y s t e mm o d e li no i lf i e l d ，d a t as t r e a mu n s u a lp a t t e r n ，y a l e ，c o n c e p td r i f tp u l g i n l i i 一查堡至塑兰堕堡里竺窒生堂堡垒塞 第一章绪论 随着计算机应用的飞速发展，数据流处理逐渐成为人工智能领域新的研究热点，在这 种应用中，数据采用的模型不是永久的关系而是瞬时、实时的数据流的形式。本文以采油 二厂网络中心对p d p m i s 系统数据流的实时处理作为引子，将围绕基于油田网络监控系 统中数据流查询和数据流挖掘的相关主题进一步研究和探讨。本章主要讨论全文的研究背 景、国内外的研究现状、以及本文的组织包括主要研究工作和内容安排。 1 1 课题研究背景 传统的数据库( 如关系、对象数据库) 存储的是相对静止的数据，在这类数据库系统 巾某一时刻数据的快照都是固定的“当前视图”。为了通过数据库系统中数据的变化来反 映现实世界中事物的发展，需要采取一些相应的处理方法。如在关系数据库管理系统中， 用户可以在数据库记录中添加利用d a t e f i m e 等数据类型定义与特定的应用相关的时间属 性，以此将事物的发展和变化记录到数据库系统中。但是，这样的存储方式以及能够提供 的对基于时间的数据的管理能力是非常有限的，而且不能满足实时的需求。 在计量学、观察、策略分析、实时监控等领域中，像股票的价格、传感器的输出、网 络监听和流量监测、电话通信等方面，其时间特性是事物内在固有的。在这些应用环境中， 信息以数据流的形式输入，实时的、连续的、有序的数据序列不断抵达，我们把这种一系 列连续且有序的点组成的序列( 而，z ，一，吒) 称为数据流。通常，按照其固定的次序对序 列中的数据线性扫描，由于数据频繁的变化，一般只对数据进行一次或者几次读取。由于 数据对象和数据处理方式的显著的变化，传统的数据库处理方式已经难以胜任，需要一种 新的数据模型、新的数据挖掘算法、新的查询检索规范来分析和管理数据流信息。 计算机、网络、通信技术之间的相互渗透和信息技术发展的数据化、综合化已成趋势， 传统的电路交换向分组交换演进，信息的传输、交换、处理逐渐融合。传统的数据库管理 系统对于许多现代应用已明显无法适应了。在新的工程领域比如g p s 和微传感器，它们不 断从所处的外界环境中获得采样信息，持续的产生出大量的实时数据，而如何及时地、有 效地对这样大量快速变化的异步数据流进行的不间断处理正是相关应用中至关重要的环 节，也是数据流数据管理系统( d s m s ) 致力解决的问题。 数据流管理系统( d s m s ) 是一种新的数据管理系统，是一种新的处理数据信息的方 法，包括专门针对流数据类型设计的数据模型、查询机制及其他算法。在功能上和适用范 围上与现代其他的数据库管理系统有所区别，但是在技术上又有着千丝万缕的联系。在这 种新生的数据管理系统中，能够发现如分布式数据库、内存数据库、主动数据库、时悉数 据库、实时数据库等不同数据库管理系统技术上的体现。 目前，d s m s 技术的研究和系统的开发还处于一个相对无序的状态，大多数是针对某 一特定领域的应用设计和开发的。但从另一个角度来看，这却比较全面地从不同侧面展示 了数据流数据管理系统的强大生命力，愈发激励着研究人员进一步探索的兴趣。另一方面， d s m s 相关领域的技术研究中又出现了更有前景的方向，那就是d s m s 技术和x m l 技术 的结合【4 j 。x m l 技术的引入，使得应用系统间进行复杂的实时流数据交换和处理成为可 能，为d s m s 系统有效地管理流数据提供了理论上和实际上的规范与指导。 数据挖掘研究的问题虽然主要集中在数据的常规模式方面，但在电子商务欺诈行为监 测、电信和信用卡欺骗、药物效果研究、气象预报、网络入侵检测等方面，研究数据的异 l 绪论 常模式往往比常规模式更有价值。 目前，企业信息化建设呈现出“数据集中化、业务综合化、管理扁平化、决策科学化” 的发展趋势。各企业为了提高自己的市场竞争力和国际竞争力，纷纷提出了建立立足于企 业多年积累的历史数据和核心业务的数据挖掘系统的实施方案，例如：移动通信、邮政储 蓄系统、冶金行业等有了较好的商业应用。国内的石油企业也做着相关的有益的尝试。在 数据挖掘工作开展之前，必须明确数据挖掘所需要解决的问题和所需要达到的预定目标。 也只有在目标明确定义的前提下，数据挖掘的工作才有方向和意义。根据油田生产的特点 火致有下面几个数据挖掘的主题；( 1 ) 揭示事物偏离常规出现异常现象的偏离型知识：利 用分类分析法或聚类分析法等对油田生产中出现的一些异常例如，单量异常变化、含水异 常变化、超注欠注等进行分析。及时发现异常井号，泄漏等故障，优化生产运行参数，减 少盗油犯罪案件的发生，保证油田正常、安全、经济运行；( 2 ) 揭示事物相互联系相互依 赖的关联型知识：利用相关分析、回归分析或时间序列分析等方法挖掘出数据之间的联系， 分析变量之间联系的密切程度，基于观测数据建立变量之间适当的依赖关系等。更有利于 油田分散数据的融合，以及检测出各变量对油田生产的影响程度。有利于更好的指 导生产；( 3 ) 根据历史数据推测未来数据的预测型知识：油田信息化建设应用于油田生产 经营以来，积累了大量生产经营历史数据和成果数据，通过建立有兴趣的模型，提取和挖 掘出大量数据后面的知识，探索出油田生产中的规律性，可以进行预测油藏开发指标、 预测未来的生产情况等，从而更有效的进行生产调接和优化，并为参与市场竞争作出重要 的决策。 1 2 国内外研究现状 国外数据流管理系统研究现状 国外方面，( 1 ) 美国加州大学伯克莱分校正在构建一个t e l e g r a p h c q l 3 】系统，该系统用 于连续的数据流的处理。t e l e g r a p h c q 的目的在于处理对大量高速变化的数据流而进行的 大量连续查询流：( 2 ) 布郎大学的a u r o r a 工程 4 - 5 建造了一个专门用于流监 控的数据处理系统。是面向工作流的系统，用户可以通过组合b o x e s ( 查询操作符) 和a r r o w s ( 查询操作符之间的数据流) 创建查询计划。a u r o r a 系统的核心包括大量的网络触 发器。每个触发器是一个数据流图，每个节点是七个内置操作之一。对每个应用a u r o r a 系 统的流监控系统，应用管理员向a u r o r a 触发器网络中创建和增加一个或多个触发器。 a u r o r a 在触发器网络上实施编译期优化( 比如，重排操作，共享公共子表达式的状态) 和 运行期优化。作为运行期优化的一部分，a u r o r a 发现资源过载并根据质量服务的应用描述 进行负载平衡。另外，他们还正在设计一种可升级的分布式a u r o r a ，叫做a u r o r a * ；( 3 ) 斯 坦福大学已经开始了一种全面d s m s 的设计和原型实现，该系统为s t r e a m ( s t a n f o r d s t r e a md a t am a n a g e r ) 阳j 。s t r e a m 是一个以关系为基础的数据流管理系统，它重点在于内 存管理和近似查询。它可以用于处理快速的、易变的、大量涌入的数据流信息，其连续查 询能力非常好；( 4 ) 维斯康星大学，w e b n i a g a r a l 7j ，是可以处理基于动态w e b 内 容的连续x m l q l 查询的连续查询系统：( 5 ) 康乃尔大学，传感器网络c o u g a r l 8 1 ， 是使用a d t s 表示传感器模型，以时间序列表示输出的传感器数据库；( 6 ) 纽约大学，高 速时间序列数据流在线统计s t a t s t r e a m t l o l ，是用于计算跨越多流的在线统计流监控系统；( 7 ) g i g a s c o p e t 川是一个分布式网络监控结构，提出推某些查询操作符到数据源( 例如路由器) ； ( 8 ) o p e n c q 1 2 】是另一个监控w e b 内容流的连续查询系统，注重可伸缩的事件驱动的查询处 理；f 9 ) t r j b e c a i ”l 是一个早期的i n t e m e t 通信量在线监控工具。 国外数据流挖掘研究现状 大庆油学院硕士研究生学位论文 r ，m o t w a n i 教授领导的研究小组，另一个是u i u c 的c a g g a r w a l 和j h a n 教授领 导的研究小组。前者的研究侧重在数据流管理、数据流的连续查询和数据流的聚类方面 1 4 - 1 8 提出了不同于传统d b m s 的d s m s ( d a t as t r e a mm a n a g e m e n ts y s t e m ) 概念，他们 的研究得到了美国国家自然科学基金的资助。后者的研究侧重在数据流分析方面，对于数 据流的在线分析，从聚类、分类、频繁项集挖掘以及可视化等角度做了大量研究工作1 1 9 - 2 1 ， 提出了倾斜时间窗口( t i l t e d - t i m ew i n d o w ) 策略，采用不同时间粒度保存数据流的信息，他 们的研究得到了美国军方和国家自然科学基金的资助。 异常模式的数据流挖掘方面，a a m i n g ，r a g r a w a l 和p r a g h a v a n l 2 2 】提出了基于偏差 的孤立点探测的线性方法；e k n o r r 和r n g 于1 9 9 8 年提出了在大型数据库中基于距离的 孤立点挖掘算法；还有一些针对孤立点的研究见参考文献。基于聚类分析的孤立点( 也称 为离群点、异常点) 挖掘是近几年提出的一个问题。 国内数据流挖掘研究现状 国内这方面的研究正在起步，文献资料也比较少，有些学校和研究所正在对数据流进 行研究，与国际上数据流领域极其活跃的研究态势相比，国内数据流技术的研究基本上处 于跟踪学习阶段，复旦大学、北京大学、哈尔滨工业大学、东北大学、东南大学等一些研 究机构已经针对数据流的各种相关问题展开了深入的研究，发表了一些有关数据流技术的 论文，但是具有国际影响的技术成果很少，有待进一步提高。复旦大学集中在数据流管理 和挖掘的研究，中科院计算机技术研究所试图构建一个面向网络信息安全的数据流计算模 型，重点研究的一些问题有网络数据流的获取、网络数据流建模、数据流查询模型、数据 流计算算法等，他们的目标是在这个模型的基础上开发出具体的有显示度的宏观网络监控 应用系统。 国内也异常模式挖掘的研究1 2 ”，但往往限于与数据处理有关的问题之中，较少作一般 性的分析和处理。 1 3 主要研究工作及内容安排 研究的主要内容包括：数据流管理系统( d s m s ) ，d s m s 系统中数据流查询和数据 流挖掘，基于数据流的油田监控系统模型，数据流异常提取和趋势监控等。 本文主要围绕基于油田网络监控系统中数据流查询和数据流挖掘相关技术进行研究， 本文的主要研究工作有以下几个方面： f 1 ) 通过对国内外数据流技术系统的研究，总结出关于数据流、数据流查询、数据流 挖掘以及数据流管理系统( d s m s ) 的基本特点、模型以及关键技术等； ( 2 ) 研究数据流异常模式的提取和趋势检测定义和算法、数据挖掘集成环境y a l e 以 及最新的基于y a l e 的针对时间序列数据流处理真实和模拟的概念漂移的c o n c e p td r i f t 插件，并给出数据挖掘算法以及可适应的时间窗口的实验样例； f 3 ) 建立基于数据流的油田网络监控系统的模型，给出系统的体系结构，包含数据流 信息、控制信息的流程，介绍模型主要模块的功能，并重点介绍数据处理模块的数据挖掘 处理器； ( 4 ) 大庆采油二厂网络监控项目。采用o r a c l e 的审计功能、o r a c l e 触发器、 o r a c l e 的j o b 功能、j a v a 与e x c e l 结合、x m l 技术、数据挖掘技术，对于现场多 个生产小队用p d p m i s 系统上传的生产数据流，进行实时和延时相结合的异常监控。提 取生产数据异常情况进行报警。流系统的方式增强系统的可扩展性。 全文的组织如下： 第一章绪论 绪论 介绍了课题的研究背景，国内外的研究现状，主要研究工作和内容安排。 第二章数据流技术 系统介绍了数据流、数据流查询、数据流挖掘以及数据流管理系统( d s m s ) 的基本 特点、模型以及关键技术等。 第三章数据流中异常模式的提取与趋势监控研究 介绍数据流异常模式的提取和趋势检测定义和算法、数据挖掘集成环境y a l e 以及 模拟概念漂移的c o n c e p t d r i f t 插件，并给出k b s 数据流以及可适应的时间窗口的实验样 例。 第四章基于数据流查询和挖掘的油田网络监控系统模型 建立了数据流查询和挖掘的油田网络监控系统模型，给出了系统的体系结构，包括数 据流信息、控制信息流程，并对主要模块的功能进行了介绍。 第五章油田网络监控系统的设计与实现 大庆采油二厂网络监控项目的设计与实现，对于现场多个生产小队用p d p m i s 系统 上传的生产数据流，进行实时和延时相结合的异常监控，提取生产数据异常情况进行报警。 一 查垦鱼垫堂堕堡塑塞生堂堡堡苎 第二章数据流技术 本章系统的介绍了数据流的概念、基本模型、特点，数据流查询的特征及语义、操作 算法，并着重介绍了数据流挖掘，包括本文运用的滑动窗口技术以及数据流中异常模式的 提取与趋势监测，同时还介绍了d s m s 系统与传统d b m s 的区别，以及数据流管理系统 中的数据模型、查询机制和涉及的数据库技术。 2 1 数据流概述 2 1 1 数据流概念及数据流模型 数据流概念：一系列连续且有序的点组成的序列，x f ，一，z 。称为数据流；按照固操 纵语言定的次序，这些点只能被读取一次或者几次。 传统数据库技术的一个共同点是：数据存储在介质中，可以多次利用；用户提交数据 操纵语言( d m l ) 来获取查询结果。2 0 世纪末一种新的应用模型对它提出了有力的挑战。 这种名为流式数据的应用模型广泛出现在众多领域，例如，金融系统的应用、自动提款枫 提取款额的读取。在其他方面如网络流量的监测、电话通信记录的获取、w e b 数据的应 用和传感器网络监测到的数据处理等等。 d a t as 乱r e a m 图2 - 1 数据流模型 f i g 2 - 1 d a t ast r e a mm o d e l 数据流模型【2 4 】如图2 - l ，其中f 表示任一时间戳，a t 表示在该时间戳到达的数据，数据 流可以表示为 一，日。，q ，盯。， 。在数据流模型【2 4 中，处理的数据不再是从磁盘和内存 中随机访问读取的数据，而是一个或多个连续的、无穷的数据项组成的序列。 数据流模型可分为以下3 类： ( 1 ) 时间序列数据流。用来描述时间序列数据，如每分钟纳斯达克( n a s d a q ：i 成交量、 每5m i n 所观测到的i p 流量。则有 口。= ( _ ，)( 2 1 ) 其中，i 对应着递增的时刻。 ( 2 ) c a s hr e g i s t e r 数据流。这是一类应用普遍的模型，类似收银机记录。如对i p 地址 的监控，同- - i p 资源可对一地分时传送或向多个地址传送。则有 口，= ( ，1 ，) ，0 ，鲥力= 4 一l 【力- i - ，。 ( 2 - 2 ) ( 3 ) t u r n s t i l e 数据流。由拥挤的地铁站中记录乘客出入的十字转门的启发而得的。可 有效研究动态的删除与插入操作，但是很难得到有意义的界【2 6 1 。则有 盯，= ( ，u ，) ，l 。0 ， 4 【】_ a 。【门+ u 。( 2 - 3 ) 其中，u 可视作删除与插入符，数值可正可负。 前2 种流模型具有很好的实际意义，特别是时序数据流，文献剐对时序数据流分析做 了全面的研究。t u r n s t i l e 模型具有较好的理论价值。 数据流技术 数据流与存储在数据库中的数据的区别在于： ( 1 ) 数据流中的数据是实时到来的：而数据库中的数据是存储在磁盘中 ( 2 ) 数据流中的数据是按序流过的，对数据只能进行顺序的访问；而磁盘中的数据可 以随机访问 ( 3 ) 数据流中的数据是无限的；而数据库中的数据是有限的 ( 4 ) 由于在有限的存储空间内无法存储无限数据流的全部数据，因此数据流中大部分 的数据在处理后被丢弃了，数据流上的查询多数只能得到近似的查询结果；而数据库上的 查询则可以得到精确的查询结果 ( 5 ) 系统只能保存数据流全部数据的一个有限子集或统计数据，并随着数据流上新数 据的到来进行更新，这种更新的频度取决于数据流中数据到来的速度。一般来说，数据流 的更新频度要远远高于数据库中数据更新的频度 目前，数据流的数据模型主要有基于关系和基于对象定义方式。基于关系的数据流模 型将每个数据源产生的数据流看作是虚拟的关系，数据流中的每个数据项看作是一个元 组。基于对象的数据流模型将数据源及其产生的数据项看作是具有层次关系的数据类型， 数据源与数据项之间通过方法进行联系。本文使用的数据流的数据模型是基于关系的定义 方式。 2 1 2 数据流特点 理。 ( 1 ) 它是大量的、连续的、无限的数据； ( 2 ) 频繁的变化并且要求快速的即时响应； ( 3 ) 数据流管理中随机存取采用的是单一线性的扫描算法； ( 4 ) 大多数流式数据初始时处于较低层次或者多维状态，需要多层次化和多维化处 2 2 数据流查询 2 2 1 数据流上查询的特征及语义 数据流上的查询【2 8 】与传统数据库中的查询类型基本上相似，但有一个明显的区别： 数据库中的查询主要是一次查询，而数据流上的查询则更多的是连续查询。如果一个查询 提交后，系统根据当前数据集合的快照给出查询的结果，则称这样的查询为一次查询；如 果查询随着新数据的到来而不断的返回查询结果，则称这样的查询为连续查询。连续查询 注册到系统中后，除非用户明确的撤消该查询，否则随着数据流上新数据的到来，数据将 不断的返回查询结果。相对于一次查询，连续查询具有长期运行的特点。连续查询处理的 结构如图2 - 2 。 数据流上的查询还可以分为预定义查询和a dh o c 即席查询两种查询形式。预定义查 询注册到系统后，主要针对数据流后续到来的数据计算查询结果；而a dh o c 查询是针对 数据流中流过的所有数据，系统只能通过提取和组织流过数据的概要信息来支持a dh o c 查询，因此a dh o c 查询一般只能得到近似的查询结果。 二! 堡亘垫鲎堕堡主竺塑生堂垡堡壅 网 j 要结整fl 网 l 耍结拖i 黧豢刚r 2 雪高数据流e = = = = 之 1 数括沉置询 数据流r nc = = = = = ：，l 熊堡墨 杏询千装载 查询0 ( r i ，r 2 。r n ) 图2 - 2 数据流查询处理结构 数据流输出结 果 在一个只有插入操作的数据库中，所有查询均是单调的。因为当一个元组加入后，这 个元组或者满足查询，或者不满足查询，查询的结果随时间表现为递增。数据流上的大部 分连续查询均具有单调性。文献吲讨论了数据流上单调的和非单调的连续查询语义。将 时间表示成自然数的集合，在每个整数时刻，连续查询计算一次查询结果。设a ( p ，f ) 是连续查询g 在t 时刻的查询结果，嵋蹙示当前时刻，。表示查询的开始时刻，则查询q 在r 时刻的查询结果集表示为： a ( q ，r ) = u ( 爿( q ，f ) 一a ( q ，t 一1 ) ) u 一( q ，o ) ( 2 4 ) f 5 i 也就是说，单调的连续查询可以采用增量式的计算方式，即前次计算的查询结果加 上新到来的数据中满足查询条件的那部分元组为当前查询的结果。相反，对于非单调的连 续查询，查询必须每次访问过去的数据计算查询结果，其查询结果集表示为： a ( q ，f ) = u a ( q ，r ) ( 2 5 ) f t o 2 2 2 数据流上的查询操作算法 因为数据流中的数据具有无限、瞬时等特点，所以，数据流上的查询操作算法与传统 数据库中的查询操作算法1 2 8 相比有它自身的特点。 ( 1 ) 阻塞操作 在关系系统中，若一个操作在得到结果前，需要访问关系的全部数据，则称这个操作 是阻塞的。排序以及聚集函数c o u n t 、s u m 、a v g 、m a x 、m i n 等许多操作均书 阻塞的。如果使用传统的查询操作树来执行数据流上的连续查询，那么若查询操作树中的 有一个阻塞的操作，则这个查询不会有输出结果。因为阻塞操作需要扫描数据流上的全部 数据，而数据流是无限的，阻塞操作永远得不到输出结果。显然，阻塞操作不适用于数据 流的查询处理。然而许多包含阻塞操作的查询，如聚集查询又是数据流应用中一种常用的 查询类型，完全放弃阻塞操作也是不现实的。有些操作既有阻塞的实现算法，也有非阻塞 的实现算法。例如连接操作中，循环嵌套连接算法和s o r t - m e r g e 算法是阻塞的连接实现算 法，而s y n u n e t r i ch a s hj o i n 算法则是非阻塞的连接算法。s y m m e t r i ch a s hj o i n 算法在内存 中分别为参加连接的两个关系a 、b 创建h a s h 表。当a 或b 中有一个新的元组到来时， 首先将其插入到该关系对应的h a s h 表中，然后用这个元组去探测另一个关系在内存中的 数据流技术 h a s h 表，将匹配的连接结果输出。当这些操作应用到数据流上时，显然只能选择其非阻 塞的实现算法。解决阻塞操作问题的一个通用的方法是在数据流上定义窗口，将无限的数 据流限制在一个有限的范围内。窗口查询是数据流上的一个非常重要的查询类型。 ( 2 ) 近似算法 在数据流的查询处理中，由于数据流无限性的特点以及系统存储空间的限制，许多查 询无法得到精确的查询结果。在这种情况下，高质量的近似查询结果是唯一的选择。数据 流查询处理的近似算法是一个非常活跃的研究领域，已经有很多的研究成果。 抽样技术足处理犬数据集上的查询时常用近似方法，在抽样的样本上计算查询的结果，同 时给出查询结果的误差度。利用样本数据支持查询时，一些给出明确误差度，而有些查 询则无法给出明确的误差度，例如计算最大值的查询或者是大部分包含连接查询等等。 系统统计并保存数据流的概要信息，利用概要来支持数据流上的查询是另一种近似查询处 理的方法。一般来说，存储数据流概要信息的空间大小与查询结果准确性密切相关，存储 的概要信息越多，查询结果的近似程度就越高。目前主要有s k e t c h 、直方图和h a s h 表 等几种概要信息的组织方式。利用小波变换的系数来保存数据的特征信息，以此来支持数 据流上的聚集查询也是一种有效的近似方法。 ( 3 ) 滑动窗口 滑动窗口是数据流上应用比较多的一种特殊的数据抽样方法。滑动窗口是指在数据流 上设定一个区间，该区间只包括数据流中最近到来的那部分数据。随着新数据的到来，窗 口向前移动，用最新的数据替换最旧的数据。与其他抽样方法相比，滑动窗i z l 的优点在于 其语义明确。更重要的是，在许多应用中，例如传感器网络，用户关心的只是数据流中新 近到来的那部分数据。此时，滑动窗口是一种十分理想的抽样方法，通过滑动窗口对连续 查询的范围限定，包括两种限定方式：一种是窗口中包括最近到来的r 个元组，称为基 于顺序或基于计数限定的滑动窗口。另一种是窗口中包含最近t 个时间单元内到来的元 组，称为基于时间限定的滑动窗口。数据流上连续查询处理的执行方式有两类：一类是立 即执行方式；一类是周期执行方式。立即执行是只指数据流上每个新数据到来，均触发执 行一次查询：而周期执行是指每隔固定的时间间隔触发执行一次查询。由于连续查询的执 行方式不同，所以，滑动窗口的滑动方式也随之不同。当连续查询是立即执行方式时，窗 口的滑动以元组为单位，即没到一个新的元组，窗口就向前滑动，计算查询结果；当连续 查询是周期执行方式时，窗口的滑动是以固定个数的元组或固定的时间间隔为单位滑动， 计算查询结果。 2 3 数据流挖掘 2 3 1 数据流挖掘的主要任务 在数据流挖掘【2 ”2 j 中，数据摘要或模型表示、趋势检测、异常检测是关键技术【5 4 】。 基于目前数据流挖掘的现状，以下方面的研究将得到更多的关注：( 1 ) 针对数据流高维时 态混合属性的特点，寻找新的适于数据流的数据结构和建模方法，研究有效度量数据相似 性的方法；( 2 ) 研究针对数据流的高效异常挖掘算法；( 3 ) 研究数据流基于时间变化的特 性，探索数据流变化的表示与建模方法，挖掘数据进化和变化的趋势；( 4 ) 研究数据流基 于约束的聚类分析；( 5 ) 研究数据流的局部周期挖掘算法。 就目前主要的数据流挖掘的任务为： 多维( 在线) 数据流分析( m u l t i - d i m e n s i o n a l ( o n l 协e ) a n a l y s i so fs t r e a m s ) 数据流聚类分析( c l u s t e r i n gd a t as t r e a m s ) 数据流分类分析( c l a s s i f i c a t i o no f d a t as t r e a m s ) 大庆石油学院硕士研究生学位论文 数据流频繁模式挖掘( m i n i n gf r e q u e n tp a t t e r n si nd a t as t r e a m s ) 数据流序列模式挖掘( m i n i n gs e q u e n t i a lp a t t e r n si nd a t as t r e a m s ) 数据流局部周期挖掘( m i n i n gp a r t i a lp e r i o d i c i t yi nd a t as t r e a m s ) 数据流显著倾斜挖掘( m i n i n gn o t a b l eg r a d i e n t si nd a t as t r e a m s ) 数据流孤立点和异常模式挖掘( m i n i n go u t l i e r sa n du n u s u a lp a t t e r n si nd a t a s t r e a m s ) 2 3 2 数据流挖掘特点 数据流挖掘就是在流式数据上发现提取隐含在其中的、人们事先不知道的、但又是潜 在有用的信息和知识的过程。由于数据流本身的特点，许多传统的数据挖掘算法并不适合 于数据流的挖掘。因为数据是以流动的方式出现，并不象传统的数据是静态存储在磁盘中。 许多数据如果没有被保存将无法重新访问。所以要求基于数据流的挖掘算法不能多次重复 扫描数据，只能通过对数据进行一次扫描完成挖掘。还有数据流中的数据量规模宏大，内 存无法存储全部数据，也使得基于数据流挖掘的算法只能利用有限的内存提取数据流的一 个样本作为算法的输入数据，所以挖掘的结果也是近似值。同时根据数据流的特点，挖掘 的结果也应浚是实时结果。基于以上数据流挖掘的特点，传统的数据挖掘方法如果不改进 多数不适合在数据流上挖掘。例如：在数据流中挖掘关联规则时，用基于频集理论的 a p r i o r i 算法获取最大频繁项集，就不能直接应用于数据流上。因为该算法必须经过多次 扫描事物数据库，才能获取最大频繁项集，进而产生关联规则。还有由于数据流随着时间 的变化，新数据将被不断地读入，许多算法在处理数据时并不能将流入的所有数据堆积处 理，即便算法有这样的能力，数据也是随着时间的变化不断更新，所以挖掘到的结果也在 随时间不断地变化。也使得挖掘的结果不能是绝对精确的。这就要求数据流的挖掘算法要 有定的修改能力，即伸缩性。而且基于数据流的高速流入和数据流中的数