基于異常因子的時間序列異常模式檢測

劉雪梅，王亞茹

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

0 引 言

南水北調工程是緩解我國北部地區水資源緊張，優化水資源配置的一項戰略性基礎設施工程。在工程安全監測中有一類數據是按照發生的時間順序保存的，這類數據叫做時間序列。在時間序列大量的數據中，有些極少出現的子序列與其他子序列有顯著的不同，使得人們懷疑它是由不同的機制產生的，這些子序列稱為異常模式[1]。在工程安全中，異常模式往往更能夠幫助人們認識事物。因此，從海量數據中挖掘出異常模式，對保證南水北調工程的安全具有重要意義。

1 時間序列上進行異常模式挖掘

時間序列具有高維性、海量性、含有大量噪聲等特征，直接在原始時間序列上進行異常模式挖掘要花費大量的時空代價，會影響算法的可靠性。

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

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

目前用于異常檢測的方法可分為基于模型的檢測方法[10]、基于聚類的檢測方法[11]、基于異常點檢測方法[12-13]、基于密度的檢測方法[14-15]。基于異常點檢測方法較為簡單，但時間序列的高維性使該方法失效。基于密度的異常檢測方法精度高，但時空復雜度高。基于聚類的方法對于發現頻繁模式比較適用。基于模型的方法，建立模型和參數的估計存在一定的困難。

在時間序列分段線性表示的基礎上，文中提取子序列的斜率、均值、極值差，將時間序列映射到該特征空間，每個子序列就對應到該特征空間中的一個點，用特征值構成的三元組表示各子序列在特征空間的位置，在此基礎上計算各模式間的距離。通過一定的處理，得到正常模式間的距離，比較每個模式的距離與正常模式距離的比值，提取異常模式。

2 基于異常因子的時間序列異常模式探測算法

2.1 時間序列分段線性表示

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

(1)ti是時間序列的起點；

(2)ti是時間序列的終點；

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

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

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

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

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

輸出：時間序列的分段線性表示

Step1:序列的第一個點加入重要點序列。

s=(x1,1)

Step2:分別計算以點xi為端點的相鄰兩個線段的斜率。

j=0;k=1;h=2

for(i=1 to n)

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

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

Step3:判斷點xi是否為重要點，若是，則加入重要點集合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為子序列的最大時間跨度

s=s+(xi,i)

Step4:最后一個點加入重要點序列。

s=s+(xn,n)

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

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

2.2 異常模式探測算法

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

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

vd=ximax-ximin

(1)

定義3 模式斜率：連接重要點的直線段的實際斜率。

(2)

定義4 模式均值：子序列中各時間點數據均值。

(3)

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

dist(p,q)=

(4)

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

(5)

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

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

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

(6)

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

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

算法2：異常模式檢測算法。

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

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

Step1:計算子序列間的模式距離距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中每個子序列與其他子序列之間的距離，去掉最大值后的均值作為子模式的距離d[i]。所有子模式的距離排序后取中位數，各中位數的均值作為正常模式距離。

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

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

3 實 驗

3.1 實驗結果

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

利用算法1對時間序列進行分段線性表示，結果如圖2所示。

圖1 南水北調工程監測數據原始時間序列

圖2 分段線性表示后的時間序列

利用人工合成數據進行檢驗，原始時間序列如圖3所示。

圖3 人工合成數據原始時間序列

利用算法1對人工數據進行分段線性表示，結果如圖4所示。

圖4 人工合成數據分段線性表示

當斜率閾值d取不同值時，對實測數據異常檢測的輸出結果如表1所示。

表1 d取不同值時的實驗結果(實測數據)

斜率閾值d取不同值時，對人工數據異常檢測結果如表2所示。

表2 d取不同值時的實驗結果(異常數據)

3.2 實驗分析

結果表明,用實測數據和合成數據均能正確檢測出異常模式。基于斜率的時間序列分段線性表示有一個參數：斜率差值的閾值。實驗表明,檢測結果受閾值影響較小。隨著d值的增大，分段數目越少，壓縮率越高。對于南水北調工程安全檢測數據，當d>4時壓縮率保持不變，檢測結果受閾值影響較小；對于人工合成數據，當d>3時，壓縮率保持不變，檢測結果受閾值影響較小，兩種數據驗證均取得了正確的檢測結果。

4 結束語

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

[1] 賈國棟.多相關周期性時間序列上的異常模式關聯規則挖掘[D].沈陽:東北大學,2010.

[2] 譚宏強,牛 強.基于滑動窗口及局部特征的時間序列符號化方法[J].計算機應用研究,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] 陳帥飛,呂 鑫,戚榮志,等.一種基于關鍵點的時間序列線性表示方法[J].計算機科學,2016,43(5):234-237.

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

[6] 劉 博,郭建勝.改進的多元時間序列符號化表示方法研究[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] 李 敏,劉 軻,羅惠瓊,等.基于混合高斯模型的異常檢測算法改進[J].計算機應用與軟件,2014,31(6):198-200.

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

[12] 蘇衛星,朱云龍,劉 芳,等.時間序列異常點及突變點的檢測算法[J].計算機研究與發展,2014,51(4):781-788.

[13] 尚 華.兩類時間序列模型的異常值檢測研究[D].北京:首都經濟貿易大學,2016.

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

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