The Move-Split-Merge Metric for Time Series
The Move-Split-Merge Metric for Time Series
复制标题
DOI：
10.1109/tkde.2012.88
复制
发表时间：
2013-06
影响因子：
8.9
通讯作者：
Alexandra Stefan;V. Athitsos;Gautam Das
中科院分区：
文献类型：
--
作者：
Alexandra Stefan;V. Athitsos;Gautam Das
提出了一种新的时间序列度量，称为移动-分裂-合并（MSM）。此指标使用三个基本操作作为构建块：移动、拆分和合并，可以按顺序应用这些操作将任何时间序列转换为任何其他时间序列。Move操作更改单个元素的值，Split操作将单个元素转换为两个连续的元素，Merge操作将两个连续的元素合并为一个。每个操作都有一个相关的成本，两个时间序列之间的MSM距离被定义为将第一个时间序列转换为第二个时间序列的最便宜的操作序列的成本。一个有效的，二次时间算法计算MSM距离。与动态时间规整（DTW）距离相比，MSM具有度量的期望属性，并且与具有真实的惩罚的编辑距离（ERP）度量相比，MSM对于原点的选择是不变的。同时，在公开时间序列数据集上的实验表明，MSM是一种有意义的距离度量，与DTW和ERP相比，它通常会导致更低的最近邻分类错误率。
A novel metric for time series, called Move-Split-Merge (MSM), is proposed. This metric uses as building blocks three fundamental operations: Move, Split, and Merge, which can be applied in sequence to transform any time series into any other time series. A Move operation changes the value of a single element, a Split operation converts a single element into two consecutive elements, and a Merge operation merges two consecutive elements into one. Each operation has an associated cost, and the MSM distance between two time series is defined to be the cost of the cheapest sequence of operations that transforms the first time series into the second one. An efficient, quadratic-time algorithm is provided for computing the MSM distance. MSM has the desirable properties of being metric, in contrast to the Dynamic Time Warping (DTW) distance, and invariant to the choice of origin, in contrast to the Edit Distance with Real Penalty (ERP) metric. At the same time, experiments with public time series data sets demonstrate that MSM is a meaningful distance measure, that oftentimes leads to lower nearest neighbor classification error rate compared to DTW and ERP.