羅 莎 朱 威 王培源 鄒 彤 郭唐永

(中國地震局地震研究所，武漢 430071)

網(wǎng)絡(luò)數(shù)據(jù)流分析方法*

羅 莎 朱 威 王培源 鄒 彤 郭唐永

(中國地震局地震研究所，武漢 430071)

介紹網(wǎng)絡(luò)數(shù)據(jù)流中最主要的數(shù)據(jù)流挖掘技術(shù)。

數(shù)據(jù)流;網(wǎng)絡(luò)數(shù)據(jù);分析;數(shù)據(jù)流挖掘;技術(shù)

1 引言

在網(wǎng)絡(luò)安全越來越受到重視的今天，如何對網(wǎng)絡(luò)數(shù)據(jù)進行分析，從中得到有用的信息或找到攻擊線索，已成為計算機網(wǎng)絡(luò)領(lǐng)域的一個新興課題。

由于網(wǎng)絡(luò)數(shù)據(jù)日益豐富多樣，并大量地、源源不斷地產(chǎn)生，并以數(shù)據(jù)流的形式存在，使得網(wǎng)絡(luò)數(shù)據(jù)流(Data Stream)的處理逐漸成為當前網(wǎng)絡(luò)與數(shù)據(jù)庫領(lǐng)域新的研究熱點。本文將詳細介紹網(wǎng)絡(luò)數(shù)據(jù)流的分析方法。

2 基于數(shù)據(jù)流的網(wǎng)絡(luò)流量分析

在網(wǎng)絡(luò)數(shù)據(jù)包高速到達的情況下實時地對網(wǎng)絡(luò)數(shù)據(jù)流進行監(jiān)測是極具挑戰(zhàn)性的工作，同時對網(wǎng)絡(luò)流量統(tǒng)計、監(jiān)控，查詢管理及異常和入侵檢測等方面都具有重大的意義。當今影響網(wǎng)絡(luò)性能的事件多具有突發(fā)性，在突發(fā)點，網(wǎng)絡(luò)業(yè)務(wù)流量突然出現(xiàn)不正常的重大變化，流量值的變化范圍超過了上千倍，并且增長迅速，沒有任何加速過程。這種變化對網(wǎng)絡(luò)服務(wù)和網(wǎng)絡(luò)性能的影響勢必是災(zāi)難性的。因此如何在盡可能短的時間內(nèi)盡可能地準確發(fā)現(xiàn)這些異常并快速定位異常，采取相應(yīng)措施具有非常重要的意義。而數(shù)據(jù)流分析則提供了一種行之有效的方法。

在網(wǎng)絡(luò)流量突發(fā)異常檢測中，采用數(shù)據(jù)流的方法，可以在數(shù)據(jù)高速海量特點的前提下，從網(wǎng)絡(luò)流量中提取出有效的摘要結(jié)構(gòu)，執(zhí)行單遍掃描算法實時檢測異常。數(shù)據(jù)流中的關(guān)鍵技術(shù)(數(shù)據(jù)流的管理技術(shù)和對數(shù)據(jù)流挖掘技術(shù))和數(shù)據(jù)流相關(guān)算法(作為管理及挖掘的基礎(chǔ)的數(shù)據(jù)摘要生成算法;主要面向管理的數(shù)據(jù)流統(tǒng)計查詢算法;以及數(shù)據(jù)流分類、高頻項挖掘、聚類、變化及異常發(fā)現(xiàn)等挖掘算法)可以作為網(wǎng)絡(luò)流量突發(fā)異常檢測中的研究手段，以解決實時性檢測的問題［1］。

3 數(shù)據(jù)流的定性分析和多維分析

內(nèi)容分析法、相關(guān)分析法、對比分析法、歸納分析法和推理分析法是網(wǎng)絡(luò)數(shù)據(jù)分析最常用的和最基本的方法，同樣可以應(yīng)用于數(shù)據(jù)流的分析。

多維聯(lián)機分析處理(OLAP)具有強大的分析功能，OLAP系統(tǒng)可以提供給用戶強大的統(tǒng)計、分析(包括時間序列分析、非過程化建模、多維結(jié)構(gòu)的隨機變化等)、報表處理功能。多維分析的主要特點有：快速性、可分析性、多維性、交互性、信息性和共享性。這些特點使得OLAP系統(tǒng)適用于數(shù)據(jù)流這種無限量、頻繁變化并需要快速的響應(yīng)的數(shù)據(jù)的分析。

另外，在一個OLAP數(shù)據(jù)模型中，信息被抽象地視為一個立方體，它包括維和度量。這個多維的數(shù)據(jù)模型使終端用戶提交的復(fù)雜查詢、報表數(shù)據(jù)的分類排列、概要數(shù)據(jù)向詳細數(shù)據(jù)的轉(zhuǎn)化和過濾、數(shù)據(jù)的切片等工作變得簡單。數(shù)據(jù)流的概要技術(shù)正好可以與該多維數(shù)據(jù)模型結(jié)合使用。

OLAP的功能有：對數(shù)據(jù)的多維觀察;復(fù)雜的計算能力;時間智能;管理功能。其中時間智能是指OLAP系統(tǒng)能夠很好地理解時間的序列性。而數(shù)據(jù)流是一個按照時間遞增順序排列的無窮序列，可以利用OLAP對時間的智能管理功能進行分析［2］。

4 網(wǎng)絡(luò)數(shù)據(jù)流挖掘

挖掘技術(shù)是數(shù)據(jù)分析的關(guān)鍵技術(shù)，目前比較成熟并且應(yīng)用較廣泛的有數(shù)據(jù)挖掘技術(shù)，還有適應(yīng)網(wǎng)絡(luò)發(fā)展需要而產(chǎn)生的網(wǎng)絡(luò)數(shù)據(jù)挖掘。網(wǎng)絡(luò)數(shù)據(jù)流的分析就可以利用數(shù)據(jù)流挖掘技術(shù)。

4.1 數(shù)據(jù)流挖掘

數(shù)據(jù)流(Data Stream)是實時的、連續(xù)的、有序的項的序列，由到達時間隱含表示或顯示地由時間戳制定。按照固定的次序，這些數(shù)據(jù)項只能被讀取一次。因此，按照數(shù)據(jù)項到達的順序，將數(shù)據(jù)流完整地存儲到本地是不可能的［3］。

數(shù)據(jù)流的特點是：有序性、連續(xù)性、實時性;無限性;單遍性;概要性;低層次性和多維性;近似性;即時性。

數(shù)據(jù)挖掘是指從海量數(shù)據(jù)中發(fā)現(xiàn)一些有趣的趨勢或模式，以便指導有關(guān)未來的活動的決策。數(shù)據(jù)挖掘與傳統(tǒng)的數(shù)據(jù)分析的本質(zhì)區(qū)別是數(shù)據(jù)挖掘是在沒有明確假設(shè)的前提下去挖掘信息、發(fā)現(xiàn)知識。數(shù)據(jù)挖掘所得到的信息應(yīng)具有先前未知、有效和可實用3個特征。數(shù)據(jù)流挖掘就是在數(shù)據(jù)流上發(fā)現(xiàn)提取隱含在其中的、人們事先不知道的、但又潛在有用的信息的過程。

4.2 數(shù)據(jù)流挖掘技術(shù)

哈爾濱焊接研究院有限公司研發(fā)中心副主任黃瑞生先生做了題目為“厚壁鋁合金窄間隙激光填絲焊接技術(shù)”的報告，報告重點介紹了針對5A06鋁合金大厚板焊接需求，采用激光光束以一定軌跡運動的掃描焊接方法，研究了激光束不同運動軌跡對鋁合金激光深熔焊接焊縫成形及氣孔的影響，在此基礎(chǔ)上應(yīng)用掃描激光填絲焊接技術(shù)焊接了130mm厚5A06鋁合金，并對焊接接頭組織、性能進行分析。

傳統(tǒng)數(shù)據(jù)挖掘需要隨機訪問數(shù)據(jù)，應(yīng)用在數(shù)據(jù)流上需要動態(tài)挖掘，即考慮流數(shù)據(jù)的實效性和動態(tài)性，數(shù)據(jù)流內(nèi)在分布變化及算法單遍的限制。目前數(shù)據(jù)流挖掘技術(shù)主要有：數(shù)據(jù)流的聚類分析、數(shù)據(jù)流的分類分析和數(shù)據(jù)流的頻繁模式挖掘［4］。

1)數(shù)據(jù)流的聚類分析

聚類是一種無監(jiān)督學習方法。根據(jù)內(nèi)間相似度最小而內(nèi)部相似度最大的原則，將數(shù)據(jù)集分為若干簇。在數(shù)據(jù)流挖掘中，聚類可以看作一種數(shù)據(jù)壓縮工具，它在日志分析和點擊流分析中廣泛應(yīng)用。數(shù)據(jù)流的聚類就是通過單遍掃描數(shù)據(jù)流，持續(xù)地將數(shù)據(jù)流數(shù)據(jù)對象分組成多個類或簇，在同一個簇中的數(shù)據(jù)對象之間具有較高的相似度，而不同簇間的數(shù)據(jù)對象的相似度很小。因為數(shù)據(jù)流可看成是隨時間不斷變化的無限過程，其隱含的聚類可能隨時間動態(tài)地變化而導致聚類質(zhì)量減低。

聚類算法可以分成劃分方法、基于層次的方法和基于密度的方法等幾類，算法的選擇取決于數(shù)據(jù)的類型、聚類的目的和應(yīng)用。數(shù)據(jù)流的聚類算法不同于傳統(tǒng)數(shù)據(jù)的聚類算法，必須是增量式的，對聚類的表示要簡潔，對新數(shù)據(jù)的處理要快速，對噪音和異常數(shù)據(jù)必須是穩(wěn)健的。因此，基于數(shù)據(jù)流的聚類算法要在一個相對較小的內(nèi)存空間上，對數(shù)據(jù)流進行一遍掃描后，把數(shù)據(jù)集合分為一個個簇集。

Guha等人［5，6］提出流數(shù)據(jù)聚類算法 STREAM算法是對完整數(shù)據(jù)流的聚類算法，它忽略了流數(shù)據(jù)是隨時間演化的，以及在不同的時間所呈現(xiàn)的模式不同。Babcock等人［7］提出了在固定尺寸的時間窗內(nèi)的聚類算法，算法所解決的是如何在一個有限的時間窗內(nèi)對流數(shù)據(jù)進行有效聚類，由于流數(shù)據(jù)是海量的，而算法所能分析的時間窗內(nèi)的數(shù)據(jù)是有限的，不能對歷史的數(shù)據(jù)聚類。Aggarwal等人［8］提出一個數(shù)據(jù)流的聚類演化框架Glustream，在這個框架中，將數(shù)據(jù)流的聚類分成在線微聚類與離線宏聚類兩個階段，微聚類在線統(tǒng)計流數(shù)據(jù)的類信息，離線宏聚類利用存儲的快照來進行聚類，該算法實現(xiàn)近期數(shù)據(jù)的聚類，同時實現(xiàn)了用戶指定時間段的聚類。

2)數(shù)據(jù)流的分類分析

分類是一種有監(jiān)督的學習方法。數(shù)據(jù)流上的分類就是提出一個分類模型，并通過單遍掃描數(shù)據(jù)流，持續(xù)地利用分類模型將數(shù)據(jù)對象影射到某一個給定的類別中。

針對數(shù)據(jù)流的分類，Domingos等人［9］提出了一種高效的增量決策樹算法——VFDT(Very Fast Decision Tree)。VFDT能用固定的內(nèi)存和固定的時間為每個樣本構(gòu)建一棵決策樹，有效地解決了時間、內(nèi)存和樣本對高速數(shù)據(jù)流上的數(shù)據(jù)挖掘的限制。它利用Hoeffding邊界來保證算法的輸出模型與批量學習(batchlearner)的輸出模型是趨向于一致的。

3)數(shù)據(jù)流的頻繁模式挖掘［11］

數(shù)據(jù)流頻繁模式挖掘方法是要挖掘近似的頻繁模式。在數(shù)據(jù)流上挖頻繁模式是具有挑戰(zhàn)性的，因為挖掘頻繁項集是必須的，但關(guān)聯(lián)是一個典型的塊操作，例如，任何一個項集的計算在沒有過去和將來數(shù)據(jù)的集時是不完全的。既然我們只能保持一個有限窗口中的數(shù)據(jù)，在動態(tài)環(huán)境下挖掘和更新頻繁模式是有難度的。Giannella等人［12］用 FP-tree(Frequent Pattern tree)為數(shù)據(jù)結(jié)構(gòu)，并在此基礎(chǔ)上提出了FP-Stream算法。該算法采用傾斜時間窗口技術(shù)來維護頻繁模式以解決數(shù)據(jù)流頻繁模式挖掘中的時問敏感問題。

FP-stream結(jié)構(gòu)包括兩部分：一個用來捕獲頻繁和準頻繁項信息的頻繁模式樹(FP-tree)和為每個頻繁模式提供的傾斜時間窗口(tilted-time window)表。

4.3 K-means算法原理

聚類分析是數(shù)據(jù)挖掘的一個重要分支，針對數(shù)據(jù)流的聚類分析已經(jīng)成為了當今知識發(fā)現(xiàn)與數(shù)據(jù)挖掘領(lǐng)域中的一個重要的研究熱點。K-means算法是典型的數(shù)據(jù)流聚類算法，其原理如下：

K-means算法是建立在歐式距離基礎(chǔ)上的滑動窗口內(nèi)樣本序列x=(x0，x1，…，xw-1)與y=(y0，y1，…，yw-1)之間的歐式距離為

在該算法中，每個簇(類)用該簇中對象(樣本)的平均值來表示，使所有對象到聚類中心的距離平方和最小。K-means的算法過程如下：

輸入：聚類個數(shù)k，以及包含n個數(shù)據(jù)對象的樣本集。

輸出：滿足方差最小標準的k個聚類。

處理流程：

1)從n個數(shù)據(jù)對象中任意選擇k個對象作為初始聚類中心;

2)循環(huán)下述流程3)到4)，直到每個聚類不再發(fā)生變化為止;

3)根據(jù)每個聚類中所有對象的均值(中心對象)，計算樣本集中每個對象與這些中心對象的距離，并根據(jù)最小距離重新對相應(yīng)對象進行劃分;

4)重新計算每個(有變化)聚類的均值(中心對象)。

K-means算法的特點是收斂速度較快，因此能夠適應(yīng)流數(shù)據(jù)在算法時間效率上的嚴格要求。

5 數(shù)據(jù)流挖掘研究展望

基于目前數(shù)據(jù)流挖掘的研究現(xiàn)狀，以下方面的研究將得到更多的關(guān)注：

1)數(shù)據(jù)流連續(xù)挖掘。數(shù)據(jù)流的連續(xù)、實時、無限制的特性決定了數(shù)據(jù)流的查詢是基于連續(xù)查詢或長期查詢。但在分析和挖掘數(shù)據(jù)流時，算法只能對數(shù)據(jù)流進行單遍掃描，僅能臨時存儲少量的數(shù)據(jù)，因此需要提出新的內(nèi)存駐留算法來實現(xiàn)對數(shù)據(jù)的連續(xù)查詢。支持數(shù)據(jù)流上的連續(xù)挖掘的算法通常需滿足3個條件，即基于內(nèi)存、快速和能夠適應(yīng)概念轉(zhuǎn)移。當前有關(guān)算法的研究大多是在傳統(tǒng)的增量式數(shù)據(jù)挖掘技術(shù)基礎(chǔ)之上發(fā)展而來，因此，提出更有效的數(shù)據(jù)流連續(xù)、快速挖掘算法成為當前數(shù)據(jù)流挖掘技術(shù)的一個研究熱點問題［13］。

2)半結(jié)構(gòu)化文檔挖掘由于網(wǎng)絡(luò)的大范圍使用，大量的數(shù)據(jù)被轉(zhuǎn)換成電子格式放在網(wǎng)上，但是這些數(shù)據(jù)并不是以一種同樣的格式存在，有些數(shù)據(jù)是完全無結(jié)構(gòu)的，如聲音、圖像;有些數(shù)據(jù)又有嚴格的結(jié)構(gòu)，例如數(shù)學模型、關(guān)系數(shù)據(jù)庫中的數(shù)據(jù);而更多的數(shù)據(jù)是介于兩者之間，有結(jié)構(gòu)但不嚴格，我們稱之為半結(jié)構(gòu)化的數(shù)據(jù)。當前絕大多數(shù)信息是以半結(jié)構(gòu)化形式存在的，目前研究主要解決的問題是在已有的半結(jié)構(gòu)化狀態(tài)下如何有效的利用這些信息。但是由于信息以半結(jié)構(gòu)化形式存在，因此，文檔中的語義信息殘缺不全，如何有效的提取文檔中蘊含的語義信息以及如何提取其中的數(shù)據(jù)成為當前研究的一個難點。

1 陳婷婷.基于數(shù)據(jù)流的網(wǎng)絡(luò)流量突發(fā)異常檢測［D］.哈爾濱工業(yè)大學，2006.

2 王永利.數(shù)據(jù)流概要與數(shù)據(jù)流分析若干關(guān)鍵問題研究［D］.東南大學，2006.

3 司開君，毛宇光.一種新的基于數(shù)據(jù)流的數(shù)據(jù)模型［J］.計算機技術(shù)與發(fā)展，2007，17(1)：1-4.

4 孫曉華.數(shù)據(jù)流挖掘技術(shù)研究［D］.哈爾濱理工大學，2007.

5 Guha S，et al.Clustering data streams［A］.In Proceedings of the Annual Symposium on Foundations of Computer Science［C］.IEEE，2000.

6 Guha S，et al.Clustering data streams：Theory and practice［J］.IEEE Transactions on Knowledge and Data Engineering，2003，15(3)：515-528.

7 Babcock B，et al.Maintaining variance and K-medians over data streams windows［A］.Proceedings of the 22nd Symposium on Principles of Database Systems［C］.2003.

8 Aggarwal C，et al.A framework for clustering evolving data streams［A］.Proceedings of the 29th VLDB Conference［C］.Berlin，Germany，2003.

9 Yang Ying，Wu Xindong and Zhu Xingquan.Combining proactive and reactive predictions for data streams［A］.Proc of KDD［C］.Chicago，IL，USA，2005：710-715.

10 Domingos P and Hulten G.Mining high-speed data streams［A］.Pro-ceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining［C］.Boston，USA：ACM Press，2000：71-80.

11 田玥，大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)流異常檢測系統(tǒng)的研究與實現(xiàn)［D］.東北大學，2005

12 Giannella C，et al.Mining frequent patterns in data streams at multiple time granularities［A］.In：Data Mining：Next Generation Challenges and Future Directions［C］.2004，191-212.

13 楊穎，韓忠明，楊磊，數(shù)據(jù)流的核心技術(shù)與應(yīng)用發(fā)展研究綜述［J］.計算機應(yīng)用研究，2005，11：4-7.

ANALYSIS METHODS FOR NETWORK DATA STREAM

Luo Sha，Zhu Wei，Wang Peiyuan，Zou Tong and Guo Tangyong
(Institute of Seismology，CEA，Wuhan 430071)

The analysis methods of network data stream are introduced，in which the most important part is the data stream mining technology.It has of extensive practical background and application value to research this technology.

data stream;network data;analysis;data stream mining;technology

1671-5942(2011)Supp.-0146-04

2011-04-15

羅莎，女，1985年生，碩士，主要研究方向為嵌入式數(shù)據(jù)庫的應(yīng)用和數(shù)據(jù)處理.E-mail：luoshayezi@163.com

TH76.3

A