分布式数据流挖掘技术综述Word文档下载推荐.docx

分布式数据流挖掘技术综述Word文档下载推荐.docx

《分布式数据流挖掘技术综述Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《分布式数据流挖掘技术综述Word文档下载推荐.docx（4页珍藏版）》请在冰点文库上搜索。

早期的数据流管理系统应用领域较为单一，并且大多采用集中式架构，虽然提供了基本算子，但是算子与底层模块的耦合度较高，难以实现扩展开发。

随着技术的发展和需求的提升，分布式技术对数据流处理的重要性显现出来。

21世纪初，随着各类开放式计算平台的兴起，S4［3］、Storm［4］、SparkStreaming［5］以及Samza［6］等数据流处理平台相继被提出，分布式数据流处理技术已经成为热点。

1数据流模型数据流是一个带有数据时间戳（TimeStamp）的多维数据点集合x1,…，xk，每个数据点xi是一个d维的数据记录。

数据流不被控制且潜在体积无限大，数据流处理系统无法保存庞大的数据流。

目前的数据流研究领域存在多种数据流模型，根据数据流模型自身的特点，可以从两个方面对数据流模型进行分类［7］，分别是按照数据流中数据描述现象的方式和算法处理数据流时所采用的时序范围。

1.1按照描述现象的方式分类按照数据流中数据描述现象的方式，数据流模型可以分为时序（TimeSeriel）模型、现金登记（CashRegister）模型和十字转门（Turnstile）模型，其中十字转门模型的适用范围最广，但也是最难处理的。

（1）时序模型：

将数据流中的每个数据看作独立的对象。

（2）现金登记（CashRegister）模型：

数据流中的多个数据项增量式地表达某一现象。

（3）十字转门（Turnstile）模型：

数据流中的多个数据项表达某一现象，随着时间的流逝，该现象可增可减。

1.2按照算法所采用的时序范围分类部分算法并不将数据流的数据作为处理对象，而是选取某个时间范围的数据进行处理，按照算法处理数据流时所采用的时序范围，可以将数据流模型分为：

快照（Snapshot）模型、界标（Landmark）模型和滑动窗口（SlidingWindow）模型，其中界标模型与滑动窗口模型使用得比较普遍。

（1）快照模型：

处理数据的范围限定在两个预定义的时间戳之间。

（2）界标模型：

处理数据的范围从某一已知时间到当前时间。

（3）滑动窗口模型：

处理数据的范围由固定窗口的大小决定，窗口的终点永远是当前时间。

2支撑技术根据数据流的特点，数据流处理技术需要满足单遍扫描、低时空复杂度等要求。

为了有效地处理数据流，新的数据结构、技术和算法是必须的。

参考文献［8］将数据流挖掘的支撑技术分为两类，分别是基于数据（Databased）的技术，旨在以小范围的数据代替所有数据，达到数据流处理方法的高性能；

另一种是基于任务（Taskbased）的技术，力图在时间和空间上得到更有效的解决方法。

2.1基于数据的技术数据挖掘与查询需要读取扫描过的数据［9］，但是由于数据流的数据量远大于数据流处理系统的可用内存，不能保证所有数据都能被存储。

因此数据流处理系统需要维持一个概要数据结构，用于保留扫描过的信息。

生成数据流概要信息的主要方法有：

抽样、梗概和大纲数据结构等。

（1）抽样：

属于传统的统计学方法，通过一定概率决定数据是否被处理。

抽样技术的弊端是，数据流的长度无法预测，并且数据流的流速不稳定。

（2）梗概：

是将数据流中的数据做随机投影，从而建立小空间的汇总，其主要缺陷是精度问题。

（3）大纲数据结构：

通过应用概要技术生成比原始数据流小得多的数据概要，是当前数据流的概要描述。

直方图、小波变换分析和哈希方法都属于大纲数据结构。

2.2基于任务的技术在算法与应用方面，基于任务的技术可以在时间和空间上更好地进行数据流的处理，目前主要的基于任务的技术包括：

滑动窗口、倾斜时间框架、衰减因子。

（1）滑动窗口：

用户往往对最近的数据更感兴趣，因此只需要保留少量最近的数据并对其进行分析，而对于大量的历史数据，只需要保留概要结构。

这样，既满足了用户需求，又减少了内存开销。

滑动窗口的大小需要用户自定义，但在大多数应用中，该窗口的大小是无法预知的，因此，这是滑动窗口的一个较大的缺陷。

（2）衰减因子：

衰减因子是另一种强调近期数据重要性的方式，它衰减了历史数据对计算结果的影响。

数据在计算之前，先经过衰减函数的作用，这样数据对计算结果的影响会随着时间的推进而减少。

（3）倾斜时间框架：

也称为多窗口技术，滑动窗口与衰减因子只能在一个粒度的窗口上操作。

但是，多数应用会需要在不同粒度的窗口上进行挖掘与分析，为此，可以构建不同层次的时间窗口。

最近的数据记录在细粒度窗口上，较远的历史数据记录在粗粒度窗口上，这样既满足了需求，又不需要太多内存消耗。

除了上述支撑技术，参考文献［7］还提到了基于算法的自适应技术和近似技术，这些技术本质上都是为了算法能够有更好的效果，在精度与时间折中的状态下，对数据流进行有效的处理。

3分布式数据流挖掘随着计算机技术的迅速发展，众多领域内海量、高速的数据飞速增涨，并且需求也趋于多样化与实时性。

例如在移动通信领域，电信数据种类繁多，数量巨大，网络承载流量巨大，如果能够对这些数据进行实时挖掘与分析，就可以有效地避免通信诈骗事件的发生。

又如在交通领域，路线规划一直是该领域研究的热点，通过对车流量进行实时监测与分析，作出合理的路线规划，可以有效减缓交通压力。

这些应用场景的主要特点就是数据量庞大、实时性要求高以及涉及的数学模型复杂。

传统的集中式数据流挖掘不能很好地满足上述应用场景的特点，而分布式数据流挖掘却显示出它的优势。

分布式数据流挖掘是指基于分布式流处理系统，实现算法的分布式并行化，达到算法的有效性和时效性。

分布式流处理系统采用分布式架构，区别于Hadoop［10］之类的处理平台，其处理能力随着节点数目的增长而扩展，具备良好的伸缩性。

并且，大多分布式数据流处理系统分离了计算逻辑和基础模块，系统只负责数据的传输与任务的分配，具体的处理流程和计算单元则由用户自己定义。

在分布式数据流处理系统上实现算法，首先需要根据系统的编程模型设计算法的分布式架构，其次要实现算法的并行化。

并行化后的算法能够在分布式平台上取得更好的效果。

3.1并行化数学模型算法的并行化指使用多台计算机资源实现算法，节省大量计算时间，能极大地提高算法效率。

算法并行化是分布式数据流挖掘顺利进行的一个重要前提。

一般直接编写并行程序是相当困难的，而且各领域使用的串行算法已经相当成熟，所以如何将串行算法转换为并行算法成为研究的重点。

参考文献［11］分析了串行算法并行化的可行性并总结了有向带权图模型、集合划分模型和标记AVL树模型三种将串行算法并行化的数学模型。

（1）有向带权图模型一个串行程序可以抽象为一个有向带权图，程序中的所有函数为构成图的节点，节点的相关程度作为权值，函数之间的调用关系构成图的边，这样的图称为函数调用图。

同理，一个函数也可以这样被拆分。

有向带权图分为连通图与非连通图，在函数调用图中，连通图表示各函数之间均存在调用关系，这样的图代表的串行程序是不易并行化的；

而非连通图代表的串行程序是较易并行化的。

需要对每个连通分支进行不断划分，直到划分至最小原子为止。

（2）集合划分模型集合划分模型是为了解决如何搜索权值最小的边以及如何基于连通图进行并行划分。

运用二元关系的相关知识建立模型，基于有向带权图进行划分。

（3）标记AVL树模型AVL树，即平衡二叉树，在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。

当AVL树增加或者删除节点导致树失去平衡时，AVL树通过旋转使树重新达到平衡。

使用AVL树模型并行化串行算法的前提是，AVL旋转不会影响函数之间的调用关系。

在此前提下，基于有向带权图模型，将图中的一个连通分支作为根节点，分解该图。

每进行一次分解，AVL树就增加两个子节点，若影响到树的平衡向性，则旋转树，否则继续分解图，最终生成一棵平衡二叉树。

树的左子树与右子树代表并行的两部分函数。

3.2分布式数据流处理系统本文选取4种具有代表性的分布式数据流处理系统进行介绍，表1对比了这4种分布式数据流处理系统的各项特点。

3.2.1S4S4于2010年由Yahoo！

公司开源，是一个采用去中心化结构的数据流处理系统，各节点通过ZooKeeper［12］进行协调工作。

S4遵循actor设计模式，数据项在S4中被抽象为事件（event），计算单元会以PE的形式存在，每个PE只能处理key值相同的事件。

虽然系统的伸缩性和扩展性良好，但缺乏消息处理的反馈机制，无法进行有效的故障恢复等。

3.2.2StormStorm于2011年由Twitter公司开源，是一个分布式、高容错的实时计算系统。

Storm实现了实时处理数据流计算，弥补了Hadoop、Spark等批处理系统所不能满足的实时要求。

Storm主要分为Nimbus和Supervisor两种组件，这两种组件都是无状态且快速失败的。

与S4相同的是Storm通过Zookeeper进行任务分配与心跳检测，不同的是Storm利用消息反馈机制保证数据记录被完全处理。

Storm被广泛应用于实时分析、在线机器学习、持续计算、分布式远程调用等领域。

3.2.3SparkStreamingSparkStreaming于2012年被开源，它是核心SparkAPI的一个扩展，SparkStreaming与Spark相同，均采用了RDD（弹性分布式数据集）机制。

在数据处理方面，SparkStreaming引入微批次的概念，它并不会像Storm那样一次一个地处理数据流，而是在处理前按时间间隔预先将其切分为一段一段的批处理作业，把对数据流的处理看作是批处理操作。

但是由于基于RDD转换的操作能力有限，并且微批次处理增加了数据处理延迟，所以SparkStreaming还有很大的改进空间。

3.2.4SamzaSamza于2013年由LinkedIn公司开源。

与Storm和SparkStreaming不同的是，Samza以一条条消息作为数据流处理的单位。

在Samza中，数据流被切分开来，每个部分都由一组只读消息的有序数列构成，而这些消息每条都有一个特定的ID（offset）。

该系统也支持批处理，即逐次处理同一个数据流分区的多条消息。

尽管Samza的数据传输依赖于Kafka，并且需要依靠Yarn来完成资源调度，Samza的执行与数据流模块却是可插拔式的。

4结论本文系统地介绍了数据流挖掘中的数据流模型和支撑技术。

结合数据流挖掘技术的发展，对分布式数据流挖掘进行了概述，并且详细地介绍了分布式数据流挖掘所涉及的相关数学模型及数据流处理系统。

这些内容对于深入了解数据流挖掘并将其进行实际应用有着重要的意义。

参考文献［1］ARASUA,BABCOCKB,BABUS,etal.Stream:

thestanforddatastreammanagementsystem［J］.BookChapter,2003（26）:

665-665.［2］ABADIDJ,CARNEYD,ETINTEMELU,etal.Aurora:

anewmodelandarchitecturefordatastreammanagement［J］.theVLDBJournal—theInternationalJournalonVeryLargeDataBases,2003,12

（2）:

120-139.［3］NEUMEYERL,ROBBINSB,NAIRA,etal.S4:

Distributedstreamcomputingplatform［C］.2010IEEEInternationalConferenceonDataMiningWorkshops.IEEE,2010:

170-177.［4］TOSHNIWALA,TANEJAS,SHUKLAA,etal.Storm@twitter［C］.Proceedingsofthe2014ACMSIGMODInternationalConferenceonManagementofData.ACM,2014:

147-156.［5］ZAHARIAM,DAST,LIH,etal.Discretizedstreams:

anefficientandfaulttolerantmodelforstreamprocessingonlargeclusters［C］.Proceedingsofthe4thUSENIXConferenceonHotTopicsinCloudComputing,2012:

10.［6］MORALESGDF,BIFETA.Samoa:

scalableadvancedmassiveonlineanalysis［J］.JournalofMachineLearningResearch,2015,16

（1）:

149-153.［7］孙玉芬,卢炎生.流数据挖掘综述［J］.计算机科学,2007,34

（1）:

1-5.［8］GABERMM,ZASLAVSKYA,KRISHNASWAMYS.Miningdatastreams:

areview［J］.ACMSigmodRecord,2005,34

（2）:

18-26.［9］谈恒贵,王文杰,李游华.数据挖掘分类算法综述［J］.微型机与应用,2005,24

（2）:

4-6.［10］谢桂兰,罗省贤.基于HadoopMapReduce模型的应用研究［J］.微型机与应用,2010,29（8）:

4-7.［11］吴越.串行算法并行化处理的数学模型与算法描述［J］.计算机技术与发展,2012,22（5）:

14-18.［12］HUNTP,KONARM,JUNQUEIRAFP,etal.ZooKeeper:

waitfreecoordinationforInternetscalesystems［C］.USENIXAnnualTechnicalConference,2010,8:

9.AET会员年终大福利！