符号化高维时间序列的检索算法研究

论文摘要

大规模的时间序列的数据挖掘问题在近些年的关注程度逐渐升高,其中高维时间序列的检索算法更是难点。由于数据维度的增多,大大增加了数据挖掘算法的复杂性,一些学者认为将时间序列符号化是十分必要的。在符号化方面,很多当今成型的算法大都是针对一维序列的,无法很好的应用于高维时间序列的符号化。本文提出一种基于多级κ均值聚类的高维时间序列的符号化方法。通过定义最大允许的平方误差τmax,来决定符号化的粒度。在符号序列检索方面,以倒排表数据结构为基础设计出一套针对符号化时间序列的检索算法。首先将倒排表查询的粗筛选算法转换成界限t集合求交问题,并提出一种基于堆的完全划分方法,使得算法在原有的基于堆的不完全划分的方法上有了较大提高。采用最长公共子序列（LCSS）作为度量序列间距离的方法。不同于传统的LCSS算法,本文提出了一种限制最小匹配率ρmin的Limited-LCSS算法,并在此基础上针对倒排表的数据结构特点对算法进行了优化,显著的提高了算法的效率。并实现了时间轴的弹性匹配。定义了高维字符的匹配方法,使得算法适用于高维的字符化时间序列的检索。最后针对人体动作序列这一典型的高维时间序列进行索引实验,证明算法具有较高的运算效率,在数据引入噪声的情况下,依然有这较高的正确性。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景
• 1.2 时间序列数据挖掘的研究现状
• 1.2.1 时间序列符号化现状
• 1.2.2 时间序列的相似性检索研究现状
• 1.3 本文工作及组织结构
• 2 时间序列的符号化
• 2.1 符号化的含义
• 2.2 符号化的意义
• 2.3 常见的时间序列符号化方法
• 2.3.1 静态法
• 2.3.2 动态法
• 2.3.3 综合法
• 2.3.4 人工法
• 2.4 基于k均值聚类的符号化方法
• 2.4.1 k均值聚类
• 2.4.2 符号分配
• max的选取'>2.4.3 τ_max的选取
• 2.4.4 多级k均值聚类的符号化算法
• 3 时间序列的相似性
• 3.1 时间序列的相似性概念
• 3.2 相似性查询的完备性和对索引的影响
• 3.3 时间序列的相似性度量
• 3.3.1 Minkowski距离
• 3.3.2 动态时间弯曲距离
• 3.3.3 编辑距离
• 3.3.4 最长公共子序列距离
• 4 基于倒排表结构的符号化时间序列检索模型
• 4.1 倒排表索引动作符号
• 4.2 相似度匹配算法
• 4.3 粗筛选算法
• 4.4 界限t集合求交
• 4.4.1 基于堆的不完全划分法
• 4.4.2 基于堆的完全划分法
• 4.5 Limited-LCSS算法
• 4.5.1 相关定理证明
• 4.5.2 算法基本思想
• 4.5.3 算法描述
• 5 符号化检索实验
• 5.1 界限t集合求交算法比较
• 5.2 人体动作库检索
• 5.2.1 实验数据说明
• 5.2.2 符号化处理
• 5.2.3 实验结果与分析
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢