劉雪梅，王亞茹

(華北水利水電大學(xué) 信息工程學(xué)院，河南 鄭州 450045)

0 引 言

南水北調(diào)工程是緩解我國北部地區(qū)水資源緊張，優(yōu)化水資源配置的一項(xiàng)戰(zhàn)略性基礎(chǔ)設(shè)施工程。在工程安全監(jiān)測(cè)中有一類數(shù)據(jù)是按照發(fā)生的時(shí)間順序保存的，這類數(shù)據(jù)叫做時(shí)間序列。在時(shí)間序列大量的數(shù)據(jù)中，有些極少出現(xiàn)的子序列與其他子序列有顯著的不同，使得人們懷疑它是由不同的機(jī)制產(chǎn)生的，這些子序列稱為異常模式[1]。在工程安全中，異常模式往往更能夠幫助人們認(rèn)識(shí)事物。因此，從海量數(shù)據(jù)中挖掘出異常模式，對(duì)保證南水北調(diào)工程的安全具有重要意義。

1 時(shí)間序列上進(jìn)行異常模式挖掘

時(shí)間序列具有高維性、海量性、含有大量噪聲等特征，直接在原始時(shí)間序列上進(jìn)行異常模式挖掘要花費(fèi)大量的時(shí)空代價(jià)，會(huì)影響算法的可靠性。

目前常用的時(shí)間序列表示法主要有頻域表示法[2]、奇異值表示法[3]、分段線性表示法[4-5]、符號(hào)化表示法[6]。文獻(xiàn)[7]中，通過離散傅里葉變換，將時(shí)間序列從時(shí)域映射到頻域，傅里葉變換會(huì)平滑掉具有重要特征的點(diǎn)，對(duì)非平穩(wěn)的時(shí)間序列不適用。奇異值表示法的時(shí)空復(fù)雜度高。分段線性表示方法通過首尾相連的線段將時(shí)間序列分割成多個(gè)子序列，目前常用的主要有兩種：一是限制分段數(shù)目。文獻(xiàn)[8-9]中使用了分段聚集近似法(piecewise aggregate approximation)，也稱PAA算法。PAA算法忽略了時(shí)間序列的特征值，出現(xiàn)了較大的擬合誤差。第二種方法是通過限制分段誤差將時(shí)間序列劃分成長度不等的子序列,分段誤差的閾值對(duì)分段的影響較大。而分段結(jié)果的好壞直接影響到異常檢測(cè)的準(zhǔn)確性。

通過以上分析得出，如何選擇合適的分段數(shù)目是限制分段數(shù)目算法存在的問題，如何選擇重要點(diǎn)及閾值是不限制分段數(shù)目方法的難點(diǎn)。結(jié)合兩者的優(yōu)缺點(diǎn)，提出了基于斜率及子序列的最大時(shí)間跨度，不限制分段數(shù)目進(jìn)行時(shí)間序列分割，同時(shí)為了盡可能減少閾值對(duì)結(jié)果的影響，限制每段子序列的最大時(shí)間跨度，實(shí)現(xiàn)對(duì)分段數(shù)目最大值的限制，將不限制分段數(shù)目與限制分段數(shù)目相結(jié)合。

目前用于異常檢測(cè)的方法可分為基于模型的檢測(cè)方法[10]、基于聚類的檢測(cè)方法[11]、基于異常點(diǎn)檢測(cè)方法[12-13]、基于密度的檢測(cè)方法[14-15]?；诋惓｜c(diǎn)檢測(cè)方法較為簡單，但時(shí)間序列的高維性使該方法失效。基于密度的異常檢測(cè)方法精度高，但時(shí)空復(fù)雜度高。基于聚類的方法對(duì)于發(fā)現(xiàn)頻繁模式比較適用?；谀Ｐ偷姆椒ǎ⒛Ｐ秃蛥?shù)的估計(jì)存在一定的困難。

在時(shí)間序列分段線性表示的基礎(chǔ)上，文中提取子序列的斜率、均值、極值差，將時(shí)間序列映射到該特征空間，每個(gè)子序列就對(duì)應(yīng)到該特征空間中的一個(gè)點(diǎn)，用特征值構(gòu)成的三元組表示各子序列在特征空間的位置，在此基礎(chǔ)上計(jì)算各模式間的距離。通過一定的處理，得到正常模式間的距離，比較每個(gè)模式的距離與正常模式距離的比值，提取異常模式。

2 基于異常因子的時(shí)間序列異常模式探測(cè)算法

2.1 時(shí)間序列分段線性表示

定義1 重要點(diǎn)[12]：給定時(shí)間序列T=(t1,t2,…,tm),若ti(1≤i≤m)為極值點(diǎn)并滿足以下條件之一，則稱其為重要點(diǎn)。

(1)ti是時(shí)間序列的起點(diǎn)；

(2)ti是時(shí)間序列的終點(diǎn)；

(3)(ti-ti-1)*(ti+1-ti)<0。

對(duì)于時(shí)間序列模式表示，只需保留引起模式變化的重要點(diǎn)，這樣既能保留時(shí)間序列的形狀特征，又能實(shí)現(xiàn)大幅度的壓縮。文中提出的分割算法，重要點(diǎn)為引起斜率變化幅度較大及子序列達(dá)到最大時(shí)間跨度的點(diǎn)。分段線性表示方法就是用K條重要點(diǎn)相連的直線段來表示時(shí)間序列。由于是近似的表示時(shí)間序列，因此會(huì)平滑掉一些數(shù)據(jù)，使數(shù)據(jù)的管理更加高效。采用不限制分段數(shù)目與限制分段數(shù)目的方法相結(jié)合，基于斜率選擇合適的分段點(diǎn)進(jìn)行分割。

基于斜率的時(shí)間序列分割算法將相鄰的兩點(diǎn)作為一個(gè)最小分段，計(jì)算相鄰兩段斜率的差值與閾值進(jìn)行比較，若小于閾值，則將兩端合并，若大于閾值，則中間點(diǎn)為分割點(diǎn)。為了避免因閾值選擇不當(dāng)，平滑掉時(shí)間序列的主要特征，限制子序列的最長時(shí)間跨度，這也是文中的創(chuàng)新之處。算法1具體描述了基于斜率的時(shí)間序列分段線性表示方法。

算法1：基于斜率的時(shí)間序列分段線性表示算法。

輸入：(時(shí)間序列array(x1,x2,…,xn),d),其中d為斜率誤差閾值

輸出：時(shí)間序列的分段線性表示

Step1:序列的第一個(gè)點(diǎn)加入重要點(diǎn)序列。

s=(x1,1)

Step2:分別計(jì)算以點(diǎn)xi為端點(diǎn)的相鄰兩個(gè)線段的斜率。

j=0;k=1;h=2

for(i=1 to n)

tg1[i]=(xk-xj)/(k-j)

tg2[i]=(xh-xk)/(h-k)

Step3:判斷點(diǎn)xi是否為重要點(diǎn)，若是，則加入重要點(diǎn)集合s。

if(fabs(tg1[i])-tg2[i])>d)

j=i;k=i+1;h=i+2

Thens=s+(xi,i)

Else k=i+1;h=i+2

if(k-j>D)//D為子序列的最大時(shí)間跨度

s=s+(xi,i)

Step4:最后一個(gè)點(diǎn)加入重要點(diǎn)序列。

s=s+(xn,n)

Step5:輸出分段線性表示的子序列。

L(x)={L(x1,x2),L(x2,x3),…,L(xn-1,xn)}

2.2 異常模式探測(cè)算法

設(shè)時(shí)間序列x1=(x11,x12,…,x1n)是時(shí)間序列x=(x1,x2,…,xn)的子序列。

定義2 模式極值差：子模式中的最大值和最小值之間的差值。

vd=ximax-ximin

(1)

定義3 模式斜率：連接重要點(diǎn)的直線段的實(shí)際斜率。

(2)

定義4 模式均值：子序列中各時(shí)間點(diǎn)數(shù)據(jù)均值。

(3)

定義5p和q的距離：設(shè)p=(xp,yp,zp),q=(xq,yq,zq),則p和q之間的距離為：

dist(p,q)=

(4)

定義6 異常因子(lof)：該模式距離與正常模式的距離的比值。

(5)

其中,D為正常模式間距離;di為第i段子序列的距離。

定義7 異常模式:如果異常因子大于給定的閾值，則為異常模式。

異常模式檢測(cè)將子序列的斜率、均值、極值差組成的三維特征空間進(jìn)行距離的計(jì)算，三者值域差別很大，但衡量時(shí)間序列都很重要，因此要將三者的值域進(jìn)行規(guī)范化處理。設(shè)x1=(x11,x12,…,x1n)為其中一個(gè)子序列，則利用式(6)將該組特征值規(guī)范化到值域?yàn)?0,1)的區(qū)間。

(6)

其中，xmax和xmin分別表示各特征值的最大值和最小值。

時(shí)間序列異常檢測(cè)在模式間距離的基礎(chǔ)上求出異常因子，通過判斷異常因子是否超出給定的閾值來判斷模式狀態(tài)。先通過算法1將時(shí)間序列進(jìn)行線性分割，通過式1～3計(jì)算出每段子序列的極值差、斜率和均值，利用式(6)將時(shí)間序列的每個(gè)特征值規(guī)范到(0,1)，將每段子序列看成該空間中的一個(gè)點(diǎn)，其坐標(biāo)值為規(guī)范化后的斜率、均值和極值差。由定義可知異常模式的異常因子較大。傳統(tǒng)的距離計(jì)算的方法需要計(jì)算模式與其他每個(gè)模式間的距離，復(fù)雜度高。相對(duì)于頻繁模式，異常模式是極少出現(xiàn)的模式，因此在計(jì)算模式間距離時(shí)，無需計(jì)算一個(gè)子模式與其余每個(gè)子模式的距離，只需在一個(gè)周期內(nèi)取一個(gè)子模式，計(jì)算一個(gè)子模式與所取子模式間的距離即可，將每個(gè)子模式與其他子模式間的距離的均值作為該模式的距離，再將每個(gè)模式的距離求均值作為正常模式的距離。利用式(5)計(jì)算出異常因子，在一定程度上降低了時(shí)間復(fù)雜度。

算法2：異常模式檢測(cè)算法。

輸入: ((s1,e1),(s2,e2),…,(sm,em),d)

輸出:異常模式。其中sm為子序列的起始位置，em為終止位置。

Step1:計(jì)算子序列間的模式距離距d[m]

For i=1 to m

d1[i]=d(i,T),d2[i]=d(i,2*T)……dn[i]=d(i,n*T)

Step2：將Step1中每個(gè)子序列與其他子序列之間的距離，去掉最大值后的均值作為子模式的距離d[i]。所有子模式的距離排序后取中位數(shù)，各中位數(shù)的均值作為正常模式距離。

Step3:根據(jù)式(5)求出異常因子。

Step4:異常因子超出閾值，輸出異常模式。

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)結(jié)果

文中算法采用實(shí)測(cè)數(shù)據(jù)和合成數(shù)據(jù)進(jìn)行驗(yàn)證。實(shí)測(cè)數(shù)據(jù)集采用南水北調(diào)工程滲透壓力斜測(cè)儀檢測(cè)數(shù)據(jù)，斷面樁號(hào)：SH(3)+699，日期為2015年10月18日到2016年10月21日，p8-2的監(jiān)測(cè)數(shù)據(jù)。原始時(shí)間序列如圖1所示。

利用算法1對(duì)時(shí)間序列進(jìn)行分段線性表示，結(jié)果如圖2所示。

圖1 南水北調(diào)工程監(jiān)測(cè)數(shù)據(jù)原始時(shí)間序列

圖2 分段線性表示后的時(shí)間序列

利用人工合成數(shù)據(jù)進(jìn)行檢驗(yàn)，原始時(shí)間序列如圖3所示。

圖3 人工合成數(shù)據(jù)原始時(shí)間序列

利用算法1對(duì)人工數(shù)據(jù)進(jìn)行分段線性表示，結(jié)果如圖4所示。

圖4 人工合成數(shù)據(jù)分段線性表示

當(dāng)斜率閾值d取不同值時(shí)，對(duì)實(shí)測(cè)數(shù)據(jù)異常檢測(cè)的輸出結(jié)果如表1所示。

表1 d取不同值時(shí)的實(shí)驗(yàn)結(jié)果(實(shí)測(cè)數(shù)據(jù))

斜率閾值d取不同值時(shí)，對(duì)人工數(shù)據(jù)異常檢測(cè)結(jié)果如表2所示。

表2 d取不同值時(shí)的實(shí)驗(yàn)結(jié)果(異常數(shù)據(jù))

3.2 實(shí)驗(yàn)分析

結(jié)果表明,用實(shí)測(cè)數(shù)據(jù)和合成數(shù)據(jù)均能正確檢測(cè)出異常模式?；谛甭实臅r(shí)間序列分段線性表示有一個(gè)參數(shù)：斜率差值的閾值。實(shí)驗(yàn)表明,檢測(cè)結(jié)果受閾值影響較小。隨著d值的增大，分段數(shù)目越少，壓縮率越高。對(duì)于南水北調(diào)工程安全檢測(cè)數(shù)據(jù)，當(dāng)d>4時(shí)壓縮率保持不變，檢測(cè)結(jié)果受閾值影響較小；對(duì)于人工合成數(shù)據(jù)，當(dāng)d>3時(shí)，壓縮率保持不變，檢測(cè)結(jié)果受閾值影響較小，兩種數(shù)據(jù)驗(yàn)證均取得了正確的檢測(cè)結(jié)果。

4 結(jié)束語

針對(duì)如何在大量的時(shí)間序列中提取極少出現(xiàn)的異常模式，將時(shí)間序列進(jìn)行線性分割，將不限制分段數(shù)目與子序列長度的方法相結(jié)合，提出了基于斜率與最大時(shí)間跨度的分段算法。提取了時(shí)間序列的極值差、斜率、均值三個(gè)特征值，將其映射到特征空間，降低了時(shí)間序列的維數(shù)，實(shí)現(xiàn)了較高的壓縮率。通過實(shí)測(cè)數(shù)據(jù)與合成數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，均能高效地檢測(cè)出異常時(shí)間段，證明了該算法的有效性與可行性。

[1] 賈國棟.多相關(guān)周期性時(shí)間序列上的異常模式關(guān)聯(lián)規(guī)則挖掘[D].沈陽:東北大學(xué),2010.

[2] 譚宏強(qiáng),牛 強(qiáng).基于滑動(dòng)窗口及局部特征的時(shí)間序列符號(hào)化方法[J].計(jì)算機(jī)應(yīng)用研究,2013,30(3):796-798.

[3] KORN F,JAGADISH H V,FALOUTSOS C.Efficiently supporting ad hoc queries in large datasets of time sequences[J].ACM SIGMOD Record,1997,26(2):289-300.

[4] 陳帥飛,呂 鑫,戚榮志,等.一種基于關(guān)鍵點(diǎn)的時(shí)間序列線性表示方法[J].計(jì)算機(jī)科學(xué),2016,43(5):234-237.

[5] 曹文平,羅 穎,熊啟軍,等.基于二次回歸的時(shí)間序列分割算法[J].計(jì)算機(jī)光盤軟件與應(yīng)用,2012(18):157.

[6] 劉 博,郭建勝.改進(jìn)的多元時(shí)間序列符號(hào)化表示方法研究[J].計(jì)算機(jī)仿真,2015,32(1):314-317.

[7] OBUCHOWSKI J,WYOMASKA A,ZIMROZ R.The local maxima method for enhancement of time-frequency map and its application to local damage detection in rotating machines[J].Mechanical Systems and Signal Processing,2014,46(2):389-405.

[8] KEOGH E,CHAKRABARTI K,PAZZANI M,et al.Dimensionality reduction for fast similarity search time series databases[J].Knowledge and Information Systems,2008,3(3):263-286.

[9] GEORGOULAS G,KARVELIS P,STYLIOS C D,et al.Automatizing the broken bar detection process via short time Fourier transform and two-dimensional piecewise aggregate approximation representation[C]//IEEE energy conversion congress and exposition.[s.l.]:IEEE,2014:3104-3110.

[10] 李 敏,劉 軻,羅惠瓊,等.基于混合高斯模型的異常檢測(cè)算法改進(jìn)[J].計(jì)算機(jī)應(yīng)用與軟件,2014,31(6):198-200.

[11] 詹艷艷，徐榮聰.時(shí)間序列異常模式的K-均距異常因子檢測(cè)[J].計(jì)算機(jī)工程與應(yīng)用，2009，45(9)：141-145.

[12] 蘇衛(wèi)星,朱云龍,劉 芳,等.時(shí)間序列異常點(diǎn)及突變點(diǎn)的檢測(cè)算法[J].計(jì)算機(jī)研究與發(fā)展,2014,51(4):781-788.

[13] 尚 華.兩類時(shí)間序列模型的異常值檢測(cè)研究[D].北京:首都經(jīng)濟(jì)貿(mào)易大學(xué),2016.

[14] 李少波,孟 偉,璩晶磊.基于密度的異常數(shù)據(jù)檢測(cè)算法GSWCLOF[J].計(jì)算機(jī)工程與應(yīng)用,2016,52(19):7-11.

[15] 孫梅玉.基于距離和密度的時(shí)間序列異常檢測(cè)方法研究[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(20):11-17.