（计算机应用技术专业论文）基于数据流的时间序列异常数据挖掘的研究.pdf

浙汀理工大学硕上学位论文 摘要 基于数据流的时间序列异常数据挖掘可以用于交通领域的道路推荐、供水领域的管网 监测以及证券、医疗、环保、电力等行业的检测和预报工作。这些领域产生的数据有着明 显的时间序列的特征，同时还具有数据量大、结构复杂、实时性要求高等特点。如果仪使 用传统的理论和方法分析这些数据，往往因为计算能力、存储能力以及算法的不足而显得 无能为力。数据流挖掘理论和技术的引入为解决上述问题提供了新的思路，越来越成为国 内外研究者所关注的热点。 目前，时间序列的数据挖掘主要包括相似性查询、分类、聚类和异常检测等。论文围 绕数据流环境下时间序列异常数据挖掘这一主题，以时间序列的模式表示为基础，讨论了 时间序列数据预处理和压缩存储，提出了一种基于数据流的时间序列异常检测算法，并根 据现实生活中多维数据流的需要和对历史数据的分析，将原算法进行了改进，最终确定了 改进的基于数据流的时问序列异常检测算法。主要的研究内容和成果包括： 1 时间序列的模式表示 论文将解析几何中的线段概念和现实生活中的基本时间窗口引入到时间序列的研究 中来，提取线段的斜率作为确定时间序列分段线性表示的分段点选取的依据，提出了一种 基于基本窗口和斜率的分段线性表示方法( 简称为p l rb w s 表示) 。时间序列的 p l rb w s 表示方法简单直观，对于具有明显周期特征和短期模式波动频繁等特点的时间 序列具有很强的数据压缩能力，从而能较好地保持时间序列总体模式的变化特征。 2 时间序列的异常检测 在时间序列的模式表示基础上，论文提出了基于滑动窗口的时间序列窗口异常的定 义，同时给出了流数据环境下的基于滑动窗口的时间序列异常检测算法( 简称t o d s w ) ， 采用“窗口异常度”来衡量时问序列上当前窗口的异常程度。与其他异常数据挖算法相比， t o ds w 不需要训练，满足了数据流的实时性要求，在模式表示的基础上算法又一定程 度的降低了存储要求和i o 操作。只要合理地调整参数，算法总是能够及时、有效地检测 出当前时间序列的异常行为。 关键词：数据流；时间序列；数据挖掘；模式表示；异常检测 基于数据流的时问序列异常数据挖掘的研究 r e s e a r c ho fo u t l i e rd a t am i n i n gi nt i m es e r i e sb a s e do nd a t as t r e a m a b s t r a c t o u t l i e rd a t am i n i n gi nt i m es e r i e sb a s e do nd a t as t r e a mc a nb eu s e dt or o a dp l a n n i n gi n t r a n s p o r t a t i o n ，n e t w o r km o n i t o r i n gi nw a t e rs u p p l y , a sw e l la sd e t e c t i o na n dp r e d i c t i o ni n i n d u s t r i e ss u c ha ss e c u r i t i e s ，m e d i c a l ，e n v i r o n m e n t a lp r o t e c t i o n ，e l e c t r i c i t y ，e t c d a t ag e n e r a t e d f r o mt h e s ef i e l d sn o to n l yh a v et h ec h a r a c t e r so ft i m es e r i e s ，b u ta l s ov a s td a t a ，c o m p l e x s t r u c t u r e sa n dh i g hr e a lt i m ed e m a n d d u et ot 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 y a n da l g o r i t h m s ，i ti sa l w a y sd i f f i c u l tt oa n a l y z et h e s ed a t au s i n go n l yt h et r a d i t i o n a lt h e o r i e sa n d m e t h o d s t h ei n t r o d u c t i o no fd a t as t r e a mm i n i n gp r o v i d e san e ww a yt os e t t l et h e a b o v e - m e n t i o n e dp r o b l e m ，w i t hi n c r e a s i n gi m p o r t a n c ea t t a c h e db yr e s e a r c h e r sf r o mb o t ha t h o m ea n da b r o a d a tp r e s e n t ，d a t am i n i n go ft i m es e r i e sm a i n l yi n c l u d e ss i m i l a r i t yi n q u i r i e s ，c l a s s i f i c a t i o n ， c l u s t e r i n g ，o u t l i e rd e t e c t i o n ，e t c b a s e do nt 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 ，t h ed a t a p r e p r o c e s s i n ga n dc o m p r e s s i o ns t o r a g eo ft i m es e r i e sw e r ed i s c u s s e di nt h i sp a p e r i tw a s f o l l o w e db ya ni n i t i a la l g o r i t h mf o rt i m es e r i e so u t l i e rd e t e c t i v eb a s e do nd a t as t r e a m t a k i n g i n t oa c c o u n tt h er e q u i r e m e n to fm u l t i d i m e n s i o n a ld a t as t r e a mi nr e a ll i f ea n db yt h ea n a l y s i so f h i s t o r i c a ld a t a ，a ni m p r o v e da l g o r i t h mf o rt i m es e r i e so u t l i e rd e t e c t i v eb a s e do nd a t as t r e a mw a s u l t i m a t e l ya c h i e v e d t h er e s e a r c hw e r ea l la r o u n dt h e m e so f t h eo u t l i e rd a t am i n i n gi nt i m e s e r i e sb a s e do nd a t as t r e a m ，w h i c hc o n s i s to ft h ef o l l o w i n g ： 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 t h ec o n c e p t i o no fl i n ei na n a l y t i cg e o m e t r ya n db a s et i m ew i n d o wi nr e a ll i f ew e r e i n t e g r a t e di n t ot h er e s e a r c ho ft i m es e r i e si nt h i sp a p e r t h es l o p eo fal i n ew a se x t r a c t e da st h e b a s i so fd e t e r m i n a n t st os e l e c tp 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 ss u b p o i n t so ft i m es e r i e s a 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 nb a s ew i n d o wa n ds l o p ew a sp r o p o s e d ，w h i c hw a s a b b r e v i a t e da s “p l r b w s ”p l r b w so f t i m es e r i e si ss i m p l ea n di n t u i t i v e m o r e o v e r , i th a s as t r o n gd a t a c o m p r e s s i o nc a p a b i l i t y f o rt h o s et i m es e r i e st h a th a v ee v i d e n tc y c l i c c h a r a c t e r i s t i c so rw i t hf r e q u e n tf l u c t u a t i o n si ns h o r t - t e r mp a t t e r n s a ss u c h ，i ti sc a p a b l eo f m a i n t a i n i n gt h ec h a n g i n go v e r a l lp a t t e r no ft i m es e r i e s 2 浙江理工大学硕上学位论文 2 o u t l i e rd e t e c t i v eo ft i m es e r i e s 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 ed e f i n i t i o no fw i n d o wo u t l i e ro ft i m e s e r i e sb a s e do ns l i d i n gw i n d o ww a sg i v e n ，a l o n gw i t ht h ea l g o r i t h mo ft i m es e r i e so u t l i e r d e t e c t i v eb a s e do ns l i d i n gw i n d o w ( d e n o t e da s “t o d s w ”) i nt h ee n v i r o n m e n to fd a t as t r e a m w i n d o wo u t l i e rd e g r e e w a sa d o p t e di nj u d g i n gt h eo u t l i e rd e g r e eo fc u r r e n tw i n d o wi nt h e t i m es e r i e s c o m p a r e dw i t ho t h e ro u t l i e rd a t am i n i n ga l g o r i t h m s ，t o d s wm e e t st h er e a l t i m e d a t as t r e a mr e q u i r e m e n t sb yi t sn e e d l e s s n e s sf o rt r a i n i n g f u r t h e r m o r e ，t h i sp a t t e r n r e p r e s e n t a t i o nb a s e da l g o r i t h mr e d u c e st h es t o r a g er e q u i r e m e n t sa n d i oo p e r a t i o nt oac e r t a i n e x t e n t a sl o n ga sr e a s o n a b l ea d j u s t m e n t st ot h ep a r a m e t e r sa r em a d e ，t h ea l g o r i t h mc a na l w a y s d e t e c tt h ea b n o r m a lb e h a v i o ro fc u r r e n tt i m es e r i e st i m e l ya n de f f e c t i v e l y k e y w o r d s ：d a t as t r e a m ；t i m es e r i e s ；d a t am i n i n g ；p a t t e r nr e p r e s e n t a t i o n ；o u t l i e rd e t e c t i v e 浙江理工大学学位论文原创性声明 本人郑重声明：我恪守学术道德，崇尚严谨学风。所呈交的学位论文，是本人在导师 的指导下，独立进行研究工作所取得的成果。除文中已明确注明和引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写过的作品及成果的内容。论文为本人亲自撰 写，我对所写的内容负责，并完全意识到本声明的法律结果由本人承担。 学位论文作者签名：t 乡名、季纵 日期- 沁学年弓月。7 日 浙江理工大学学位论文版权使用授权书 学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家 有关部门或机构送交论文的复印件和电子版，允许论文被查阅或借阅。本人授权浙江理工 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 保密口，在 不保密口。 学位论文作者签名：童声考钦 吼研年多月，7 日 年解密后使用本版权书。 指黝f 婚秘 指导教师签名：7 。i 醐：加蛑朋7 日 浙江理工大学硕上学位论文 1 1 课题的背景、目的及意义 第一章绪论 金融、电信、工农业生产及科学实验等各个领域每时每刻都在产生海量的数据，这些 数据中大多数是对和时间相关历史数据的记录，我们称之为时态数据( t e m p o r a ld a t a ) 。时 态数据既可以指按时间的先后顺序排列的数据，也可以指按空问的前后顺序排列的随机数 据。根据记录数据的类型的不同，时态数据主要可以分为三类，即时间序列、事务序列 和事件序列【2 】。所谓时间序列就是按照时间先后顺序排列的各个观测记录的有序集合，其 中观测记录是数值类型的。时间序列数据在金融、交通、电力等各个行业都大量存在。比 如股票市场上每天都在波动的股票价格，它的背后存在着时序关系；道路上行驶的车流， 有着一定的时序关系；人们生活中离不开的电力，它的使用情况也存在着时序关系。 传统时问序列的研究工作主要采用的是概率统计学方面的方法，经过长期的发展，理 论基础完备，并在实际工作中起着重要的作用【3 】。然而它主要的研究方法是全局模型，研 究的对象是随机性的动态数据，并且对时间序列的要求相对较高( 如自回归滑动平均模型 a r m a 4 】要求时间序列必须是平滑的，同时模型产生的时间序列与实际产生的时间序列的 误差不相关并呈正态分布) ，并不能适应绝大多数实际系统所产生的时间序列。此外，传 统的研究分析主要是一种验证工作，而当今我们已不满足于验证，我们需要的是对系统整 体的把握及预测。比如关心某个周期内出现的频繁模式，比较不同序列在某个周期内的运 动模式是否相似，关注某个时间序列产生的异常情况等等。现实生活中不乏这样的例子： a ) 在股票市场，短线操作关心的是某个相当短的时间周期内股票的走势，并对未来 短期内的走势进行预测判断；而长线操作关心的是整体的走势。 b ) 开车出门的时候，用户关心的是当前及未来短期内的道路通行情况，并希望系统 能比较多条道路通行情况，推荐合适的通行道路。 c ) 医院的设备仪器希望能检测或者预测出被检查人员的病情，及时将该病情通知他 们，以便能得到及时、妥善的治疗。 对于上述实例，传统的时间序列研究方法已不能适应，势必要求有新兴的理论和技术 来满足它的需要，这就是数据挖掘技术。数据挖掘技术是从上世纪9 0 年代初发展起来的 门学科，到目前为止已经建立了一套比较完备的体系。当前，它又有新的发展方向，那 基于数据流的时问序列异常数据挖掘的研究 便是数据流挖掘。 一般我们把具有以下几个特征的数据称作数据流或流数据： 1 数据量一般是随时间无限增氏的。 2 数据是实时产生的。 3 无法对数据产生的速度和规模进行预测和控制。 4 一项数据处理过后就会被丢弃或者压缩存档，无法对历史数据进行随机访问。 由于数据流的这些特点，大多数传统的数据处理技术无法快速有效地处理数据流中的 数据。通过研究，绝大多数学者都认为一个系统或者算法如果要很好地处理这类数据量巨 大、永无止境的数据流，至少必须满足以下几点要求： 处理数据流中每条记录必须只使用很短且恒定的时间，否则将会跟不上数据到来 的速度； 只能使用固定大小的内存空间，与已经处理过的数据量的大小无关； 只需要对数据进行一次扫描，因为在大多数应用中，或者无法得到历史数据，或 者根本没时间去访问历史数据； 必须能够在处理的任何阶段输出可用的结果，而不是等到处理完所有的数据后才 输出结果，因为我们可能永远到达不了数据的尽头； 理想情况下，应该能够得到一个与传统算法在没有任何约束条件下在相应的静态 数据集上得到的结果相同或者近似的结果； 当数据流的模型发生变化时，计算的结果必须也要能够及时得到调整，反映数据 的变化。 这些要求看上去很难达到，但是只有这样才能真正有效地处理大规模的数据流上的数 据。在一些特殊的情况下，如果数据流的规模不是很大，产生的速度也不是很快，而且硬 件设备的存储和计算处理能力远远超过数据流中的数据量的时候，可以放松其中的几点要 求。但在时间复杂度和空间复杂度上算法还是要满足一定的要求，即：时间复杂度最好和 数据量的大小呈线性关系；空间复杂度最好和数据量的大小无关，或者要保持在对数关系 之内。 本课题是围绕着数据流环境下的时间序列异常数据挖掘展开的，它有着广泛的应用前 景： 在交通领域，道路推荐系统通常将路口饱和度作为畅通指标，然而如果道路中发 生交通事故，路口的饱和度是降低了，但实际上这条道路并不是畅通的。如果通 2 浙汀理工大学硕士学位论文 过时间序列的异常数据挖掘能判断出道路的畅通与否，则就能进一步提高道路推 荐系统的正确率。 在供水行业，如果大口径水管破裂而不能及时维修，将给人们的生活和出行带来 极大的不便。如果能采用监控系统的时问序列异常数据挖掘技术而进行及时维修， 就能减少人们生活不便的时间，给国家挽回大量的损失。 在医疗、环境保护、电力和天然气等行业的检测和预报工作。 1 2 国内外的研究现状及发展动态 时间序列上的数据挖掘研究伴随着数据挖掘的兴起而迅速发展，其研究内容包括时间 序列上的相似性查询、模式挖掘、分类和聚类、异常检测等。时间序列上的异常检测是近 年来数据挖掘的研究热点之一。到目前为止，学术界还没有一个公认的异常时间序列的定 义，根据不同的假设，各类研究人员提出了不同的定义。和异常相关的定义还有新颖 ( n o v e l 5 ，6 1 ) 、不规则( a n o m a l y 7 1 ) 、奇异( s u r p r i s e t 8 】) 等。相对于单个点的异常研究， 时间序列异常研究的是一个时间段的异常。下面将简要描述下国内外时间序列的研究现状 及发展动态。 国外很早【9 一0 1 就开始了时问序列的异常检测研究工作，近年又出现了许多新的观点和 研究方法。 文献 8 提出了t s a - t r e e 的改进型来实现奇异模式的查询，他们把奇异模式定义为 时间序列上的突然变化，通过小波系数的局部极大值来发现。但是他们对奇异模式的定义 是建立在小波系数的基础上，因此不够准确和全面，有些奇异模式无法发现】。 文献 1 2 采用可增量学习的概率模型( 比如a r 模型) 对历史时间序列数据建模，能 够动态适应新的数据，渐渐遗忘历史数据。给新到来的序列点与模型的偏差度打分，分高 的认为是高概率异常。不过他们也是针对异常点的检测，不是异常序列。他们还提出了异 常发现算法，需要满足的两个条件：( 1 ) 异常发现算法必须足在线的，一旦发现异常，就 能立刻发现；( 2 ) 异常发现算法必须适应动态变化的非稳定数据环境。 文献 1 1 提出了线性时问和空间范围下的奇异模式( s u r p r i s ep a t t e m ) 发现。如果一 个模式的出现频率与它的期望出现概率显著差异时，认为它是奇异模式。该定义的优点在 于奇异模式的定义不需要借助领域专家知识，一般用户也能发现奇异模式。他们提出了 t a r z a n 算法，采用后缀树来编码所有出现的模式，用马尔科夫模型预测未现模式的期望出 现概率。 3 基于数据流的时问序列异常数据挖掘的研究 文献 5 ，6 提出基于支撑向量回归( s u p p o r tv e c t o rr e g r e s s i o n ，s v r ) 模型的算法， 可以在线发现时态序列的新颖事件。采用s v r 模型对历史时间序列建立回归模型，判断新 到来的序列点与s v r 回归模型的匹配程度，考察连续一段时间内的匹配情况，给出其为 新颖事件的置信度。建立回归模型时采用时延嵌入过程( t i m e - d e l a y e de m b e d d i n gp r o c e s s ) 得到训练样本集，s v r 回归模型可增量更新。 国内对于时间序列和异常检测的研究起步较晚，虽然近年发展很快，但基于时间序列 的异常检测的研究工作仍然相对缺乏。 文献 1 3 提出了基于时间序列模式表示的模式异常方法。并不直接对时间序列本身的 序列点进行异常判别，而且用时间序列的模式表示代替时间序列，判断时间序列的模式是 否异常，提高了异常检测的准确率和效率。提出了基于模式密度的异常检测算法( t o d ) ， 无需训练，并支持时间序列的动态更新。但该算法并不支持多维度的情况，不能满足实际 应用的需要。 文献 1 4 - 1 6 将序列挖掘了应用到异常检测，但基本上研究的都是基于事件序列入侵 检测。 总之，国内外对序列时间异常检测都做了不少的工作，但总的来说研究还是零散的， 存在的分歧和争议比较多，远未达到系统研究的深度。 1 3 本文的工作 1 3 1 研究内容和成果 论文主要围绕数据流环境下时间序列异常数据挖掘这一主题，以时问序列的模式表示 为基础，讨论了时间序列数据预处理和压缩存储，提出了一种基于数据流的时间序列异常 检测算法，并根据现实生活中多维数据流的需要和对历史数据的分析，将原算法进行了改 进，最终确定了改进的基于数据流的时间序列异常检测算法。其关系如图1 1 所示。 论文的主要研究内容和创新工作简单介绍如下： ( 1 ) 时间序列数据流的模式表示 数据流有着明显的时间序列特征，为了研究复杂而海量的数据流，通常研究的对象并 不是原始时问序列数据流，而是将时间序列数据流通过各种方法表示后加以研究。文章采 用了一种基于基本窗口和斜率的分段线性模式表示方法来表示时间序列，不但对实时采集 的数据流进行了预处理，而且对海量的数据流进行了一定程度地压缩，有效地减少了数据 4 浙江理工大学硕上学位论文 挖掘所需要的存储空间和计算量。 基于数据流的时间序列数据的异常数据挖掘的改进 图1 1 论文研究内容的关系图 ( 2 ) 时间序列数据流的异常检测 人们通常关心的是最近的时问序列数据流信息，因此文章采用了滑动窗口策略来挖掘 异常数据。窗口的滑动策略是每经过一个基本窗口时间，就向前滑动一个基本窗口，于是 异常的时间序列也就是在所有滑动窗口的基本窗口中进行挖掘。在引入滑动窗口策略之 后，论文提出了一种基于数据流的时间序列异常检测算法。随着基本窗口的不断滑出，历 史信息也不断地积累，为了进一步提高异常时间序列数据挖掘的精确度，文章将滑动窗口 策略和历史信息指数衰减相结合，提出了一种改进的基于数据流的时间序列异常检测算法 并将其推广到多维数据流的情况，在不增加算法执行时问的同时有效地提高了数据挖掘的 精确度，更适应于现实中流数据的异常数据挖掘。 1 3 2 组织结构 全文共分5 章，简单介绍如下： 第一章：绪论 首先介绍了基于数据流的时问序列异常数据挖掘的背景、目的及意义，接着介绍了本 课题的国内外研究现状及发展动态，最后简单介绍了论文主要的研究内容和研究成果。 第二章：基于数据流的时间序列模式表示 首先介绍了几种常见的时间序列的模式表示方法，比较他们各自的优缺点。提出了一 基于数据流的h 寸问序列异常数据挖掘的研究 种基于基本窗口和斜率的分段线性表示( 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 nb a s e w i n d o wa n ds l o p e ，p l rb w s ) 方法，并与其他几种分段线性表示方法进行了比较。 第三章：基于数据流的时间序列异常数据挖掘 首先介绍了几种常见的时间序列异常类型，在时间序列的模式表示基础上，提出了一 种基于滑动窗口的时间序列窗口异常定义，用“窗口异常度”来描述模式的异常程度。根 据时间序列的窗口异常定义，提出了基于滑动窗口的窗口异常检测算法( t i m es e r i e so u t l i e r d e t e c t i v eb a s e do ns l i d i n gw i n d o w ，t o d s w ) 。 第四章：基于数据流的时问序列异常数据挖掘的改进 简单介绍了几种常见的历史信息存储策略，通过比较采用指数衰减策略将历史基本窗 口的信息加以利用。对原先的基于数据流的时间序列异常检测算法进行了改进并将其推广 到多维数据流的情况，提出了一种改进的基于滑动窗口的窗口异常检测算法。 第五章：总结与展望 总结了全文的研究工作，并对以后所要进一步研究的工作进行了展望。 6 浙汀理工大学硕士学位论文 2 1 引言 第二章基于数据流的时间序列模式表示 时间序列就是按照时问先后顺序排列的各个观测记录的有序集合，其中观察记录是数 值类型的。时间序列数据在金融、交通、电力等各个行业都大量存在，典型的例子包括股 票每天的收盘价、某地区的降雨量、道路交通系统中的车流量等。随着时间的推移，这些 复杂数据也不断地积累，并朝着海量的方向发展。如何对这些海量时间序列数据进行统计、 分析，从中发现有用的信息，进而预测事物的发展动态，一直以来都是人们感兴趣的问题。 数据流有着明显的时间序列特征，为了研究复杂而海量的数据流，通常研究的对象并 不是原始时间序列数据流，而是将时间序列数据流通过各种方法表示后加以研究。这是因 为一方面由于大多数数据挖掘算法并不适应时间序列的超高维数，海量的数据量又将使得 直接在时间序列上进行数据挖掘在存储和计算上要花费巨大的代价；另一方面时间序列数 据容易受外界的噪声干扰而产生误差，这就可能会影响数据挖掘算法的准确性和可靠性。 将时间序列数据流通过各种方法表示以后，可以仅仪考虑原时间序列的主要形态，忽 略那些细小而不改变性质的变化。其优势可以描述如下： 对时间序列进行了一定程度的压缩，减少了数据量，有利于数据挖掘的存储和计算； 去除了时间序列的部分噪声，保留了时间序列的主要形态，降低了误差对数据挖掘的 影响，有利于数据挖掘效率和精准度的提高； 从对时间序列时间点的分析过渡到时间序列时问段的数据挖掘，更符合大多数领域所 关心一段时间内的数据变化模式和规律。 2 2 相关定义 本节将给出时间序列正式的数学形式描述及相关术语的记号和定义【4 1 。在论文的其它 章节，如不特别说明，将沿用以下的相关术语的记号和定义。 定义2 1 时间序列 时问序列是由一系列元素组成的有序集合，这些元素本身由记录时刻和记录值构成， 记为x = ( x 。= o 。，) ，x ：= 0 ：，v ：) ，= o 。，v 。) ) ，其中元素x ，= 0 ，u ) 表示在如时刻取得记 7 基于数据流的时问序列异常数据挖掘的研究 录值为v i ，这里记录时刻t i 是严格单调增加的，即f j t ， t ，。 通常w j - f 百j 序列的记录时问问隔a t = t f + l t ，是相等的，于是对于上述时间序列可以取 t 。= 0 ，a t = l ，那么时间序列x = ( = o 。，v 。) ，x ：= o ：，v ：) ，x 。= o 。，叱) ) 可以简记为 x = ( x iz ：，x 。) 。i x l 称为时间序列x 的模，表示时间序列的长度，即元素x 的数量。 对于广义时间序列，记录值v i 可以是离散符号、结构数据、多媒体数据等，但当前论文 只采用狭义的时间序列，即1 ，的取值为实数类型。 定义2 2 时间序列的模式表示 设有时间序列x = ( x 。，x ：，x 。) ，其模式是指该时间序列的某种变化特征。时间序列 的模式可以是该时间序列在一段时间的均值或者中值，也可以是时间序列离散化后的符 号，甚至可以是时间序列的傅立叶变换系数。 通过提取时间序列的模式，可以将时问序列变换到模式空间，于是就得到了时间序列 的模式表示。用符号定义如下： x ( f ) = ( w ) + p 0 ) ，f n + 。 ( 2 1 ) 其中，w 是时间序列的模式，以w ) 是时间序列的模式表示，p ( 力是时间序列的模式和它的模 式表示之间的误差。 时间序列的模式表示能够压缩数据，保留时间序列的主要形态，忽略其中的微观细节， 给进一步的研究工作提供方便。图2 1 是2 0 0 6 年日本上河原地区某取水点浊度记录信息 时间序列，共有8 6 8 8 个记录信息；图2 2 是该时间序列的一个模式表示，它只需要保 留1 0 4 5 个记录信息，不但压缩率达到了8 7 9 7 ，而且很好地保持了原始时间序列的主要 形态。 图2 12 0 0 6 年日本上河原地区某取水点浊度记录信息 8 浙江理工大学硕士学位论文 图2 22 0 0 6 年日本上河原地区某取水点浊度记录信息分段线性表示 2 3 常见的时间序列模式表示 2 3 1 符号表示法 符号表示法就是要把由实数组成的时间序列用符号序列表示。它是近几年提出的时间 序列近似表示的方法之一，因其离散化、非实数表示的特点得到越来越多的关注。 符号化方法主要可分为两大类【1 8 】：一类足对时间序列不作任何预处理，直接根据序列 的数值特点进行符号划分，可以称之为直接法，主要包括静态法，动态法，以及综合法； 另一类是首先对时间序列做适当变换，然后再划分，可以称之为问接法，主要有小波空间 法。 p a r k 等人 1 9 - 2 0 1 采用等宽离散化和最大墒离散化方法将时间序列的实数值映射到有限的 符号，以后缀树为索引，提出了一种动态时问弯曲距离的下界距离( l o w e rb o u n d i n g d i s t a n c e ，l b d ) ，在提高查询效率的同时保证了查询的完备性，他们的工作使得基于符号 化表示的时间序列相似性查询能够支持比欧式距离更鲁棒的动态时间弯曲距离。 e a m m o n 2 1 1 在分段集成近似( 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 ，p a a ) 基础上提出了 一种新型符号化方法( s y m b o l i ca g g r e g a t ea p p r o x i m a t i o n ，s a x ) 。其基本思想是首先将原 始时间序列正规化，然后利用p a a 对长度为i q 的时间序列降维，得到n ( n n ) 维的时间序列， 最后将降维后的序列值离散化为m 个等概率的区间，并将处于同一个概率区问的序列值用 同一个符号表示，实现了时间序列的符号化表示。s a x 与其它符号化方法相比有以下的优 点：( 1 ) 简单、易用且算法不依赖于具体实验数据；( 2 ) 在符号化的过程中实现了降维 ( n k ) 的时 间序列。 线性分段存在两个关键问题：一个是如何选择合适的线段数目；另一个是如何选择合 基于数据流的时间序列异常数据挖掘的研究 适的分段点。根据对这两个问题的不同解决方法，可以将线性分段算法分为以下三种类型： ( 1 ) 限制分段数k ：给定时间序列，产生的p l r 只包括k 条直线段。 文献【4 0 和【4 l 】分别独立提出了时间序列的分段聚集近似( p i e c e w i s ea 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 o g h 等人的实验表明， 将p a a 方法用于时间序列的索引，使得相似性查询的效率比d f t 表示方法提高了l 一2 个 数量级【4 0 1 。 ( 2 ) 限制分段误差：不规定分段的数目，通过控制分段误差来选择合适的分段点。 限制分段误差的方式主要有两种：一种是给定时间序列，产生的p l r 中每个分段的 最大误差不超过某个用户指定的误差阈值m a x e r r o r ；另一种是给定时间序列，产生的p l r 中所有分段的误差总和不超过某个用户指定的误差阂值t o t a l m a x e r r o r 。 根据分段误差控制的方法不同，这类算法又可分为以下三种： 滑动窗e 1 ( s l i d i n gw i n d o w ) ：从时问序列的第一个点开始一个新的分段，持续向后增 长直到该分段与时问序列的拟合误差超出了某个指定阈值，结束该分段，然后以下一 个序列点作为新分段的开始，不断重复上述过程直到时间序列末端。这类算法的优点 是简单直观且支持在线分段，缺点是在某些情况下会得到很差的近似表示。p a r k 等人 提出单调变化的分段算法，在光滑的数据集上取得了良好效果，但是在具有大量噪音 的实际数据上，得到的分段太多4 2 1 。滑动窗口方法的时间复杂度为口o ( n 木，) ，其中， 是分段的平均长度。 自底向上( b o t t o m u p ) ：首先得到最精细的线性分段表示，即时间序列上相邻两点组 成最小分段。然后计算合并两个相邻分段所产生的拟合误差，合并拟合误差最小的两 个邻接分段，直到该拟合误差超过某个指定阈值。自底向上算法的时间复杂度与滑动 窗i ：1 方法一样，都是o ( n 幸z ) 。 自项向下( 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 算法 4 引。t o p d o w n 算法的时间复 t 2 浙汀理t 大学硕上学位论文 杂度比较高，达到o ( n 2 ) 。 ( 3 ) 其他表示方法 除了上述主要的两种时间序列表示方法之外，还存在着一些其他表示方法。这些方法 主要采用一些启发式规则，从时间序列中选择具有明显特征意义的时间点将时间序列分割 为许多子段，通过线性插值等方法计算每个子段内的拟合直线段，然后得到时n 1 j 序列。 通常这些算法一般不限制分段数和分段误差，重要的是如何选择合适的分段点。p e r n g 等人提出了界标模型( l a n d m a r km o d e l ) 用于时间序列的分割，其中m 阶界标点被定义为 m 阶导数为0 的点，通过最小距离和百分比原则选择部分界标点作为分段点f 删。 p r a t 和f i l l l 【提出了基于重要点的分段方法，重要点被定义为在局部范围内与局部端 点的比值超过参数r 的极值点，将重要点作为时间序列的分段点。通过选择不同参数r ， 可以获得不同精细程度的p l r 表示【4 5 】。 文献 4 6 提取时间序列的特征点作为时间序列的分段点，通过连接这些特征点，得到 时间序列的分段线性表示。其中特征点指满足以下两个条件的点：1 ) 该点必须是序列的 极值点；2 ) 该极值点保持极值的时间段与该序列长度的比值必须大于指定的闽值。 文献 1 3 借鉴了数字图象研究领域中边缘算子的基本思想，将边缘算子与时间序列的 特点结合起来，提出时态边缘算子，根据时态边缘算子计算时间序列各点的边缘幅度，根 据边缘幅度和选择算法选取一些时间序列的边缘点作为时间序列的分段点，然后将这些分 段点依次用线段连接，就得到了时间序列的一种分段线性表示，称为时间序列的 t e o ( t e m p o r a le d g eo p e r a t o r ) 表示。 图2 3 显示了时间序列的分段线性表示方法的分类。 在时间序列的各种模式表示方法中，p l r 表示方法相对而言更加简单直观，具有时 间多解析的特点，而且多数p l r 表示方法支持时问序列的动态增量更新。时间序列的p l r 表示方法还具有以下优势： 支持快速相似性搜索； 支持时间序列新的距离度量，包括模糊查找，加权序列，d t w 距离，信息反馈等； 同时支持文本和数据序列； 支持新的聚类、分类算法； 支持奇异点检测。 基于数据流的时问序列异常数据挖掘的研究 图2 3 分段线性表示方法的分类 2 4 基于基本窗口和斜率的分段线性模式表示 本节将介绍论文提出的一种基于基本窗口和斜率的时间序列分段线性表示( p l r b a s e do nb a s ew i n d o wa n ds l o p e p l rb w s ) 方法。首先通过定义基本窗口，将时间序列 划分为若干个时间问隔等长的子序列，然后通过借鉴解析几何中两点确定一条直线时该直 线性状的两个描述值：斜率和截距，将斜率和时间序列结合起来，根据预先定义的斜率阈 值判断是否对时间序列进行分段。该方法简单直观，对具有明显的周期性和短期模式波动 频繁等特点的时间序列，能够有效地实现数据压缩，从而把握时问序列总体模式的变化特 征。 2 4 1 基于基本窗口和斜率的分段线性模式表示 下面首先给出时间序列分段线性表示、时间序列的基本窗口和时间序列分段线性表示 的压缩率的定义。 定义2 3 时间序列的分段线性表示 时间序列的模式可以是时间序列的全局特征，也可以是与时问相关的局部特征。如果 把时间序列的全局特征称为时间序列的模式的话，那么与时问相关的局部特征可以称为时 问序列的子模式。如果将时间序列沿时间轴分成若干个子序列，然后连接每个子序列的首 尾端点，构成若干条直线段，并且用所有的直线段来表示该时间序列的模式，就得到了一 种时问序列的模式表示方法，称为分段线性表示方法。用符号定义如下： 1 4 浙江理工大学硕上学位论文 v x = ( x i , x ：，k ) ，jx o ) = 4 ( t ，川) + q ( f ) ，f 队】 肫w 2 ) + e 2 ( t ) ，f 叫i , t 2 。 ( 2 2 ) 以( f ，w k ) + e 。g ) f t k - 1 , 咒】 其中，w ，表示时问区间 w ，w r 】的两个端点坐标，z ( f ，w ，) 表示连接模式w 两端点的线性 函数，e i o ) 表示某时问段内时间序列与它的模式表示之间的误差。 定义2 4 时间序列的基本窗口 对于时间序列x = ( x ix ：，工。) ，如果将k 个记录时间间隔规定为一个基本窗口，那 么基本窗口中将包含k 个元素，即基本窗口b r v ( x ) - - ( x i 工川，x m 一。) 。由此可以看出时 间序列的基本窗口实际上是时间序列的一定时间间隔的子序列。如果用时间序列的分段线 性表示基本窗口，同样的基本窗口可以用符号表示如下： v 召( x ) = ( x ix 川，x m 一。) ，了b 肜( x ，f ) = z o ，) + q o ) ，f i , t 。】 肫) + e z 叫1 , t 2 。( 2 3 ) 乃g ，) + p ，咖h i + k 一1 】 其中，w ，表示时间区间 w f - l w ，】的两个踊, a 肺- 一a 川- - i ，z ( f ，) 表示连接模式w f 两端点的线性 函数，白o ) 表示某时问段内时间序列与它的模式表示之间的误差。 定义2 5 时间序列分段线性表示的压缩率 对于时间序列x = ( x 1 , x ：，邑) ，通过线性分段算法得到的时间序列为 x = ( x ：，x ；，x ：) ，其