基于最窄平行四邊形的數(shù)據(jù)流突變檢測算法.pdf

1、數(shù)據(jù)流上的突變檢測在網(wǎng)絡(luò)流量監(jiān)測,金融風(fēng)險(xiǎn)分析,傳感器網(wǎng)絡(luò)等領(lǐng)域都有著十分廣泛的應(yīng)用。傳統(tǒng)的突變檢測算法只能對流上的聚集函數(shù)值進(jìn)行檢測,而在現(xiàn)實(shí)應(yīng)用中,還有相當(dāng)一部分的突變檢測要求能針對非聚集函數(shù)進(jìn)行檢測。本文提出了一種新穎的數(shù)據(jù)流上的突變檢測算法,即最窄平行四邊形法。該方法用一系列扁平的平行四邊形來模擬數(shù)據(jù)流上具有相同趨勢的點(diǎn),并保證每個(gè)點(diǎn)的誤差不超過平行四邊形寬度的一半。于是,等距到達(dá)的數(shù)據(jù),便可根據(jù)得到的平行四邊形還原其中的每一個(gè)

2、點(diǎn),從而實(shí)現(xiàn)基于任意類型函數(shù)的突變檢測。在提出最窄平行四邊形基本算法之后,本文又對該算法進(jìn)行了一系列改進(jìn),使其時(shí)間復(fù)雜度從O(nh)降到了O(h),其中n為平行四邊形內(nèi)包含的點(diǎn)的個(gè)數(shù),h為覆蓋這些點(diǎn)的凸包的邊數(shù)。通過對真實(shí)數(shù)據(jù)流上的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)分析,以及與現(xiàn)有突變檢測算法的比較,驗(yàn)證了最窄平行四邊形算法在時(shí)間和空間上的高效性。針對現(xiàn)有各種基于直方圖的突變檢測方法在構(gòu)造數(shù)據(jù)流模型時(shí)存在的空間低效性,本文又對最窄平行四邊形法進(jìn)行了擴(kuò)展,使其

3、在針對聚集函數(shù)的突變檢測中能更加節(jié)省存儲(chǔ)空間,從而在相同的內(nèi)存容量限制下能檢測更大的滑動(dòng)窗口。最后通過實(shí)驗(yàn)驗(yàn)證了該方法對現(xiàn)有基于直方圖的突變檢測方法的優(yōu)越性。本文的主要貢獻(xiàn)可總結(jié)為如下三方面:·基于大部分?jǐn)?shù)據(jù)流上數(shù)據(jù)變化的規(guī)律,提出了最窄平行四邊形法。通過對流上原始數(shù)據(jù)進(jìn)行壓縮,支持基于任意函數(shù)的突變檢測。據(jù)我們所知,這是第一次把凸包算法應(yīng)用到數(shù)據(jù)流的突變檢測上來。·對基本的最窄平行四邊形算法進(jìn)行了改進(jìn),使其時(shí)間復(fù)雜度從O(nh)降到了