节点文献
基于约束动态时间弯曲距离的时间序列相似性匹配
The Similarity Measurement Based on Constraint Dynamic Time Warping
【作者】 高成锴；
【导师】 冯林；
【作者基本信息】 大连理工大学 ， 计算机应用技术， 2010， 硕士
【摘要】 时间序列相似性匹配是数据挖掘中的重要工具。本文首先对不同时间序列的处理技术进行详细的概括,在前人基础上分析现有挖掘工具；之后说明其中存在的问题,包括时间序列度量和数据流处理,并辨析各个方法的优缺点。最终提出了针对动态时间弯曲的过匹配问题,在对这个问题进行详细分析的基础上提出应用于不同领域的两种算法,即Flex Dynamic Time Warping (FDTW)和Lining Bound Mine (LBM)算法,通过给出的证明和实验验证算法的准确性。FDTW是一种全新的度量方式,主要解决DTW算法存在的过匹配问题,它使用三个迭代矩阵对路径选择严格限制,若超出限制范围则无法成为路径的选择点。文章不仅给出算法,并且证明算法的正确性。LBM算法是应用在时间序列数据流中支持弹性形变的子序列匹配算法。由于数据流相对于传统静态时间序列的特殊性,无法支持重复性查找,所以数据流子序列算法必须通过一次扫描找到区域最优解。前人曾提出spring算法,但spring算法存在冗余计算以及过匹配现象。LBM算法使用全局约束和判断减少过匹配以及冗余计算,经过实验验证,相对于spring算法不仅速度得到提升,并且不会出现过匹配现象。
【Abstract】 Time series similarity matching is an important tool in data mining. Firstly, time series of different treatment technologies detailed summary of the basis of the previous analysis of existing mining tools; after the description of the existing problems, including time-series measurements and data stream processing, and Analysis of advantages and disadvantages of each method. Eventually made over for dynamic time warping matching problem, a detailed analysis of this issue based on the proposed application of the two algorithms in different fields, that Flex Dynamic Time Warping (FDTW) and Lining Bound Mine (LBM) algorithm, algorithm proof and experimental validation of their accuracy.FDTW DTW algorithm is mainly to solve the existing problems have made matching metric, which uses three iterations of the routing matrices strictly limited, if out of the path matching region cannot be the choice of points.LBM algorithm is applied in the time series data stream support for elastic deformation of the sub-sequence matching algorithm. As opposed to traditional static data flow time series are unique, cannot support the repetitive look, so the data flow sequence algorithm must be found through a scan area optimal solution. Algorithms have been proposed previous spring, but the existence of redundant computing algorithm and the spring had mismatch. LBM algorithm uses global constraints and determine the reduction of redundant computing over match and, after the experiment, the speed relative to the spring algorithm not only be enhanced, and will not match the phenomenon occurred.