萬新貴

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210003)

?

分布式數(shù)據(jù)流挖掘技術(shù)綜述

萬新貴

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210003)

網(wǎng)絡(luò)信息技術(shù)的高速發(fā)展產(chǎn)生了新的數(shù)據(jù)模型，即數(shù)據(jù)流模型，并且越來越多的領(lǐng)域出現(xiàn)了對數(shù)據(jù)流實(shí)時(shí)處理的需求，龐大且高速的數(shù)據(jù)以及應(yīng)用場景的實(shí)時(shí)性需求均推進(jìn)了數(shù)據(jù)流挖掘技術(shù)的發(fā)展。首先介紹了常見的數(shù)據(jù)流模型；然后根據(jù)數(shù)據(jù)流模型的特點(diǎn)總結(jié)數(shù)據(jù)流挖掘的支撐技術(shù)；最后，分析了分布式數(shù)據(jù)流挖掘的重要性和有效性，給出了算法并行化的數(shù)學(xué)模型，并介紹了幾種具有代表性的分布式數(shù)據(jù)流處理系統(tǒng)。

數(shù)據(jù)流模型；數(shù)據(jù)流挖掘；分布式；并行化；數(shù)據(jù)流處理系統(tǒng)

0 引言

數(shù)據(jù)流(Data Stream)常常產(chǎn)生于Web上的用戶點(diǎn)擊、網(wǎng)絡(luò)入侵檢測、實(shí)時(shí)監(jiān)控系統(tǒng)或無線傳感器網(wǎng)絡(luò)等動態(tài)環(huán)境中。與傳統(tǒng)數(shù)據(jù)集相比較，這些海量的數(shù)據(jù)流具有快速性、連續(xù)性、變化性、無限性等特點(diǎn)。海量的數(shù)據(jù)流、復(fù)雜的數(shù)學(xué)模型和高要求的時(shí)效性使得傳統(tǒng)的數(shù)據(jù)挖掘面臨巨大的挑戰(zhàn)，數(shù)據(jù)流挖掘技術(shù)得到了迅猛的發(fā)展。

20世紀(jì)初，出現(xiàn)了諸如STREAM[1]、Aurora[2]等數(shù)據(jù)流管理系統(tǒng)(Data Stream Management System)。早期的數(shù)據(jù)流管理系統(tǒng)應(yīng)用領(lǐng)域較為單一，并且大多采用集中式架構(gòu)，雖然提供了基本算子，但是算子與底層模塊的耦合度較高，難以實(shí)現(xiàn)擴(kuò)展開發(fā)。隨著技術(shù)的發(fā)展和需求的提升，分布式技術(shù)對數(shù)據(jù)流處理的重要性顯現(xiàn)出來。

21世紀(jì)初，隨著各類開放式計(jì)算平臺的興起，S4[3]、Storm[4]、Spark Streaming[5]以及Samza[6]等數(shù)據(jù)流處理平臺相繼被提出，分布式數(shù)據(jù)流處理技術(shù)已經(jīng)成為熱點(diǎn)。

1 數(shù)據(jù)流模型

數(shù)據(jù)流是一個(gè)帶有數(shù)據(jù)時(shí)間戳(Time Stamp)的多維數(shù)據(jù)點(diǎn)集合x1,…，xk，每個(gè)數(shù)據(jù)點(diǎn)xi是一個(gè)d維的數(shù)據(jù)記錄。數(shù)據(jù)流不被控制且潛在體積無限大，數(shù)據(jù)流處理系統(tǒng)無法保存龐大的數(shù)據(jù)流。

目前的數(shù)據(jù)流研究領(lǐng)域存在多種數(shù)據(jù)流模型，根據(jù)數(shù)據(jù)流模型自身的特點(diǎn)，可以從兩個(gè)方面對數(shù)據(jù)流模型進(jìn)行分類[7]，分別是按照數(shù)據(jù)流中數(shù)據(jù)描述現(xiàn)象的方式和算法處理數(shù)據(jù)流時(shí)所采用的時(shí)序范圍。

1.1 按照描述現(xiàn)象的方式分類

按照數(shù)據(jù)流中數(shù)據(jù)描述現(xiàn)象的方式，數(shù)據(jù)流模型可以分為時(shí)序(Time Seriel)模型、現(xiàn)金登記(Cash Register)模型和十字轉(zhuǎn)門(Turnstile)模型，其中十字轉(zhuǎn)門模型的適用范圍最廣，但也是最難處理的。

(1)時(shí)序模型：將數(shù)據(jù)流中的每個(gè)數(shù)據(jù)看作獨(dú)立的對象。

(2)現(xiàn)金登記(Cash Register)模型：數(shù)據(jù)流中的多個(gè)數(shù)據(jù)項(xiàng)增量式地表達(dá)某一現(xiàn)象。

(3)十字轉(zhuǎn)門(Turnstile)模型：數(shù)據(jù)流中的多個(gè)數(shù)據(jù)項(xiàng)表達(dá)某一現(xiàn)象，隨著時(shí)間的流逝，該現(xiàn)象可增可減。

1.2 按照算法所采用的時(shí)序范圍分類

部分算法并不將數(shù)據(jù)流的數(shù)據(jù)作為處理對象，而是選取某個(gè)時(shí)間范圍的數(shù)據(jù)進(jìn)行處理，按照算法處理數(shù)據(jù)流時(shí)所采用的時(shí)序范圍，可以將數(shù)據(jù)流模型分為：快照(Snapshot)模型、界標(biāo)(Landmark)模型和滑動窗口(Sliding Window)模型，其中界標(biāo)模型與滑動窗口模型使用得比較普遍。

(1)快照模型：處理數(shù)據(jù)的范圍限定在兩個(gè)預(yù)定義的時(shí)間戳之間。

(2)界標(biāo)模型：處理數(shù)據(jù)的范圍從某一已知時(shí)間到當(dāng)前時(shí)間。

(3)滑動窗口模型：處理數(shù)據(jù)的范圍由固定窗口的大小決定，窗口的終點(diǎn)永遠(yuǎn)是當(dāng)前時(shí)間。

2 支撐技術(shù)

根據(jù)數(shù)據(jù)流的特點(diǎn)，數(shù)據(jù)流處理技術(shù)需要滿足單遍掃描、低時(shí)空復(fù)雜度等要求。為了有效地處理數(shù)據(jù)流，新的數(shù)據(jù)結(jié)構(gòu)、技術(shù)和算法是必須的。參考文獻(xiàn)[8]將數(shù)據(jù)流挖掘的支撐技術(shù)分為兩類，分別是基于數(shù)據(jù)(Data-based)的技術(shù)，旨在以小范圍的數(shù)據(jù)代替所有數(shù)據(jù)，達(dá)到數(shù)據(jù)流處理方法的高性能；另一種是基于任務(wù)(Task-based)的技術(shù)，力圖在時(shí)間和空間上得到更有效的解決方法。

2.1 基于數(shù)據(jù)的技術(shù)

數(shù)據(jù)挖掘與查詢需要讀取掃描過的數(shù)據(jù)[9]，但是由于數(shù)據(jù)流的數(shù)據(jù)量遠(yuǎn)大于數(shù)據(jù)流處理系統(tǒng)的可用內(nèi)存，不能保證所有數(shù)據(jù)都能被存儲。因此數(shù)據(jù)流處理系統(tǒng)需要維持一個(gè)概要數(shù)據(jù)結(jié)構(gòu)，用于保留掃描過的信息。生成數(shù)據(jù)流概要信息的主要方法有：抽樣、梗概和大綱數(shù)據(jù)結(jié)構(gòu)等。

(1)抽樣：屬于傳統(tǒng)的統(tǒng)計(jì)學(xué)方法，通過一定概率決定數(shù)據(jù)是否被處理。抽樣技術(shù)的弊端是，數(shù)據(jù)流的長度無法預(yù)測，并且數(shù)據(jù)流的流速不穩(wěn)定。

(2)梗概：是將數(shù)據(jù)流中的數(shù)據(jù)做隨機(jī)投影，從而建立小空間的匯總，其主要缺陷是精度問題。

(3)大綱數(shù)據(jù)結(jié)構(gòu)：通過應(yīng)用概要技術(shù)生成比原始數(shù)據(jù)流小得多的數(shù)據(jù)概要，是當(dāng)前數(shù)據(jù)流的概要描述。直方圖、小波變換分析和哈希方法都屬于大綱數(shù)據(jù)結(jié)構(gòu)。

2.2 基于任務(wù)的技術(shù)

在算法與應(yīng)用方面，基于任務(wù)的技術(shù)可以在時(shí)間和空間上更好地進(jìn)行數(shù)據(jù)流的處理，目前主要的基于任務(wù)的技術(shù)包括：滑動窗口、傾斜時(shí)間框架、衰減因子。

(1)滑動窗口：用戶往往對最近的數(shù)據(jù)更感興趣，因此只需要保留少量最近的數(shù)據(jù)并對其進(jìn)行分析，而對于大量的歷史數(shù)據(jù)，只需要保留概要結(jié)構(gòu)。這樣，既滿足了用戶需求，又減少了內(nèi)存開銷。滑動窗口的大小需要用戶自定義，但在大多數(shù)應(yīng)用中，該窗口的大小是無法預(yù)知的，因此，這是滑動窗口的一個(gè)較大的缺陷。

(2)衰減因子：衰減因子是另一種強(qiáng)調(diào)近期數(shù)據(jù)重要性的方式，它衰減了歷史數(shù)據(jù)對計(jì)算結(jié)果的影響。數(shù)據(jù)在計(jì)算之前，先經(jīng)過衰減函數(shù)的作用，這樣數(shù)據(jù)對計(jì)算結(jié)果的影響會隨著時(shí)間的推進(jìn)而減少。

(3)傾斜時(shí)間框架：也稱為多窗口技術(shù)，滑動窗口與衰減因子只能在一個(gè)粒度的窗口上操作。但是，多數(shù)應(yīng)用會需要在不同粒度的窗口上進(jìn)行挖掘與分析，為此，可以構(gòu)建不同層次的時(shí)間窗口。最近的數(shù)據(jù)記錄在細(xì)粒度窗口上，較遠(yuǎn)的歷史數(shù)據(jù)記錄在粗粒度窗口上，這樣既滿足了需求，又不需要太多內(nèi)存消耗。

除了上述支撐技術(shù)，參考文獻(xiàn)[7]還提到了基于算法的自適應(yīng)技術(shù)和近似技術(shù)，這些技術(shù)本質(zhì)上都是為了算法能夠有更好的效果，在精度與時(shí)間折中的狀態(tài)下，對數(shù)據(jù)流進(jìn)行有效的處理。

3 分布式數(shù)據(jù)流挖掘

隨著計(jì)算機(jī)技術(shù)的迅速發(fā)展，眾多領(lǐng)域內(nèi)海量、高速的數(shù)據(jù)飛速增漲，并且需求也趨于多樣化與實(shí)時(shí)性。例如在移動通信領(lǐng)域，電信數(shù)據(jù)種類繁多，數(shù)量巨大，網(wǎng)絡(luò)承載流量巨大，如果能夠?qū)@些數(shù)據(jù)進(jìn)行實(shí)時(shí)挖掘與分析，就可以有效地避免通信詐騙事件的發(fā)生。又如在交通領(lǐng)域，路線規(guī)劃一直是該領(lǐng)域研究的熱點(diǎn)，通過對車流量進(jìn)行實(shí)時(shí)監(jiān)測與分析，作出合理的路線規(guī)劃，可以有效減緩交通壓力。這些應(yīng)用場景的主要特點(diǎn)就是數(shù)據(jù)量龐大、實(shí)時(shí)性要求高以及涉及的數(shù)學(xué)模型復(fù)雜。傳統(tǒng)的集中式數(shù)據(jù)流挖掘不能很好地滿足上述應(yīng)用場景的特點(diǎn)，而分布式數(shù)據(jù)流挖掘卻顯示出它的優(yōu)勢。

分布式數(shù)據(jù)流挖掘是指基于分布式流處理系統(tǒng)，實(shí)現(xiàn)算法的分布式并行化，達(dá)到算法的有效性和時(shí)效性。分布式流處理系統(tǒng)采用分布式架構(gòu)，區(qū)別于Hadoop[10]之類的處理平臺，其處理能力隨著節(jié)點(diǎn)數(shù)目的增長而擴(kuò)展，具備良好的伸縮性。并且，大多分布式數(shù)據(jù)流處理系統(tǒng)分離了計(jì)算邏輯和基礎(chǔ)模塊，系統(tǒng)只負(fù)責(zé)數(shù)據(jù)的傳輸與任務(wù)的分配，具體的處理流程和計(jì)算單元?jiǎng)t由用戶自己定義。

在分布式數(shù)據(jù)流處理系統(tǒng)上實(shí)現(xiàn)算法，首先需要根據(jù)系統(tǒng)的編程模型設(shè)計(jì)算法的分布式架構(gòu)，其次要實(shí)現(xiàn)算法的并行化。并行化后的算法能夠在分布式平臺上取得更好的效果。

3.1 并行化數(shù)學(xué)模型

算法的并行化指使用多臺計(jì)算機(jī)資源實(shí)現(xiàn)算法，節(jié)省大量計(jì)算時(shí)間，能極大地提高算法效率。算法并行化是分布式數(shù)據(jù)流挖掘順利進(jìn)行的一個(gè)重要前提。

一般直接編寫并行程序是相當(dāng)困難的，而且各領(lǐng)域使用的串行算法已經(jīng)相當(dāng)成熟，所以如何將串行算法轉(zhuǎn)換為并行算法成為研究的重點(diǎn)。參考文獻(xiàn)[11]分析了串行算法并行化的可行性并總結(jié)了有向帶權(quán)圖模型、集合劃分模型和標(biāo)記AVL樹模型三種將串行算法并行化的數(shù)學(xué)模型。

(1)有向帶權(quán)圖模型

一個(gè)串行程序可以抽象為一個(gè)有向帶權(quán)圖，程序中的所有函數(shù)為構(gòu)成圖的節(jié)點(diǎn)，節(jié)點(diǎn)的相關(guān)程度作為權(quán)值，函數(shù)之間的調(diào)用關(guān)系構(gòu)成圖的邊，這樣的圖稱為函數(shù)調(diào)用圖。同理，一個(gè)函數(shù)也可以這樣被拆分。

有向帶權(quán)圖分為連通圖與非連通圖，在函數(shù)調(diào)用圖中，連通圖表示各函數(shù)之間均存在調(diào)用關(guān)系，這樣的圖代表的串行程序是不易并行化的；而非連通圖代表的串行程序是較易并行化的。需要對每個(gè)連通分支進(jìn)行不斷劃分，直到劃分至最小原子為止。

(2)集合劃分模型

集合劃分模型是為了解決如何搜索權(quán)值最小的邊以及如何基于連通圖進(jìn)行并行劃分。運(yùn)用二元關(guān)系的相關(guān)知識建立模型，基于有向帶權(quán)圖進(jìn)行劃分。

(3)標(biāo)記AVL樹模型

AVL樹，即平衡二叉樹，在AVL樹中任何節(jié)點(diǎn)的兩個(gè)子樹的高度最大差別為一，所以它也被稱為高度平衡樹。當(dāng)AVL樹增加或者刪除節(jié)點(diǎn)導(dǎo)致樹失去平衡時(shí)，AVL樹通過旋轉(zhuǎn)使樹重新達(dá)到平衡。

使用AVL樹模型并行化串行算法的前提是，AVL旋轉(zhuǎn)不會影響函數(shù)之間的調(diào)用關(guān)系。在此前提下，基于有向帶權(quán)圖模型，將圖中的一個(gè)連通分支作為根節(jié)點(diǎn)，分解該圖。每進(jìn)行一次分解，AVL樹就增加兩個(gè)子節(jié)點(diǎn)，若影響到樹的平衡向性，則旋轉(zhuǎn)樹，否則繼續(xù)分解圖，最終生成一棵平衡二叉樹。樹的左子樹與右子樹代表并行的兩部分函數(shù)。

3.2 分布式數(shù)據(jù)流處理系統(tǒng)

本文選取4種具有代表性的分布式數(shù)據(jù)流處理系統(tǒng)進(jìn)行介紹，表1對比了這4種分布式數(shù)據(jù)流處理系統(tǒng)的各項(xiàng)特點(diǎn)。

表1 分布式數(shù)據(jù)流處理系統(tǒng)比較

3.2.1 S4

S4于2010年由Yahoo！公司開源，是一個(gè)采用去中心化結(jié)構(gòu)的數(shù)據(jù)流處理系統(tǒng)，各節(jié)點(diǎn)通過ZooKeeper[12]進(jìn)行協(xié)調(diào)工作。S4遵循actor設(shè)計(jì)模式，數(shù)據(jù)項(xiàng)在S4中被抽象為事件(event)，計(jì)算單元會以PE的形式存在，每個(gè)PE只能處理key值相同的事件。雖然系統(tǒng)的伸縮性和擴(kuò)展性良好，但缺乏消息處理的反饋機(jī)制，無法進(jìn)行有效的故障恢復(fù)等。

3.2.2 Storm

Storm于2011年由Twitter公司開源，是一個(gè)分布式、高容錯(cuò)的實(shí)時(shí)計(jì)算系統(tǒng)。Storm實(shí)現(xiàn)了實(shí)時(shí)處理數(shù)據(jù)流計(jì)算，彌補(bǔ)了Hadoop、Spark等批處理系統(tǒng)所不能滿足的實(shí)時(shí)要求。Storm主要分為Nimbus和Supervisor兩種組件，這兩種組件都是無狀態(tài)且快速失敗的。與S4相同的是Storm通過Zookeeper進(jìn)行任務(wù)分配與心跳檢測，不同的是Storm利用消息反饋機(jī)制保證數(shù)據(jù)記錄被完全處理。Storm被廣泛應(yīng)用于實(shí)時(shí)分析、在線機(jī)器學(xué)習(xí)、持續(xù)計(jì)算、分布式遠(yuǎn)程調(diào)用等領(lǐng)域。

3.2.3 Spark Streaming

Spark Streaming于2012年被開源，它是核心Spark API的一個(gè)擴(kuò)展，Spark Streaming與Spark相同，均采用了RDD(彈性分布式數(shù)據(jù)集)機(jī)制。在數(shù)據(jù)處理方面，Spark Streaming引入微批次的概念，它并不會像Storm那樣一次一個(gè)地處理數(shù)據(jù)流，而是在處理前按時(shí)間間隔預(yù)先將其切分為一段一段的批處理作業(yè)，把對數(shù)據(jù)流的處理看作是批處理操作。但是由于基于RDD轉(zhuǎn)換的操作能力有限，并且微批次處理增加了數(shù)據(jù)處理延遲，所以Spark Streaming還有很大的改進(jìn)空間。

3.2.4 Samza

Samza于2013年由LinkedIn公司開源。與Storm和Spark Streaming不同的是，Samza以一條條消息作為數(shù)據(jù)流處理的單位。在Samza中，數(shù)據(jù)流被切分開來，每個(gè)部分都由一組只讀消息的有序數(shù)列構(gòu)成，而這些消息每條都有一個(gè)特定的ID(offset)。該系統(tǒng)也支持批處理，即逐次處理同一個(gè)數(shù)據(jù)流分區(qū)的多條消息。盡管Samza的數(shù)據(jù)傳輸依賴于Kafka，并且需要依靠Yarn來完成資源調(diào)度，Samza的執(zhí)行與數(shù)據(jù)流模塊卻是可插拔式的。

4 結(jié)論

本文系統(tǒng)地介紹了數(shù)據(jù)流挖掘中的數(shù)據(jù)流模型和支撐技術(shù)。結(jié)合數(shù)據(jù)流挖掘技術(shù)的發(fā)展，對分布式數(shù)據(jù)流挖掘進(jìn)行了概述，并且詳細(xì)地介紹了分布式數(shù)據(jù)流挖掘所涉及的相關(guān)數(shù)學(xué)模型及數(shù)據(jù)流處理系統(tǒng)。這些內(nèi)容對于深入了解數(shù)據(jù)流挖掘并將其進(jìn)行實(shí)際應(yīng)用有著重要的意義。

[1] ARASU A, BABCOCK B, BABU S, et al. Stream: the stanford data stream management system[J]. Book Chapter, 2003(26):665-665.

[2] ABADI D J, CARNEY D, ?ETINTEMEL U, et al. Aurora: a new model and architecture for data stream management[J]. the VLDB Journal—the International Journal on Very Large Data Bases, 2003, 12(2): 120-139.[3] NEUMEYER L, ROBBINS B, NAIR A, et al. S4: Distributed stream computing platform[C].2010 IEEE International Conference on Data Mining Workshops. IEEE, 2010: 170-177.

[4] TOSHNIWAL A, TANEJA S, SHUKLA A, et al. Storm@ twitter[C].Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. ACM, 2014: 147-156.

[5] ZAHARIA M, DAS T, LI H, et al. Discretized streams: an efficient and fault-tolerant model for stream processing on large clusters[C].Proceedings of the 4th USENIX Conference on Hot Topics in Cloud Computing, 2012: 10.

[6] MORALES G D F, BIFET A. Samoa: scalable advanced massive online analysis[J]. Journal of Machine Learning Research, 2015, 16(1): 149-153.

[7] 孫玉芬, 盧炎生. 流數(shù)據(jù)挖掘綜述[J]. 計(jì)算機(jī)科學(xué), 2007, 34(1): 1-5.

[8] GABER M M, ZASLAVSKY A, KRISHNASWAMY S. Mining data streams: a review[J]. ACM Sigmod Record, 2005, 34(2): 18-26.

[9] 談恒貴, 王文杰, 李游華. 數(shù)據(jù)挖掘分類算法綜述[J]. 微型機(jī)與應(yīng)用, 2005, 24(2): 4-6.

[10] 謝桂蘭, 羅省賢. 基于 Hadoop MapReduce 模型的應(yīng)用研究[J]. 微型機(jī)與應(yīng)用, 2010,29(8): 4-7.

[11] 吳越. 串行算法并行化處理的數(shù)學(xué)模型與算法描述[J]. 計(jì)算機(jī)技術(shù)與發(fā)展, 2012, 22(5): 14-18.

[12] HUNT P, KONAR M, JUNQUEIRA F P, et al. ZooKeeper: wait-free coordination for Internet-scale systems[C].USENIX Annual Technical Conference, 2010, 8: 9.

A survey of distributed data streams mining technique

Wan Xingui

(School of Computer, Nanjing University of Posts and Telecommunications, Nanjing 210003,China)

The rapid development of Internet information technology has generated a new data model—data stream model. The demands for real-time processing of data stream are emerging in an increasing number of areas, large-scale and high-speed data as well as real-time application of scenarios require the further technological development of data stream mining. This thesis, at its beginning, introduces the common data stream model and then summarizes the supporting technology applied in data stream mining based on the characteristics of the data stream model. Finally, this thesis analyzes the importance and effectiveness of distributed data stream mining technology, presents the parallel algorithm mathematical model and introduces several representative distributed data stream processing system.

data stream model; data stream mining; distributed; parallel; data stream processing system

TP311

A

10.19358/j.issn.1674- 7720.2016.21.002

萬新貴. 分布式數(shù)據(jù)流挖掘技術(shù)綜述[J].微型機(jī)與應(yīng)用，2016,35(21)：8-10,13.

2016-08-10)

萬新貴(1991-)，通信作者，女，碩士研究生，主要研究方向：流數(shù)據(jù)挖掘。E-mail:15850795019@163.com。