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

基于DTW距离的两步式时间序列相似搜索

作　者: 欧阳一村
导　师: 任江涛
学　校: 中山大学
专　业: 软件工程
关键词: DTW距离两步式时间序列相似搜索
分类号: TP391.3
类　型: 硕士论文
年　份: 2010年
下　载: 68次
引　用: 0次
阅　读: 论文下载

内容摘要

动态时间弯曲(DTW)是一种度量具有不同长度或不同步的时间序列之间相似度的有效方法,它被广泛地应用于时间序列的相似搜索。但是这种方法因为时间复杂度太高而使得一般不能直接应用于相似搜索问题的解决上。针对这个问题,本论文提出了一种基于DTW的两步式时间序列相似搜索方法。这种两步式方法应用于DTW距离的计算之前,通过这些过程,得到比原来数据集规模小得多的候选集,仅在小规模候选集上进行DTW距离计算,从而使算法整体复杂度大幅下降。第一步是通过值域划分柱图将时间序列映射到K维空间,构造这个空间内两个序列之间新的距离函数。此距离函数值小于实际DTW值,所以进行范围查询时,可以将部分序列从候选集中排除。这个方法时间复杂度比较低,但由于未考虑元素顺序和弯曲宽度约束,过滤能力相对来说并不高,所以作为两步式方法的第一步。第二步是针对DTW距离提出的新的上下界,包括上界和下界。它能够在得到两条不同时间序列DTW距离的两个方向的估计值,以这两个估计值作为筛选出候选时间序列的标准。新的下界函数比已有的下界函数更加接近实际的DTW距离值,同时还可以通过计算得到上界函数值。新的上下界函数的时间复杂度比较高,但由于过滤能力的较大增强,可以作为两步式方法的第二步。两步式方法实际上从时间复杂度和过滤能力上取得了平衡。两种方法的结合使得两步式方法同时吸取了两者的优势。仿真实验的结果不但表明了两步式方法的每一步都优于已有的同类方法,而且两者相结合也优于两种方法独立使用的结果。

全文目录

摘要  3-4
ABSTRACT  4-8
第1章引言  8-14
  1.1 课题的研究背景及意义  8
  1.2 课题的研究现状  8-12
  1.3 论文的主要工作及创新点  12-13
  1.4 论文的体系结构  13-14
第2章时间序列相似搜索的相关技术  14-26
  2.1 自由扫描  14-16
  2.2 快速映射  16-17
  2.3 下界函数  17-22
  2.4 二进制柱图  22-24
  2.5 小结  24-26
第3章柱图空间的相似搜索  26-40
  3.1 柱图空间相似搜索原理  26-27
  3.2 基于柱图的空间序列  27-29
  3.3 柱图空间序列距离函数  29-35
  3.4 仿真实验  35-38
  3.5 小结  38-40
第4章 DTW距离的上下界值估计  40-62
  4.1 DTW 距离上下界估值方法的作用  40-41
  4.2 经典的DTW 距离下界估值方法  41-43
  4.3 上下界估值方法  43-57
  4.4 仿真实验  57-61
  4.5 小结  61-62
第5章两步式相似搜索  62-68
  5.1 两步式相似搜索的原理  62-64
  5.2 两步式相似搜索的比较优势  64
  5.3 仿真实验  64-66
  5.4 小结  66-68
第6章结束语  68-70
  6.1 全文总结  68-69
  6.2 进一步的研究工作  69-70
参考文献  70-75
研究生阶段的研究工作  75-76
致谢  76

基于DTW距离的两步式时间序列相似搜索

内容摘要

全文目录

相似论文