一種基于滑動窗口的時間序列異常檢測算法

裴麗鵲

（福建對外經濟貿易職業技術學院信息技術系，福建 福州 350016）

一種基于滑動窗口的時間序列異常檢測算法

裴麗鵲

（福建對外經濟貿易職業技術學院信息技術系，福建 福州 350016）

時間序列的異常檢測的應用越來越廣泛，本文是討論在基于分段線性的FKD時間序列模式表示基礎上時間序列的異常檢測。文中提出了一種基于滑動窗口的時間序列模式偏離和窗口異常度的概念，并在此基礎上提出了基于滑動窗口的時間序列模式異常的檢測算法。通過實驗證明了該算法是合理的、有效的。

時間序列；滑動窗口；異常檢測

1 引言

數據挖掘是從大量的數據中抽取潛在的、新穎的、有價值的過程。數據挖掘的主要任務是發掘相似的模型，但異常檢測在近年越來越受關注，特別在金融、通信、網絡監測等眾多領域有著廣泛的應用。

當前異常數據挖掘的方法主要有五類[1]：基于統計的方法、基于聚類的方法、基于距離的方法、基于密度的方法、基于偏差的方法。其中基于統計的方法包括了基于分布的方法和基于深度的方法。但這些方法主要是針對于無序的數據集，而對于序列值之間存在嚴格順序的時間序列并不適用。

2 相關研究

國外于1995年開始對于時間序列的異常研究有所研究，近年來又提出了許多新的觀點和方法，而國內起步較晚，但近幾年來發展很快。對于異常數據挖掘的研究工作目前還不是很成熟，甚至迄今為止，在學術界上時間序列的異常還沒有一個公認的定義。和異常相關的定義主要有新穎、不規則、奇異等。根據異常的表現形式不同，時間序列的異常可以分為三種：序列異常、點異常和模式異常。

C.Shahabi等[2]提出了TSA-Tree的改進型來實現奇異模式的查詢，他們把奇異模式定義為時間序列上的突然變化，通過小波系數的局部極大值來發現。

Junshui Ma和Simon Perkins[3][4]提出基于支撐向量回歸模型的算法，可以在線發現時態序列的新穎事件。采用SVR(Support vector regression)模型對歷史時間序列建立回歸模型，判斷新到來的序列點與SVR回歸模型的匹配程度，考察連續一段時間內的匹配情況，給出其為新穎事件的置信度。建立回歸模型時采用時延嵌入過程得到訓練樣本集，SVR回歸模型可增量更新。

肖輝[5]在時間序列的模式表示基礎上，提出了基于模式密度的時間序列的模式異常定義，用“異常因子”來衡量時間序列模式的異常程度。根據模式異常定義，提出了時間序列的異常檢測算法。

文獻[2]研究的是時間序列的點異常，文獻[3，4]是對時間序列根據建立的訓練模型進行訓練，從而檢測相對訓練模型序列點的離群度，文獻[5]是對時間序列的模式進行異常判斷。

本文是討論時間序列在基于分段線性的FKD時間序列模式表示基礎上，提出了使用窗口異常度來檢測數據流在某一段時間內時間序列數據的異常。

3 相關定義

3.1 滑動窗口模型

本文采用的是基于固定窗口的大小固定不變的滑動窗口，滑動窗口以固定窗口為單位不斷更新。每進入一個新的固定窗口，若滑動窗口已滿，最先進入滑動窗口的一個固定窗口被刪除，滑動窗口隨之更新一次；否則，將新進的固定窗口添加到滑動窗口的尾部。滑動窗口內的數據對象對應一個固定窗口的序列 〈FW1，FW2， Λ，FWK〉，固定窗口采用的是文獻[6]定義1，滑動窗口的模型如圖1所示。

圖1 滑動窗口模型

3.2 Minkowski距離[7]

Minkowski距離是歐幾里德距離的推廣，也稱 Lp距離.對于給定時間序列列 X={x1，x2，…，xn}和 Y={y1，y2，…，yn}，其 Lp距離定義如下：

其中，當p=1時稱為曼哈頓距離，當p=2時為歐氏距離，當p=∞時稱為最大距離。歐幾里德距離是時間序列查詢中使用最早也是最廣的一種相似度量。L1距離在時間序列查詢中使用也比較多，在測量誤差滿足加性拉普斯分布時最優，穩定性較高。Keogh等對歐世距離進行改進，根據對查詢序列不同的部分的程序，使用了帶加權重的歐式距離，通過不斷改變權重支持線性漂移。距離公式為：

3.3 模式距離

在文獻 [6]中已經詳細討論了時間序列的KFD表示，這里我們直接給出它的定義：

對于時間序列 X=〈x1，x2，…，xn〉，采用固定窗口線性分段后，時間序列X為固定窗口的集合，即 X=〈FWx1，FWx2，…，FWxk〉。 其中 K=int(N/k)+1。其中FWX的符號表示如下：

其中，wi表示時間區間[wi-1,wi]的兩個端點坐標，kiwi表示連接模式wi兩端點斜率，diwi表示連接模式wi的截距。

在對時間序列進行FKD表示之后，我們從模式中抽取3個特征：線段的長度、線段的斜率和線段的截距。模式距離采用使用加權的曼哈頓距離，定義模式距離如下：

任取模式 f1=（l1，k1，d1）和 f2=（l2，k2，d2） ，其中li，ki，di分別表示模式的斜率和截距，模式 f1，f2之間的L1距離定義為：

3.4 模式偏離度

模式偏離度是指固定窗口中某一模式與其它模式的模式距離小于給定閾值 的模式總數的倒數，符號化表示為：

其中Com（Li，μ）表示固定窗口中模式距離小于給定閾值μ的模式總數。模式的偏離度表示的是在滑動窗口內如果與該模式的近似模式越多，那么偏離度較小，模式越正常，否則該模式異常的可能性較大。

3.5 窗口異常度

固定窗口FWTJ的異常度為固定窗口中各個模式偏離度的累加與各個模式數量總和的比值，簡稱窗口異常度，符號化表示為：

其中 Li∈。Count表示是各個模式數量的總和。窗口異常度表示在滑動窗口內，由各個模式組成的固定窗口的異常程度，如果固定窗口中的模式在滑動窗口中出現的次數越多，那么它的偏離度越小，由它構成的固定窗口的異常度也就越少，那么它的偏離度就越大，由它們構成的固定窗口的異常度也就越大，固定窗口的異常度也就越大。

4 時間序列異常檢測算法

根據FKD算法，將時間序列根據固定窗口的大小和斜率與截距來確定固定模式的數目，由此我們將離當前數據流最近方向的W個固定窗口構成一個滑動窗口。而固定窗口大小的分段點確定是根據數據流的速度，在保證固定窗口大小合適的模式的基礎上，以時間間隔來作為固定窗口分隔點。

當數據流一接收到，就生成一個滑動窗口，同時也生成一個固定窗口，并將其添加到滑動窗口中，隨著數據流的不斷到來，滑動窗口中的固定窗口不斷增加直到到達他的長度W為止。當數據對象Xi到達時，根據FKD算法進行處理，來確定模式，接著處理下一個數據。隨之數據不斷的流入，在固定窗口中不斷處理新的數據流，計算數據流進行模式處理的同時，不斷的計算該窗口中各模式的模式距離，從而進一步計算出該窗口的異常度。

算法：Time_Series_Outlier_Detecive（dataStream,maxSlope,

輸入：數據流dataStream，斜率閾值maxSlope，固定窗口時間間隔FixWindowInvertal，

滑動窗口大小slidingWindowSize，模式距離閾值u

輸出：當前基本窗口異常度outlierDegree

Step1：初始化固定窗口

初始化滑動窗口

在滑動窗口中添加固定窗口

X1=GetCurrentData(dataStream)

Step2：While(DataStream)

Tempdata=GetCurrentData(dataStream)

Step3：if沒到到固定窗口的分段時間間隔

While(到固定窗口的分段時間間隔)

If沒有下一個數據流

固定窗口添加模式操作

計算并輸出窗口異常度

產生新的固定窗口

在滑動窗口增加基本窗口

Else

根據FKD算法處理新的數據流

End if

End while

Step4：if到固定窗口的分段時間

X2=GetCurrentData(dataStream)

根據FKD算法處理計算機數據流X2

End if

End while

5 實驗結果及分析

5.1 實驗方法

本次實驗采用了Ma_Data模擬流數據變形的仿真數據，通過不設定窗口異常度閾值和設定窗口異常度閾值兩種方式，來觀察算法的性能。

Ma_Data數據流是由Ma等人在文獻[4]中用于檢測新穎事件的時間序列仿真數據集，如由下隨機過程產生：

其中 t=1，2，K，N，N=1200。 n（t） 是一個加性高斯噪音，均值為 0，標準差為 0.1。 e1（t）是一個異常事件，定義如下：

其中，n1（t）符合正態分布 N（0，0.5）。

我們在實驗中又對Ma_Data數據流進行變形，增加 X3（t）數據流，

5.2 實驗結果

5.2.1 不設定窗口異常度閾值的情況

在實驗中，首先我們不設定窗口異常度閾值，將所有窗口的異常度都顯示出來，窗口異常度的取值范圍為[0，1]。變型的Ma_Data數據的窗口異常度結果顯示如圖2：

圖2 不設閾值的變型的Ma_Data數據數據的窗口異常度

5.2.2 設定窗口異常度閾值的情況

在實驗中，設我們窗口異常度閾值為0.3，若窗口的異常度超過0.3，認為窗口異常，輸入窗口的異常度，否則認為窗口無異常。變型的Ma_Data數據數據的窗口異常度結果顯示如圖3

所示：

圖3 設定閾值的變型的Ma_Data數據數據的窗口異常度

6 小結

時間序列的異常檢測近年來引起了許多學者的關注，但至今為止，還沒有一個公認的定義。本文在時間序列采用FKD算法的模式表示基礎上，提出了使用模式距離來表示該模式的相似度，通過窗口的異常度來描述模式的異常度，同時給出了相應的異常檢測算法。在仿真數據流上的實驗表明：算法能夠較準確并及時的發現時間序列的異常窗口，該算法是合理的、有效的。

[1]杜洪波.時間序列相似性查詢及異常檢測算法的研究[D].沈陽：沈陽工業大學,2008.

[2]C.Shahabi,X.Tian,and W.Zhao.Tsa-Tree:A wavelet-based approach to improve the efficiency of multi-level surprise and trend queries[C].Proceedings of 12th International Conference on Scientific and Statistical Database Management.Washington:IEEE Computer Society.2000.P55-68.

[3]Junshui Ma and Simon Perkins.Time-series Novelty Detection Using One-class Support Vector Machines[C].Preceedings of the International Joint Conference on Neural Networks,2003

[4]Junshui Ma and Simon Perkins Online Novelty Detection on Temporal Sequences[C].Proceedings of the International Conference on Knowledge Discovery and Data Mining.NewYork:ACM Press.2003.P24-27.

[5]肖輝.時間序列的相似性查詢與異常檢測[D].上海：復旦大學,2005.

[6]裴麗鵲.一種基于分段線性的FKD時間序列模式表示[J].赤峰學院學報（自然科學版）,2008,(4):55-58.

[7]曲吉林.時間序列挖掘中索引與查詢技術的研究[D].天津：天津大學,2006.

AN OUTLIER DETECTION ALGORITHM OF TIME SERIES BASED ON SLIDING WINDOW

PEI Li-que
（Department of information&technology，Fujian international business&Economic college,Fuzhou Fujian 350016）

With the background of the extensive application of the outlier detection on time series, this paper discusses the outlier detection using FKD time series pattern based on piece-wise linear.This article also proposes a concept of the deviation of time series pattern and window abnormal degree base on sliding window and a detection algorithm accordingly.The related experiment showed that this detection algorithm is reasonable and effective.

time series；sliding window；outlier detection

TP310.6

A

1672－2868（2011）03－0028－04

2011-2-25

裴麗鵲（1977-），女，福建寧德人。福建對外經濟貿易職業技術學院副教授，研究方向：數據挖掘、計算機輔助教學

責任編輯：陳 侃