（计算机应用技术专业论文）基于人体运动捕捉数据的高维时间序列模式挖掘算法的研究.pdf

大连理工大学硕士学位论文 摘要 时间序列是包含一系列随时间变化的数据的序列，它反映了某种属性值随时间变化 的特征。在金融、经济、自然科学、信息工程等重要领域，每天都会产生大量的时间序 列，因此如何有效地处理这些数据并挖掘其背后隐含的规律和知识，成为人们日益关注 的问题，随着研究的深入，许多经典的问题得到了有效地解决。而近年来，随着技术的 发展，出现了许多复杂庞大的高维时间序列数据库，然而其带来的计算复杂度的激增， 使得大部分能够成功地应用于一维时间序列的挖掘技术，都无法应用在高维时间序列的 挖掘上。 针对该问题，本文首先对时间序列数据挖掘领域的研究进行了系统的文献总结，分 析了时间序列及高维时间序列的分类、特点和研究现状。之后，阐述了该领域研究的几 个主要问题，即相似性度量、快速检索、主旨模式挖掘，并针对每个问题，对主流方法 的特点、适用范围及优缺点进行了详细的分析与说明。 在此基础上，本文针对当前该领域的两个热点问题，即序列的快速检索和主旨模式 挖掘，以人体运动捕捉数据作为具体分析对象，进行了深入的研究，分别提出了有效的 解决方法，并通过相关实验验证了算法的有效性。 ( 1 ) 在序列的快速检索方面，通过充分挖掘人体运动的特征，本文提出了两个新的 模型：借助于运动中产生的能量对运动进行描述的能量模型和利用相关系数描述人体运 动中关节问协作状态的运动协调性模型。利用这两个模型，可以从人体运动中提取出能 够有效地体现出其运动特征的低维度索引序列。之后，利用支持向量机对该低维索引序 列进行粗分类，从而最大程度地避免了与查询序列不相似的序列参与到时间复杂度较高 的精确比较中。最后，在经过租分类的候选序列集合上，利用基于d t w 距离进行度量 和k e o g h 索引下界进行剪枝的线性检索算法精确地度量输入运动和候选动作之间的相 似性。 ( 2 ) 在主旨模式挖掘方面，针对现有算法易受噪声干扰的问题，本文提出了一种基 于最长公共子序列距离的主旨模式挖掘算法。但该度量方法具有复杂度较高的问题，因 此，在搜索过程中，该算法采用了基于子序列距离判别的策略进行了剪枝。之后，采用 了层次化聚类的方法将相邻重叠并高度相似的候选模式进行合并，仅保留下能够充分体 现序列各部分特征的序列。最后，对于提取出来的非等长候选模式，使用了最小描述长 度原则求得其相关权重，并据此选择出现频率最高、最能体现原时间序列特征的主旨模 式。 关键词：高维时闻序列；快速检索；主旨模式挖掘；支持向量机；弹性匹配 大连理工大学硕士学位论文 t h er e s e a r c ho f t h es e q u e n c em i n i n ga l g o r i t h m so nt h eh i g h - d i m e n s i o n t i m es e r i e sb a s e do nh u m a nm o t i o nc a p t u r ed a t a a b s t r a c t e v e r yt i m es e r i e sc a l lb ec o n s i d e r e da sat i m e - v a r y i n gs e q u e n c e w h i c hc 】汹i nm a n ya r e a s s u c ha sl r l n a n c e ，e c o n o m y ，n a t u r a ls c i e n c ea n di n f o r m a t i o ne n g i n e e r i n g r e s e a r c h e so nh o wt o p f o c e s sa n dm i n et h e s et i m es e r i e sh a v e b e e np a i dg r e a ta t t e n t i o n sa n dm a n yc l a s s i cp r o b l e m s h a v eb e e ns o l v e de f f i c i e n t l y i nr e c e n ty e a r s ，a sb o t ht h et e c h n o l o g i e sa n dt h er e q u i r e m e n t s d e v e l o p e dr a p i d l y ，m a n yl a r g e - s c a l ea n dc o m p l e xt i m es e r i e sd a m b 硒e sh a v eb e e ne s t a b l i s h e d u n f o r t u n a t e l y ，b e c a u s eo ft h eh i g h l yi n c r e a s i n gc o m p u t a t i o nc o m p l e x i t y ，m o s to ft h ed a t a m i i l i n gt e c h n o l o g i e s ，w h i c hc a l lb ea p p l i e do nt h eo n e d i m e n s i o nt i m es e r i e ss u c c e s s f u l l y ，a r e n o ta v m l a b l ew h e nu s e dt od e a lw i t hh i g h - d i m e n s i o nt i m es e r i e s a i m i n ga tt h i sp r o b l e m , w eh a v em a d eas y s t e m a t i c a ls u m m a r i z a t i o no nt h er e s e a r c h e so f d a t am i n i n go nt i m es e r i e sa n dac o m p r e h e n s i v ea n a l y s i so nt h ec h a r a c t e r i s t i c s ，v a r i e t i e sa n d c u r r e n tr e s e a r c hs i t u a t i o no f t h eh i g h - d i m e n s i o nt i m es e r i e s b a s e do nt h er e v i e wt h ee x i s t i n g t e c l m o l o 西e s ，w ef o c u so nt w op o p u l a rt o p i c s ：t h ef a s ts e q u e n c es e a r c h i n ga n dm o t i fm i n i n g o nh i g h - d i m e n s i o nt i m es e r i e s b yt a k i n gt h eh u m a nm o t i o nc a p t u r ed a t aa st h ea n a l y s i s o b j e c t , e f f e c t i v ea l g o r i t h mi sb m u g h tf o r w a r do nt h et w os u b j e c t sr e s p e c t i v e l ya n dt h e e x p e r i m e n t sv e r i f yt h ea v a i l a b i l i t ya n dh i g hp e r f o r m a n c e ( 1 ) d i f f e r e n tf r o mt h es p a t i a lp o s i t i o nb a s e dm o d e lu s e di nt r a d i t i o n a lr e c a i e v a lm e t h o d s ，a n o v e lm o d c lb a s e do nk i n e t i ce n e r g yi sp r o p o s e da n du s e dt od e s c r i b eh u m a nm o t i o n b a s e d o nt h em o d e l 。t h em o t i o nc o o r d i n a t i o ni si n t r o d u c e da n du s e d 协e x t r a c tt h el o w - d i m e n s i o n a l i n d e x i n gs e q u e n c e st h a t a r er e m a r k a b l ef e a t u r e so fo r i g i n a lm o t i o n s t h es u p p o r tv e c t o r m a c h i n ei sa p p l i e dt oc l a s s i f yt h em o t i o n f i n a l l y , t h es e q u e n t i a li n d e x i n ga l g o r i t h mb a s e do n t h ek e o g hl o w e rb o u n di se m p l o y e dt oi n e a 飘】豫t h es i m i l a r i t yo fq u e r ym o t i o na n dc a n d i d a t e m o t i o n se x a c t l y ( 2 ) a g a i n s tt h ep r o b l e mt h a te x i s t i n ga l g o r i t h m sa l ea p t t ob ei n t e r f e r e db yn o i s e ，am o t i f m i n i n ga l g o r i t h mb a s e do nt h el c s sd i s t a n c e i si n m x l u e e d n ea l g o r i t h mh a sp r u n e d e f f i c i e n t l yb yu s i n gt h eh e u r i s t i cs t r a t e g yb a s e do n t h ed i s t a n c eb e t w e e ns u b s e q u e n c e sd u r i n g t h es e a r c h t h e nt h em d lp r i n c i p l ei su s e dt oc a l c u l a t et h ew e i g h t so ft h eu n e q u a l - l e n g t h c a n d i d a t es e q u e n c e sb a s e do nw h i c ht h em o t i f p a t t e r n sa r es e l e c t e d k e yw o r d s ：h i g h - d i m e n s i o nt i m es e r i e s ；f a s ts e a r c h i n g ；m o t i fm i n i n g ；s u p p o r tv e c t o r m a c h i n e ；e l a s t i cm a t c h i n g i i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名： 盘老自在。日期：呈! 盟垒! 兰旦1 2 胃 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名：墨鱼垫 导师签名 珥年旦月卑日 大连理工大学硕士学位论文 1 绪论 1 1数据挖掘技术及其主要任务 随着数字内容的获取以及存储技术的不断发展，越来越多的数据被存储在数据库、 数据仓库、以及互联网上。在庞大的数据之后，往往隐藏着一些非常有价值的信息，面 对海量的数据，人们迫切地意识到需要新的技术和工具以支持从大量的数据中智能地、 自动地抽取出有价值的知识或信息，数据库知识发现( k n o w l e d g ed i o v c r yi nd a t a b a s e ， k d d ) 就是为解决上述问题而提出的智能数据分析( k t c h i g c n t d m a n 出s i s ，d a ) 技术。 数据挖掘的概念于1 9 8 9 年在美国底特律召开的第一届国际人工智能联合会议的专 题讨论会上被正式提出，之后该问题得到了学术界以及企业界的广泛关注，并一直迅速 地发展，每年都有许多数据挖掘方面的国际级的学术会议召开，许多企业如m m 等也 一直致力于该技术的研究与应用，因此，相当数量的数据库知识发现产品和应用系统相 继出现，得到了广泛关注。同时，多学科的相互交融与相互促进，如数据库技术、机器 学习、统计学、信息提取、数据可视化以及并行处理等，使得数据库知识发现这一学科 在理论上得到越来越多的支持，因此众多应用领域中，如文本挖掘、超文本挖掘、图像 挖掘、多媒体数据挖掘、时间序列数据挖掘，都取得了令人满意的成果。 数据挖掘方面的方法或算法，按挖掘任务的不同，可以分为以下几个大类：分类知 识发现、数据聚类、关联规则发现、数据总结、序列模式发现、依赖关系或依赖模型发 现、异常发现和趋势预测等。 ( 1 ) 分类知识发现 分类知识发现是数据挖掘中最常见的任务，其目的在于根据样本数据寻求相应的分 类规则，然后根据获得的规则来确定某一非样本个体或对象是否属于某一特定的组或 类。在这种分类知识发现中，样本个体或对象的类标记是己知的。数据挖掘的任务在于 从样本数据的属性中发现个体或对象分类的一般规则，从而根据该规则对非样本数据对 象进行分类。 ( 2 ) 数据聚类 数据聚类是用于发现在数据库中未知的对象类。这种数据类划分的依据是“物以类 聚”，即按个体或数据对象间的相似性，满足相似性条件的个体或数据对象划分在一组 内，不满足相似性条件的个体或数据对象划分在不同的组。由于在数据挖掘之前，数据 类划分的数量与类型均是未知的，因此在数据挖掘后需要对数据挖掘结果进行合理的分 析和解释。 基于人体运动捕捉数据的高维时间序列模式挖掘算法的研究 ( 3 ) 关联规则发现 关联规则发现是在数据库中寻找数据对象间的关联模式。关联模式发现主要用于零 售业交易数据分析，以进行物品更合理的摆放，最终提高销售量。因此，该方法有时也 直接称为“货篮分柝”。 ( 4 ) 数据总结 数据总结是将数据库中的大量相关数据从较低概念层次抽象到较高概念层次的过 程。计数、求和、求平均值、求最大值和最小值等计算都是数据总结的具体化。由于数 据库中的数据所包含的信息往往是最原始、最基本的信息，有时人们需要从较高的层次 上浏览数据，这就要求从不同的层次上对数据进行总结以满足需要。 ( 5 ) 序列模式发现 序列模式发现是在数据库中寻找一段时间区间内的序列间的关联模式，一个序列模 式的例子是几个月以前购买奔腾个人电脑的客户很可能在1 个月内订购新的c p u 芯片。 序列模式同关联模式非常相似，区别在于序列模式表述的是基于时间的关系，而不是关 于数据对象问的关系。因此，在有些文献中也称其为基于时间的关联规则发现。 ( 6 ) 依赖关系或依赖模型发现 依赖关系或依赖模型发现是通过数据库中数据的分析，获取数据间的某种因果联 系，这种因果联系既可能是内在的某种概率分布关系的描述，也可能是数据对象间存在 的确定的函数关系。 ( 7 ) 异常发现 异常发现用于在数据库中发现数据中存在的偏差或异常。如二月份与一月份相比销 售收入的骤然升高，类似这样的相邻时间段内信息的异常变动就应引起人们的关注。 ( 8 ) 趋势预测 趋势预测是根据数据库中的历史信息对未来信息做出估计。实际上，预测这一数据 挖掘任务并不一定是独立的一般来讲，上述几种数据挖掘任务的结果，都可以在分析 后用于趋势预测。 1 2 时间序列数据挖掘技术概述 近些年来，时间序列数据库的数据挖掘作为数据挖掘问题中的一个子问题受到了广 泛的关注。如零售行业的p o s 机数据、证券公司的股票数据以及人造卫星观测到的气象 数据等都是典型的时间序列，这些数据在商业、金融、医学和社会科学等大型数据库中 占据了很大的比例。与传统数据挖掘算法所研究的对象不同的是，其它数据对象通常是 静态的数据，即欲挖掘的模式与数据库中信息呈现的顺序无关。然而。在一些与时间紧 大连理工大学硕士学位论文 密相关的领域，例如股票趋势预测、入侵检测、通信数据流分析、多媒体信息检索以及 关键设备运行状态的监控等，采用与时序无关的数据挖掘技术并不能最大程度地提取到 有价值的信息，而此时引入时序信息往往可以有效地改善挖掘的结果。随着此类应用的 范围不断扩大，尤其是对多媒体等复杂信息进行深层次处理的需求不断增加，对于时间 序列数据库的数据挖掘引起了广泛的关注。 时间序列被系统地定义为：具有时间信息、并且每一个时间点都由单个或多个变量 构成的序列。由这样的序列构成的数据库叫做时间序列数据库( t i m es e r i e sd a t a b a s e t s d b ) 。与其它数据类型相比较，时序数据有着自身的特点，认识这些特点有助于找到 合适的方法对其进行研究。从数据挖掘的角度进行归纳，时间序列数据有以下特点： ( 1 ) 有明显的时间先后 每个记录都必须有时间维，序列中数值或数据点的位置依赖于时间，即数据的取值 依赖于时间的变化，但不一定是时间t 的严格函数。 ( 2 ) 反映出序列特征 不论哪种类型，应该是在某一时间段内连续( 或采样) 的记录集，有一定的连贯性和 规律性可寻，从整体上看，往往呈现某种趋势性或出现周期性变化的现象。 ( 3 ) 随机性 每一时刻的数值或数据点的位置具有一定的随机性，不可能完全准确的用历史值预 测。 对于时间序列的相关研究，主要集中在对时间序列的分块表示、索引建立、相似性 检索、模式分析、异常事件检测等方面。根据每一个时刻对应的数据不同，其又可划分 为一维时间序列和多维时间序列。一维时间序列，即每个时刻只包含一个单变量的时间 序列，由于仅具有一个维度且研究时间较早，因此在索引建立及相似性检索等许多方面 都出现了一些较为成熟的算法。 1 3 高维时间序列数据挖掘技术概述 近年来，随着技术的发展以及需求的增加，出现了许多更加复杂庞大的时间序列数 据库：即与一个时刻对应的往往是多个实数变量或者描述性的属性，而非简单的一维、 实值变量；其相互之间的关系也再局限于变量与时间之间的相关性，变量与变量之间也 会具有一定的联系，以至有时需要用图而不仅仅是多维向量来表示变量之间的关系。这 样的时间序列被称为高维时间序列。较为典型的例子有航天飞船等重要仪器的运行状态 数据、互联网中关键服务器的通讯流量数据、高新生物医学实验中的测量数据、地震以 及天文方面的重要测量数据、应用于多种行业的人体运动捕捉数据等。 基于人体运动捕捉数据的高维时间序列模式挖掘算法的研究 在实际应用中，由于每一时刻对应数据的维度膨胀所带来的计算复杂度的激增，使 得大部分成功应用于一维时间序列的挖掘技术，诸如发掘时间序列中的主旨模式、检测 时间序列中的异常事件以及时间序列的分类和聚类等技术，都无法成功地应用在高维时 间序列的挖掘上。因此在各方面尤其是模式提取、异常检测等高计算复杂度问题上。都 需要寻找新的有效算法。 目前，国内外对此领域的研究还不够深入，仅在对高维时间序列的相似性检索方愿 进展较大，己有支持多种相似性度量的索引机制被提出，并具有较好的性能，然而对于 其他方面的研究，譬如主旨模式的提取、异常检测、分类聚类等方面，尚属空白。近年 来，众多领域中的大量复杂的高维时间序列都需要使用新方法进行有效地、深层次地分 析，因此研究相关的有效算法是很有意义的。 1 4 本文工作及组织结构 本文立足于分析和对比时间序列相似性度量、索引建立以及模式挖掘等主要研究方 向的现有解决方法，通过使用人体运动捕捉数据作为具体分析对象，对高维时间序列的 特征进行了深入的分析，分别在相似性检索和模式挖掘方面给出了高精度、低复杂度的 算法，并通过实验证明了该算法的有效性。 本文内容安排如下： 第一章主要介绍了数据挖掘的基本概念、任务和主要研究问题，随后将时间序列的 数据挖掘作为该领域的一个子问题引出进行了阐述，最后指出研究高维时间序列数据挖 掘相关算法的重大意义和价值。 第二章首先详细地总结了针对一维时间序列分析方面的若干个主要问题，如相似性 度量、索引建立和主旨模式挖掘等方向，国内外已经取得的研究成果。之后，对比列出 了针对高维时间序列对象方向的研究现状。 第三章重点分析了时间序列在相似性度量、降维以及索引建立方面常用的各种方 法，其中包括各算法的主要思想，关键推导，使用范围，优缺点等。 在第四章中，针对序列的快速检索问题，本文使用人体运动捕捉数据作为分析对象 进行研究。首先，提出了一种新的借助于运动中产生的能量对运动进行描述的模型。在 此基础上，引入运动协调性的概念，并据此提取出能够有效地体现原运动特征的低维度 索引序列。之后，利用支持向量机和索引序列对运动进行粗分类。最后，利用基于k e o s h 下界的线性索引算法精确地度量输入运动和候选动作之间的相似性。实验表明该检索方 法具有较好的速度和准确性。 大连理工大学硕士学位论文 第五章中，本文指出了现有主旨模式挖掘算法在噪声环境下度量精度差的问题，并 提出了基于最长公共子序列距离的弹性匹配主旨模式算法，同时针对该方法计算复杂度 高的问题，给出了基于剪枝优化的改进算法。之后，采用了层次化聚类的方法将相邻重 叠并高度相似的候选模式进行合并，仅保留下能够充分体现序列各部分特征的序列。最 后，对于搜索过程中提取出来的非等长候选模式，使用了最小描述长度原则求得其权重， 并据此选择出现频率最高、最能体现原时间序列特征的主旨模式。 最后在结论部分，总结了本文的研究成果，指出在时间序列相似性的研究过程中遇 到的难点和下一步的研究方向。 一5 一 基于人体运动捕捉数据的高维时间序列模式挖掘算法的研究 2 时间序列国内外相关研究介绍 2 1 时间序列的表示以及相似性检索的研究现状 时间序列的相似性检索是目前研究的热点之一，其相关算法是大多数时间序列挖掘 算法的应用基础；同时，它也是人们能够有效地管理大型时间序列数据库的重要技术之 一 在该问题中，其中一个重要的问题就是相似性的定义，目前常用的衡量相似性的方 法有欧几里得距离、动态时间形变距离( d y n a m i ct i m ew a r p i n g ，d t w ) 以及最长公共子 序列距离( l o n g e s tc o m m o ns u b s e q u e n c e ，l c s s ) 。欧式距离由于定义简单、计算方便， 很早便被广泛的使用。但是，随着应用的发展，其在许多噪声下无法给出精确度量结果 的缺点日益无法满足应用的需求。 针对该问题，一些针对噪声干扰具有鲁棒性的度量方法逐渐开始替代欧式距离，其 中d t w 和l c s s 是两种应用最为广泛的方法，前者通过重新校准序列时间轴上的对应 关系来消除噪声的影响，后者则通过寻找序列间的最长公共子序列来剔除尖锐噪声点， 因此具有更强的鲁棒性。另外，人们还提出基于形状等特征的度量方法。 在相似性检索中，另一个重要的问题就是低维索引的建立以及索引组织方法。在索 引建立方面，已有的研究成果从频域变换、线性分段和正交变换等多个方面入手，给出 了傅立叶变换、小波变换、线性分段近似、主分量分析、独立分量分析等多种方法，用 于解决不同类型数据的低维索引的提取。基于这些低维索引，为了能够在检索过程中加 快检索速度，需要引入一些高效的空间数据结构来组织索引，目前常用的结构r - t r e e 及其变形r 。- t r e e ，建立在这些结构上的搜索算法可以有效地进行剪枝用以提高效率。 国外对这两个问题的研究大约开始于2 0 世纪9 0 年代。a g r a w a l i h 等首先于1 9 9 3 年 提出了利用傅立叶变换对时间序列进行变换，提取前若干个频率分量作为序列索引的算 法，并论证了该算法的有效性。f a l o u t s o s 【2 】等随后提出了同样基于傅立叶变换的支持予 串查询的索引算法，该文同时提出了用于解决时闻序列相似性检索问题的算法框架，并 规定了该类算法所应满足的几个条件。r a f m 【3 等则提出了在相似性比较中允许形变的索 引算法，c h a r t l 4 等证明了离散小波变换可以替代离散傅立叶变换来提取时间序列的频率 分量作为索引，并且该方法更加有效并具有更低的复杂度。另一些学者则将研究重点放 在时间序列的分割和近似表示尚，y i 5 】等、k e o g h 嘲等分别提出了基于分段常数近似 ( p c a ) 的标志提取算法，并分别证明了这种方法可以适用于多种相似性度量而无需改变 索引结构。k e o g h 7 】等针对p c a 进行了改进，提出了自适应长度的p c a 算法，该算法 一6 一 大连理工大学硕士学位论文 可以在序列变换缓慢的部分使用较少的信息对其进行近似，而在变换剧烈的部分使用较 多的信息进行近似，从而克服了传统p c a 需要将序列分割成等长予序列、信息表达不 够充分的缺陷，但该算法的复杂度较高，达到了o ( n 2 ) 。针对d t w 算法复杂度过高的 问题，k e o g h 8 1 等在2 0 0 2 年提出了计算d t w 距离精确下界的算法，这是目前性能最好 的d t w 下晃算法。在分段线形近似的基础之上，k e o g h l 9 1 等提出了基于地标( 1 a n d m a r k ) 的技术，该技术通过提取序列的数学特征点，如极值、拐点等作为索引。在此基础上， p e m g 【o 】等提出了更具通用型的地标模型，该模型具有不受时间轴上伸缩、振幅伸缩等 噪声干扰的性质。k i m n 】等提出了一个简化的地标模型，通过提取一个序列中的最小、 最大、最初和最末的元素，来解决在由时间轴上的形变所引起的匹配问题。在子序列查 询方面，其他一些改善查询性能的技术也被提出。b a e z a 1 2 l 等和p a r k 1 3 等分别独立地提 出利用后缀树来避免重复求解基于动态规划的相似性度量问题。k e o g h 0 4 ) 等提出了分段 线形近似算法来约简时间序列的维数，这种算法能有效应用于包括动态时间变形等数种 相似性度量，并且已被证明优于基于离散傅立叶变换的标志提取算法。在此基础上， k e o g h t ”】等提出了一种基于哈希的概率索引方法。 国内的相关研究起步较晚，并主要集中在一维时间序列相似模式匹配方面。蒋嵘f l q 等提出了一种基于形态表示的时间序列相似性搜索算法，该方法采用线性分段近似的方 法将复杂的时间序列简化成若干直线段，之后使用一系列符号来表示时间序列，在此基 础上通过构造基于云模型的形态概念树，使用增强的动态规划算法来实现相似序列的查 找。黄河【1 7 】等使用线性回归方法用直线对时间序列进行建模。为了进一步简化数据，该 文从每段序列中提取特征向量来表示该段。针对各段特征向量的长度可能不同的问题， 提出了线性检索方法来加快检索的速度。虞健飞【1 8 】等使用马尔科夫过程来描述时间序列 的动态特性，将时间序列之间的距离转化成其对应的马尔科夫过程状态转移矩阵之间对 应行的平均k u l l b a c k - l i e b l e r 距离来衡量时间序列之间的相似性。李爱国l l 观等使用分段 多项式表示( p p r ) 的方法来表示时间序列，提出基于线性多项式回归的正交变换在变换 索引时间序列数据方面具备非漏报性质，并提出了一种快速的相似性检索方法。李秋丹 刚等提出一种基于小波包变换的时间序列相似搜索算法。该文首先利用小波包可对信号 进行精细分析的特点，对时间序列进行维数约简，用变换后的低频系数和部分高频均值 系数作为特征向量表示原始序列；然后用多维索引结构r - t r e e 存储这些特征向量，将 欧几里德距离作为相似尺度，最后基础上实现了范围查询和k 近邻查询。龚薇等1 2 u 提出 了一种基于变化点的时间序列近似表示方法。该方法首先定义了偏离度的概念- 偏离度 衡量了时间序列上各点在局部范围内的偏离程度。之后根据各点的偏离度，定义了时间 基于人体运动捕捉数据的高维时间序列模式挖掘算法的研究 序列的变化点，将所有的变化点依次用直线段相连，从而得到了基于变化点的时间序列 分段线性表示。 2 2 时间序列模式分析的研究现状 目前对于模式分析的研究主要集中在主旨模式和周期性出现模式的发现及提取。 k e o 曲皿j 等人在2 0 0 2 年提出主旨模式的概念，所谓主旨模式，即指未知的而又频繁出现 的模式。该研究方向的成果可以作为归结和可视化大规模时间序列数据库的有力工具。 此外，主旨模式还可应用于关联规则的提取以及聚类等方面。 b i l l 瞄l 等人于2 0 0 3 年提出了一种基于概率的算法，该方法首先将高维的时间序列投 影到低维的子空间上，之后在该低维空间中搜索主旨模式的候选序列，最后再使用原始 序列进行精确搜索，从而找到主旨模式。y o s h i k i 2 4 1 等人针对高维的时间序列，在2 0 0 3 年提出了一种基于主分量分析和最小描述长度( m i n i m u md e s e r i p t i o i ll e n g t h ，m d l ) 法 则的主旨模式提取算法。实验结果表明，他们的算法可以有效地支持可变长主旨模式的 提取，然而却存在着信息损失过多结果不精确的缺陷。针对已有的主旨模式算法无法有 效地将遍历搜索和复杂模式描述结合在一起的i 日题，j e n s c n 2 5 1 等入提出了一种通用性的 模式提取算法，这种算法允许用诸如正则表达式等复杂方式描述模式，他们的实验表明， 此算法可以应用在d n a 序列检测等多种领域，但该算法同时存在着复杂度高、通用性 较差的问题。对于时间序列中周期性出现的模式，也引起学者浓厚的兴趣。w a l i d l 2 6 1 等 人在2 0 0 2 年提出了在线增量挖掘算法，这种能够自适应调整阈值的算法能够有效地发 现局部周期性模式。y a n g 2 7 等人在2 0 0 3 年提出了一种异步周期模式的模型，用来描述 噪音环境下的模式的周期性。c h f i s t o s m j t 提出了在没有先验知识的条件下，从时间序 列中检测近似和部分周期性的算法。这种基于相关函数以及快速傅里叶交换的算法，可 以从时间序列中提取周期长度的特征，并满足最小置信阈值。另外还有一些研究集中于 定义及发现时间序列中的异常。k e o g h 溯等在2 0 0 2 年提出了奇异模式的概念，在此基础 上，他们使用后缀树对所有模式进行编码，通过马尔可夫模型来预测模式变化的趋势。 c h a n e 3 0 j 等在2 0 0 3 年提出了基于机器学习的高维时间序列异常检测算法。b u n k d 3 q 等在 2 0 0 4 年给出了图的形似度定义，并提出了检测图的时间序列中的异常事件算法。 在国内，关于模式分析相关的研究相对较少，并主要集中在一维时间序列上。黄河 蚴等在该文提出了一种新的能够快速挖掘时间序列中模式的方法。该算法首先将时间序 列分成若干等长的子序列；接着从每个子序列中提取能够反映其变化趋势特征的特征序 列；然后根据该特征序列将相应的子序列分配到一系列盒子中，使得不同盒子中的子序 列因数据变化趋势不同而不相似，而在同一盒子中的序列由于数据变化趋势相同而有可 大连理工大学硕士学位论文 能相似；最后通过计算每个盒子中任意两个子序列间的欧几里德距离来发现所有的模 式。詹艳艳1 3 3 1 等使用分段线性近似方法以及基于斜率提取边缘点的s e e p 方法来近似地 表示时间序列，在此基础之上通过使用基于模式表示方法的挖掘频繁子模式的算法。李 斌f 蚓等使用遗传算法来降低主旨模式搜索的时间的复杂度。郑诚t 3 5 等给出了基于小波交 换模极大值的时间序列中异常事件多尺度检测的方法。通过沿小波变换模极大值线搜 索，该方法可以在各个尺度上观察异常事件。 2 3 高维时间序列相关问题的研究现状 国外在该方面的研究起步较早，研究方向主要集中在如何有效地对高维数据进行降 维，并据此建立低复杂度、精度可靠的、可实际应用的大型高维时间序列数据库的检索 算法。k a h v e c i 等【3 6 l 定义了一种新的针对高维时间序列，并在幅度伸缩和位移噪声下保 持不变的相似性度量方法，在此基础上，给出了新的索引结构c s i n d e x ，该结构可以根 据序列的幅度伸缩和位移情况对原序列进行变形和聚类以达到精确比较序列相似性的 目的。v l a c h o s 等【3 7 】给出了一种基于最长公共子序列度量的高维时间序列索引结构，该 索引还可以在不重构的条件下支持欧式距离、d t w 距离等度量方法。实验证明该方法可 以在保证无漏检序列的前提下，大幅降低搜索时间复杂度。l ic h u a n j u n 等i 3 8 】提出了一种 快速分类高维时间序列的方法，该方法首先使用s v d 对序列进行特征提取，之后使用 s v m 对特征向量进行分类。 另外，还有相当一部分的相关研究选择一些特定的高维时间序列进行研究，提出其 相关的解决方法，其中人体运动捕捉数据就是研究重点之一。k o v a r 等【3 9 】提出了一种基 于查询结果再查询的算法，该算法首先找出与查询序列数值上相似的候选序列，之后使 用这些序列作为查询序列进行再查询，该算法可以找到一些与查询序列逻辑上相似但数 值上差异较大的序列，并且其速度可以达到实时交互的要求。m u l l e r 等4 0 i 通过充分挖掘 人体运动过程中人体各关节之间相对位置的几何关系，提取出了基于几何关系的低维布 尔值索引序列，该索引被用来对运动进行粗略的判别，在搜索过程中可以避免一些无谓 的判断。在此基础上，使用了改进的d t w 索引算法，从而完成对序列的快速搜索。w u 等【4 1 】将每帧分解为九个姿态片断，针对每个片断，利用自组织网络聚类构建一个索引网 络，据此选出与查询动作最相似的候选动作序列。c l i f f o r d 等【4 2 】将研究重点放在了如何 有效地提取动作的关键帧，并从熵和互信息的角度考虑，对人体运动的每一帧的重要性 进行定义，从而选出关键帧k c 0 曲等【4 3 】提出了现有的基于d t w 距离度量的搜索算法只 能消除局部形变带来的噪声，而无法解决全局形变带来的噪声的问题，提出了基于包含 边界的索引方法，并通过人体运动捕捉数据进行了验证。l i u 掣删提出了一系列基于离 基于人体运动捕捉数据的高维时间序列模式挖掘算法的研究 线训练的数据表示、压缩和索引的算法。该算法首先通过分类器训练一个离线线性模型， 之后使用该模型可以对运动数据进行分类、查询等操作。 国内关于高维时间序列模式挖掘的相关研究并不多序列的搜索上，并主要集中在相 似性搜索算法的研究。刘丰彤】等提出了针对高维的入体运动捕捉数据的快速搜索算法， 该算法基于关键帧以及高维聚类算法来加速搜索。梁建海脚培用浮动搜索算法对高维时 间序列进行特征选择得到低维特征参数。并采用w s t b ( w e i g h t e ds h a p et ob i t v e c t o r ) 方法实现对高维时序的相似性搜索。郝井华 4 7 1 等针对时间序列型高维数据提出了一种基 于局部线性映射( l o c a ll i n e a rm a p p i n g ，l l m ) 的数据变换方法，并基于l l m 的映射特 性提出了三种异常指标，将其应用于面向国家重大建设项目稽察数据一致性判别问题的 高维时间序列数据异常检测中，该算法由于针对特殊数据进行处理，因此缺乏通用性。 大连理工大学硕士学位论文 3 时间序列研究的相关技术 3 1 相关定义 一维时间序列：长度为 的一维时间序列r 可表示为t = ，0 ，其中每个均 为实数。 高维时间序列：长度为玎的高维时间序列r 可表示为r = ；，：，其中每个l 二均 为一个向量。 子序列：给定长度为打的时间序列r ，它的长度为d 的子序列p 可以表示为 p = 0 ，0 + l ，其中1 s m _ o 和b - b 0 。该条件保证 了在形变路径中，各元素是单调递增的。 这样满足d t w 约束条件并且使得形交代价函数最小的路径就是d t w 距离，该路 径满足下列关系式： d 册 c ) = m i i l 二心 ( 3 2 ) 该问题可以利用动态规划进行求解，这里定义r ( f ，力为从原点到点o ，力的最短形变 距离，贝l j r ( i ，) 可以表示为： ，( f ，) = d ( f ，j ) + m i n r ( i l ，) ，o ，一1 ) ，r ( i 一1 ，- ，一1 ) ) ( 3 3 ) 根据该公式，路径w 可以在o ( m n ) 的时间复杂度内求解，但这依然是个比较高的 复杂度。 3 2 3 动态时间弯曲距离k e o g h 下界距离 计算序列间的动态弯曲距离的算法需要o ( m n ) 的复杂度，这一缺陷阻止了该算法在 大型时间序列数据库中检索的应用。研究人员提出了许多方法来加速d t w 距离的计算 速度，但由于d t w 本身不满足三角不等式，因此大部分算法都不是d t w 的精确索引。 直到2 0 0 2 年，k 心曲才第一次提出了关于d t w 距离的精确下界，该方法从数学上保证 了不会出现漏检的候选序列。这里给出该下界算法的定义。 首先需要定义一个d t w 形变路径的约束条件，在实际计算中，为了防止一些不符 合实际情况的路径被选中，需要约束形变路径中每个元素中f ，的关系，常用的约束 条件有两种，s a k o e c h i b a 和i t a k u r a 路径约束。如图3 2 所示。以前者为例，其应满足 条件_ ，一，f ，+ ，其中，定义为可达半径。在此基础上定义时间序列的上界和下界序 列，【，和。给定一时间序列q ，则其对应的u 和分别是 q = m a x ( x j _ ，而+ ，) ( 3 4 ) 厶= m i n ( t 一，x j + ，) ( 3 5 ) 基于人体运动捕捉数据的高维时间序列模式挖掘算法的研究 曩圈 s 曩轴刊融嘲酗细辑翱翔珈蓦。蓼峨 图3 2s a k o e - c h i b a 和i t a k u m 路径约束 f i g 3 2 t h ep a t hc o n s 廿a i n to f t h es a k o e - c h i b ar u l ea n dt h ei t a k u r ar u l e 最后给出k e o g h 文中定义的d t w 距离下界的具体定义，给定时问序列q 和c ，长 度分别为n 和朋，并且每帧都具有个属性。 则它们之间下界距离可以表示为 l b k e o g h ( q ，c ) = ( 3 6 ) 3 2 4 最长公共子序列距离( l o n g e s tc o m o ns u b s e q u e n c edis t a n c e ) 当两时间序列在大部分时间段具有相似的形态，而只在很短的时间范围内发生剧烈 突变或间断时，欧几里德距离和d t w 距离都无法准确地衡量时间序列发生短期突变或 间断时的相似性。 为了有效地支持该噪声环境下的相似序列匹配，人们提出了基于最长公共子序列的 距离度量方法。该算法只尝试匹配序列闯的相似部分，并忽略不相似的部分。 最长公共子串方法在语音识别和文本匹配研究中得到广泛研究，其基本思想是用最 长公共子串的长度来衡量两个字符串的相似性程度对于时间序列来说，一种直接的方 法就是把时间序列的序列值离散化为单个字符，从而时间序列就自然成为字符串。 给定两序列q 和c ，长度分别为阼和j ，l ，它们之间的最长公共子序列的长度可以使 用下面的公式进行求解。 大连理工大学硕士学位论文 根据最长公共子序列( l o n g e s tc o m m o ns l 】b 跎q 咖c e ) 的定义，给定两符号序列x 和 y ，长度分别为n * o m ，它们之间的最长公共子序列的长度表示为： i o f = o o r m = o z c s s ( q ，c ) = l c s s ( q 。，q ) = 1 i + l c s s ( q - 1 ，c 胛一i )矿q = q ( 3 7 ) 【删a x ( z c s s ( q ，c 晨- 1 ) ，z c s s ( q 。_ i ，g ) ) o t h e r w i s e 该长度可以使用动态规划有效地进行求解。在此基础上，有多种基于最长公共子序 列算法的距离表示方法提出，在此仅列举出一种常用形式，两序列之间的最长公共子序 列距离可以表示为 p 瞄= 面l 丽c s s 厕( q , c ) ( 3 8 ) 该算法的特点在于其只尝试匹配序列间的相似部分，并忽略不相似的部分，因此可 以有效地降低噪声对于挖掘结果带来的负面影响。 l c s s 算法和d