萬新貴

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

　　摘要：網(wǎng)絡(luò)信息技術(shù)的高速發(fā)展產(chǎn)生了新的數(shù)據(jù)模型,，即數(shù)據(jù)流模型,，并且越來越多的領(lǐng)域出現(xiàn)了對數(shù)據(jù)流實時處理的需求，龐大且高速的數(shù)據(jù)以及應(yīng)用場景的實時性需求均推進(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),。

　　關(guān)鍵詞：數(shù)據(jù)流模型,；數(shù)據(jù)流挖掘；分布式,；并行化,；數(shù)據(jù)流處理系統(tǒng)

0引言

　　數(shù)據(jù)流(Data Stream)常常產(chǎn)生于Web上的用戶點(diǎn)擊、網(wǎng)絡(luò)入侵檢測,、實時監(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é)模型和高要求的時效性使得傳統(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)擴(kuò)展開發(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)成為熱點(diǎn),。

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

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

　　目前的數(shù)據(jù)流研究領(lǐng)域存在多種數(shù)據(jù)流模型,，根據(jù)數(shù)據(jù)流模型自身的特點(diǎn),，可以從兩個方面對數(shù)據(jù)流模型進(jìn)行分類［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ù)看作獨(dú)立的對象,。

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

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

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

　　部分算法并不將數(shù)據(jù)流的數(shù)據(jù)作為處理對象，而是選取某個時間范圍的數(shù)據(jù)進(jìn)行處理,，按照算法處理數(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ù)的范圍由固定窗口的大小決定,，窗口的終點(diǎn)永遠(yuǎn)是當(dāng)前時間,。

2支撐技術(shù)

　　根據(jù)數(shù)據(jù)流的特點(diǎn)，數(shù)據(jù)流處理技術(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ù),，力圖在時間和空間上得到更有效的解決方法,。

　　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)需要維持一個概要數(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ù)做隨機(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ù)可以在時間和空間上更好地進(jìn)行數(shù)據(jù)流的處理,，目前主要的基于任務(wù)的技術(shù)包括：滑動窗口、傾斜時間框架,、衰減因子,。

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

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

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

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

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

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

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

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

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

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

　　一般直接編寫并行程序是相當(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)圖模型

　　一個串行程序可以抽象為一個有向帶權(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)用圖,。同理,，一個函數(shù)也可以這樣被拆分。

　　有向帶權(quán)圖分為連通圖與非連通圖,，在函數(shù)調(diào)用圖中,，連通圖表示各函數(shù)之間均存在調(diào)用關(guān)系，這樣的圖代表的串行程序是不易并行化的；而非連通圖代表的串行程序是較易并行化的,。需要對每個連通分支進(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)的兩個子樹的高度最大差別為一，所以它也被稱為高度平衡樹,。當(dāng)AVL樹增加或者刪除節(jié)點(diǎn)導(dǎo)致樹失去平衡時,，AVL樹通過旋轉(zhuǎn)使樹重新達(dá)到平衡。

　　使用AVL樹模型并行化串行算法的前提是,，AVL旋轉(zhuǎn)不會影響函數(shù)之間的調(diào)用關(guān)系,。在此前提下，基于有向帶權(quán)圖模型,，將圖中的一個連通分支作為根節(jié)點(diǎn),，分解該圖。每進(jìn)行一次分解,，AVL樹就增加兩個子節(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)的各項特點(diǎn)。

　　3.2.1S4

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

　　3.2.2Storm

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

　　3.2.3Spark Streaming

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

　　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ù)流挖掘進(jìn)行了概述，并且詳細(xì)地介紹了分布式數(shù)據(jù)流挖掘所涉及的相關(guān)數(shù)學(xué)模型及數(shù)據(jù)流處理系統(tǒng),。這些內(nèi)容對于深入了解數(shù)據(jù)流挖掘并將其進(jìn)行實際應(yīng)用有著重要的意義,。

　　參考文獻(xiàn)

　　［1］ 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.

　　［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.

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

　　［7］ 孫玉芬, 盧炎生. 流數(shù)據(jù)挖掘綜述［J］. 計算機(jī)科學(xué), 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.

　?。?］ 談恒貴, 王文杰, 李游華. 數(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.

　?。?1］ 吳越. 串行算法并行化處理的數(shù)學(xué)模型與算法描述［J］. 計算機(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.