基于人体运动捕捉数据的高维时间序列模式挖掘算法的研究

摘要

时间序列是包含一系列随时间变化的数据的序列，它反映了某种属性值随时间变化的特征。在金融、经济、自然科学、信息工程等重要领域，每天都会产生大量的时间序列，因此如何有效地处理这些数据并挖掘其背后隐含的规律和知识，成为人们日益关注的问题，随着研究的深入，许多经典的问题得到了有效地解决。而近年来，随着技术的发展，出现了许多复杂庞大的高维时间序列数据库，然而其带来的计算复杂度的激增，使得大部分能够成功地应用于一维时间序列的挖掘技术，都无法应用在高维时间序列的挖掘上。 针对该问题，本文首先对时间序列数据挖掘领域的研究进行了系统的文献总结，分析了时间序列及高维时间序列的分类、特点和研究现状。之后，阐述了该领域研究的几个主要问题，即相似性度量、快速检索、主旨模式挖掘，并针对每个问题，对主流方法的特点、适用范围及优缺点进行了详细的分析与说明。 在此基础上，本文针对当前该领域的两个热点问题，即序列的快速检索和主旨模式挖掘，以人体运动捕捉数据作为具体分析对象，进行了深入的研究，分别提出了有效的解决方法，并通过相关实验验证了算法的有效性。 (1)在序列的快速检索方面，通过充分挖掘人体运动的特征，本文提出了两个新的模型：借助于运动中产生的能量对运动进行描述的能量模型和利用相关系数描述人体运动中关节间协作状态的运动协调性模型。利用这两个模型，可以从人体运动中提取出能够有效地体现出其运动特征的低维度索引序列。之后，利用支持向量机对该低维索引序列进行粗分类，从而最大程度地避免了与查询序列不相似的序列参与到时间复杂度较高的精确比较中。最后，在经过粗分类的候选序列集合上，利用基于DTW距离进行度量和Keogh索引下界进行剪枝的线性检索算法精确地度量输入运动和候选动作之间的相似性。 (2)在主旨模式挖掘方面，针对现有算法易受噪声干扰的问题，本文提出了一种基于最长公共子序列距离的主旨模式挖掘算法。但该度量方法具有复杂度较高的问题，因此，在搜索过程中，该算法采用了基于子序列距离判别的策略进行了剪枝。之后，采用了层次化聚类的方法将相邻重叠并高度相似的候选模式进行合并，仅保留下能够充分体现序列各部分特征的序列。最后，对于提取出来的非等长候选模式，使用了最小描述长度原则求得其相关权重，并据此选择出现频率最高、最能体现原时间序列特征的主旨模式。

目录

文摘

英文文摘

声明

1绪论

1.1数据挖掘技术及其主要任务

1.2时间序列数据挖掘技术概述

1.3高维时间序列数据挖掘技术概述

1.4本文工作及组织结构

2时间序列国内外相关研究介绍

2.1时间序列的表示以及相似性检索的研究现状

2.2时间序列模式分析的研究现状

2.3高维时间序列相关问题的研究现状

3时间序列研究的相关技术

3.1相关定义

3.2相似性度量方法

3.2.1欧几里德距离(Euclidean Distance)

3.2.2动态时间弯曲距离(Dynamic Time Warping Distance)

3.2.3动态时间弯曲距离Keogh下界距离

3.2.4最长公共子序列距离(Longest Common Subsequence Distance)

3.3相似性变换方法

3.3.1分段线性近似(PCA)

3.3.2其他线性分段算法

3.3.3离散傅立叶变换(DFT)

3.3.4离散小波变换(DWT)

3.3.5地标(Land Mark)

3.3.6奇异值分解(SVD)

3.3.7独立分量分析(ICA)

3.4高维索引技术

3.4.1 R-Tree

3.4.2 R*-Tree

4基于相关性降维和支持向量机分类的高维时间序列快速检索算法

4.1相关定义及知识

4.1.1人体运动描述模型

4.1.2人体运动能量模型的定义

4.1.3人体运动协调性模型的定义

4.1.4支持向量机

4.2人体运动序列的快速检索算法

4.2.1基于多类支持向量机的粗分类算法

4.2.2基于DTW索引下界的精确检索算法

4.2检索算法的相关实验验证

4.3.1人体运动协调性模型有效性验证

4.3.2人体运动检索算法有效性验证

5基于最长公共子序列距离的快速主旨模式算法

5.1相关定义及知识

5.1.1相关定义

5.1.2相关知识

5.2快速主旨模式挖掘算法

5.2.1相关定理证明

5.2.2算法的基本思想

5.2.3算法描述

5.3主旨模式挖掘算法的相关实验验证

5.3.1算法运行有效性实验

5.3.2噪声下鲁棒性实验

结论

参考文献

攻读硕士学位期间发表学术论文情况

致 谢