一种基于滑动窗口的时间序列异常检测算法

裴丽鹊

（福建对外经济贸易职业技术学院信息技术系，福建 福州 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-），女，福建宁德人。福建对外经济贸易职业技术学院副教授，研究方向：数据挖掘、计算机辅助教学

责任编辑：陈 侃