萬(wàn)新貴

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

　　摘要：網(wǎng)絡(luò)信息技術(shù)的高速發(fā)展產(chǎn)生了新的數(shù)據(jù)模型，即數(shù)據(jù)流模型，并且越來(lái)越多的領(lǐng)域出現(xiàn)了對(duì)數(shù)據(jù)流實(shí)時(shí)處理的需求，龐大且高速的數(shù)據(jù)以及應(yīng)用場(chǎng)景的實(shí)時(shí)性需求均推進(jìn)了數(shù)據(jù)流挖掘技術(shù)的發(fā)展。首先介紹了常見(jiàn)的數(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ò)入侵檢測(cè)、實(shí)時(shí)監(jiān)控系統(tǒng)或無(wú)線傳感器網(wǎng)絡(luò)等動(dòng)態(tài)環(huán)境中。與傳統(tǒng)數(shù)據(jù)集相比較，這些海量的數(shù)據(jù)流具有快速性、連續(xù)性、變化性、無(wú)限性等特點(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ò)展開(kāi)發(fā)。隨著技術(shù)的發(fā)展和需求的提升，分布式技術(shù)對(duì)數(shù)據(jù)流處理的重要性顯現(xiàn)出來(lái)。

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

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

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

　　目前的數(shù)據(jù)流研究領(lǐng)域存在多種數(shù)據(jù)流模型，根據(jù)數(shù)據(jù)流模型自身的特點(diǎn)，可以從兩個(gè)方面對(duì)數(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)門(mén)(Turnstile)模型，其中十字轉(zhuǎn)門(mén)模型的適用范圍最廣，但也是最難處理的。

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

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

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

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

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

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

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

　　(3)滑動(dòng)窗口模型：處理數(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ù)挖掘與查詢需要讀取掃描過(guò)的數(shù)據(jù)［9］，但是由于數(shù)據(jù)流的數(shù)據(jù)量遠(yuǎn)大于數(shù)據(jù)流處理系統(tǒng)的可用內(nèi)存，不能保證所有數(shù)據(jù)都能被存儲(chǔ)。因此數(shù)據(jù)流處理系統(tǒng)需要維持一個(gè)概要數(shù)據(jù)結(jié)構(gòu)，用于保留掃描過(guò)的信息。生成數(shù)據(jù)流概要信息的主要方法有：抽樣、梗概和大綱數(shù)據(jù)結(jié)構(gòu)等。

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

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

　　(3)大綱數(shù)據(jù)結(jié)構(gòu)：通過(guò)應(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ù)包括：滑動(dòng)窗口、傾斜時(shí)間框架、衰減因子。

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

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

　　(3)傾斜時(shí)間框架：也稱為多窗口技術(shù)，滑動(dòng)窗口與衰減因子只能在一個(gè)粒度的窗口上操作。但是，多數(shù)應(yīng)用會(huì)需要在不同粒度的窗口上進(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)下，對(duì)數(shù)據(jù)流進(jìn)行有效的處理。

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

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

　　分布式數(shù)據(jù)流挖掘是指基于分布式流處理系統(tǒng)，實(shí)現(xiàn)算法的分布式并行化，達(dá)到算法的有效性和時(shí)效性。分布式流處理系統(tǒng)采用分布式架構(gòu)，區(qū)別于Hadoop［10］之類的處理平臺(tái)，其處理能力隨著節(jié)點(diǎn)數(shù)目的增長(zhǎng)而擴(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)算法的并行化。并行化后的算法能夠在分布式平臺(tái)上取得更好的效果。

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

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

　　一般直接編寫(xiě)并行程序是相當(dāng)困難的，而且各領(lǐng)域使用的串行算法已經(jīng)相當(dāng)成熟，所以如何將串行算法轉(zhuǎn)換為并行算法成為研究的重點(diǎn)。參考文獻(xiàn)［11］分析了串行算法并行化的可行性并總結(jié)了有向帶權(quán)圖模型、集合劃分模型和標(biāo)記AVL樹(shù)模型三種將串行算法并行化的數(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)系，這樣的圖代表的串行程序是不易并行化的；而非連通圖代表的串行程序是較易并行化的。需要對(duì)每個(gè)連通分支進(jìn)行不斷劃分，直到劃分至最小原子為止。

　　(2)集合劃分模型

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

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

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

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

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

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

　　3.2.1S4

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

　　3.2.2Storm

　　Storm于2011年由Twitter公司開(kāi)源，是一個(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兩種組件，這兩種組件都是無(wú)狀態(tài)且快速失敗的。與S4相同的是Storm通過(guò)Zookeeper進(jìn)行任務(wù)分配與心跳檢測(cè)，不同的是Storm利用消息反饋機(jī)制保證數(shù)據(jù)記錄被完全處理。Storm被廣泛應(yīng)用于實(shí)時(shí)分析、在線機(jī)器學(xué)習(xí)、持續(xù)計(jì)算、分布式遠(yuǎn)程調(diào)用等領(lǐng)域。

　　3.2.3Spark Streaming

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

　　3.2.4Samza

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

4結(jié)論

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

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