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

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

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

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