分布式数据流挖掘技术综述分布式数据流挖掘技术综述
网络信息技术的高速发展产生了新的数据模型,即数据流模型,并且越来越多的领域出现了对数据流实时处理
的需求,庞大且高速的数据以及应用场景的实时性需求均推进了数据流挖掘技术的发展。首先介绍了常见的数
据流模型;然后根据数据流模型的特点总结数据流挖掘的支撑技术;最后,分析了分布式数据流挖掘的重要性
和有效性,给出了算法并行化的数学模型,并介绍了几种具有代表性的分布式数据流处理系统。
万新贵
(南京邮电大学 计算机学院,江苏 南京 210003)
摘要:摘要:网络信息技术的高速发展产生了新的数据模型,即
关键词:关键词:数据流模型;数据流挖掘;分布式;并行化;数据流处理系统
0引言引言
数据流(Data Stream)常常产生于Web上的用户点击、网络入侵检测、实时监控系统或无线传感器网络等动态环境中。与
传统数据集相比较,这些海量的数据流具有快速性、连续性、变化性、无限性等特点。海量的数据流、复杂的数学模型和高要
求的时效性使得传统的数据挖掘面临巨大的挑战,数据流挖掘技术得到了迅猛的发展。
20世纪初,出现了诸如STREAM[1]、Aurora[2]等数据流管理系统(Data Stream Management System)。早期的数
据流管理系统应用领域较为单一,并且大多采用集中式架构,虽然提供了基本算子,但是算子与底层模块的耦合度较高,难以
实现扩展开发。随着技术的发展和需求的提升,分布式技术对数据流处理的重要性显现出来。
21世纪初,随着各类开放式计算平台的兴起,S4[3]、Storm[4]、Spark Streaming [5]以及Samza[6]等数据
流处理平台相继被提出,分布式数据流处理技术已经成为热点。
1数据流模型数据流模型
数据流是一个带有数据时间戳(Time Stamp)的多维数据点集合x1,…,xk,每个数据点xi是一个d维的数据记录。数据流不
被控制且潜在体积无限大,数据流处理系统无法保存庞大的数据流。
目前的数据流研究领域存在多种数据流模型,根据数据流模型自身的特点,可以从两个方面对数据流模型进行分类
[7],分别是按照数据流中数据描述现象的方式和算法处理数据流时所采用的时序范围。
1.1按照描述现象的方式分类按照描述现象的方式分类
按照数据流中数据描述现象的方式,数据流模型可以分为时序(Time Seriel)模型、现金登记(Cash Register)模型和十字转
门(Turnstile)模型,其中十字转门模型的适用范围最广,但也是最难处理的。
(1)时序模型:将数据流中的每个数据看作独立的对象。
(2)现金登记(Cash Register)模型:数据流中的多个数据项增量式地表达某一现象。
(3)十字转门(Turnstile)模型:数据流中的多个数据项表达某一现象,随着时间的流逝,该现象可增可减。
1.2按照算法所采用的时序范围分类按照算法所采用的时序范围分类
部分算法并不将数据流的数据作为处理对象,而是选取某个时间范围的数据进行处理,按照算法处理数据流时所采用的时
序范围,可以将数据流模型分为:快照(Snapshot)模型、界标(Landmark)模型和滑动窗口(Sliding Window)模型,其中界标模
型与滑动窗口模型使用得比较普遍。
(1)快照模型:处理数据的范围限定在两个预定义的时间戳之间。
(2)界标模型:处理数据的范围从某一已知时间到当前时间。
(3)滑动窗口模型:处理数据的范围由固定窗口的大小决定,窗口的终点永远是当前时间。
2支撑技术支撑技术
根据数据流的特点,数据流处理技术需要满足单遍扫描、低时空复杂度等要求。为了有效地处理数据流,新的数据结构、
技术和算法是必须的。参考文献[8]将数据流挖掘的支撑技术分为两类,分别是基于数据(Databased)的技术,旨在以小范
围的数据代替所有数据,达到数据流处理方法的高性能;另一种是基于任务(Taskbased)的技术,力图在时间和空间上得到更
有效的解决方法。
2.1基于数据的技术基于数据的技术
数据挖掘与查询需要读取扫描过的数据[9],但是由于数据流的数据量远大于数据流处理系统的可用内存,不能保证所
有数据都能被存储。因此数据流处理系统需要维持一个概要数据结构,用于保留扫描过的信息。生成数据流概要信息的主要方
法有:抽样、梗概和大纲数据结构等。