能量模型数据挖掘的研究

摘要：本文通过数据挖掘自身的特点，有效地结合相关算法并基于人体运动捕捉数据，给出这两个问题的有效解决方法。主要工作如下： (1) 提出了基于能量模型的算法。相对于现有文献中使用的关节的几何位置，本文提出了的人体能量模型能够有效地降低动作数据的维度，并且能够正确地反映原动作的特征。在此基础上，使用相关系数来表示人体运动过程中各关节之间的相关性，并据此提取出原动作的低维度索引，实验表明该索引能够有效地体现原动作的特征。使用支持向量机结合低维度索引可以有效地讲输入动作划分到一个动作大类中，在此基础上使用基于Keogh下界的线性索引算法可以精确、快速地检索到与输入动作DTW距离最近的候选动作。 (2) 提出了基于公共子序列距离的数据挖掘算法。相对于现有文献中使用的欧式距离，本文使用的基于最长公共子序列的度量方法能够有效地降低噪声对于挖掘结果的不利影响。使用启发式搜索可以将搜索所需要的时间降低为使用朴素式搜索算法的60%以下，并且随着序列的长度的增加、计算量的增大，前者相对于后者运行时间的百分比有明显的减小趋势，利用这一特性，该算法可以在长序列的主旨模式挖掘中，大规模地减少算法的运行时间。在各长度的候选模式集合中，使用层次化聚类分析可以有效地合并相似度较高的候选模式，以达到合理约简模式、消除相邻重叠模式对结果不利影响的目的。使用最小描述长度原则可以根据模式的长度以及出现频率对候选模式表达整个原序列的能力进行有效地评估，从而达到支持非固定长度主旨模式挖掘的目的。

关键词：人体运动能量；最长公共子序列；数据挖掘

中图分类号 TP31 文献标识码Adoi:10.3969/j.issn.1003-

6970.2011.01.008

The Research of the Data Mining Based on Energy model

WANGFei

(NanYang Industry University continue technology institute，NanYang473009)

【Abstract】By taking the human motion capture data as the analysis object, effective algorithm is brought forward on the two subjects respectively and the experiments verify the availability and high performance. (1) Different from the spatial position based model used in traditional retrieval methods, a novel model based on kinetic energy is proposed and used to describe human motion. Based on the model, the motion coordination is introduced and used to extract the low-dimensional indexing sequences that are remarkable features of original motions. The support vector machine is applied to classify the motion. Finally, the sequential indexing algorithm based on the Keogh lower bound is employed to measure the similarity of query motion and candidate motions exactly. (2) Against the problem that existing algorithms are apt to be interfered by noise, a motif mining algorithm based on the LCSS distance is introduced. The algorithm has pruned efficiently by using the heuristic strategy based on the distance between subsequences during the search. Then the MDL principle is used to calculate the weights of the unequal-length candidate sequences based on which the motif patterns are selected.

【Keywords】 Human Motion Capture Data, the High-Dimension Time Series, Data Mining

0 引言

采用时间序列的相似性检索相关算法是大多数时间序列挖掘算法的应用基础；同时，它也是人们能够有效地管理大型时间序列数据库的重要技术之一。

国外的相关研究中，Agrawal[1]等首先于1993年提出了利用傅立叶变换对时间序列进行变换，提取前若干个频率分量作为序列索引的算法，并论证了该算法的有效性。Faloutsos[2]等随后提出了同样基于傅立叶变换的支持子串查询的索引算法，该文同时提出了用于解决时间序列相似性检索问题的算法框架，并规定了该类算法所应满足的几个条件。Rafiei[3]等则提出了在相似性比较中允许形变的索引算法，Chan[4]等证明了离散小波变换可以替代离散傅立叶变换来提取时间序列的频率分量作为索引，并且该方法更加有效并具有更低的复杂度。另一些学者则将研究重点放在时间序列的分割和近似表示尚，Yi[5]等、Keogh [6]等分别提出了基于分段常数近似(PCA)的标志提取算法，并分别证明了这种方法可以适用于多种相似性度量而无需改变索引结构。Keogh[7]等针对PCA进行了改进，提出了自适应长度的PCA算法，该算法可以在序列变换缓慢的部分使用较少的信息对其进行近似，而在变换剧烈的部分使用较多的信息进行近似，从而克服了传统PCA需要将序列分割成等长子序列、信息表达不够充分的缺陷，但该算法的复杂度较高，达到了 。

国内的相关研究起步较晚，并主要集中在一维时间序列相似模式匹配方面。蒋嵘[8]等提出了一种基于形态表示的时间序列相似性搜索算法，该方法采用线性分段近似的方法将复杂的时间序列简化成若干直线段，之后使用一系列符号来表示时间序列，在此基础上通过构造基于云模型的形态概念树，使用增强的动态规划算法来实现相似序列的查找。黄河[9]等使用线性回归方法用直线对时间序列进行建模。为了进一步简化数据，该文从每段序列中提取特征向量来表示该段。针对各段特征向量的长度可能不同的问题，提出了线性检索方法来加快检索的速度。龚薇等[10]提出了一种基于变化点的时间序列近似表示方法。该方法首先定义了偏离度的概念-偏离度衡量了时间序列上各点在局部范围内的偏离程度。之后根据各点的偏离度，定义了时间序列的变化点，将所有的变化点依次用直线段相连，从而得到了基于变化点的时间序列分段线性表示。

本文立足于分析和对比时间序列相似性度量、索引建立以及模式挖掘等主要研究方向的现有解决方法，通过使用人体运动捕捉数据作为具体分析对象，对高维时间序列的特征进行了深入的分析，分别在相似性检索和模式挖掘方面给出了高精度、低复杂度的算法，并通过实验证明了该算法的有效性。

1 方法

1.1 试验目的

本章提出了一种分为粗分类和精确匹配两个过程的序列快速检索算法。首先通过使用支持向量机对动作序列的低维索隐序列进行分类，将其粗略地归于一个规模相对较小的动作类别中，从候选序列集合中将与查询动作不同类的动作序列去除，避免精确比较过程中不必要的比较。最终，在经过粗分类选择的类别所包含的候选动作序列集合中，使用基于DTW距离Keogh索引下界的检索算法更加准确地挑选出候选动作。

1.2 实验过程

实验相关的所有算法均采用C++实现，实验硬件环境为Athlon X2 3000+，1GB内存。在实验中采用的测试数据均为卡内梅基隆大学图形学实验室提供的免费人体运动数据(mocap.cs.cmu.edu)。在该实验中，使用的测试数据中包含走、跳高、跳远、爬高四种动作类别，其中最长的动作包含1200帧，最短的包含400帧，总共包含1,1000,000帧数据，大小为1.1GB。

图1中给出了走路、跳高以及爬高三种动作关于动能的相关系数向量，从图中可以明显地看出它们之间相差很大。图2给出了上述每种动作的三组的实例，虽然这些动作之间具有一些局部或者全局相位差等噪声，但它们的相关系数向量仍然非常接近。势能的相关系数向量与动能的结果相似。

上述实验表明，关于运动能量的相关系数向量，对于同类动作来说非常相似，而对于不同种动作则相差较远，因此可以将其作为区分不同类动作的特征序列。

图1走路、跳高以及爬高三种动作关于动能的相关系数向量

Fig. 1The coordination vector of the kinetic energy of walking, jumping high and climbing high motions

2 结 果

为了验证算法对噪声的鲁棒性，实验中使用一段正弦函数并在其中加入随机加性噪声并对其进行一些局部的拉伸、压缩来模拟噪声环境。

该段正弦函数包含100个周期，周期为0.1，每周期包含30个点，幅值为10。现分别向该函数施加幅值为0～8、0～20的随机均匀分布的加性噪声，并随机拉伸、压缩一些周期的波形。在匹配过程中，设定欧式距离的阈值为30，LCSS距离的阈值为1/2，量化级别为512。加入噪声前，给定一个周期的波形，使用欧式距离和LCSS距离都可以准确地提取出全部周期。在加入了0～8均匀分布的随机加性噪声后，使用前者仅可以提取出59个周期，使用后者可以提取到98个周期；加入0～20均匀分布的随机加性噪声后，前者仅仅可以提取出37个周期，而使用后者则可以提取出95个周期；而在随机拉伸以及缩放40个周期之后，由于前者对于相位差十分敏感，使用其度量仅可以提取出33个周期，而使用后者则可以提取出89个周期。通过上述数据可以看出LCSS距离在各种噪声下都具有较强的鲁邦性。

3 总 结

本文针对当前该领域的两个热点问题，即序列的快速检索和主旨模式挖掘，以人体运动捕捉数据作为具体分析对象，进行了深入的研究，分别提出了有效的解决方法，并通过相关实验验证了算法的有效性。

(1) 在序列的快速检索方面，通过充分挖掘人体运动的特征，本文提出了两个新的模型：借助于运动中产生的能量对运动进行描述的能量模型和利用相关系数描述人体运动中关节间协作状态的运动协调性模型。利用这两个模型，可以从人体运动中提取出能够有效地体现出其运动特征的低维度索引序列。之后，利用支持向量机对该低维索引序列进行粗分类，从而最大程度地避免了与查询序列不相似的序列参与到时间复杂度较高的精确比较中【11】。最后，在经过粗分类的候选序列集合上，利用基于DTW距离进行度量和Keogh索引下界进行剪枝的线性检索算法精确地度量输入运动和候选动作之间的相似性。

(2) 在主旨模式挖掘方面，针对现有算法易受噪声干扰的问题，本文提出了一种基于最长公共子序列距离的主旨模式挖掘算法。但该度量方法具有复杂度较高的问题，因此，在搜索过程中，该算法采用了基于子序列距离判别的策略进行了剪枝。之后，采用了层次化聚类的方法将相邻重叠并高度相似的候选模式进行合并，仅保留下能够充分体现序列各部分特征的序列【12】。最后，对于提取出来的非等长候选模式，使用了最小描述长度原则求得其相关权重，并据此选择出现频率最高、最能体现原时间序列特征的主旨模式。

在未来的研究中，本文将从以下两个方向入手：

(1) 在高维时间序列挖掘的各个方向【13】，尤其是序列检索方向，通用的降维和索引方法所能带来的性能提升已经非常有限，研究的重点逐渐转变为如何针对常用的高维时间序列，通过充分挖掘其自身的特征，提出有效的、其专用的挖掘算法。

(2) 快速检索和主旨模式挖掘算法是大多数挖掘算法的基础，如异常事件检测、聚类和分类，如何将现有的算法有效地应用于这些领域中，也是本文未来的研究方向。

参考文献

[1] Agrawal R,Faloutsos C,Swami AN. Efficient Similarity Search in Sequence Databases. 4th Proc. on Foundations of Data Organization and Algorithms (FODO), 1993: 69-84.

[2] Faloutsos C,Ranganathan M,Manolopoulos Y.Fast Subsequence Matching in Time-Series Databases. Proc. of the 1994 ACM SIGMOD Int. Conf. on Management of Data,1994: 419-429.

[3] Rafiei D,Mendelzon A.On Similarity-Based Queries for Time Series Data. SIGMOD Record, 1997, 26(2): 13-25.

[4] Chan K,Fu A.W.Efficient Time Series Matching by Wavelets.Proc. 15th Int. Conf. on Data Engineering (ICDE), 1999, 4(2): 126-133.

[5] Yi B,Faloutsos C.Fast Time Sequence Indexing for Arbitrary Lp Norms.The VLDB Journal, 2000, 5(3): 385-594.

[6] Keogh E.J,Chakrabarti K,Pazzani M.J.,Mehrotra S.Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases. Journal of Knowledge and Information Systems, 2001, 3(3): 263-286.

[7] Keogh E.J,ChakrabartiK, Mehrotra S,Pazzani M.J.Locally Adaptive Dimensionality eduction for Indexing Large Time Series Databases. Proc. 2001 ACM SIGMOD Conf. on Management of Data, 2001, 4(3): 151-162.

[8] 蒋嵘,李德毅.基于形态表示的时间序列相似性搜索[J]. 计算机研究与发展, 2000,37(5): 601-608.

[9] 黄河, 熊范纶, 杭小树. 时序数据库中快速相似搜索的算法研究, 模式识别与人工智能, 2003,16(2): 169-173.

[10] 虞健飞,朱家元,张恒喜.相似时间序列挖掘方法,计算机仿真,2003,20(9): 61-62,94.

[11] 李爱国,覃征.大规模时间序列数据库降维及相似搜索.计算机学报,2005,28(9): 1467-1475.

[12] 李秋丹,迟忠先,孙瑞超.一种时间序列相似匹配新算法.控制与决策,2004,19(8): 915-919.

[13] 龚薇,肖辉,曾海泉.基于变化点的时间序列近似表示.计算机工程与应用,2000,37(6): 601-608.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文