數(shù)據(jù)流聚類分析與異常檢測算法.pdf

1、數(shù)據(jù)流作為一種新型的數(shù)據(jù)模型,在許多應(yīng)用諸如網(wǎng)絡(luò)流量管理、金融數(shù)據(jù)處理、工業(yè)監(jiān)控、交通治理、網(wǎng)站信息的發(fā)布和訂閱、以及電子商務(wù)中都扮演著重要的角色。在數(shù)據(jù)流挖掘技術(shù)日益得到廣泛關(guān)注的今天,存在于數(shù)據(jù)中的不確定性問題和多數(shù)流處理問題給研究人員帶來了新的挑戰(zhàn):一方面,由于不確定數(shù)據(jù)流既要求保留數(shù)據(jù)流的無限,快速等特性,還需要利用有限的系統(tǒng)資源減少不確定性因素對挖掘過程造成的影響;另一方面,多數(shù)據(jù)流處理技術(shù)則要求不僅關(guān)注于一條數(shù)據(jù)流的流量變化

2、,同時還需要根據(jù)大量數(shù)據(jù)流之間的相關(guān)性與分布特征進(jìn)行分析處理,因此我們需要重新研究新的面向多數(shù)據(jù)流及不確定數(shù)據(jù)流的挖掘算法。學(xué)術(shù)界雖然已經(jīng)對數(shù)據(jù)流上的聚類分析與異常檢測問題進(jìn)行了廣泛的研究,但仍存在許多問題尚待解決。本文主要研究不確定數(shù)據(jù)流聚類分析算法和多數(shù)據(jù)流異常趨勢檢測問題,旨在為現(xiàn)有的數(shù)據(jù)流系統(tǒng)提供更為多樣的聚類分析與異常檢測功能。同時,還對每個所提出的技術(shù)及其相關(guān)工作進(jìn)行大量、深入的實驗分析,實驗結(jié)果都充分證明了所提出技術(shù)的有效

3、性和高效性。本文的主要貢獻(xiàn)體現(xiàn)在如下四個方面:
　　本文提出了一種新的不確定數(shù)據(jù)流聚類算法(EMicro),用于在傳統(tǒng)的數(shù)據(jù)流聚類的基礎(chǔ)上解決數(shù)據(jù)不確定性給聚類過程造成的影響。首先它根據(jù)概率數(shù)據(jù)的特點定義了新的聚類標(biāo)準(zhǔn),使之能兼顧距離與概率雙重因素;然后根據(jù)新的聚類要求,提出了一種基于概率引力的元組分配策略;最后,為了有效的減少異常點對聚類結(jié)果的影響,我們提出了一套緩沖式異常點處理機(jī)制。
　　本文提出了一種基于信息論的概率數(shù)

4、據(jù)流聚類算法(EnMicro),用于在信息熵的標(biāo)準(zhǔn)下重新實現(xiàn)聚類過程。首先它基于信息熵的概念定義了元組的不確定性,并通過其來反映數(shù)據(jù)質(zhì)量的好壞;然后通過新定義的元組不確定性標(biāo)準(zhǔn),提出了能夠兼顧時間與數(shù)據(jù)不確定性的混合衰減模型;最后,在新的不確定性標(biāo)準(zhǔn)和混合衰減模型的基礎(chǔ)上,提出了一種新的概率數(shù)據(jù)流聚類算法。
　　本文提出了一套在多數(shù)據(jù)流情況下的異常趨勢檢測方法。首先,針對現(xiàn)有趨勢定義的不足之處,引入了一種適合數(shù)據(jù)流環(huán)境下的趨勢定義

5、,它的優(yōu)點在于其較低的時空復(fù)雜度;為了在趨勢計算過程中選擇合適的時間尺度,又提出了一種基于奇異值分解的選擇算法,同時給出了一種用于在線調(diào)整參數(shù)的概要數(shù)據(jù)結(jié)構(gòu);最后,當(dāng)關(guān)注重點由單數(shù)據(jù)流轉(zhuǎn)向多數(shù)據(jù)流時,我們將基于多數(shù)據(jù)流的斜度統(tǒng)計值來監(jiān)控異常情況。
　　本文實現(xiàn)了一套名為DiCAS的網(wǎng)絡(luò)數(shù)據(jù)流異常檢測系統(tǒng),它結(jié)合上海電信骨干網(wǎng)上的數(shù)據(jù)流量監(jiān)測需求,實現(xiàn)了對多數(shù)據(jù)流量的在線監(jiān)測。DiCAS系統(tǒng)采用降維分析算法對SNMP數(shù)據(jù)流進(jìn)行分析,

6、通過監(jiān)測網(wǎng)絡(luò)鏈路上不同流量數(shù)據(jù)的相關(guān)性變化來發(fā)現(xiàn)異常流量。模擬實驗和在真實環(huán)境中的應(yīng)用表明,DiCAS系統(tǒng)能夠滿足骨干網(wǎng)流量監(jiān)測應(yīng)用的需要,并且極大地提高了監(jiān)測系統(tǒng)的實效性。綜上所述,本文設(shè)計了若干種異常檢測和聚類分析算法,并且將數(shù)據(jù)流模型與不確定數(shù)據(jù)類型相結(jié)合,是對現(xiàn)有數(shù)據(jù)流挖掘技術(shù)的有益補(bǔ)充和改進(jìn)。理論分析和實驗結(jié)果均表明本文算法能夠高效地解決相應(yīng)問題,與現(xiàn)有數(shù)據(jù)流處理方法相比,本文算法在存儲空間開銷、挖掘處理速度以及結(jié)果準(zhǔn)確性上都