萬新貴

       （南京郵電大學 計算機學院，江蘇 南京 210003）

　　摘要：網絡信息技術的高速發展產生了新的數據模型，即數據流模型，并且越來越多的領域出現了對數據流實時處理的需求，龐大且高速的數據以及應用場景的實時性需求均推進了數據流挖掘技術的發展。首先介紹了常見的數據流模型；然后根據數據流模型的特點總結數據流挖掘的支撐技術；最后，分析了分布式數據流挖掘的重要性和有效性，給出了算法并行化的數學模型，并介紹了幾種具有代表性的分布式數據流處理系統。

　　關鍵詞：數據流模型；數據流挖掘；分布式；并行化；數據流處理系統

0引言

　　數據流(Data Stream)常常產生于Web上的用戶點擊、網絡入侵檢測、實時監控系統或無線傳感器網絡等動態環境中。與傳統數據集相比較，這些海量的數據流具有快速性、連續性、變化性、無限性等特點。海量的數據流、復雜的數學模型和高要求的時效性使得傳統的數據挖掘面臨巨大的挑戰，數據流挖掘技術得到了迅猛的發展。

　　20世紀初，出現了諸如STREAM［1］、Aurora［2］等數據流管理系統(Data Stream Management System)。早期的數據流管理系統應用領域較為單一，并且大多采用集中式架構，雖然提供了基本算子，但是算子與底層模塊的耦合度較高，難以實現擴展開發。隨著技術的發展和需求的提升，分布式技術對數據流處理的重要性顯現出來。

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

1數據流模型

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

　　目前的數據流研究領域存在多種數據流模型，根據數據流模型自身的特點，可以從兩個方面對數據流模型進行分類［7］，分別是按照數據流中數據描述現象的方式和算法處理數據流時所采用的時序范圍。

　　1.1按照描述現象的方式分類

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

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

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

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

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

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

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

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

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

2支撐技術

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

　　2.1基于數據的技術

　　數據挖掘與查詢需要讀取掃描過的數據［9］，但是由于數據流的數據量遠大于數據流處理系統的可用內存，不能保證所有數據都能被存儲。因此數據流處理系統需要維持一個概要數據結構，用于保留掃描過的信息。生成數據流概要信息的主要方法有：抽樣、梗概和大綱數據結構等。

　　(1)抽樣：屬于傳統的統計學方法，通過一定概率決定數據是否被處理。抽樣技術的弊端是，數據流的長度無法預測，并且數據流的流速不穩定。

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

　　(3)大綱數據結構：通過應用概要技術生成比原始數據流小得多的數據概要，是當前數據流的概要描述。直方圖、小波變換分析和哈希方法都屬于大綱數據結構。

　　2.2基于任務的技術

　　在算法與應用方面，基于任務的技術可以在時間和空間上更好地進行數據流的處理，目前主要的基于任務的技術包括：滑動窗口、傾斜時間框架、衰減因子。

　　(1)滑動窗口：用戶往往對最近的數據更感興趣，因此只需要保留少量最近的數據并對其進行分析，而對于大量的歷史數據，只需要保留概要結構。這樣，既滿足了用戶需求，又減少了內存開銷。滑動窗口的大小需要用戶自定義，但在大多數應用中，該窗口的大小是無法預知的，因此，這是滑動窗口的一個較大的缺陷。

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

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

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

3分布式數據流挖掘

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

　　分布式數據流挖掘是指基于分布式流處理系統，實現算法的分布式并行化，達到算法的有效性和時效性。分布式流處理系統采用分布式架構，區別于Hadoop［10］之類的處理平臺，其處理能力隨著節點數目的增長而擴展，具備良好的伸縮性。并且，大多分布式數據流處理系統分離了計算邏輯和基礎模塊，系統只負責數據的傳輸與任務的分配，具體的處理流程和計算單元則由用戶自己定義。

　　在分布式數據流處理系統上實現算法，首先需要根據系統的編程模型設計算法的分布式架構，其次要實現算法的并行化。并行化后的算法能夠在分布式平臺上取得更好的效果。

　　3.1并行化數學模型

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

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

　　(1)有向帶權圖模型

　　一個串行程序可以抽象為一個有向帶權圖，程序中的所有函數為構成圖的節點，節點的相關程度作為權值，函數之間的調用關系構成圖的邊，這樣的圖稱為函數調用圖。同理，一個函數也可以這樣被拆分。

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

　　(2)集合劃分模型

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

　　(3)標記AVL樹模型

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

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

　　3.2分布式數據流處理系統

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

　　3.2.1S4

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

　　3.2.2Storm

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

　　3.2.3Spark Streaming

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

　　3.2.4Samza

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

4結論

　　本文系統地介紹了數據流挖掘中的數據流模型和支撐技術。結合數據流挖掘技術的發展，對分布式數據流挖掘進行了概述，并且詳細地介紹了分布式數據流挖掘所涉及的相關數學模型及數據流處理系統。這些內容對于深入了解數據流挖掘并將其進行實際應用有著重要的意義。

　　參考文獻

　　［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］ 孫玉芬, 盧炎生. 流數據挖掘綜述［J］. 計算機科學, 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］ 談恒貴, 王文杰, 李游華. 數據挖掘分類算法綜述［J］. 微型機與應用, 2005, 24(2): 4-6.

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

　　［11］ 吳越. 串行算法并行化處理的數學模型與算法描述［J］. 計算機技術與發展, 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.