Computing an accurate mean of a set of time series is a critical task in applications like nearest-neighbor classification and clustering of time series. While there are many distance functions for time series, the most popular distance function used for the computation of time series means is the non-metric dynamic time warping (DTW) distance. A recent algorithm for the exact computation of a DTW-Mean has a running time of $\mathcal{O}(n^{2k+1}2^kk)$, where $k$ denotes the number of time series and $n$ their maximum length. In this paper, we study the mean problem for the move-split-merge (MSM) metric that not only offers high practical accuracy for time series classification but also carries of the advantages of the metric properties that enable further diverse applications. The main contribution of this paper is an exact and efficient algorithm for the MSM-Mean problem of time series. The running time of our algorithm is $\mathcal{O}(n^{k+3}2^k k^3 )$, and thus better than the previous DTW-based algorithm. The results of an experimental comparison confirm the running time superiority of our algorithm in comparison to the DTW-Mean competitor. Moreover, we introduce a heuristic to improve the running time significantly without sacrificing much accuracy.
翻译:计算一套时间序列的准确平均值是近邻分类和时间序列群集等应用中的一项关键任务。 虽然时间序列有许多远程功能, 但计算时间序列手段最受欢迎的远程功能是非计量动态时间扭曲( DTW) 距离。 DTW- MEan 精确计算的最新算法运行时间为$\mathcal{O}(n ⁇ 2k+1}2kkkk) 美元, 其中美元表示时间序列的数量和时间序列的最大长度。 在本文中, 我们研究移动- split- merge (MSMM) 参数的平均值问题, 它不仅为时间序列分类提供高实用的准确性, 而且还包含能够进一步多样化应用的参数属性的优点。 本文的主要贡献是时间序列 MSM- Mean 的精确有效的算法。 我们算法的运行时间是 $\\ mathcal{ (nQk+3} 2 k} k}3 $, 因此, 我们研究移动- smerge (MSM) 的精确度衡量结果比我们之前的实验性矩阵的更高时间 。