动态时间规整聚类

机器算法验证 时间序列 聚类
2022-01-19 09:15:27

使用动态时间规整 (DTW) 执行时间序列聚类的方法是什么?

我已经阅读了 DTW 作为一种在两个时间序列之间找到相似性的方法,同时它们可以在时间上移动。我可以将此方法用作聚类算法(如 k-means)的相似性度量吗?

4个回答

是的,您可以使用DTW方法对时间序列进行分类和聚类我整理了以下资源,这些资源都集中在这个主题上(我最近回答了一个类似的问题,但不在这个网站上,所以为了大家方便,我在这里复制内容):

不要时间序列使用 k-means。

DTW没有被平均最小化;k-means 可能不会收敛,即使收敛也不会产生很好的结果。均值是坐标上的最小二乘估计量。它最小化方差,而不是任意距离,k-means 旨在最小化方差,而不是任意距离

假设您有两个时间序列。两个正弦波,频率相同,采样周期较长;但它们被抵消了。由于 DTW 会进行时间扭曲,它可以对齐它们,使它们完美匹配,除了开头和结尾。DTW 将为这两个系列分配一个相当小的距离。但是,如果您计算两个系列的平均值,它将是一个平坦的 0 - 它们相互抵消。均值不做动态时间扭曲,并失去了 DTW 获得的所有价值。在这样的数据上,k-means 可能无法收敛,结果将毫无意义。K-means 真的应该只与方差(= 平方欧几里得)或某些等效的情况(如余弦,在 L2 归一化数据上,其中余弦相似度π欧几里得距离的平方相同)2

相反,使用 DTW 计算距离矩阵,然后运行层次聚类,例如单链接。与 k-means 相比,序列甚至可能有不同的长度。

Petitjean 等人最近提出了一种 DTW 重心平均 (DBA) 方法。平均时间序列。另一篇论文中,他们从经验和理论上证明了如何使用 k-means 对时间序列进行聚类。作者在 GitHub 上提供了一个实现(代码链接)。

1 F. Petitjean、G. Forestier、GI Webb、AE Nicholson、Y. Chen 和 E. Keogh,“时间序列的动态时间扭曲平均可以实现更快、更准确的分类”,2014 年 IEEE 数据挖掘国际会议,深圳,2014 年.

2 F. Petitjean, P. Gançarski,通过平均总结一组时间序列:从 Steiner 序列到紧凑多重对齐,理论计算机科学,第 414 卷,第 1 期,2012

动态时间扭曲比较实现的数据点,这可能会或可能不会起作用。更严格的方法是通过称为望远镜距离的度量来比较时间序列的分布

这个指标很酷的一点是,经验计算是通过拟合一系列二元分类器(如 SVM)来完成的。

有关简要说明,请参阅

对于聚类时间序列,它已被证明优于 DTW;见原始论文[1]中的表1。

[1] Ryabko, D. 和 Mary, J. (2013)。时间序列分布之间基于二元分类的度量及其在统计和学习问题中的应用。机器学习研究杂志,14(1),2837-2856。