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

萬新貴

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

?

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

萬新貴

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

網(wǎng)絡(luò)信息技術(shù)的高速發(fā)展產(chǎn)生了新的數(shù)據(jù)模型，即數(shù)據(jù)流模型，并且越來越多的領(lǐng)域出現(xiàn)了對數(shù)據(jù)流實時處理的需求，龐大且高速的數(shù)據(jù)以及應(yīng)用場景的實時性需求均推進了數(shù)據(jù)流挖掘技術(shù)的發(fā)展。首先介紹了常見的數(shù)據(jù)流模型；然后根據(jù)數(shù)據(jù)流模型的特點總結(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上的用戶點擊、網(wǎng)絡(luò)入侵檢測、實時監(jiān)控系統(tǒng)或無線傳感器網(wǎng)絡(luò)等動態(tài)環(huán)境中。與傳統(tǒng)數(shù)據(jù)集相比較，這些海量的數(shù)據(jù)流具有快速性、連續(xù)性、變化性、無限性等特點。海量的數(shù)據(jù)流、復(fù)雜的數(shù)學(xué)模型和高要求的時效性使得傳統(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)，雖然提供了基本算子，但是算子與底層模塊的耦合度較高，難以實現(xiàn)擴展開發(fā)。隨著技術(shù)的發(fā)展和需求的提升，分布式技術(shù)對數(shù)據(jù)流處理的重要性顯現(xiàn)出來。

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

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

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

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

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

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

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

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

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

1.2 按照算法所采用的時序范圍分類

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

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

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

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

2 支撐技術(shù)

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

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

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

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

(2)梗概：是將數(shù)據(jù)流中的數(shù)據(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ù)流的處理，目前主要的基于任務(wù)的技術(shù)包括：滑動窗口、傾斜時間框架、衰減因子。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2)集合劃分模型

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

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

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

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

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

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

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

3.2.1 S4

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

3.2.2 Storm

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

3.2.3 Spark Streaming

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

3.2.4 Samza

Samza于2013年由LinkedIn公司開源。與Storm和Spark Streaming不同的是，Samza以一條條消息作為數(shù)據(jù)流處理的單位。在Samza中，數(shù)據(jù)流被切分開來，每個部分都由一組只讀消息的有序數(shù)列構(gòu)成，而這些消息每條都有一個特定的ID(offset)。該系統(tǒng)也支持批處理，即逐次處理同一個數(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ù)流挖掘進行了概述，并且詳細地介紹了分布式數(shù)據(jù)流挖掘所涉及的相關(guān)數(shù)學(xué)模型及數(shù)據(jù)流處理系統(tǒng)。這些內(nèi)容對于深入了解數(shù)據(jù)流挖掘并將其進行實際應(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]. 計算機科學(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]. 微型機與應(yīng)用, 2005, 24(2): 4-6.

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

[11] 吳越. 串行算法并行化處理的數(shù)學(xué)模型與算法描述[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].微型機與應(yīng)用，2016,35(21)：8-10,13.

2016-08-10)

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