萬新貴

       （南京郵電大學 計算機學院，江蘇 南京 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ù)學模型，并介紹了幾種具有代表性的分布式數(shù)據(jù)流處理系統(tǒng)。

　　關(guān)鍵詞：數(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ù)流、復雜的數(shù)學模型和高要求的時效性使得傳統(tǒng)的數(shù)據(jù)挖掘面臨巨大的挑戰(zhàn)，數(shù)據(jù)流挖掘技術(shù)得到了迅猛的發(fā)展。

　　20世紀初，出現(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世紀初，隨著各類開放式計算平臺的興起，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)模型、界標(Landmark)模型和滑動窗口(Sliding Window)模型，其中界標模型與滑動窗口模型使用得比較普遍。

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

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

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

2支撐技術(shù)

　　根據(jù)數(shù)據(jù)流的特點，數(shù)據(jù)流處理技術(shù)需要滿足單遍掃描、低時空復雜度等要求。為了有效地處理數(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)計學方法，通過一定概率決定數(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ù)概要，是當前數(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ù)學模型復雜。傳統(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)只負責數(shù)據(jù)的傳輸與任務(wù)的分配，具體的處理流程和計算單元則由用戶自己定義。

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

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

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

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

　　(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)標記AVL樹模型

　　AVL樹，即平衡二叉樹，在AVL樹中任何節(jié)點的兩個子樹的高度最大差別為一，所以它也被稱為高度平衡樹。當AVL樹增加或者刪除節(jié)點導致樹失去平衡時，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)的各項特點。

　　3.2.1S4

　　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)的伸縮性和擴展性良好，但缺乏消息處理的反饋機制，無法進行有效的故障恢復等。

　　3.2.2Storm

　　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)用于實時分析、在線機器學習、持續(xù)計算、分布式遠程調(diào)用等領(lǐng)域。

　　3.2.3Spark 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.4Samza

　　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ù)學模型及數(shù)據(jù)流處理系統(tǒng)。這些內(nèi)容對于深入了解數(shù)據(jù)流挖掘并將其進行實際應(yīng)用有著重要的意義。

　　參考文獻

　?。?］ ARASU A, BABCOCK B, BABU S, et al. Stream: the stanford data stream management system［J］. Book Chapter, 2003(26):665-665.

　?。?］ 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.

　?。?］ 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.

　?。?］ 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.

　?。?］ 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.

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

　?。?］ 孫玉芬, 盧炎生. 流數(shù)據(jù)挖掘綜述［J］. 計算機科學, 2007, 34(1): 1-5.

　?。?］ 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.

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

　?。?1］ 吳越. 串行算法并行化處理的數(shù)學模型與算法描述［J］. 計算機技術(shù)與發(fā)展, 2012, 22(5): 14-18.

　?。?2］ 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.