（企业管理专业论文）时间序列的相似性挖掘及其在股票时间序列中的应用.pdf

摘要 时间序列数据就是按时间先后顺序排列各个观测记录的数据集，广泛存在 于社会、经济、技术等领域中。它不仅仅是历史事件的记录，更重要的是蕴藏 其中的不显现的、有趣的模式。在时间序列数据库越来越大的今天，如何对这 些海量数据进行分析处理，挖掘其背后蕴藏的价值信息，对于人们正确认识事 物和科学决策提供依据具有重要的实际意义，对时间序列的数据挖掘的研究显 得愈发必要。 时问序列分析的一个重要研究方向是采用数据挖掘的方法来揭示数据内部 规律。相对于数据挖掘较成熟的部分而言( 如关系数据库中关联规则和分类规则 的挖掘等) ，时间序列数据挖掘的研究还属于数据挖掘研究领域中一个较新的分 支。 目前对于时间序列数据挖掘的研究主要集中在相似性搜索和模式挖掘上。 相似性搜索是时间序列数据挖掘的研究基础，因为无论是分类、聚类还是关联 规则挖掘，都需要解决时间序列的相似度问题，相似性搜索是时间序列数据挖 掘的研究基础。在相似性搜索研究中存在的主要问题是时间序列数据量过大， 一个有效的解决办法是对时间序列进行重新描述，减小数据量，人们已经提出 了几种时间序列的描述方法。本文第三章在前入的基础之上将界标模型与分段 线性化结合，提出了一种基于关键点的时间序列分段线性化表示方法，该方法 从原始序列中提取关键点( 符合一定条件的界标) ，以关键点来作为分段的界线， 以最大似然函数和最小二乘法来拟合各分段线性拟合函数。该方法结合了两种 序列表示方法的特点，同时考虑了时间序列数据内在的整体特征，而且保留各 分段在时间序列中的位置信息。在分段线性化表示的基础上文章又提出了种 相似性计算方法，该方法对于时间序列的多种变形都不敏感。 股票市场的技术分析一直是一个热门的研究课题，人们提出了各种不同地 方法来预测股市的走势。技术分析中一个经典组成部分是形态分析。不同的形 态有着不同的意义，形态的背后常常蕴含着一定的规律，往往预示着股票价格 的未来走势，如头肩项是一个长期趋势的转向形态，通常出现在牛市的尽头， 股价开始出现滞涨，形态分析目的是预测市场价格变化的未来趋势、为股票投 资者决策提供依据。文章最后将在相似性挖掘研究的基础上讨论一个基于数据 挖掘技术进行证券市场的技术分析的方法。该方法通过应用时间序列的相似性 搜索来寻找股市的走势模式，从而进行股市指数等有关变量的预测。 本文的创新点主要表现在：在前人研究的基础之上，将界标模型和分段线 性化进行了结合，以关键点( 满足条件的界标) 作为分段依据，以最大似然函 数和最小二乘法来拟合各分段线性拟合函数；优点在于符合人体生理实验结果， 考虑了时间序列数据内在的整体特征，而且保留各分段在时间序列中的位置信 息、能够滤去实际时间序列中的噪声。文章另一个创新点是将时间序列相似性 挖掘技术运用于股票时间序列的分析之中。 关键词：相似性挖掘，分段线性化，界标模型，股票时间序列，形态分析 a b s t r a c t t i m es e r i e sd a t ai st h ed a t as e tt h a tm a n g e se v e r yo n ea c c o r d i n gt ot h et i m e ， a n di tu s e ss o c i a l ，e c o n o m i ca n dt e c h n o l o g i cf i e l d sw i d e l y i ti sn o to n l yt h eh i s t o r y r e c o r d ，b u ta l s ot h es u b m e r g e da n di n t e r e s t i n gm o d ec o n t a i n e d s i n c et i m es e r i e s d a t a b a s ei sb i g g e ra n db i g g e rt o d a y , i th a v ei m p o r t a n ts i g n i f i c a n c et oh o wt oa n a l y z e t h eh u g ed a t a , f o rp e o p l et ou n d e r s t a n da n dm a k er i g h td e c i s i o n i t s s t r o n g l y n e c e s s a r yt os t u d yo nd a t am i n i n go f t i m es e r i e s o n eo ft h ei m p o r t a n tr e s e a r c hd i r e c t i o n so ft i m es e r i e si st oo p e no u tt h e i n t e r n a ll a w so fd a t ab yu s i n gd a t am i n i n g o p p o s i t et om a t u r ep a r to fd a t am i n i n g ( s u c ha sm i n i n go fd a t a b a s ea s s o c i a t i o nr u l e sa n dc l a s s i f yr u l e s ) ，m i n i n go ft i m e s e r i e ss t i l lf a l l si n t oan e wb r a n c h r e c e n t l yt h es t u d yo nd a t am i n i n go ft i m es e r i e sm a i n l yc o n c e n t r a t e so n b o t l l t h es i m i l a r i t ys e a r c ha n dt h ep a t t e r nm i n i n gf r o mal i m es e r i e s s i m i l a r i t ys e a r c hi s j u s tt h er e s e a r c hb a s eo fd a t am i n i n go nt i m es e r i e s ，s i n c ea s s o c i a t i o n ，c l a s s i f ya n d c l u s t e r i n ga l ln e e ds o l v et h es i m i l i t u d ed e g r e ep r o b l e mo ft i m es e r i e s n l em a i n p r o b l e mo ft h er e s e a r c hi ns i m i l a r i t ys e a r c hi st h a tt h et i m es e r i e sd a t ai st o oh u g e o n eo ft h ee f f e c t i v es o l u t i o n si sd e s c r i b i n gt h ed a t ao n c ea g a i ns oa st or e d u c et h e d a t a sn u m b e r a n ds o m eo ft h ed e s c r i p t i o nm e t h o d sh a v eb e e np u to u t t h et 1 1 i r d c h a p t e ro fp a p e rc o m b i n e st h el a n d m a r k m o d e la n dp l r ( p i e c e - w i s el i n e a r r e p r e s e n t a t i o no ft i m es e r i e s ) ，a n db r i n gf o r w a r dai n d i c a t i v em e t h o do ft i m es e r i e s p i e c e w i s el i n e r , b a s eo nk e yp o i n t s ( 1 a n d m a r ka c c o r d i n g w i t hs o m es t a t e d c o n d i t i o n ) n l em e t h o dd i s t i l l st h ek e yp o i n t sf r o mo r i g i n a ls e r i e s a n df i t se a c h s u b s e c t i o nl i n e rf i t t i n gf u n c t i o nb yu s i n gm a x i m u ml i k e l i h o o df u n c t i o na n dt h e m e t h o do fl e a s ts q u a r e s 1 1 1 em e t h o dc o m b i n e st h ec h a r a c t e r i s t i c so ft w os e r i e s i n d i c a t i v em e t h o d s n l ep a p e rp u t so u ta n o t h e rc o m p u t a t i o n a lm e t h o do ns i m i l a r i t y , w h i c hi sn o ts e n s i t i v eo nm a n yk i n d so f t r a n s f i g u r a t i o no f t i m es e r i e s t e c h n o l o g i ca n a l y s i si sap o pr e s e a r c hs u b j e c ta l lt h ew h i l e , a n dp e o p l ep u to u t a l lk i n d so fm e t h o d st of o r e c a s tt h et r e n do fs t o c km a r k e t ac l a s s i cc o m p o n e n ti n i i i t h et e c h n o l o g i ca n a l y s i si st h es p e c i a t i o na n a l y s i s d i f f e r e n ts p e c i a t i o nh a sd i f f e r e n t s i g n i f i c a n c ea n di m p l i e ss o m el a w st h a tc o u l df o r e t e l lt h ef u t u r et r e n do f s t o c kp r i c e f i n a l l y , t h ep a p e rd i s c u s s e sa m e t h o do ft e c h n o l o g i ca n a l y s i so ns t o c km a r k e tb a s e o nd a t am i n i n gt e c h n o l o g y n l em e t h o di sa p p l i e dt of i n et h et r e n dm o d eo fs t o c k m a r k e ta n df o r e c a s ts o m ev a r i a b l e ss u c ha ss t o c ki n d e xb ys i m i l a r i t ys e a r c ho ft i m e s e r i e s n l ei n n o v a t i o no fp a p e rm a i n l ym a n i f e s tt h a tc o m b i n e st h el a n d m a r km o d e l a n ds u b s e c t i o nl i n e rm o d e l ，p u tk e yp o i n t s ( 1 a n d m a r kt h a ta c c o r ds o m ec o n d i t i o n s ) a sw a r r a n t y , f i te a c hs u b s e c t i o nl i n e rf i t t i n gf u n c t i o nb yu s i n gm a x i m u ml i k e l i h o o d f i m c t i o na n dt h em e t h o do fl e a s ts q u a r e s n ee x c e l l e n c eo ft h em e t h o di st h a ti t f u l f i l st h ee x p e r i m e n t a t i o no u t p u to fp h y s i o l o g y , c o n s i d e r st h ei n t e r n a lh o l i s t i c c h a r a c t e r i s t i co ft i m es e r i e s ，a l s or e s e r v e st h e d i r e c t i o ni n f o r m a t i o no fe a c h s u b s e c t i o ni nt i m es e r i e s ，a n df i l t r a t e st h en o i s eo fa c t u a lt i m es e r i e s a n o t h e r i n n o v a t i o no ft h ep a p e ri sb r i n g i n gt h ec o m p a r a b i l i t ym i n i n gt e c h n o l o g yo ft i m e s e r i e st ot h ea n a l y s i so f t i m es e r i e so ns t o c km a r k e t k e yw o r d s ：s i m i l a r i t ys e a r c h ，p l e ，t i m es e r i e so ns t o c km a r k e t , s p c c i a t i o n a n a l y s i s i v 东北财经大学研究生学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文 置恻龅概雠堆嫡疆鲥啦雌舡哼懒汁柏摩罔，是本人在导师指 导下，在东北财经大学攻读硕士学位期间独立进行研究所取得的 成果。据本人所知，论文中除已注明部分外不包含他人已发表或 撰写过的研究成果，对本文的研究工作做出重要贡献的个人和集 体均已注明。本声明的法律结果将完全由本人承担。 作者签名：垡哗年日期：锄7 年f 0 月面目 东北财经大学研究生学位论文使用授权书 醇两度孙懒辟摊艮筻在僻b 牺9 谤忡群瘟幂系本人在东 北财经大学攻读硕士学位期间在导师指导下完成的硕士学位论 文。本论文的研究成果归东北财经大学所有，本论文的研究内容 不得以其他单位的名义发表。本人完全了解东北财经大学关于保 存、使用学位论文的规定，同意学校保留并向有关部门送交论文 的复印件和电子版本，允许论文被查阅和借阅。本人授权东北财 经大学，可以采用影印、缩印或其他复制手段保存论文，可以公 布论文的全部或部分内容。 作者签名： 导师签名： 暂继牟 知f 盘王， 日期：蛳7 年，o 月面目 日期：砷7 年j o 月吾。日 第一章绪论 第一章绪论 本章首先从数据挖掘的角度出发简要回顾了时间序列的发展，然后重点介 绍时间序列数据挖掘的研究现状。同时介绍了有关时间序列数据挖掘的各个研 究方向，并对此做出评述，指出今后的研究方向。 1 1 选题的研究背景与研究意义 数据挖掘是一门交叉学科，它汇聚了数据库、人工智能、统计学、可视化、 并行计算等不同学科和领域，近年来受到各界广泛关注。促进数据挖掘诞生、 发展、应用有众多原因，f r i e d m a n 1 9 9 7 便列举了四个主要理由：超大规模数据 库的出现，例如商业数据仓库和计算机自动收集的数据记录；先进的计算机技 术，例如更快和更大的计算能力和并行体系结构；经营管理的实际需要；对这 些数据应用精深的统计方法计算的能力。经营管理的实际需要是指：企业所面 l 临的市场竞争压力日趋严重，企业经营管理者特别是决策者希望能够从企业积 累的大量历史数据中找到应对日趋严重的竞争压力的良方，希望能够从这些数 据中找到经营管理中所存在问题的根本原因，能够快速从大量数据中挖掘出对 经营管理有用的信息，以应对瞬息万变的市场压力。可以说数据挖掘技术是一 个对管理决策者提供决策支持的有力工具。 所谓时间序列数据就是按时间先后顺序排列各个观测记录的数据集，广泛 存在于社会、科学、经济、技术等领域中，如金融证券市场中每天的股票价格 变化等；然而，时间序列数据不仅仅是历史事件的记录，更重要的是蕴藏在这 些数据中的不显现的、有趣的模式。随着时间推移和技术的发展，时间序列数 据库也越来越大，如何对这些海量数据进行分析处理，挖掘其背后蕴藏的价值 信息，对于我们揭示事物发展规律变化的内部规律，发现不同事物之间的相互 关系，为人们正确认识事物和科学决策提供依据具有重要的实际意义，对时间 序列的数据挖掘的研究显得愈发必要。而股票时间序列就是一个典型的时间序 列，对它的数据挖掘研究将大有可为。例如，在股票价格时间序列数据库中寻 找出具有特殊波形的数据，从中抽取出该特殊波形，如头肩顶、头肩底等，这 时间序列的相似性挖掘及其在股票时间序列中的应用 些波形往往预示着股票价格的未来走势，因此将各种波形进行聚类后将有助于 股票分析，为股票投资者的决策提供依据。 采用数据挖掘的方法揭示数据内部规律己成为时间序列分析的一个重要研 究方向。经典的时间序列分析方法如移动平均法( m o v i n g a v e r a g e ) 、指数平滑法 ( e x p o n e n t i a ls m o o t h i n g ) 以及b o xj e n k i n s 的a r m a a r i m a 方法等，其中大 多数是基于数学模型的。在当前海量时间序列数据库环境下，索引结构的性能 随着维数的增大迅速降低，在维数较高时，甚至不如顺序扫描，以数学模型为 基础的时间序列分析方法显得十分吃力。在时间序列分析中引入数据挖掘技术 是大势所趋。同时，相对于数据挖掘较成熟的部分而言( 如关系数据库中关联规 则和分类规则的挖掘等) ，针对于时间序列数据挖掘的研究是数据挖掘研究领域 中的较新的一个分支。在时间序列的数据挖掘研究中，又以相似性搜索挖掘为 一个重要的研究内容，这主要是受到实际需要的驱使而产生的。因为无论是分 类、聚类还是关联规则挖掘，都需要解决时间序列的相似度问题，所以相似性 搜索是时间序列数据挖掘的研究基础。 相似性的研究是时间序列数据挖掘的研究中的一个最基本的而且比较困难 的问题。主要困难在于相似性度量的定义和算法的时间复杂度。而相似性度量 的定义和算法的时间复杂度又都依赖于时间序列的表示方法。因此，研究一种 高效的时间序列相似性搜索方法很有实际意义。 1 2 数据挖掘概述 数据挖掘( d m ，d a t am i n i n g ) 是数据库技术和机器学习等人工智能技术 相结合的产物，是一门新兴的数据智能分析技术1 。2 0 世纪8 0 年代末，随着数 据库、互联网技术的迅速发展以及管理信息系统( m i s ) 和网络数据中心( d c ) 的推广应用，数据的存取、查询、描述统计等技术已日臻完善，但高层次的决 策分析、知识发现等实用技术还很不成熟，导致了“信息爆炸”与“知识贫乏” 并存的现象。到了9 0 年代，人们提出在数据库基础上建立数据仓库，应用机器 学习和统计分析相结合的方法处理数据，二者的结合促成了数据挖掘技术的诞 生。数据挖掘的核心模块技术经历了数十年的发展，其中包括数理统计、人工 智能、机器学习。今天，这些成熟的技术，加上高性能的关系数据库引擎以及 2 第一章绪论 广泛的数据集成，让数据挖掘技术在当前的数据仓库环境中进入了实用的阶段。 1 2 1 数据挖掘的定义 所谓数据挖掘，在技术上的定义就是从大量的、不完全的、有噪声的、模 糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又 是潜在有用的信息和知识的过程；在商业角度的定义就是一种新的商业信息处 理技术，其主要特点是对商业数据库中的大量业务数据进行抽取、转换、分析 和其他模型化处理，从中提取辅助商业决策的关键性数据。简单地说，就是从 大量数据中提取或挖掘知识。挖掘算法的好坏直接影响到知识发现的质量和效 率，因此目前大多数研究都集中于数据挖掘算法及其应用上。 1 2 2 数据挖掘的方法及应用 根据i b m 的划分法，按照挖掘的数据模式的不同，可以将数据挖掘的分析 方法划分为以下四类： ( 1 ) 关联分析 关联分析是寻找数据库中值的相关性，即寻找在同一个事件中出现的不同 数据项的相关性，比如一次购买活动中所买不同商品的相关性。关联规则可以 记为a ；b ，a 成为前提，b 成为后续，反映a 中的项目出现时，b 中的项目 也跟着出现的规律。关联分析属于数据挖掘研究领域一个比较成熟的分支，人 们提出了多种关联规则的挖掘算法，如a p r i o r i 、s t e m 、a i s 、d h p 等算法。 ( 2 ) 序列分析 与关联分析相似，序列分析的目的也是为了挖掘数据项之间的联系，但序 列分析的侧重点在于分析数据项之间在发生时间上的前后关系。序列规则也可 记为a 等b ，表示a 发生以后将会发生b 。序列模式分析描述问题的过程是： 在给定的事件序列数据库中，每个序列都是按照事件发生时间排列的一组交易 集，将挖掘序列函数作用在这个事件序列数据库上，然后返回该数据库中出现 的高频序列。 序列规则的研究基本与关联规则同步，各种算法也基本上是对各种关联规 则挖掘算法的修改。 时间序列的相似性挖掘及其在股票时间序列中的应用 ( 3 ) 分类分析 分类要解决的问题是为一个事件或对象归类。在使用上，既可以用此模型 分析已有的数据，也可以用它来预测未来的数据。例如，用分类来预测哪些客 户最可能对直接邮件推销做出回应。 分类分析是通过分析己知分类信息的历史数据总结出预测模型。这里用于 建立模型的数据称为训练集，通常是已经掌握的历史数据。训练集也可以是通 过实际的实验得到的数据。 ( 4 ) 聚类分析 聚类是把整个数据库分成不同的群组( c l u s t e r ) 。它的目的是要使群与群之 间的差别很明显，而同一个群之间的数据则尽量相似。与分类不同，在开始聚 类之前我们并不知道要把数据分成几组，也不知道怎么分( 依照哪几个变量) 。 因此在聚类之后要有一个对业务很熟悉的人来解决这样分群的意义。在很多情 况下，一次聚集得到的分群对于特定的业务来说可能并不好，这时需要删除或 增加变量以影响分群的方式，经过几次反复之后才能最终得到一个理想的结果。 神经元网络和k 一均值是比较常用的聚类方法。 目前，数据挖掘( d a t am i n i n g ) 在很多领域都是一个很时髦的词，尤其是在 如银行、电信、保险、交通、零售( 如超级市场) 等商业领域。数据挖掘所能 解决的典型商业问题包括：数据库营销( d a t a b a s em a r k e t i n g ) 、客户群体划分 ( c u s t o m e rs e g m e n t a t i o n & c l a s s i f i c a t i o n ) 、背景分析( p r o f i l ea n a l y s i s ) 、交叉 销售( c r o s s s e l l i n g ) 等市场分析行为，以及客户流失性分析( c h u r n a n a l y s i s ) 、 客户信用记分( c r e d i ts c o r i n g ) 、欺诈发现( f r a u dd e t e c t i o n ) 等。 1 2 3 数据挖掘与传统数据分析方法的区别 数据挖掘与传统的数据分析( 如查询、报表、联机应用分析) 的区别在于二 者探索数据关系时所使用的方法不同。传统的数据分析是对假设的验证，即用 户首先对特定的数据关系做出假设，然后使用分析工具去确认或否定假设。与 此相反的是，数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识，所 得到的信息应具有先未知，有效和可实用等特征。 先前未知的信息是指该信息是预先未曾预料到的，即数据挖掘是要发现那 4 第一章绪论 些不能靠直觉发现的信息或知识，甚至是违背直觉的信息或知识，挖掘出的信 息越是出乎意料，就可能越有价值。商业应用中最典型的例子就是通过数据挖 掘发现了小孩尿布和啤酒之间有着惊人的联系。 1 3 时间序列数据挖掘的研究进展及评述 时间序列的数据挖掘技术自上世纪9 0 年代以来有了快速发展。由最初相似 性的分析到目前的人工智能的多学科交叉研究，时间序列的数据挖掘技术已经 有了多个研究方向，主要包括相似性的研究和模式挖掘的研究等，分述如下。 ( 1 ) 相似性搜索 时间序列数据的相似性搜索问题最早由m m 公司的a g r a w a l 等人于1 9 9 3 年提出，该问题描述为“给定某个时间序列，要求从一个大型时间序列数据库 中找出与之最相似的序列”2 。这与找出符合查询的精确数据的通常的数据库查 询是不同的。由于实际需要的驱动，使得在时间序列的数据挖掘研究中，相似 性搜索是一个重要的研究内容。在相似性搜索的基础上又发展出了时间序列的 聚类、分类、以及关联规则的抽取等等数据挖掘技术。 相似性搜索首先要解决的问题是相似性的定义。相似性就是指测定两个给 定的时间序列是否为具有相似的行为曲线。但困难地方是时间序列往往是来自 于实际，这使得相似性的测量要求并不是完全严密的，而且时间序列数据库来 自于各个领域，测量标准也不尽相同。而相似性度量模型则是依据所定义的相 似性进行数学抽象而成。在相似性定义方面，有比较简单粗糙的，如a g r a w a l 等人提出的一种相似性，它是根据直观意义上时间序列数据的上升、下降的趋 势定义的，通过这种相似性可以比较租糙地从数据库中发现具有相似形状的时 间序列。后来a g r a w a l 等又提出一种e 相似性度量模型3 ，这种相似性可以容 忍时间序列中噪声的存在而引起的局部不匹配，并对时间轴上的偏移以及幅值 的缩放不敏感。有的相似性定义则比较复杂，例如g a u t a md a s 等提出的种 称为f 相似的相似性模型：设f 是一个函数集，对于两个待比较的时间序列 而言，如果它们满足一定长度要求的子序列，且存在f 中的个函数f 使得其 中的某个子序列可以近似的映射到另一个子序列，则称两个时间序列具有f 相 似。这种相似性对异常点( o u t l i e r s ) 、基线以及比例因子不敏感。 相似性的测量方法包括欧几里德距离测量方法、c s l i 等提出的相关性测 5 时间序列的相似性挖掘及其在股票时间序列中的应用 量和动态时间扭曲法d t w 等。其中欧几里德距离测量方法是一个基本的、简 单的测量方法，多数研究也都是基于欧几里德距离的。为了提高相似计算的效 率同时又不会丢失原有的信息，人们又提出对时间序歹迸行重新描述，经过多 年的努力，先后出现了许多面向相似性搜索的时间序列近似表示方法。 本文将在文章的第二部分对时间序列的相似性搜索挖掘做进一步的研究。 ( 2 ) 模式挖掘 模式挖掘主要包括时态模式挖掘和趋势预测。时态模式挖掘的一个主要技 术是关联规则的挖掘4 。 时态模式挖掘 在时态模式挖掘方面，c h e nx i a o d o n g 等人5 提出了一种具有比较好的包容 性的时态模式挖掘的定义，其定义如下： 定义1 1 ( 时态模式) ：一个时态模式是一个二元组 。其中 p a r 是一个一般意义上的模式，可以是趋势、偏差、分类规则和关联规则等， t i r n e e x p 就是一个时间表达式，它表示p a t t 在巾( t i m e e x p ) q b 的每个时间区间内 成立。 r i c h a r dj p o v i n e l l i 对时间序列中的事件( e v e n t ) 的出现加以模式发现和预 测。他对相空间( p h a s es p a c e s ) 采用时间延迟法( t i m e d e l a y e de m b e d d i n g ) 进行重新 构建，然后在相空间上定义了一种事件标志函数，寻找那些对于预测未来事件 有用的点，进行聚类形成时态模式，用这些时态模式进行事件的预测。 g a u t a md a s 6 则通过在时间序列中挖掘局部模式( 1 0 c a lp a t t e r n ) ，从中抽取关 联规则。他首先用一个时间窗口在时间序列上滑动形成子序列，然后通过相似 性测量对子序列聚类，然后采用规则生成方法发现序列中模式的行为和时间的 关系。 趋势预测 趋势预测采用的技术主要是分类规则的挖掘技术，即l a s t m 7 提出的首先对 时间序列进行预处理，然后从中抽取关键的预测属性( p r e d i c t h l ga t t r i b u t e s ) ，这 些属性对时间序列的发展趋势影响较大，将其组成属性集，这些预测属性表征 了时间序列的某种特性，这种特性与时间没有关系，因此可以采用普通的静态 的数据挖掘工具对时间序列进行行为趋势的分类预测。具体可参考参考文献9 。 6 第一章绪论 本章注释： 1 李菁菁、邵培基、黄亦潇数据挖掘在中国的现状和发展研究【j 】管理工程学报，2 0 0 4 1 8 ( 3 ) ：1 0 1 5 。r a g r a w a l cf a l o u t s o s as w a m i e f f i c i e n ts i m i l a r i t ys e a r c hi ns e q u e n c e d a t a b a s e c i n ：d l o m e te d p r o c e e d i n g so f t h ei n t e r n a t i o n a lc o n f e r e n c eo f f o a n d a t i o n so f d a t ao r g a n i z a t i o na n da l g o r i t h m s ( ：o d o ) c ，1 9 9 3 ：6 9 - 8 4 r a g r a w a l ，k i l i n ，h s s a w i m e y , a n dk s h i m f a s ts i m i l a r i t ys e a r c hi nt h ep r e s e n c eo f n o i s e ，s e a l i n g ，a n dt r a n s l a t i o ni nt i m e s e r i e sd a t a b a s e ，i np r o c 1 9 9 5i n t c o n f = v e f yt a r g e d a t a b a s e s ( v l d b 9 5 ) ，z u r i c h ，s w i t z e r l a n d 1 9 9 5 ：4 9 0 - 5 0 1 4d a s ，g l i n ，k m a n n i t a , h r e n g a n a t h a n ，g & s m y t h ，pr u l e d i s c o v e r yf r o mt i m es e r i e s i n p r o c e e d i n g so f t h e4 t hi n t lc o n f e r e n c e0 1 1k n o w l e d g ed i s c o v e r ya n d d a t am i i l 抽昏n e wy o r l q n y , a u g2 7 - 3 1 1 9 9 8 ：1 6 2 2 3 z h q i n ，z m a n ，a n e w a l g o r i t h m f o r n e u r a l n e t w o r k a r c h i t e c t u r es t u d y p r o c e e d i n g s o f t h e 3 r dw o r l dc o n g r e s so nl m e l l i g e mc o n t r o la n da u t o m a t i o n j u n e ，2 0 0 0h e f e i ，e r c h i n a 7 9 5 - 7 9 9 ? 。d a s , g l i n , k m a n n i l a , h r e n g a n a t h a n q s m y t h ，p r u l ed i s c o v e r yf r o mt i m es e r i e s i n p r o c e e d i n g so f t h e4 t hi n t lc o n f e r e n c e0 1 1k n o w l e d g ed i s c o v e r ya n dd a t am i n i n g n e wy o r l n y a u g2 7 - 3 1 1 9 9 8 ：1 6 2 2 7 l a s tm k l e i n ，y k n o w l e d g ed i s c o v e r yi nt i m es e r i e sd a t a b a s e s i e e et r a m o ns y s t e m ， m a n , a n d c y b e r n e t i c s - p a r t b ，2 0 0 1 ，3 1 ( i ) ：1 6 0 - 1 6 9 7 时间序列的相似性挖掘及其在股票时间序列中的应用 第二章时间序列相似性挖掘研究现状及评述 如前所述，采用数据挖掘方法来揭示数据内部规律已经是时间序列分析的 一个重要研究方向。这当中又由于实际的需要，使得相似性搜索挖掘成为时间 序列数据挖掘研究中一个非常重要的研究内容。具体来讲。相似性搜索挖掘部 分的研究包括相似性的度量和面向相似性搜索的时间序列表示方法等方面工 作。本章将对时序数据相似性挖掘研究现状进行介绍，并在此基础上进行评述。 2 1 时间序列的定义 时间序列是指按时间变化的序列值或事件，时间序列数据库是指由随时间 变化的序列值或事件组成的数据库。这些值或事件通常是在等时间间隔测得的。 以数学方式表达为如下： 定义2 1 ：一个时间序列数据库是指一系列记录 昌，n 为序列值的个数， 其中每个记录为m + l 维数据，即弓= q ，a 2 ，一 4 n ，t ，a ；为特性值，可以是连 续实数也可以是离散数据，而且可以是与时间有关联也可以没有。如果某特性 值与时间有关，则该特性值为动态特性，否则为静态特性，一般时间序列的研 究主要是针对动态特性。t 是一个时间间隔的标志，例如天、月、年等。 以股票每天的交易记录为例来说明上述定义，e = 6 0 0 0 0 0 ，浦发银行，2 4 8 ， 2 6 3 ，2 4 2 ，2 5 8 ，2 5 5 1 0 5 ，6 2 ，其中6 0 0 0 0 0 是股票代码，浦发银行是股票名 称，接下来的分别为当天的开盘价，最高价，最低价，收盘价，成交量以及第 6 2 个交易日。前两个特性显然与时间无关，为静态特性，而其他特性值是与时 间密切相关的，是动态特性。很显然，对于静态特性研究的意义不大。 定义2 2 ：对于定义2 1 中的特性值a ；可以定义为特性函数f ，其f 是时间 的函数，函数的系数可以从特性值a ；中得到，其函数表达为 f ；也) = a i r j ，其中，t x t j ( 2 - 1 ) 一般对于时间序列的数据挖掘的研究往往集中于某个重要的单个特性值， 如股票时间序列数据库中主要研究股票的每日收盘价，因为这是影响投资者决 策行为的主要因素。 8 第二章时间序列相似性挖掘研究现状及评述 2 2 基本的时间序列相似性测量方法 对象之间相似性的定义和度量处于一个非常基础的位置之上，它的研究对 很多方面都具有重要意义，如统计理论、数据挖掘等。相似性度量是时间序列 相似性挖掘中的一个关键技术，无论哪一种相似性搜索的方法或形式都依赖于 时间序列相似性的测量方法上。时间序列的特殊性和数据挖掘的特点使得相似 性测量有一些特殊性：要求相似性的测量不必是精确的匹配( 即完全相同) ，因 为相似性搜索是查询与给定的时间序列变化行为最接近的时间序列；要求相似 性的测量方法一定要效率高，因为时间序列的数据量一般非常大，甚至有数十 万上百万的数据量；同时要求该相似性算法可以适合于其他的计算( 如聚类、 规则提取等) ，因为相似性测量只是一个基础性的技术，相似性的测量不是目的， 而是要为其他的算法服务。 对于时间序列的相似性测量，不同的数据表达形式相似性测量的方法也不 尽相同。常用的测量方法主要有以下三种。 ( 1 ) 欧几里德距离测量方法 对于时间序列数据的相似性分析中，经常采用欧几里德距离作为相似计算 的工具，两个时间序列的欧氏距离定义为 定义2 3 假设 x j ) 是目标时间序列，( y 。) 是需要进行相似测量的数据库中 的一个时间序列，n 是 x ， 的长度，n 是 y ，) 的长度，假设n n 。则进行相似 性测量时只考虑 y ， 的长度为n 的子序列。时间序列 y 。) 的j ( d = n 一 + 1 ) 个 子序列记为 z ? ，则测量 x ， 和 y ， 的相似性的距离矩阵定义为 呼善( x , - k ，z ) 2 ( 2 - 2 ) 其中足，是比例因子。若在进行查询前原始时间序列中的长度为n 的子序列 已经产生，则查询时，每个时间序列需要计算n n + 1 次。 采用欧氏距离进行测量的优点是容易计算，易于理解，可以用于索引和聚 类等数据挖掘。它的缺点是对序列中的噪声很敏感，而且欧氏距离会随着序列 长度的增加而增加。而实际的时间序列数据往往会很长，含有较多的噪声，仅 仅通过简单的欧几里德距离测量方法不能正确做出两个时间序列是否相似的判 定，同时由于数据量很大，相似性的计算效率也很低l 欧氏距离也不允许有不 9 时间序列的相似性挖掘及其在股票时间序列中的应用 同的基线，如当两支股票分别在￥2 0 和￥8 0 进行波动时，尽管他们的波形很相 似，但是其欧氏距离会很大。 ( 2 ) 相关性测量 另一个相似性测量方法是在文献1 中考虑的相关性测量方法，这种方法不但 能够将相似性作为位置的函数而且不必对原始数据库的时间序列产生所有的长 度为n 的子序列。一个目标时间序列 t ) 和时间序列数据库中的序列 y 。 之间 的线性相关定义如下： c 。：1 兰! ! 乏! 兰 ( 2 3 ) c 。= 7 = = = 圭= = _ 1 = = = = 一 二。o ， 。：；：，_ ，； 其中滓l ，n + n 1 。这种相关性的计算对于 工。) 比较长的时间序列的 计算花费是很大的，在这种情况下，傅立叶变换的卷积定理提供了一个很好的 解决办法。首先在 _ ) 和( y ， 的末尾补充0 使得两个时间序列变为长度都为 ，= n + ”一1 的新序列 x ：) 和 y 1 ) ，然后对 x ：) 和 y ：) 进行离散傅立叶变换生成 置 和( f ，最后通过逐点相乘 z 和 r 就会得到相关系数，结果转化为如 下形式： - f 一1 f t - y - j - ，j ，j 铲面而 ( 2 4 ) 式( 2 3 ) 和( 2 - 4 ) 在p a r s e v a l s t h e o r e m l 上是一致的。如对 x 。 和 y ， 进行合 适的规范化处理，则作为相似性测量参数的相关性因子c 。的值将在【一l ，1 】的范 围内，如为l 则说明两个时间序列完全匹配。当存在干扰信号时，相关因子的 值一般小于1 ，而且序列值 c 。) 峰值的位置就是 x ，) 中与 y ， 匹配的可能位置。 ( 3 ) 动态时间弯曲法( d t w ，d y n a m i c t i m e w a r p i n g ) 欧氏距离由于时间轴的微小变形都会被引起很大的变化，因此不再适用于 时间轴有轻微变形的时间序列相似性的测量。而动态时间弯曲距离可有效消除 欧氏距离的缺陷，它允许序列在时间轴上的偏移，序列各点不要求一一对应， 并且能够计算不同长度序列之间的距离。图2 1 中a 和b 分别显示了欧氏距离 和动态时间弯曲距离计算时序列各点之间的对应关系。图中所示，虽然两个时 间序列的形状相似，但是它们在时间轴上并不是完全对齐的，因此a 图中用欧 氏距离计算相似性结果将会是距离很大，可能会导致产生不相似的结果。若测 l o 第二章时间序列相似性挖掘研究现状及评述 量时，时间轴可以根据具体情况进行移动，在两个序列之间寻找一条对齐路径， 使得两个序列之间的欧氏距离最小，从而更直观( 更类似于人类思考方式) 地测 量时间序列的相似性，会更有效的找到两个时间序列的相似形状。在实际应用 中，例如语音识别系统中，当人们的发音频率发生改