高效时间序列聚类算法的研究

论文摘要

时间序列是具有时间顺序的数据点集合,是一种普遍存在的数据形态,例如心电图、股票价格的变化等大量与时间相关的数据。时间序列聚类是将相似的时间序列划分为同类,时间序列聚类分析可以从中提取出隐藏着的与时间相关的有价值的信息,帮助人们进行决策,在医疗健康、股票投资、异常监测等领域有着重要的应用价值。由于时间序列数据具有高维、不等长、时序等特性,无法直接计算时间序列之间的距离,因此,传统的静态聚类算法无法直接适用于时间序列。近十多年来,众多的研究者和技术人员致力于时间序列聚类算法的研究,主要聚焦于两个方面:可以高效降维的时间序列数据重表示方法和精准的时间序列相似性度量方法。目前虽然已经产生一些有效的时间序列聚类算法,但是还存在以下缺陷:(1)时间序列重表示算法在降低维度的同时,损失了过多的原始序列信息,造成算法精度的下降;(2)时间序列相似性度量方法无法很好的估算时间序列之间的距离,精度较低;(3)现有的较好的相似性度量方法具有较高的时间复杂度,效率较低。因此,研究新型高效的时间序列聚类算法具有十分重要的理论价值和现实意义。论文选题来源于国家自然科学基金项目。为了克服现有时间序列聚类算法的缺陷,作者深入研究目前最好的时间序列聚类算法,并针对它们的缺陷,提出了两个高效的时间序列聚类算法。论文主要工作及创新点如下:(1)提出了一种高效的时间序列重表示方法,在降低维度的同时,极大程度地保留原始序列信息,并且该方法提取了原始时间序列的形状特征,可以提高相似性度量方法的精度;(2)提出了时间序列同步位点的概念以及其判别方法。同步位点可以捕获时间序列曲线的宏观形状,基于同步位点,提出了一种高效的时间序列相似性度量方法,该方法将全局相似性与局部相似性相结合,更好地计算时间序列之间的相似度;(3)针对时间序列存在无用前缀,降低算法的精度问题,提出了一种高效无用前缀删除方法。基于上述所提出的时间序列的重表示和无用前缀删除方法,提出了一种新的高效的时间序列聚类算法TSCEFAD算法;(4)最长公共子序列算法是目前最好的时间序列相似性度量方法之一,但现有的算法具有较高的时间复杂度,效率很低,作者设计了一种更为高效的最长公共子序列算法用于计算时间序列之间的相似度,并基于所提出的高效的最长公共子序列算法,提出并设计了一种新型高效的时间序列聚类算法TSCELCS算法。在目前最权威的开源时间数据集UCR上,本文设计的两个算法分别与同类最好的算法进行了仿真实验对比。实验结果表明:本文设计的两个算法可以有效地对时间序列数据集进行聚簇,在时间和精度上优于现有的最好的时间序列聚类算法。作者今后的努力方向是进一步提高本文算法的时间和精度性能,并努力将本文提出的算法应用于多变量时间序列聚类问题中。

论文目录

• 摘要
• ABSTRACT
• 符号对照表
• 缩略语对照表
• 第一章 绪论
•   1.1 选题背景及意义
•   1.2 国内外研究现状
•   1.3 论文主要工作及创新点
•   1.4 论文组织结构
• 第二章 基础理论与相关工作综述
•   2.1 基础理论
•     2.1.1 基本概念及问题定义
•     2.1.2 时间序列标准化
•     2.1.3 时间序列数据重表示
•     2.1.4 时间序列相似性度量
•     2.1.5 时间序列聚类框架
•     2.1.6 最长公共子序列算法相关知识
•   2.2 相关工作综述
•     2.2.1 TSAP算法
•     2.2.2 CATSSS算法
•     2.2.3 FASMC算法
•     2.2.4 VTC算法
•   2.3 本章小结
• 第三章 TSCEFAD:一种基于增强型碎片匹配的时间序列聚类算法
•   3.1 TSCEFAD算法设计动机
•   3.2 TSCEFAD算法框架
•   3.3 TSCEFAD算法的主要优化策略
•     3.3.1 重表示方法
•     3.3.2 一种基于同步位点的相似性度量方法
•     3.3.3 无用前缀的去除
•   3.4 TSCEFAD算法的设计与实现
•     3.4.1 TSCEFAD算法的设计思想
•     3.4.2 TSCEFAD算法的实现
•     3.4.3 时间序列重表示方法的实现
•     3.4.4 时间序列相似性度量方法的实现
•     3.4.5 时空复杂度分析
•   3.5仿真实验
•     3.5.1 实验平台及平台介绍
•     3.5.2 实验数据集介绍
•     3.5.3 算法性能对比指标
•     3.5.4 对比算法
•     3.5.5 算法性能比较
•   3.6 本章小节
• 第四章 TSCELCS:一种基于高效最长公共子序列的时间序列聚类算法
•   4.1 TSCELCS算法设计动机
•   4.2 TSCELCS算法框架
•   4.3 ELCS算法的关键策略
•     4.3.1 构建无冗余的最长公共子序列图
•     4.3.2 正向拓扑排序
•     4.3.3 反向拓扑排序
•     4.3.4 图优化策略
•   4.4 TSCELCS算法的设计与实现
•     4.4.1 TSCELCS算法的设计思想
•     4.4.2 TSCELCS算法的实现
•     4.4.3 相似性度量方法的实现
•     4.4.4 最长公共子序列方法的实现
•     4.4.5 正向拓扑排序方法的实现
•     4.4.6 反向拓扑排序方法的实现
•     4.4.7 时空复杂度分析
•   4.5 仿真实验
•     4.5.1 实验平台及平台介绍
•     4.5.2 实验数据集介绍
•     4.5.3 对比算法
•     4.5.4 算法性能对比指标
•     4.5.5 算法性能比较
•   4.6 本章小节
• 第五章 总结与展望
•   5.1 论文工作总结
•   5.2 未来展望
• 参考文献
• 致谢
• 作者简介

文章来源

类型: 硕士论文

作者: 郑炜超

导师: 李雁妮

关键词: 时间序列聚类,相似性度量,同步位点,最长公共子序列

来源: 西安电子科技大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机软件及计算机应用

单位: 西安电子科技大学

基金: 国家自然科学基金项目

分类号: TP311.13;O211.61

DOI: 10.27389/d.cnki.gxadu.2019.000503

总页数: 83

文件大小: 2968K

下载量: 221