（系统工程专业论文）基于动态扭曲算法的时间序列部分周期模式挖掘研究.pdf

摘要 随着信息技术的飞速发展，经济、管理和金融等领域产生了大量的时间序列 数据。对于时间序列数据的挖掘越来越引起人们的高度重视，其主要目的是获取 时间序列数据中隐含的有价值的知识和信息。重复出现的周期行为在时间序列数 据中是广泛存在的，对周期模式挖掘的研究有着重要的理论价值和现实意义。由 于数据源及传输过程中存在的问题，导致实际时间序列中噪声是不可避免的，研 究噪声环境下的时间序列周期模式挖掘更具挑战性。本文基于动态扭曲距离，研 究提出一种新的部分周期模式挖掘方法，重点是处理带噪声的时间序列数据，并 应用于静态时间序列和动态时间序列( 数据流) 的挖掘。 本文首先综述了时间序列数据挖掘和周期模式挖掘的研究现状，指出目前部 分周期模式挖掘算法存在的不足。其次，给出和本文研究相关的一些定义和 c o n y 算法。第三，对于噪声环境下的静态时间序列和数据流的部分周期模式挖 掘进行深入的研究，并通过仿真数据验证本文所提算法的有效性。最后在总结全 文的基础上，指出了本文有待深入研究的问题。本文工作的创新性主要包括以下 两点： l 、提出了基于动态扭曲距离的时间序列部分周期模式挖掘算法( d t 聊) 。 本文中详细描述了d t w p 算法的原理及计算过程，给出算法应用过程中应注意 的问题，通过人工数据的仿真试验结果表明，本文所提出的d t w p 算法能对噪 声环境下的部分周期模式进行有效挖掘，不管是从算法精度上还是抗噪声能力上 都优于基于卷积的算法c o n v 。 2 、提出了适用于数据流的在线部分周期模式挖掘算法( o d t 聊) 。基于单 滑动窗的原理，改进了传统的动态扭曲距离矩阵，推导出在线周期模式挖掘算法， 并对影响算法过程的两个重要参数：窗口长度及滑动大小进行了详细研究。仿真 试验结果表明，本文所提出的o d t w p 算法能对数据流的部分周期模式进行有效 挖掘。 关键词：时间序列，部分周期模式挖掘，噪声，动态扭曲距离，在线算法 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , an u m b e ro ft i m es e r i e s d a t ae x i s ti nal o to ff i e l d s ，s u c ha s ，e c o n o m i c s ，m a n a g e m e n t ，f m a n c i a lm a r k e te t c t i m es e r i e sd a t am i n i n gh a sa t t r a c t e dm u c ha t t e n t i o nt oo b t a i nv a l u a b l ea n di m p l i e d k n o w l e d g ea n di n f o r m a t i o nf r o mt i m es e r i e s b e c a u s er e p e a t e dp e r i o d i cb e h a v i o ri s v e r yc o m m o ni nt i m es e r i e s ，i ti sm u c hv a l u a b l ea n di m p o r t a n c et os t u d yo np e r i o d i c p a t t e r n o fd a t am i n i n g d u et ot h ep r o b l e mo ft h ep r o c e s so fs o u r c eo fd a t a t r a n s m i s s i o n , n o i s ei si n e v i t a b l ei nr e a lt i m es e r i e s t h es t u d yo fp e r i o d i cp a t t e r n si n n o i s ye n v i r o n m e n ti sm o r ec h a l l e n g i n g t l l i sd i s s e r t a t i o np r o v i d ean e wm e t h o do f p e r i o d i cp a t t e r nm i n i n gb a s e dd y n a m i ct i m ew a r p i n gd i s t a n c et od e a lw i t ht h et i m e s e r i e sd a t aw i t hn o i s ea n da p p l yi tt os t a t i ca n dd y n a m i ct i m es e r i e s ( d a t as t r e a m ) d a t a m i n i n g f i r s t l y , t h i sd i s s e r t a t i o na d d r e s s e st h es t a t u so ft i m es e r i e sd a t em i n i n ga n d p e r i o d i cp a t t e r nm i n i n ga n dp o i n t st h es h o r t a g eo ft h ea l g o r i t h mo fp a r t i a lp e r i o d i c p a t t e r n sm i n i n gi nc u r r e n t t h e n , i ta n a l y s e st h ec o n c e p t i o no ft h er e l a t e dd e f i n i t i o n a n dc o n v a l g o r i t h m t h i r d l y , t h ep a r t i a lp e r i o d i cp a t t e r n sd a t am i n i n go fs t a t i ca n d d y n a m i ct i m es e r i e s ( d a t as t r e a m ) i nt h ep r e s e n c eo fn o i s ei ss t u d i e dm o r ed e e p l y b y u s i n gt h es y n t h e t i cd a t ai ne m p i r i c a ls t u d yt op r o v et h ee f f e c t i v e n e s so ft h ea l g o r i t h m w ep r o p o s e d l a s t l y , b a s e do nt h es u m m a r yo ft h ed i s s e r t a t i o n ，w ep o i n tt h ew o r kc a n b es t u d i e di nt h ef u t u r e t h em a i ni n n o v a t i v ea c h i e v e m e n t sa r ed e s c r i b e da sf o l l o w s ： 1 ) t h ea l g o r i t h mo fd t w pb a s e do nd t wt h e o r yi sp r o p o s e d t h em a i ni d e a a n dc o m p u t a t i o no fd t w p a l g o r i t h mi sd e s c r i b e di nd e t a i li np a p e ra n dt h ep r o b l e m o fc o m p u t a t i o na p p l i c a t i o ni sa l s op o i n t e d b yu s i n gt h es y n t h e t i cd a t at oc o n d u c t e x p e r i m e n t , w ef e n dt h ea l g o r i t h mw ep r o p o s e dc a nm i n ep a r t i a lp e r i o d i cp a t t e r n s e f f e c t i v e l yi nn o i s ye n v i r o n m e n t e x p e r i m e n ts h o w sb o t ht h ea c c u r a c ya n dt h e r e s i l i e n c eo fn o i s eo fd t w pa l g o r i t h mb e t t e rt h a nc o n v a l g o r i t h m 2 ) t h eo d t w pa l g o r i t h mo fd a t as t r e a m sm i n i n gi sp r o p o s e d b a s e do ns l i d i n g w i n d o wt h e o r y , w ei m p r o v et h ed t wm a t r i xt od e d u c et h eo n l i n ea l g o r i t h mo f p a r t i a lp e r i o d i cp a t t e r n sm i n i n g w ea l s os e r i o u s l ys t u d yt h et w op a r a m e t e r s ：t h e l e n g t ho fw i d o wa n dt h es i z eo ft h es l i d i n g ，w h i c ha f f e c tt h er e s u l to fo d t w p a l g o r i t h m b yt h ee x p e r i m e n t a ls t u d y , w ef i n do d t w pa l g o r i t h ms h o w st h e e x c e l l e n c eo fa c c u r a c ya n dt i m ep e r f o r m a n c e k e yw o r d s ：t i m es e r i e s ，p a r t i a lp e r i o d i cp a t t e r nm i n i n g ，n o i s e ，d y n a m i c t i m ew a r p i n g ，o n l i n ea l g o r i t h m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得丞鲞叁鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作7 眷 签字日期： 。p 夕年多月塔同 | 学位论文版权使用授权书 本学位论文作者完全了解墨鲞叁鲎有关保留、使用学位论文的规定。 特授权墨盗盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者虢尹寰 签字日期：。7 年箩月谬日 导师签名：历主跤耋 签字日期：三一7 年f 月2 公同 第一章绪论 1 1 选题背景和研究意义 第一章绪论 数据挖掘就是利用统计、机器学习、软计算方法( 包括神经网络、粗集理论、 模糊逻辑、进化计算等) 、数据库、网格技术等各个学科领域的先进技术对大量 历史数据进行分析处理，从中提取出隐含的、事先未知的和有价值的知识，为人 们的决策分析提供更高层次的技术支持。 近年来，数据挖掘( d a t am i n i n g ) 在不同领域中常常扮演着重要的角色。例 如在商业管理中的进销货管理、商品分析、客户行为分析、电子商务等，医学上 的疾病预防与治疗、医院管理等，科学上的天气预测、地震预测，或其他方面如 防治犯罪等等的相关应用。 目前数据挖掘研究已由结构化数据转向半结构化和非结构化数据，由事务数 据转向文本数据、时态数据、空间数据和多媒体数据，由同构数据转向异构数据， 由集中式数据转向分布式数据、由静态数据挖掘转向动态数据挖掘。 在人类社会的各个领域中广泛存在数据往往是按照时间顺序排列，各个观测 记录包含着时间属性，如网页服务器依序记录着使用者在每个时间点中所浏览的 网页的情况、股票价格的历史数据、网站的点击次数等等。此种数据构成的序列 称为时间序列。时间序列是反映事物运动、发展、变化的一种最常见的描述方式。 对时间序列进行挖掘，以获得有用的信息就具有非常重要的研究意义。 由于时间序列数据具有高维度，高相关性和大量噪音等独特结构，使得许多 经典的数据挖掘算法难以应用于时间序列数据挖掘中。目前，在时间序列数据挖 掘的研究工作中尚存在很多问题未解决。 重复出现的周期行为在时间序列数据中是广泛存在的，对周期模式挖掘的研 究有着重要的理论价值和现实意义。噪声( n o i s e ) 是一个测量变量中的随机错误 或偏差瞳，。由于数据源及传输过程中存在的问题，导致实际时间序列中噪声是不 可避免的，研究噪声环境下的时间序列周期模式挖掘更富有挑战性，具有重要的 理论价值和现实意义。 本文基于动态扭曲距离，研究提出一种新的部分周期模式挖掘方法，重点是 处理带噪声的时间序列数据，并应用于静态时间序列和动态时间序列( 数据流) 的挖掘。 第。章绪论 1 2 时间序列数据挖掘综述 时间序列是一组按时间顺序排列观测数据值，在现实生活中广泛存在。大量 数据集之中的数据都带有时间特征，遍及经济、气象、通信、医疗等等多个领域。 股市每日( 或月) 指数、交换机每小时的业务量、某一患者的脑电波和w e b 页的 日访问量、年太阳黑子数等等，这些都是比较常见的例子。 由于时间序列的广泛性存在，1 9 9 3 年，a g r a w a l 等人口“1 首先发表了关于时间 序列相似搜索的研究论文。随着数据挖掘研究领域的拓展，针对时间序列数据的 挖掘研究日益受到人们的关注，自从2 0 世纪9 0 年代以来发展迅速，其研究内容 涵盖了时间序列的相似模式匹配、分类和聚类、异常检测、序列模式挖掘、周期 模式挖掘等等。在数据挖掘领域内，基于时间序列的数据挖掘已经称为一个新的 热点。 l 、趋势分析 一般来说，时间序列分析的目标有两个： ( 1 ) 时间序列建模，即观察产生时间序列的机制或根本因素。 ( 2 ) 时间序列预测，即预测时间序列变量的未来值。 趋势实际上是时间序列的一个符号化、抽象化的表示。时间序列的变化趋势 反应了序列的动态特性，具有更高的使用价值。 趋势分析是由以下刻画时间序列数据的特征的四个主要成分或趋势组成： ( 1 ) 趋势或长期运动：指时间序列图在长时间间隔运动的大体方向。 ( 2 ) 周期运动或周期变化：这里涉及到周期，即关于趋势线或曲线的长期波 动，可以是也可以不是周期性的。 ( 3 ) 季节性运动或季节性变化：这些是系统或日历相关的。例子包括每年的 重现的事件。 ( 4 ) 不规则的或随机的运动t 这刻画了时间序列运动中随机的或偶然的零星 事件，例如劳动纠纷、洪水、或公司内部的人事变化。 目前的趋势分析和时间序列建模讨论都集中在以上四点。j h a n 瞄3 对季节性数 据及周期性数据进行了研究分析，并用数学的方法：自相关分析、最, j , - - 乘法及 a r i m a 进行趋势问题的探讨。 2 、相似性搜索 时间序列搜索是整个时间序列数据挖掘的基础，所有的序列挖掘工作，比如 分类、聚类，都是在搜索的基础上做进一步的研究工作。序列相似性搜索方面的 基础性工作是i 主i a g r a w a l 等h 6 1 提出的。时间序列的搜索可以分成全序列匹配问题 ( w h o l es e q u e n c em a t c h i n g ) 和子序列搜索( s u b s e q u e n c em a t c h i n g ) i b - j 题。 第一章绪论 与常规的数据库查询不同，相似性搜索寻找与给定的查询序列仅有微小差别 的数据序列。给定时间序列集合s ，子序列匹配寻找s 中的序列，它们包含与给 定的查询序列x 相似的子序列。而全序列匹配寻找s 中彼此相似的序列的集合。 子序列匹配是应用中更经常遇到的问题，时间序列分析中的相似查询对金融市场 分析( 例如，股票数据分析) 、医疗诊断( 例如，心电图分析) 和科学或工程数 据库( 例如，能量消耗分析) 是很有用的。 目前在相似性搜索工作的研究中，f a l o u t s o s 等口1 将时间序列全匹配问题推广 到子序列搜索问题。l o h 等旧1 用滑动平均变换和插值索引对f a l o u t s o s 的方法进行 了改进。针对大数据库应用，m o o n 等阳1 提出双度量( d u a lm a t c h ) 方法，基于d t w 距离进行子序列快速搜索：p a r k 等n0 1 采用概括后缀树方法；w o n g 等n 2 3 使用滑动 窗口等技术。 3 、模式挖掘 序列模式挖掘是挖掘频繁出现的有序时间或子序列。序列模式的一个例子是 “购买了数码照相机的顾客很可能在一个月内购买h p 彩色打印机”。对于零售 数据来说，序列模式在货架布置和促销方面是很有用的。这个行业，以及电讯业 和其他工业也可以将序列模式用于针对销售、顾客保持以及许多其他任务。可以 使用序列模式的其他领域包括w e b 访问模式分析、天气预报、生产过程和网络 入侵检测。注意，序列模式挖掘的多数研究集中在分类或符号模式，而数值曲线 分析通常属于时间序列分析的趋势分析和预测范畴。 序列模式问题足由a g r a w a l 和s r i k a n t 在9 5 年n3 。，基于对消费者的购买序列首 先提出来的。序列模式可以分为关联规则挖掘和序贯模式挖掘。其中关联规则挖 掘，挖掘的是给定数据集中数据项之间存在的有价值的联系n 制。描述的是交易内 部( i n t r a t r a n s a c t i o n ) 的项集之间的关联，例如，一个顾客在购买电脑的同时也会 购买软件，市场购物分析是它的一个典型应用。序贯模式挖掘描述的是交易之间 ( i n t e r - t r a n s a c t i o n ) 的关联，例如，1 0 购买计算机的客户在随后交易中会升级内存。 关联规则中采用i 拘a p r i o r i 1 特性广泛应用于时间序列序列模式的挖掘中。另一种 常用的方法是基于数据库投影的模式成长技术，不需要生成候选模式。 4 、周期性分析 时间序列周期性分析研究是在时间序列模式挖掘研究的基础上展开的。模式 挖掘的一些方法和概念在周期模式挖掘中仍然存在广泛应用，目前，时问序列周 期模式挖掘的研究集中于给出不同类型的周期模式的定义及其挖掘算法，如关联 规则周期旧1 4 1 引、部分周期模式n 6 1 9 1 、异步周期模式挖掘憎嶝3 、令人惊异的周期模 式乜3 2 们等，不同的部分周期模式的提出及其相应的挖掘算法是现在的研究重点。 目前大多数的周期性分析算法都是采用了欧氏距离( e u c l i d e a n 距离) 作为距 第，一章绪论 离度量公式，该距离公式的优点是简单、直接，可以应用于索引和聚类等数据挖 掘；缺点是作为一种静态度量，无法有效体现时间序列的动态特性，不具有多分 辨率特性，只能比较长度相同的两个序列之间的距离，而且对序列的横向、纵向 平移、压缩、拉伸敏感，不具有噪声处理能力。 动态时间扭曲距离( d t w ，d y n a m i ct i m ew a r p i n g ) 是一种新的距离度量公式， 通过寻找两个序列之间的扭曲代价最小的扭曲路径，基于动态最优的原则实现 的。该算法可以通过适时的转换、扩张和压缩实现两个序列的局部特征的比较， 允许在时间轴上有弹性的移动以便能够在两个时间序列的不同的时间阶段发现 相似的波形。动态时间扭曲最初用于语音识别领域心5 。，现在已经广泛应用于各个 领域，如生物信息，机器人技术、化学工程及医药研究等删钔，由b e r n d t 和 c 1 i f o r d ”叫引入到时间序列数据挖掘领域。与欧氏距离相比，该距离公式具有更 强的容噪能力。 目前尚无将动态时间扭曲距离公式用于时间序列周期模式挖掘中处理噪声 问题的相关文献，本文在这一方面进行了探索研究。 5 、数据流挖掘 所谓数据流就是大量连续到达的、潜在无限的数据的有序序列，这些数据或 其摘要信息只能按照顺序存取并被读取一次或有限次。在网络监控、入侵检测、 情报分析、金融服务、股票交易、电子商务、电信、卫星遥感( 气象、环境资源 监控等) 、w e b 页面访问和科学研究等众多领域中，数据以流的形式出现。由于 数据流的特殊性，短时间内有大量数据连续到达，这些数据具有随时间动态变化 的趋势，往往又是高维的。 国外在数据流挖掘方面有两个比较有影响的研究小组：一个是s t a n f o r d 大学 的r m o t w a n i 教授领导的研究小组，另一个是u i u c 的c a g g a r w a l 和j h a r t 教 授领导的研究小组。前者的研究侧重在数据流管理、数据流的连续查询和数据流 的聚类方面阳卜训，提出了不同于传统d b m s 的d s m s ( d a t as t r e a mm a n a g e m e n t s y s t e m ) 概念，他们的研究得到了美国国家自然科学基金的资助。后者的研究侧 重在数据流分析方面，对于数据流的在线分析，从聚类、分类、频繁项集挖掘以 及可视化等角度做了大量研究工作，提出了倾斜时问窗口( t i l t e d t i m ew i n d o w ) 策略，采用不同时间粒度保存数据流的信息，他们的研究得到了美国军方和国家 自然科学基金的资助。 由于数据流中的数据是不断增加的，因此，在算法处理中，完整甚至部分地 存储过去数据的方法不可行，需要能够只使用新数据就能够追踪变化的算法，这 就要求算法必须是增量式的，表示要简洁，对新数据的处理要快速，对噪音和异 常数据是稳健的。因为数据流可看成是随时间不断变化的无限过程，其随时间动 第一章绪论 态地变化导致现有的时间序列挖掘算法不能够适用。 1 3 时间序列周期模式挖掘进展综述 时间序列周期模式挖掘研究是在时间序列频繁模式研究的基础上展开的。频 繁序列模式挖掘算法用于发现在一个序列集中频繁发生的序列模式，由r a g r a w a l n l 提出。频繁序列模式挖掘的核心和难点在于识别或发现序列集中存在 的所有频繁项集，其中最著名的算法就是r a g r a w a l 提出的a p i o r i 算法h 3 。 作为频繁模式挖掘算法的延续，很多频繁模式挖掘的概念和算法在周期模式 挖掘算法中仍然在广泛应用，如频繁、置信度、a p i o r i 算法等。目前提出的这些 部分周期模式挖掘算法中，大部分聆1 仍然采用a p i o r i 算法的思想，首先生成周 期1 模式，然后基于a p r i o r i 原理或最大子模式命中集特性，找到所有的周期模式。 其中，最大子模式命中集特性是在a p i o r i 算法的基础上，对a p r i o r i 原理的改进， 二者只是在复杂模式生成过程中存在差异。 1 3 1 周期模式的分类 周期行为在时间序列中是广泛存在并具有重要应用价值，例如，可用于预测。 周期模式挖掘的目标是为了寻找具有周期行为的子序列。对周期模式进行分类能 更有效的解决周期模式挖掘中不同角度的问题。 基于模式覆盖，可将周期模式分为完全周期模式n 酗和部分周期模式n h 9 1 。 完全周期模式中每个时间都对时间相关序列的周期行为起作用( 以精确 或近似方式) 。例如：年中的每一天都近似地对该年的季节轮换起作用。 部分周期模式指定某些时间点上的行为而非全部时间点的行为。例如， 揭露某指定股票价格在每周五高和在每周二低的模式是部分周期模式。这 个模式是“部分的”，是由于它没有描述每周的任何其他几天的规律。另一 个例子是，给定一个时间序列t = a b d a b c a b b ，不是长度为3 的完全周期模式。 然而，当放宽限制，某些位置不予考虑，那么可以找到模式为a b * ，为不 关心的字符，此时的模式为部分周期模式。 基于周期的精确性，周期模式可以分为同步周期模式和异步周期模式。 同步周期模式要求事件出现在每个“稳定”周期内相对固定的偏移处， 如每天下午3 点。 异步周期模式允许事件在某种松散定义的岗期内波动。 基于周期的连贯性，周期模式可以分为完美周期模式和不完美周期模式。完 第一章绪论 美周期模式指一个周期模式的发生贯穿于序列的全过程，不中断。 设周期为p 的周期模式在长度为，的时间序列中实际发生次数为r n ，则该周 期模式的置信度为该周期模式的实际发生次数与该周期模式在该序列上的最大 可能发生次数的比值，即c o l t = 们 t p ( c o n ：1 ) ，当置信度c o i l = 1 时，该周期模 式是完美周期，否则，就是不完美周期，这里的周期模式可以是部分周期，也可 以是完全周期。 1 3 2 部分完全周期模式挖掘进展 部分周期在生活中的存在非常广泛的。比如说，我们每天早上6 ：0 0 到6 ：3 0 锻炼身体，其余的时间可能需要做工作和生活中的各种事情，那么，只有每天早 上6 ：0 0 6 ：3 0 ，我们的行为具有规律性，其它时间都是杂乱无章的，那么我们遵 循的就是一个部分周期模式。 部分周期模式是比完全周期模式更加松散的一种周期类型，但是在生活中的 存在更加广泛，因此部分周期模式的研究就更富有意义，也是当前的研究热点。 目前，数值型时间序列的完全周期问题已经被广泛研究，而部分周期研究主 要应用在符号序列中1 。尽管已经有很多方法用来挖掘完全周期模式，但是这些 算法应用于部分周期挖掘时，因为在一个部分周期当中，周期和非周期行为是混 杂在一起的6 3 引，这些完全周期挖掘算法或者不适用或者计算代价太高。 至今，有关部分周期模式挖掘大部分研究都应用t a p r i o r i 特性启发式和采用 了类a p r i o r i 挖掘方法。基于类a p r i o r i 特性的时间序列部分周期模式挖掘算法主要 有片断周期时间序列模式挖掘算法n 引、类a p r i o r i 时间序列部分周期模式挖掘算 法、最大子模式命中算法。 最近，z h e 叫等人提出了现有部分周期模式挖掘中所没有的一种类型：部分 周期关联。并提供了一种d q p c a ( p r i n c i p a lc o m p o n e n ta n a l y s i s ) 算法去寻找所 以最小部分周期关联，且只扫描时间序列一次。 在完全周期的相关研究中，o z d e n n 钉首先将时间性概念引入到时间序列频繁 模式挖掘中，提出循环关联规则挖掘算法。他所提的算法所提出的算法是部分完 全循环行为挖掘算法。 1 3 3 同步异步周期模式2 蚴脚3 挖掘进展 h 觚中提出部分周期模式的概念n 6 侧，并提出了有效挖掘部分周期模式的算 法n6 1 ，还提出了与部分周期有关的特性，如a p r i o r i 特性和最大予模式命中集特性： 第一章绪论 还首次提出了不完美周期的概念，给出了周期模式发生置信度的计算公式，只要 该周期模式的置信度大于等于一个最低限值m i l lc o i l ，那么该周期模式就是有效 周期模式；除此之外，在最大子模式命中集特性的基础上，构建了最大子模式命 中集算法，最大子模式命中集算法能够快速准确地将挖掘出来周期1 一模式合并为 复杂周期模式，l = 匕a p r i o r i 算法的效率显著提高，最大子模式命中集算法在时间序 列周期模式挖掘研究中被广泛应用。 2 0 0 5 年，文献m 1 提出了基于卷积的部分周期检测算法，将完全周期模式的 快速傅立叶变换经过改进后，引入到部分周期挖掘中，可以找到所有可能的同步 周期模式。 2 0 0 6 年，文献拍吼4 0 1 提出了密周期模式的概念，将时间序列划分为密区间，挖 掘分布于各密区间上的同步部分周期模式。 尽管h a r t n 副提出的部分周期模式算法能够发现时间序列中存在的一些周期 模式，但是当序列中存在一些扰动，或是一些数据集合缺失，或者是特定的数据 集合加入，使得周期模式的发生错位时，该算法就挖掘不出其中所包含的周期模 式。我们称这样含扰动的周期模式为异步周期模式。h a r t ；1 提出的算法只能处理 同步周期模式。即周期模式或是按照周期间隔发生的，或是在该周期间隔的整数 倍处发生。显然，异步周期模式比同步周期模式在生活中存在的更加广泛。比如 库存补充案例，最初是每个月的第一周补充感冒药物，后来由于流感爆发，库存 补充在每月的第三周增加补充一次，后来，尽管库存补充频率又恢复为每月一次， 但是补充时间却改为每月的第三周，这就形成了周期行为的异步形式。 后来，y a n g 等人瞪川提出了在阈值区间挖掘最长子序列异步周期模式的问题。 通过设置阈值来定义有效时间节和有效时间段，例如通过m i nr e p 、m a xd i s 的 最小阈值来验证序列中有效的连续时间点和时间段。y a n g 提出了异步周期模式的 概念m 1 ，较好地解决了由于扰动的存在对周期同步性的带来的破坏。但是也存在 一些问题，首先，不能够挖掘多事件时间序列的周期模式，即在一个时间点上不 能够同时发生多个事件；其次，只能挖掘模式的最长子序列，这只能抓住部分系 统行为。 k h u a n g 晗等人对其进行了改进，提出了更一般的异步周期模式挖掘算法， 可以挖掘多事件的时间序列的周期模式。其算法乜不但实现并改j , 挂- j v a n g 等人心町 的算法的全部功能，而且有效的提高了算法效率。 1 3 4 其他周期模式挖掘进展 除了常见分类的周期模式研究外，还有一些人从另外的一些角度对周期模式 第一章绪论 进行了研究。因为在一些特定的应用领域中，对于出现次数较多的模式并不会作 为一个重要的代表，例如：w e b 服务器负载记录中，服务器的状态可能非为几个 不同的等级，如，低、较低、高、较高、停止等五个状态。这些状态在一定的时 间范围内，所显示的状态波动可能会遵循一些周期的行为。像是发生低的状态几 率往往会比高的或停止的几率来得高，然而对于管理者而言，对于服务器发生停 止的情况会比发生低的情况来得更有兴趣。因此若是以以往找出次数较多的方式 去衡量样式的重要性，则这类的数据将会被遗漏掉。 因此，w a n g 等人h ，针对每个所发生的事件来指定不同最小出现次数的阂 值观念，解决事件与事件之间不容易被找出来的问题。而b e r g e r 等人提出了挖掘 时间序列数据库中非预期的周期模式，利用机率值来代替原本以出现次数的方式 来找出非预期的周期模式，作为重要的模式。在2 0 0 1 年，w e iw a n g 等人心3 1 首次 在周期模式中提出“意外”的概念，利用事件在序列中所发生的意外程度值来找 出符合的意外周期模式( s u r p r i s i n gp e r i o d i cp a t t e r n ) 。w e iw a n g 等人认为序列中 的每个事件的每次发生带有不同的权重信息，其权重与该事件每次发生的概率有 关，该算法就是用来挖掘带有概率的周期模式。后来，h h l i n h 2 1 等人利用前序 树( p r e f i x ) 的结构来帮助加快找出意外周期模式。 除了意外周期模式外，还有文献h 朝提到了一种名为时p 的新颖的周期模式。 在新颖周期模式( r p p ) 中，并非序列中的所有的点都包含在该周期模式中，且每 个r p p 周期内部都可以允许存在噪音。 1 3 5 噪声对周期模式挖掘的影响 噪声( n o i s e ) 是被测量的变量的随机误差或方差。在噪声环境中，所观察的 序列可能不能正确反应潜在行为。噪声被看作是模式挖掘过程中的挑战。 作为一个重要度量单位，置信度或支持度被广泛用来衡量周期模式的重要 性。由于噪声的存在，一个符号可能会被一些其他的符号错误地表示。这个替代 的符号可能会阻止正被发现中的模式的出现，会削弱模式的置信度。结果是，一 个频繁模式可能被噪声隐蔽了。这种现象目前在许多应用中普遍存在。 当序列模式很长时这个问题就会变得很尖锐，因为长的模式更容易被噪声所 扭曲。在y a n g 和w a n g ，h a n 等人的实验中显示，甚至只有一个中等长度的噪声， 一个频繁长的模式也有近6 0 的可能被标识为不频繁模式。此外，用支持度衡量 的模式不能检测到频繁集的问题会更严重。解决方案，利用“可能性矩阵”，去 清晰显示符号与替代符号之间的联系。一个新的度量是：匹配，被用来量化模式 的重要性且被定义为数据库中序列中的模式大量出现的次数。如果没有噪声出现 第一一章绪论 的话，模式的匹配实际上代表期望的“实际的置信水平”。 国内外关于噪声环境下的时间序列周期挖掘研究的相关文献较少。i n d y k 等 人1 发展了一个o ( n l 0 9 2 刀) 的时间算法用于解决这个问题，在这里1 1 表示时间序 列的长度。我们把这个算法叫做r e l a x 。e l f e k y 等人口6 1 提议了一个o ( n l o g 刀) 的 时间算法用于解决同一个问题。算法b 6 1 是基于卷积的，在本文中把它称做c o n v 。 在数据流前后关系中，p a p a d i m i t r i o u - 等) k 4 鄙已提出了一种叫做a w s o m 的算法， 这种算法是一种用小波的线形周期发现算法。使用“小波”去近似数据流a w s o m 算法只能发现二次幂阶的周期率。所有这三种算法瑚4 韧只能承受弱弹性的噪声。 1 4 本文的主要内容和创新点 1 4 1 本文的主要内容 本文研究了噪声环境下时间序列部分周期模式挖掘问题，主要是基于动态时 间扭曲原理( d y n a m i ct i m ew a r p i n g ) ，提出一种新的部分周期模式挖掘方法，并 应用于静态时间序列和动态时间序列( 数据流) 的部分周期模式挖掘中，主要内 容如下： 第一章，为绪论部分，介绍了本文的选题背景及研究意义、时间序列数据挖 掘研究进展，重点阐述了时间序列周期模式挖掘研究进展，指出目前部分周期模 式挖掘算法对噪声处理存在的不足，综述了本文的主要内容和创新点。 第二章，作为全文的理论基础，详细介绍了本文的相关定义和算法，给出了 时间序列、周期模式、周期段、匹配、置信度、部分周期、段周期等重要概念的 定义，给出了时间序列中相似性度量常用的三种距离：欧式距离、海明距离和动 态扭曲距离，重点分析了动态扭曲算法原理、计算过程和特点。同时，也介绍了 基于卷积的部分周期模式挖掘算法( c o n v 算法) ，这个算法将于下章中的提出 的d t w p 算法进行比较。 第三章，提出了基于动态扭曲距离的时间序列部分周期模式挖掘算法 ( d t 岍) ，在卷积平移挖掘周期思想的基础上，利用d t w 距离能有效处理时间 轴的平移、拉伸和变形的优势，结合d t w 距离矩阵的特点，提出一种新的时间 序列部分周期模式挖掘算法，指出d t w p 算法应用过程中的注意点。仿真试验 结果表明，d t w p 算法能在噪声环境下对部分周期模式进行有效挖掘，显示了较 好的算法精度和抗噪性能，各项算法指标都优于基于卷积的c o n v 算法。 第四章，提出了适用于数据流的在线部分周期模式挖掘算法( o d t w p ) ，考 虑数据流是实时、快速、有序和只能被读取一次或者几次的特点，对在线部分周 第，一章绪论 期模式挖掘进行了研究。基于单滑动窗的原理，改进了传统的动态扭曲距离矩阵， 推导出在线周期模式挖掘算法，并对影响算法过程的两个重要参数：窗口长度及 滑动大小进行了详细研究。仿真试验结果表明，o d t w p 算法能对数据流的部分 周期模式进行有效挖掘。 第五章，总结全文，并提出展望。 1 4 2 本文的创新点 本文基于动态扭曲距离，研究提出一种新的部分周期模式挖掘方法，重点是 处理带噪声的时间序列数据，并应用于静态时间序列和动态时间序列( 数据流) 的挖掘，主要创新点如下： 1 、提出了基于动态扭曲距离的时间序列部分周期模式挖掘算法( d t 岍) 。 本文中详细描述了d t w p 算法的原理及计算过程，给出算法应用过程中应注意 的问题，通过人工数据的仿真试验结果表明，本文所提出的d t w p 算法能对噪 声环境下的部分周期模式进行有效挖掘，不管是从算法精度上还是抗噪声能力上 都优于基于卷积的算法c o n v 。 2 、提出了适用于数据流的在线部分周期模式挖掘算法( o d t w p ) 。基于单 滑动窗的原理，改进了传统的动态扭曲距离矩阵，推导出在线周期模式挖掘算法， 并对影响算法过程的两个重要参数：窗口长度及滑动大小进行了详细研究。仿真 试验结果表明，本文所提出的o d t w p 算法能对数据流的部分周期模式进行有效 挖掘。 第二章本文相关定义及算法介绍 第二章本文相关定义及算法介绍 作为时间序列部分周期模式挖掘的理论基础部分，本章给出了时间序列、周 期模式、周期段、匹配、置信度、部分周期、段周期等相关的基本概念。在此基 础上，重点介绍了动态扭曲距离( d y n a m i ct i m ew a r p i n g ) 的原理及算法过程， 同时介绍了基于卷积的部分周期模式挖掘算法( c o n v ) ，并将于下章与本文所 提出的算法进行比较。 2 1 时间序列 定义2 - 1 时间序列( t i m es e r i e s ) 3 ：设t 为某个时间集，对t t ，工，为随机 变量。对全体工，( f t ) ，当t 为离散集时，t = 1 2 ， 或t = 1 , 2 ，刀 ，称 x t ) 是 随机序列。 x t ) 中的t 一般代表等间隔的时间增长量，称随机序列) 为时间序列。 这里的“时间”具有广义坐标轴的含义，指按时间的先后顺序排列的数据， 例如产品销售记录数据、股票价格数据、水温记录数据等h7 1 。时间序列是一类复 杂类型数据，它的显著特征是：对象之间保持着严格的时间顺序h 引。 在一个时间序列中可得到一个具有n 个时间标记性的特征值的序列。对于一 个给定的特征e ，e ，表示e 在时间点i 的值，特征e 的时间序列可表示为： t = e o ，e z ，巳一，。例如在能源消耗的时间序列中的特征可能是某顾客的时能源消 耗率，而在股票价格的时间序列中的特征可能是某特定公司的日收盘股票价格。 若把时间序列的特征值离散化为几个不相关的水平并用符号( 口，b ，c ，等) 表示， 特征值的集合可表示为：= l 口，b ，c ，。这样丁可以看成足由有限的字母表中 的刀个符号组成的序列。 除了具有特征值的时间序列外，时间序列也可以是事件类型的有限集合中的 刀个时间标记性事件组成的序列。如在计算机网络中监测各种事件的事件日志。 每个事件类型可用符号去表示( 例如，a ，b ，c 等) 。时间序列可被看作由有限 的字母表z 中的，1 个符号组成的序列。此时，这样的时间序列称之为数据流。 定义2 - 2 数据流( d a t as t r e a m ) h 9 1 ：是指一系列连续且有序的点组成的序 列，按照固定的次序，这些点只能被读取一次或者几次。 一个标记为s 的数据流，虽然是无穷的，但有着跟时间序列相同的符号。一 个数据流可被认为是有限字符集中无限长度的序列旧”。 第二章本文相关定义及算法介绍 2 2 相似性度量 相似性度量是衡量两个序列相似性的依据或标准，是相似性查找的基础。重 新描述的目的是能够更加快速准确地实现相似性度量。主要的度量方法如下所 示。 2 2 1 欧式距离 时间序列是一类重要数据对象，在经济、气象很多领域都大量存在，对这些 数据进行分析，可揭示事物变化和发展的规律。大多数的相似性度量采用了 e u c l i d e a n 距离或者是与距离相关的某种形式。快速傅立叶分析以及小波分析等 工具能够进行有效的特征提取，使得l p 距离可以使用快速的索引技术。对给定 的长度相等的序列x 和y ，他们之间的与距离定义为： 啦耻1 x ；- y , i p r ( 2 1 ) 其中，n 表示时间序列的长度。当p = l 时，就是m a n h a t t a n 距离：当p = 2 时， 是应用最广泛的e u c l i d e a n 距离，也是最简单，最直接的一种。 近来，h a n 等人介绍频繁模式挖掘及聚类算法：d a s 等人介绍了如何从时间 序列中发现关联规则；k e o g h 和p a z z a n i 婿提出一种可伸缩的时间序列分类算法。 所有这些工作的前提都是要比较时间序列间的相似性，一般采用的是欧式距离及 其变形。 e u c l i d e a n 距离以及几乎全部其他的相似性定义，都隐含要求待匹配计算的 两个序列长度是相同的。然而在实际的工业数据中，由于不同对象的变化速度不 同，使得类似变化过程的采样数据长度差异很大。例如，如果水温控制中一个阶 跃干扰过程数据长度为2 0 0 ，而蒸汽压力阶跃干扰过程数据长度可能只有1 0 0 。 但他们有可能具有相同的变化过程，这就无法采用等长序列距离比较他们之间的 相似性。 然而欧式距离对序列在时间轴上的轻微变化非常敏感，一些轻微的变化可能 会使得序列之间的欧式距离变化很大。对一些实际的时