（管理科学与工程专业论文）时间序列数据挖掘中相似性和趋势预测的研究.pdf

天津大学博士学位论文 中文摘要 时间序列存在于社会的各个领域，对于时间序列数据挖掘的研究目前主要集 中在相似性搜索和模式挖掘上。在相似性搜索研究中存在的主要问题是时间序列 数据量过大，一个有效的解决办法是对时间序列进行重新描述，减小数据量。在 模式挖掘方面，趋势预测是一个比较新的思路，它从时间序列数据中抽取决定时 间序列的行为发展趋势的静态属性，组成静态数据库，然后将泛化性能较强的分 类技术应用于静态数据库中挖掘分类规则，对行为发展趋势做出预测。 相似性研究中有效的数据描述是提高相似性搜索效率的关键，本文第二章提 出了一种结构自适应的时间序列分段线性化表示方法，该方法可以自动地产生线 性化的段数k 。大大压缩了相似性的计算量。同时在分段线性化表示的基础上提 出了一种相似性计算方法，该方法对于时间序列的多种变形都不敏感。 本文拟从时间序列数据库中挖掘到表征时间序列发展趋势的分类规则，首先 必须对时间序列进行静态模式的抽取，得到分类属性。本文就此在第三章深入阐 述了静态模式的抽取方法。 以股票为主要的时间序列研究对象，抽取的静态模式往往含有较多的干扰， 因此需要分类工具必须有较强的泛化性能，为了解决这一问题在第四章采用正则 最小二乘学习算法训练的前馈神经网络，对时间序列的静态模式进行分类。该方 法将正则化和网络裁剪相结合，既提高了泛化性能又精简了网络结构，降低了不 相关属性对分类的影响。 属性约简和规则抽取是粗集理论在数据挖掘中的一个重要应用。由于神经网 络固有的不能得到显式知识的缺陷，第五章将粗集理论应用于神经网络得到的知 识中，从中抽取分类规则将是一种极为有效的解决方法。 k 最近邻分类算法( k n n ) ，在许多领域都有成功的应用，对训练样本进行 浓缩是提高算法计算效率的有效方法。本文在第六章采用简化的c u r e 聚类算 法首先对训练样本中的每一类样本集进行聚类，用聚类后形成的子类代表点代替 属于该子类的所有样本集，再采用一般的k 小n 法，这样大大减小了训练样本的 数量，提高了计算速度。该法可以有效的排除孤立点( 噪声) ，从而也大大提高 了算法的分类精度。 数据分布随时间而变化的数据( 这里称为时变数据) 也是客观存在的，现有的 数据挖掘方法对时变数据很难处理。本文第七章提出了一种带移动窗的神经网络 数据分类算法，网络中存储的分类知识能够随时更新，较好地处理了这类问题。 第八章总结了全文研究内容，并对今后的研究前景进行了展望。 关键词：时间序列，相似性，分类，神经网络，粗集理论，k r i l l 天津大学博士学位论文 a b s t r a c t r e c e n t l yt h es t u d yo nd a t am i n i n go f t i m es e r i e sm a i n l yc o n c e n t r a t e so nb o t ht h e s i m i l a r i t ys e a r c hi nat i m es e r i e sd a t a b a s ea n dt h ep a t t e r nm i n i n gf r o ma t i m es e r i e s i nt h et i m es e r i es i m i l a r i t ys e a r c h ，d u et ot h eh i g hd i m e n s i o n a l i t yo ft h ed a t a ，a n e f f i c i e n t t e c h n i q u e f o rt h e s i m i l a r i t yc o m p u t a t i o n i s v e r ya n x i o u s i nt h ep a t t e r n m i n i n gt h et r e n dp r e d i c t i o ni s an e wd o m a i n i te x t r a c t st h es t a t i ca t t r i b u t e sf r o ma t i m es e r i e st h a ta r et h em o s ti m p o r t a n tp r e d i c t i n ga t t r i b u t e s t h o s ea t t r i b u t e sc a r l b e c r e a t e das t a t i cd a t a b a s e t h e n ，ah i g hg e n e r a l i z e dc l a s s i f i c a t i o nt e c h n i q u ec a r lb eu s e d t om i n er u l e sf r o mt h et i m es e r i e s 。 i nt h es i m i l a r i t yr e s e a r c h ，a ne f f i c i e n tr e p r e s e n t a t i o ni sak e yo fd e s c r e a s i n gt h e b u r d e no ft h es i m i l a r i t yc o m p u t a t i o n i nc h a p t e r2 ，w ep r e s e n tas t r u c t u r e a d a p t i v e p i e c e w i s e l i n e a r s e g m e n t sr e p r e s e n t a t i o n o f t i m es e r i e s t h e a l g o r i t h m c a l l a u t o m a t i c a l l yp r o d u c e t h ekp i e c e - w i s e s e g m e n t s o ft i m e s e r i e s ，w h i c hc a n a p p r o x i m a t e t h e o r i g i n a l t i m es e r i e s t h i s s i m p l er e p r e s e n t a t i o n m a k e st h e c o m p u t a t i o no f t h es i m i l a rm e a s u r em o r ee f f i c i e n t a n dw e p r e s e n tam e t h o do f t h e s i m i l a rm e a s u r ew h i c hi s d e s i g n e dt o b ei n s e n s i t i v et o n o i s e ，s h i f t i n g ，a m p l i t u d e s c a l i n ga n d t i m es c a l i n g a st h eb a s i ci s s u eo ft h eo t h e rc h a p t e r s ，i nc h a p t e r3 ，w ee x p a t i a t et h ep r o c e s so ft h e s t a t i ca t t r i b u t e se x t r a c t i o n i nc h a p t e r 4 ，w ea p p l yt h el e a r n i n ga l g o r i t h mo f f e e d f o r w a r dn e u r a ln e t w o r k sb a s e d o nt h er e g u l a r i z e dl e a s ts q u a r e st ot h ec l a s s i f i c a t i o nm i n i n gf r o mt h es t a t i ca t t r i b u t e s d a t a b a s eo ft i m es e r i e s t h ea l g o r i t h mi m p r o v e st h ec l a s s i f i c a t i o np e r f o r m a n c eo f f e e d f o r w a r dn e u r a ln e t w o r k s t h r o u g hc o m b i n i n g t h e r e g u l a r i z a t i o n a n dp r u n i n g t e c h n o l o g y i n 廿l er o u g hs e t t h e o r y , t h ea t t r i b u t er e d u c t i o na n dt h ev a l u er e d u c t i o na r et w o i m p o r t a n ti s s u e s t h e yc a n b eu s e dt om i n et h ec l a s s i f i c a t i o nr u l e sf r o mt h ed a t a b a s e i nc h a p t e r5 ，w eu s eav a l u er e d u c t i o na l g o r i t h mi nt h er o u g hs e tt h e o r yt oe x t r a c tt h e r u l e sh i d d e ni nt h er e g u l a r i z e df e e d f o r w a r dn e u r a ln e t w o r k s u c hac o m b i n a t i o n g e n e r a t e sa e x c e l l e n tr e s u l t s k n e a r e s tn e i g h b o r sr u l e ( k 小n ) i so n eo ft h em o s tw i d e l yu s e dc l a s s i f i c a t i o n t e c h n i q u e s b u ti t sd r a w b a c k i st h a ti tm a yi n c u re x p e n s i v ec o m p u t a t i o n a lc o s tw h e n t h en u m b e ro ft r a i n i n gs a m p l e si sg r e a t i nc h a p t e r6 ，w ep r e s e n ta l li m p r o v e dk - n n a l g o r i t h m t h ec u r ec l u s t e r i n gi sf i r s tc a r r i e do u tt os e l e c tt h es u b s e to f t h et r a i n i n g s e t ，a n dt h e nag e n e r a lk - n ni su s e d t h ep r e s e n ta p p r o a c hc a nl a r g e l yr e d u c et h e v o l u m eo ft h e t r a i n i n g s e ta n do m i to u t l i e r s t h e r e f o r ei tc a r ll e a d t ob o t h 天津大学博士学位论文 c o m p u t a t i o n a le f f i c i e n c ya n dh i g h e rc l a s s i f i c a t i o na c c u r a c y k n o w l e d g ed i s c o v e r yi nt i m e v a r y i n gd a t a b a s e si s a ni m p o r t a n ts u b j e c to fd a t a m i n i n gt e c h n o l o g y t h ep r e v i o u s1 k e r a t u r e sd i d n tp r e s e n ta n ye f f i c i e n ta l g o r i t h mt o m i n e k n o w l e d g e i nt i m e - v a r y i n gd a t a b a s e s i nc h a p t e r7w e p r e s e n t a m o v i n g - w i n d o w n e u r nn e t w o r kc l a s s i f i c a t i o na l g o r i t h mt h a tc a l le f f e c t i v e l yc l a s s i f yt h et i m e v a r y i n g d a t a t h ek n o w l e d g es t o r e di nt h en e t w o r kc a l lb e u p d a t e dw i t ht h et i m e t h e g e n e r a l i z a t i o np e r f o r m a n c eo ft h ep r e s e n ta l g o r i t h mi sh i g h e rt h a nt h a to fg e n e r a l n e u r a ln e t w o r k sc l a s s i f i c a t i o na l g o r i t h m c h a p t e r8s u m m a r i z e s t h ei m p o r t a n tr e s e a r c hr e s u l t si nt h i sd i s s e r t a t i o n ，a n dp o i n t s o u tt h ep r o b l e m st h a ta r ew o r t h yo f 血r t h e rr e s e a r c hi nt h ef u t u r e k e y w o r d s ：t i m e s e r i e s ，s i m i l a r i t y , c l a s s i f i c a t i o n , n e u r a ln e t w o r k s ，r o u g hs e tt h e o r y , k - n e a r e s t n e i g h b o r 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加阻标注和致谢之处外，沦文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨注盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：多晚曩孥 签字同期：w 哆年多月，日 学位论文版权使用授权书 本学位论文作者完全了解苤盗盘兰 有关保留、使用学位论文的规定。 特授权墨注苤鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权况明) 学位论文作者签名 溯日擎 翎虢咖砍 签字目期：v ，；年月，口日签字日期：少哆年，月7 。同 第一章绪论 第一章绪论 本章首先从数据挖掘的角度出发简要回顾了时间序列的发展，然后重点介 绍时间序列数据挖掘的研究现状，以及分类技术的主要方法及其简单评述。同 时介绍了有关时间序列数据挖掘的各个研究方向，并对此做出评述，指出今后 的研究方向。 1 1 选题的研究背景与研究意义 首先说明的是，从系统的角度出发对时间序列的分析是自上个世纪6 0 年 代开始8 0 年代趋于成熟的，而本文是从数据挖掘的角度出发对时间序列进行 分析，是指从中获得正确的、隐含的、有潜在应用价值和晟终可理解的模式的 非平凡过程【”。 数据挖掘是多门学科和多门技术相结合的产物，也是个非常年轻而又活 跃的研究领域。在促进数据挖掘诞生、发展、应用的众多原因中，主要有4 种，即超大规模数据库的出现、先进的计算机技术、经营管理的实际需要和对 这些数据的精深计算能力。从经营管理角度出发，进入2 1 世纪以后，全球经 济一体化的进程日益加快，企业所面临的市场竞争压力日趋严重，企业经营管 理者特别是决策者希望能够从企业积累的大量历史数据中找到应对日趋严重 的竞争压力良方，希望能够从这些数据中找到经营管理中问题的根本原因，能 够快速从大量数据中挖掘出对经营管理有用的信息，以应对瞬息万变的市场压 力。因此可以说数据挖掘技术是一个对管理决策者提供决策支持的有力工具。 时间序列数据存在于社会的各个领域，如科学研究记录：包括天文观测， 气象图像等。病历记录：包括病人的每次看病的病情记录以及，t l , 电图等扫描仪 器的数据记录等。金融和商业交易记录：如股市每天的交易价格及交易量，超 级市场每种商品的销售情况等。时间序列几乎无处不在。随着科学技术的不断 发展，计算机以及存储设备的存储容量日益增大。时间序列数据库也越来越大， 因此对于时间序列的数据挖掘的研究显得愈发必要。 相对于数据挖掘较成熟的部分而言( 如关系数据库中关联规则和分类规则 的挖掘等) ，针对于时间序列数据挖掘的研究是数据挖掘研究领域中的较新的 一个分支，目前国际上对于时间序列的数据挖掘的研究逐步成为一个新的热 点，但国内在这方面的研究文献尚不多见，比较重要的工作有1 9 9 8 年欧阳为 民等曾经从理论框架的角度对时态数据挖掘做过介绍和分析1 2 】。 1 第一章绪论 时间序列的数据挖掘技术早在上个世纪9 0 年代已经有人提出，主要是对 时间序列的相似性搜索，此后在此基础上又出现了时间序列数据库中子序列匹 配的和整体匹配的研究 3 - 8 1 。在这些相似性计算过程中都存在时间序列数据量 过大的问题，这将引起搜索效率的大大降低，因此时间序列的有效描述将是提 高搜索效率【9 。1 4 】的方法之一，由p a v l i d i s 1 5 最早提出分段线性化描述是用直线 段来近似拟合原始时间序列的形状，这样用直线段来代替原始数据将大大减少 了数据量，此后k e o g h 1 6 】又作了进一步的研究，但是在文献 1 7 1 中提到的分段 线性化方法计算量较大，需要多次迭代，这一缺点在数据量大时尤为明显，而 且其中采用的相似性测量方法对于时间轴按比例缩放的情况是敏感的，然而这 一现象在实际时间序列中是经常出现的，因此解决这一问题也是相当重要的。 在相似性的基础上，人们又发展出了许多模式识别的方法，如通过相似性 计算对时间序列进行分类 1 7 】、聚类1 1 8 1 等。关于时间序列的数据挖掘技术除了 相似性的研究外，还有其他的一些更接近于人类思维方式的研究方法即模式挖 掘方法 1 9 , 2 0 l ，如关联规则的抽取 1 9 l ，可以得到形如“如果某一天m i c r o s o f t 上 涨而且i n t e l 下降，则i b m 第二天上涨”的规则，而文献【2 0 】提出可以从时间 序列中抽取分类规则，但是这种方法有一个前提条件，即是必须对时间序列进 行预处理，从中预先抽取静态模式，然后从模式中提取对时间序列影响较大的 特征属性，对时间序列进行趋势预测。这种分类规则的提取对于科学观测数据 的分析以及金融经济的预测将会提供有效的帮助。但是文献 2 0 】中采用的规则 挖掘方法得到的预测精度比较低，有待于研究更有效的、泛化能力更强的分类 规则挖掘方法。 前馈神经网络作为数据挖掘的分类工具，已有很多论文发表【2 。”j ，但是前 馈神经网络固有的缺点( 如过拟合、分类规则的知识表示无法理解等) 使得人们 提出了各种各样的改进模型以便提高泛化性能【2 5 】或从训练好的神经网络中提 取分类规则【2 6 q6 1 。但现有算法存在各种各样的局限性，有待进一步的改进以 提高适用性。同时可以将神经网络和其他不同的分类技术如粗集理论、模糊逻 辑、机器学习等规则生成技术进行信息融合，互相取长补短，提高分类精度。 属性分布随时间变化的时变数据也是存在于很多领域，比如半导体制造p 4 过程是经常在工程师的指导下做出改变的，以便快速地达到较高的生产率，从 上个月数据中抽取的知识不可能正确的预测本月的状态。因此普通的分类技术 将不再适用于时变数据的挖掘。因此提出一种针对于时变数据的分类技术显然 是很必要的，但迄今研究的人并不多，本文的研究将为时变数据库的分类技术 提供一种有力的工具。 2 第一章绪论 1 2 数据挖掘概论 数据挖掘是2 0 世纪9 0 年代兴起的一项新技术，它是知识发现的关键步骤， 国内外学术界和企业界都非常重视对数据挖掘技术和软件工具的研究和开发。 面对信息社会中数据和数据库的爆炸式增长，人类分析数据和从中提取有 用信息的能力远远不能满足实际需要。所以迫切需要一种能够智能的自动地把 数据转换成有用信息和知识的技术和工具。数据库管理系统和人工智能中的机 器学习两种技术的发展和结合促成了知识发现( k d d ，k n o w l e d g ed i s c o v e r yi n d a t a b a s e ) 这一新技术的产生。1 9 8 9 年8 月在美国底特律召开的第1 1 界国际人 工智能联合会议的专题讨论会上首次提出了k d d 。它是一门交叉性学科，内 涵极为广泛，理论和技术难度很大，所以使针对大型数据库的k d d 技术一时 还难于满足应用需要。于是1 9 9 5 年，在美国计算机年会( a c m ) j 二提出了数据 挖掘( d a t am i n i n g ) 概念。也有一些文献把数据挖掘技术称为知识抽取 ( k n o w l e d g ee x t r a c t i o n ) 、数据考古学 a t aa r c h a e o l o g y ) 、数据捕捞( d a t a d r e d g i n g ) 等等【3 - q 。多数人认为数据挖掘是k d d 过程的关键技术见图1 1 ，从 而不加区分的使用知识发现和数据挖掘两个术语。 选择预处理 转换数据挖掘解释 黼t 竺工二竺r 竺工：三y 识 图1 - 1 k d d 过程 1 2 1 数据挖掘定义 从技术角度看，数据挖掘是指从数据库中抽取隐含的、潜在的、先前未知 的、有用的信息如知识、规则、约束和规律等的一个非平凡过程”。从广义 上理解数据、信息也是知识的表达形式，但人们更将概念、规则、模式、规律 和约束等看成知识。 人们将数据看作形成知识的源泉，原始数据可以是结构化的，如关系数据 库中的数据；也可以是半结构化的，如文本、图像数据；甚至是分布在网络上 的异构数据。发现知识的方法可以是数学的、非数学的、演绎的和归纳的。发 现的知识可以用于信息管理、查询优化、决策支持和过程控制等。它把人们对 数据的应用从低层次的简单查询提升到从数据库中挖掘知识，提供决策支持。 3 第一章绪论 1 2 2 数据挖掘系统的分类【3 9 l 数据挖掘是一门交叉学科，受多个学科的影响，包括数据库系统、统计学、 机器学习、可视化和信息科学等。此外依赖于所用的数据挖掘方法，以及可以 使用的其他学科技术，如神经网络、模糊逻辑、粗集理论、知识表示、归纳逻 辑程序设计或高性能计算等。 由于数据挖掘源于多个学科，因此数据挖掘研究就产生了大量的、各种不 同类型数据挖掘系统，这样就需要对数据挖掘系统给出一个清楚的分类。从不 同的角度出发，对数据挖掘系统术有几种分类，主要是根据挖掘的数据库的种 类、根掘得到的知识分类和所使用的技术分类【l 】。 ( 1 ) 根据数据库分类数据挖掘所基于的数据库类型有：关系型、事务型、 面向对象型、推论型( d e d e c t i v e ) 、空间型、时序型、多媒体型、异质型 ( h e t e r p g e n e o u s ) 、主动型( a c t i v e ) 、遗留型( 1 e g a c y ) 、文本挖掘和基于网络信息的 挖掘等。 ( 2 ) 根据得到的知识分类包括关联规则、特征规则、分类规则、判别 ( d i s c r i m i n a n t ) 规则等的挖掘和聚类、演变( e v o l u t i o n ) 分析、偏差( d e v i a t i o n ) 分析、 孤立点分析和相似性分析等，此外根据所挖掘的知识的抽象层次进行划分，可 以包括原始层知识( 在原始数据层) 、多层次知识和高层次知识的数据挖掘。 ( 3 ) 根据所采用的技术分类常用的数据挖掘技术有 人工神经网络：它从结构上模仿生物神经网络，是一种通过训练来学习的 非线性预测模型。可以完成分类、聚类和特征挖掘等任务。 决策树：用树型结构来表示决策集合。这些决策集合通过对数据集的分类 产生规则，典型的决策树方法有分类回归树( c a r t ) 、c 4 5 等，其典型应用为 分类规则的挖掘。 遗传算法口9 ：是一种新的优化技术，基于生物进化概念设计了一系列的 过程来达到优化的目的。这些过程有基因组合、交叉、变异和自然选择等。遗 传算法易于并行计算，并且已经应用于分类和其他优化问题。 粗集理论：它是一种研究不确定性问题的数学工具，作为集合论的扩展， 主要用于研究不完全和不完整信息描述的数据挖掘技术。可以用于分类，进行 特征归约和最小属性子集归约。 模糊逻辑：通过隶属度函数定义分类系统的“模糊”闽值或边界，从而可 以产生人们易于理解的分类规则。 最近邻技术：通过k 个与之相近的历史记录的组合来辨别新的记录，也 称为k 最近邻技术。主要应用于分类、聚类和偏差分析等。 可视化：采用直观的图形方式将信息模式、数据的关联或趋势呈现给决策 4 第一章绪论 者，决策者可以通过可视化技术交互式的分析数据关系。 1 3 时间序列数据挖掘的研究进展及评述 时间序列的数据挖掘技术自2 0 世纪9 0 年代以来有了快速的发展。由最初 的相似性的分析到目前的人工智能的多学科交叉研究，时间序列的数据挖掘技 术已经有了多个研究方向。 相似性的研究是时间序列的一个最基本的而且比较困难的问题，所谓相似 性简单的说是指测定两个给定的时间序列是否具有相似的行为曲线，这个问题 之所以困难是因为时间序列往往是来自于实际，因此对于相似性的测量要求并 不是完全严密的，而且时间序列数据库来自于各个领域，测量标准也不尽相同。 随着数据挖掘技术的不断发展，产生了各种挖掘技术，因此这些技术在相似性 的基础上也不断的被应用于时间序列数据库，比如对时间序列进行聚类【4 叫2 1 、 分类【1s , 4 3 ，产生关联规则1 9 , 4 4 1 等。 时间序列研究的另一个基础问题是时间序列的索引( i n d e x ) 问题1 4 ”，即给 定一个时间序列集o ，索引技术是指能够在q 中尽快的找到与给定时间序列q 最相似的序列子集q 1 ，当然索引技术也需要相似性的计算。 无论是相似性研究还是索引技术，时间序列的有效的描述( r e p r e s e n t a t i o n ) 仍然是提高计算效率的一个关键途径【1 9 1 。 关于时间序列的数据挖掘技术除了相似性的研究外，主要还有模式挖掘的 研究，其中主要包括时态模式挖掘和趋势预测。时态模式挖掘的一个主要技术 是关联规则的挖掘 1 9 1 。趋势预测采用的主要是分类规则的挖掘技术，即 l a s t ，m 2 0 提出的首先对时间序列进行预处理，然后从中抽取关键的预测属性 ( p r e d i c t i n ga t t r i b u t e s ) ，这些属性对时间序列的发展趋势影响较大，将其组成属 性集，这些预测属性表征了时间序列的某种特性，这种特性与时间没有关系， 因此可以采用普通的静态的数据挖掘工具对时间序列进行行为趋势的分类预 测。 1 3 1 时间序列的定义 时间序列是指随时间变化的序列值或事件，时间序列数据库是指由随时间 变化的序列值或事件组成的数据库。这些值或事件通常是在等时间间隔测得 的。以数学方式表达为如下： 定义1 1 ：一个时间序列数据库是指一系列记录b 羔。，为序列值的个数， 其中每个记录为m + l 维数据，即o = h ，日：，f ， ，d ，为特性值，可以是 5 第一章绪论 连续实数也可以是离散数据，而且可以是与时间有关联也可以没有。如果某特 性值与时间有关，则该特性值为动态特性，否则为静态特性，一般时间序列的 研究主要是针对动态特性。f ，是一个时间间隔的标志，例如天、月、年等。 现举例说明上述定义，以股票每天的交易记录为例， r ，= 6 0 0 6 8 0 ，邯郸钢铁，8 0 5 ，8 0 6 ，7 8 8 ，7 9 4 ，3 1 0 6 5 ，2 4 ，其中6 0 0 6 8 0 是股票代码， 邯郸钢铁是股票名称，相继分别为当天的开盘价，最高价，最低价，收盘价， 成交量以及第2 4 个交易日。很显然前两个特性是与时间无关的，为静态特性， 而其他特性值是与时间密切相关的，是动态特性。很显然，对于静态特性研究 的意义不大。 定义1 2 ：对于定义1 1 中的特性值f 可以定义为特性函数z ，其，是时 间的函数，函数的系数可以从特性值d 中得到，其函数表达为 f i ( t x ) = a i ，? ，其中3 t x i 一般对于时间序列的数据挖掘的研究往往集中于某个重要的单个特性值， 如股票时间序列数据库中主要研究股票的每日收盘价，因为这是影响投资者决 策行为的主要因素。 1 3 2 时间序列数据挖掘的相关研究 目前，国内外研究资料中对时间序列数据挖掘的研究内容还比较零乱，并 没有系统的理论框架，在对当前时间序列数据挖掘的主要工作进行整理后，本 文认为时间序列的研究工作主要集中在相似搜索和模式挖掘等方面，分述如 下。 一、相似搜索 通常数据库查询是指要找出符合查询的精确数据，而相似性搜索与之不 同，它是找出与给定查询序列的变化行为最接近的数据序列。其中主要包括子 序列匹配( s u b s e q u e n c em a t c h i n g ) 和整体序列匹配( w h o l es e q u e n c em a t c h i n g ) ”1 ， 子序列匹配是指在时间序列集中找出与给定时间序列相似的所有时间序列，而 整体序列匹配是指找出时间序列集中彼此间相似的序列。在相似性搜索的基础 上又发展出了时间序列的聚类、分类、以及关联规则的抽取等等数据挖掘技术。 无论是那一种相似性搜索的方法或形式都依赖于时间序列相似性的测量 方法上，因此相似性测量是一个关键技术，下面对相似性的测量方法做一下介 绍。 f 一1 相似性测量的基本要求 6 第一章绪论 因为相似性搜索是查询与给定的时间序列变化行为最接近的时间序列，因 此要求相似性的测量不必是精确的匹配( 即完全相同) 。同时由于时间序列的数 据量一般非常大，甚至有数十万上百万的数据量，因此要求相似性的测量方法 一定要效率高。由于相似性测量只是一个基础性的技术，相似性的测量不是目 的，而是要为其他的算法服务，因此要求该相似性算法可以适合于其他的计算， 如已经提到的索引( i n d e x i n g ) 、聚类、规则提取等。 ( 二) 基本的时间序列相似性测量方法 对于时间序列的相似性测量，不同的数据表达形式相似性测量的方法也不 尽相同，主要有以下三种常用的测量方法。 1 欧几里德距离测量方法 对于时间序列数据的相似性分析中，经常采用欧几里德距离作为相似计算 的工具 3 , 4 , 4 6 , 5 4 】，两个时间序列的欧氏距离定义为 定义1 3 假设扛f 是目标时间序列，是两个需要进行相似测量的数据 库中的一个时间序列， ，z 是扛；) 的长度，n 是砂0 的长度，假设 n 。则进 行相似性测量时仅仅考虑t y ，) 的长度为n 的子序列。时间序列0 的 j ( j = n 一”+ 1 ) 个子序列记为扛 ，则测量扛 和j 的相似性的距离矩阵定 义为 m ；n ( 一一k ，z ? ) 2 ( 1 - 1 ) 。 i = l 其中k ，是比例因子。若在进行查询前原始时间序列中的长度为n 的予序 列已经产生，则查询时，每个时间序列需要计算n 一i + 1 次。 采用欧氏距离进行测量的优点是容易计算，易于理解，可以用于索引和聚 类等数据挖掘。但是它的缺点也是不容忽视的，它不允许有不同的基线，如当 两支股票分别在￥2 0 和￥8 0 进行波动时，尽管他们的波形很相似，但是其欧 氏距离会很大。 2 相关性测量 另一个相似性测量是在文献 4 8 】中考虑的相关性测量方法，这种方法不但 能够将相似性作为位置的函数而且不必对原始数据库的时间序列产生所有的 长度为 的子序列。 一个目标时间序列扛， 和时间序列数据库中的序列l y ， 之间的线性相关 定义如下： 7 第一章绪论 铲一j 坠娑兰( 1 - 2 ) 凳。x ；y j 其中i = 1 ，v + 一1 。这种相关性的计算对于扛； 比较长的时间序列其计 算花费是很大的，在这种情况下，傅立叶变换的卷积定理提供了一个很好的解 决办法。首先在扛。) 和b ) 的末尾补充0 使得两个时间序列变为长度都为 f - n + ”一1 的新序列扛；) 和) ，然后对扛： 和涉；) 进行离散傅立叶变换生成 x ， 和亿) ，最后通过逐点相乘讧。) 和佤) 就会得到相关系数，结果转化为如 下形式： 铲蒜vw-u v - ( 1 - 3 ) c ，2 。2 2 一 ( 卜j ) v 厶一_ ；l ，v 一川弩 式( 1 3 ) 和( 1 - 2 ) 在p a r s e v a l s t h e o r e m1 _ k 是- - n n 。如果对扛f 和 y ) 进行 合适的规范化处理，则作为相似性测量参数的相关性因子c ，的值将在 ，i ，1 】 的范围内，如果为1 则说明两个时间序列完全匹配。当有干扰信号的情况下， 相关因子的值一般小于1 ，而且序列值每，) 的峰值的位置就是扫。 中与扛。 匹配 的可能位置。 3 动态时间扭曲法d t w ( d y r m m i e t i m e w a r p i n g ) 由于时间轴的微小变形将会引起欧氏距离很大的变化，因此对于时间轴有 轻微变形的时间序列相似性的测量，欧氏距离将不再适用，如图l _ 2 所示，虽 然两个时间序列的形状相似，但是它们在时间轴上并不是完全对齐的，因此a 图中用欧氏距离计算相似性结果将会是距离很大，可能会导致产生不相似的结 果。若测量时，时间轴可以根据具体情况进行移动，在两个序列之间寻找一条 对齐路径，使得两个序列之间的欧氏距离最小，从而更直观( 更类似于人类思 考方式) 地测量时间序列的相似性，会更有效的找到两个时间序列的相似形状。 在实际应用中，例如语音识别系统中，当人们的发音频率发生改变时如何识别 就是一个这样的问题。对于这种情况人们提出了一种新的相似性测量方法即动 态时间扭曲法( d t w ) 【49 1 ，该方法允许在时间轴上有弹性的移动以便能够在两 个时间序列的不同的时间阶段发现相似的波形，这种方法已经成功的应用于语 音处理技7 r 1 5 0 , s 。d t w 是由b e r n d t 和c l i 硒r d 5 2 】引入到时间序列数据挖掘技 术的。但是文中提到该算法的计算复杂度很大，当处理很大的数据库时将会受 8 第一章绪论 到限制。但是这一方法仍然被广泛的应用于各个领域如生物信息【5 孙，化学工 程【5 4 】以及医药研究 5 5 , 5 6 】等。下面简述经典的d t w 算法。 憋螳+ 01 0皿 3 d4 amo” 图1 - 2a 图为欧氏测量方法b 图为d t w 测量方法 假设有两个时间序列q 和c ，它们的长度分别是，2 和m ，分别表示如下 o = q 】，q 2 ，一，q f ，q 。 ( 1 4 ) c = q ，c 2 ，c ，| c 。 ( 1 - 5 ) 为了用d t w 调整两个时间序列，构建一个n m 阶的矩阵，其中的第( 奶 个元素就是两个时间序列的点q ，和c ，之间的距离d ( q ，c 。) ( 其中一种典型的情 况是欧氏距离即d ( q ，c ，) = ( g ；一c y ) 2 ) ，如图1 - 3 所示。一个扭曲路径矿就是 一个上述矩阵元素的连续集，这个路径定义了时间序列q 和c 之f m 的一个映 射，的第k 个元素被定义为w 。= ( f ，) 。，因此可以得到一个路径集为： = w 1 ，w 2 ，一，w ，w f其中m a x ( m ，盯) k m + 一1 ( 1 - 6 ) 扭曲路径要求满足如下条件限制。 ( 1 ) 边界条件：w 12 ( 1 ，1 ) ，w r 。( 研， ) ，简单的说即要求扭曲路径必须 从矩阵的起始位置处开始和结束位置处结束。 ( 2 ) 连续性：给定w = ( 口，b ) ，w n = ( 日，b ) ，则要求a 一口1 和b b 1 ， 这要求扭曲路径每一步的设定都是连续的。 ( 3 ) 单调性：给定w = ( 口，6 ) ，w h = ( 口7 ，b ) ，要求口一a o 和b b 0 ， 即要求路径必须是在时间轴上的单调增长。 很显然满足上述条件的路径有很多，但是这里要求路径满足一个最小的扭 曲代价( w a r p i n gc o s t ) ： 脚( q ，c ) - m i n 幽1 乙。k i ) ( 1 - 7 ) 第一章绪论 基于动态最优的原则，在所有的路径中，发现欧几里德距离最小路径的方 法是用如下定义的一个渐增的距离公式r ( f ，j ) 。 ，( f ) = d ( q ，c ，) + m i n r ( i - 1 ，j - 1 ) ，r ( f 1 ) ，r ( i ，- 1 ) )( 1 8 ) 欧氏距离可以看作是d t w 的一个特例，当n = m 时，限制w 。= ( f ，u ，) 。， 其i = j = k 。 文献 5 7 1 给出了将d t w 和欧氏距离应用于时间序列聚类和分类的比较。 一 i w - - ， 一 f l v l i l 图1 - 3 扭曲路径的例子 f 三1 时间序列的重新描述 无论针对于上文提到的哪种测量方法，当时间序列的数据量很大时都会遭 遇到计算效率的问题，虽然相关性有一定的解决办法，但是它也是通过将时间 序列进行傅立叶变换之后再处理，因此也是一种时间序列的重新描述。为了提 高相似计算的效率同时又不会丢失原有的信息，人们提出了几种时间序列的描 述方法，简述如下。 1 频域表示法 由于时间序列的信号往往是由各种不同频率的信号叠加而成的，将基于频 域的技术用于时间序列的分析将是有效的，即将时域内的数据转换到频域内进 行分析。为了分析时间序列的相似性，将保持数据间欧几里德距离不变的正交 变换应用于时间序列的数据变换是必要的。通常，使用独立于数据的变换，其 变换矩阵是预先确定的，与输入数据无关。其中两个常见的独立于数据的变换 是离散傅立叶变换( d f t ) 和小波变换( d w t ) 。由于在时域中两个时间序列的距 离与频域中欧氏距离类似，因此上述两个变换可以用于测量相似性的计算。同 时由于一般情况下频域中前几个频率系数就能够捕捉到原时域数据的大部分 1 0 第一章绪论 信息，因此仅保持前几个系数就能够计算出实际距离的下界。 ( 1 ) 离散傅立叶变换( d f t ) 对于时域中的时间序列x = 扛。 ，f _ o ，1 ，月1 ，它的d f t 变换过程为 砟2 忑1 - n - 1 x , e x p ( 一j 2 z ：f i n ) ，f = 0 ，1 ，弦l ( 1 - 9 ) 其中辱为变换后频域中的序列。- ，是虚数单元= 仃。可以通过下式的 反变换公式将厨还原为x ： x i 2 j i nz n - i o x f e x p ( j 2 硐 )7 2 0 ，1 ，h 。1 ( 1 - 1 0 ) 厨中除局外都是复数。定义时间序列x 的能量e 0 ) 为每一点的平方和， 即 e ( z ) ；2s ：蚶 ( 1 - 1 1 ) 基于p a r s e v a l 的定理 5 8 】，d f t 保持了这个能量不变，即 n 。- i 州= = 盼l 2 ( 1 - 1 2 ) 因为d f t 是一个线性变换【5 叭，则p a r s e v a l 的定理隐含说明d f t 也保持了 两个时间序列x 和y 的欧氏距离不变的性能，即 d ( x ，y ) = d ( x ，y ) x 和y 分别是x 和y 的傅立叶变换结果。 当进行相似性搜索时，可以用最前面的女 2 3 个口i ) 个傅立叶系数进行 欧氏距离计算。 经过傅立叶变换后用其有限的几个系数来描述时域中的时间序列，其优点 是大大提高了计算效率。但是也存在一定的缺点，其一是不直观，其二是将行 维的时间序列映射到k 维空间中时要求k 维空间能够存储时间序列的所有信 息，而且该方法并不是对所有领域的时间序列都适用。 ( 2 ) 小波变换 傅立叶变换对于频率组成不随时间变化的时间序列处理起来效果很好，但 是当时间序列的频率组成随时间变化时，d f t 将丢失局部的时间信息，而采 用小波变换