數(shù)據(jù)流上的異常檢測(cè).pdf

1、近年來(lái)，由于來(lái)自實(shí)際應(yīng)用中的需求的推動(dòng)，數(shù)據(jù)流上的異常檢測(cè)技術(shù)的研究已經(jīng)受到了學(xué)術(shù)界和工業(yè)界的越來(lái)越多的重視。數(shù)據(jù)流上的異常檢測(cè)在金融風(fēng)險(xiǎn)分析、通信網(wǎng)監(jiān)測(cè)、網(wǎng)絡(luò)流量管理、趨勢(shì)分析、Web日志分析、網(wǎng)絡(luò)入侵檢測(cè)、傳感器網(wǎng)絡(luò)管理等領(lǐng)域具有廣泛的應(yīng)用。例如，為了調(diào)節(jié)電信網(wǎng)絡(luò)的性能，需要對(duì)電信網(wǎng)中的數(shù)據(jù)流進(jìn)行監(jiān)測(cè)，其檢測(cè)異常的準(zhǔn)確性對(duì)電信網(wǎng)絡(luò)的正常運(yùn)行是至關(guān)重要的。同樣的應(yīng)用場(chǎng)景也存在于高速公路上的交通管理，相關(guān)趨勢(shì)的分析和預(yù)測(cè)，網(wǎng)頁(yè)點(diǎn)擊流的分

2、析，信息系統(tǒng)的入侵檢測(cè)以及傳感器網(wǎng)絡(luò)的管理等。在這些場(chǎng)景中，有相當(dāng)一部分應(yīng)用需要及時(shí)地對(duì)任務(wù)進(jìn)行處理，以獲得盡可能短的響應(yīng)時(shí)間。 然而，傳統(tǒng)的數(shù)據(jù)庫(kù)技術(shù)是用來(lái)管理靜態(tài)數(shù)據(jù)集的，其很難直接被用于對(duì)動(dòng)態(tài)數(shù)據(jù)的實(shí)時(shí)監(jiān)測(cè)和挖掘。因此，為了實(shí)時(shí)地監(jiān)測(cè)數(shù)據(jù)流，需要采用伸縮性強(qiáng)的異常檢測(cè)算法在有限的時(shí)間內(nèi)處理大量的數(shù)據(jù)流。在對(duì)數(shù)據(jù)流的處理中，最大的挑戰(zhàn)就是要在有限的內(nèi)存空間，需要順序的單遍掃描算法，并且要實(shí)時(shí)返回精確的結(jié)果。本文綜述了國(guó)際上關(guān)

3、于數(shù)據(jù)流異常檢測(cè)的研究成果，在分析了現(xiàn)有研究工作的基礎(chǔ)上，提出了異常的定義和數(shù)據(jù)流上異常檢測(cè)要研究的問(wèn)題，以及異常檢測(cè)系統(tǒng)的框架。在對(duì)數(shù)據(jù)流上異常檢測(cè)的研究過(guò)程中，本文的主要貢獻(xiàn)有如下三個(gè)方面： 1．提出了自適應(yīng)的突變的定義，自適應(yīng)的突變更加全面地概括了數(shù)據(jù)流上的突變信息，并且排除了顛簸數(shù)據(jù)的干擾。根據(jù)該定義，本文又提出了三種突變檢測(cè)方法，其中包括FalsePositive，F(xiàn)alseNegative和綜合突變檢測(cè)算法，這些算法

4、能夠保證以高于用戶指定的準(zhǔn)確率檢測(cè)數(shù)據(jù)流上的突變，而且這些算法既能檢測(cè)單調(diào)聚集函數(shù)值的突變，又能檢測(cè)非單調(diào)聚集函數(shù)值的突變。突變檢測(cè)算法所依賴的是本文提出的倒置桶序列的直方圖(簡(jiǎn)稱IH)。這種新穎的直方圖技術(shù)具有較小的時(shí)間復(fù)雜度0(n(10gn+IogR))和空間復(fù)雜度O(logn+log_R)，并能為突變檢測(cè)提供準(zhǔn)確的聚集查詢支持，因此與現(xiàn)有直方圖技術(shù)相比更加適用于數(shù)據(jù)流上的突變檢測(cè)。 2．提出了基于單調(diào)搜索空間的突變檢測(cè)算法

5、。首先，提出了數(shù)據(jù)流上的單調(diào)搜索空間的構(gòu)建算法及改進(jìn)后的構(gòu)建算法，從而對(duì)實(shí)際應(yīng)用中的近似分形數(shù)據(jù)進(jìn)行了分形變換，使得滑動(dòng)窗口的錯(cuò)排序誤差errMs為0。其次，基于單調(diào)的搜索空間設(shè)計(jì)了突變檢測(cè)算法。該算法能將突變檢測(cè)處理時(shí)間復(fù)雜度從0(m)降為D(10gm)，m為需要被檢測(cè)的滑動(dòng)窗口數(shù)目。最后，分析并給出了基于單調(diào)搜索空間的突變檢測(cè)方法的誤差界限，使得本文提出的突變檢測(cè)算法具有理論上的誤差上限的保證。 3．提出了基于分段分形模型的

6、無(wú)參數(shù)異常檢測(cè)算法。首先，本文提出了最優(yōu)的分段分形模型以及數(shù)據(jù)流上的近似最優(yōu)分段分形模型。利用近似最優(yōu)的分段分形模型為長(zhǎng)為禮的數(shù)據(jù)流建模的時(shí)間復(fù)雜度為0(nlogn)，空間復(fù)雜度為O(10gn)。第二，提出了基于分段分形模型的突變檢測(cè)算法，該算法在分段分形模型具有理論誤差界限保證的前提下，能夠準(zhǔn)確地檢測(cè)數(shù)據(jù)流上的突變。第三，本文提出了無(wú)參數(shù)的異常檢測(cè)算法。該算法能夠在最合適尺寸的滑動(dòng)窗口上檢測(cè)異常的情況，不需要用戶設(shè)定任何參數(shù)，也不需要

7、使用訓(xùn)練數(shù)據(jù)。使用該算法在數(shù)據(jù)流上檢測(cè)異常的時(shí)間復(fù)雜度僅為O(n)，空間復(fù)雜度僅為0(1)。 綜上所述，本文針對(duì)現(xiàn)有異常檢測(cè)中存在的三類問(wèn)題，分別提出了從問(wèn)題定義、概要數(shù)據(jù)結(jié)構(gòu)到異常檢測(cè)算法的完整方案，并提出了以本文技術(shù)為核心的異常檢測(cè)系統(tǒng)框架。理論分析和實(shí)驗(yàn)結(jié)果表明，與已有的研究成果相比，本文給出的異常檢測(cè)方法具有較高的精度和較低的時(shí)間、空間復(fù)雜度，更加適用于數(shù)據(jù)流一的應(yīng)用場(chǎng)景：金融風(fēng)險(xiǎn)分析、通信網(wǎng)監(jiān)測(cè)、網(wǎng)絡(luò)流量管理、趨勢(shì)分析