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

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

(中國地震局地震研究所，武漢 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ò)安全越來越受到重視的今天，如何對(duì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行分析，從中得到有用的信息或找到攻擊線索，已成為計(jì)算機(jī)網(wǎng)絡(luò)領(lǐng)域的一個(gè)新興課題。

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

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

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

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

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

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

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

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

OLAP的功能有：對(duì)數(shù)據(jù)的多維觀察;復(fù)雜的計(jì)算能力;時(shí)間智能;管理功能。其中時(shí)間智能是指OLAP系統(tǒng)能夠很好地理解時(shí)間的序列性。而數(shù)據(jù)流是一個(gè)按照時(shí)間遞增順序排列的無窮序列，可以利用OLAP對(duì)時(shí)間的智能管理功能進(jìn)行分析［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)是實(shí)時(shí)的、連續(xù)的、有序的項(xiàng)的序列，由到達(dá)時(shí)間隱含表示或顯示地由時(shí)間戳制定。按照固定的次序，這些數(shù)據(jù)項(xiàng)只能被讀取一次。因此，按照數(shù)據(jù)項(xiàng)到達(dá)的順序，將數(shù)據(jù)流完整地存儲(chǔ)到本地是不可能的［3］。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.3 K-means算法原理

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

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

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

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

輸出：滿足方差最小標(biāo)準(zhǔn)的k個(gè)聚類。

處理流程：

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

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

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

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

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

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

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

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

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

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

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

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

4 孫曉華.數(shù)據(jù)流挖掘技術(shù)研究［D］.哈爾濱理工大學(xué)，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)的研究與實(shí)現(xiàn)［D］.東北大學(xué)，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］.計(jì)算機(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年生，碩士，主要研究方向?yàn)榍度胧綌?shù)據(jù)庫的應(yīng)用和數(shù)據(jù)處理.E-mail：luoshayezi@163.com

TH76.3

A