（计算机软件与理论专业论文）时间序列相似搜索方法的研究.pdf

时间序列相似搜索方法的研究摘要 时间序列相似搜索的研究 专业：计算机软件与理论 硕士生：涂宇 指导老师：刘玉葆副教授 摘要 时间序列数据泛指随时问或空间有序变化的数据，这些数据往往采用等时间 或等空间间隔测量。时间序列数据广泛应用于商业、经济、地质、生物医药、太 空探测等诸多科学工业领域中。如何充分有效地管理和利用这些时间序列数据， 从中发现隐藏的规律和知识，受到广泛关注。由于时间序列数据具有高维性、噪 声干扰及波动性等特点，因此时间序列数据挖掘成为数据挖掘中的一个重要研究 方向。 时间序列数据挖掘大体可以分为时间序列表示和挖掘两个阶段。时间序列表 示是提取时间序列的主要特征，在更高层次上对时间序列重新描述。挖掘是指对 表示后的时间序列做进一步的数据挖掘工作。本文主要在时间序列表示和相似搜 索方面做了相关研究。本文主要工作为如下几个方面： 1 时间序列的表示是时间序列数据挖掘研究的基础。重要点的分段表示法 ( i p ) 是目前应用最为广泛的时间序列特征提取方法之一，具有较好的数据压缩和 去除噪声能力，但参数的选择对时间序列的近似效果有很大的影响。基于多分辨 率的重要点检索分段方法( m i p ) 也是一种时间序列特征提取方法，该方法能很好 的近似时间序列，但运行效率比较低。为了改进以上两种方法的不足，我们提出 了一种改进的序列分段的方法：基于重要点的多分辨率检索表示法。针对时间序 列的b e n c h m a r k 做了大量的实验，从误差，压缩率、效率等方面来衡量本文方法 和前面两种方法。实验表明，与基于重要点的分段方法相比，m r i p 方法能对时 间序列进行更好的压缩，误差更小，有更好的近似效果；与基于多分辨率的重要 点检索分段方法相比，在近似效果相当的情况下，运算效率更高。 2 基于b i r c h 聚类特征及凝聚层次聚类的思想和时间序列数据相邻的点有 内在的依赖关系，本文提出了基于聚类特征的时间序列划分算法( s e g m e n t a t i o n a l g o r i t h mf o rt i m es e r i e sb a s e do nb i r c hc l u s t e r i n g ，简称s b c ) 。对时间序列的 l 时间序列相似搜索方法的研究摘要 b e n c h m a r k 做了相关划分实验，并和经典的s w 划分算法进行实验对比。通过实 验结果分析，本文划分方法能达到很好的划分性能。 3 采用基于重要点的多分辨率检索表示法提取特征模式后，对提取的模式 序列提出了基于斜率模式的动态时间弯曲距离度量( s l o p e。采用基于dtw) b i r c h 聚类特征的时间序列划分算法提取特征模式后，对提取的模式序列介绍了 基于均值模式的动态时间弯曲距离度量( m e a n 实验，本文提出和介绍的距离度量有很好的过滤性能。与全序列d t w 搜索相比， 只对极少量满足过滤条件的序列与待搜索序列进行全序列d t w 距离计算，在时 间性能上有很大的提高。 关键字：数据挖掘时间序列划分算法相似搜索 时间序列相似搜索方法的研究 a b s t r a c t r e s e a r c ho n s i m i l a r i t ys e a r c h i n g i nt i m e s e r i e sd a t a b a s e 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 ：砌翰 s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rl i uy u b a o a bs t r a c t at i m es e r i e sr e f e r st oad 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 da n d i n t e r v a li nt i m eo rs p a c e ，w h i c hi s w i d e l ye m p l o y e di nc o m m e r c i a l ，e c o n o m i c ， g e o l o g y , b i o - m e d i c i n e ，s p a c ee x p l o r a t i o na n dm a n yo t h e rs c i e n t i f i c a n di n d u s t r i a l f i e l d s h 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 e c t i v e l ya n dh o wt od i s c o v e r h i d d e nr u l e sa n dk n o w l e d g ef r o mt h e mi sa ni n t e r e s t i n gp r o b l e mb u t ，t i m es e r i e sd a t a u s u a l l yh 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 o l a t i l i t y t h e r e f o r e ，t i m es e r i e sd a t a m i n i n gi so n eo f t 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 f d a t am i n i n g t i m es e r i e sd a t a m i n i n g c a nh ed i v i d e di n t ot w os t a g e s ，t i m es e r i e s r e p r e s e n t a t i o na n dm i n i n g t h ef i r s ts t a g e ，t i m e s e r i e sr e p r e s e n t a t i o n , r e f e r st o e x t r a c t i o nt h em a i nf e a t u r e sa n dah i g hl e v e lf e a t u r ed e s c r i p t i o no ft i m es e r i e s a n d t h es e c o n ds t a g e ，m i n i n g ，i ss i m i l a rt ot h et r a d i t i o n a ld a t am i n i n g t i m es e r i e s r e p r e s e n t a t i o na n ds i m i l a rs e a r c ha r es t u d i e di n t h i sp a p e r s e v e r a la s p e c t so ft h i s p a p e ra r ea sf o l l o w s ： 1 t i m es e r i e sd a t ar e p r e s e n t a t i o ni so n eo fi m p o r t a n tp r o b l e m so ft i m es e r i e s d a t am i n i n g 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 nb a s e do ni m p o r t a n tp o i n t ( i p ) i so n eo f t h em o s tw i d e l ye m p l o y e dm e t h o d so ff e a t u r ee x t r a c t i o nf o rt i m es e r i e s t h i sm e t h o d c a nc o m p r e s st i m es e r i e sm u c ha n dr e m o v en o i s e si nt i m es e r i e s h o w e v e r , t h ec h o i c e o ft h ep a r a m e t e rh a sg r e a te f f e c to nt h er e s u l to fa p p r o x i m a t i o nf o rt i m es e r i e s m u l t i r e s o l u t i o ni m p o r t a n tp o i n tr e t r i e v a lm e t h o d ( m i p ) i sa n o t h e rm e t h o do ff e a t u r e e x t r a c t i o nf o rt i m es e r i e s t h i sm e t h o dp e r f o r m sw e l li nt h er e s u l to fa p p r o x i m a t i o n f o rt i m es e r i e s ，b u tt h es p e e di sl o w i no r d e rt oi m p r o v et h es h o r t c o m i n g so ft h e a b o v et w om e t h o d s ，an o v e lm u l t i r e s o l u t i o nr e t r i e v a lm e t h o db a s e do ni m p o r t a n t i i i 时间序列相似搜索方法的研究a b s i r ra c t p o i n t ( m r i p ) f o rt i m es e r i e sr e p r e s e n t a t i o ni sp r o p o s e di n t h i sp a p e r c o m p a r e d w i t hi p , t h en e wm e t h o dc a na p p r o x i m a t et or a wt i m es e r i e sm o r ep r e c i s e l y , c o m p r e s s t i m es e r i e sm o r ev a l i d l y , a n dr e m o v en o i s e sm o r ee f f e c t i v e l y c o m p a r e dw i t hm i p , t h e n e wm e t h o di sh i g h e ri ns p e e da n dh a sa l m o s tn od e g r a d e di na p p r o x i m a t i o nf o rt i m e s e r i e s e x p e r i m e n tr e s u l t so nt i m es e r i e sb e n c h m a r kp r o v et h ee f f i c i e n c y 2 t h e r ei si n h e r e n t l yd e p e n d e n c ea m o n ga d j a c e n tp o i n t so ft i m es e r i e sd a t a b a s e do nb i r c hc l u s t e r i n gf e a t u r e sa n da g g l o m e r a t i v eh 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 na l g o r i t h mf o rt i m es e r i e sb a s e do nb i r c hc l u s t e r i n g ( s b c ) i sp r o p o s e d i n t h i sp a p e r c o m p a r e dw i t ht h ec l a s s i cs w , e x p e r i m e n tr e s u l t so nt i m es e r i e s b e n c h m a r kp r o v e dt h a tt h em e t h o di nt h i sp a p e rc a na c h i e v eg o o dp e r f o r m a n c e 3 an e wd i s t a n c em e a s u r ec a l l e ds l o p e p a t t e r nd y n a m i ct i m ew a r p i n gd i s t a n c e ( s l o p e - d t b oi sd e f i n e d t h i sm e t h o dc o m p u t e r sw a r p 啦d i s t a n c eu s i n ge x t r a c t i n g f e a t u r e sb ym r i p a l s oo t h e rd i s t a n c em e a s u r ec a l l e dm e a n - p a t t e r nd y n a m i ct i m e w a r p d i s t a n c e ( m e a n - d t w ) i si n t r o d u c e d t h i sm e t h o dc o m p u t e r sw a r p 吨 d i s t a n c eu s i n ge x t r a c t i n gf e a t u r e sb ys b c e x p e r i m e n tr e s u l t so fs i m i l a rs e a r c hs h o w s l o p e - d t wa n dm e a n - d t wh a v eag o o df i l t e rp e r f o r m a n c e c o n s e q u e n t l y , t h et w o m e t h o d sm e n t i o n e da b o v eo n l yc o m p u t e r st h ed t wd i s t a n c eb e t w e e nt h et i m es e r i e s d a t at ob ef m da n dav e r ys m a l ln u m b e ro ft i m es e r i e sd a t at h a tm e e t st h ec o n d i t i o no f f i l t e r c o m p a r e dw i t hc o m p u t e rt h ed t wd i s t a n c eb e t w e e n t h et i m es e r i e sd a t at ob e f e n da n da ut h et i m es e r i e sd a t a , t h et i m ep e r f o r m a n c eo fs l o p e d t wa n dm e a n - d t w i sg r e a t l yi m p r o v e d k e yw o r d s ：d a t am i n i n g ，t i m es e r i e s ，s e g m e n t a t i o na l g o r i t h m , s i m i l a rs e a r c h i v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：洽、当 日期：知i o 年6 月2 日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：涂字 日期：沙f 啤6 月多日 导师签名： 夏。h 百 日期：伽i 口年月乙日 时间序列相似搜索方法的研究第1 章绪论 第1 章绪论 随着计算机技术的飞速发展，使得金融经济、工农业生产、科学实验和人类 生活的各个领域都积累了大量数据。面对快速增长的海量数据，传统的数理统计 和数据管理工具已经不能满足需求。因而需要功能强大和高效的分析工具，从海 量数据中发现隐藏在这些数据背后的知识，提高信息的利用率。正是在这一背景 下，数据挖掘技术应运而生，并逐渐在各行各业的决策支持中发挥越来越重要的 作用。 1 1 数据挖掘的产生与发展 数据挖掘( d a t am i n i n g ，d m ) “1 是知识发现过程的一个步骤，然而在产业界、 媒体和数据库研究界，术语数据挖掘比长术语从数据库中发现知识更流行。因此 一般采用数据挖掘功能的广义观点，即是指从存放在数据库、数据仓库或其他信 息库中的大量数据中挖掘有趣知识的过程。整个数据挖掘过程如图1 1 所示嘲。 1 1 1 数据挖掘的一般过程 1 需求分析 对不同应用领域的数据进行挖掘，需要预先准备相关的知识，了解用户的最 终需求。一般包括关联规则发现、相似搜索、数据分类、聚类、离群点分析等。 把用户需求和领域知识结合起来，使挖掘具有一定的预见性，这样既可以减少工 作量，又能使挖掘工作更有目的和成效。 2 数据预处理 数据挖掘处理的对象一般是存储在数据库系统中的大量数据，通常不能直接 进行数据挖掘，需要对数据进行预处理n 3 。一般包括数据清理( 处理不一致数据 以及消除噪声) ，数据集成( 把多种不同数据源组合在一起) ，数据选择( 选择与分 析任务相关的数据) ，数据变换( 通过汇总或聚集等操作将数据变换成适合挖掘的 形式) 。充分合理做好数据预处理相关工作，能提高有效挖掘的准确性。 3 数据挖掘 时间序列相似搜索方法的研究第l 章绪论 根据数据挖掘的任务，选择合适的模型和参数，确定相应的数据挖掘算法( 如 统计分析，模式识别，机器学习，支持向量机等) ，对预处理的数据进行相关挖 掘工作。 4 评估模式 由数据挖掘得到的模式可能没有使用价值，也可能没有实际意义或者不能准 确反映真实信息，因此需要根据某种兴趣度度量，识别真j 下有实际价值的模式。 5 知识表示 为了便于用户容易理解和使用挖掘得到的结果，需要尽量直观地呈现挖掘结 果，一般采用可视化和知识表示等方法表示。 图1 1 数据挖掘的全过程 1 1 2 数据挖掘对象及功能 1 数据挖掘对象 原则上讲，可以对任何类型的信息存储库以及瞬态数据进行数据挖掘工作。 2 时间序列相似搜索方法的研究第1 章绪论 一般来说，数据挖掘主要对象有结构化数据，半结构化数据及非结构化数据，包 括关系数据库、事务数据库、数据仓库、文本数据库、多媒体数据库、时间序列 数据库、空间数据库等。 2 数据挖掘功能 数据挖掘功能用于指定数据挖掘任务要找的模式类型。数据挖掘任务一般 可以分为两类：描述和预测。描述性挖掘任务是刻画数据库中数据的一般性质； 预测性挖掘任务是对当前数据进行推断，以做出预测。数据挖掘的任务具体可分 为：概念类描述、挖掘频繁模式、分类和预测、聚类分析、孤立点分析和演变 分析等。 1 2 时间序列数据挖掘 时间序列数据泛指随时间或空间有序变化的数据，这些数据往往采用等时间 或等空间间隔测量。时间序列数据广泛应用于商业、经济、地质、生物医药、太 空探测等诸多科学工业领域中。如气象预报研究中，每天气温与气压的读数；金 融证券市场中，股票价格的变化；生物医学中，病人的心电图；企业电力系统运 行中，电力的消耗等。 1 2 1 研究背景及意义 与传统数据相比，时间序列数据具有高维性、海量性和复杂性等特点，因此 时间序列数据挖掘有别于传统的数据挖掘。 高维性：时间序列数据的长度( 即维数) 一般都在几十以上，特殊情况下甚 至成千上万。随着数据维数升高，高维索引结构的搜索性能急剧下降，即产生“维 灾问题( c u r s eo f d i m e n s i o n a l i t y ) 川3 圳。采用传统的数据挖掘方法不能很好的解决 时间序列数据的维度灾害问题，因此如何提取时间序列的特征，降低数据的维数 在更高层次上对时间序列重新描述，成为时间序列数据挖掘的重要前提工作，是 时间序列数据挖掘工作的重中之重。 海量性：时间序列数据是连续并且不断变化的，一般的时间序列数据库数据 规模都非常大。由于大量遥感勘测装置、传感器以及其他联机工具的广泛使用， 时间序列数据库迅速增长，通常以每分钟数亿字节的数量级增长甚至更快。如何 时间序列相似搜索方法的研究第1 章绪论 有效，快速甚至实时地分析数量级如此巨大的时间序列数据，发现隐藏在这些海 量数据背后的知识，对时间序列数据挖掘来说是个巨大的挑战。 复杂性：由于时间序列数据来源于生活中的各个领域，采样和测量不同时间 序列数据源标准不统一，并且由于时间序列数据是连续的，使挖掘方法受到限制。 此外时间序列存在振幅伸缩平移，时间轴伸缩和弯曲等各种变形瞄1 ，这些问题使 得时间序列相似性定义、相似性度量、索引建立和相似搜索都非常困难。 综合收集到的有关时间序列数据挖掘的文献资料，时间序列数据挖掘的研究 内容主要包括时间序列的表示朋、相似性度量及搜索旧1 、预测n 司、分类n 、 聚类n 8 1 们、异常点检测瞳删1 及可视化嘶，2 础等。 最近几年，时间序列数据挖掘受到越来越多学者的关注，并取得了蓬勃的发 展，同时也存在很多不足。k e o g h 等人选取了5 7 篇引用较多的论文，并用5 0 个 真实的数据集将这些论文中的方法进行实验例，得出如下结论：用不同类型的数 据集进行测试，这些算法的性能明显下降。这一结论表明，这些算法可能仅对某 种时间序列类型有效，缺乏普遍有效性。这说明时间序列数据挖掘的复杂性。如 何有效的对时间序列数据进行数据挖掘是一个十分有研究意义的课题，也是本文 研究的重点。 1 2 2 时间序列的表示 时间序列数据具有高维性、海量性、复杂性和噪声干扰等特点，直接在原 始序列上进行数据挖掘工作不但难度比较大，在计算和存储上要付出很高的代 价，而且影响算法的准确性和可靠性。因此在不影响挖掘准确性和可靠性的前提 下，尽可能的减少计算和存储的代价。利用时间序列的表示方法提取时间序列的 主要特征，将时间序列变换到低维特征空间，对时间序列维数约简，在更高层次 上对时间序列的重新描述是一种有效的方法。时间序列的表示能够对时间序列数 据进行有效压缩，突出时间序列的模式变化特征，更有利于时间序列数据挖掘。 此外，时间序列表示也是相似性度量、相似搜索、异常点检测、分类及聚类的基 础。因此，时间序列表示是时间序列数据挖掘工作的一个重要问题。 国内外学者提出了多种时间序列表示方法1 。时间序列常用的表示方法有频 域表示法( d f t 忉和d w t 嗍) 、分段线性表示( p l a 嘲、p a a n 0 1 和a p c a n 0 - 1 ) 、 4 时间序列相似搜索方法的研究第1 章绪论 奇异值分解法( s v d 1 0 1 ) 和符号化方法n 妇等。 1 频域表示 频域表示的基本思路是采用诸于d f t 或d w t 等方法将时间序列从时间域 映射到频率域，用频谱来表示原始的时间序列。这种方法能有效压缩时间序列， 对其进行降维。对于大部分时间序列来说，能量主要集中在几个主要的频率上， 因此可以用很少的几个频率来近似表示原始时间序列，达到数据压缩的目的，而 且能够较好地保持时间序列的主要形态。 2 分段线性表示 分段线性表示采用首尾相邻的一系列线段近似表示时间序列，是种比较直 观的表示方法，具有较高数据压缩能力，可以根据实际需求获得时间序列数据不 同精度的近似表示。 利用线段来近似表示时间序列的思想最早可追溯到文献 9 ，文中指出分段 线性表示不仅能对数据起压缩的作用，而且能对时间序列进行不同精度的近似表 示。时间序列p l r 表示法是用k 条首位相接的线段来近似原始时间序列，线段 的数目决定了对原始时间序列的压缩能力。线段越多，线段平均长度就越短，压 缩率越低，反应时间序列的短期波动情况；线段越小，线段平均长度就越长，压 缩率越高，反应时间序列的中长期趋势。时间序列的p l r 表示简单直观，易于 理解和实现，距离度量灵活，是一种很好的模式表示方法汹啪1 。时间序列的p a a 方法对时间序列进行等间隔划分，用该段的平均值表示每个子段。p r a t t 和f i n k 提出基于重要点的分段方法，该方法采用极值点近似表示原始时间序列b 引。 3 奇异值分解表示 奇异值分解法是对时间序列数据库的整体进行特征提取和压缩。s v d 误差 小，但其时间复杂度较高，计算开销大。 4 符号化方法表示 符号化方法表示n 町就是通过一些离散化方法将时间序列映射到有限的符号 表上，将时间序列转换为有限符号的有序集合。符号化表示的优点是能利用许多 字符串现有的研究成果，缺点在于怎样选择合适的离散化算法，怎样合理解释符 号蕴含的意思，以及如何定义符号之间的相似性度量。 许多相关文献对时间序列符号化表示方法展开了研究：文献 3 4 对时间序列 时闻序列相似搜索方法的研究第1 章绪论 数据利用等间隔和最大熵方法实现符号化表示：b e t t y 等人采用区间离散化方法 实现对时间序列的符号化表示嗌1 ；e a m o n nk e o g h 等人采用等间隔划分时间序列， 采用均值表示每个分段实现对时间序列符号化表示。 时间序列的表示都会丢失部分信息，无论采用哪种方法，都难以避免这种问 题，关键是如何权衡划分结果的准确性与划分算法的效率。s v d 和p l a 表示法， 这些方法都能够保证误差尽可能小，但时问复杂性比较高。而p a a 、a p c a 和基 于重要点的分段方法，效率比较高。其中，p r a t t 和f i n k 提出的基于重要点的分 段方法有一定的优势，可以通过设置不同的参数，达到控制分段精度和误差的目 的，且其时间复杂性比较低，是目前主要采用的方法。 1 2 3 相似性度量及搜索 时间序列的相似性度量研究是时间序列数据挖掘分类、聚类及异常点检测等 的基础。一般两条时间序列之间的“相似”通过距离函数来衡量，距离越近越相 似，反之则越不相似。时间序列的相似性度量应当尽量支持时间序列的振幅伸缩 和平移、时间轴伸缩和弯曲等各种形变。相似序列搜索是在相似性度量的基础上 进行的。相似序列搜索通常是指从时间序列数据库中找出与给定时间序列满足某 种相似性度量的序列。 1 2 。3 1 相似性度量 时间序列相似性度量主要有：欧氏距离洲8 1 、动态时间弯曲距离口9 删和编辑 距离h 1 4 2 1 等，其中欧氏距离直观简单，计算量小，时间复杂度低，支持各种索引 方法，但不支持时间序列的各种形变；动态时间弯曲距离是目前相似性度量中的 研究热点，该距离度量支持时间序列的时间轴弯曲，但其计算量大，时间复杂性 高；编辑距离支持时间轴的伸缩，但其计算复杂性高且不易理解。 1 欧氏距离 欧氏距离( e u c l i d e a nd i s t a n c e ) 啪侧是时间序列相似性研究中广泛采用的相似 性度量。欧氏距离的优点是直观简单，计算量小，满足距离三角不等式，支持多 维空间索引；缺点是不支持噪声及时间序列的各种形变。 欧几里德距离的一些改进可以支持时间序列的振幅伸缩和平移，但是仍然不 支持时间轴的伸缩和弯曲h 引。 6 时间序列相似搜索方法的研究第1 章绪论 2 动态时间弯曲距离 动态时间弯曲距离( d y n a m i ct i m ew a r p i n gd i s t a n c e ，d t w ) 油一们广泛用于语音 识别领域。为了消除欧几里德距离的缺陷，支持时间序列的时间轴伸缩，使得相 似波形的时间序列能够在时间轴上对齐匹配，b e m d t 和c l i f f o r d 将动态时间弯曲 距离弓l 入到时间序列的相似性研究中n 引。该方法的基本思想是根据最小代价的时 间弯曲路径进行对齐匹配，计算两个序列之间的距离。 动态时间弯曲距离优点是支持时间轴上的伸缩和弯曲，并能计算不同长度的 时间序列间的距离；缺点是计算代价大时间复杂度高，不适合直接对时间序列进 行数据挖掘，因此限制了d t w 距离的广泛使用。 为了克服动态时间弯曲距离时间复杂度高的缺点，许多学者提出了d t w 距 离的下冕( l o w e rb o u n d i n g ，l b ) 距离。通过l b 距离快速过滤掉不满足要求的时 间序列，再对剩下的时问序列与待搜索序列计算d t w 距离h 3 。由于l b 距离 的计算比d t w 距离快的多，且满足距离下界，因此采用l b 距离能够显著提高 相似性搜索效率，并能保证搜索的完备性。 3 编辑距离 编辑距离( e d i t i n gd i s t a n c e ) 是度量一个模式近似出现的标准。编辑距离主要 用于度量字符串之间的相似性。 编辑距离的优点是支持时间轴上的伸缩，缺点是计算复杂性高且不易理解。 以上介绍的几种相似性度量方法是在时间域上判断序列相似的简单方法，但 是通常为了降低时间序列的维数，通过变换将时间序列映射到特征域，在不同的 特征域上又给出不同的相似性度量。 1 2 3 2 时间序列相似性序列搜索 相似序列搜索通常定义为：从时间序列数据库中找出与给定时间序列满足某 种相似性度量的序列。相似性搜索一般分为两类：全序列搜索和子序列搜索。由 于时间序列自身数值的波动性与连续性，造成了时间序列相似性搜索特有的问 题。 首先，怎样定义相似性。相似性依赖于目前分析的任务、人的主观意识以及 时间序列数据本身，给时间序列相似性定义带来一定困难。时间序列相似性一般 采用诸于欧氏距离，动态时间弯曲距离等相似性度量来衡量。 7 时间序列相似搜索方法的研究 第1 章绪论 其次，怎样提高搜索效率。时间序列数据量庞大并且一般是流式序列，对原 始时间序列直接进行相似搜索复杂度很高并且效率低下。这就需要对时间序列进 行预处理并建立有效的索引机制来提高搜索效率。 再次，怎样衡量搜索的结果。搜索完备性是衡量搜索结果的标准之一。搜索 完备性包括：搜索准确性及完全性。设t 是时间序列库中与待搜索序列满足相 似性度量的时间序列集，r 是实际搜索到的时间序列集。若r 是t 的子集，则 搜索不满足完全性，t - r 表示遗漏的正确结果；相反，若t 是r 的子集，则搜索 不满足准确性，r t 表示引入的错误结果。一般快速相似搜索的步骤可以简单的 描述为：先通过完全性搜索找到所有可能满足条件的序列集合即使得t 是r 的子 集；再在候选集中剔除掉那些不满足条件的序列数据即除去r - t 的时间序列集， 使搜索结果满足准确性。 综上所述，时间序列研究的主要内容大体可以分为数据表示和挖掘两个阶 段。时问序列表示是提取时间序列的主要特征，在更高层次上对时间序列重新描 述。挖掘是指对表示后的时间序列做进一步的数据挖掘工作。 1 3 本文工作 本文主要对时间序列的划分、距离相似度量及相似搜索等问题做了相关研 究。 1 重要点的分段表示法( i p ) 是目前应用最为广泛的时间序列特征提取方法 之一，具有较好的数据压缩和去除噪声能力，但参数的选择对时间序列的近似效 果有很大的影响。基于多分辨率的重要点检索分段方法( m i p ) 也是一种时间序列 特征提取方法，该方法能很好的近似时间序列，但运行效率比较低。为了改进以 上两种方法的不足，我们提出了一种新的序列分段的方法：基于重要点的多分辨 率检索表示法。针对时间序列的b e n c h m a r k 做了大量的实验，从误差，压缩率、 效率等方面来衡量本文方法和前面两种方法。实验表明，与基于重要点的分段方 法相比，m r i p 方法能对时间序列进行更好的压缩，误差更小有更好的近似效果， 与基于多分辨率的重要点检索分段方法相比，在近似效果相当的情况下，运算效 率更高。 2 时间序列数据相邻的点有内在的依赖关系。基于b i r c h 聚类特征及凝聚 8 时间序列相似搜索方法的研究第1 章绪论 层次聚类的思想，本文提出了基于聚类特征的时间序列划分算法( s e g m e n t a t i o n a l g o r i t h mf o rt i m es e r i e sb a s e do nb i r c hc l u s t e r i n g ，简称s b c ) 。对时间序列的 b e n c h m a r k 做了相关划分实验，并和经典的s w 划分算法进行实验对比。通过实 验结果分析，本文划分方法能达到很好的划分性能。 3 采用基于重要点的多分辨率检索表示法提取特征模式后，对提取的模式 序列提出了基于斜率模式的动态时间弯曲距离度量( s l o p ed t w ) 。采用基于 b i r c h 聚类特征的时间序列划分算法提取特征模式后，对提取的模式序列介绍了 基于均值模式的动态时问弯曲距离度量( m e a nd t w ) 。对时间序列搜索进行大量 实验，本文提出和介绍的距离度量有很好的过滤性能。与全序列d t w 搜索相比， 只对极少量满足过滤条件的序列与待搜索序列进行全序列d t w 距离计算，在时 间性能上有很大的提高。 本文以下章节的内容安排如下： 第2 章首先分析了基于重要点分段表示法和基于多分辨率的重要点检索分 段方法两种现有的时间序列表示方法的不足，接着提出了基于重要点的多分辨率 检索法的时间序列表示方法，并对该算法进行描述和相关分析。最后针对本文提 出的方法和前面两种方法进行大量实验对比，充分说明本文方法的优越性。 第3 章提出了基于b i r c h 聚类特征的时间序列划分算法。首先简单介绍了本 算法的一些相关知识，并对该算法进行描述和相关分析。其次通过相关实验，分 析说明本文划分方法能达到很好的划分性能。 第4 章首先对第2 章时间序列划分算法得到的模式序列提出基于斜率模式的 动态时间弯曲距离度量，并对第3 章时间序列划分算法得到的模式序列介绍了基 于均值模式的动态时间弯曲距离度量。其次通过实验分析比较这两种距离度量和 全序列d t w 的搜索性能。实验结果表明，上述两种距离度量能有效的过滤掉不 满足要求的序列，只对极少量满足过滤条件的序列进行全序列d t w 距离计算， 与全序列d t w 搜索相比在时间性能上有很大的提高。 第5 章对本文所做的工作进行总结，并指出之后的研究方向。 9 时间序列相似搜索方法的研究第2 章基于重要点的多分辨率检索法的时间序列表示 第2 章基于重要点的多分辨率检索法的时 间序列表示 在商业、经济、地质、生物医药、太空探测等诸多科学工业领域中广泛存在 时间序列数据，如何充分有效地管理和利用这些时间序列数据，在时间序列中发 现隐藏的知识，分析时间序列变化规律，帮助人们科学地做出决策，已经受到越 来越多的关注。 2 1 引言 时间序列数据具有海量性、复杂性和噪声干扰等特点，直接在原始序列上进 行数据挖掘工作不但在计算和储存上要花费高昂代价，而且影响算法的准确性和 可靠性。因此，国内外学者提出了多种时间序列表示方法，提取时间序列的主要 特征，将时间序列变换到低维特征空间，对时间序列维数约简。 分段线性拟合表示法是目前应用最为广泛的时间序列特征提取方法之一。该 方法采用首尾相邻的一系列线段近似表示时间序列，是一种比较直观的表示方 法，具有较高的噪声滤除和数据抽象能力，可以根据应用需要获得时间序列数据 不同精度的抽象表示。其中应用最广的是p r a t t 和f i n k 2 3 提出的基于重要点的分 段方法( 为了叙述方便，简称i p ) 。但直接采用极值点作为分段点不能有效地去 除噪音，保留了大量未过滤的细节变化，数据压缩率小。因此，需要采取某种方 法从极值点中选择一部分点作为重要点，常用的方法是前后极值点的比值，差值 或持续时间超过给定的参数。但参数的选择对表示法有很大的影响，以前后极值 点的差值超过给定的参数为例，如果参数取值较d , n 提取的特征点较多，虽然能 较好的近似原始时间序列但不能很好的压缩数据和去除噪声干扰；如果参数取值 较大则提取的特征点较少，虽然能较好的压缩数据但可能平滑掉了原始时间序列 中的某些局部极值点，导致许多重要信息丢失。可能某两个相邻的参数值都会出 现这种问题，选择较小的那个参数会无法去除噪声干扰而选择较大的那个参数导 致重要信息的丢失，也就是说可能在某些情况下并没有合适的参数能对原始序列 l o 时间序列相似搜索方法的研究第2 章基于重要点的多分辨率检索法的时间序列表示 进行很好的近似，2 4 节实验证明确实存在这种情况。 此外当几个连续数据点形成的数据子序列为单调序列时，i p 对时间序列近 似误差较大，不能发现中间的转折点，因此序列近似结果为( 如图2 1 所示) 中的 线段。而在实际应用中，突变序列中的转折点往往是数据分析处理的关键所在， 如数据序列中的异常检测，股票市场的转机点的等。当用i p 对时问序列进行线 性近似是都会将这些重要的转折点过滤掉，不能很好的近似原始时间序列。而更 精确和合理的近似应为( 如图2 2 所示) 中的线线段。 图2 1 极值点对序列的近似图2 2 对序列的精确近似 本文提出的基于重要点的多分辨率检索分段方法( 为了叙述上的方便，简称 m r i p ) ，该方法先以i p 提取时间序列的部分重要点，将时间序列的部分重要点 作为初始分割点，再采用c h a l i a wp h e t k i n g n 力等人提出了多分辨率的重要点检索 方法( 为了叙述上的方便，简称m i p ) 来对时间序列进行进一步近似。实验结果表 明，与基于重要点分段方法相比，该方法误差更小，具有很好的压缩率，并能去 除噪音干扰；与基于多分辨率的重要点检索分段方法相比，在近似效果相当的情 况下，运算效率更高。 本章组织如下：第2 2 节简要介绍已有的时序数据表示方法；第2 3 节介绍 本文提出的基于重要点的多分辨率检索法；第2 4 节是实验结果及分析；第2 5 节是小结。 2 2 时间序列线性拟合算法研究 通常用原始时间序列的极值点来对序列进行划分，得到多个直线。这种线性 时间序列相似搜索方法的研究第2 章基于重要点的多分辨率检索法的时间序列表示 的极值点拟合算法尽管算法简单，运算效率高，较好地保留了原始时间序列的变 化模式，但不能有效地去除噪音，保留了大量未过滤的细节变化，从而降低了压 缩率。因此，需要采取某种方法从极值点中选择一部分点作为重要点，重要点的 选择一般通过与前后极值点的比较来确定，常用的方法是前后极值点的比值，差 值或持续时间超过给定的参数。 2 2 1 基于重要点的分段方法( i p ) f i n k 和p r a t t 在文献 4 8 中提出了其中一种选择重要点的方法，将重要点定 义为前后极值点的差值超过给定的参数c 。该算法的描述如图2 3 所示 图2 3f p s e g m e n t a t i o n ( x ，c ) 算法描述 步骤1 即函数f i n dp e a kp o i n t ( x ) 找到时间序列的所有极值点，步骤2 即函 数s e l e c tp e a kp o i n t ( i n i t 复杂度为线性的。但这种方法的不足之处是可能在某些情况下并没有合适的参数 能对原始序列进行很好的近似并且不能找到重要转折点。f p s e g m e n t a t i o n ( x ，c ) 算法中f i n dp e a kp o i n t ( x ) 函数描述如图2 4 所示。 时间序列相似搜索方法的研究第2 章基丁重要点的多分辨率检索法的时间序列表示 图2 4f i n d _ p e a k _ p o i n t ( x ) 函数描述 该函数的功能是找到所有的极值点，并将极值点的下标保存在i n i t _ _ p e a k 数 组中。f p s e g m e n t a t i o n ( x ，c ) 算法中s e l e c t p e a kp o i n t ( i n i t _ p e a k ，c ) 函数描述如图 2 5 所示。 图2 5s e l e c t _ p e a kp o i n t ( i n i t _ _ p e a k , c ) 函数描述 该函数的功能是从所有极值点中筛选出前后极值点的差值超过给定的参数 c 的极值点，并将满足条件的极值点下标保存在s e l e c ti n d e x 数组中。 2 2 2 基于多分辨率的重要点检索分段方法( m ip ) c h a l i a wp h e t k i n g h 等人提出了多分辨率的重要点检索方法，首先得到计算 时间序列的最粗糙的线性分段表示，即用一条线段来拟合时间序列。选择偏离这 条线段上方的最大点和下方的最大点，把这两个作为重要点( 可能只有一个点) ， 将整条线段分成三段( 或两段) 。然后再对划分后的这些线段采用类似的方法，直 到每个分段的数据个数不超过参数l e n 结束。该方法的优点是迭代到一定程度， 对原始时间序列有很好的近似效果，但不足之处