（计算机软件与理论专业论文）在线的时间序列异常检测算法研究.pdf

在线的时间序列异常检测算法研究 专业：计算机软件与理论 硕士生：汪斐 指导教师：印鉴教授 摘要 数据挖掘通过从海量的数据中发现隐藏的、潜在有用的信息和知识，为人们 提供决策支持，在近年来取得了蓬勃的发展。由于越来越多的数据与时间有着密 切的联系，时间序列数据挖掘作为数据挖掘的一个分支，正受到越来越多的关注。 时间序列的异常检测是指从时间序列中发现少量、不频繁出现的模式。而在 线的时间序列异常检测是指算法能根据新数据的变化，对不断产生的数据进行增 量式的异常检测，有很实用的应用价值。 本文提出了一种新的针对时间序列的在线异常检测算法。本文首先回顾了现 有的时间序列异常检测方法，然而这些方法绝大部分是对时间序列进行离线分 析，即在检测之前要求能完整地读取整个时间序列，有很大的局限性。针对这一 问题，本文提出了对时间序列进行在线异常检测的算法框架，并把这一问题分为 两个子步骤：首先找出每一时刻的局部异常，接着从局部异常中选择用户可能感 兴趣的异常。对于第一个步骤，本文通过分析每一时刻的局部异常间的关系，提 出了t o l o d ( t i m es e r i e so n l i n eo u t l i e rd e t e c t i o n ) 算法。t o l o d 算法在某些 情况下仍会出现计算量较大的情况，为此，本文提出了它的近似算法a t o l o d ( a p p r o x i m a t et i m e s e r i e so n l i n eo u t l i e rd e t e c t i o n ) 算法，进一步的加快了检测 的速度。接着，本文给出了第二个步骤中判别函数的具体形式。在合成和真实数 据集上的实验表明，本文所提出的在线异常检测方法在很多领域有很好的应用效 果。 关键词：数据挖掘，时间序列，异常检测，在线算法 r e s e a r c ho no n l i n eo u t l i e rd e t e c t i o ni nt i m es e r i e s m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r i e s n a m e ： w a n gf e i s u p e r v i s o r ：p r o f e s s o ry i nj i a n a b s t r a c t d a t am i n i n gi st h ep r o c e s so ff i n d i n gi m p l i c i ta n d p o t e n t i a l l yu s e f u li n f o r m a t i o n o rk n o w l e d g ei nl a r g ed a t a b yh e l p i n gp e o p l em a k ed e c i s i o n ，d a t am i n i n gh a sb e e n d e v e l o p i n gr a p i d l yi nr e c e n ty e a r s a sm o r ea n dm o r et i m er e l a t e dd a t ab e c o m e s p o p u l a r , t h e r eh a sb e e nag r o w i n gi n t e r e s ti nm i n i n gt i m es e r i e sd a t a ，w h i c hi sa p o p u l a rb r a n c ho fd a t am i n i n g o u t l i e rd e t e c t i o ni nt i m es e r i e si st of i n du n u s u a l 1 e s sf r e q u e n tp a t t e r nt h a ti s l e a s ts i m i l a rt oo t h e rs e q u e n c e si nt i m es e r i e s o n l i n eo u t l i e rd e t e c t i o nm e a n st h e a l g o r i t h mi sa d a p t e df o rn e wc h a n g i n gd a t a ，m a k i n gi n c r e m e n t a ld e t e c t i o no nt h en e w d a t a ，w h i c hh a sm a n yi m m e d i a t ea p p l i c a t i o n s t h i sp a p e rp r e s e n t san e wm e t h o do fo n l i n eo u t l i e rd e t e c t i o ni nt i m es e r i e s w e f i r s tr e v i e w e dt h ee x i s t i n go u t l i e rd e t e c t i o nm e t h o d si nt i m es e r i e s ；t h e s em e t h o d sc a n o n l yd e t e c to u t l i e r so f f - l i n e ，w h i c hm e a n st h e yr e q u i r ef u l la c c e s st ot h ew h o l et i m e s e r i e sb e f o r ea n a l y s i s ，h o w e v e r , m a n ya p p l i c a t i o n sc a n n o tp r o v i d es u c hf a c i l i t i e s t o s o l v et h i sp r o b l e m ，t h i sp a p e rp r o p o s e san e wf r a m e w o r kf o ro n l i n eo u t l i e rd e t e c t i o n i nt i m es e r i e s ，w h i c hd i v i d et h i sp r o b l e mi n t ot w os t e p s ：f i r s tf i n dl o c a lo u t l i e ri n e v e r ym o m e n t ，a n dt h e ns e l e c tp a t t e r n st h a tm a yi n t e r e s tu s e rf r o mt h e s el o c a lo u t l i e r s c o n c e r n i n gt h ef i r s ts t e p ，w eh a v ea n a l y z e dt h er e l a t i o n s h i po fl o c a lo u t l i e rb e t w e e n e a c hm o m e n t ，a n dp r o p o s e dt h et o l o d ( r i m es e r i e so n l i no u t l i e rd e t e c t i o n ) a l g o r i t h m u n d e rc e r t a i nc i r c u m s t a n c e s ，t o l o da l g o r i t h ms t i l lr e q u i r e s l a r g e c a l c u l a t i o n ，s o ，w ei n t r o d u c ei t sa p p r o x i m a t ea l g o r i t h ma t o l o d ( a p p r o x i m a t et i m e s e r i e so n - l i n eo u t l i e rd e t e c t i o n ) ，f u r t h e rr e d u c et h et i m es p e n ti nd e t e c t i o n n e x t ， w eg i v et h es p e c i f i cf o r mo fd i s c r i m n a n tf u n c t i o ni nt h es e c o n ds t e p e x p e r i m e n t so n b o t hs y n t h e t i ca n dr e a ld a t a s e t sd e m o n s t r a t et h eu t i l i t yo fo u rp r o p o s e da t o l o d a l g o r i t h mi nah o s to fd o m a i n s k e y w o r d s ：d a t am i n i n g ，t i m es e r i e s ，o u t l i e rd e t e c t i o n ，o n l i n ea l g o r i t h m 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：、五l 生 日期a 携年乡月寥日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：讧虫 日期：溯年s 月8 日 导师签名： 日期：舻厂月g 日 在线的时问序列异常榆测算法研究 第1 章引言 数据挖掘是- - f - 新兴的数据处理技术，它通过从海量的数据中发现潜在的、 隐藏的信息和知识，为人们提供决策支持。在本章中，将介绍数据挖掘的产生与 发展，并简要说明数据挖掘的一般步骤。接着介绍时间序列数据挖掘的基本概念 和应用价值，以及当前时间序列数据挖掘中的一些领域及研究成果。最后，将介 绍本文的研究成果、研究方法以及论文的结构。 1 1 数据挖掘的产生与发展 数据挖掘是信息技术自然演化的结果。早期，人们主要是利用数据库系统收 集、管理各种数据，以提高数据管理的效率。那时，数据库系统主要是应用于事 务处理。随着计算机硬件处理能力的不断增强以及信息化技术的不断应用，人们 已经积累了大量的海量数据。然而可惜的是，由于缺乏相关的分析工具，人们很 难对这些海量数据进行处理、加工，以理解隐藏在数据中的信息并为决策提供参 考。人们迫切的需要将这些数据转换成有用的信息和知识，显然传统的数据库检 索和查询技术很难满足这一要求。伴随着数据仓库出现的联机分析处理( o l a p ) 技术具有汇总、合并和聚集功能，能帮助人们从不同的角度观察信息，在一定程 度上解决了这一问题。但是，联机分析处理技术仅仅是简单的对数据的汇总、统 计，并不能进行更深层次的分析，获取隐藏的信息。正是在这一背景下，数据挖 掘技术应运而生，并逐渐在各行各业的决策支持中扮演着越来越重要的角色。 数据挖掘( d a t am i n i n g ，d m ) 又称为数据库中的知识发现( k n o w l e d g e d i s c o v e r yf r o md a t a b a s e ，k d d ) ，是指从存放在数据库、数据仓库或其他信息库 中的大量数据中挖掘有趣知识的过程【l 】。知识发现是将原始数据转换成有用的知 识的一个复杂的过程，它一般包含以下几个步骤： ( 1 ) 数据清理( d a t ac l e a n i n g ) 消除噪声或不一致数据。 ( 2 ) 数据集成( d a t ai n t e g r a t i o n ) 多种数据源可以组合在一起。 ( 3 ) 数据选择( d a t as e l e c t i o n ) 从数据库中检索与分析任务相关的数据。 ( 4 ) 数据变换( d a t at r a n s f o r m a t i o n ) 数据变换或统一成适合挖掘的形式，如通 n ：线的时问序列异常俭测算法研究 过汇总或聚集操作。 ( 5 ) 数据挖掘( d a t a m i n i n g ) 基本步骤，使用智能方法提取数据模式。 ( 6 ) 模式评估( p a t t e me v a l u a t i o n ) 根据某种兴趣度度量，识别表示知识的真 正有趣的模式。 ( 7 ) 知识表示( k n o w l e d g ep r e s e n t a t i o n ) 使用可视化和知识表示技术，向用户 提供挖掘的知识。 其中，步骤1 到步骤4 可以认为是数据挖掘前的数据准备阶段，它为数据挖 掘提供相关的数据，并以统一的形式表示出来。在上面的步骤中，使用的是数据 挖掘的狭义定义，即只是从数据库中提取有趣的模式，它是知识发现过程的一个 步骤。然而目前在产业界、媒体和数据库研究界，“数据挖掘”比较长的术语“数 据库中知识发现”更流行【1 1 ，所以，数据挖掘一般指的是知识发现这一全过程。 整个知识挖掘的全过程如图1 1 所示。 i ： i ： ： 数据库i 一一望塑一l 一 图1 1 知识发现全过程 2 模式 o o 知识 一一一一一一一 r-t 一一一一一一一一一一一一 广iif 一一一一一一一一一一一一 广 一 il 一一一一一 一一一一一 ，y 一 一一 在线的时间序列异常检测算法研究 数据挖掘可以处理的数据类型很多，一般来说，其主要来源从结构性数据到 半结构性及非结构性数据，包括关系数据库、面向对象数据库、空间数据库、推 理数据库、多媒体数据库、时态数据库、文本数据库、图像数据库及音频和视频 数据源等 2 1 。数据挖掘任务一般可以分为两类：描述和预测。描述性挖掘任务刻 画数据库中数据的一般特性；预测性挖掘任务在当前数据上进行推断，以进行预 测。具体来分，数据挖掘的任务可分为：发现概念类描述、关联分析、分类和 预测、聚类分析、孤立点分析和演变分析等。 数据挖掘系统往往会产生数以千计的潜在模式，然而并不是所有的模式都是 用户感兴趣的。一个模式是有趣的，那么它必须( 1 ) 易于被人理解；( 2 ) 在某 种程度上，对于新的或测试数据是有效的；( 3 ) 是潜在有用的；( 4 ) 是新颖的【1 1 。 只有符合上述这些条件，所挖掘出来的模式才能被称为知识。 数据挖掘是一门涉及很广的交叉学科，应用了数据库系统、统计学、机器学 习、可视化和信息科学等相关学科的知识。从数据挖掘界于1 9 9 5 年召开了它的 第一届知识发现与数据挖掘国际学术会议开始，数据挖掘技术得到了越来越多的 应用，主要应用集中在大型银行、保险公司、电信公司和零售业。尽管数据挖掘 技术取得了很多的应用，但它目前仍有很多问题及挑战( 如性能问题、隐私问题) ， 这些都有待研究者的进一步努力。 1 2 时间序列数据挖掘 简单地说，与时间相关的数据就是时序数据。将数据按照时间的先后顺序所 排成的序列就是时间序列，时间序列反映的是某一观测值随时间的变化情况。很 多数据都是时间序列，比如，股票交易市场上每只股票的价格走势；网页上所投 放广告的单位时间内的点击量；商品零售行业中商品每日的销售数据；医院中病 人的心电图数据等。通过对这些时间序列进行数据挖掘，人们希望可以从中找出 有用的知识，比如，根据过去股票数据的走势来预测明天的股票价格；当广告点 击出现异常的时候能及时地通知用户，以让广告商查找相关的原因；根据过去的 商品销售数据预测将来的销售量，或从历史销售数据中发现潜在的问题；当病人 心跳异常的时候及时通知医生进行相应的处理。随着各种时间序列数据的不断增 长，如何有效的利用这些数据，从中挖掘出潜在的有用信息，帮助人们更好的认 在线的时间序列异常检测算法研究 识数据中所隐藏的知识，进行科学决策，是一个永恒的主题，它正不断地吸引着 越来越多的人来研究这一领域。 现有的针对时间序列的数据挖掘研究主要集中于索引、分类、聚类、分割和 异常检测等几个方面。而以上这些方面的研究，都牵涉到两个基础的问题，分别 是：时问序列相似性度量和时间序列的表示。下面将结合本文的具体内容，先简 要介绍这两方面，接着重点介绍时间序列异常检测方面的研究成果，最后，再简 要介绍时间序列数据挖掘的其它几个领域。 1 2 1 时间序列相似性度量 几乎所有的与时间序列有关的算法，如：索引、分类、聚类、分割等，都需 要评价两个时间序列的相似程度。因此，用来表示两个时间序列相似性程度的时 间序列相似性度量可以算是整个时间序列数据挖掘的基础性工作。 最常见的相似性度量是欧几里德距离( e u c l i d e a nd i g a n c e ) ，它因为简单易 算且适合大规模运算，而被应用在很多领域。但是它不允许数据在时间轴上的移 动，对于数据在时间轴上的微小位移有可能导致很大的差异。动态时间弯曲距离 ( d y n a m i ct i m ew a r p i n g ) 被认为在局部时间序列对齐上较欧几里德距离有更好 的灵活性，它最早被用于语音识别等方面，之后b e r n d t 和c l i f f o r d 将这一技术引 入了数据库领域【3 】。最近有研究表明，允许全局缩放时间序列的均匀缩放 ( u n i f o r ms c a l i n g ) 在处理某些领域的问题上很重要，f u 等结合了这两种技术， 提出了s w m ( s c a l e da n dw a r p e dm a t c h i n g ) 度量 4 】，它在处理生物统计学、运 动捕捉及手写识别等领域能取得更有意义的结果。 除了以上所介绍的基于形状的相似性度量之外，在这里有必要提及k e o g h 等人提出的基于数据压缩的相似性度量【5 1 。它的思想是若把相似的数据进行连接 并压缩，则它们的压缩比应比不相似的数据大。基于这一思想，k e o g h 等人定义 了c d m ( c o m p r e s s i o n 。b a s e dd i s s i m i l a r i t ym e a s u r e ) ，并通过大量实验说明它在 时间序列分类、聚类和异常检测上的准确性高，鲁棒性好。除此之外，还有基于 特征的相似度，以及基于模型的相似度等方法，但因应用范围不广，这里就不做 介绍了。 4 在线的时间序列异常检测算法研究 1 2 2 时间序列表示 时间序列可以被认为是高维度的数据，每一个子时间序列都可以认为是高维 空间中的一个点。因为高维数据处理起来比较麻烦，很多算法在处理前都会将时 间序列降维表示。这样不仅可以降低维度，还可以减弱噪声数据对时间序列的影 响，某些表示方法还可以反映出一些时间序列的本质特征，为进一步的处理、分 析奠定基础。 在早期的研究中，为了对时间序列进行索引，f a l o u t s o s 等人对时间序列进行 离散傅立叶( d i s c r e t ef o u r i e rt r a n s f o r m ，d f t ) 变化，并选取前面几个高能量系 数来表示这个时间序列【6 】。但这一方法需要在创建降维表示之前对整个时间序列 进行访问，因而不能应用于数据流的表示。k e o g h 7 1 和y i 8 1 等人分别提出了p a a ( p i e c e w i s ec o n s t a n ta p p r o x i m a t i o n ) 表示方法，此方法将时间序列进行等距离 分割，并在每个分割区域内求平均值，这种方法可以应用于数据流，取得了一定 的效果。l i n 等人在p a a 的基础上，进一步的将数值转化成离散的字符表示，并 提出了s a x ( s y m b o l i ca g g r e g a t ea p p r o x i m a t i o n ) 表示法【9 】，在时间序列的处理 上借用传统的离散处理技术，取得了不错的效果。 1 2 3 时间序列异常检测 时间序列的异常检测是指在时间序列中发现少量的与其它子序列不相似的 部分，而这些不相似的部分，往往就是实际应用中的异常或者是用户感兴趣的部 分。 d a s g u p t a 等人提出用免疫系统中的逆向选择思想来进行时间序列的异常检 测【1 0 1 。其主要思想是，先用给定的一段正常的时问序列进行训练，从中产生出 一组与正常时间序列不能匹配的检测细胞。接着再用这组检测细胞对新的时间序 列进行匹配，如果有检测细胞能与新的时间序列进行匹配，则说明有异常发生。 s h a h a b i 等人提出了基于小波变换的对时间序列进行异常检测的方法【1 1 1 ，其所提 出的t s a t r e e 支持在多个层次上查询异常。m a 等人提出了对时间序列进行在线 异常检测的框架1 2 】，这篇文章用支持向量回归的方法对将来的时间序列进行预 测，当预测值与实际值不符合的次数达到阈值的情况下，就判断异常产生。l i 在线的时间序列异常睑测算法研究 等人将时间序列异常检测的方法与数据仓库的技术结合，提出了在多维时间序列 中发现异常的方法【1 3 】。在国内，则有詹艳艳等人提出先将时间序列转换为模式 表示，并在此基础上提取异常值【1 4 】，这一方法提高了算法的效率和准确性。 k e o g h 等人则提出了针对整串时间序列查找与其它子序列最不相似子序列 的思想，并把这种异常子序列称为d i s c o r d 【l 引。其所提出的查找d i s c o r d 的h o t s a x 算法，相比穷举算法在速度上有极大的提高。b u 等人在k e o g h 等人的基础 上，提出查找时间序列中最不相似的前几个d i s c o r d 的w a t 算法【l6 | 。这两种方 法可以有效地应用在生物信息学、航天遥感及医学等各领域。因本文的研究工作 有部分借鉴了k e o g h 等提出的算法，所以本文会在之后的章节详细介绍h o t s a x 算法。 1 2 4 时间序列数据挖掘的其它研究工作 对时间序列的索引是指给定查询时问序列q ，以及相似性度量d ( q ，c ) ，在 数据库中查找所有与时间序列q 的距离小于阈值的序列。f a l o u t s o s 等人提出了 对子时间序列进行索引的方法【6 】，其主要步骤为对时间序列数据进行降维，并利 用多维索引结构，如r 水t r e e 1 7 1 或x t r e e 1 8 1 等对降维后的数据进行索引。因为索 引的效率主要依赖于时间序列降维的好坏，因此之后有大量的研究工作是关于如 何对时间序列降维以取得更好的索引效果的。早期的研究中，f a l o u t s o s 等人是使 用离散傅立叶变化的方法进行降维处理的，此外，还有使用其它方法进行降维处 理的，如奇异值分解【j 9 】、离散小波变换2 0 , 2 1 ，以及p a a 7 , 8 】等方法。此外，m o o n 等人利用了在构造索引时的对称性，改进了索引的效率【2 2 1 。k e o g h 等则提出了在 动态时间弯曲距离下的索引方法 2 3 1 。 分类和聚类已经有数十年的研究历史了，然而由于时间序列的高维度、高特 征相关性以及大量噪声等特点，使得很多经典的分类、聚类算法难以在时间序列 数据上发挥作用。现有的很多做法是使用新的相似性度量，即把这些相似性度量 的计算函数作为现有的分类或聚类算法的子函数使用【2 4 2 6 1 。其它的一些研究工作 有，g e u r t s 提出使用决策树组合局部模式的方法来进行分类【2 刀，这种方法不仅提 高了准确率，并且保留了决策树方法可以产生较好的可解释分类规则的优点。 p o v i n e l l i 等人提出基于重构相空间的方法进行分类 2 8 】，避免了对序列基本形状的 6 在线的时问序列异常柃测算法研究 假设。b a g n a l l 等人先把时间序列转化为限幅数据( c l i p p e dd a t a ) ，并在其上进行 聚类分析【2 9 1 ，提高了时空效率，且几乎不影响正确率。l i n 等人利用小波的多分 辨率特性，提出任意时间的聚类算法【3 0 1 ，通过多次、逐步提高分辨率的聚类， 避免聚类算法陷入局部最小。 时间序列分割是将长序列分割成不重叠的、有序的子序列集合。时间序列的 分割方法大致可以归类为以下三种类型：滑动窗口、自项向下、自底向上【3 l 】。 c h u n g 等人口2 】使用基于模式的遗传算法对时间序列进行分割，取得了不错的效 果。在对时间序列进行分割的基础上，可以做进一步的数据挖掘工作，如文本和 时间序列的协同挖掘【3 3 】、变化点检测【3 4 1 ，以及相似性度量计算3 5 1 等。 近几年来，时间序列的数据挖掘取得了长足的发展，但也存在着很多不足。 k e o g h 等人从3 6 0 多篇关于时间序列数据挖掘的论文中选取了5 7 篇引用较多的 论文，并将这些方法用于5 0 个真实的数据集【3 6 j 。其得出的结论令人惊讶，在用 多种不同类型的实际数据集进行测试或改变少许的实现细节，则这些算法的性能 有明显地下降。这一结论表明，这些算法仅仅是对某种时间序列类型及某种实现 方式是有效的，而缺乏解决现实数据问题的普遍有效性。k e o g h 等人的工作展示 了时间序列数据挖掘的复杂性，但这也同时表明这一领域还有广阔的研究空间。 1 3 本文的主要工作 本文对时间序列的异常检测问题进行研究，并提出了一种新的时间序列在线 异常检测方法。所谓在线，是指在不暂停算法的情况下，系统能根据新数据的变 化，对不断产生的新数据进行增量式的异常检测。 在线时间序列异常检测有很多具体的应用。比如，在安全十分重要的应用中， 当不正常的事件发生时，系统能在性能明显降低之前把它迅速地检测出来。这可 以通过将很多传感器与系统相连，系统对传感器产生的时间序列进行分析，并报 告任何不正常的事件【1 2 】。又比如，可以把网络流量作为时间序列来考虑，当发 现网络流量异常时，及时的通知用户，或者是对病人心电图的实时检测，当病人 心跳异常的时候及时地通知医生。另外一个应用是帮助不同领域的科学家，让他 们可以仅仅对被检测出异常的时间序列进行分析，而不需要一直不断的监视着时 间序列来判断是否有异常发生。 7 在线的时间序列异常检测算法研究 目前的一些时间序列的异常检测方法绝大部分是针对整串时间序列的离线 分析5 ，1 0 ，1 1 ，1 5 ，16 1 ，它们在分析之前需要能够完全访问整个时间序列，有很大的局 限性。而在实际的应用中，常常需要对不断产生的时序数据进行实时的分析、检 测。本文借鉴了h o ts a x 离线算法进行异常检测的思想，提出了针对不断产生 的时间序列进行在线异常检测的方法。 本文以下章节的内容安排如下： 第2 章介绍了时间序列异常检测的定义，以及现有的针对时间序列进行离线 异常分析的方法。 第3 章提出了新的在线时间序列异常检测的方法。其中首先分析了现有算法 的不足，接着提出了对时间序列进行在线异常检测的算法框架，其把这一问题分 为两个步骤：首先在每一时刻找出当时的局部异常，接着从局部异常中选择用户 可能感兴趣的异常。对于第一个步骤，本文提出了t o l o d 算法，但是它在某些 情况下仍会出现计算量较大的情况，因此接着提出了它的近似算法a t o l o d 。 之后，介绍了第二个步骤中判别函数的具体形式。一些较难的数据结构及算法也 在这一章中介绍。 第4 章对所提出的算法进行了大量的实验，在合成和真实数据集上的实验展 示了这一在线异常检测方法的有效性。之后，本文进行了相关的分析。 第5 章对本文所做的工作进行总结，并指出之后的研究方向。 在线的时问序列异常检测算法研究 第2 章相关工作 时间序列异常检测方面的研究还不是很成熟，到目前为止，对于时间序列的 异常还没有一个公认的定义。许多研究者在各自的研究过程中都提出了不同的关 于时间序列异常的定义，如新颖、异常、奇异、变化点、不f 常的等。因此在这 一章，会先介绍与本文工作相关的针对整串时间序列进行离线异常分析的定义， 并接着介绍s a x 表示法和k e o g h 等提出的h o ts a x 方法。 2 1 相关定义 为了文章的完整性，我们首先从定义本文所适用的数据类型开始： 定义2 - 1 时间序列：若t = t t ，锄是一个包含有m 个实数变量的有序序列，则 称丁为时间序列。 实际上，本文的研究对象并不是时间序列的全局属性，而是时间序列的其中 一部分，这一般被称为子序列。 定义2 2 子序列：给定一个长度为m 的时间序列兀对于任意的刀5 m ，若序列c 是从序列丁的p 位置开始的连续采样，也就是c - 名，锄一1 ( 1 印勤一n + 1 ) ，则 称c 为丁的子序列。 因为任何的子序列都有可能是异常，因此无论什么算法，最终都需要获取所 有的子序列。这一步骤可通过使用滑动窗口来达到。 定义2 3 滑动窗口：给定长度为m 的时间序列t ，以及用户指定的子序列长度，z ， 可以通过在序列丁上滑动长度为n 的窗口，每滑动一步，就取出当时窗口中的子 序列c p 的方法来获取所有的子序列。 本文是通过相似性度量来评价各个子序列间的相似性的，并尝试找出与其它 子序列具有最远距离的子序列。因此，现在有必要来定义相似性度量： 定义2 - 4 相似性度量：d i s t 是一个函数，它接收序列c 和m 作为参数，并返回 一个非负值尺，返回的r 可以被认为是m 到c 的相似性距离。对于接下来的工 9 在线的时间序列异常俭测算法研究 作，需要函数d i s t 是对称的，也就是说d i s t ( c , m ) = d i s t ( m , c ) 。 相似性度量函数有时也被称为距离函数。在计算子序列与其它子序列间的距 离时，待考察的子序列周围的子序列需要被排除。因为在通常情况下，任何子序 列的最近匹配总是这个子序列之前或之后一两个点的子序列。如果允许这种情况 发生的话，那么利用距离度量来查找d i s c o r d 的结果会变得没有任何意义，因此， 要限制这种情况的发生。下面给出的是非自身匹配的形式定义： 定义2 5 非自身匹配：给定时间序列l 其中包含长度为 的起始位置为p 的子 序列c 以及起始位置为q 的匹配序列m ，如果忉- q l _ n ，则称m 为c 的非自身匹 配，它彳门间的距离为d i s t ( c , 加。 在有了以上这些定义之后，就可以定义时间序列的d i s c o r d 了： 定义2 - 6 时间序列d i s c o r d ：给定时间序列丁，如果长度为，l 的子序列d 到它的 最近的非自身匹配的距离最大，则称d 为丁的d i s c o r d 。也就是说，对于丁的任 意子序列c ，d 的所有非自身匹配m o ，以及c 的所有非自身匹配m c ，都有 m i n ( d i s t ( d ，m o ) ) m i n ( d i s t ( c , 蚴) 。 在这里，为了论文的一般性，本文故意省略了相似性距离函数的具体形式。 在接下来的工作中，将使用欧几里德距离作为距离函数来查找时问序列的 d i s c o r d 。注意，尽管在剩下的工作中使用的是欧几里德距离，但是这一方法对 于其它的相似性距离度量同样适用。下面是欧几里德距离的定义： 定义2 7 欧几里德距离：给定两个长度为n 的时间序列q 和c ，那么它们之间 的欧几里德距离定义为： 2 2s a x 表示法 d i s t ( q ，c ) = 在介绍具体的离线查找d i s c o r d 算法之前，需要先简单的介绍时间序列的 s a x ( s y m b o l i ca g g r e g a t ea p p r o x i m a t i o n ) 表示法【9 1 。因为时间序列的高维度特 性，为了处理的方便，很多算法都会将时间序列来降维表示，以加快处理的速度， 1 0 在线的时间序列异常检测算法研究 下一节介绍的算法也同样如此。 长度为n 的时间序列c 在w 维空间中可以用向量c = c l ，c 。来表示。其中 第i 个元素可以通过下面的公式来计算： 也就是说，为了将n 维的时间序列变换到w 维，可以通过将这个时间序列 分成w 等份，并计算每一等份中数据的平均值，所有等份的平均值所组成的w 维向量就是这个时间序列的降维表示。这种简单的表示方法一般被称为 p a a ( p i e c e w i s ea g g r e g a t ea p p r o x i m a t i o n ) 表示法。 在将时间序列转换为p a a 表示之后，可以进一步的将向量转换为离散表示。 我们希望每一个符号所表示的时间序列能具有相同的概率。在对大量数据集进行 测试之后发现，基本上所有的标准化的时间序列都遵循高斯分布，因此可以按照 高斯分布将所有的数值转化为离散表示。下面定义分割点的概念，这些分割点所 划分的区域在高斯曲线下具有相同的面积： 定义2 8 分割点：曰邛l ，尾i 是一数列，若它使得从p f 到夕件i 在n ( o ，1 ) 高斯曲 线下的面积都是1 屉( 风和屁分别定义为0 0 和o o ) ，则b 是分割点。 在具体的实现中，分割点可以通过查表来得到，表2 1 是一个当a 为3 到6 的分割表的具体例子。 表2 - 1 查找表示例，其中的分割点可以将高斯分布 分成任意的等概率区间( 图示为口= 3 到6 ) 心 34 56 p i 一0 4 30 7 30 6 7 4 4 90 8 4 1 6 20 9 6 7 4 2 p 2 0 4 3 0 7 3o 0 2 5 3 3 50 4 30 7 3 d 3 0 6 7 4 4 90 2 5 3 3 5o d 4 0 8 4 1 6 20 4 3 0 7 3 p 5 0 9 6 7 4 2 在有了这份查找表之后，我们可以将时间序列的p a a 表示转换为离散表示 ，l c 吣 w 抄 产 兰行 = 在线的时间序列异常检测算法研究 了。首先可以取得p a a 表示向量中的一个元素，并将它与查找表比较。若它小 于最小的分割点的话，则它被映射为符号一a ；若它在屈1 和屈之间，则它被映射 到第i 个符号。这样就可以将任意时间序列转换为符号表示了。 定义2 - 9 词映射：词是由一系列的字母组成。长度为n 的子序列c 可以通过下 面的方式被映射为词e = 占，6 2 ，6 。令a j 表示第个字母，则从p a a 表示的元 素虿可通过下面的方式映射到仑： 乏i = a j i f f p h sc is p j 可以看出，s a x 表示需要两个参数，分别是词的长度以及符号的个数。其 中，词的长度设置低维空间的维数，而符号个数则指定用多少个符号来表示低维 空间中的时间序列。图2 1 是将时间序列转为s a x 表示的一个具体示范。其中 时间序列的长度为2 5 0 ，词的长度设置为1 0 ，符号的个数为3 。可以看出，符号 a ，b 和c 出现的次数都大约具有相等的概率。 图2 - 1s a x 表示法的具体例子 2 3h o ts a x 算法介绍 在本节中，将介绍对整串时间序列离线查找d i s c o r d 的h o ts a x 算法。针 对整串时间序列进行查找d i s c o r d 的穷举算法相对简单，只需要扫描每一个子序 列，并且比较它们与它的最近非自身匹配的距离，拥有最大值的那个子序列就是 整串时间序列的d i s c o r d 。这可以通过一个二重循环来实现，在外层循环中遍历 所有的子序列，而在内层循环中，则查找这个子序列的最近非自身匹配。算法 1 2 在线的时间序列异常检测算法研究 2 1 是这一过程的伪代码： 算法2 1 查找d i s c o r d 的基本算法 输入：t ：整个时间序列，n ：d i s c o r d 的长度 输出：d i s c o r d 的位置，以及它到它的最近非自身匹配的距离 1 f u n c t i o n 1 0 c ，d i s t 】- s e a r c h ( t , ，z ) 2 d i s c o r d d i s t a n c e = o ； 3 d i s c o r d l o c a t i o n = n a n ； 4f o re a c h pi nt 开始外层循环 5 n e a r e s t _ n e i g h b o r d i s t = i n f ； 6f o re a c hqi nt 开始内层循环 7 i fl p ql = n 非自身匹配判断 8 d i s t = d i s t ( t p ，钿1 ，t q ，钿1 ) ； 9i fd i s t d i s c o r d d i s t a n c e 1 0 b r e a k ；停止内层循环 1 1 e n d 12i fd i s t d i s c o r d _ _ d i s t a n c e ； 18 d i s c o r d d i s t a n c e = n e a r e s t _ n e i g h b o r d i s t 19 d i s c o r d _ l o c a t i o n = p ； 2 0e n d 2 1e n d 结束外层循环 2 2 r e t u r n d i s c o r d _ l o c a t i o n ，d i s c o r d _ d i s t a n c e 】 对上述算法进行分析，这个算法的时间复杂度为o ( m 2 ) ( m 为时间序列t 的 长度) 。若需要分析的时间序列的长度很长时，这一算法的效率很低。 实际上，可以对这一算法进行优化。在外层循环中，当算法考察当前的子序 在线的时间序列异常榆测算法研究 列是否为时间序列的d i s c o r d 时，实际上并不需要计算它与它的m n 2 ( 川为时 间序列的长度，n 为d i s c o r d 的长度) 个非自身匹配的距离，以得出它到它的最 近非自身匹配的距离，并接着用这个距离与当前找到的最大距离进行比较，以判 断其是否为d i s c o r d 。实际上，在计算待考察子序列到它的最近非自身匹配的距 离的时候，并不需要找到它的最近非自身匹配，只要发现候选子序列到某一子序 列的距离比当前找到的最大距离小，就可以得出这个子序列不能成为d i s c o r d ， 从而避免之后的计算。在上述算法中的9 1 i 行就是进行这- - n 断。 因此，我们需要尽可能多的让第9 行的逻辑判断为真，以省去不必要的计算。 这可以通过以下两个方面来进行： ( 1 ) 外层循环优化：在不等式的右边，让d i s c o r dd i s t a n c e 尽可能的大。我们 注意到，在外层循环中，d i s c o r dd i s t a n c e 被用来保存当前找到的与它的最 近非自身匹配的最大距离，若发现当前考察的子序列具有更大的距离时， 则替换d i s c o r dd i s t a n c e 与d i s c o r dl o c a t i o n 。因此，如果在外层循环中尽 可能早的先考虑最有可能成为d i s c o r d 的子序列，也就是让 d i s c o r dd i s t a n c e 在循环过程中，尽可能早的拥有一个较大的值，则在之后 的循环中，可以对很多子序列的计算剪枝，避免不必要的计算。 ( 2 )内层循环优化：在第9 行不等式的左边，让由距离函数计算出来的结果尽 可能的小，也就是让d i s t ( t p ，锄1 ，岛，t q + ) 尽早的具有一个较小的值。 当上述不等式成立时，也就表明起始位置为p 的子序列到它的某一非自身 匹配的距离已经小于当前找到的最好结果。这样可以不需要继续对起始位 置为p 的子序列进行考察，因为它已经不具有成为d i s c o r d 的条件。因此 算法需要在内层循环中，尽早的考虑与起始位置为p 的子序列相似的子序 列。 下面会介绍如何利用s a x 表示法，设计相应的算法和数据结构，以满足上 文的优化要求。 设用户指定的d i s c o r d 的长度为n ，在查找d i s c o r d 之前，令大小为n 的滑动 窗e l 在时间序列上滑动，从中抽取所有的子序列，并将每个子序列都转换成s a x 表示，同时将转化所得到的词保存在t r i e 树中，并且记录这个词所出现的次数。 这样在对整个时间序列扫描一次之后，就得到了每一个词所出现的次数，以及这 1 4 在线的时问序列异常检测算法研究 个词所代表的子序列的位置。注意，这一过程可以在d ( 研) 的时间复杂度内完成 ( 研为整串时间序列的长度) 。 若有某个词的出现次数为1 ，则可认为这个词所代表的子序列与其它的子序 列都不相似，因为只有这一个子序列被转换为这个词。在算法2 一l 的外层循环中， 应优先考虑这一类的子序列。因此，我们可以将所有的词按照它们的出现次数从 小到大排序，并在外层循坏中优先考虑具有较小出现次数的词所代表的子序列。 同样的，可以认为同一个词所代表的子序列都相似，因为它们有相同的s a x 表示。因此，在内层循环中，可以从t i l e 树中获取与当前子序列具有相同s a x 表示的子序列，并在内层循环中优先考虑这些子序列，以达到使所计算出的相似 性距离较小的目的。 在进行了这些优化之后，h o ts a x 算法比穷举算法有近千倍的提甜1 5 】。在