數(shù)據(jù)流離群點檢測研究.pdf

1、近幾年來，隨著信息技術(shù)的發(fā)展，出現(xiàn)了一類新的數(shù)據(jù)模型——數(shù)據(jù)流。它以實時、連續(xù)、有序的數(shù)據(jù)序列方式存在于人們生產(chǎn)和生活各個領(lǐng)域，如股票交易，火車售票系統(tǒng)，傳感器網(wǎng)絡(luò)等。它具有數(shù)據(jù)量大，連續(xù)快速，不可預(yù)測和短暫易逝等特點。數(shù)據(jù)流的這些特點決定了很多傳統(tǒng)數(shù)據(jù)挖掘技術(shù)無法推廣到數(shù)據(jù)流上。它要求數(shù)據(jù)挖掘具有在線挖掘能力，能在有限的空間里實時地處理源源不斷地流入的數(shù)據(jù)并及時將挖掘結(jié)果反饋給用戶。在很多數(shù)據(jù)流實際應(yīng)用中，人們往往只關(guān)注數(shù)據(jù)流中離當(dāng)前

2、比較近的數(shù)據(jù)，對較遠(yuǎn)的歷史數(shù)據(jù)興趣不大。為了滿足這種應(yīng)用需要，滑動窗口技術(shù)應(yīng)運(yùn)而生。滑動窗口（包括基于時間的和基于數(shù)量的）內(nèi)的數(shù)據(jù)是數(shù)據(jù)流離當(dāng)前最近一段數(shù)據(jù)。
　　 數(shù)據(jù)流上離群點(異常點)檢測是數(shù)據(jù)流數(shù)據(jù)挖掘的一個重要的分支，它在數(shù)據(jù)流應(yīng)用中有著非常重要的理論和應(yīng)用價值。比如：在銀行的交易數(shù)據(jù)中，一些異常交易數(shù)據(jù)可能預(yù)示金融欺詐。在機(jī)場安檢系統(tǒng)里，檢測一些異常的行為可以有助于避免恐怖襲擊。在疾病監(jiān)控數(shù)據(jù)中，挖掘一些異常的疾病數(shù)

3、據(jù)可以監(jiān)控一些疾病的變異和預(yù)警重大傳染病暴發(fā)。在產(chǎn)品生產(chǎn)的數(shù)據(jù)中，檢測產(chǎn)品的一些缺陷可以較快地了解生產(chǎn)機(jī)器的性能狀況。由于數(shù)據(jù)流數(shù)據(jù)量大，不可能被存儲到存儲介質(zhì)上，挖掘靜態(tài)數(shù)據(jù)中的離群點檢測算法無法推廣到數(shù)據(jù)流上去。因此需要研究數(shù)據(jù)流中的離群點檢測方法。由于數(shù)據(jù)流中的數(shù)據(jù)具有易逝性，再加上流數(shù)據(jù)量大速度快，因此流上的離群點檢測方法只能單遍訪問數(shù)據(jù)，需要以較少的時空代價增量反饋離群點。在滑動窗口的數(shù)據(jù)模型中，滑動窗口不斷向前滑行， 一部分

4、舊數(shù)據(jù)會滑出窗口，一部分新的數(shù)據(jù)流入了窗口。這種新舊數(shù)據(jù)交替直接影響窗口上離群點檢測結(jié)果。為了反應(yīng)窗口內(nèi)數(shù)據(jù)變化的趨勢，窗口上的離群點檢測方法一方面要將新進(jìn)的信息補(bǔ)充到已有離群信息中去，同時定期地清除過期的離群信息，從而提高算法的準(zhǔn)確率并節(jié)約存儲空間。
　　 基于滾動物理窗口的最近滑動窗口離群點檢測方法充分利用ROF-tree結(jié)構(gòu)優(yōu)勢，動態(tài)維護(hù)窗口內(nèi)的頻繁模式和離群信息。通過定期執(zhí)行修枝和刷新算法清除掉ROF-tree樹上的過期

5、和非離群的數(shù)據(jù)，有效地提高了內(nèi)存空間的使用效率。該方法使用保守估計策略得到的數(shù)據(jù)的離群度的近似值總不小于數(shù)據(jù)真實的離群度，從而實現(xiàn)了盡力不漏報離群點的目標(biāo)。
　　 為了能動態(tài)地，方便地檢測可變滑動窗口內(nèi)的離群點，我們提出了基于頻繁模式的流數(shù)據(jù)離群度量——抵觸頻繁模式離群因子FPCOF，它能更加直觀準(zhǔn)確地度量數(shù)據(jù)的離群程度，并在此基礎(chǔ)上給出一種能迅速準(zhǔn)確地挖掘數(shù)據(jù)流上任意大小滑動時間窗口內(nèi)離群點的算法ODFP-SW。算法通過構(gòu)建S

6、WODFP-Tree樹，在將流入的數(shù)據(jù)增量更新到樹上的過程中，同時計算出了數(shù)據(jù)的FPCOF值，并通過樹上的候選離群集的刪除和移動，動態(tài)更新候選離群集以及候選離群點的FPCOF值，能實時動態(tài)地反映數(shù)據(jù)流中離群信息的變化過程。
　　 在數(shù)據(jù)流離群點檢測的應(yīng)用中，選擇一個合適的離群度的最小檢測門限是一件復(fù)雜而困難的事情。人們因而提出了檢測數(shù)據(jù)流上TOP-K離群點的需求。針對這種需求，我們提出了一種數(shù)據(jù)流上滑動窗口TOP-K離群點檢測方

7、法。方法根據(jù)切爾諾夫(Chernoff)邊界定理和當(dāng)前第K離群點的離群度，估算出TOP-K離群點的最低離群度門限。依據(jù)門限將窗口內(nèi)的數(shù)據(jù)分為兩類：候選TOP-K離群點和非離群數(shù)據(jù)。當(dāng)滑動窗口不斷向前滑行時，算法將窗口中的過期的和非離群數(shù)據(jù)清除，這樣可以節(jié)約大量存儲空間，并能高概率地保證了方法對窗口內(nèi)TOP-K離群點檢測的正確性。
　　 在數(shù)據(jù)流滑動窗口查詢研究領(lǐng)域中，連續(xù)查詢結(jié)果失效的問題成為了一個新研究熱點。查詢結(jié)果的維護(hù)代價