（计算机应用技术专业论文）时间序列挖掘相关算法研究及应用.pdf

摘要 随着计算机与信息技术的普及和大容量存储技术的发展，人们在日常事务处 理和科学研究中逐渐积累了大量的宝贵数据。这些数据背后蕴藏着对决囊有重要 参考价值的信息。如何充分有效地利用这些历史数据，从中提取出用户需要的信 息正成为当今数据挖掘领域广泛关注的热点问题。 时阃序歹1 j 数据反映了属性值在时间或空问顺序上的特征。利用时间序列数据 挖掘( t i m es e r i e sd a t am i n i n g ，简称t s d m ) ，可以获得数据中蕴含的与时间相 关的有用信息，实现知识的提取。由于时间序列的数据类型复杂且具有高维性、 噪声干扰及波动性等特点，因此时间序列挖掘是数据挖掘中的一个重要研究方 向。目前重点的研究内容包括时间序列的模式表示、时间序列的相似性查询、时 间序歹| j 的聚类积分类、时阊序歹 j 的异常检铡等。 本文在国内外时间序列数据挖掘最新研究的基础上，以石油工业领域中测井 和录井色谱数据序列的分析处理为实际应用背景，对时间序列挖掘中的线性拟 合、在线划分、相似性度量、时态频繁模式挖掘四个方面的问题进行了研究分析， 提出一些算法和解决方案，取得一定成果。主要工作和创新之处有： l 。提出了一种基于关键点的时间序列线性拟合表示方法。该算法在扫描数 据的过程中利用单调序列中三个连续数据形成的夹角和非单调序列中的极值点， 从序列中挑选反映趋势变化的关键点，实现时间序列的线性拟合。实验结果表明 该算法拟合效果蘸好，剔除了嗓音干扰，并能够精确定位单调序列中的突变转折 点，发现序列中的尖蜂状态。 2 提出了一种基于层次聚类的在线序列分割算法。该算法利用数据序列的 有序性特征，构造了一种存储划分特征的链表结构，一次扫描数据库完成数据序 列的在线划分，时间复杂度为o ( r t ) 。同时，利用链表结构中保存的划分特征信息， 历史信息的快速查询成为可能。实验结果表现此算法具有良好的划分性能和可扩 展性能。 3 提出了一种基于关键点动态时间弯曲距离的相似性度量方法该方法在 时间序列线性拟合的基础上，仅使用序列中的关键点用于弯曲距离矩阵计算。实 验结果表明：基于关键点的动态时间弯曲距离度量方法在准确性上优于欧氏距 离，与经典的动态时间弯曲距离近似，但明显提高了捡索速度。 4 对f p g r o w t h 算法进行改进，使之适用于时态约束下的频繁模式挖掘。 由于经典的频繁模式挖掘算法f p - g r o w t h 没有考虑时间向量的影响，无法直接应 时问序列挖掘相关算法研究及应用 用于时态频繁模式的挖掘。改进后的算法构造了一种用于存储频繁模式时态属性 的双树结构。利用这种双树结构，两次扫描数据库实现时态频繁项目的有效挖掘。 实验结果表明该算法是有效的和可扩展的。 5 针对目前石油工业领域中各类数据序列的特点和实际的应用需求，给出 时间序列挖掘算法在测井和录井数据序列中的应用样例。实验结果显示：数据 序列在线划分算法实现了测井曲线的快速粗划分和分段信息的快速查询；数据 序列线性分段拟合方法能够有效捕获色谱和测井数据序列中的尖峰予序列，准确 定位序列中的变化转折点，忽略变化细微的数据点，在保持序列形态不变的同时 极大地降低了数据存储量。 全文共分为七个章节，第一章对时间序列挖掘进行了综述，包括其应用背景、 国内外研究进展等；第二章至第五章从四个方面展开了算法研究探讨：时间序列 的线性拟合、时间序列的在线划分、时间序列的相似性度量和时态频繁模式挖掘； 第六章在上述研究的基础上，给出了序列挖掘算法在石油测井和录井数据序列中 的应用实例；最后一部分，即第七章，对全文进行总结，并提出了进一步的研究 思路。 。 关键词：时间序列，线性拟合，关键点，在线划分，划分特征链表，相似性查询， 时态频繁模式 a b s t r a c t w i t l lt h e p o p u l a r i t y o fc o m p u t e ra n di n f o r m a t i o nt e c h n o l o g y , a n dt h e g r e a t d e v e l o p m e n to fs t o r a g et e c h n i q u eo fh i g hc a p a c i t y , ag r e a ta m o u n to fd a t ai sa c c u m u l a t e d i nd a i l yw o r ka n di ns c i e n t i f i cr e s e a r c h m u c hp o t e n t i a l l yu s e f u lk n o w l e d g ei sb i d e db e h i n d d a t a t o d a yh o wt om a n a g ea n du s et h e s et i m es e r i e sd a t ae f f i c i e n t l ya n de x t r a c tu s e f u l i n f o r m a t i o ni sa ni m p o r t a n tp r o b l e mi nd a t am i n i n g t i m es e r i e sd a t ar e f l e c t st h ef e a t u r e so fa t t r i b u t ev a l u e sa l o n gt i m es e q u e n c eo rs p a t i a l s e q u e n c e b ym i m n gp a t t e r n sf r o mt i m es e r i e sd a t a ，w ec a ng e tu s e f u li n f o r m a t i o nr e l a t e d t ot i m eh i d d e ni nt h ed a t a b a s e ，t h u si m p l e m e n te x t r a c t i o no fk n o w l e d g e t i m es e r i e sa r e c o m p l e xt y p e so fd a t a t h e yo f t e nh a v eh i g hd i m e n s i o n a l i t y ，n o i s ea n dv a r i o u sd i s t o r t i o n s e t c t i m es e r i e sd a t am i n i n g ( t s d m ) i so n eo ft h em o s ti m p o r t a n tr e s e a r c hf i e l d so fd a t a m i n i n g 。i t st o p i c s i n c l u d et i m es e r i e s r e p 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 ，c l u s t e r i n g ， c l a s s i f i c a t i o n o u t l i e rd e t e e t i o na n ds oo n b a s e do nt h ea c t u a la p p l i c a t i o no f a n a l y z i n gw e l ll o g g i n ga n dm u dl o g g i n gt i m es e r i e s i no i l f i e l d ，t h i sp a p e rd i s c u s s e st h ec u r r e n tr e s e a r c hs i t u a t i o n ，r e l a t e dw o r k ，a n ds o m e u p - t o d a t et e c h n o l o g i e s a n d d e v e l o p m e n t s i na l l u s i o n t ot h ep r o b l e m so fc u r r e n t a p p r o a c h e s ，w es t u d yt i m es e r i e s d a t am i n i n gi nf o u r a s p e c t s ：l i n e a rf i t t i n g ，o n l i n e s e g m e n t a t i o n ，s i m i l a r i t ys e a r c ha n dt e m p o r a lf r e q u e n tp a t t e r n sd i s c o v e r y s o m er e l a t e d a l g o r i t h m sa n ds o l u t i o n sa r ep r e s e n t e dh e r e t h em a i nw o r k sa n dc o n t r i b u t i o n so ft h i s d i s s e r t a t i o na r e ： 1 an o v e ll i n e a rf i t t i n ga l g o r i t h mb a s e do nk e yp o i n t si sp r e s e n t e d t h ea p p r o a c hf i r s t c h o o s e st h r e ec o n t i n u o u sd a t ap o i n t si nt u r nw h e nt h ed a t ap o i n t si nt i m es e r i e sa r es c a n n e d a c c o r d i n gt ot h ea n g l ef o r m e db yt h e s et h r e ed a t aa n dt h ee x t r e m ev a l u ei nm o n o t o n e s e q u e n c e ，t h em e t h o dt h e nr e c o r d sk e yp o i n t sr e f l e c t i n gt h es e q u e n c e sc h a n g i n gf e a t u r e u s i n gt h e s ek e yp o i n t s ，t h eo r i g i n a lt i m es e r i e sc a l lb ef i t t e dl i n e a r l yw h i l es o m es m a i l n o i s e sa r ea t t e n u a t e d t t l ea l g o r i t h mc a nf i n dp e a ks u b s e q u e n c e sa n dj u m pp o i n t sm o r e a c c u r a t e l y t h e o r ya n a l y s i sa n de x p e r i m e n tr e s u l t ss h o wt h a tt h en e wm e t h o di se f f i c i e n t 2 an e wo n l i n es e g m e n t a t i o na l g o r i t h mf o rt i m es e r i e si sp r e s e n t e d ，w h i c hi sb a s e do n h i e r a r c h i c a lc l u s t e r i n g a c c o r d i n gt ot h eo r d e rc h a r a c t e r i s t i c so fs e q u e n c ed a t a ，an o v e l s e g m e n tf e a t u r el i s ti sd e v e l o p e df o rs a v i n gs e g m e n ti n f o r m a t i o n i nt h ea l g o r i t h m , t i m e s e r i e sc a nb es e g m e n t e de f f e c t i v e l yw i t ho n es c a no ft h ed a t a b a s ea n dt h et i m ec o m p l e x i t y i so ( n ) h i s t o r i c a li n f o r m a t i o nc a l la l s ob ei n q u i r e dq u i c k l yu s i n gt h es e g m e n tf e a t u r el i s t 时间序列挖掘相关算法研究及应用 e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h mi se f f i c i e n ta n ds c a l a b l e 3 an e wd i s t a n c em e a s u r ec a l l e dk e y p o i n t sd y n a m i ct i m ew a r p i n gd i s t a n c ei sd e f i n e d h e r e t h i sm e t h o dc o m p u t e sw a r p i n gd i s t a n c eu s i n gk e y p o i n t so ft i m es e r i e s e x p e r i m e n t s s h o wt h a tt h en e wm e t h o di sm u c hm o r ea c c u r a t et h a ne u c l i d e a nd i s t a n c e c o m p a r e dw i t h t h ec l a s s i c a ld y n a m i ct i m ew a r p i n gd i s t a n c e ，t h ek e y p o i n t sd y n a m i ct i m ew a r p i n gd i s t a n c e p r o d u c e so n et ot h r e eo r d e r so fm a g n i t u d es p e e d - u p 、i mn oa p p r e c i a b l ed e c r e a s ei n a c c u r a c y 4 w i t h o u tc o n s i d e r i n gt h ef u n c t i o no ft i m ev e c t o r , t h et r a d i t i o n a lm i n i n ga l g o r i t h m c a l l e df p - g r o w t hd o e s n tb eu s e dt om i n et e m p o r a lf r e q u e n tp a t t e r n sd i r e c t l y a ni m p r o v e d a l g o r i t h mf r o mf p g r o w t h i s d e v e l o p e df o rm i m n gt e m p o r a lf r e q u e n tp a t t e r n s n 峙 a l g o r i t h mu s e san o v e ld o u b l eb + - t r e et os t o r et i m ea t t r i b u t e so ff r e q u e n tp a t t e r n s u s i n g t h ed o u b l et r e es t r u c t u r e ，f r e q u e n ti t e m s e t sc a l lb ed i s c o v e r e de f f i c i e n t l yb yp e r f o r m i n gt w o s c a n so ft r a n s a c t i o nd a t a b a s e e x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h a tt h i s a l g o r i t h mi s e f f i c i e n ta n ds e a l a b l e 5 a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fe x p l o r a t i o nd a t as e r i e sa n dt h ea c t u a la p p l i c a t i o ni n o i lf i e l d ，s o m et e s te x a m p l e so ft h e s ea b o v ea l g o r i t h m sa r es h o w e dh e r e ，w h o s ed a t ai s c o m ef r o mw e l ll o g g i n ga n dm u dl o g g i n g ：w e l ll o g g i n gc u r v ec a nb es e g m e n t e d a p p r o x i m a t e l ya n ds e g m e n t i n gi n f o r m a t i o nc a l la l s ob ei n q u i r e dq u i c k l yu t i l i z i n gt h i s o n l i n es e g m e n t a t i o nm e t h o do ft i m es e r i e s ；t h es u p e r i o r i t yo ft h el i n e a rf i t t i n gm e t h o d o ft i m es e r i e si ss h o w e dh e r e u s e r sc a na c q u i r et h ep i n n a c l es u b s e q u e n c ef r o mw e l l l o g g i n go rm u dl o g g i n ga c c u r a t e l y , r e c o r dk e yt u r n i n gp o i n t sr e f l e c t i n gt h es e q u e n c e s f e a t u r ea n di g n o r ed a t ap o i n t sw i t ht i n yc h a n g i n g i nt h i sa l g o r i t h m ，t h es h a p eo fc u r v ei s m a i n t a i n e dw h i l et h es t o r a g ei sd e c r e a s e dg r e a t l y t h i sp a p e ri n c l u d e ss e v e n c h a p t e r s c h a p t e r1g i v e sa no u t l i n ei nt s d m ，i n c l u d i n gt h e p r a c t i c a lb a c k g r o u n d ，a n ds o m eu p - t o d a t et e c h n o l o g i e sa n dd e v e l o p m e n t si nt h i sf i e l d f o u rp a n so ft s d ma r ed i s c u s s e df r o mc h a p t e r2t oc h a p t e r5 ：l i n e a rf i t t i n g ，o n l i n e s e g m e n t a t i o n ，s i m i l a r i t ys e a r c ha n dt e m p o r a lf r e q u e n tp a t t e r n sd i s c o v e r y b a s e do nt h e r e s e a r c hb e f o r e ，c h a p t e r6g i v e ss o m ea p p l i c a t i o n su s i n gw e l ll o g g i n ga n dm u dl o g g i n g d a t a f i n a l l y , o u rc o n c l u s i o n sa r ep r e s e n t e da n df u r t h e rr e s e a r c hp e r s p e c t i v e sa r eg i v e ni n c h a p t e r7 ， k e yw o r d s ：t i m es e r i e s ，l i n e a rf i t t i n g ，k e yp o i n t s , o n l i n es e g m e n t a t i o n ，s e g m e n t a t i o n f e a t u r el i s t ，s i m i l a r i t ys e a r c h ，t e m p o r a lf r e q u e n tp a t t e r n 图表目录 图卜l 时间序列样例1 图i - 2 采用欧式距离聚类结果6 图i - 3 欧式距离和动态时间弯曲距离的点对齐关系7 图2 - i 数据序列的基本变化模式1 7 图2 - 2f p s e g m e n t a t i o n 方法用于时间序列的线性拟合1 8 图2 - 3 数据序列压缩后选取的重要点1 9 图2 - 4 重要点样例1 9 图2 - 5 数据序列的四种基本变化模式2 1 图2 - 6 三点关系示意图2 1 图2 7 相邻三点关系示意图2 3 图2 8 渐变序列的序列拟合效果2 4 图2 - 9 单调突变序列的序列拟合效果2 4 图2 一l oi k p 算法的划分效果2 8 图2 - 1 l 测井数据的划分效果比较2 9 图2 - 1 2 三种序列分段算法拟合效果3 l 图3 - i 层次聚类3 6 图3 - 2 曲线的三种表现形式3 9 图3 - 3s f - l is t 结构4 2 图3 4o s h c 与s w 的性能比较4 6 图3 - 5o s h c 与t d 的性能比较4 7 图3 - 6s w 与o s h c 划分比较4 7 图4 一l 时间序列层次聚类样例5 l 图4 - 2c y l i n d e r - b e l l f u n n e l 时间序列5 2 图4 3 时间序列的欧氏距离度量5 2 图4 - 4 时间序列动态时间弯曲距离5 4 图4 5 时间序列的动态时间弯曲距离度量5 6 图4 6 序列q 和s 的累积距离5 7 图4 7 两条相似序列的备点对应关系6 0 图4 8d t w 和k e y d t w 的弯曲路径比较6 1 图表目录 图4 - 9 子序列查询6 3 图5 - 1t e m f p 树中的叶结点结构7 0 图5 - 2 例5 1 中的t e m f p - t r e e 7 2 图5 - 3 例5 2 的图形表示7 3 图5 4t e m f p 算法数据可扩展性7 6 图5 - 5t e m p f p 算法运行时间与阈值三的关系7 7 图5 - 6 查询( 1 ) 和查询( 2 ) 的运行时问比较7 7 图5 7 内存使用量比较7 8 图6 1 测并数据样例8 0 图6 - 2 测井数据划分效果8 2 图6 - 3s w 与0 s h c 划分效果比较8 3 图6 - 4 关键点序列分段算法对测井数据序列拟合效果8 5 图6 - 5 三种序列分段算法拟合效果8 6 图6 - 6 岩石热解曲线的相似性度量8 8 图6 - 7 气相色谱曲线的相似性度量8 8 表2 1i k p 算法实现框架，。2 5 表2 2k p s e g m c n t a t i o n 算法实现框架2 6 表2 3 实验数据信息2 7 表2 4 三种序列分段算法的压缩率比较3 0 表4 1i s s k 算法实现框架5 9 表4 2 k e y d t w 算法实现框架6 0 表4 3 查询性能比较6 2 表5 - 1 时态数据库样例7 1 表5 - 2 例5 2 的查询模式及输出7 3 表6 - 1 三种序列分段算法的压缩率比较8 5 d m ： k d d ： t s d m ： d f t ： d w t ： s v d ： t a h ： p l r ： p a a ： l c s ： d t w ： l b ： f p t r e e i k p ： s w ： t d ： b u ： c f ： o s h c ： s f l i s t ： s f ： i s s k ： k e y d t w ： t d m ： t e m f p ： t m p f p t r e e ： d b + 一t r e e ： 缩写说明 d a t am i n i n g ，数据挖掘 k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，数据库中知识发现 t i m es e r i e sd a t am i n i n g ，时间序列数据挖掘 d i s c r e t ef o u r i e rt r a n s f o r m ，离散傅立叶变换 d i s c r e t ew a v e l e tt r a n s f o r m ，离散小波变换 s i n g u l a rv a l u ed e c o m p o s i t i o n ，奇异值分解 t y p ea b s t r a e t i o nh i e r a r c h y ，类型抽象层次 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 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 ，分段聚集近似 l o n g e s tc o m m o ns u b s e q u e n c e ，最长公共子串 d y n a m i ct i m ew a r p i n g ，动态时间弯曲 l o w e rb o u n d i n g ，下界 f r e q u e n tp a t t e r nt r e e ，频繁模式树 i d e n t i f y i n gk e yp o i n t s ，关键转折点选择 s l i d i n gw i n d o w ，滑动窗口技术 t o p d o w n ，自顶向下 b o t t o m u p ，自底向上 c l u s t e r i n gf e a t u r e ，聚类特征 a no n l i n es e g m e n t a t i o na l g o r i t h mf o rt i m es e r i e sb a s e do n h i e r a r c h i c a lc l u s t e r i n g ，基于层次聚类的时间序列在线分割算法 s e g m e n t a t i o nf e a t u r el i s t ，划分特征链表 s e g m e n t a t i o nf e a t u r e ，划分特征 i d e n t i f ys i m i l a rs e q u e n c e sb a s e do nk e yp o i n t s ，基于关键点序列的 相似性查询算法 k e y p o i n td y n a m i ct i m ew a r p i n g ，关键点动态时间弯曲 t e m p o r a ld a t am i n i n g ，时态数据挖掘 t e m p o r a lf r e q u e n tp a t t e r nm i n i n g ，时态频繁模式挖掘 t e m p o r a lf r e q u e n tp a t t e r nt r e e ，时态频繁项目树 d o u b l eb + t r e e ，双树结构 中国科学技术大学学位学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究 工作所取得的成果。除已特别加以标注和致谢的地方外，论文中 不包含任何他人已经发表或撰写过的研究成果。与我一同工作的 同志对本研究所做的贡献均已在论文中作了明确的说明。 。 本人授权中国科学技术大学拥有学位论文的部分使用权， 即：学校有权按有关规定向国家有关部门或机构送交论文的复 印件和电子版，允许论文被查阅或借阅，可以将学位论文编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：盖垒塞 聊7 年岁月日 1 1 概述 第一章绪论 随着计算机的日益普及，大容量存储技术的发展以及多种数据获取技术的广 泛应用，在金融1 1 ，2 ，3 1 、生物医药 4 , 5 1 、地质【6 1 、太空探澳, j l t , s 】、网络管理【9 1 等诸多 科学工业领域中产生和积累了大量以时间序列形式存在的各类数据。如金融证券 市场中股票价格的波动；石油工业生产领域中某一口井在某个深度的录井读数； 商业领域中超市销售数据库中保存的每种商品每天的销售数量和金额；以及在生 物医学中，某一症状病入在每个时刻的心跳变化等等。这些数据与时问密不可分 且是有序的，因此构成了时间序列数据库。 一般来说，时间序列( t i m es e r i e s ) 泛指那些随时间或空间有序变化的数据 集合，这些数据记录集合往往采用等时间或空间间隔进行度量。如何充分有效地 管理和利用这些海量数据序列，更有效地发现和理解这些数据序列背后隐含的规 律和知识，已经受到越来越多数据挖掘研究者广泛关注时间序列数据挖掘 ( t i m es e r i e sd a t am i n i n g ，简称t s d m ) 由此应运而生，并成为数据挖掘领域 中一个重要研究方向l l o , t h 。 f i g l 1e x a m p l e so f t i m es e r i e s 图卜l 时闻序列样例 传统的时间序列分析方法作为概率统计学科的一个课题，主要集中于时间序 列数据的建模、滤波和预测等方面。经过几十年的发展，取得了许多重要成果， 在实际应用中发挥了重要作用。传统的时闻序列分析方法往往是先提出假设再进 行验证，其目的是实现对系统整体行为的把握和预测。但在实际生活和工作中逐 渐提出了一些新需求：在实际的时间序列分析过程中需要对时间序列局部特征进 行分析；发现不同数据源在相同时间区间内或者相同数据源在不同时间区间中的 相似性和差异性，从中提取关联规则，发现知识：在线监控不断变化的时间序列 是否在某一时刻发生异常；为用户提供个性化的更容易理解的关于时间序列形 态的形象化描述信息。传统的时间序列分析技术对数据库应用领域( 如数据仓库 以及知识发现等) 提出的新需求开始显得力不从心。因此从二十世纪九十年代早 期开始，时问序列数据挖掘作为一个新的研究方向出现，并成为数据挖掘领域的 一个重要分支时间序列挖掘是针对时间序列的模式发现过程，旨在研究隐含在 时间序列中更深层次的知识，包括时间序列的拟合、时阃序列的相似性查询、时 序模式挖掘、时问序列的异常检测等研究内容。 1 2 研究历史与现状 时间序列数据挖掘的目的就是从时间序列中检测出用户感兴趣的模式，这些 模式可以帮助人们更好地认识时间序列中蕴含的规律，加深人们对系统或者现象 的理解【5 】。时间序列数据挖掘的许多技术来源于传统时间序列分析的理论与技 术。两者的研究对象与目的也基本相似，即发现时间序列数据中蕴含的规律。所 不同的是时间序列数据挖掘更加关注海量时同序列的处理技术且更加强调时回 序列的形态特征，通常用形态特征来刻画时问序列中蕴含的规律，而传统时间序 列分析技术通常用解析函数或者统计量刻画时同序列中蕴含的规律。 综合收集到的关于时间序列数据挖掘的文献资料，时间序列数据挖掘的研究 任务主要为u 1 ： 对闯序列的拟合；由于对闯序列的数据量庞大且数据类型及为复杂，直接 在原始时间序列上进行数据挖掘不但效率低下，而且往往难以获得满意的 结果。时间序列的拟合表示方法是对时间序列进行抽象和概括的特征表示 方法，是在更高层次上对时间序列的重新描述。时间序列的拟合表示不但 能够对时间序列数据进行压缩，而且突出了时问序列的模式变化特征。 对闻序列的划分；给定一个包含n 个时问点的时间序列q ，构建一个模型， 将q 分为k 个部分( k 近似表示q 。分割有两个主要的应用，可以用 于检测生成时间序列的系统发生的变化，即变化点检测；也可以用于创建 时自j 序列的高级表示以便索引、聚类和分类。 时间序列的相似性( 不相似性) 查询：给定一个时间查询序列q 以及某个 相似性，不相似性度量d ( q ，c ) ，发现时问序列数据库d b 中与q 最匹配的 那些时间序列。判断两个时间序列的相似程度需要一个测量时间序列相似 性的距离度量方法目前时间序列数据挖掘中用到的距离度量大致可以分 为两大类：欧几里德距离和非欧几里德距离。 2 第一章绪论 时间序列的模式挖掘：模式挖掘是时间序列数据挖掘的重要研究内容之 一，近年来相关研究成果不断涌现。针对不同的应用目的，人们试图从时 间序列数据库中发现的模式也各不相同，如特定模式、频繁模式、周期模 式、异常模式等。 时间序列的可视化：时间序列可视化是时间序列数据挖掘中一个应用前景 广阔的研究方向。一般来说，人们比较难于理解复杂的时间序列数据，而 形象化了的数据则非常容易理解。因此有关这方面的研究近几年来也逐渐 被时间序列数据挖掘研究领域的研究者们关注【1 2 以4 1 。 时间序列的应用研究：时间序列数据广泛存在于现实世界的各个领域，因 此时间序列数据挖掘的应用领域十分广泛。典型的应用包括；机电系统诊断 t s a 6 、生物信息学1 7 郴1 、运动图像分析 2 0 , 2 1 】、生产过程监测 2 2 , 2 3 1 、基于 规则的时间序列预报【2 4 】以及时间序列概括2 5 1 等。 以下重点介绍时间序列的模式表示、时间序列的相似性度量、时态模式挖掘、 时间序列挖掘的应用研究四方面的研究工作。 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 t ) 、k l ( k a r h u n e e t l o e v e ) 变换或者离散小波变换( d i s c r e t ew a v e l e t t r a n s f o r m ，简称d w t ) 将时间序列从时间域映射至频率域，用频谱来表示原始 3 时问序列挖掘相关算法研究及应用 时间序列r 6 , 2 7 l 。通过频域变换有效解决了高维特征向量的降维问题d f t 方法计 算方便快捷，在变换过程中保证了特征抽取的完整性。利用较少的几个频率实现 原始序列的近似表示，保持序列主要形态的同时实现了数据压缩。d w t 方法利 用少数小波参数近似模拟原始时间序列实现线性变换。 ( 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 ) 是一种常见的降维 方法。在时间序列的模式表示中，s v d 通过对整个时间序列数摆库的整体表示 实现对整个时间序列数据库的特征提取和压缩。尽管s v d 线性变换方法在数据 重构上误差最小，但其时间复杂度较高( o ( m n 2 ) ) ，这里m 为时问序列数据库的 大小，n 是时间序列的平均长度。当增量加入时间序列数据或删除已有部分数据 时，s v d 方法需要重新计算，计算开销较大。 ( 3 ) 符号化表示 时间序列的符号化表示就是通过一些离散化方法将时间序列的连续实数值 或者一段时间内的时间序列波形映射到有限的符号表上，将时间序列转换为有限 符号的有序集合。许多相关文献对时阃序歹 j 符号化表示方法展开了研究：文献 2 8 】 利用滑动窗口技术实现对子序列的聚类。文献f 2 9 将时间序列相邻点的变化率符 号化；文献 3 0 】对时间序列数据采用等间隔和最大嫡方法实现符号化；文献【3 1 】 提出了基于云模型的符号化方法。b e t t y 等人利用区间离散化方法实现了时间序 列的符号表示口2 1 。文献 3 3 】通过类型抽象层次( t y p ea b s t r a c t i o nh i e r a r c h y ，简 称t a h ) 模型实现符号化。 符号化表示的优点在于可以利用许多字符串研究领域的成果，缺点在于如何 选择合适的离散化算法，解释符号的意义，以及定义符号之间的相似性度量。 ( 4 ) 分段线性表示 文献【3 4 】首次提出了时间序列的分段线性表示( p i e c e w i s el i n e a r r e p r e s e n t a t i o n ，简称p l r ) 思想，是时间序列的模式表示方法中研究最早和最 多的方法之一。p l r 是指用k 条首尾相邻的一系列线段来近似表示一条长度为n 的时间序列。 在时间序列的p l r 表示中，线段的数目决定了对原始序列的近似粒度。线 段越多，线段的平均长度就越短。反映了时问序列的短期波动情况：线段越少， 线段的平均长度就越长，反映了时间序列的中长期趋势。 这种线性建立的表示方法易于理解和实现，具有转换速度快、无漏报和距离 度量灵活等优点文献 3 5 ，3 6 提出的时间序列分段聚集近似( p i e e e w i s e a g g r e g a t e a p p r o x i m a t i o n ，简称p a a ) 方法将时间序列等宽度划分，每个子段用时间序列 4 第一章绪论 在该子段上的平均值来表示。p a r k 等人l 】7 】提出单调变化的分段算法。通过依次 计算序列数据的单调变化对时间序列进行分段。p e n g 等人哪j 提出的界标模型 ( l a n d m a r km o d e l ) 通过最小距离和百分比原则选择部分界标点作为时间序列的 分段点。p r a t t 和f r i n k i 3 9 l 将重要点作为时间