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

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

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

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

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

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

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

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