论文一种基于动态时间弯曲距离的快速子序列匹配算法是关于对写作弯曲论文范文与课题研究的大学硕士、相关本科毕业论文弯曲论文开题报告范文和相关文献综述及职称论文参考文献资料下载有帮助。
摘 要： 动态时间弯曲距离在用于计算时间序列间的距离时是极其耗费时间的,尤其是处理较大规模的时间序列数据库中的子序列匹配问题时,时间消耗更是难以忍受.该文提出一种新的低边界距离,能够快速滤掉不满足结果条件的时间序列,以提高查询速度,并证明该低边界距离不会丢弃真实的结果.一种基于水平边界区域的索引技术被用于进一步提高查询效率.分别以真实数据集和人造数据集作为实验数据来测试该文所提出的算法的性能,结果表明该算法在数据库规模上和序列长度上都有良好的健壮性.
关键词： 时间弯曲距离； 低边界距离； 范围查询； 数据库
中图分类号： TN911?34； TP311.13 文献标识码： A 文章编号： 1004?373X（2017）06?0025?06
Abstract： It is very time?consuming to calculate the distance between time sequences by using dynamic time warping distance, especially when the subsequence matching in large time?series databases is concerned. A new method of lower bound distance is presented in this paper, which can quickly filter the time sequences which are unable to satiy the result condition, so as to improve the query speed. It is proven that the true results can not be lost if the method is used. To further increase the query speed, a technique for building an index based on skyline bounding region is also proposed. Some experiments with the data from real data set and synthetic data set were carried out to verify the performance of the methods. The results reveal that the method has robostness in the scale of database and sequence length.
Keywords： time warping distance； lower bounding distance； range query； database
0 引 言
时间序列是由一些在特定时间点上采样得到的实数组成.在现实世界中,有很多时间序列的例子,如股票的、天气的变化情况、商品的销售记录.时间序列间的相似性查询就是从时间序列数据库中发现与给定查询序列有相似的变化模式的序列,该操作在很多新的数据库应用领域（数据挖掘、数据仓库）中是很重要的,它能用于预测未来发展趋势、识别新的模式、发现规则[1?3].例如,可能需要找出一天的股票中的特定模式来预测未来发展趋势；也可能需要找出历史上与今天有相似磁暴模式的日子来预测地球磁场的变化.
通常,时间序列相似性查询可以分为两类：全序列匹配和子序列匹配.全序列匹配是给定一条查询序列,在数据库中找出与其相似的完整数据序列,而子序列匹配是在数据库中找出与其相似的部分数据序列,即子序列.全序列匹配又可以看成是子序列匹配的一种特殊情况[3?5],故子序列匹配比全序列匹配有更广泛的应用.本文重点研究子序列匹配.
子序列匹配就是在给定一变长时间序列数据库、一长度为N的查询序列Q和阈值ε的情况下,从数据库中找出所有与查询序列相似的子序列（即子序列与Q之间的距离小于ε）,并返回这些结果.
1 子序列匹配
在介紹子序列匹配前,先说明本文所用到的符号以及它们的定义,见表1.
1.1 动态时间弯曲距离
动态时间弯曲（Dynamic Time Warping,DTW）距离不要求时间序列中的元素与元素之间进行一一对应匹配,允许序列中的元素自我复制后再进行对齐匹配.当时间序列沿时间轴发生弯曲时,可以在弯曲部分进行自我复制,使两条时间序列之间的相似波形进行对齐匹配.DTW距离很好地解决了时间序列发生时间轴伸缩和弯曲后的相似性度量问题.例如,给定两条序列P等于<4,5,6,8,9>和Q等于<3,4, 7,8,9,7>,可以分别将这两条序列拉伸为P′等于<4,5,6,6,8,9,9>和Q′等于<3,3,4,7,8,9,7>,通过计算P′和Q′间的距离来衡量P和Q间的距离.在这种情况下,就称序列P和Q之间相互“调整”.P和Q之间“调整”的路径称为弯曲路径.在两条序列间存在多条弯曲路径,可称根据最小弯曲代价的路径计算的距离为动态时间弯曲距离.
表1 符号及其定义
由于存在多条弯曲路径,找到最小弯曲代价的路径是极其耗费时间的.为了解决这一问题文献[6]介绍了一种基于累积距离矩阵的动态规划方法来计算两条时间序列之间的DTW距离,时间复杂度为O（MN）.累积距离矩阵实际上是一个递推关系.给定两条时间序列P等于,Q等于
[DDTW（P,Q）等于f（M,N）f（i,j）等于d（pi,qj）+minf（i,j-1）f（i-1,j）f（i-1,j-1）f（0,0）等于0, f（i,0）等于f（0,j）等于∞i等于1,2,等,M； j等于1,2,等,N] （1）
总结:该文是关于弯曲论文范文，为你的论文写作提供相关论文资料参考。
参考文献：
1、 一千年·时间和距离·吴永平的前世今生 我对吴永平越是熟识，就越是觉得他好象是由两个形象重合而成。一个吴永平是1987到1991年在江西景德镇陶瓷学院学习雕塑本科后，又于2001到20。
2、 一种面向动态异构多处理器的任务调度算法 摘 要：提出了基于遗传算法的面向动态异构多处理器的调度算法（Heterogeneous Scheduling Genetic Algorithm。
3、 一种电能计量设备运维作业动态优化模型算法 摘 要：针对电网企业传统模式下运维作业所存在的任务分配不科学、路径规划不合理和无法实时响应动态需求等问题，提出了一种新的动态优化模型及求解算法 。
4、 种时间 “我有一个美丽的愿望，长大以后能播种太阳……”作业还没写完，时针已经指向了10点我揉揉酸胀的眼睛，看着窗外漆黑的夜空，突然想起了《种太阳》这首歌。
5、 一种质量门的动态控制方法 摘要：精益生产是继丰田生产模式后又一对制造业产生深远影响的管理方式，该生产模式的核心思想是提高质量，消除浪费。由于传统质量门缺乏整体性和系统性，。
6、 坚持全面严治党强化运用监督执纪四种形态 总书记在党的十九大报告指出：“勇于自我革命，从严管党治党，是我们党最鲜明的品格”“坚持开展批评和自我批评，坚持惩前毖后、治病救人，运。