（计算机软件与理论专业论文）时间序列的相似性查询与异常检测.pdf

摘要 摘要 时间序列是按时间顺序排列的、随时间变化且相互关联的数据序列，在经济、 金融、科学观测和工程等各个领域都广泛存在。如何有效地管理和利用这些历史 时间序列，发现这些数据背后隐含的规律和知识，是人们广泛关注的问题。与传 统时间序列分析提出假设然后进行验证的数据处理方法不同，时间序列数据挖掘 适合发现型任务，能够从大量历史数据中挖掘出潜在的、未知的、有价值的知识， 已经吸引了越来越多的关注。 目前，时间序列数据挖掘主要包括相似性查询、序列挖掘、分类、聚类以及 异常检测。论文主要研究了翅型堡查塑量显簋捡型? 包括时间序列的模式表示、 相似性度量、索引和查询、异常定义和检测，主要的研究内容和研究成果简单介 绍如下： ( 1 ) 时间序列的模式表示 由于时间序列数据的海量和复杂数据特点，直接在时间序列上进行数据挖掘 不但在储存和计算上要花费高昂代价而且可能会影响算法的准确性和可靠性。时 问序列的模式表示是一种对时间序列进行抽象和概括的特征表示方法，是在更高 层次上对时间序列的重新描述。论文首次将边缘算子日l 入时间序列研究，提出了 基于时态边缘算子的分段线性表示方法( 简称为t e o 表示) 。t e o 表示简单直观， 具有数据压缩和除噪能力。在不同领域的时间序列数据集上的实验表明：与其它 几种分段线性表示相比，t e o 表示与原始时间序列之间的拟合误差更小，具有 很强的适应性，能够应用于不同的数据特征环境。 ( 2 ) 时间序列的相似性度量 欧几罩德距离和动态时间弯曲距离是时间序列数据挖掘中主要采用的两种 相似性度量。但是欧几里德距离不支持时间序列的线性漂移和时间弯曲，动态时 间弯曲距离则因为平方阶的时间复杂度无法得到广泛的应用。论文在时间序列的 模式表示基础上，提出了动态模式匹配距离( 简称为d p m 距离) ，d p m 距离支持 时问序列的时间弯曲，时间复杂度随着模式长度的增长而接近线性。在仿真数据 集和人脸图像识别数据集上的实验表明：采用d p m 距离的k n n 方法在分类准确 第v i 页 摘要 率上超过了动态时自j 弯曲距离和欧式距离，在分类速度上比动态时间弯曲距离提 高了十倍以上。 ( 3 ) 时间序列的索引 多维空间索引常被用于时间序列的相似性查询，比如r - t r e e ，r + t r e e ，x t r e e 等。但是这些索引结构是为空间对象索引而设计的，只考虑了空间对象的形状和 位置，忽视了空间对象之间的顺序关系，因此并不适合时间序列的相似性查询。 在r t r e e 的基础上，提出了一种有序的多维空间索引o r - t r e e ，能够保存空间对 象之间的顺序关系。实验表明：与r t r e e 相比，基于o r t r e e 的相似性查询在 磁盘i o 次数和候选集比率上都大幅度下降，相似性查询的效率得到了显著提高。 该方法同样可以推广到其它的多维空间索引。 ( 4 ) 时间序列的相似性查询 采用动态模式匹配距离的时间序列相似性查询效率仍然不高，为了进一步提 高相似性查询的效率，提出了动态模式匹配距离的下界距离( 简称为d p m _ l b 距 离) ，只需扫描时间序列一趟。实验表明：采用d p ml b 距离能够快速过滤5 0 以上不满足相似性要求的时间序列，大大减少了动态模式匹配距离的计算量。同 时，d p ml b 距离满足距离收缩性引理，能够保证相似性查询的完备性。 ( 5 ) 时间序列的异常检测 目前，时间序列的异常还没有一个大家公认的定义。论文归纳了时问序列的 三种异常类型，并对时间序列的模式异常进行了深入探讨和研究。在时间序列的 模式表示基础上，提出了基于模式密度的时间序列模式异常的定义。同时，给出 了时间序列模式异常的检测算法，采用“异常因子”来衡量时间序列模式的异常 程度。与其它异常检测算法相比，t o d 算法不需要训练集，而且对算法参数的 变化不敏感。在仿真数据集和真实数据集( 如股票数据等) 上的实验证明了模式异 常定义的合理性以及t o d 算法的有效性。 关键词：时间序列，模式表示，相似性查询，空间存取方法，异常检测 中图分类号：t p 3 9 第v i i 页 英文摘要 a b s t r a c t at i m es e r i e si sad a t as e q u e n c eo fo b s e r v a t i o n sw h i c ha r eo r d e r e di nt i m e ( o r s p a c e ) ，w h i c he x i s t si nv a r i o u sf i e l d se x t e n s i v e l y , s u c ha si n d u s t r y , e c o n o m y , f i n a n c e ， s c i e n c eo b s e r v i n ga n ds o c i a ls c i e n c e ，e t c h o wt om a n a g ea n du s et h e s et i m es e r i e s d a t a e f f i c i e n t l y i sa ni n t e r e s t i n gp r o b l e m c l a s s i c a lt i m es e r i e s a n a l y s i sa l w a y s p r o p o s eah y p o t h e s i sf i r s t ，t h e np r o v ei t sv a l i d i t y , w h i c hi sn o ts u i t a b l ef o rd i s c o v e r y t a s k t i m es e r i e sd a t am i n i n gc a ne x t r a c th i d d e na n dp o t e n t i a l l yu s e f u lk n o w l e d g e f r o ml a r g ea m o u n t so fd a t aw h i c hm a y b eo m i t t e db yu s e r , w h i c ha t t r a c t sm o r ea n d m o r ea n e n t i o n a tp r e s e n t ，m a i nt o p i c so ft i m es e r i e sd a t al i l i i l i n gi n c l u d es i m i l a r i t ys e a r c h ， t e m p o r a lp a t t e mm i n i n g ，c l a s s i f i c a t i o na n dc l u s t e ra n do u t l i e rd e t e c t i o n i nt h i s d i s s e r t a t i o n ，s i m i l a r i t ys e a r c ha n do u t l i e rd e t e c t i o na r et ob es t u d i e d ，w h i c hi n c l u d e s e v e r a lp r o b l e m ss u c ha sp a t t e mr e p r e s e n t a t i o no ft i m es e r i e s ，s i m i l a r i t ym e a s u r e ， i n d e xf o rs i m i l a r i t ys e a r c h d e f i n i t i o na n dd e t e c t i o no fo u t l i e ri nt i m es e r i e s t h em a i n w o r k sa n dc o n t r i b u t i o n so f t h i sd i s s e r t a t i o na r e ： ( 1 ) p a t t e r nr e p r e s e n t a t i o no f t i m es e r i e s d u et ol a r g ea m o u n ta n dc o m p l e xd a t ac h a r a c t e ro ft i m es e r i e s ，d a t am i n i n g d i r e c t l yo nr a wt i m es e r i e s i s t i m e c o n s u m i n ga n di n e f f i c i e n t s o m e t i m e s ，t h e a c c u r a c ya n dr e l i a b i l i t yo fm i n i n gr e s u l t sw i l ld e s c e n d p a t t e r nr e p r e s e n t a t i o no ft i m e s e r i e si sa b s t r a c ta n ds u m m a r yo ft i m es e r i e s ，a l s oah i 曲l e v e lf e a t u r ed e s e r i p t i o no f t i m es e r i e s an e wp i e c e w i s el i n e a rr e p r e s e n t a t i o n0 l 鼬o ft i m es e r i e si sp r o p o s e d t h em e t h o dd e s i g n sak i n do f t e m p o r a le d g eo p e r a t o ra n du s ei tt of i n de d g ep o i n t so f t i m es e r i e s ，c h o o s es o m ee d g ep o i n t sa ss e g m e n t e dp o i n t s ，t h e nc o n n e c tt h e s e s e g m e n t e dp o i n t sw i t hl i n es e g m e n t s c a l l e dt e or e p r e s e n t a t i o no ft i m es e r i e s t e o r e p r e s e n t a t i o ni sv e r ys i m p l ea n di n t u i t i o n i s t i c ，i tc a nc o m p r e s st i m es e r i e sm u c h ，a n d r e m o v es o m en o i s e si nt i m es e r i e s d e t a i l e de x p e r i m e n t ss h o wt h a tc o m p a r e dw i t h s e r v e r a lp l r r e p r e s e n t a t i o n s ，t e or e p r e s e n t a t i o ni sam o r ep r e c i s ea p p r o x i m a t i o nt o r a wt i m es e r i e s a n dc a nb ea p p l i e dv a r i o u sf i e l d sw i t hd i v e r s ed a t af e a t u r e s ( 2 ) s i m i l a r i t ym e a s u r e e u c l i d e a nd i s t a n c ea n dd y n a m i ct i m ew a r p i n g ( d t w ) d i s t a n c ea r et w om a i n s i m i l a r i t ym e a s u r e sb e t w e e nt i m es e r i e s h o w e v e r , e u c l i d e a nd i s t a n c ei sn o ts u i t a b l e f o rt i m es e r i e sw h e no c c u r sl i n e a rd r i f to rt i m ew a r p i n g ，d t wd i s t a n c ec a n n o tb e 第v i i i 面 英文摘要 a d o p t e dw i d e l yb e c a u s eo fi t ss q u a r et i m ec o m p l e x i t y an e ws i m i l a r i t ym e a s u r e ， c a l l e dd y n a m i cp a t t e r nm a t c h i n g ( d p m ) d i s t a n c ei sd e f i n e db a s e do nt h ep a t t e m r e p r e s e n t a t i o no ft i m es e r i e s d p md i s t a n c ec a l ls u p p o r ta l lt r a n s f o r m a t i o n so ft i m e s e r i e si n c l u d et i m ew a r p i n gw i t ha p p r o x i m a t el i n e a rt i m ec o m p l e x i t y e x p e r i m e n t so n s e v e r a lt u r ed a t a s e t ss h o wt h a tt h ea c c u r a c yo fc l a s s i f i c a t i o no fk n nm e t h o db a s e d d p md i s t a n c ee x c e e d sb a s e do ne u c l i d e a nd i s t a n c ea n dd t w d i s t a n c e ，t h es p e e do f c l a s s i f i c a t i o ni sa l s oi m p r o v e da b o v et e nt i m e s ( 3 ) i n d e xf o rt i m es e r i e s s p a t i a la c c e s sm e t h o d ( s a m ) o f t e nb eu s e db ys i m i l a r i t ys e a r c ho v e rt i m es e r i e s d a t a ，s u c ha sr - t r e e ，r * - t r e e ，x - t r e e ，e t c a l lt h e s em e t h o d sa r ed e s i g n e df o rs p a t i a l o b j e c t s ；w h i c ho n l yc o n s i d e rt h ep o s i t i o na n ds h a p eo fs p a t i a lo b j e c t s ，i g n o r eo r d e r r e l a t i o n sb e t w e e nt h e m i nt h i sd i s s e r t a t i o n ，an e ws p a t i a li n d e xs t r u c t u r ec a l l e dt h e o r - t r e ei sp r o p o s e d ，w h i c hm a k es o m ei m p o r t a n tm o d i f i c a t i o n st oc l a s s i c a lr - t r e e ， k e e po r d e rr e l a t i o n sb e t w e e ns p a t i a lo b j e c t si nt h el e a fn o d e so ft h eo r - t r e e t h i s i m p r o v e m e n tr e d u c e st h en u m b e r so fa c c e s sd i s ka n df a l s ea l a r m sg r e a t l y , a n dc a nb e g e n e r a l i z e dt oo t h e rs a m s e x p e r i m e n t sb a s e do ns i m i l a r i t ys e a r c hi nt i m es e r i e sd a t a p r o v ei t sh i g he f f i c i e n c yo f t h eo r t r e e ( 4 ) s i m i l a r i t ys e a r c hi nt i m es e r i e s s i m i l a r i t ys e a r c hb a s e do nd p md i s t a n c ei sn o th i g he f f i c i e n t al o w e rb o u n d i n g m e a s u r e ( d p ml b ) f o rd p m d i s t a n c ei si n t r o d u c e dt oi m p r o v et h es i m i l a r i t ys e a r c h i nt i m es e r i e s d p m l bm e a s u r ec o m p u t ev e r yf a s t ，n e e ds c a nw h o l et i m es e r i e so n l y o n c e e ：i p e r i m e n t ss h o wt h a tt h ed p m l bm e a s u r ec a l lq u i c k l yf i l t e ra b o v eh a l fo f t i m es e r i e sw h i c hi sd i s s i m i l a rm mt h eq u e r yt i m es e r i e s a n dr e d u c et h ec o m p u t a t i o n o fd p md i s t a n c el a r g e l y t h ed p m l bm e a s u r ea l s os a t i s f i e sl o w e rb o u n d i n g l e m m a ，w h i c he n s u r e si n t e g r i t yo fs i m i l a r i t yr e s u l t ( 5 ) o u t l i e rd e t e c t i o ni nt i m es e r i e s a tp r e s e n t ，t h e r ei sn od e f i n i t i o no fo u t l i e ro f t i m es e r i e st ob ea c c e p t e db ym o s t o f r e s e a r c h e r s t h r e et y p e so fo u t l i e ro f t i m es e r i e sa r ec o n c l u d e d ，a n dp a t t e mo u t l i e r i sd i s c u s s e dd e e p l y an e wd e f i n i t i o no fp a t t e r no u t l i e ri nt i m es e r i e si si n t r o d u c e d ， b a s e do nt h ep a t t e r nr e p l l e s e n t a t i o no f t i m es e l i e s ，u s eo u t l i e rf a c t o rs e r i e sd e s c r i b et h e o u t l i e ro t 、t i m es e r i e s w i t ht h ed e f i n i t i o n ，t h et o i ) a l g o r i t h mf o rd e t e c tp a t t e r no u t li e r i nt i m es e r i e si sp r o p o s e d w h i c hg i v e sa no u t l i e rt h c t o rs e q u e n c ea sr e s u l t s ap a t t e r n i sc o n s i d e r e da s a no u t l i e ri f i t so u t l i e rf a c t o re x c e e d sas p e c i f i e dt h r e s h o l d c o m p a l l c d w i t ho t h e rm e t h o d s ，t h ei o da l g o r i t h mn e e dn o tt r a i n i n gd a t a s e t ，a n di sn os c n s i t i v e 第1 x 页 英文摘要 t oi t s p a r a m e t e r s e x p e r i m e n t so l ls y n t h e t i ca n dr e a ld a t as h o wt h a to u ro u t l i e r d e f i n i t i o no ft i m es e r i e si sr e a s o n a b l ea n dt h et o dm e t h o di se l i c i e n tt od e t e c t o u t l i c r si nt i m cs e r i e s k e y w o r d s ：t i m es e r i e s ，p a t t e r np r e s e n t a t i o n ，s i m i l a r i t ys e a r c h ，s p a t i a la c c e s s m e t h o d ，o u t l i e rd e t e c t i o n c l c ：t p 3 9 第x 贞 时间序列的相似性查询与异常检测 s i m i l a r i t ys e a r c ha n do u t l i e rd e t e c t i o ni n t i m es e r i e s 导师 指导小组成员 肖辉 胡运发教授 施伯乐 胡运发 顾宁 葛家翔 教授 教授 教授 教授 图表目录 图表目录 图1 1 时间序列的时间弯曲6 图1 - 2 论文的主要研究内容及相互关系9 图2 - 1 时间序列及其模式表示1 5 图2 2 时间序列的分段线性表示1 9 图2 3s o b e l 边缘算子2 2 图2 - 4 时间序列的边缘点2 3 图2 5 时间序列c l o s e a 上p l r 表示的拟合误差比较2 9 图2 - 6 时间序列r a n d o m w a l k 上p l r 表示的拟合误差比较3 0 图3 - 1 时间序列的振幅平移3 5 图3 - 2 时间序列的振幅伸缩3 5 图3 3 时间序列的不连续性3 5 图3 - 4 时间序列的线性漂移3 6 图3 - 5 时间序列的时间轴伸缩3 6 图3 - 6 时问序列的时间轴弯曲3 6 图3 7 时间序列的动态时间弯曲路径3 8 图3 - 8 时间序列x ； 和y = 之间的累积距离矩阵3 9 图3 9 时间序列的动态模式匹配4 3 图3 1 0f a c e s 数据集示例4 5 图3 一llf a c e s 数据集上k n n 分类准确率( 按人脸表情分类) 4 6 图3 。1 2c b f 数据集三类时间序列样本4 8 图3 1 3 不同大小的c b f 数据集上k n n 方法的分类时间4 9 图4 1 三条时间序列的0 r t r e e 索引结构5 9 图4 2d p ml b 距离在不同误差阈值下的候选比率6 6 图4 3d p ml b 距离在不同误差阈值下时间代价6 6 图4 4 不同大小数据集下采用d p ml b 距离的候选比率6 7 图4 5r t r e e 和o r t r e e 索引的性能比较6 9 图5 一l 时间序列的模式异常7 2 第1 v 页 图表目录 图5 2k 可达领域( k = 2 ) 图5 3 时间序列的异常因子示例 图5 - 4 时间序列数据集m a d a t a 上的异常因子 图5 5 时问序列k e o g h上的异常因子data 图5 - 6 时间序列f i rd a t a 上的异常因子 图5 - 7 沪市每同成交额序列的异常因子一 7 6 7 7 8 0 8 1 8 2 8 3 表2 1 时间序列的有关符号及定义1 4 表2 2 时间序列的t e o 表示算法2 5 表2 3k d a t a 数据集描述2 6 表2 4 压缩率为8 0 时几种p l r 表示的拟合误差2 8 表3 1f a c e s 数据集上k n n 分类准确率( 按人脸朝向分类) 4 6 表3 2f a c e s 数据集上k n n 分类准确率( 按人脸表情分类) 4 7 表3 3c b f 数据集上k r m 分类准确率和分类时间4 8 表4 1o r - t r e e 的查询算法6 0 表4 2o r - t r e e 的插入算法6 1 表4 3o r - t r e e 的结点分裂算法6 2 表5 1 时间序列的异常检测算法7 7 第v 页 第一章绪论 第一章绪论 本章阐述了全文研究工作的背景和意义，介绍了时间序列的相似性查询 与异常检测等相关问题的研究现状。同时，简要介绍了全文的研究内容、相 关成果以及组织结构 1 1 研究背景 随着社会信息化和数字化的发展，人们在金融、经济、工农业、科学工程和 实验中不断产生的大量的各种类型的数据得以保存。据粗略估算，自2 0 世纪8 0 年代起，全球信息量每隔十几个月甚至几个月就要增加一倍，呈爆炸式增长。至 2 0 0 0 年，全球数据存储容量已达3 0 0 万个t b 。因此，如何充分有效地管理和利 用这些海量数据、发现这些数据背后隐含的规律和知识，就成为人们目前非常关 注的问题。 在这些保存的历史数据中，绝大部分都是根据时间顺序对历史事件的记录， 我们称之为时态数据( t e m p o r a ld a t a ) 。根据记录数据类型的不同，时态数据主要 包括三种类型：时间序列，事务序列和事件序y j z h 0 2 。所谓时间序y 0 ( t i m es e f i e s ) 就是按照时间先后顺序排列的各个观测记录的有序集合，其中观察记录是数值类 型的。时间序列在商业、经济以及科学观测等各个社会领域中都广泛存在，比如 金融证券市场中每天的股票价格：商业零售行业中，某项商品的周期销售额：气 象预报研究中，某一地区的气温与气压读数；以及在生物医学中，某一症状病人 在每个时刻的心跳变化等等。 传统的时间序列分析是作为概率统计学科的一个课题来研究的，经过几十年 的发展，已经奠定了比较完善的理论基础，在实际应用中也发挥了重要的作用 b j r 9 4 】。传统的时间序列分析着重研究具有随机性的动态数据，研究方法着重 于全局模型的构造。常用的方法有自回归滑动平均( a p d v i a ) 模型等 b 0 9 3 。a r m a 模型是一种线性分析方法，它要求时间序列必须是平稳的，并要求a r m a 模型所 产生的时间序列与时间观测序列的误差互不相关并呈正态分布。而对于绝大多数 实际系统所产生的时间序列( 如股市价格综合指数) 来说，这种平稳性假设以及误 第1 页 第一章绪论 差的互不相关性和正态分布往往很难满足。此外，传统时间序列分析是一种验证 型的分析工具，先提出假设然后进行验证，目的是为了对系统整体行为的把握和 预测，它不适合用于发现型的任务。然而在实际分析中，往往需要对时间序列局 部特征进行分析，比如发现频繁出现的变化模式；比较不同序列在某段时间内， 其运动变化是否相似；监控时间序列是否在某一时刻产生异常等等。这些发现型 任务在许多应用领域中同样具有重要的意义。下面就是一些典型应用的例子： 在气象预报分析中，对于气压序列，需要找出在一段时间内那些频繁出 现的变化模式，结合专家知识和经验，从中归纳气压变化的规律；或者 给定一个气压序列和气温序列，要求找出这两个序列之间有那些是经常 出现的相互关联的变化模式等。 在证券市场，找出在过去两星期里与微软公司的股票价格序列的变化模 式相似的公司，从中可以分析产生这种变化模式的原因。 在金融领域，跟踪信用卡顾客的使用情况，当顾客在某段时期内的信用 卡使用情况异常时，能够及时报告，预防信用欺诈。 对于上述时问序列应用分析问题，传统的时间序列分析方法已不能适用。数 据挖掘是- r 新兴的交叉性学科，可以从大量的历史数据中提取出隐含的、事先 未知的、有价值的知识，为人们的社会实践提供决策支持 h k 0 1 】。这与那些先提 出假设再进行验证的数据处理方法截然不同。 自上个世纪9 0 年代以来，时间序列数据挖据得到越来越多的研究者的关注 和重视。时间序列数据挖掘是针对时间序列的模式发现过程，旨在研究隐含在时 间序列之中的更深层次的知识，包括时间序列的相似性查询、时序模式挖掘、时 间序列分类和聚类、时间序列异常发现等研究内容。 本文的工作围绕时间序列展开，从时间序列的模式表示出发，主要研究了时 间序列的相似性查询和异常检测这两个问题。时间序列的相似性查询是时间序列 数据挖掘的重要问题，它可以分为全序列匹配查询和子序列匹配查询。全序列匹 配查询是从时间序列数据集中找出所有与查询序列在整体上相似性匹配的时间 序列；子序列匹配查询则是从比查询序列长得多的时间序列中找出所有与查询序 列相似性匹配的子序列的位置偏移和长度。时间序列的异常检测是近几年发展起 来的一个热点问题，目的是为了发现时间序列中的异常变化情况，在异常发生时 能够立即向用户发出警告。 第2 页 第一章绪论 1 2 研究现状 时间序列上的数据挖掘研究自从2 0 世纪9 0 年代以来发展迅速，其研究内容 涵盖了时间序列的相似性查询、时序模式挖掘、时间序列分类和聚类、时间序列 异常检测等等。 吐间序歹的相j 咧生查询是时间序列数据挖掘的重要问题，至今还没有得到很 好地解决。时间序列来源于实际生活中的各个应用领域，采样方法和测量标准都 不一致，具有短期波动频繁、大量噪声干扰以及非稳态的特点，使得相似性查询 变得非常困难。相似性度量是时间序列的相似性查询的基础，时间序列的索引技 术则可以提高相似性查询的效率。 鲢间庄殛的显堂捡捌是近几年的研究热点。目前，还没有一个公认的时间序 列异常定义，根据不同假设，都提出了许多不同的时间序列异常定义。与时间序 列异常相关的术语包括新颖性、奇异模式、偏离点和不规则等等。 由于时间序列的海量和复杂的数据特点，直接在原始时间序列上进行数据挖 掘不但效率低下，往往难以获得满意的结果。时间序列的模式表示是对时间序列 进行抽象和概括的特征表示方法，是在更高层次上对时间序列的重新描述。时阃 序列的模式表示不但能够对时间序列数据进行压缩，而且突出了时间序列的模式 变化特征。 以下重点介绍时间序列的模式表示、相似性度量、查询索引和异常检测这四 方面的研究工作。 1 2 1 时间序列的模式表示 时问序列数据挖掘的对象通常是海量的时间序列数据，其短期波动频繁、大 量噪声干扰以及非稳态的特点使得直接采用原始时间序列进行相似性查询、时间 序列分类和聚类、时序模式挖掘等工作不但效率低下，甚至会影响时间序列数据 挖掘的准确性和可靠性。因此，许多研究者提出了时间序列的模式表示方法，从 更高层次上对时间序列重新进行描述，在时间序列的模式表示上进行数据挖掘。 时间序列模式表示的基本思想是从时间序列中提取特征，将时间序列变换到特征 空间，采用特征空间的特征模式来表示原始时间序列。时间序列的模式表示有两 个优点：首先是压缩了时间序列数据，能够提高数据挖掘工作的效率；其次时问 箱3 页 第一章绪论 序列的模式表示在一定程度上保留了时间序列的主要特征，去除了一些次要细 节，更能反应时间序列的变化情况，有利于数据挖掘的进行。 时间序列的模式表示方法主要可以分类四种类型：频域表示法、奇异值表示 法、符号表示法以及分段线性表示法。 1 2 1 1 频域表示 频域表示的基本思想将时间序列看作是一个离散信号，采用离散傅立叶变换 ( d i s c r e t ef o u r i e rt r a n s f o r m ，d f r ) 或者离散小波变换( d i s c r e t ew a v e l e tt r a n s f o r m ， d w n 将时间序列从时间域映射到频率域空间，用频谱来表示原始时间序列 ( a f s 9 3 ；c f 9 9 ) 。对于大部分信号来说，能量主要集中在几个主要的频率上，因 此可以用很少的几个频率来近似表示原始时间序列，达到数据压缩的目的，而且 能够较好地保持时间序列的主要形态。 时间序列的频域表示应用于相似性查询时支持欧几里德距离和索引，能够保 证查询的完备性，但不支持加权欧几里德距离等度量。 1 2 1 2 奇异值表示 奇异值分解( s i n g u l a rv a l u ed e c o m p o s i t i o n ，s v d ) 是一种常见的降维方法，已 经成功用于图像和文本的索引【k s a 9 9 ；w a s + 9 6 】。时间序列的s v d 表示方法与 其它的模式表示方法不同，它是对整个时间序列数据库的整体表示，是对整个时 间序列数据库的特征提取和变换。作为线性变换，s v d 方法在数据重构上误差 最小，这使得s v d 在一些情况下能够取得很好的性f l r i p 9 6 。但是，s v d 表示 方法的时间复杂度为o ( m n 2 ) ，其中m 是指时间序列数据库的大小，n 是指时间 序列的平均长度。当插入或者删除一条时间序列时，整个时间序列数据库的s v l 3 表示都必须重新计算，时间代价很高。 121 3 符号化表示 时间序列是有连续的实数值构成的。时间序列的符号化表示就是通过一些离 散化方法将时间序列的实数值或者一段时间内的时间序列波形映射到有限的符 号表上，将时间序列表示为有限符号的有序集合，即字符串。符号化表示的优点 在于可以利用许多字符串研究领域的成果，缺点在于如何选择合适的离散化算 法，解释符号的意义，以及定义符号之间的相似性度量。 第4 页 第一章绪论 a g r a w a l 等人 a p w + 9 5 将时间序列的波形符号化，引入多种符号算子；p a r k 等人 p c y 0 0 + 直接将时间序列的值采用等宽离散化方法和最大熵方法符号化； h y 9 9 将时问序列相邻点的变化率符号化；【蒋o o 提出了基于云模型的符号化 方法。 1 2 1 4 分段线性表示 时间序列的分段线性表示( p i e c e w i s el i n e a rr e p r e s e n t a t i o n ，p l r ) 是指采用首 尾相邻的一系列线段来近似表示时间序列。利用线段来近似表示时间序列的思想 最早可追溯到 p h 7 4 ，他们指出分段线性表示有数据压缩和过滤的作用，而且具 有时间多解析的特点。时间序列p l r 表示中线段的数目决定了对原始时间序列 的近似粒度。线段越多，线段平均长度就越短，反应了时间序列的短期波动情况： 线段越小，线段平均长度就越长，反应了时间序列的中长期趋势。 时问序列的p l r 表示简单直观，而且具有许多优点，得到众多研究者的重 视，是一种很有希望的模式表示方法( k j m 9 5 ；p k c 0 1 ；p l c 9 9 ；k p 9 8 ；l s l + 0 0 ； p f 0 2 ；x f h 0 4 ) 。 与时间序列的分段线性表示思想类似的还有分段多项式表示，采用多项式函 数而不是线段来近似表示一段时间范围内的时间序列。当多项式的阶为l 时，则 退化为时间序列的分段线性表示。 1 2 2 时间序列的相似性度量 时间序列的相似性度量研究是时间序列数据挖掘的基础问题。两条完全相同 的时间序列几乎不存在，因此采用相似性度量来衡量时间序列之间的相似性。时 间序列的相似性度量不一定支持距离三角不等式，必须能够应用到时间序列的数 据挖掘中，例如时间序列的相似性查询、聚类和分类等等。 由于时间序列数据的复杂性，经常发生振幅平移和伸缩、线性漂移和时间轴 伸缩等形变，因此相似性度量应该最大程度地支持时间序列的上述形变。 1 2 2 1 欧几里德距离 欧几里德距离是时间序列相似性研究中最广泛采用的相似性度量 a f s 9 3 ； f r m 9 4 ；g k 9 5 ；r m 9 7 ；c f 9 9 1 。欧几里德距离的优点是计算简单，容易理解，在 第5 页 交变换下保持不变，满足距离三角不等式，支持多维空间索引，也可以应用到时 一、， 间序列的聚类和分类等研究领域。它的确强是不允许时间序列有不同的基准线， 例如，在一个月内，分别用华氏和摄氏两种标准记录每天的气温，得到的两条气 温序列尽管波形一致，但是在欧几里德距离下不会认为是相似的。 欧几里德距离的一些改进可以支持时问序列的振幅平移和伸缩，但是仍然不 支持线性漂移和时间弯i 擅 g k 9 5 ；d g m 9 7 ；l k w 0 0 ；r m 9 8 1 。如图1 - l 所示，两条 时间序列的波形基本相似，但是波峰和波谷的位置并没有完全对齐，而是略有偏 差，在欧几里德距离下这两条时间序列也不会被认为是相似的。 图1 - 1 时间序列的时间弯曲 1 _ 2 2 2 动态时间弯曲距离 为了支持时间序列的时间轴伸缩，使得时间序列的相似波形能够在时间轴上 对齐匹配，b e m d t 和c l i f f o r d 将在语音识别中广泛使用的动态时间弯i 抽( d y n a m i c t i m ew a r p i n g ，d t w ) 距离引入到时间序列的相似性研究q 6 b c 9 4 。动态时问弯曲 距离根据最小代价的时间弯曲路径进行对齐匹配，能够支持时间序列的时间轴伸 缩，但是d t w 距离不满足距离三角不等式，时间复杂度为o ( 玎2 ) ，其中”表示 时间序列的长度。这些缺点限制了d t w 距离的广泛使用。 在相似性查询研究中，许多研究者提出了d t w 距离的下界( l o w e rb o u n d i n g ， l b ) e e 离，通过l b 距离快速过滤部分不满足相似性要求的时间序列，再对剩下 的时间序列计算d t w 距离( y j f 9 8 ；k p c o i ；k e 0 0 2 ) 。由于l b 距离的计算比d t w 距离快的多，且满足距离收缩性引理，因此这种方法能够提高基于d t w 距离的 相似性查询效率，并保证查询的完备性。但是这种方法并不使用于时间序列的聚 类和分类算法。 另外一种方法是提出d t w 距离的近似度量。【p l c 0 1 提出过一种基于时间 第6 页 第一章绪论 序列子段的近似度量，该近似度量定义为所有子段d t w 距离的最大值，要求子 段是单调变化且每条时间序列的子段数目相同。【k e 0 0 2 在d t w 距离的全局约束 假设下，提出