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

裴麗鵲

（福建對外經(jīng)濟貿(mào)易職業(yè)技術(shù)學(xué)院信息技術(shù)系，福建 福州 350016）

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

裴麗鵲

（福建對外經(jīng)濟貿(mào)易職業(yè)技術(shù)學(xué)院信息技術(shù)系，福建 福州 350016）

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

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

1 引言

數(shù)據(jù)挖掘是從大量的數(shù)據(jù)中抽取潛在的、新穎的、有價值的過程。數(shù)據(jù)挖掘的主要任務(wù)是發(fā)掘相似的模型，但異常檢測在近年越來越受關(guān)注，特別在金融、通信、網(wǎng)絡(luò)監(jiān)測等眾多領(lǐng)域有著廣泛的應(yīng)用。

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

2 相關(guān)研究

國外于1995年開始對于時間序列的異常研究有所研究，近年來又提出了許多新的觀點和方法，而國內(nèi)起步較晚，但近幾年來發(fā)展很快。對于異常數(shù)據(jù)挖掘的研究工作目前還不是很成熟，甚至迄今為止，在學(xué)術(shù)界上時間序列的異常還沒有一個公認的定義。和異常相關(guān)的定義主要有新穎、不規(guī)則、奇異等。根據(jù)異常的表現(xiàn)形式不同，時間序列的異?？梢苑譃槿N：序列異常、點異常和模式異常。

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

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

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

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

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

3 相關(guān)定義

3.1 滑動窗口模型

本文采用的是基于固定窗口的大小固定不變的滑動窗口，滑動窗口以固定窗口為單位不斷更新。每進入一個新的固定窗口，若滑動窗口已滿，最先進入滑動窗口的一個固定窗口被刪除，滑動窗口隨之更新一次；否則，將新進的固定窗口添加到滑動窗口的尾部?；瑒哟翱趦?nèi)的數(shù)據(jù)對象對應(yīng)一個固定窗口的序列 〈FW1，F(xiàn)W2， Λ，F(xiàn)WK〉，固定窗口采用的是文獻[6]定義1，滑動窗口的模型如圖1所示。

圖1 滑動窗口模型

3.2 Minkowski距離[7]

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

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

3.3 模式距離

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

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

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

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

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

3.4 模式偏離度

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

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

3.5 窗口異常度

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

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

4 時間序列異常檢測算法

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

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

算法：Time_Series_Outlier_Detecive（dataStream,maxSlope,

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

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

輸出：當(dāng)前基本窗口異常度outlierDegree

Step1：初始化固定窗口

初始化滑動窗口

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

X1=GetCurrentData(dataStream)

Step2：While(DataStream)

Tempdata=GetCurrentData(dataStream)

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

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

If沒有下一個數(shù)據(jù)流

固定窗口添加模式操作

計算并輸出窗口異常度

產(chǎn)生新的固定窗口

在滑動窗口增加基本窗口

Else

根據(jù)FKD算法處理新的數(shù)據(jù)流

End if

End while

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

X2=GetCurrentData(dataStream)

根據(jù)FKD算法處理計算機數(shù)據(jù)流X2

End if

End while

5 實驗結(jié)果及分析

5.1 實驗方法

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

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

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

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

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

5.2 實驗結(jié)果

5.2.1 不設(shè)定窗口異常度閾值的情況

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

圖2 不設(shè)閾值的變型的Ma_Data數(shù)據(jù)數(shù)據(jù)的窗口異常度

5.2.2 設(shè)定窗口異常度閾值的情況

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

所示：

圖3 設(shè)定閾值的變型的Ma_Data數(shù)據(jù)數(shù)據(jù)的窗口異常度

6 小結(jié)

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

[1]杜洪波.時間序列相似性查詢及異常檢測算法的研究[D].沈陽：沈陽工業(yè)大學(xué),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].上海：復(fù)旦大學(xué),2005.

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

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

AN OUTLIER DETECTION ALGORITHM OF TIME SERIES BASED ON SLIDING WINDOW

PEI Li-que
（Department of information&technology，F(xiàn)ujian 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-），女，福建寧德人。福建對外經(jīng)濟貿(mào)易職業(yè)技術(shù)學(xué)院副教授，研究方向：數(shù)據(jù)挖掘、計算機輔助教學(xué)

責(zé)任編輯：陳 侃