萬新貴
(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院,江蘇 南京 210003)
摘要:網(wǎng)絡(luò)信息技術(shù)的高速發(fā)展產(chǎn)生了新的數(shù)據(jù)模型,,即數(shù)據(jù)流模型,,并且越來越多的領(lǐng)域出現(xiàn)了對(duì)數(shù)據(jù)流實(shí)時(shí)處理的需求,龐大且高速的數(shù)據(jù)以及應(yīng)用場(chǎ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),。
關(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ǎng)絡(luò)等動(dòng)態(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ù)對(duì)數(shù)據(jù)流處理的重要性顯現(xiàn)出來,。
21世紀(jì)初,,隨著各類開放式計(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)集合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è)方面對(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)門(Turnstile)模型,,其中十字轉(zhuǎ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)門(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ù)(Databased)的技術(shù),,旨在以小范圍的數(shù)據(jù)代替所有數(shù)據(jù),達(dá)到數(shù)據(jù)流處理方法的高性能,;另一種是基于任務(wù)(Taskbased)的技術(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ù)都能被存儲(chǔ)。因此數(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ù)流的長(zhǎng)度無法預(yù)測(cè),,并且數(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ù)包括:滑動(dòng)窗口,、傾斜時(shí)間框架,、衰減因子。
(1)滑動(dòng)窗口:用戶往往對(duì)最近的數(shù)據(jù)更感興趣,因此只需要保留少量最近的數(shù)據(jù)并對(duì)其進(jìn)行分析,,而對(duì)于大量的歷史數(shù)據(jù),,只需要保留概要結(jié)構(gòu)。這樣,,既滿足了用戶需求,,又減少了內(nèi)存開銷?;瑒?dòng)窗口的大小需要用戶自定義,,但在大多數(shù)應(yīng)用中,該窗口的大小是無法預(yù)知的,,因此,,這是滑動(dòng)窗口的一個(gè)較大的缺陷。
(2)衰減因子:衰減因子是另一種強(qiáng)調(diào)近期數(shù)據(jù)重要性的方式,,它衰減了歷史數(shù)據(jù)對(duì)計(jì)算結(jié)果的影響,。數(shù)據(jù)在計(jì)算之前,先經(jīng)過衰減函數(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),,通過對(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è)重要前提,。
一般直接編寫并行程序是相當(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)系,這樣的圖代表的串行程序是不易并行化的,;而非連通圖代表的串行程序是較易并行化的,。需要對(duì)每個(gè)連通分支進(jìn)行不斷劃分,直到劃分至最小原子為止,。
(2)集合劃分模型
集合劃分模型是為了解決如何搜索權(quán)值最小的邊以及如何基于連通圖進(jìn)行并行劃分,。運(yùn)用二元關(guān)系的相關(guān)知識(shí)建立模型,基于有向帶權(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)不會(huì)影響函數(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對(duì)比了這4種分布式數(shù)據(jù)流處理系統(tǒng)的各項(xiàng)特點(diǎn),。
3.2.1S4
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ì)算單元會(huì)以PE的形式存在,,每個(gè)PE只能處理key值相同的事件。雖然系統(tǒng)的伸縮性和擴(kuò)展性良好,,但缺乏消息處理的反饋機(jī)制,,無法進(jìn)行有效的故障恢復(fù)等。
3.2.2Storm
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ù)分配與心跳檢測(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年被開源,它是核心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公司開源。與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ā)展,對(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)
?。?] 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.
[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.
?。?] 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 faulttolerant 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.
?。?] 孫玉芬, 盧炎生. 流數(shù)據(jù)挖掘綜述[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.
[9] 談恒貴, 王文杰, 李游華. 數(shù)據(jù)挖掘分類算法綜述[J]. 微型機(jī)與應(yīng)用, 2005, 24(2): 4-6.
?。?0] 謝桂蘭, 羅省賢. 基于 Hadoop MapReduce 模型的應(yīng)用研究[J]. 微型機(jī)與應(yīng)用, 2010,29(8): 4-7.
?。?1] 吳越. 串行算法并行化處理的數(shù)學(xué)模型與算法描述[J]. 計(jì)算機(jī)技術(shù)與發(fā)展, 2012, 22(5): 14-18.
[12] HUNT P, KONAR M, JUNQUEIRA F P, et al. ZooKeeper: waitfree coordination for Internetscale systems[C].USENIX Annual Technical Conference, 2010, 8: 9.