学位论文 > 优秀研究生学位论文题录展示

基于DTW的时间序列相似性搜索的研究

作　者: 孙达辰
导　师: 尚福华
学　校: 大庆石油学院
专　业: 计算机应用技术
关键词: 动态时间弯曲时间序列相似度分段线性表示趋势转折点
分类号: TP311.13
类　型: 硕士论文
年　份: 2010年
下　载: 197次
引　用: 1次
阅　读: 论文下载

内容摘要

时间序列相似性搜索是时间序列数据挖掘领域的研究热点之一,主要需要序列间的距离度量、对原始数据的表示和实现相似性搜索这一任务的搜索算法三种技术。其中,距离度量是用来度量两条时间序列相似程度的依据,动态时间弯曲距离度量是众多距离度量中的一种,能有效地处理局部时间位移,以动态时间弯曲距离为序列间的距离度量算法,由于直接应用动态规划来计算,时间复杂度较高,这将导致在实际应用中效率很低;由于时间序列本身海量高维等特点,常常使相似搜索很难完成,这就必须以新的表示形式更好、更简洁地表达出原有数据的主要性质,在经过某种方法表示后的数据集上进行相似搜索,其中,分段线性表示方法是众多表示方法中的一种,具有快速的相似性搜索、支持新的距离度量、支持信息反馈,支持文本和数据序列、支持新的聚类和分类算法、支持奇异点检测等优点,针对其表示精度不高的缺点,大量学者提出了改进的方法。本文首先分析了时间序列相似性搜索的研究现状,对时间序列相似性搜索所需要的相关技术进行了研究。然后,对时间序列中的表示方法、尤其是分段线性表示方法进行了深入的研究。通过研究,提出了“基于时间序列趋势转折点的分段线性表示方法”,该方法在充分利用时间序列时变特征的基础上,以有效地提取序列中的趋势和压缩原始数据为目标,以时间序列中达到一定波动程度的局部极值点和非局部极值点为分段的依据。本方法在有效地提取序列中的趋势和压缩原始数据的同时,能够随着时间序列长度的增长对序列进行划分,具有高效、实现方法简便、效果直观的优点,对于不同领域的数据适应性良好。接下来,本文,重点剖析以动态时间弯曲距离为序列间距离度量的搜索算法,在研究了现有算法的基础上,提出了以提高现有搜索算法搜索效率为目标的改进算法,本算法由于避免原算法中的某些重复计算,有效地提高了运算效率。最后,结合本文提出的“基于时间序列趋势转折点的分段线性表示方法”和“提高动态时间弯曲运算效率的一种改进算法”,提出了“基于趋势转折点的动态时间弯曲算法”。实验表明,“基于趋势转折点的动态时间弯曲算法”在完成准确地进行相似性搜索的同时,明显地提高了算法的效率。

全文目录

摘要  4-5
ABSTRACT  5-6
创新点摘要  6-9
第一章绪论  9-14
  1.1 本文的研究背景及意义  9-10
  1.2 研究现状综述  10-12
    1.2.1 时间序列中的分段线性表示  10-11
    1.2.2 基于DTW 的时间序列距离度量  11-12
  1.3 本文的主要研究内容  12
  1.4 本文的组织结构  12-14
第二章时间序列相似搜索  14-24
  2.1 数据挖掘概述  14-17
    2.1.1 数据挖掘的发展概况  14
    2.1.2 数据挖掘的分类  14-15
    2.1.3 数据挖掘的功能  15
    2.1.4 数据挖掘的基本模型及各及阶段的任务  15-17
  2.2 时间序列挖掘  17-18
  2.3 时间序列相似搜索  18-23
    2.3.1 时间序列中的距离度量  18-19
    2.3.2 时间序列中的数据表示  19-23
  2.4 时间序列相似搜索的发展方向  23
  2.5 小结  23-24
第三章基于时间序列趋势转折点的分段线性表示方法研究  24-43
  3.1 时间序列分段线性表示方法的由来  24
  3.2 时间序列分段线性表示方法  24-30
    3.2.1 基于特征点的分段线性表示方法  27-29
    3.2.2 基于重要点的分段线性表示方法  29-30
  3.3 基于时间序列趋势转折点的分段线性表示方法  30-33
    3.3.1 时间序列趋势转折点  30-32
    3.3.2 基于趋势转折点的分段线性表示  32-33
  3.4 仿真实验  33-42
    3.4.1 实验环境和实验数据  33-35
    3.4.2 实验方法  35-42
  3.5 小结  42-43
第四章提高DTW 运算效率的一种改进算法  43-52
  4.1 基于DTW 的搜索方法  43-46
    4.1.1 时间弯曲距离  44-45
    4.1.2 基于动态时间弯曲距离的搜索算法  45-46
  4.2 提高 DTW 运算效率的一种改进算法  46-47
    4.2.1 现有 DTW 算法存在的缺点  46
    4.2.2 对现有DTW 算法的改进行  46-47
    4.2.3 改进后的算法  47
  4.3 仿真实验  47-51
    4.3.1 实验环境和实验数据  47-48
    4.3.2 实验方法  48-50
    4.3.3 实验结果分析  50-51
  4.4 小结  51-52
第五章仿真实验与结论分析  52-54
  5.1 基于趋势转折点的DTW 算法  52
    5.1.1 算法描述  52
  5.2 仿真实验  52-53
    5.2.1 实验环境和实验数据  52
    5.2.2 实验方法  52-53
  5.3 实验结果分析  53
  5.4 小结  53-54
结论与展望  54-55
参考文献  55-59
发表文章目录  59-60
致谢  60-62
详细摘要  62-69

基于DTW的时间序列相似性搜索的研究

内容摘要

全文目录

相似论文