第24卷第11期2007年11月 计算机应用研究
Applicat ion Research of Com puters Vol. 24No. 11
Nov. 2007
基于时间序列模式表示的异常检测算法
詹艳艳, 陈晓云, 徐荣聪
(福州大学数学与计算机科学学院, 福州350002)
*
摘 要:提出了一种基于时间序列的模式表示提取时间序列异常值的异常检测算法(PREOV) 。时间序列的模式表示本身就具有压缩数据、保持时间序列基本形态的功能, 并且具有一定的除噪能力。在时间序列模式表示的基础上提取异常值, 可以大大提高算法的效率和准确性, 达到事半功倍的效果。在本算法中, 还使用了一定的剪枝策略, 使得算法的时间复杂度进一步降低。该算法计算简单、实现方便、无须训练, 可以支持时间序列的动态增长。
关键词:斜率; 时间序列; 模式表示; 支持数; 异常值
中图分类号:TP 391. 41 文献标志码:A 文章编号:1001-3695(2007) 11-0096-04
Out lier detection a lgorith m based on pat t ern r epr esent at ion of t im e series
ZHAN Ya n-ya n, CHEN Xiao-yun, XU Rong-cong
(S chool of M athematics &Comp uter S cience, Fuz hou Univer sity, Fuzhou 350002, China)
Abst ract :This pa per im ported a n algorit hm which was ba sed on the pat tern repres enta tion of t im e series ext ra ct outlier v alue (PREOV) . The pat tern represent at ion of tim e series its elf ha d t he function of com pres s da ta a nd keep the bas ic s ha pe of t im e s eries, a nd it had a cert ain ext ent effect of noises rem ova l. Ba sed on P RE OV could enorm ously increas e the efficiency and ve-ra city of a lgorithm , a nd g ot tw ice t he result wit h half t he effort. Besides, us ed som e st rat egy of pruning , w hich m a de the algo-rithm ’s t im e com plexity m ore lower. And t his algorit hm can be easy calcula ted a nd carry out, t he t raining is needless and it can s upport t he dynam ic increase of tim e series. Key wo rds:slope; t im e series; pa tt ern repres enta tion; support; outlier va lue 时间序列是指按照时间先后顺序排列的各个观测记录的有序集合, 广泛存在于商业、经济、医疗等领域。随着时间的推移, 时间序列通常包含大量的数据。对时间序列进行分析, 可以揭示事物运动、变化和发展的内在规律, 对于人们正确认识事物并据此作出科学的决策具有重要的现实意义。
在对时间序列进行分析时, 经常希望能够发现这些时间序列在不同时间段的形态有何关联关系。这种关联关系一般表现为时间序列中频繁出现的变化模式和极少出现的变化模式。这种极少出现的变化模式称之为异常模式。在某些领域, 异常模式的发现对人们来说往往更有价值。例如, 医院可以从病人的心电图序列中发现异常模式从而进行诊断和治疗。
目前为止, 时间序列的异常检测已广泛应用到医疗、金融、入侵检测以及可疑活动监控等领域。
法并不适用于时间序列。
时间序列的研究工作还不是很成熟, 甚至到目前为止, 对于时间序列的异常还没有一个公认的定义。许多研究者在自己的研究过程中都提出了不同的时间序列异常定义, 如新颖[1～4]、奇异[5, 6]、变化点[7]、异常[8, 9]、不正常的[10]等。
按照异常的表现形式不同, 线性时间和空间上时间序列的异常主要可以分为点异常和模式异常两种, 它们都是用于发现一条时间序列上的异常情况的。本文主要研究的是模式异常。它是指在一条时间序列上与其他模式之间具有显著差异的模式。事实上, 点异常也可以认为是长度为1的模式异常。
本文提出了一种基于时间序列的模式表示提取时间序列异常值的异常检测算法。由于时间序列的模式表示方法本身就具有刻画时间序列的主要形态而忽略那些微小细节的特点。它可以对时间序列进行压缩, 换来更小的存储和计算代价; 可以只保留时间序列的主要形态, 去除细节干扰, 更能反映时间序列的自身特征。
近年来, 异常检测作为数据挖掘的一个分支, 正受到越来越广泛的关注。以往的很多研究都是基于无序数据集的, 而时间序列的序列点之间又恰恰是有序的。因此很多异常检测算
定义1 时间序列的模式表示。
收稿日期:2006-08-21; 修返日期:2006-10-20 基金项目:福建省自然科学基金资助项目(Z051503) ; 校科技发展基金资助项目(2004-XQ-17)
作者简介:詹艳艳(1981-) , 女, 浙江绍兴人, 硕士研究生, 主要研究方向为机器学习、数据挖掘(yanyan. 4x@163. com) ; 陈晓云(1970-) , 女, 福建晋江人, 副教授, 硕导, 主要研究方向为数据挖掘、机器学习、模式识别; 徐荣聪(1952-) , 男, 福建莆田人, 副教授, 硕导, 主要研究方向为计算数学等.
1 相关工作
2 相关定义
时间序列的模式是指时间序列的某种变化特征, 它可以是时间序列离散化后的符号, 也可以是时间序列的傅里叶变换系数等。通过提取时间序列的模式, 将时间序列变换到模式空间, 就得到了时间序列的模式表示。
时间序列的模式表示方法有很多, 主要有频域表示、奇异值表示、符号化表示、分段线性表示等几种。本文所讨论的基于时间序列模式表示的异常检测算法可以应用到所有的模式表示方法中。本文实验所采用的是分段线性表示方法中的IE O 表示(这是在笔者另外一篇论文“基于插值边缘算子的时间序列模式表示”中提出的时间序列PLR 方法) 。
定义2 时间序列的子模式。
设有时间序列X =枙x 1, x 2, …, x n 枛和X 1=枙x i 1, x i 2, …, x in 枛。其中x i 1, x i 2, …, x in ∈X, 并且有1
定义3 支持数。
设有时间序列X =枙x 1, x 2, …, x n 枛, 及其子模式X 1=枙x i 1, x i 2, …, x in 枛。如果子模式X 1在时间序列X 中出现了k 次, 则称该子模式的支持数为k(支持数k 是一个整数) 。
3 基于时间序列模式表示的异常检测算法
在本文中提出了一种基于时间序列模式表示的异常检测(PREOV) 算法。该算法在时间序列模式表示的基础上提取时间序列的异常值进行异常检测。3. 1 算法的基本思想
算法主要是基于一种逆向频繁模式挖掘思想, 即异常模式肯定是时间序列中最不频繁的模式, 也就是支持数最低的模式。换句话说, 支持数越高的模式, 其异常值就越小; 反之, 支持数越低的模式, 其异常值就越大。异常值是体现时间序列中某一个模式异常程度的值。
在算法执行过程中, 首先使用时间序列的IEO 表示方法得到时间序列的模式表示; 然后用直线段将时间序列模式表示的序列点两两连接, 并且提取每一个线段的特征值, 即斜率和线段长度。在接下去的运算中, 把每一个线段作为一个候选子模式, 分别按照线段的斜率、长度、高度计算每一个候选子模式的支持数k 1, k 2, k 3。当两个候选子模式的斜率(长度、高度) 相等时(这里, 斜率和高度都取精确到小数点后一位进行比较) , 认为这两个候选子模式是相同的, 两个候选子模式的支持数都加1。这样, 就得到了每一个候选子模式的支持数。接着, 根据支持数计算每一段子模式的异常因子以及每一个序列点的异常值。
1) 子模式的高度 设X 1=枙x i 1, x i 2, …, x in 枛是时间序列X =枙x 1, x 2, …, x n 枛的子模式, slope (i) 和length (i) 分别为该子模式的斜率和长度, 则子模式的高度定义为
high (i) =|slope(i) ×length (i) |
(1)
2) 子模式的异常因子 设X 1=枙x i 1, x i 2, …, x in 枛是时间序列X =枙x 1, x 2, …, x n 枛的子模式, k 1(i) , k 2(i) , k 3(i) 分别为该子模式的斜率、长度和高度的支持数, 则斜率、长度和高度的异常因子o 1(i) , o 2(i) , o 3(i) 定义为
o j (i) =1/k j (i) ; j =1, 2, 3
(2)
该子模式的异常因子定义为
o(i) =max(norm (o 1(i) ×o 2(i) ) +nor m (o 3(i) ) )
(3)
其中:norm (i) 是一个数据规范化公式。它可以将数据规范化为0～1。其具体定义如下:
norm(sup i ) =[sup i -min(sup i ) ]/[m ax(sup i ) -min(sup i ) ](4)
显然, 此时子模式的异常因子o(i) 的值也在0～1。在本文中, 认为组成同一个子模式的各点的异常因子是相等的。3. 2 基于时间序列模式表示的异常检测算法
算法:P RE OV
输入:时间序列X =枙x 1, x 2, …, x n 枛及其长度y n 。当压缩率为85%时的时间序列X 的模式表示IEO:X I =枙x ′1, x ′2, …, x ′n 枛
及其长度n 。输出:时间序列X =枙x 1, x 2, …, x n 枛每一点的异常值。具体步骤:
a) 根据上述算法思想以及公式计算每一段子模式的异常因子。
b) for(i =0; i
子, 并且进一步去除噪声产生的单点异常*/
{if((end[i]-begin[i]==1) &&(i >=3)
&&(i
for(l =i -3; l
if(k ==1) //说明确实是由异常引起的outlier 1[j]=outlier[i];
else if(k ==0) //说明是由噪声引起的{if(outlier[i -1]>=outlier[i +1]) outlier 1[j]=outlier[i -1]; else
outlier 1[j]=outlier[i +1]; }}else
{for(j =begin[i]; j
//最后一个序列点的异常因子等于最后一个子模式的异常因子
c) for(ii =0.8; ii >=0; ii -=0. 01)
//计算该时间序列中每一点的异常值for(j =0; j
{if(outlier 1[j]>=ii) outlier 2[j]+=ii; }
d) 输出该时间序列中每一个点的异常值。3. 3 算法的两大特点
a) 基于时间序列的模式表示提取异常值, 大大减少了计算量, 减少了噪声的干扰, 提高了算法的效率和准确性。
如图1所示, (a ) 是一条具有9382个采样点的原始时间序列; (b) 是该时间序列的一个分段线性表示, 只需保存258个线段端点, 压缩率达到97. 3%, 但是仍然很好地保留了原时间序列的主要形态, 与原始序列的拟合误差仅为1. 63。
b) 使用了一定的剪枝策略, 使得算法的时间复杂度进一步降低。
本算法中时间耗费最大的地方是在计算每一个候选子模式支持数时。在算法的实现过程中, 使用一个数组s[n -1]
[2]来实现剪枝。其中:s[i][0]代表候选子模式i 的支持数,
由于每一个候选子模式至少是其本身的支持者, s[i][0]的初始值为1; s[i][1]代表与候选子模式i 相同的其他候选子模式, 由于第一个候选子模式在数组中的存放位置是从0开始的, 把数组s[i][1]的初始值设置成-1。在算法中设置两个关卡进行剪枝, 如下所示:
//计算每一个候选子模式的支持数for(i =0; i
if(s[i][1]==-1) //关卡1{for(j =i +1; j
{if(exactconver t(slope[i], exact) ==
exactconver t(slope[j], exact) ) //斜率相等{s[i][1]=i; //候选子模式i 与其本身相同 s[j][1]=i; //候选子模式i 与候选子模式j 相同 s[i][0]+=1; //候选子模式i 的支持数加1 s[j][0]+=1; //候选子模式j 的支持数加1}}}
for(j =i +1; j
s[j][0]=s[i][0];
//与候选子模式i 相同的子模式支持度相同}if(s[i][0]>max)
max =s[i][0]; //计算所有候选子模式中的最大支持度else if (s[i][0]
min =s[i][0]; //计算所有候选子模式中的最小支持度}
1.20.811.20.60.40.80.20.610
0.412139
(a)42776415
85530.20
长度原始时间为9382
序列，(b)为257, 时间1即序213942776
4158553
处理后列的分的段时间线性序表示列长度，线段为数258
目图1时间序列及其模式表示
关卡1和2的设置都是基于同一个思想, 即如果候选子模式i 和候选子模式j 相同, 而候选子模式i 与候选子模式k 不同, 那么候选子模式j 与候选子模式k 也不可能相同。这样就可以省去很大一部分由于重复计算而造成的时间耗费。虽然表面上看, 该算法的时间复杂度为O(n 2
/2) , 但由于这两个关卡的存在, 算法的实际时间复杂度是远远低于O(n 2
/2) 的, 只有当所有候选子模式之间两两均不相同时才有可能达到O(n 2/2) ; 相反, 相同的候选子模式越多, 算法的时间复杂度就越低, 当所有候选子模式均相同时, 该算法是线性的, 其时间复杂度仅为O(n) 。
4 实验及结果分析
以下的实验过程中, 在比较线段斜率和长高度时均精确到小数点后一位。
4. 1 实验1:Keog h_Data数据集4. 1. 1 实验数据
Keogh_Data 数据集是Keog h 等人[11]用于检测异常模式所使用的仿真数据集。该时间序列由以下随机过程产生:Y 1(t) =sin(50π/N t) +n(t) ; Y 2(t) =sin(50π/N t) +n(t) +e 3。其中:t =1, 2, …, N(N =800) ; n(t) 是一个加性高斯噪声, 均值为0, 标准差为0. 1; e 3(t) 是一个异常模式, 定义为
e π/N t ) -sin(50π/N t) t ∈[400, 432]
3(t) =
｛sin(750
other wise
从上面的描述中可以知道, Y 1(t) 是一个带高斯噪声的周期为32的正弦波; Y 2(t) 则是在区间[400, 432]改变了该正弦波的周期以后得到的异常模式。该异常模式使得时间序列在区间[400, 432]的波形由一个变成了两个。4. 1. 2 实验结果及分析
1) IMM 算法[1] 该算法采用人工免疫系统的负选择(ne-getive-selection) 机制来检测时间序列的异常模式。
2) TS A-Tree 算法
[5]
该算法使用TSA-T ree 的改进型来实
现异常模式的检测, 把异常模式定义为时间序列上的突然变化, 通过计算小波系数的局部极大值来发现异常模式。
3) Tarza n 算法[11] 该算法把异常模式定义为出现频率与它的期望出现频率具有显著差异的模式。该算法使用后缀树来编码所有出现的模式, 使用马尔可夫模型来预测尚未出现的模式的期望出现概率。
以上三种算法与本文算法的实验效果对比图如图2所示。
图2四种算法在Keogh_Data数据集上的实验效果对比图
实验表明:TS A-Tree 算法没有发现异常; IM M 算法发现了错误的异常模式; Tarza n 算法和PREOV 算法都可以正确地发现异常模式。但是Ta rz an 算法是在原始时间序列上发现异常模式的, 而PRE OV 算法是在时间序列模式表示的基础上发现异常模式的。由于时间序列的模式表示具有压缩数据的特点, PRE OV 算法的效率要比Tarza n 算法高, 时间耗费也更低。4. 2 实验2:Ma_Data 数据集4. 2. 1 实验数据
Ma_Data 数据集是Ma 等人
[3]
用于检测异常模式所使用
的仿真数据集。该时间序列由以下随机过程产生:X 1(t) =
sin(40π/Nt) +n(t) , X 2(t) =sin(40π/N t) +n(t) +e 1(t) , X 3(t) =sin(40π/Nt) +n(t) +e 1(t) +e 2(t)
。其中:t =1, 2, …, N(N =
1200) ; n(t) 是一个加性高斯噪声, 均值为0, 标准差为0. 1; e 1(t) 和e 2(t) 是两个异常事件, 定义为
n (t) t ∈[600, 620]e 1(t) =
{
10
otherw ise
其中:n 1(t) 符合正态分布N(0, 0. 5) 。
e sin(40π/N t) t ∈[820, 870]2(t) =
{
0. 4×0
otherw ise
可以看出, 时间序列X 1(t) 是一条长度为1200的正常时间序列; X 2(t) 是在X 1(t) 中加入了一个异常事件e 1(t) ; X 3(t) 则是在X 1(t) 中加入了两个异常事件e 1(t) 和e 2(t) 。4. 2. 2 实验结果及分析
Ma 等人提出的S VR(基于支撑向量回归模型) 与PREOV 算法的实验效果对比图如图3所示。
实验表明:SVR 算法和PREOV 算法都可以正确地发现时间序列X 2(t) 和X 3(t) 上的异常模式。但是S VR 算法必须经过训练(在实验中, M a 等人使用前400个序列点用于训练, 后800个序列点进行异常模式的检测)
[4]
, 而PRE OV 算法不需要
第11期詹艳艳, 等:基于时间序列模式表示的异常检测算法
[4]
・ ・ 99
训练也可以正确提取出异常模式, 并且可以支持时间序列的动态增长。
X 2(t ) SVR
X 3(t ) SVR
BORISYUK R, DENHAM M, HOPPENSTE ADT F, et al. An oscilla-tor y neural network model of sparse distributed memory and nov elty detection [J ]. BioS ystems, 2000, 58(1) :265-272.
[5]S HAH ABI C, TIAN X, ZHAO W. TS A-Tr ee:a wavelet-based ap-proach to impr ove the efficiency of multi-level surprise and trend que-ries[C]//Proc of the 12th Inter national Conference on Scientific and Statistical Databa se M ana gement. Washington DC:IE EE Computer Society, 2000:55-68.
PREOV PREOV
[***********][***********]001200
(a)SVR 和PREOV 算法在(b)SVR 和PREOV 算法在时间序列X 2(t ) 上的实验效果时间序列X 3(t ) 上的实验效果
图3SVR 和PREOV 算法在
Ma_Data数据集上的实验效果对比图
[6]C HAKRABARTI S, S ARAQWAGI S, DOM B. Mining sur pr ising pat-ter ns using tempor al description length[C]//Pr oc of the 24th Interna-tional Confer ence on Ver y Larg e Data Bases. San Francisco:Morgan Kaufmann Publisher s, 1998:606-617.
5 结束语
由于时间序列的海量和复杂的数据特点, 直接在时间序列上进行数据挖掘不但在储存和计算上要花费高昂代价而且还可能会影响算法的准确性和可靠性。本文提出了一种基于时间序列模式表示的异常检测算法。该算法在时间序列模式表示方法的基础上提取时间序列的异常值, 提高了算法的效率和准确性, 达到事半功倍的效果。本算法无须训练, 可以支持时间序列的动态增长。参考文献:
[1]
AS GUPTA D, FORRES T S . Novelty detection in time series da ta using ideas from immunology[C]//Proc of the 5th Inter national Con-ferenceon Intelligent S ystems. 1996:82-87. [2]
MA J , PERKINS S . Time-series novelty detection using one-cla ss sup-port vector machines [C]//Pr oc of Interna tional J oint Conference on Neura l Networks. 2003. [3]
MA J , PERKINS S. Online novelty detection on temporal sequences [C]//Proc of Inter national Conference on Knowledge Discovery and Da ta Mining. New York:ACM Press, 2003:24-27.
[9][8][7]
YAMANIS HI K, TAKEUCHI J. A unifying fr amework for detecting outlier s and change points from non-stationary time ser ies data[C]//Proc of the 8th ACM SIGKDD Interna tional C onfer ence on Knowledg e Discovery a nd Data M ining. New Yor k:ACM Pr ess, 2002:676-681. WHITEHEAD B, HOYT W A. Function appr oximation approa ch to anomaly detection in propulsion system test data [J]. Journal of P ro-pulsio n and Po we r, 1995, 11(5) :1074-1076.
DECOSTE D. M ining multivar iate time-ser ies sensor data to discover behavior envelopes[C]//Pr oc of the 3r d Conference on Knowledg e Discovery a nd Data M ining. [S. l. ]:AAAI Press, 1997:151-154.
[10]J AGADIS H H V, KOUDAS N, MUTHUKRIS HNAN S. Mining devi-ants in a time series databa se[C]//Proc of the 25th Inter national Conference on Ver y Lar ge Data Ba ses. San Francisco:Mor gan Kauf-mann Publisher s, 1999:102-113.
[11]KEOGH E, LONARDI S, C HIU W. Finding surpr ising patterns in a
time series databa se in linea r time and space [C]//Proc of the 8th ACM S IGKDD Inter national Confer ence on Know ledge Discov ery and Data Mining. New York:AC M Press, 2002:550-556.
(上接第45页) 空间, 存储效率高。另一方面, 对于有向图的存
的平均估计执行时间为O(L ×K +MFL ×MFN ×log L) 。
储, 判断到底应用哪种形式的存储结构, 主要取决于该有向图是稀疏图还是稠密图。但在实际应用中, 由于无法预知大型数据库数据结构转换后的有向项集图到底是稀疏图还是稠密图, 无法给出统一存储结构标准。三叉链表结构不受此影响。因此, 三叉链表结构的提出可以真正规范大型有向图的存储结构标准。5. 2 时间特性
算法在时间上的总代价包括两个组成部分, 即有向项集图构建算法的时间代价和最大频繁项集挖掘算法的时间代价。有向项集图构建算法的时间代价主要取决于一次事务数据库扫描过程中的二进制编码与支持度计数, 即取决于事务数据库的事务总数L 和数据项总数K 。它的平均估计执行时间为O(L ×K) 。最大频繁项集挖掘算法的时间代价主要取决于遍历有向项集图时的执行次数和项集Tidlis t 的交操作(与运算) 。由于三叉链表存储结构中的节点可以通过连接链表存储的地址直接定位搜索, 执行次数主要取决于最大频繁项集的平均长度MFL 和最大频繁项集的个数MFN 。它的平均估计执行时间为O(M FL ×M FN) 。项集Tidlist 交操作(与运算) 的时间由事务数据库的事务总数L 决定。如果将每一个tid 的比较作为基本操作的话, 并应用最优化的位串比较算法(如对半方法) , 它的平均估计执行时间是O (log L ) 。因此, 整个算法
[5][4][2]
6 结束语
发现最大频繁项集是多种数据挖掘应用中的关键问题。本文提出的存储结构及挖掘算法可以较好地满足大型数据库转换数据结构后对有向项集图的高效存储要求, 以及关联规则中挖掘最大频繁项集的高效时间要求, 有效地解决了关联规则挖掘中所遇到的技术难点, 具有一定的理论价值和现实意义。参考文献:
[1]
HEN M S, HAN J ia-wei, YU P S. Data mining:an ov erview fr om database per spective [J]. IE EE Transactions o n Knowle dge and Da ta Engineering, 1996, 8(6) :866-883.
许卓群, 杨冬青, 唐世渭, 等. 数据结构与算法[M]. 北京:高等教育出版社, 2005:254-270. [3]
LEI Wen, LI Min-qiang. A new association rules mining algorithms based on directed itemsets gr aph[C]//Pr oc of the 9th Int ’l Conf RS -FDGrc. 2003:660-664.
宋志平, 李应红, 屈裕安. 大型有向图的三叉链表式存储结构[J ]. 计算机工程与应用, 2002, 38(21) :39-41.
黄建设. 一种改进的关联规则算法探讨[J]. 计算机仿真, 2005, 22(12) :72-75.
第24卷第11期2007年11月 计算机应用研究
Applicat ion Research of Com puters Vol. 24No. 11
Nov. 2007
基于时间序列模式表示的异常检测算法
詹艳艳, 陈晓云, 徐荣聪
(福州大学数学与计算机科学学院, 福州350002)
*
摘 要:提出了一种基于时间序列的模式表示提取时间序列异常值的异常检测算法(PREOV) 。时间序列的模式表示本身就具有压缩数据、保持时间序列基本形态的功能, 并且具有一定的除噪能力。在时间序列模式表示的基础上提取异常值, 可以大大提高算法的效率和准确性, 达到事半功倍的效果。在本算法中, 还使用了一定的剪枝策略, 使得算法的时间复杂度进一步降低。该算法计算简单、实现方便、无须训练, 可以支持时间序列的动态增长。
关键词:斜率; 时间序列; 模式表示; 支持数; 异常值
中图分类号:TP 391. 41 文献标志码:A 文章编号:1001-3695(2007) 11-0096-04
Out lier detection a lgorith m based on pat t ern r epr esent at ion of t im e series
ZHAN Ya n-ya n, CHEN Xiao-yun, XU Rong-cong
(S chool of M athematics &Comp uter S cience, Fuz hou Univer sity, Fuzhou 350002, China)
Abst ract :This pa per im ported a n algorit hm which was ba sed on the pat tern repres enta tion of t im e series ext ra ct outlier v alue (PREOV) . The pat tern represent at ion of tim e series its elf ha d t he function of com pres s da ta a nd keep the bas ic s ha pe of t im e s eries, a nd it had a cert ain ext ent effect of noises rem ova l. Ba sed on P RE OV could enorm ously increas e the efficiency and ve-ra city of a lgorithm , a nd g ot tw ice t he result wit h half t he effort. Besides, us ed som e st rat egy of pruning , w hich m a de the algo-rithm ’s t im e com plexity m ore lower. And t his algorit hm can be easy calcula ted a nd carry out, t he t raining is needless and it can s upport t he dynam ic increase of tim e series. Key wo rds:slope; t im e series; pa tt ern repres enta tion; support; outlier va lue 时间序列是指按照时间先后顺序排列的各个观测记录的有序集合, 广泛存在于商业、经济、医疗等领域。随着时间的推移, 时间序列通常包含大量的数据。对时间序列进行分析, 可以揭示事物运动、变化和发展的内在规律, 对于人们正确认识事物并据此作出科学的决策具有重要的现实意义。
在对时间序列进行分析时, 经常希望能够发现这些时间序列在不同时间段的形态有何关联关系。这种关联关系一般表现为时间序列中频繁出现的变化模式和极少出现的变化模式。这种极少出现的变化模式称之为异常模式。在某些领域, 异常模式的发现对人们来说往往更有价值。例如, 医院可以从病人的心电图序列中发现异常模式从而进行诊断和治疗。
目前为止, 时间序列的异常检测已广泛应用到医疗、金融、入侵检测以及可疑活动监控等领域。
法并不适用于时间序列。
时间序列的研究工作还不是很成熟, 甚至到目前为止, 对于时间序列的异常还没有一个公认的定义。许多研究者在自己的研究过程中都提出了不同的时间序列异常定义, 如新颖[1～4]、奇异[5, 6]、变化点[7]、异常[8, 9]、不正常的[10]等。
按照异常的表现形式不同, 线性时间和空间上时间序列的异常主要可以分为点异常和模式异常两种, 它们都是用于发现一条时间序列上的异常情况的。本文主要研究的是模式异常。它是指在一条时间序列上与其他模式之间具有显著差异的模式。事实上, 点异常也可以认为是长度为1的模式异常。
本文提出了一种基于时间序列的模式表示提取时间序列异常值的异常检测算法。由于时间序列的模式表示方法本身就具有刻画时间序列的主要形态而忽略那些微小细节的特点。它可以对时间序列进行压缩, 换来更小的存储和计算代价; 可以只保留时间序列的主要形态, 去除细节干扰, 更能反映时间序列的自身特征。
近年来, 异常检测作为数据挖掘的一个分支, 正受到越来越广泛的关注。以往的很多研究都是基于无序数据集的, 而时间序列的序列点之间又恰恰是有序的。因此很多异常检测算
定义1 时间序列的模式表示。
收稿日期:2006-08-21; 修返日期:2006-10-20 基金项目:福建省自然科学基金资助项目(Z051503) ; 校科技发展基金资助项目(2004-XQ-17)
作者简介:詹艳艳(1981-) , 女, 浙江绍兴人, 硕士研究生, 主要研究方向为机器学习、数据挖掘(yanyan. 4x@163. com) ; 陈晓云(1970-) , 女, 福建晋江人, 副教授, 硕导, 主要研究方向为数据挖掘、机器学习、模式识别; 徐荣聪(1952-) , 男, 福建莆田人, 副教授, 硕导, 主要研究方向为计算数学等.
1 相关工作
2 相关定义
时间序列的模式是指时间序列的某种变化特征, 它可以是时间序列离散化后的符号, 也可以是时间序列的傅里叶变换系数等。通过提取时间序列的模式, 将时间序列变换到模式空间, 就得到了时间序列的模式表示。
时间序列的模式表示方法有很多, 主要有频域表示、奇异值表示、符号化表示、分段线性表示等几种。本文所讨论的基于时间序列模式表示的异常检测算法可以应用到所有的模式表示方法中。本文实验所采用的是分段线性表示方法中的IE O 表示(这是在笔者另外一篇论文“基于插值边缘算子的时间序列模式表示”中提出的时间序列PLR 方法) 。
定义2 时间序列的子模式。
设有时间序列X =枙x 1, x 2, …, x n 枛和X 1=枙x i 1, x i 2, …, x in 枛。其中x i 1, x i 2, …, x in ∈X, 并且有1
定义3 支持数。
设有时间序列X =枙x 1, x 2, …, x n 枛, 及其子模式X 1=枙x i 1, x i 2, …, x in 枛。如果子模式X 1在时间序列X 中出现了k 次, 则称该子模式的支持数为k(支持数k 是一个整数) 。
3 基于时间序列模式表示的异常检测算法
在本文中提出了一种基于时间序列模式表示的异常检测(PREOV) 算法。该算法在时间序列模式表示的基础上提取时间序列的异常值进行异常检测。3. 1 算法的基本思想
算法主要是基于一种逆向频繁模式挖掘思想, 即异常模式肯定是时间序列中最不频繁的模式, 也就是支持数最低的模式。换句话说, 支持数越高的模式, 其异常值就越小; 反之, 支持数越低的模式, 其异常值就越大。异常值是体现时间序列中某一个模式异常程度的值。
在算法执行过程中, 首先使用时间序列的IEO 表示方法得到时间序列的模式表示; 然后用直线段将时间序列模式表示的序列点两两连接, 并且提取每一个线段的特征值, 即斜率和线段长度。在接下去的运算中, 把每一个线段作为一个候选子模式, 分别按照线段的斜率、长度、高度计算每一个候选子模式的支持数k 1, k 2, k 3。当两个候选子模式的斜率(长度、高度) 相等时(这里, 斜率和高度都取精确到小数点后一位进行比较) , 认为这两个候选子模式是相同的, 两个候选子模式的支持数都加1。这样, 就得到了每一个候选子模式的支持数。接着, 根据支持数计算每一段子模式的异常因子以及每一个序列点的异常值。
1) 子模式的高度 设X 1=枙x i 1, x i 2, …, x in 枛是时间序列X =枙x 1, x 2, …, x n 枛的子模式, slope (i) 和length (i) 分别为该子模式的斜率和长度, 则子模式的高度定义为
high (i) =|slope(i) ×length (i) |
(1)
2) 子模式的异常因子 设X 1=枙x i 1, x i 2, …, x in 枛是时间序列X =枙x 1, x 2, …, x n 枛的子模式, k 1(i) , k 2(i) , k 3(i) 分别为该子模式的斜率、长度和高度的支持数, 则斜率、长度和高度的异常因子o 1(i) , o 2(i) , o 3(i) 定义为
o j (i) =1/k j (i) ; j =1, 2, 3
(2)
该子模式的异常因子定义为
o(i) =max(norm (o 1(i) ×o 2(i) ) +nor m (o 3(i) ) )
(3)
其中:norm (i) 是一个数据规范化公式。它可以将数据规范化为0～1。其具体定义如下:
norm(sup i ) =[sup i -min(sup i ) ]/[m ax(sup i ) -min(sup i ) ](4)
显然, 此时子模式的异常因子o(i) 的值也在0～1。在本文中, 认为组成同一个子模式的各点的异常因子是相等的。3. 2 基于时间序列模式表示的异常检测算法
算法:P RE OV
输入:时间序列X =枙x 1, x 2, …, x n 枛及其长度y n 。当压缩率为85%时的时间序列X 的模式表示IEO:X I =枙x ′1, x ′2, …, x ′n 枛
及其长度n 。输出:时间序列X =枙x 1, x 2, …, x n 枛每一点的异常值。具体步骤:
a) 根据上述算法思想以及公式计算每一段子模式的异常因子。
b) for(i =0; i
子, 并且进一步去除噪声产生的单点异常*/
{if((end[i]-begin[i]==1) &&(i >=3)
&&(i
for(l =i -3; l
if(k ==1) //说明确实是由异常引起的outlier 1[j]=outlier[i];
else if(k ==0) //说明是由噪声引起的{if(outlier[i -1]>=outlier[i +1]) outlier 1[j]=outlier[i -1]; else
outlier 1[j]=outlier[i +1]; }}else
{for(j =begin[i]; j
//最后一个序列点的异常因子等于最后一个子模式的异常因子
c) for(ii =0.8; ii >=0; ii -=0. 01)
//计算该时间序列中每一点的异常值for(j =0; j
{if(outlier 1[j]>=ii) outlier 2[j]+=ii; }
d) 输出该时间序列中每一个点的异常值。3. 3 算法的两大特点
a) 基于时间序列的模式表示提取异常值, 大大减少了计算量, 减少了噪声的干扰, 提高了算法的效率和准确性。
如图1所示, (a ) 是一条具有9382个采样点的原始时间序列; (b) 是该时间序列的一个分段线性表示, 只需保存258个线段端点, 压缩率达到97. 3%, 但是仍然很好地保留了原时间序列的主要形态, 与原始序列的拟合误差仅为1. 63。
b) 使用了一定的剪枝策略, 使得算法的时间复杂度进一步降低。
本算法中时间耗费最大的地方是在计算每一个候选子模式支持数时。在算法的实现过程中, 使用一个数组s[n -1]
[2]来实现剪枝。其中:s[i][0]代表候选子模式i 的支持数,
由于每一个候选子模式至少是其本身的支持者, s[i][0]的初始值为1; s[i][1]代表与候选子模式i 相同的其他候选子模式, 由于第一个候选子模式在数组中的存放位置是从0开始的, 把数组s[i][1]的初始值设置成-1。在算法中设置两个关卡进行剪枝, 如下所示:
//计算每一个候选子模式的支持数for(i =0; i
if(s[i][1]==-1) //关卡1{for(j =i +1; j
{if(exactconver t(slope[i], exact) ==
exactconver t(slope[j], exact) ) //斜率相等{s[i][1]=i; //候选子模式i 与其本身相同 s[j][1]=i; //候选子模式i 与候选子模式j 相同 s[i][0]+=1; //候选子模式i 的支持数加1 s[j][0]+=1; //候选子模式j 的支持数加1}}}
for(j =i +1; j
s[j][0]=s[i][0];
//与候选子模式i 相同的子模式支持度相同}if(s[i][0]>max)
max =s[i][0]; //计算所有候选子模式中的最大支持度else if (s[i][0]
min =s[i][0]; //计算所有候选子模式中的最小支持度}
1.20.811.20.60.40.80.20.610
0.412139
(a)42776415
85530.20
长度原始时间为9382
序列，(b)为257, 时间1即序213942776
4158553
处理后列的分的段时间线性序表示列长度，线段为数258
目图1时间序列及其模式表示
关卡1和2的设置都是基于同一个思想, 即如果候选子模式i 和候选子模式j 相同, 而候选子模式i 与候选子模式k 不同, 那么候选子模式j 与候选子模式k 也不可能相同。这样就可以省去很大一部分由于重复计算而造成的时间耗费。虽然表面上看, 该算法的时间复杂度为O(n 2
/2) , 但由于这两个关卡的存在, 算法的实际时间复杂度是远远低于O(n 2
/2) 的, 只有当所有候选子模式之间两两均不相同时才有可能达到O(n 2/2) ; 相反, 相同的候选子模式越多, 算法的时间复杂度就越低, 当所有候选子模式均相同时, 该算法是线性的, 其时间复杂度仅为O(n) 。
4 实验及结果分析
以下的实验过程中, 在比较线段斜率和长高度时均精确到小数点后一位。
4. 1 实验1:Keog h_Data数据集4. 1. 1 实验数据
Keogh_Data 数据集是Keog h 等人[11]用于检测异常模式所使用的仿真数据集。该时间序列由以下随机过程产生:Y 1(t) =sin(50π/N t) +n(t) ; Y 2(t) =sin(50π/N t) +n(t) +e 3。其中:t =1, 2, …, N(N =800) ; n(t) 是一个加性高斯噪声, 均值为0, 标准差为0. 1; e 3(t) 是一个异常模式, 定义为
e π/N t ) -sin(50π/N t) t ∈[400, 432]
3(t) =
｛sin(750
other wise
从上面的描述中可以知道, Y 1(t) 是一个带高斯噪声的周期为32的正弦波; Y 2(t) 则是在区间[400, 432]改变了该正弦波的周期以后得到的异常模式。该异常模式使得时间序列在区间[400, 432]的波形由一个变成了两个。4. 1. 2 实验结果及分析
1) IMM 算法[1] 该算法采用人工免疫系统的负选择(ne-getive-selection) 机制来检测时间序列的异常模式。
2) TS A-Tree 算法
[5]
该算法使用TSA-T ree 的改进型来实
现异常模式的检测, 把异常模式定义为时间序列上的突然变化, 通过计算小波系数的局部极大值来发现异常模式。
3) Tarza n 算法[11] 该算法把异常模式定义为出现频率与它的期望出现频率具有显著差异的模式。该算法使用后缀树来编码所有出现的模式, 使用马尔可夫模型来预测尚未出现的模式的期望出现概率。
以上三种算法与本文算法的实验效果对比图如图2所示。
图2四种算法在Keogh_Data数据集上的实验效果对比图
实验表明:TS A-Tree 算法没有发现异常; IM M 算法发现了错误的异常模式; Tarza n 算法和PREOV 算法都可以正确地发现异常模式。但是Ta rz an 算法是在原始时间序列上发现异常模式的, 而PRE OV 算法是在时间序列模式表示的基础上发现异常模式的。由于时间序列的模式表示具有压缩数据的特点, PRE OV 算法的效率要比Tarza n 算法高, 时间耗费也更低。4. 2 实验2:Ma_Data 数据集4. 2. 1 实验数据
Ma_Data 数据集是Ma 等人
[3]
用于检测异常模式所使用
的仿真数据集。该时间序列由以下随机过程产生:X 1(t) =
sin(40π/Nt) +n(t) , X 2(t) =sin(40π/N t) +n(t) +e 1(t) , X 3(t) =sin(40π/Nt) +n(t) +e 1(t) +e 2(t)
。其中:t =1, 2, …, N(N =
1200) ; n(t) 是一个加性高斯噪声, 均值为0, 标准差为0. 1; e 1(t) 和e 2(t) 是两个异常事件, 定义为
n (t) t ∈[600, 620]e 1(t) =
{
10
otherw ise
其中:n 1(t) 符合正态分布N(0, 0. 5) 。
e sin(40π/N t) t ∈[820, 870]2(t) =
{
0. 4×0
otherw ise
可以看出, 时间序列X 1(t) 是一条长度为1200的正常时间序列; X 2(t) 是在X 1(t) 中加入了一个异常事件e 1(t) ; X 3(t) 则是在X 1(t) 中加入了两个异常事件e 1(t) 和e 2(t) 。4. 2. 2 实验结果及分析
Ma 等人提出的S VR(基于支撑向量回归模型) 与PREOV 算法的实验效果对比图如图3所示。
实验表明:SVR 算法和PREOV 算法都可以正确地发现时间序列X 2(t) 和X 3(t) 上的异常模式。但是S VR 算法必须经过训练(在实验中, M a 等人使用前400个序列点用于训练, 后800个序列点进行异常模式的检测)
[4]
, 而PRE OV 算法不需要
第11期詹艳艳, 等:基于时间序列模式表示的异常检测算法
[4]
・ ・ 99
训练也可以正确提取出异常模式, 并且可以支持时间序列的动态增长。
X 2(t ) SVR
X 3(t ) SVR
BORISYUK R, DENHAM M, HOPPENSTE ADT F, et al. An oscilla-tor y neural network model of sparse distributed memory and nov elty detection [J ]. BioS ystems, 2000, 58(1) :265-272.
[5]S HAH ABI C, TIAN X, ZHAO W. TS A-Tr ee:a wavelet-based ap-proach to impr ove the efficiency of multi-level surprise and trend que-ries[C]//Proc of the 12th Inter national Conference on Scientific and Statistical Databa se M ana gement. Washington DC:IE EE Computer Society, 2000:55-68.
PREOV PREOV
[***********][***********]001200
(a)SVR 和PREOV 算法在(b)SVR 和PREOV 算法在时间序列X 2(t ) 上的实验效果时间序列X 3(t ) 上的实验效果
图3SVR 和PREOV 算法在
Ma_Data数据集上的实验效果对比图
[6]C HAKRABARTI S, S ARAQWAGI S, DOM B. Mining sur pr ising pat-ter ns using tempor al description length[C]//Pr oc of the 24th Interna-tional Confer ence on Ver y Larg e Data Bases. San Francisco:Morgan Kaufmann Publisher s, 1998:606-617.
5 结束语
由于时间序列的海量和复杂的数据特点, 直接在时间序列上进行数据挖掘不但在储存和计算上要花费高昂代价而且还可能会影响算法的准确性和可靠性。本文提出了一种基于时间序列模式表示的异常检测算法。该算法在时间序列模式表示方法的基础上提取时间序列的异常值, 提高了算法的效率和准确性, 达到事半功倍的效果。本算法无须训练, 可以支持时间序列的动态增长。参考文献:
[1]
AS GUPTA D, FORRES T S . Novelty detection in time series da ta using ideas from immunology[C]//Proc of the 5th Inter national Con-ferenceon Intelligent S ystems. 1996:82-87. [2]
MA J , PERKINS S . Time-series novelty detection using one-cla ss sup-port vector machines [C]//Pr oc of Interna tional J oint Conference on Neura l Networks. 2003. [3]
MA J , PERKINS S. Online novelty detection on temporal sequences [C]//Proc of Inter national Conference on Knowledge Discovery and Da ta Mining. New York:ACM Press, 2003:24-27.
[9][8][7]
YAMANIS HI K, TAKEUCHI J. A unifying fr amework for detecting outlier s and change points from non-stationary time ser ies data[C]//Proc of the 8th ACM SIGKDD Interna tional C onfer ence on Knowledg e Discovery a nd Data M ining. New Yor k:ACM Pr ess, 2002:676-681. WHITEHEAD B, HOYT W A. Function appr oximation approa ch to anomaly detection in propulsion system test data [J]. Journal of P ro-pulsio n and Po we r, 1995, 11(5) :1074-1076.
DECOSTE D. M ining multivar iate time-ser ies sensor data to discover behavior envelopes[C]//Pr oc of the 3r d Conference on Knowledg e Discovery a nd Data M ining. [S. l. ]:AAAI Press, 1997:151-154.
[10]J AGADIS H H V, KOUDAS N, MUTHUKRIS HNAN S. Mining devi-ants in a time series databa se[C]//Proc of the 25th Inter national Conference on Ver y Lar ge Data Ba ses. San Francisco:Mor gan Kauf-mann Publisher s, 1999:102-113.
[11]KEOGH E, LONARDI S, C HIU W. Finding surpr ising patterns in a
time series databa se in linea r time and space [C]//Proc of the 8th ACM S IGKDD Inter national Confer ence on Know ledge Discov ery and Data Mining. New York:AC M Press, 2002:550-556.
(上接第45页) 空间, 存储效率高。另一方面, 对于有向图的存
的平均估计执行时间为O(L ×K +MFL ×MFN ×log L) 。
储, 判断到底应用哪种形式的存储结构, 主要取决于该有向图是稀疏图还是稠密图。但在实际应用中, 由于无法预知大型数据库数据结构转换后的有向项集图到底是稀疏图还是稠密图, 无法给出统一存储结构标准。三叉链表结构不受此影响。因此, 三叉链表结构的提出可以真正规范大型有向图的存储结构标准。5. 2 时间特性
算法在时间上的总代价包括两个组成部分, 即有向项集图构建算法的时间代价和最大频繁项集挖掘算法的时间代价。有向项集图构建算法的时间代价主要取决于一次事务数据库扫描过程中的二进制编码与支持度计数, 即取决于事务数据库的事务总数L 和数据项总数K 。它的平均估计执行时间为O(L ×K) 。最大频繁项集挖掘算法的时间代价主要取决于遍历有向项集图时的执行次数和项集Tidlis t 的交操作(与运算) 。由于三叉链表存储结构中的节点可以通过连接链表存储的地址直接定位搜索, 执行次数主要取决于最大频繁项集的平均长度MFL 和最大频繁项集的个数MFN 。它的平均估计执行时间为O(M FL ×M FN) 。项集Tidlist 交操作(与运算) 的时间由事务数据库的事务总数L 决定。如果将每一个tid 的比较作为基本操作的话, 并应用最优化的位串比较算法(如对半方法) , 它的平均估计执行时间是O (log L ) 。因此, 整个算法
[5][4][2]
6 结束语
发现最大频繁项集是多种数据挖掘应用中的关键问题。本文提出的存储结构及挖掘算法可以较好地满足大型数据库转换数据结构后对有向项集图的高效存储要求, 以及关联规则中挖掘最大频繁项集的高效时间要求, 有效地解决了关联规则挖掘中所遇到的技术难点, 具有一定的理论价值和现实意义。参考文献:
[1]
HEN M S, HAN J ia-wei, YU P S. Data mining:an ov erview fr om database per spective [J]. IE EE Transactions o n Knowle dge and Da ta Engineering, 1996, 8(6) :866-883.
许卓群, 杨冬青, 唐世渭, 等. 数据结构与算法[M]. 北京:高等教育出版社, 2005:254-270. [3]
LEI Wen, LI Min-qiang. A new association rules mining algorithms based on directed itemsets gr aph[C]//Pr oc of the 9th Int ’l Conf RS -FDGrc. 2003:660-664.
宋志平, 李应红, 屈裕安. 大型有向图的三叉链表式存储结构[J ]. 计算机工程与应用, 2002, 38(21) :39-41.
黄建设. 一种改进的关联规则算法探讨[J]. 计算机仿真, 2005, 22(12) :72-75.