宋巧紅,齊金鵬,張 煜

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

0 概述

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

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

1 HWKS的理論框架

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

圖1 HWKS突變點檢測過程

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

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

(1)

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

(8)

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

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

圖2 待檢測序列的Z分解

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

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

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

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

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

(9)

(10)

(11)

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

(12)

(13)

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

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

(14)

H0:Fm=Gnvs.H0:Fm≠Gn

(15)

為了檢驗H0,制定一個策略:

(16)

1.3 HWKS框架的異常點搜索策略

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

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

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

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

2 實驗結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

圖5 多次仿真的實驗結(jié)果

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

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

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

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

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

相比于HWKS方法和KS方法,在檢測突變點時,HW方法需要耗費更多的時間,而且命中率不是很高。

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

3 結(jié)束語

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

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

[2] 蔣 濤,馮玉才,朱 虹,等.時序數(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ù)據(jù)挖掘分析[J].電子科技大學(xué)學(xué)報,2005,34(4):556-558.

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

[7] 侯澍旻,李友榮,劉光臨.一種基于KS檢驗的時間序列非線性檢驗方法[J].電子與信息學(xué)報,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] 王小宜,盧正鼎,凌賀飛.一個基于小波的時序數(shù)據(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)計特征的時序數(shù)據(jù)符號化算法[J].計算機學(xué)報,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.