（计算机应用技术专业论文）水文时间序列相似模式挖掘的研究与应用.pdf

河海大学硕士学位论文水文时间序列相似模式挖掘的研究与应用 摘要 水文序列相似性查找可用于雨洪过程预测、环境演变分析、水文过程规律分 析等方面。最为直接的应用是回答防汛指挥中经常问到的“当前水文过程相当于 历史上哪一时期的同类过程”等问题。由于水文数据数量大、类型复杂，仅使用 水文学的理论和传统统计方法加以分析，往往因为计算能力、存储能力以及算法 的不足等而显得无能为力。在水文领域引入数据挖掘的理论与技术，为解决水文 科学研究面临的问题提供了新的思路。 论文围绕时间序列相似性查找这个主题，从时间序列的模式表示出发，讨论 了时间序列的相似性度量，探索适合水文时间序列特点的相似性查找模型。主要 工作包括： l 、时间序列的模式表示。 使用一种基于特征点的时间序列线性分段方法作为时间序列的模式表示。该 方法简单直观，对于具有明显的周期性和短期模式波动频繁等特点的时间序列， 能够有效地实现数据压缩，从而把握时间序列总体模式的变化特征。 2 、时间序列的相似性度量。 在时间序列的模式表示基础上，引入了动态模式匹配距离。该距离支持时间 序列的时间弯曲，其时间复杂度随着模式长度的增长而接近线性。 3 、水文时间序列相似性查找模型。 设计适应水文时间序列数据特点的相似性查找模型。以该模型为基础，以基 于特征点的时间序列线性分段方法作为降维手段，以动态模式匹配距离为相似性 度量标准，结合水文时间序列相似性挖掘主题，实现了针对该主题的一个具体应 用。 实验表明，基于特征点的时间序列线性分段方法与动态模式匹配距离相结合 是解决常见的水文相似性查询问题的有效途径。 关键词：时间序列、模式表示、相似性度量、相似性查询 河海大学硕士学位论文水文时间序列相似模式挖掘的研究与应用 a b s t r a c t h y d r o l o g i c a lt i m es e r i e ss i m i l a r i t ys e a r c hc a l lb eu s e dt or a i na n df l o o d sf o r e c a s t , a n d t h ea n a l y s i so fe n v i r o n m e n te v o l v e m e n ta n dh y d r o l o g i c a lp r o c e s s e t c n 圮d i r e c t a p p l i c a t i o ni st oa n s w e rs u c hq u e s t i o n sa s w h i c hh y d r o l o g i c a lp r o c e s si nh i s t o r yd o e s t h eo n g o i n go n ec o r r e s p o n dt o ? t h eq u a n t i t yo fh y d r o l o g i c a ld a t ai sh u g ea n di t s t y p ei sc o m p l e x i t y i ti sh a r dt oa n a l y s i su s i n go n l yt h em e t h o d so fh y d r o l o g i c a l t h e o r i e sa n dt r a d i t i o n a ls t a t i s t i c s ，b e c a u s eo ft h el i m i t a t i o no fc o m p u t i n ga b i l i t y , s t o r a g ea b i l i t ya n da l g o r i t h m s n 沁i n t r o d u c t i o no fd a t am i n i n gt h e o r i e sa n d t e c h n o l o g i e st oh y d r o l o g i c a la r e ap r o v i d e san e ww a yt os e t t l et h ep r o b l e m st h a tt h e h y d r o l o g i c a ls c i e n c ec o n f r o n t sw i t l l b a s e do nt h ep a t t e r nr e p r e s e n t a t i o na n ds i m i l a r i t ym e a s u r eo ft i m es e r i e s 。t h i s p a p e re x p l o r e st h es i m i l a r i t ys e a r c hm o d e l ，w h i c hi sa d a p t i v et ot h ec h a r a c t e r i s t i c so f h y d r o l o g i c a ld a t a 1 1 1 ew o r ko f t h ep a p e rm a i n l yi n c l u d e s ： ( 1 ) p a t t e mr e p r e s e n t a t i o no f t i m es e r i e s u s eam e t h o do ft i m es e r i e sp 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 nf e a t u r e p o i n t sa saw a yf o rp a t t e r nr e p r e s e n t a t i o n 1 1 1 i sm e t h o di ss i m p l ea n di n t u i t i v e a n d c a l la c h i e v ed a t ac o m p r e s s i o ne f f e c t i v e l yf o rt i m es e r i e sw i t ho b v i o u s p e r i o d i c i t ya n d v i o l e n tp a t t e r nf l u c t u a t i o nd u r i n gas p e c i f i cp e r i o d ，s ea st ow e l lh o l dt h ec h a n g e c h a r a c t e r i s t i c so f t h ew h o l ep a t t e r n ( 2 ) s i m i l a r i t ym e a s u r e b a s e do nt h ep a t t e r nr e p r e s e n t a t i o no ft i m es e r i e s t h i sp a p e ri n t r o d u c e s t h e d y n a m i cp a t t e mm a t c h i n g ( d p m ) d i s t a n c e ，w h i c hs u p p o r t st i m ew a r p i n go fs e r i e s a n dw h o s et i m ec o m p l e x i t ya p p r o a c h e sl i n e a r i t ya l o n gw i t l lt h ei n c r e a s eo ft h el e n g t h o f p a t t e m s ( 3 ) s i m i l a r i t ys e a r c hm o d e lo f h y d r o l o g i c a lt i m es e r i e s w ed e s i g nt h es i m i l a r i t ys e a r c hm o d e lo ft i m es e r i e s w h i c hi sa d a p t i v et ot h e c h a r a c t e r i s t i c so fh y d r o l o g i c a ld a t a t h e nu s i n gt h em e t h o do fp l rb a s e do nf e a t u r e p o i n t sa sm e a n so fd i m e n s i o nr e d u c t i o na n dd p md i s t a n c ea ss i m i l a r i t ym e a s u r e ， c o m b i n i n gt h e m o t i fo fh y d r o l o g i c a lt i m es e r i e ss i m i l a r i t ym i n i n g , t h i s p a p e r i m p l e m e n t sa c o n c r e t ea p p l i c a t i o n e x p e r i m e n ts h o w st h a tt h ec o m b i n a t i o no f p l rb a s e do nf e a t u r ep o i n t sa n dd p m i sa ne f f e c t i v ew a yt od e a lw i t ht h ec o m m o ni s s u eo f h y d r o l o g i c a ls i m i l a r i t y k e y w o r d s ：t i m es e r i e s ，p a t t e r nr e p r e s e n t a t i o n ，s i m i l a r i t ym e a s u r e ，s i m i l a r i t ys e a r c h 河海大学硕士学位论文 水文时间序列相似模式挖掘的研究与应用 记号与术语 b a s ed i s t a n c e , e g d j ，d 2 d y n a m i ct i m ew a r p i n gd i s t a n c e t i m es e r i e s t h er e s te l e m e n t so fx b u tt h e f i r s t p a t t e r no f t i m es e r i e s n m lt i m es e r i e s e l e m e n t s f r o mt h ei - t hf 0t h el a s to fx v x 1 ， z 州p m 舷 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同事对本研究所做的任何贡献均己在论文中作了明确的说明并 表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ： ( 注：手写亲笔签名) 学位论文使用授权说明 口7 年够月日 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期 刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文 档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允 许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权河 海大学研究生院办理。 论鼍篡黧，l 仁，7 年肇月v 日( 注：手写亲笔签名) ， 河海大学硕士学位论文 水文时间序列相似模式挖掘的研究与应用 1 1 研究背景 第一章绪论 1 1 1 水文数据挖掘 2 0 0 2 年，叶守泽和夏军发表了【l j ，认为水文科学研究的领域面l 临来自许多方 面的不确定性和非确知问题：利用更多的高新技术，如水文遥感、水文示踪技术 和地理信息系统等，揭示水文时间和空间变化规律，提出新的认识，是2 1 世纪 水文科学发展的一个必然趋势。我国水文业务部门自2 0 世纪8 0 年代以来，在以 计算机为代表的高新技术浪潮的推动下，充分应用高新技术手段，对水文信息基 础设施进行了重点投资建设，对水文科学面临的各个方面的问题进行了许多有益 的研究。最为突出的是国家水文数据库系统和全国防汛实时雨水情库系统已基本 建成，至2 0 0 4 年全国水文数据累积量已超过1 0 t b ，加上逐渐形成的与气象、国 土资源等相关信息系统的相关连接，能够形成种类较为齐全、总量十分巨大的信 息资源，为我国水文科学研究提供了很好的信息环境。面对这些数量巨大、类型 复杂的数据，仅使用水文学的理论和传统统计方法加以分析，往往因为计算能力， 存储能力以及算法的不足等而显得无能为力。在此基础上引入数据挖掘的理论与 技术，研究水文数据挖掘的理论、技术和方法，为解决水文科学研究面临的问题 提供了新的思路和可能的途径。 数据挖掘是指从大量的实际应用数据中，提取隐含在其中的、人们事先不知 道的、但潜在有用的信息和知识的过程 2 1 。水文数据挖掘( h y d r o l o g i c a ld a t a m i n i n g ) 是数据挖掘技术在水文领域的应用，是从大量的、不完全的、有噪声的、 模糊的、随机的水文及其相关数据中，提取隐含在其中的水文信息和知识的过程 例。一般认为，数据挖掘是知识发现过程中的一个特定步骤，使用专门算法从数 据库中抽取模式( p a t t e r n ) ，然后通过知识发现中的解释和评价模块将模式转换成 用户可以理解的知识。但是，广义的数据挖掘通常被认为是数据准备、模式抽取、 知识表示等步骤组成的知识发现全过程。数据挖掘把人们对数据的应用和理解从 低层次的简单查询，提升到从海量数据中挖掘知识，以提供决策支持。 水文现象是时变现象，这一变化过程称为水文过程。水文数据是对这一过程 的离散记录，其包含的水文信息是水文科学发展的源泉和基础，水文学需要大量 获取新的信息，并在这种新的信息基础上提取出新的知识。水文数据挖掘就是这 一需求的产物。 水文数据按其描述的物理量分为各种类型的水文时间序列。所谓时间序列 ( t i m e s e r i e s ) 是指按照时间先后顺序排列的各个观测记录的有序集合【4 1 。目前许 河海大学硕士学位论文承文时间序列相似模式挖掘的研究与应用 多水文学家认为，水文时间序列一般由确定分量和随机分量组成。确定分量具有 一定的物理概念，随机分量由不规则的振荡和随机影响造成，二者不能严格地从 物理成因上加以阐明【朋。因此，水文数据挖掘主要是对时序数据的挖掘，需要与 水文领域数据分析处理技术紧密结合，同时也需要充分利用计算机软件技术、数 据库、数据仓库及其他数据处理等新技术。 根据水文科学研究与实际应用的需要，水文数据挖掘可细分为相似性查找、 序列模式挖掘和周期分析等。本文重点讨论使用数据挖掘技术在水文时间序列数 据库中进行相似模式的查找。 1 1 2 水文时间序列相似性查找 所谓相似性查找是指找出给定序列最接近的其他序列。找出与给定序列相似 的所有数据序列称为子序列匹配，找出彼此i 日j 相似的序列称为整体序列匹配。水 文序列相似性搜索就是要在水文序列库中找出各类相似的子序列序列对。其表 征的水文知识包括气候及下垫面的演变过程及趋势。可用于雨洪过程预测、环境 演变分析、水文过程规律分析等方面。最为直接的应用是回答防汛指挥中经常会 问到的“当前水文过程相当于历史上哪一时期的同类过程”等问题。另外，在不 同的时空尺度下，水文现象一般具有不同的规律。在这种情况下，水文学家寻求 水文规律总是先认识一定尺度的水文规律，然后通过揭示不同尺度之间的联系， 再把这个规律推论到其他尺度上去。近2 0 年来，水文学十分重视这方面的研究， 认为水文尺度问题是水文学基础研究的一个前沿课题和难题。另一方面，水文尺 度问题与水文相似性问题密切相关，因为如果能寻找出水文相似性，那么就可以 通过这种相似性来处理水文尺度问题。例如，近些年来研究发现，有些水文现象 受到分形理论的影响。按照分形理论，在一定尺度范围内，具有自相似性的水文 现象，其不同尺度的规律性之间的关系取决于一种称为标度变换的简单变换。因 此，对于具有自相似性的水文现象，通过标度变换就可以将该水文现象从一种尺 度下获得的规律变换成另一种尺度的规律。可以看出，水文尺度和水文相似性的 研究，对从理论上解决无实测水文资料情况下水文规律的探求问题具有深远的理 论意义和重大的应用价值。 传统的时间序列相似性搜索研究强调精确匹配，但是在数据挖掘应用中，由 于数据量巨大，一般采用基于近似匹配的“近似”的相似性搜索。数据挖掘背景 下的时间序列相似性搜索不仅是有用的数据分析工具，也是聚类、分析、关联规 则等其他数据挖掘应用的基础。当前，时间序列相似性搜索在水文时间序列分析 中的应用不多。 水文时间序列相似性挖掘的关键问题在于： ( 1 ) 子序列的划分：在国家水文数据库中，洪水过程已经按产汇流理论进行 了划分，形成了各类要素的摘录表，但日值类过程则需要按拟解决的问题类型进 河海大学硕士学位论文 水文时间序列相似模式挖掘的研究与应用 行划分。发现既符合水文理论，又适合计算机处理的过程划分方法十分重要。 ( 2 ) 序列的特征提取：一般方法是对序列进行变换，如通过傅立叶变换、小 波变换或分段平均等方法映射到特征空间，以特征空间中序列间距离小于给定阀 值作为相似性判定标准。变换方法与不同水文要素过程的适应性是问题的关键。 ( 3 ) 相似性度量的确定：对于水文过程而言，不同的水文要素过程有不同的 特征。根据水文过程的特点，确定与之相适应的相似性度量，是保障挖掘结果有 用性的重要条件。 ( 4 ) 多要素过程联合相似性查找：为了研究区域水文规律，水文过程的相似 性搜索需要具备处理多个要素过程同时相似的能力，如a 站某一时段与b 站某 一时段不但水位过程相似，而且降雨过程也相似等。 本文在深入研究和比较各类相似性挖掘方法的基础上，结合水文领域的应用 背景，着重探讨使用数据挖掘技术来解决水文时间序列的特征提取和相似性度量 问题。 1 2 时间序列相似性查找研究现状 时间序列相似性查找( 也叫相似性搜索，下同) 的目的是在时间序列数据库中 发现与给定模式相似的序列或查找时序库中相似的序列对 6 1 。从序列长度的角度 可以分为两类【7 j ： ( 1 ) 全序列匹配( w h o l em a t c h i n g ) ：比较的序列之间长度相等。 ( 2 ) 子序列匹配( s u b s e q u e n c em a t c h i n g ) ：参考序列长度比较小，而查询序 列长度较大，在长序列中查找与参考序列最相似的子序列。 从搜索任务的角度，根据查询及其结果的要求，时间序列相似性查询又可 以分为以下三种： ( 1 ) 指定查询序列搜索( r a n g eq u e r y ) 即给定查询序列，在时序数据库中查 找所有与之相似的序列，子序列。 ( 2 ) 匹配序列对查询( a l l - p a i r sq u e r y ) ：在时序数据库中发现所有彼此相似的 序列子序列对。 ( 3 ) 最近邻搜索( n e a r e an e i g h b o rs e a r c h e s ) ：给定一个查询序列，在时序数 据库中查找k 个与之最相近的序列子序列。 鉴于时间序列数据量大、维数高、噪声强等特点，f a l o u t s o s 等人通过对时 间序列相似性的研究，提出了g e m i n i ( g e n e r i cm u l t i m e d i ai n d e x i n gm e t h o d ) 方法 【8 】： 首先，建立专业领域内的相似性度量标准： 其次，使用降维技术将原始时问序列从n 维降到n 维。其中n n ，且在n 维特征空间中，多维空日j 索引结构能够有效组织这些特征向量； 最后，在n 维索引空间中定义相似性度量杯准，并且保证查询的完备性。 河海大学硕士学位论文水文对问序列相似模式挖掘的研究与应用 其中，相似性度量是时间序列相似性查询的基础；索引技术则可以提高相 似性查询的效率；降维技术( 也叫模式表示，以下称之为模式表示) 是对时间序列 进行抽象和概括的特征表示方法，是在更高层次上对时间序列的重新描述，不但 能够对时间序列数据进行压缩，而且突出了时间序列的模式变化特征。目前，时 间序列的相似性查找研究的大部分工作都是建立在g e m i n i 方法基础上的。 近年来，国内外许多学者和研究人员致力于时间序列的相似性研究，提出 了许多不同的方法。从时间序列模式表示的角度，大致归为两种途径：第一种途 径通过变换将时问序列由时域映射到频域来研究；第二种途径则直接在时域上进 行各种不同的特征提取来研究相似性问题。下面分别介绍两种途径中的典型方 法。 1 频域方法 通过某种映射函数，将时间序列映射到频率域中进行相似性搜索的各种方 法统称为频域方法。 a g r a w a l 等人首次提出采用频谱来表示时间序列【7 】。该方法使用离散傅立叶 变换( d i s c r e t ef o u r i e r t r a n s f o r m , d f t ) 将时间序列从时域空间映射到频域空间，根 据p a r s e v a l 理论，时域能量函数与频域能量谱函数相同，且频域空间中的大部分 能量都集中在前几个系数上。因此可以仅保留前k 个( 2 到3 个) 傅立叶系数，将 序列映射成k - 维空间上的点，从而达到降维的目的。这样，每个时间序列经d f t 变换后被映射为较低维空间中的一个点。为了能高效率搜索访问这些点，采用 r 树作为其索引结构。由于p a r s e v a l 理论保证了时间序列经d f t 变换前后的欧 氏距离等价性，因而该方法保证了特征提取的完备性。但是该方法仅讨论了序列 完全匹配，没有涉及到子序列匹配问题。 在这类方法中，除了d f t 变换外，其他正交变换，如离散余弦变换( d i s c r e t e c o s i n et r a n s f o r m , d c t ) 、离散小波变换( d i s c r e t ew a v e l e tt r a m f o r n l ，d w t ) 等也可 以达到降维的目的。c h a n 和f u n 就采用h a r t 小波变换，将时间序列的d w t 表 示用于索引和相似性查询，并将其与d f t 方法进行了比较。尽管小波变换有较 好的时间复杂度和磁盘性能，但是d f t 方法也可以通过利用傅立叶变换的对称 性而提高其性甜1 0 l ，并最终达到与d w t 相当的效果。 2 时域方法 一种时域方法是把长时间序列分割成若干较短的子序列【1 1 2 1 。其基本思想 是：如果两个时间序列有足够多的在时间序上互不重叠的子序列对相似，那么这 两个时间序列就相似。由于没有对子序列进行降维，所以当时间序列很长，被比 较序列数量大时，该方法的效率会下降。 另一种时域方法是对时间序列进行适当的变换或表示，提取其特征值，然 后基于特征值进行相似性比较。i t 3 提出了一种基于多项式回归分析的相似性度 4 河海大学硕士学位论文 水文时间序列相似模式挖掘的研究与应用 量和时间序列相似模式抽取的系统化方法，其基本思路是：用一个分段多项式回 归模型近似一个时间序列，把原始序列映射到多项式系数张成的特征空间，并推 导出此特征空间的欧氏距离作为相似性度量，从而自然地把原始序列分为一个不 重叠的有序子序列集合，然后对这个子序列集合进行聚类，得到一组不重叠的模 式；1 1 4 j 提出了基于缩放和移位变换的时间序列相似性定义，从几何视角来决定 缩放比例因子a 和移位偏移量b ；a g r a w a l i ”j 等人将时间序列用波形符号来表示， 在此基础上引入了多种符号算子，定义了s d l 语言来描述时间序列；p 6 提出了 一个界标模型( l a n d m a r k s m o d e l ) ，其基本思想是由原始序列得到界标序列，用界 标序列代替原始序列作为相似查询的对象。 目前，虽然数据挖掘技术已经在金融、电信、政府、制造、能源、交通、 环保、制药等行业得到了广泛应用，国内外许多学者和研究人员采用不同的方法 围绕时间序列相似性的研究也已取得了一定的成果。但水文数据挖掘特别是水文 时间序列相似模式挖掘的研究还处于起步阶段，研究内容多集中在水文数据的单 项和局部数据的模拟与处理方面，对基于水文数据库的全局性多因素数据挖掘涉 及很少，在数据挖掘技术与水文数据适应性方面所进行的研究还不够。 1 3 本文工作 1 3 1 研究目标 本文围绕时间序列模式相似性这个主题，从时间序列的模式表示出发，讨 论了时间序列的线性分段、相似性度量和相似性查找。在此基础上设计适合水文 时间序列特点的相似性模型，并应用于水文时间序列相似性的查找。 本文将时间序列的模式表示作为其他研究的基础，而相似性度量则是时间 序列的相似性查询的基础，论文的主要研究问题及相互关系如图1 1 所示： i时间序列的相似性查找 t 丁 时间序列的相似性度量 丁丁 l时间序列的模式表示 图1 - 1 论文的主要研究内容和相互关系 河海大学硕士学位论文水文时问序列相似模式挖掘的研究与应用 1 3 2 研究内容 本文的主要工作包括： ( 1 ) 时间序列的模式表示。使用一种基于特征点的时间序列线性表示方 法，并将其作为水文时间序列降维、除噪的手段。水文时间序列具有不同于 其他时间序列的特点，突出表现为时间序列的不规则性以及短期局部模式的 剧烈变化性。实验表明，本文使用的基于特征点的线性表示方法，无论是对 模式趋势的总体把握情况，还是与原始时间序列的拟合误差情况，均具有独 特的优势，比较适合水文时间序列的数据特点。 ( 2 ) 时间序列的相似性度量。在时间序列模式表示的基础上，结合动态 时间弯曲( d y n a m i ct u n ew a r p i n g ，d t w ) 的基本思想，引入了动态模式匹配 ( d y n a m i cp a t t e r nm a t c h i n g , d p m ) 距离，既克服了d t w 距离时间复杂度高的 缺点，又具有支持序列时间轴弯曲的优点。实验表明，基于d p m 距离的相 似性度量，其时间复杂度随着模式长度的增加而接近线性，而其聚类效果与 d t w 距离相当。 ( 3 ) 基于上述技术，设计水文时间序列相似性查找模型，并在水文数据 集上进行实验，对模型的有效性和正确性加以验证。 1 3 3 本文结构 全文共分五章，简单介绍如下： 第一章：绪论。介绍了时间序列数据挖掘的相关研究背景和研究现状，并 简要介绍本文的主要研究内容。 第二章：时间序列的模式表示。介绍了时间序列的几种典型的模式表示方 法，并讨论了它们的优缺点。论文使用一种基于特征点的时间序列模式表示方法， 并在水文数据集上与p a a 模式表示方法进行了比较。 第三章：时间序列的相似性度量。介绍了几种常见的相似性度量，指出欧 氏距离和动态时间弯曲距离存在的缺点。引入了动态模式匹配距离，并通过实验 比较了分别采用这三种距离进行聚类的效果。 第四章：水文时间序列的相似性查询及其应用。介绍了时间序列相似性查 询的相关研究，并以第二章使用的基于特征点的线性分段方法为模式表示手段， 以第三章引入的动态模式匹配距离为相似性度量标准，设计水文时间序列相似性 查找模型，并在水文数据集上进行实验，对模型的有效性和正确性加以验证。 第五章：总结与展望。总结了全文研究工作，并指出了下一步要开展的工 作。 6 河海大学硕士学位论文水文时间序列相似模式挖掘的研究与应用 第二章时间序列的模式表示 2 1 引言 由于时间序列的维数高、数据量大以及噪声干扰严重等特点，直接在时间 序列上进行数据挖掘不但在存储和计算上要花费高昂代价，而且可能会影响算法 的准确性和可靠性。对此许多研究者提出了时间序列的模式表示( 也叫特征提取) 方法，用以刻画时间序列的主要形态而忽略那些微小的细节。 时间序列的模式表示有三方面的好处： ( i ) 对时间序列进行压缩，换来更小的存储和计算代价： ( 2 ) 只保留了时间序列的主要形态，去除了细节干扰，更能反映出时间序列 的自身特征，有利于提高数据挖掘的效率和准确性； ( 3 ) 水文领域关心的是水文时间序列一段时间内的变化模式和规律，而不是 时间序列中单个序列点的值，模式表示更能符合其特点。 因此，时间序列的模式表示是时间序列数据挖掘的先决条件，是水文时间 序列相似性挖掘的关键问题之一，其效果直接影响数据挖掘的结果。 2 2 相关研究 首先，给出时间序列和模式表示的数学形式描述【4 】。 定义2 - 1 时间序列 时间序列是由记录值和记录时间组成的元素的有序集合，记为 x = ( 而= ( v ，f 1 ) ，x 2 = ( v 2 ，t 2 ) ，- - - - ( v 。，) ) ，元素x ，= ( v 。，t ，) 表示时间序列在t 。 时刻的记录值为v l ，记录时n t , 是严格增加的。 一般情况下，时间序列的采样间隔时间a t = f “| - t ，相等，可以看作t ，= 0 ， 加= 1 ，此时将时间序列x = ( x l = ( v 1 ，t i ) ，x 2 = ( v 2 ，t 2 ) ，x 。- - - - ( v 。，t 。) ) 简记为 x = ( x l , x ：，x 。) 。对于广义时间序列，记录值一可以是多种类型，包括离散符 号、数据结构、多媒体数据等。本文只考虑狭义时间序列，即v 。为实数值的情形。 定义2 - 2 时间序列的模式表示 时间序列x = ( _ ，x ：，x n ) 的模式表示如下： x ( t ) = ，( 叻+ p ( f ) ，t = 1 , 2 ，一 其中，w 是时间序列的模式，八w ) 是时间序列的模式表示，p ( f ) 是时间序列 7 河海大学硕士学位论文水文时间序列相似模式挖掘的研究与应用 与其模式表示之间的误差。 时间序列的模式表示能够压缩数据，保留时间序列的主要形态，忽略其中的 微观细节。如图2 - l 所示，图2 - 1 ( a ) 是一条具有3 6 5 个数据点的原始水文时间序 列数据；图2 - 1 ( b ) 是该时间序列的一个模式表示，只需保留个7 0 数据点，不但 压缩率达到8 1 ，而且很好地保留了原始时间序列的主要形态。 图2 - 1 时间序列及其模式表示 时间序列模式依据其表现形式的不同，可以分为频域表示法、奇异值表示法、 符号表示法以及分段线性表示法等。 2 2 1 频域表示 a g r a w a l 等人首次提出采用频谱来表示时间序列。通过使用离散傅立叶变换 ( d i s c r e t ef o u r i e r t r a n s f o r m ，d f t ) 将时间序列从时域空间映射到频域空间，通过选 择前k ( 一般1 3 ) 个d f t 系数来表示该时间序列。文献【1 7 1 在全序列匹配问题中采 用d f t 表示方法获得了很好的性能。 d f t 变换的优点在于：( 1 ) 降维幅度大，只用极少数傅立叶系数来表示时间 序列，避免了采用多维索引时产生的“维灾( d i m e n s i o nc u r s e ) ”问题。( 2 ) 保持 欧氏距离的不变性，即两条时间序列间的欧氏距离在时域和频域上保持不变。因 8 河海大学硕士学位论文 水文时间序列相似模式挖掘的研究与应用 此，当一些比较小的d f t 系数被舍弃后，时间序列在频域上的欧氏距离将不大 于时域的欧氏距离，从而保证了基于d f t 变换的时间序列相似性查询的完备性。 其缺点是可能会丢失时间序列的局部特征。 与离散傅立叶变换相比，离散小波变换( d i s c r e t ew a v e l e tt r a n s f o m ld w t ) 是 时间和频率的局部变换，能更加有效地提取和分析局部信号。d w t 方法具备时 频局部化的特点，不但包含了频率信息，同时还包含了时间信息( 而d f t 是对信 号的整体变换，只考虑了频率信息) 。在离散小波系数中，前几个系数代表信号 的一个粗糙的全局近似，接下来的系数则是对该信号的进一步细节描绘。这一特 性在对数据作多分辨率解析时非常有用。c h a r t 和f u 【1 8 】采用h a r r 小波变换，将 时间序列的d w t 表示用于索引和相似性查询，实验结果表明：时间序列的h a r t 小波表示用于相似性查询时，查询的精度、磁盘性能和伸缩性都超过了时间序列 的d f t 表示方法。之后，c h a r t 等人还将时间序列的d w t 表示与动态时间弯曲 距离结合，处理了时间序列在时间轴弯曲时的相似性查询问趔1 9 1 。p o p o v a n o v 和 m i l l e 一硎比较了大量的不同种类的小波( 包括正交小波和非正交小波) 用于时间序 列表示时相似性查询的性能，指出当数据的频谱指数 1 5 时，采用频域表示 法在相似性查询时就能获得良好的性能。 与d f t 表示方法一样，d w t 表示方法同样具备保持欧氏距离的不变性和查 询完备性的特点。d w t 表示方法的一个缺点是：只适用于长度为2 的整数次方 的时间序列。 w l o 等人比较了d f t 表示和d w t 表示，认为在相似性查询问题上两种表示方 法性能相当，但是d w t 只需线性时间，计算更为迅速。 2 2 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 ) 是一种常见的降维方法，已 经成功用于图像和文本的索引【2 l ，2 2 l 。s v d 表示方法与其他的时间序列表示方法 不同，它是对整个时序数据库的整体表示。通过分析所有的时间序列，计算新的 坐标体系，使得第一条坐标轴对应最大的方差，第二条坐标轴对应次大的方差并 与之前的坐标轴正交，依次得到所有的坐标轴，根据这些坐标轴将时间序列从原 始空间变换到新的坐标空间。s v d 方法是一种线性变换，在数据重构上误差最 小田】，这使得s v d 在一些情况下能够取得很好的性能。但是，s v d 方法的时间 复杂度为o ( m n 2 ) ，其中m 是指时间序列数据库的大小，席指时间序列的平均长 度。当插入或删除一条时间序列时，所有时间序列的s v d 表示方法都必须重新 计算，时间代价很高。 河海大学硕士学位论文水文时间序列相似模式挖掘的研究与应用 2 2 3 符号化表示 其基本思想是：首先将时间序列离散化，映射到包含少量字符的字符串，然 后再引用字符串匹配和索引的相关成果。 a g r a w a l 等人将时间序列的波形用符号来表示，在此基础上引入了多种符号 算子，定义了s d l 语言来描述时间序列1 2 4 1 。j o s s o n 和b a d a l t 2 5 i 将时间序列相邻 点的差值映射到一个符号表，将时间序列看作文本，采用签名文件( s i g n a t u r ef i l 曲 来索引时间序列。h u a n g 和y u 提出了i m p a c t s 算法，将时间序列相邻点的变 换率符号化，建立后缀树( s u f f i xt r e e ) 对时间序列进行索引和查询以适应约束较 多的动态查询 2 6 1 。p a r k 等人的工作使得基于符号化表示的时间序列相似性查询 能够支持比欧氏距离更鲁棒的动态时间弯曲距离，他们采用等宽离散化和最大熵 离散化方法将时间序列的实数值映射到有限的符号，以后缀树为索引，提出了一 种动态时间弯曲距离的下界距离，在提高查询效率的同时保证了查询的完备性 【2 7 ，2 3 i 。1 2 9 提出了基于云模型的形态表示方法，根据云模型将时间序列的形态符号 化。 符号化方法的缺点在于字符串之间是精确的匹配，而时间序列的相似性查询 则要求近似匹配，因此需要定义字符间的相似性度量；此外，离散化方法和字符 表大小的选择也是一个难点。 2 2 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 l r 中， 线段的数目决定了对原始序列的近似粒度。线段越多，线段的平均长度就越短， 反映了时间序列的短期波动情况；线段越少，线段的平均长度就越长，反映了时 间序列的中长期趋势。k e o g h 【3 0 j 等人将输入为时间序列，输出为p l r 的算法统 称为线性分段算法( l i n e a rs e g m e n t a t i o n a l g o r i t h m s ) 。直观上讲，p l r 方法就是用 置条首尾邻接的直线段来近似表示一条长度为n ( n k ) 的时间序列。 线性分段的关键问题在于：l 、如何选择合适的线段数目? 2 、如何选择合适 的分段点? 根据对这两个问题的不同解决方法，将线性分段算法分为以下几种类 型： ( 1 ) 限制分段数k 即给定时间序列，产生的p l r 只包括x 个直线段。1 3 1 和 3 2 1 分别独立提出了 时间序列的分段聚集近似( p i e c 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 ) 方法，将时间 序列等宽度划分，每个子段用时间序列在该子段上的平均值来表示。p a a 方法 简单直观，能够支持任意长度的相似性查询和所有的m i n k o w s k i 度量以及加权欧 氏距离，而且能够用于索引以提高查询的效率。k e c i g h 等人的实验表明，将p a a l o 河海大学硕士学位论文水文时问序列相似模式挖掘的研究与应用 方法用于时间序列的索引，使得相似性查询的效率比d f t 表示方法提高了1 2 个数量级【3 l 】。 ( 2 ) 限制分段误差 即不规定分段的数目，通过控制分段误差来选择合适的分段点。主要有两种 限制分段误差的方式： 1 ) 给定时间序列，产生的p l r 中每个分段的最大误差不超过某个用户指定 的误差阀值m a xe r r o r ； 2 ) 给定时间序列，产生的p l r 中所有分段的误差总和不超过某个用户指定 的误差阀值，d 脚m a xe r r o r 。 根据分段误差控制的方法不同，这类算法又可分为以下三种： 1 ) 滑动窗i z l ( s l i d i n gw m d o w ) ：从时间序列的第一个点开始一个新的分段，持 续向后增长直到该分段与时间序列的拟合误差超出了某个指定阀值，结束该分 段，然后以下一个序列点作为新分段的开始，不断重复上述过程直到时间序列末 端。这类算法的优点是简单直观且支持在线分段，缺点是在某些情况下会得到很 差的近似表示。p a r k 等人提出单调变化的分段算法，在光滑的数据集上取得了良 好效果，但是在具有大量噪音的实际数据上，得到的分段太多口3 1 。滑动窗口方 法的时间复杂度为o ( n ，1 ，其中，是分段的平均长度。 2 ) 自底向上( b o t t o m - u p ) ：首先得到最精细的线性分段表示，即时间序列上相 邻两点组成最小分段。然后计算合并两个相邻分段所产生的拟合误差，合并拟合 误差最小的两个邻接分段，直到该拟合误差超过某个指定阀值。自底向上算法的 时间复杂度与滑窗方法一样，都是o ( n - ，) 。 3 ) 自顶向下( t o p - d o w n ) ：该算法是b o t t o m - u p 算法的逆过程。首先得到计算 时间序列的最粗糙的线性分段表示，即用一条线段来拟合时间序列。然后计算将 该线段分割成两条拟合线段所能降低的拟合误差，选择最大拟合误差的分割点， 重复上述过程，直到每个分段的误差都不超过某个指定阀值。p a r k 等人改进了该 算法，将时间序列的极值点作为初始分割点，然后再使用经典t o p - d o w n 算法 3 4 1 。 t o p - d o w n 算法的时间复杂度比较高，达到o ( n 2 ) 。 2 2 5 其他表示方法 这类方法采用一些启发式规则，从时间序列中选择具有明显特征意义的时间 点将时间序列分割为许多子段，通过线性插值等方法计算每个子段内的拟合直线 段，就得到了时间序列的一种p l r 。这类算法一般不限制分段数和分段误差，重 要的是如何选择合适的分段点。p e n g 等人提出了界标模型( l a n d m a r km o d e l ) 用于 河海大学硕士学位论文水文时间序列相似模式挖掘的研究与应用 时间序列的分割，其中m 阶界标点被定义为m 阶导数为0 的点，通过最小距离 和百分比原则选择部分界标点作为分段【 j 。p r a t t 和f r i n k 提出了基于重要点的分 段方法，重要点被定义为在局部范围内与局部端点的比值超过参数r 的极值点， 将重要点作为时间序列的分段点。通过选择不同参数r ，可以获得不同精细程度 的表示【j 6 1 。 在时间序列的各种模式表示方法中，p l r 方法相对而言更加简单直观，具有 时间多解析的特点，而且多数p l r 方法支持时间序列的动态增量更新。 2 3 基于特征点的分段线性表示 在充分了解和分析各种时间序列模式表示方法的基础上，本节将使用一种基 于特征点的分段线性表示( p l rb a s e do rf e a t u r ep o i n t s ，p l r _ f p ) 作为时间序列的 模式表示方法。该方法简单直观，对于具有明显的周期性和短期模式波动频繁等 特点的时间序列，能够有效地实现数据压缩，从而把握时间序列总体模式的变化 特征。 下面首先给出时间序列分段线性表示和特征点的定义。 定义2 - 3 时间序列的分