基于多級(jí)Haar小波變換與KS統(tǒng)計(jì)的突變點(diǎn)快速探測方法

宋巧紅,齊金鵬,張 煜

(東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院,上海 201620)

0 概述

在數(shù)據(jù)挖掘和統(tǒng)計(jì)領(lǐng)域,時(shí)序數(shù)據(jù)突變點(diǎn)的檢測已經(jīng)引起了廣泛的關(guān)注[1-2],大部分方法是通過比較時(shí)間序列樣本在過去和現(xiàn)在的概率分布來檢測的[3],這種根據(jù)分布的不同來檢測出異常點(diǎn)的方法靈活性較差[4-6]。在統(tǒng)計(jì)方面,已經(jīng)探索出了一些用于突變點(diǎn)檢測的方法,比如KS統(tǒng)計(jì)理論[7]。KS統(tǒng)計(jì)理論是一種非參數(shù)的統(tǒng)計(jì)理論,其量化了樣本的經(jīng)驗(yàn)分布函數(shù)和參考分布的累積分布函數(shù)之間的距離,尤其是兩樣本的KS檢驗(yàn)方法,被廣泛用于比較2個(gè)樣本,因?yàn)樗鼘?個(gè)樣本的經(jīng)驗(yàn)分布函數(shù)的位置和形狀參數(shù)的差異特別敏感[8]。另一方面,小波變換對于異常點(diǎn)的檢測有很好的前景。小波變換可以很容易地從不同的時(shí)間或空間距離上提取數(shù)據(jù)的分布特征[9]。小波分析的核心是多分辨率分析,可以把其中一個(gè)信號(hào)分解成不同大小的分辨率級(jí)別的子信號(hào)。小波的定位、正交性和多速率濾波等特性是對信號(hào)平穩(wěn)性和瞬態(tài)性分析必不可少的條件[10]。

然而,這些方法大多很耗時(shí),且由于時(shí)間復(fù)雜度的問題并不適合處理分析大數(shù)據(jù)[11]。此外這些方法對于一些無效的波動(dòng)不是很敏感,尤其是2個(gè)端點(diǎn)附近的突化。為了實(shí)現(xiàn)對時(shí)間序列檢測的及時(shí)性[12-13],本文在多級(jí)Harr小波變換與KS統(tǒng)計(jì)理論的基礎(chǔ)[14-15]上提出一種新的快速探測突變點(diǎn)的理論框架,簡稱HWKS(Haar Wavelet and KS),并與HW方法、T方法和KS方法從耗時(shí)、命中率、誤差以及準(zhǔn)確度4個(gè)方面進(jìn)行比較。

1 HWKS的理論框架

HWKS的框架結(jié)構(gòu)如圖1所示。首先以正常的序列X作為參考序列,然后對其和待檢測序列Z通過多級(jí)Haar小波變換,分別構(gòu)建均值二叉搜索樹(TcA)和差值二叉搜索樹(TcD)。其次,用改進(jìn)的KS統(tǒng)計(jì)理論對TcA中的根節(jié)點(diǎn)到葉子節(jié)點(diǎn)中的異常點(diǎn)進(jìn)行快速檢測。最后,對模擬的時(shí)序數(shù)列進(jìn)行突變點(diǎn)檢測,以驗(yàn)證該方法的有效性。

圖1 HWKS突變點(diǎn)檢測過程

1.1 均值二叉搜索樹和差值二叉搜索樹的構(gòu)建

一般而言,可利用多級(jí)Haar小波變換方法,將離散的時(shí)序信號(hào)Z={z1,z2,…,zN}解析成不同的頻域分量,并表示如下:

(1)

其中,cA和cD分別為均值參數(shù)和差值參數(shù)。多分辨率分析(Multi-Resolution Analysis,MRA)是小波分析的核心[16],根據(jù)MRA,可以概念化小波變換的過程,將總體的N分解成一小段一小段n。向量vi和wi分別代表縮放信號(hào)和小波基向量。離散信號(hào)Z的均值信號(hào)Ak和差值信號(hào)Di可以表示為:

(2)

Ak= (Z·Vk)Vk=

(3)

(4)

因此,可以得到如下方程:

(5)

Ak=cAk·Vk=

(6)

Dk=cDk·Wk=(cDk,1,cDk,2,…,cDk,N/2k)·

(7)

因此,可將時(shí)序數(shù)據(jù)Z分解成多維的均值參數(shù)矩陣(McA)和差值參數(shù)矩陣(McD):

(8)

其中,0≤k≤m=lbN,1≤j≤N/2k。

綜上,可將時(shí)序數(shù)據(jù)Z分解成多維的均值參數(shù)矩陣(McA)和差值參數(shù)矩陣(McD)。然后,將參數(shù)矩陣McA和McD分別映射到對應(yīng)的均值二叉搜索樹(TcA)和差值二叉搜索樹(TcD)的各層子節(jié)點(diǎn)。分別通過McA和McD來構(gòu)造TcA和TcD中的各級(jí)非葉子節(jié)點(diǎn)。同時(shí),葉子節(jié)點(diǎn)直接來自Z中的元素。多級(jí)Harr小波變換將待檢測的序列Z分解成TcA和TcD的過程,如圖2所示。

圖2 待檢測序列的Z分解

1.2 基于改進(jìn)KS統(tǒng)計(jì)理論的HWKS

KS統(tǒng)計(jì)是一種非常有用的非參數(shù)方法,被廣泛應(yīng)用于2個(gè)樣本的比較。它對2個(gè)樣本的經(jīng)驗(yàn)分布函數(shù)的位置和形狀參數(shù)的差異都特別敏感。假定一個(gè)時(shí)間序列Y={y1,y2,…,yN},可以表示為Y=f(i/N)+X,i=1,2,…,N,其中X={xi}i=1,2,…,N是獨(dú)立同分布的隨機(jī)變量,f是未知分布的噪聲信號(hào)。那么,就可以用分布函數(shù)Fm(x)來表示正常的時(shí)間序列X,同時(shí)用分布函數(shù)Gn(x)來表示異常的時(shí)間序列Y。待檢測的時(shí)間序列Z表示如下:

Z= {X,Y}={Z1,Z2}=

{z1,z2,…,zc,zc+1,zc+1,…,zn}

為了檢測Z中的突變點(diǎn),可以通過改進(jìn)的KS統(tǒng)計(jì)理論來評(píng)估X分布和Z分布之間的距離,如式(9)所示。

(9)

(10)

(11)

可以表示Z中的第j個(gè)元素zj,同時(shí)在HWKS方法中定義一個(gè)新的元素zk,j:

(12)

(13)

其中,cAk,j是TcA中的非葉子節(jié)點(diǎn),zk,j是根據(jù)cAk,j新定義的元素,且1≤j≤N/2k,a=2k(j-1)+1,b=2k×j。

可以為HWKS定義一個(gè)改進(jìn)的KS統(tǒng)計(jì)理論方法:

(14)

H0:Fm=Gnvs.H0:Fm≠Gn

(15)

為了檢驗(yàn)H0,制定一個(gè)策略:

(16)

1.3 HWKS框架的異常點(diǎn)搜索策略

為了檢測時(shí)間序列Z的突變點(diǎn),需要在TcA的根節(jié)點(diǎn)和葉子節(jié)點(diǎn)之間建立一條準(zhǔn)確和快速的最優(yōu)路徑。第1個(gè)搜索策略如下所示:

策略1假定 TcA中的非葉子節(jié)點(diǎn)是cAk,j,它左面的子節(jié)點(diǎn)和右面的子節(jié)點(diǎn)分別是cAk-1,2j-1和cAk-1,2j。

1)如果滿足|cDk-1,2j-1|>|cDk-1,2j|,選擇TcA中的左側(cè)子節(jié)點(diǎn)cAk-1,2j-1作為當(dāng)前的搜索路徑。

2)如果滿足|cDk-1,2j-1|<|cDk-1,2j|,選擇TcA中的右側(cè)子節(jié)點(diǎn)cAk-1,2j作為當(dāng)前的搜索路徑。

2 實(shí)驗(yàn)結(jié)果與分析

通過仿真的時(shí)序數(shù)據(jù)來評(píng)估HWKS的可行性,先對仿真數(shù)據(jù)進(jìn)行一次檢測,再對仿真數(shù)據(jù)進(jìn)行多次檢測。最后,設(shè)置不同的樣本長度和突變點(diǎn)位置,對每組數(shù)據(jù)都進(jìn)行400次重復(fù)實(shí)驗(yàn),通過與KS方法、HW方法和T方法的比較來分析HWKS方法的耗時(shí)、命中率、誤差和準(zhǔn)確度。

2.1 對數(shù)據(jù)的一次檢測

圖3為模擬的待檢測時(shí)序數(shù)據(jù)。每個(gè)待檢測的時(shí)序數(shù)列Z的長度都為N,由2個(gè)部分組成,一部分為正常的時(shí)序數(shù)列,長度為K,正常的序列服從均勻分布;另一部分為不正常的序列,長度為NK,通過數(shù)據(jù)拼接的方式,將均勻分布替換為服從高斯分布的序列。圖3中數(shù)據(jù)的長度為32,突變點(diǎn)的位置為6。

圖3 模擬的待檢測時(shí)序數(shù)據(jù)

用這4種方法對圖3 的時(shí)序數(shù)據(jù)進(jìn)行檢測,檢測結(jié)果如圖4所示。為了更加清楚地查看檢測結(jié)果,將圖4的數(shù)據(jù)整理在表1中。

圖4 4種方法的檢測結(jié)果

方法耗時(shí)/s誤差HWKS方法0.0350KS方法0.0028HW方法0.0818T方法0.0462

從表1可以看出,HWKS的誤差最小,耗時(shí)相對較小。KS雖然耗時(shí)較小,但是誤差很大。HW耗時(shí)較長,T方法的誤差比HWKS方法大。所以,綜合考慮,HWKS在這4種方法中,效果最好。

2.2 對不同突變點(diǎn)不同數(shù)據(jù)長度的多次檢測

先設(shè)置一個(gè)固定的突變點(diǎn),待檢測樣本的長度N=128,K=111。通過40次的仿真實(shí)驗(yàn)來檢測突變點(diǎn)的位置。圖5(a)～圖5(d)為對數(shù)據(jù)進(jìn)行處理后的分布,圖5(e)～圖5(h)為對檢測到的不同位置的突變點(diǎn)的位置進(jìn)行擬合,從圖中可看出命中的突變點(diǎn)的大概位置。

圖5 多次仿真的實(shí)驗(yàn)結(jié)果

為了更加清楚地查看檢測結(jié)果,將數(shù)據(jù)整理在表2中。對同一個(gè)突變點(diǎn)進(jìn)行多次檢測時(shí),可以發(fā)現(xiàn)HWKS方法的準(zhǔn)確度最高,耗時(shí)最小。為了進(jìn)一步驗(yàn)證HWKS方法的可行性,設(shè)置了樣本的不同長度,并設(shè)置不同的突變點(diǎn)位置,對檢測的時(shí)間長短、命中率、誤差和準(zhǔn)確度進(jìn)行檢測。檢測結(jié)果如表3所示。并將表3中各個(gè)指標(biāo)的平均值整理在表4中。

表2 多次仿真的實(shí)驗(yàn)數(shù)據(jù)

表3 多次檢測結(jié)果的時(shí)間、命中率、誤差、準(zhǔn)確度

表4 多次統(tǒng)計(jì)的平均值

從統(tǒng)計(jì)的平均值可以看出HWKS方法的準(zhǔn)確度相對較高,雖然KS的準(zhǔn)確度較高,但是耗時(shí)比HWKS要大很多。當(dāng)樣本的尺寸較小,且突變點(diǎn)發(fā)生在左邊界或者右邊界時(shí),HWKS的命中率要比KS高。

相比于HWKS方法和KS方法,在檢測突變點(diǎn)時(shí),HW方法需要耗費(fèi)更多的時(shí)間,而且命中率不是很高。

表3的結(jié)果表明,HWKS對于具有較小尺寸N的樣本的左邊界和右邊界附近的較小顯著數(shù)據(jù)波動(dòng)具有更好的性能和靈敏度,由于計(jì)算時(shí)間較短,命中率較高,因此HWKS是用于模擬時(shí)間序列上的突變點(diǎn)檢測的較好方法。

3 結(jié)束語

本文結(jié)合多級(jí)Haar小波變換與KS統(tǒng)計(jì)理論,給出對時(shí)序數(shù)據(jù)突變點(diǎn)的快速探測方法HWKS。該方法主要利用多級(jí)Haar小波變換與KS統(tǒng)計(jì)理論,對標(biāo)準(zhǔn)參考序列以及待檢測序列分別構(gòu)建均值二叉搜索樹(TcA)和差值二叉搜索樹(TcD)。并基于改進(jìn)的KS檢驗(yàn)方法提出二叉樹搜索的2種策略,進(jìn)而完成對時(shí)序數(shù)據(jù)突變點(diǎn)的快速檢測的HWKS理論框架的構(gòu)建。最后,用模擬的時(shí)序數(shù)據(jù)進(jìn)行驗(yàn)證,結(jié)果表明,與HW方法、T方法和KS方法相比,HWKS方法在對突變檢測時(shí)的誤差較小,用時(shí)最短,準(zhǔn)確度較高。綜合考慮,HWKS方法是對突變點(diǎn)進(jìn)行檢測的一種有效的方法。

[1] 李國杰.大數(shù)據(jù)研究的科學(xué)價(jià)值[J].中國計(jì)算機(jī)學(xué)會(huì)通訊,2012,8(9):8-15.

[2] 蔣 濤,馮玉才,朱 虹,等.時(shí)序數(shù)據(jù)挖據(jù)概述[EB/OL].[2017-04-14].http://doc.mbalib.com/view/8f6ae3ed41ef4cd4ec9207ae75d1cbf8.html.

[3] 秦首科.數(shù)據(jù)流上的異常檢測[D].上海:復(fù)旦大學(xué),2006.

[4] MANIKOPOULOS C,PAPAVASSILIOU S.Network intrusion and fault detection: a statistical anomaly approach[J].IEEE Communications Magazine,2002,40(10):76-82.

[5] 文 琪,彭 宏.小波變換的離群時(shí)序數(shù)據(jù)挖掘分析[J].電子科技大學(xué)學(xué)報(bào),2005,34(4):556-558.

[6] 侯澍旻.時(shí)序數(shù)據(jù)挖掘及其在故障診斷中的應(yīng)用研究[D].武漢:武漢科技大學(xué),2006.

[7] 侯澍旻,李友榮,劉光臨.一種基于KS檢驗(yàn)的時(shí)間序列非線性檢驗(yàn)方法[J].電子與信息學(xué)報(bào),2007,29(4):808-810.

[8] WANG Yao,WU Chunguo,JI Zhaohua,et al.Non-parametric change-point method for differential gene expression detection[EB/OL].[2017-04-14].https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3104986/.

[9] 王小宜,盧正鼎,凌賀飛.一個(gè)基于小波的時(shí)序數(shù)據(jù)異常探測的新算法[J].計(jì)算機(jī)工程與科學(xué),2005,27(6):83-85.

[10] LIN H D.Automated visual inspection of ripple defects using wavelet characteristic based multivariate statistical approach[J].Image and Vision Computing,2007,25(1):1785-1801.

[11] 劉丹紅,張世英.基于小波神經(jīng)網(wǎng)絡(luò)的非線性誤差校正模型及其預(yù)測[J].控制與決策,2006,21(10):1114-1118.

[12] LIN J,KEOGH E,LONARDI S,et al.A symbolic representation of time series,with implications for streaming algorithms[C]//Proceedings of ACM Sigmod Workshop on Research Issues in Data Mining & Knowledge Discovery.New York,USA:ACM Press,2003:2-13.

[13] 鐘清流,蔡自興.基于統(tǒng)計(jì)特征的時(shí)序數(shù)據(jù)符號(hào)化算法[J].計(jì)算機(jī)學(xué)報(bào),2008,31(10):1857-1864.

[14] SHARIFZADEH M,AZMOODEH F,SHAHABI C.Change detection in time series data using wavelet footprints[C]//Proceedings of International Symposium on Spatial and Temporal Databases.Berlin,Germany:Springer,2005:127-144.

[15] BRODSKY B E,DARKHOVSKY B S.Nonparametric methods in change point problem[M].Berlin,Germany:Springer,1993.

[16] ALARCON-AQUINO V,BARRIA J A.Anomaly detection in communication networks using wavelets[J].IEEE Proceedings Communications,2002,148(6):355-362.