基于数据流的时间序列异常数据挖掘的研究.doc

浙江理工大学硕士学位论文基于数据流的时间序列异常数据挖掘的研究姓名：黄志强申请学位级别：硕士专业：计算机应用技术指导教师：贾宇波20080301浙汀理工大学硕上学位论文摘要基于数据流的时间序列异常数据挖掘可以用于交通领域的道路推荐、供水领域的管网监测以及证券、医疗、环保、电力等行业的检测和预报工作。这些领域产生的数据有着明显的时间序列的特征，同时还具有数据量大、结构复杂、实时性要求高等特点。如果仪使用传统的理论和方法分析这些数据，往往因为计算能力、存储能力以及算法的不足而显得无能为力。数据流挖掘理论和技术的引入为解决上述问题提供了新的思路，越来越成为国内外研究者所关注的热点。目前，时间序列的数据挖掘主要包括相似性查询、分类、聚类和异常检测等。论文围绕数据流环境下时间序列异常数据挖掘这一主题，以时间序列的模式表示为基础，讨论了时间序列数据预处理和压缩存储，提出了一种基于数据流的时间序列异常检测算法，并根据现实生活中多维数据流的需要和对历史数据的分析，将原算法进行了改进，最终确定了改进的基于数据流的时问序列异常检测算法。主要的研究内容和成果包括：时间序列的模式表示论文将解析几何中的线段概念和现实生活中的基本时间窗口引入到时间序列的研究中来，提取线段的斜率作为确定时间序列分段线性表示的分段点选取的依据，提出了一种基于基本窗口和斜率的分段线性表示方法（简称为表示）。时间序列的表示方法简单直观，对于具有明显周期特征和短期模式波动频繁等特点的时间序列具有很强的数据压缩能力，从而能较好地保持时间序列总体模式的变化特征。时间序列的异常检测在时间序列的模式表示基础上，论文提出了基于滑动窗口的时间序列窗口异常的定义，同时给出了流数据环境下的基于滑动窗口的时间序列异常检测算法（简称），采用“窗口异常度”来衡量时问序列上当前窗口的异常程度。与其他异常数据挖算法相比，不需要训练，满足了数据流的实时性要求，在模式表示的基础上算法又一定程度的降低了存储要求和操作。只要合理地调整参数，算法总是能够及时、有效地检测出当前时间序列的异常行为。关键词：数据流；时间序列；数据挖掘；模式表示；异常检测基于数据流的时问序列异常数据挖掘的研究，：，“”，浙江理工大学硕上学位论文，（“”），：；浙江理工大学学位论文原创性声明本人郑重声明：我恪守学术道德，崇尚严谨学风。所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已明确注明和引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品及成果的内容。论文为本人亲自撰写，我对所写的内容负责，并完全意识到本声明的法律结果由本人承担。学位论文作者签名：乡名、季纵日期沁学年弓月。日浙江理工大学学位论文版权使用授权书学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅或借阅。本人授权浙江理工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于保密口，在不保密口。学位论文作者签名：童声考钦吼研年多月，日年解密后使用本版权书。指黝婚秘指导教师签名：。醐：加蛑朋日浙江理工大学硕上学位论文课题的背景、目的及意义第一章绪论金融、电信、工农业生产及科学实验等各个领域每时每刻都在产生海量的数据，这些数据中大多数是对和时间相关历史数据的记录，我们称之为时态数据（）。时态数据既可以指按时间的先后顺序排列的数据，也可以指按空问的前后顺序排列的随机数据。根据记录数据的类型的不同，时态数据主要可以分为三类，即时间序列、事务序列和事件序列【】。所谓时间序列就是按照时间先后顺序排列的各个观测记录的有序集合，其中观测记录是数值类型的。时间序列数据在金融、交通、电力等各个行业都大量存在。比如股票市场上每天都在波动的股票价格，它的背后存在着时序关系；道路上行驶的车流，有着一定的时序关系；人们生活中离不开的电力，它的使用情况也存在着时序关系。传统时问序列的研究工作主要采用的是概率统计学方面的方法，经过长期的发展，理论基础完备，并在实际工作中起着重要的作用【】。然而它主要的研究方法是全局模型，研究的对象是随机性的动态数据，并且对时间序列的要求相对较高（如自回归滑动平均模型】要求时间序列必须是平滑的，同时模型产生的时间序列与实际产生的时间序列的误差不相关并呈正态分布），并不能适应绝大多数实际系统所产生的时间序列。此外，传统的研究分析主要是一种验证工作，而当今我们已不满足于验证，我们需要的是对系统整体的把握及预测。比如关心某个周期内出现的频繁模式，比较不同序列在某个周期内的运动模式是否相似，关注某个时间序列产生的异常情况等等。现实生活中不乏这样的例子：）在股票市场，短线操作关心的是某个相当短的时间周期内股票的走势，并对未来短期内的走势进行预测判断；而长线操作关心的是整体的走势。）开车出门的时候，用户关心的是当前及未来短期内的道路通行情况，并希望系统能比较多条道路通行情况，推荐合适的通行道路。）医院的设备仪器希望能检测或者预测出被检查人员的病情，及时将该病情通知他们，以便能得到及时、妥善的治疗。对于上述实例，传统的时间序列研究方法已不能适应，势必要求有新兴的理论和技术来满足它的需要，这就是数据挖掘技术。数据挖掘技术是从上世纪年代初发展起来的门学科，到目前为止已经建立了一套比较完备的体系。当前，它又有新的发展方向，那基于数据流的时问序列异常数据挖掘的研究便是数据流挖掘。一般我们把具有以下几个特征的数据称作数据流或流数据：数据量一般是随时间无限增氏的。数据是实时产生的。无法对数据产生的速度和规模进行预测和控制。一项数据处理过后就会被丢弃或者压缩存档，无法对历史数据进行随机访问。由于数据流的这些特点，大多数传统的数据处理技术无法快速有效地处理数据流中的数据。通过研究，绝大多数学者都认为一个系统或者算法如果要很好地处理这类数据量巨大、永无止境的数据流，至少必须满足以下几点要求：处理数据流中每条记录必须只使用很短且恒定的时间，否则将会跟不上数据到来的速度；只能使用固定大小的内存空间，与已经处理过的数据量的大小无关；只需要对数据进行一次扫描，因为在大多数应用中，或者无法得到历史数据，或者根本没时间去访问历史数据；必须能够在处理的任何阶段输出可用的结果，而不是等到处理完所有的数据后才输出结果，因为我们可能永远到达不了数据的尽头；理想情况下，应该能够得到一个与传统算法在没有任何约束条件下在相应的静态数据集上得到的结果相同或者近似的结果；当数据流的模型发生变化时，计算的结果必须也要能够及时得到调整，反映数据的变化。这些要求看上去很难达到，但是只有这样才能真正有效地处理大规模的数据流上的数据。在一些特殊的情况下，如果数据流的规模不是很大，产生的速度也不是很快，而且硬件设备的存储和计算处理能力远远超过数据流中的数据量的时候，可以放松其中的几点要求。但在时间复杂度和空间复杂度上算法还是要满足一定的要求，即：时间复杂度最好和数据量的大小呈线性关系；空间复杂度最好和数据量的大小无关，或者要保持在对数关系之内。本课题是围绕着数据流环境下的时间序列异常数据挖掘展开的，它有着广泛的应用前景：在交通领域，道路推荐系统通常将路口饱和度作为畅通指标，然而如果道路中发生交通事故，路口的饱和度是降低了，但实际上这条道路并不是畅通的。如果通浙汀理工大学硕士学位论文过时间序列的异常数据挖掘能判断出道路的畅通与否，则就能进一步提高道路推荐系统的正确率。在供水行业，如果大口径水管破裂而不能及时维修，将给人们的生活和出行带来极大的不便。如果能采用监控系统的时问序列异常数据挖掘技术而进行及时维修，就能减少人们生活不便的时间，给国家挽回大量的损失。在医疗、环境保护、电力和天然气等行业的检测和预报工作。国内外的研究现状及发展动态时间序列上的数据挖掘研究伴随着数据挖掘的兴起而迅速发展，其研究内容包括时间序列上的相似性查询、模式挖掘、分类和聚类、异常检测等。时间序列上的异常检测是近年来数据挖掘的研究热点之一。到目前为止，学术界还没有一个公认的异常时间序列的定义，根据不同的假设，各类研究人员提出了不同的定义。和异常相关的定义还有新颖（，）、不规则（）、奇异（】）等。相对于单个点的异常研究，时间序列异常研究的是一个时间段的异常。下面将简要描述下国内外时间序列的研究现状及发展动态。国外很早【一就开始了时问序列的异常检测研究工作，近年又出现了许多新的观点和研究方法。文献提出了的改进型来实现奇异模式的查询，他们把奇异模式定义为时间序列上的突然变化，通过小波系数的局部极大值来发现。但是他们对奇异模式的定义是建立在小波系数的基础上，因此不够准确和全面，有些奇异模式无法发现】。文献采用可增量学习的概率模型（比如模型）对历史时间序列数据建模，能够动态适应新的数据，渐渐遗忘历史数据。给新到来的序列点与模型的偏差度打分，分高的认为是高概率异常。不过他们也是针对异常点的检测，不是异常序列。他们还提出了异常发现算法，需要满足的两个条件：（）异常发现算法必须足在线的，一旦发现异常，就能立刻发现；（）异常发现算法必须适应动态变化的非稳定数据环境。文献提出了线性时问和空间范围下的奇异模式（）发现。如果一个模式的出现频率与它的期望出现概率显著差异时，认为它是奇异模式。该定义的优点在于奇异模式的定义不需要借助领域专家知识，一般用户也能发现奇异模式。他们提出了算法，采用后缀树来编码所有出现的模式，用马尔科夫模型预测未现模式的期望出现概率。基于数据流的时问序列异常数据挖掘的研究文献，提出基于支撑向量回归（，）模型的算法，可以在线发现时态序列的新颖事件。采用模型对历史时间序列建立回归模型，判断新到来的序列点与回归模型的匹配程度，考察连续一段时间内的匹配情况，给出其为新颖事件的置信度。建立回归模型时采用时延嵌入过程（）得到训练样本集，回归模型可增量更新。国内对于时间序列和异常检测的研究起步较晚，虽然近年发展很快，但基于时间序列的异常检测的研究工作仍然相对缺乏。文献提出了基于时间序列模式表示的模式异常方法。并不直接对时间序列本身的序列点进行异常判别，而且用时间序列的模式表示代替时间序列，判断时间序列的模式是否异常，提高了异常检测的准确率和效率。提出了基于模式密度的异常检测算法（），无需训练，并支持时间序列的动态更新。但该算法并不支持多维度的情况，不能满足实际应用的需要。文献将序列挖掘了应用到异常检测，但基本上研究的都是基于事件序列入侵检测。总之，国内外对序列时间异常检测都做了不少的工作，但总的来说研究还是零散的，存在的分歧和争议比较多，远未达到系统研究的深度。本文的工作研究内容和成果论文主要围绕数据流环境下时间序列异常数据挖掘这一主题，以时问序列的模式表示为基础，讨论了时间序列数据预处理和压缩存储，提出了一种基于数据流的时间序列异常检测算法，并根据现实生活中多维数据流的需要和对历史数据的分析，将原算法进行了改进，最终确定了改进的基于数据流的时间序列异常检测算法。其关系如图所示。论文的主要研究内容和创新工作简单介绍如下：（）时间序列数据流的模式表示数据流有着明显的时间序列特征，为了研究复杂而海量的数据流，通常研究的对象并不是原始时问序列数据流，而是将时间序列数据流通过各种方法表示后加以研究。文章采用了一种基于基本窗口和斜率的分段线性模式表示方法来表示时间序列，不但对实时采集的数据流进行了预处理，而且对海量的数据流进行了一定程度地压缩，有效地减少了数据浙江理工大学硕上学位论文挖掘所需要的存储空间和计算量。基于数据流的时间序列数据的异常数据挖掘的改进图论文研究内容的关系图（）时间序列数据流的异常检测人们通常关心的是最近的时问序列数据流信息，因此文章采用了滑动窗口策略来挖掘异常数据。窗口的滑动策略是每经过一个基本窗口时间，就向前滑动一个基本窗口，于是异常的时间序列也就是在所有滑动窗口的基本窗口中进行挖掘。在引入滑动窗口策略之后，论文提出了一种基于数据流的时间序列异常检测算法。随着基本窗口的不断滑出，历史信息也不断地积累，为了进一步提高异常时间序列数据挖掘的精确度，文章将滑动窗口策略和历史信息指数衰减相结合，提出了一种改进的基于数据流的时间序列异常检测算法并将其推广到多维数据流的情况，在不增加算法执行时问的同时有效地提高了数据挖掘的精确度，更适应于现实中流数据的异常数据挖掘。组织结构全文共分章，简单介绍如下：第一章：绪论首先介绍了基于数据流的时问序列异常数据挖掘的背景、目的及意义，接着介绍了本课题的国内外研究现状及发展动态，最后简单介绍了论文主要的研究内容和研究成果。第二章：基于数据流的时间序列模式表示首先介绍了几种常见的时间序列的模式表示方法，比较他们各自的优缺点。提出了一基于数据流的寸问序列异常数据挖掘的研究种基于基本窗口和斜率的分段线性表示（，）方法，并与其他几种分段线性表示方法进行了比较。第三章：基于数据流的时间序列异常数据挖掘首先介绍了几种常见的时间序列异常类型，在时间序列的模式表示基础上，提出了一种基于滑动窗口的时间序列窗口异常定义，用“窗口异常度”来描述模式的异常程度。根据时间序列的窗口异常定义，提出了基于滑动窗口的窗口异常检测算法（，）。第四章：基于数据流的时问序列异常数据挖掘的改进简单介绍了几种常见的历史信息存储策略，通过比较采用指数衰减策略将历史基本窗口的信息加以利用。对原先的基于数据流的时间序列异常检测算法进行了改进并将其推广到多维数据流的情况，提出了一种改进的基于滑动窗口的窗口异常检测算法。第五章：总结与展望总结了全文的研究工作，并对以后所要进一步研究的工作进行了展望。浙汀理工大学硕士学位论文引言第二章基于数据流的时间序列模式表示时间序列就是按照时问先后顺序排列的各个观测记录的有序集合，其中观察记录是数值类型的。时间序列数据在金融、交通、电力等各个行业都大量存在，典型的例子包括股票每天的收盘价、某地区的降雨量、道路交通系统中的车流量等。随着时间的推移，这些复杂数据也不断地积累，并朝着海量的方向发展。如何对这些海量时间序列数据进行统计、分析，从中发现有用的信息，进而预测事物的发展动态，一直以来都是人们感兴趣的问题。数据流有着明显的时间序列特征，为了研究复杂而海量的数据流，通常研究的对象并不是原始时间序列数据流，而是将时间序列数据流通过各种方法表示后加以研究。这是因为一方面由于大多数数据挖掘算法并不适应时间序列的超高维数，海量的数据量又将使得直接在时间序列上进行数据挖掘在存储和计算上要花费巨大的代价；另一方面时间序列数据容易受外界的噪声干扰而产生误差，这就可能会影响数据挖掘算法的准确性和可靠性。将时间序列数据流通过各种方法表示以后，可以仅仪考虑原时间序列的主要形态，忽略那些细小而不改变性质的变化。其优势可以描述如下：对时间序列进行了一定程度的压缩，减少了数据量，有利于数据挖掘的存储和计算；去除了时间序列的部分噪声，保留了时间序列的主要形态，降低了误差对数据挖掘的影响，有利于数据挖掘效率和精准度的提高；从对时间序列时间点的分析过渡到时间序列时问段的数据挖掘，更符合大多数领域所关心一段时间内的数据变化模式和规律。相关定义本节将给出时间序列正式的数学形式描述及相关术语的记号和定义【。在论文的其它章节，如不特别说明，将沿用以下的相关术语的记号和定义。定义时间序列时问序列是由一系列元素组成的有序集合，这些元素本身由记录时刻和记录值构成，记为（。，），：，：），。，。），其中元素，）表示在如时刻取得记基于数据流的时问序列异常数据挖掘的研究录值为，这里记录时刻是严格单调增加的，即，。通常百序列的记录时问问隔，是相等的，于是对于上述时间序列可以取。，那么时间序列（。，。），：，：），。，叱）可以简记为（：，。）。称为时间序列的模，表示时间序列的长度，即元素的数量。对于广义时间序列，记录值可以是离散符号、结构数据、多媒体数据等，但当前论文只采用狭义的时间序列，即，的取值为实数类型。定义时间序列的模式表示设有时间序列（。，：，。），其模式是指该时间序列的某种变化特征。时间序列的模式可以是该时间序列在一段时间的均值或者中值，也可以是时间序列离散化后的符号，甚至可以是时间序列的傅立叶变换系数。通过提取时间序列的模式，可以将时问序列变换到模式空间，于是就得到了时间序列的模式表示。用符号定义如下：（）（），。（）其中，是时间序列的模式，以）是时间序列的模式表示，（力是时间序列的模式和它的模式表示之间的误差。时间序列的模式表示能够压缩数据，保留时间序列的主要形态，忽略其中的微观细节，给进一步的研究工作提供方便。图是年日本上河原地区某取水点浊度记录信息时间序列，共有个记录信息；图是该时间序列的一个模式表示，它只需要保留个记录信息，不但压缩率达到了，而且很好地保持了原始时间序列的主要形态。图年日本上河原地区某取水点浊度记录信息浙江理工大学硕士学位论文图年日本上河原地区某取水点浊度记录信息分段线性表示常见的时间序列模式表示符号表示法符号表示法就是要把由实数组成的时间序列用符号序列表示。它是近几年提出的时间序列近似表示的方法之一，因其离散化、非实数表示的特点得到越来越多的关注。符号化方法主要可分为两大类【】：一类足对时间序列不作任何预处理，直接根据序列的数值特点进行符号划分，可以称之为直接法，主要包括静态法，动态法，以及综合法；另一类是首先对时间序列做适当变换，然后再划分，可以称之为问接法，主要有小波空间法。等人采用等宽离散化和最大墒离散化方法将时间序列的实数值映射到有限的符号，以后缀树为索引，提出了一种动态时问弯曲距离的下界距离（，），在提高查询效率的同时保证了查询的完备性，他们的工作使得基于符号化表示的时间序列相似性查询能够支持比欧式距离更鲁棒的动态时间弯曲距离。在分段集成近似（，）基础上提出了一种新型符号化方法（，）。其基本思想是首先将原始时间序列正规化，然后利用对长度为的时间序列降维，得到（）维的时间序列，最后将降维后的序列值离散化为个等概率的区间，并将处于同一个概率区问的序列值用同一个符号表示，实现了时间序列的符号化表示。与其它符号化方法相比有以下的优点：（）简单、易用且算法不依赖于具体实验数据；（）在符号化的过程中实现了降维（），能有效解决对高维数据进行数据挖掘由于维数过高引起的问题；（）保证在符号空间计算出的两个符号序列的距离满足实际的两个时间序列的距离下界的要求，即不会出基于数据流的时问序列异常数据挖掘的研究现漏报。符号表示法的不足之处在于如何对时间序列进行离散化，而符号表大小的选择也是一个难点。频域表示法频域表示法主要可以分为两种：一种是通过离散傅立叶变换（，）将时间序列从时域空间映射到频域空间；另一方法采用的是离散小波变换（）。在离散傅立叶变换上，等人首先通过选择前（通常选择）个系数来表示时间序列，文献在全序列匹配问题中采用表示方法获得了很好的性能。很多研究人员也通过离散傅立叶变换对时间序列进行研究。等【】进一步了扩展了相关工作用于子序列匹配。为了保证没有错误丢失，对任何一个特定的变换兀特征空间中距离之间的度量值（对任何两个对象柳力必须满足下界：，钿。（丁（），丁）（，）。等人【给出了如何处理中的移动平均问题，并指出在不增加存储在索引中特征值数量的情况下，使用的对称性质可以进一步提高距离度量的精度【。文献【】提出了一种新的基于傅立叶变换的时间序列相似性搜索算法称为算法，解决了多序列的子序列匹配问题，通过实验证明了该算法：匕算法时间复杂度小，更具有通用性和有效性。表示存在的问题是它可能会丢失时间序列的局部特征，在表示中，这个不足支出得到了改进。小波分析具有良好的时、频多分辨率功能，可以聚焦到任意细节，从而观察到不同时间尺度上的变化情况【。与离散傅立叶变换相比，离散小波变换是时间和频率的局部变换，不但包含了频率信息，同时还包含了时间信息（而是对信号的整体变换，只考虑了频率信息），能更加有效地提取和分析局部信号。等人【提出使用波变换作为特征提取方法，实验结果表明其性能要好于。等人也在这个领域应用到小波变换。文献给出了另一类小波变换的应用，进一步说明了小波变换在时间序列查询中的优越性。传统的小波变换算法均使用变换后小波序列的前个系数作为原始时间序列的一个近似估计，但是选择前个系数不一定能很好的近似原始序列集合。文献基于上述原因，讨论了小波系数的选择方案，给出了相关的定理说明选择小波系数集合的列浙江理工大学硕上学位论文平方和最大的：歹，可以更好地近似原始序列集和缩小基于小波变换数据挖掘的相对误差。文献基于小波变换模极大值，给出了一种时间序列中异常数据的多尺度检测方法：首先求时间序列在各个尺度上的连续小波变换，找出在各尺度上的模极大值点，所有尺度上模极大值构成模极大值线，然后进行模极大值搜索，使得异常数据可以在各个尺度上进行观察。该方法无需事先知道时间序列点的个数，也无需确定曲线满足函数，但仍然停留在对数据点的挖掘之上。等人【】比较表示和表示，认为在相似性查询问题上两种表示方法性能相当，但是只需线性时间，计算更为迅速。奇异值表示法奇异值分解（，）是一种常见的降维方法，己经成功用于图像和文本的索弓，】。表示方法与其他的时间序列表示方法不同，它是对整个时序数据库的整体表示。通过分析所有的时间序列，计算新的坐标体系，使得第条坐标轴对应最大的方差，第二条坐标轴对应次大的方差并与之前的坐标轴正交，依次得到所有的坐标轴，根据这些坐标轴将时间序列从原始空间变换到新的坐标空间。方法是一种线性变换，在数据重构上误差最小，这使得在一些情况下能够取得很好的性能。但是，方法的时间复杂度为叫胁），其中是指时问序列数据库的大小，厅指时间序列的平均长度。当插入或删除一条时间序列时，所有时间序列的表示方法都必须重新计算，时间代价很高。分段线性表示法时间序列的分段线性表示（，）是时间序列的模式表示方法中研究最早，也是研究最多的方法。时间序列的中，线段的数目决定了对原始序列的近似粒度。线段越多，线段的平均长度就越短，反映了时间序列的短期波动情况；线段越少，线段的平均长度就越长，反映了时间序列的中长期趋势。等人【将输入为时间序列，输出为的算法统称为线性分段算法（）。直观上讲，方法就是用条首尾邻接的直线段来近似表示条长度为（）的时间序列。线性分段存在两个关键问题：一个是如何选择合适的线段数目；另一个是如何选择合基于数据流的时间序列异常数据挖掘的研究适的分段点。根据对这两个问题的不同解决方法，可以将线性分段算法分为以下三种类型：（）限制分段数：给定时间序列，产生的只包括条直线段。文献【和【】分别独立提出了时间序列的分段聚集近似（，）方法，将时间序列等宽度划分，每个子段用时问序列在该子段上的平均值来表示。方法简单直观，能够支持任意长度的相似性查询和所有的度量以及加权欧氏距离，而且能够用于索引以提高查询的效率。等人的实验表明，将方法用于时间序列的索引，使得相似性查询的效率比表示方法提高了一个数量级【。（）限制分段误差：不规定分段的数目，通过控制分段误差来选择合适的分段点。限制分段误差的方式主要有两种：一种是给定时间序列，产生的中每个分段的最大误差不超过某个用户指定的误差阈值；另一种是给定时间序列，产生的中所有分段的误差总和不超过某个用户指定的误差阂值。根据分段误差控制的方法不同，这类算法又可分为以下三种：滑动窗（）：从时问序列的第一个点开始一个新的分段，持续向后增长直到该分段与时问序列的拟合误差超出了某个指定阈值，结束该分段，然后以下一个序列点作为新分段的开始，不断重复上述过程直到时间序列末端。这类算法的优点是简单直观且支持在线分段，缺点是在某些情况下会得到很差的近似表示。等人提出单调变化的分段算法，在光滑的数据集上取得了良好效果，但是在具有大量噪音的实际数据上，得到的分段太多。滑动窗口方法的时间复杂度为口（木，），其中，是分段的平均长度。自底向上（）：首先得到最精细的线性分段表示，即时间序列上相邻两点组成最小分段。然后计算合并两个相邻分段所产生的拟合误差，合并拟合误差最小的两个邻接分段，直到该拟合误差超过某个指定阈值。自底向上算法的时间复杂度与滑动窗：方法一样，都是（幸）。自项向下（）：该算法是算法的逆过程。首先得到计算时间序列的最粗糙的线性分段表示，即用一条线段来拟合时间序列。然后计算将该线段分割成两条拟合线段所能降低的拟合误差，选择最大拟合误差的分割点，重复上述过程，直到每个分段的误差都不超过某个指定阈值。等人改进了该算法，将时间序列的极值点作为初始分割点，然后再使用经典算法引。算法的时间复浙汀理大学硕上学位论文杂度比较高，达到（）。（）其他表示方法除了上述主要的两种时间序列表示方法之外，还存在着一些其他表示方法。这些方法主要采用一些启发式规则，从时间序列中选择具有明显特征意义的时间点将时间序列分割为许多子段，通过线性插值等方法计算每个子段内的拟合直线段，然后得到时序列。通常这些算法一般不限制分段数和分段误差，重要的是如何选择合适的分段点。等人提出了界标模型（）用于时间序列的分割，其中阶界标点被定义为阶导数为的点，通过最小距离和百分比原则选择部分界标点作为分段点删。和【提出了基于重要点的分段方法，重要点被定义为在局部范围内与局部端点的比值超过参数的极值点，将重要点作为时间序列的分段点。通过选择不同参数，可以获得不同精细程度的表示【】。文献提取时间序列的特征点作为时间序列的分段点，通过连接这些特征点，得到时间序列的分段线性表示。其中特征点指满足以下两个条件的点：）该点必须是序列的极值点；）该极值点保持极值的时间段与该序列长度的比值必须大于指定的闽值。文献借鉴了数字图象研究领域中边缘算子的基本思想，将边缘算子与时间序列的特点结合起来，提出时态边缘算子，根据时态边缘算子计算时间序列各点的边缘幅度，根据边缘幅度和选择算法选取一些时间序列的边缘点作为时间序列的分段点，然后将这些分段点依次用线段连接，就得到了时间序列的一种分段线性表示，称为时间序列的（）表示。图显示了时间序列的分段线性表示方法的分类。在时间序列的各种模式表示方法中，表示方法相对而言更加简单直观，具有时间多解析的特点，而且多数表示方法支持时问序列的动态增量更新。时间序列的表示方法还具有以下优势：支持快速相似性搜索；支持时间序列新的距离度量，包括模糊查找，加权序列，距离，信息反馈等；同时支持文本和数据序列；支持新的聚类、分类算法；支持奇异点检测。基于数据流的时问序列异常数据挖掘的研究图分段线性表示方法的分类基于基本窗口和斜率的分段线性模式表示本节将介绍论文提出的一种基于基本窗口和斜率的时间序列分段线性表示（）方法。首先通过定义基本窗口，将时间序列划分为若干个时间问隔等长的子序列，然后通过借鉴解析几何中两点确定一条直线时该直线性状的两个描述值：斜率和截距，将斜率和时间序列结合起来，根据预先定义的斜率阈值判断是否对时间序列进行分段。该方法简单直观，对具有明显的周期性和短期模式波动频繁等特点的时间序列，能够有效地实现数据压缩，从而把握时问序列总体模式的变化特征。基于基本窗口和斜率的分段线性模式表示下面首先给出时间序列分段线性表示、时间序列的基本窗口和时间序列分段线性表示的压缩率的定义。定义时间序列的分段线性表示时间序列的模式可以是时间序列的全局特征，也可以是与时问相关的局部特征。如果把时间序列的全局特征称为时间序列的模式的话，那么与时问相关的局部特征可以称为时问序列的子模式。如果将时间序列沿时间轴分成若干个子序列，然后连接每个子序列的首尾端点，构成若干条直线段，并且用所有的直线段来表示该时间序列的模式，就得到了一种时问序列的模式表示方法，称为分段线性表示方法。用符号定义如下：浙江理工大学硕上学位论文（，：，），）（，川）（），队】肫）（），叫，。（）以（，）。），咒】其中，表示时问区间，】的两个端点坐标，（，）表示连接模式两端点的线性函数，）表示某时问段内时间序列与它的模式表示之间的误差。定义时间序列的基本窗口对于时间序列（：，工。），如果将个记录时间间隔规定为一个基本窗口，那么基本窗口中将包含个元素，即基本窗口（）（工川，一。）。由此可以看出时间序列的基本窗口实际上是时间序列的一定时间间隔的子序列。如果用时间序列的分段线性表示基本窗口，同样的基本窗口可以用符号表示如下：召（）（川，一。），了肜（，），），。】肫）叫，。（）乃，），咖一】其中，表示时间区间，】的两个踊，肺一川，（，）表示连接模式两端点的线性函数，白）表示某时问段内时间序列与它的模式表示之间的误差。定义时间序列分段线性表示的压缩率对于时间序列（，：，邑），通过线性分段算法得到的时间序列为（：，；，：），其中石，：。那么该算法的压缩率为一旦。，在数据流中，可以将基本窗口的长度形象的描述为时间序列的某个小周期。比如数据流的到达速度时间是每秒个数据对象，那么基本窗口可以定义秒。方法就是首先将不断流入的数据对象以秒的时问，隔内为单位进行分段，然后再对秒内的数据对象进行分段线性表示，最后获得多个基本窗口为单位的分段