动态时间弯曲距离推导
Deducing for dynamic time warping distance
-
摘要: 已有研究成果表明,在大多数时间序列处理应用领域中,动态时间弯曲是最为有效的相似度计算方法,但该方法计算时间复杂度较高,并且不满足距离三角不等式,无法进行快速推导.目前,动态时间弯曲优化方法集中在设计低计算复杂度的下界距离,以加快时间序列的比较,然而,这些下界距离同样不能推导,因此在相似度计算时都必须对时间序列数据进行逐一比较,导致I/O代价高,为此提出一种新颖的可推导动态时间弯曲近似距离以及相应的索引构建方法和相似时间序列查询算法.这是首次针对动态时间弯曲距离的推导问题的研究.大量实验结果表明,与现有方法相比,我们提出的方法在时间复杂度和I/O代价两方面都是高效的.Abstract: The current research achievements show that the dynamic time warping (DTW) is the best measure in most area of time series similarity measurements. However, the high time complexity for calculating DTW distance directly, and the fact that DTW does not satisfy the triangle inequality, render it impossible to deduce TWD quickly. Nowadays DTW optimizing methods are mainly devoted to designing low time complexity DTW low bound distances with low time complexity to accelerate time series comparison. Unfortunately, these DTW low bound distances cannot be deduced, either. Therefore, it must be compared one by one to compute time series similarity, which has high I/O cost. A novel educible DTW low bound distance is thus proposed, along with a corresponding index building method and a similar time series query algorithm. It is the first research on the DTW deducing problem. Extended experiment results show that compared to current technologies, the proposed method is efficient in both time complexity and I/O cost.
下载: