（计算机软件与理论专业论文）时序数据维归约方法的研究.pdf

兰州大学硕士研究生毕业论文 摘要 时间序列是一类重要的数据类型，广泛存在于金融、事务处理和科学研究等 领域中。时间序列挖掘通过对过去历史行为的客观记录分析，提取人们事先不知 道的，但又是潜在有用的与时间属性相关的信息和知识，从而揭示其内在的数据 生成机制，进而发现和预测未来行为模式。 本文系统地介绍了时间序列挖掘技术，包括时间序列的数据清理、分割、表 示和相似性度量等技术。论文研究了时间序列的分段表示方法，主要的研究工作 及成果如下： 1 由于原始时间序列具有高维性、类型复杂和富含噪声的特点，直接在时 间序列上执行数据挖掘任务，往往导致算法效率低下和挖掘结果不可靠。时间序 列的维归约是一种对时间序列进行特征抽象和概括的表示方法，是对时间序列在 更高层次上的重新描述。论文在分析了经典的自顶向下、自底向上和滑动窗口算 法的基础上，针对滑动窗口算法出现的“过拟合”的分段，通过检测前后两个分 段趋势的相近程度，对趋势相近的分段进行合并，从而有效地避免了尖峰形态数 据的影响；针对“欠拟合 的分段，采用了一种新的度量方法，对“欠拟合”的 分段进行适当分割，从而得到更好的表示效果。实验表明：以上两种改进策略效 果明显。 2 目前大量的信息系统都是实时地产生数据，这样的数据类型称作“数据 流”，具有如下两个特点：系统源源不断地产生大量的细节数据；需要实时 地对新产生的数据进行分析。针对数据流上的应用，本文提出了一种适合在线分 割的时间序列表示算法一r s w 算法，该算法基于滑动窗口算法框架，应用了文 中提出的两种改进策略，实验结果表明：r s w 是一种适合在线分割的时间序列表 示算法，具有线性复杂度和拟合误差小的特点。 关键词：时间序列，数据挖掘，维归约 兰州人学硕：f ：研究生毕业论文 a b s t r a c t t i m es e r i e si sa ni m p o r t a n td a t at y p e ，w h i c hi sw i d e l yu s e di nt h ea r e a so f f i n a n c e ，b u s i n e s sa n ds c i e n t i f i cr e s e a r c h b yt h ea n a l y s i so fh i s t o r i c a l b e h a v i o r s o b j e c t i v er e c o r d s t i m es e r i e sm i n i n ge x t r a c t st h ep o t e n t i a l l yu s e f u l a n dt i m e r e l a t e di n f o r m a t i o na n dk n o w l e d g e ，w h i c hi sn o tk n o w ni na d v a n c e i t r e v e a l si n t e r n a ld a t ag e n e r a t i o nm e c h a n i s m st of i n da n dp r e d i c tt h ef u t u r e b e h a v i o rp a t t e r n s t h i s p a p e rs y s t e m a t i c a l l yd i s c u s s e st i m e s e r i e s m i n i n gt e c h n o l o g y , i n c l u d i n gd a t ac l e a n u p 。s e g m e n t a t i o n 。r 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 e i tr e s e a r c h e st h ep i e c e w i s ep r e s e n t a t i o no ft i m es e r i e s t h em a i nr e s e a r c h w o r ka n dc o n t r i b u t i o n sa r ea sf o i l o w s ： 1 a st h eo r i g i n a lt i m es e r i e sw i t hc h a r a c t e r i s t i c so fh i g h - d i m e n s i o n a l ， c o m p l e xa n dr i c hn o i s e ，d a t am i n i n go nt i m es e r i e so r e nd i r e c t l yl e a d st o a l g o r i t h mi n e f f i c i e n c ya n dm i n i n gr e s u l t su n r e l i a b i l i t y d i m e n s i o n a l 时r e d u c t i o n o ft i m es e r i e si sam e t h o do ft i m es e r i e sa b s t r a c t i o n ，a n da h i g h e rl e v e l r e d e s c r i p t i o na b o u tt h e m w i t ha n a l y s i so ft h ec l a s s i ct o p - d o w n ，b o t t o m u p a n ds l i d i n gw i n d o wa l g o r i t h m ，t h ep a p e rs o l v e st h e “o v e r f i t t i n g ”i n s l i d i n g w i n d o wa l g o r i t h m sb yt e s t i n gt h es i m i l a r i t yo fn e i g h b o r i n gs e g m e n t s ，a n d m e r g i n gs i m i l a ro n e s t h i sm e t h o da v o i d si m p a c to fp e a kd a t ae f f e c t i v e l y a st o ”u n d e r f i t t i n g ”p r o b l e m ，an e wm e a s u r e m e n ti s u s e dt o d i v i d e “u n d e m t t i n g ” s e g m e n t sf o rb e t t e rp r e s e n t a t i o n t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt w o s t r a t e g i e sp r o p o s e di nt h ep a p e ri se f f e c t i v e 2 a tp r e s e n t ，al o to fi n f o r m a t i o ns y s t e m sp r o d u c eo n l i n ed a t a ，a n dt h i s t y p eo fd a t ai sc a l l e d ”d a t as t r e a m ”，w h i c hh a st h ef o l l o w i n gt w oc h a r a c t e r i s t i c s ： s y s t e mg e n e r a t e sal o to fd e t a i ld a t ac o n t i n u o u s l y ；n e wg e n e r a t e dd a t a n e e do n l i n ea n a l y s i s f o rd a t as t r e a ma p p l i c a t i o n s ，t h i sp a p e rd e v e l o p san e w o n l i n ea l g o r i t h mr s wf o rp r e s e n t a t i o no ft i m es e r i e s 。w h i c hi sb a s e do nt h e s l i d i n gw i n d o wa l g o r i t h mf r a m e w o r ka n da p p l i e st w os t r a t e g i e sp r o p o s e di nt h e p a p er t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tr s wi sam o r es u i t a b l ea l g o r i t h m 兰州人学硕：f ：研究生毕业论文 f o rt i m es e r i e so n l i n ed i v i s i o n ，a n dh a sl i n e a rc o m p l e x i t ya n ds m a l lf i t t i n g e r r o r s k e yw o r d s ：t i m es e r i e s ，d a t am i n i n g ，d i m e n s i o n a l i t yr e d u c t i o n 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立 进行研究所取得的成果。学位论文中凡引用他人已经发表或未发 表的成果、数据、观点等，均已明确注明出处。除文中已经注明 引用的内容外，不包含任何其他个人或集体已经发表或撰写过的科研 成果。对本文的研究成果做出重要贡献的个人和集体，均己在文中以 明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：j 碑 日 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：硒师签名： e t 期：丝岁珍 兰州大学硕l 研究生毕业论文 第一章绪论 1 1 研究背景和意义 从2 0 世纪8 0 年代开始，数据库技术广泛应用于科研、生产以及流通领域的 事务处理，因此积累了庞大的数据，特别是数据仓库以及w e b 等新型的数据源 日益普及，人们面对浩瀚的数据海洋，如何有效利用这些数据资源，找出数据背 后隐藏的信息和知识：面对这一挑战，数据挖掘技术应运而生。数据挖掘技术作 为一种新兴的智能决策支持技术，受到了广泛的关注。 数据挖掘技术是数据库技术的发展和延伸。自2 0 世纪6 0 年代起，由于计算 机技术在事务处理领域的应用，产生了人量的数据，由此引起了数据库技术的发 展，从原始的文件处理演化到复杂的、功能强大的数据库系统。自7 0 年代以来， 数据库系统的研究和开发转向层次数据库、网状数据库和关系数据库等。自8 0 年代以来，数据库的特点是广泛接受关系技术，研究和开发新的、功能强大的数 据库系统，产生了扩充关系模型、面向对象模型、对象关系模型和演绎模型 等先进的数据模型，出现了时间的、空问的、分布的、多媒体的、主动的和科学 计算的数据库、知识库在内的多种面向应用的数据库系统。9 0 年代以来，由于 万维网的蓬勃发展，出现了基于w e b 的数据库系统、多维数据库、数据仓库和 联机分析处理( o l a p ) 等新的数据处理技术。 数据库技术和人工智能中的机器学习的蓬勃发展，为快速、高效和自动处理 海量数据提供了可能。1 9 8 9 年8 月在美国底特律召开的第1 1 届国际人工智能联 合会议的专题讨论会上首次提出k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 。随后 在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年都举行了k d d 专题讨论会，汇集了来自各个领域 的研究人员和应用开发者，集中讨论数据统计、海量数据分析算法、知识表示、 知识运用等问题。 数据挖掘( d a t am i n i n g ) 是指从大量的、真实的、含噪音的数据中提取有 用的、隐藏的、用户感兴趣的信息和知识的过程【l j 。因此，数据挖掘也被称为知 识挖掘、知识提取、知识发现等。自上世纪9 0 年代以来，数据挖掘技术广泛应 用于生物、医学、天气预报、销售分析等领域，用来发现对象的演化规律和变化 兰州大学硕士研究生毕业论文 趋势。其挖掘步骤如下： 1 明确挖掘任务 数据挖掘人员与领域专家合作，对问题进行深入的分析，清晰地定义出挖掘 任务。认清数据挖掘的目的是数据挖掘前提，挖掘的最后结果是不可预测的，但 要探索的问题应是可预见的。 2 数据的准备和选择 了解相关的源数据结构并加以分析，确定数据选择的原则。并根据用户的要 求从数据库中提取与挖掘任务相关的数据。 3 数据预处理 存在不完整的、含噪声的和不一致的数据是人型的、现实世界数据库或数据 仓库的共同特点i i 】。检查数据的完整性及数据的一致性，对其中的噪声数据进行 处理，对缺失的数据利用统计方法进行填补。数据预处理技术可以改进数据的质 量，从而有助于提高其后的数据挖掘的精度和性能。常用的技术有数据清理( 消 除噪声数据、空缺值和不一致数据) 、数据集成和变换、数据归约、数据压缩和 数值数据的概念分层。在数据挖掘之前运用合理的预处理技术，可以大大提高数 据挖掘模式的质量，降低实际挖掘所需要的时间。 4 数据挖掘 运用选定的算法，从数据中提取出用户所需要的知识。数据挖掘是k d d 最 关键的步骤，也是技术难点所在。采用的技术包括：决策树、分类、聚类、粗糙 集、关联规则、神经网络和遗传算法等。数据挖掘根据k d d 的目标，选取相应 算法，分析数据，得到相应的知识模式类型。 5 评价和解释 模式是由数据挖掘得到的模型，可能没有实际意义或使用价值，或不能准确 反映数据的真实含义，甚至在某些情况下是与事实相反的，因此对于数据挖掘的 结果需要进行评估，以确定哪些是有效的、有用的模式。一般使用兴趣度度量来 识别真正有趣的模式。将挖掘出来的模式解释成应用知识并集成到业务信息系 统，根据知识本身描述的关系或结果给决策者提供技术支持。 2 兰州大学硕士研究生毕业论文 卜一数据准备和选择十数据预处理叫+ 数据挖掘 斗结果表示及解释- - i 知识 图1 1 数据挖掘的阶梯处理过程模型 数据挖掘的基本功能和可以发现的模式类型如下： 1 概念类描述( c l a s s c o n c e p td e s c r i p t i o n ) 数据可以与类或概念相关联。用汇总的、简洁的、精确的方式描述每个类和 概念称为概念类描述。主要的方法有：( 1 ) 数据特征化，是目标类数据的一般 性特征或特性的汇总；( 2 ) 数据区分，将目标类对象的一般特性与其他类的一般 特性相比较。 2 关联规则( a s s o c i a t i o na n a l y s i s ) 数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量 的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、因 果关联。关联规则挖掘是无指导学习系统中挖掘本地模式的最普通模式，利用该 过程可以获取数据集中事先并不了解或不确定的有价值信息。 3 分类( c l a s s i f i c a t i o n ) 分类是在一部分数据( 训练集) 上找出描述并区分数据类或概念的规律和模 型，以便能够使用模型预测类标记未知的对象类。在分类的基础上可以进一步推 演以实现推测数据对象的类标记和部分数据值。分类常用的方法：决策树方法、 粗集方法、贝叶斯方法、人工神经网络方法和遗传算法等。 兰州大学硕土研究生毕业论文 4 聚类( c l u s t e r i n g ) 把数据划分到不同的组中，组之间的差别尽可能大，组内的差别尽可能小。 与分类不同的是，分类中知道训练集的分类属性值，而进行聚类时，需要在训练 集中找到这个分类属性值，聚类可以直接满足用户的要求，同时也是概念描述和 异常值分析的基础。聚类技术主要包括传统的模式识别方法和数学分类学。 5 孤立点分析( o u t l i e ra n a l y s i s ) 在系统巾存在一些数据，它们不符合数据的一般模型，与其他数据对象不同 或不一致，这样的数据对象被称为孤立点。孤立点在一些应用巾非常重要，隐藏 着重要的信息，如欺诈行为检测。因此，孤立点分析和检测是一种非常有价值的 数据挖掘任务，主要的孤立点分析方法有：基于统计的孤立点检测、基于距离的 孤立点检测、基于偏离的孤立点检测。 6 演变分析( e v o l u t i o na n a l y s i s ) 演变分析是通过数据分析描述行为随时间变化的规律和特征，并对其建模。 主要的演变分析方法包括：时间序列数据分析、序列或周期模式匹配和基于相似 性的数据分析。 7 序列模式挖掘( s e q u e n c ep a t t e r nm i n i n g ) 序列模式挖掘是从序列中发现蕴含的序列模式。时间序列模式挖掘与关联规 则挖掘有许多相似之处，前者一般是发现与时间属性相关的高频率子模式，后者 一般是在忽略时间属性的情况下，发现项目之间的关联性。 图1 2 给出了数据挖掘系统结构图。其中，数据挖掘引擎是数据挖掘系统的 核心部分，由一组实现具体挖掘功能的算法组成。 知识库主要是是存放领域知识，用于指导搜索或评估模式的兴趣度。另外， 知识库还包括兴趣度阈值和元数据( 描述来自多个异种数据源的数据) 。模式评 估部分主要是使用兴趣度度量方法，识别表示知识的真正有价值的模式。数据库 和数据仓库主要根据用户的数据挖掘主题目标和具体的挖掘任务提供数据资源。 随着信息化水平的提高，证券、金融、保险和医疗等行业逐渐成数据密集型 行业，如何发现其中的隐含信息以避免金融犯罪、违规操作等行为越来越受到关 注。但是这些数据与时间紧密相连，利用传统的挖掘方法已经不能达到预期目标。 因此，时间序列数据挖掘( t i m es e r i e sd a t am i n i n g ，t s d m ) 技术应运而生，成 4 兰州人学硕士研究生毕业论文 为数据挖掘的一个重要研究方向。 图1 2 典型的数据挖掘系统结构l i j 时间序列挖掘通过对过去历史行为的客观记录分析，揭示其内在的规律( 如 波动的周期、振幅、趋势的种类等) ，进而完成预测未来行为等决策性工作。期 望通过对时间序列的分析，从大量的数据中发现和揭示某一现象的发展变化规律 或从动态的角度刻画某一现象与其他现象之间的内在数量关系，以掌握和控制未 来的行为。 时间序列的研究必须依据合适的理论和技术进行，时间序列的多样性表明其 研究必须结合序列特点找到合适的建模方法。 1 2 主要工作及创新 本文系统地介绍了时间序列挖掘技术，包括时间序列的数据清理、数据分割、 表示和相似性度量等技术。论文主要研究了时间序列的分段表示方法。本文的主 要的研究工作内容及成果如下： 兰州人学硕士研究生毕业论文 时间序列是随时间变化的属性值的序列，是信息系统中普遍存在的一类 重要数据对象，如股票行情数据。由于原始时间序列具有高维性、类型 复杂和富含噪声的特点，直接在时间序列上执行数据挖掘任务，往往导 致算法效率低下和挖掘结果不可靠。本文在分析了经典自顶向下、自底 向上和滑动窗口算法的基础上，针对滑动窗l j 算法出现的“过拟合”的 分段，通过检测前后两个分段趋势的相近程度，对趋势相近的分段进行 合并，从而有效地避免了尖峰形态数据的影响；针对“欠拟合”的分段， 采用了一种新的度量方法，对“欠拟合”的分段进行适当分割，从而得 到更好的表示效果。实验结果表明：以上两种改进策略效果明显。 针对数据流上的应用，本文提出了一种适合在线分割的时间序列表示算 法叫s w ( r e f i n e ds 1 i d i n gw i n d o w ) 算法，该算法基于滑动窗口算 法框架，应用了文中提出的两种改进策略，实验结果表明：r s w 是一种适 合在线分割的时间序列表示算法，具有线性复杂度和拟合误差小的特 点。 1 3 本文组织结构 本文共分五章，下面简要介绍一下各章的内容： 第一章：阐述了课题的研究背景和意义，以及本文的主要工作和组织结构； 第二章：时间序列挖掘问题综述。系统地介绍了时间序列挖掘相关技术，包 括时间序列的数据清洗、分割、表示、相似性性度量和预测。 第三章：对时间序列的表示分段表示算法进了详细描述，并介绍了相关研究 的工作进展。分析了线性分段表示算法的优缺点，针对算法出现的“过拟合 和 “欠拟合 的问题，提出了两种改进策略，并给出了算法的伪代码和实验效果。 第四章：针对时问序列在线分割的现实需求，应用第三章中提到的两种改进 策略，提出了一种基于s 1 i d i n gw i n d o w 算法的时间序列在线分割表示算法二一 r s w 算法，并通过实验对算法性能进行了验证。 第五章：对全文进行总结和展望。全面总结研究工作的内容，并提出下一步 的研究方向。 6 兰州大学硕： = 研究生毕业论文 第二章时间序列挖掘问题综述 2 1 研究背景 随着计算机技术的广泛应用和存储介质的大量供应，在日常的事务处理和科 学研究中，人们积累了大量的各种类型的数据，它们被描述为“数据丰富，信息 贫乏”。面对快速增长的海量级的数据，人们迫切需要强有力的数据分析工具， 来分析和理解数据，进而辅助决策和规划。 数据挖掘白上世纪9 0 年代以来，被广泛应用于生物、医学、天气预报、销 售分析等领域，用来发现对象的演化规律和变化趋势。数据挖掘可以发现的模式 类型有：概念，类描述、关联分析、分类和预测、聚类、孤立点分析和演变分析 等。 时间序列是随时间变化的属性值的序列，是信息系统中普遍存在的一类重要 数据对象，如股票行情数据。通过提取隐含在时间序列中的模式来应用于时间序 列的预测与聚类，以反映属性值在时间和空间上的特征。一方面，由于时间序列 的数据类型复杂多变、有噪声、高维性等特点，使得时间序列的挖掘成为极具挑 战一个领域；另一方面，时间序列广泛存在于日常事务处理的方方面面，因此时 间序列挖掘成为近年来成为数据挖掘学者关注的热点，其研究的方向有：时间序 列模式的表示、时间序列的相似性度量、时间序列的查询等。 2 2 时间序列挖掘技术概述 时间序列的数据挖掘技术自2 0 世纪9 0 年代以来有了快速发展，由最初的相 似性分析到目前的包含人工智能的多学科交叉研究。时间序列挖掘就是从大量的 时间序列数据中提取人们事先不知道、但又是潜在有用的与时间属性相关的信息 和知识，并用于短期、中期或长期预测，指导人们的社会、生活、经济和军事等 领域。 时间序列( t i m es e r i e so rt i m es e q u e n c e ) 是指随时间变化的属性值序列或 事件序列。由于前后时刻的数值或数据点的相关性往往呈现出某种趋势或周期性 7 兰州人学硕士研究生毕业论文 变化，因而时间序列里蕴藏着着其它信息形式所不b 皂 - t 替的知识。 时间序列是一种非常重要的数据类型，在商业应用和科学研究中广泛存在着 大量的时间序列，通过分析和处理这类数据，对自然和社会科学领域的预测、决 策和发展具有重大意义。 时间序列数据挖掘技术通过提取时间序列巾的隐含模式，将其应用于时间序 列的预测与聚类中，以反映属性值在时间和空间上的特征。由于时间序列的数据 类型复杂多变、有噪声、高维性等特点，时间序列的挖掘成为极具挑战性的一个 领域。此外，它广泛存在于日常事务处理的方方面面，因此成为近年来数据挖掘 学者关注的热点。其研究方向包括： l 、时间序列的归约 通过对数据集归约，得到原数据集的近似表示。保持了原数据的特征信息， 而数据量小得多。时间序列的归约是对时间序列进行抽象和概括的特征表示方 法，在更高层次上对时间序列进行重新描述。常用的方法有奇异值分解( s v d ， s i n g u l a rv a l u ed e c o m p o s i t i o n ) 、离散傅立叶变换( d f t ，d i s c r e t ef o u r i e r t r a n s f o r m ) 、离散小波变换( d w t ，d i s c r e t ew a v e l e tt r a n s f o r m ) 、符号映射和 分段线性表示( p l r ，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 ) 。维归约的任务是： 在保留主要特征模式的情况下，忽略部分数据，用尽可能小的空间完成原时间序 列的近似表示。 2 、时间序列的划分 对给定的包含n 个时间点的时间序列q 构建模型，将其分为k 个部分( k m a x _ e r r o r 计算 a n c h o r ：i - l 】，d a t a ( a n c h o r ：i - 1 ) 的线性回归表示序列，并存入b e s t ； k = k + 1 ：新的分段 保存第k 段的结束时刻，开始值和结束值 s e g j s ( k ) ：( i - l ，b e s t ( 1 ) ，b e s t ( e n d ) ) ； a n c h o r = i ：开始新的窗口 e n d ； e n d ； 处理最后一段 k = k + l ； 保存最后一段的结束时刻，开始值和结束值 s e g _ t s ( k ) = ( 1 e n g t h ( d a t a ) ，b e s t ( 1 ) ，b e s t ( e n d ) ) ； 图3 1s l i d i n gw i n d o w 算法伪代码 兰州人学硕士研究生毕业论文 3 4 2t o pd o w n 算法 自顶向下法( t o pd o w n ) ：首先扫描整个时间序列，找到最佳分割点将序列 分为2 个子序列，分别计算两个子序列的拟合误差。如果某个子序列拟合误差大 于阈值，则继续对该子序列用相同的方法再进行细分，直到所有子序列的拟合误 差都小于阈值。 t o p - d o w n 算法 输入：时间序列d a m ，最大累积误差阈值m a xe r r o r 输出：分段表示序列s e g _ t s b e s t s o f a r = i n f ； 力，i _ 2t ol e n g t h ( t ) 一2 计算使用第i 个点分割的参考值，记为v a l u e ( i ) e n d ； 【e ，b p 】_ m a x ( v a l u e ( ：) ) ； 计算d a t a 1 ：b p 的拟合误差e ； 矿e m a x _ e r r o r s e g j s l = t o p _ d o w n ( t 1 ：b p 】) ； e n d ； 计算d a t a b p + l ：l e n g t h ( d a m ) 的拟合误差e ； 1 7 r e m a x _ e r r o r s e g _ t s r = t o p _ d o w n ( t b p + l ：l e n g t h ( t ) ) ； e n d ； 合并s e g j s l 和s e g _ t s _ r ，并保存到s e g - t s ； 图3 2 t o p _ d o w n 算法伪代码 3 4 3b o t t o mu p 算法 自底向上法( b o t t o mu p ) ：首先把整个时问序列以每2 个点为一段进行分段， 计算相邻两段合并后的拟合误差，每次将误差最小的两段合并，直至任意相邻两 段合并后的误差小于阈值。当第f 段和第f + l 段合并后，算法只需要重新计算合 兰州大学硕l j 研究生毕业论文 并段与第f l 段和第i + 2 段的合并拟合误差。 b o t t o m _ u p 算法伪代码 输入：时间序列d a t a ，最大累积误差阈值m a x , e r r o r 输出：分段表示序列s e g _ t s 户，i l ：2 ：l e n g t h ( d a t a ) l 第i 段和第i + l 段合并，合并的结果记为s e g - t s ； e n d ； 力，i = l ：l e n g t h ( s e g - t s ) - 1 计算第i 段和第i + 1 段合并的代价c o s t ( i ) ； e n d ； 【e ，i 】= m i n ( c o s t ( ：) 】) ； w h i l ee 。令 晒= i f fl e n g t h ( t m ：以】) = l e n g t h ( t p ：g 】) i f fl e n g t h ( t m ：刀】) ：q ( 1 7 ) 将第k 段从p o s 处分割为第k 段和第k + 1 段，并更新 s e g j s ( k ) 和s e g t s ( k + 1 ) ； ，( 1 8 ) a n c h o r = p o s ； 滑动窗v i 重定位 ( 1 9 ) e n d i f , ( 2 0 ) e n d f , 图4 1r s w 算法步骤 r s w 算法采用了环形数据缓冲区b u f f e r ，用来存放需要归约的数据，一般应 该至少可以存放钆5 个分段的时序数据。当从数据流中读入的数据累积误差e 超过阈值时，对序列进行分割。然后分别计算u e 和s e ，动态调整第k 1 分段 和第k 分段的分割位置。 4 4 仿真实验 实验数据取自上证a 股综合指数2 0 0 0 年1 月4 日至2 0 0 6 年1 2 月2 9 日的 收盘点位的时间序列( 数据来源：清华金融数据；网址： h t t p ：t h f d s e m t s i n g h u a e d u o n ) ，共计1 6 8 8 个数据，数据按照式3 - 8 进行规范化 处理，规范化后的数据曲线如图所示。 兰州大学硕：l 二研究生毕业论文 1 0 8 0 6 0 4 0 2 0 1 0 8 0 6 0 4 0 2 0 图4 22 0 0 0 1 4 _ _ 2 0 0 6 1 2 2 9 期间的上证指数收盘点位序列 02 0 04 0 06 0 08 0 01 0 0 01 2 0 01 4 0 01 6 0 01 8 0 0 图4 - 3 当e = 0 4 3 5 时s l i d i n gw i n d o w 算法的分割结果 3 5 兰州人学硕士研究生毕业论文 图4 - 4 当e = 0 4 3 5 ，r = 0 1 5 ，q = 2 8 时r s w 算法的分割结果 如图4 4 所示，r s w 与s l i d i n gw i n d o w 算法相比，更准确地抽取了原时间 序列的特征信息。具体来讲，对于图4 4 中区域a 中的时间序列，s l i d i n gw i n d o w 算法和r s w 算法都没有反映足够的细节。s l i d i n gw i n d o w 算法将a 区域中的时 间序列分割为两段，且两段拟合效果都很差，r s w 算法将其合并为一段，虽然 没有能够反映时间序列变化的细节，但是反映了区域a 中时间序列的总体上升 趋势。对于b 区域中的时间序列，r s w 把握住了明显的状态变化，较好的抽取 了时间序列的特征信息，并且分割位置没有滞后。 总体而言，r s w 算法非常适合时间序列的在线分割和表示，可以抽取时间 序列的人部分特征信息，且分割位置恰到好处，在数据归约和信息抽取之间取得 了较好的平衡。同时，r s w 算法具有线性复杂度的优点，适合海量数据处理。 兰州大学硕上研究生毕业论文 5 1 总结 第五章总结与展望 本文主要研究了时序数据的维归约技术。论文首先系统地介绍了时间序列挖 掘技术，包括时间序列的数据清理、数据分割、表示和相似性度量等技术。论文 在分析了经典自顶向下、自底向上和滑动窗口算法的基础上，针对滑动窗口算法 出现的“过拟合 的分段，通过检测前后两个分段趋势的相近程度，对趋势相近 的分段进行合并，从而有效地避免了尖峰形态数据的影响：针对“欠拟合 的分 段，采用了一种新的度量方法，对“欠拟合”的分段进行适当分割，从而得到更 好的表示效果。实验表明这两种改进策略显著的减小了算法的拟合误差总和，在 视觉上更能反映时间序列的趋势信息。以上两种策略在提高算法分割的同时，人 为得增加了算法的参数，而这些参数的确定在不同领域应用领域有不同的取值， 这是改进策略的缺点所在。 针对t o pd o w n 和b o t t o mu p 算法拟合误差小，但却不适合联机环境，而 s l i d i n gw i n d o w 算法适合联机应用，但拟合效果不理想的现状，文中提出的一种 新的时序数据维归约算法r s w 。r s w 基于滑动窗口算法框架，应用了文中提出 的两种改进策略，实验结果表明：r s w 是一种适合在线分割的时间序列表示算法， 具有线性复杂度和拟合误差小的优点。 5 2 下一步研究工作的展望 本阶段我们主要的研究重点是时间序列的维归约算法，其中以线性分段算法 为主。下一阶段的主要目标是在进一步完善我们所做的基础理论研究工作的基础 上，进行与时序数据维归约问题相关的应用研究。 文中通过分析滑动窗口算法在时序数据维归约问题上的不足，提出了对时序 数据历史分段进行分割和合并的度量方法，从而可以动态地调整分割点的位置， 使得基于滑动窗口的维归约算法更为准确地抽取了时间序列的特征信息，从而为 后续的数据挖掘算法提供了保证。文中阐述的动态调整分割点的思想，可以有效 3 7 兰州人学硕士研究生毕业论文 地解决滑动窗口算法分割点位置不精确的弊端，并且这种改进保持了滑动窗口算 法线性复杂度和适合在线归约的优点。我们将继续沿着这一思路，寻找抽取特征 更准确的时序数据维归约算法。 文中提出的对时序数据历史分段进行分割和合并的度量方法，使用了额外的 参数r 和q ，这使得归约任务需要人工干预，以确定合适的参数。我们将在以 后的工作中研究参数r 和q 的物理意义，进一步研究在噪声环境下更加符合视 觉要求的时间序列维归约算法。 3 8 兰州大学硕士研究生毕业论文 参考文献 1 h a nj ，k a m b e rm d a t am i n i n gc o n c e