【时间序列】DTW算法详解

作者 | 追光者

研究 | 机器学习与时间序列

出品 | AI蜗牛车

1.DTW

1.1 时序相似度

在时间序列数据中，一个常见的任务是比较两个序列的相似度，作为分类或聚类任务的基础。那么，时间序列的相似度应该如何计算呢？

“

经典的时间序列相似性度量方法总体被分为两 类: 锁步度量(lock-step measures) 和弹性度量(elastic measures) . 锁步度量是时间序列进行 “一对一”的比 较; 弹性度量允许时间序列进行 “一对多”的比较.

——《时间序列数据挖掘的相似性度量综述》

”

最简单的相似度计算方法可能是计算两个时间序列的欧氏距离。欧氏距离属于锁步度量

假设有两个时间序列，Q和C，如果直接用欧氏距离计算相似度的话，如果存在时间步不对齐，序列长短不一等问题…

如上图1所示，如果序列长短不一，或时间步不对齐的时候，欧氏距离是无法有效计算两个时间序列的距离，特别是在峰值的时候。

图2则是DTW算法，首先将其中一个序列进行线性放缩进行某种“扭曲”操作，以达到更好的对齐效果，可以存在一对多mapping的情况，适用于复杂时间序列，属于弹性度量

1.2 DTW算法

动态时间规整在60年代由日本学者Itakura提出，用于衡量两个长度不同的时间序列的相似度。把未知量伸长或缩短(压扩)，直到与参考模板的长度一致，在这一过程中，未知序列会产生扭曲或弯折，以便其特征量与标准模式对应

首先假设有两条序列Q和C，他们的长度分别是n和m

用一个
矩阵来对比两个序列，warping路径会穿越这个矩阵，warping路径的第k个元素表示为
,横纵代表的是两个序列对齐的点

约束条件

1）边界条件：
和
，表示两条序列首尾必须匹配，各部分的先后次序匹配。

2）连续性：   如果
且
，则必须满足
。这条约束表示在匹配过程中多对一和一对多的情况只能匹配周围一个时间步的的情况，也就是不可能跨过某个点去匹配，只能和自己相邻的点对齐。这样可以保证Q和C中的每个坐标都在wraping路径中出现。

3）单调性： 如果
，且
，则必须满足
，表示warping路径一定是随时间单调递增的。

满足以上约束条件的warping路径有很多，所以问题的本质是最优化问题——找出最优warping路径，数学语言表示为：

解法思路是通过动态规划算法，数学语言描述为：

时间复杂度

单调性与连续性约束直观上表示为如下三种可能

1.3 优化方法

1.3.1 使用平方距离

原始DTW计算距离使用的是平方根计算，但是在排序任务中，平方或平方根不会对结果有影响，但是平方根计算资源消耗大，所以可以改为平方距离

1.3.2 Lower Bounding

顾名思义，这个优化方法的主要思想是先通过计算LB（lower bounding）处理掉不可能是最有匹配序列的序列，计算LB的主要有LB_Kim 和 LB_keogh等方法，这里只介绍一下LB_keogh，感兴趣可自行查阅资料。

首先上公式

如上图所示，首先找到找到序列的上包络线U和下包络线L，计算候选序列超出上下包络线区域的部分之和作为下界。

1.3.3 Early Abandoning

从 K=0 开始逐步计算DTW并且和K后面的LB_keogh部分累加，判断距离是否大于目前最好的匹配序列，在这个过程中，一旦发现大于当前最好匹配得距离，则放弃该序列停止DTW

1.3.4 Reordering Early Abandoning

如下图所示，如果要早停的话，从序列的起点按顺序计算不一定可以得到最优的结果。所以可以对序列进行排序先。首先对序列进行z归一化，

除了以上优化方法，还有计算卷LB_Keogh时转换Query/Data，级联下界（Cascading Lower Bounds）等优化方法。

1.4 总结

优点：

1.支持非等长序列

2.支持有断点序列

缺点：

1.不是一个严格的距离度量，因为它不符合三角形不等式，在一个度量空间中，距离必须符合三角形不等式。

2.对噪音敏感，所以需要对DTW的算法进行优化，不然时间复杂度很高

参考

1. 《Searching and Mining Trillions of Time Series Subsequences under Dynamic Time Warping 》——Thanawin Rakthanmanon, Bilson Campana, Abdullah Mueen, Gustavo Batista2 , Brandon Westover1 , Qiang Zhu, Jesin Zakaria, Eamonn Keogh
2. 《时间序列数据挖掘的相似性度量综述》 ——陈海燕， 刘晨晖，孙 博
3. 《时间序列数据挖掘中的动态时间弯曲研究综述》——李海林，梁叶，王少春

更多精彩内容（请点击图片进行阅读）

公众号：AI蜗牛车

保持谦逊、保持自律、保持进步

个人微信

备注：昵称+学校/公司+方向

如果没有备注不拉群！

拉你进AI蜗牛车交流群