炼数成金 门户 商业智能 机器学习 查看内容

【时间序列】DTW算法详解

2020-12-15 14:19| 发布者: 炼数成金_小数| 查看: 73890| 评论: 0|原作者: 追光者|来自: AI蜗牛车

摘要: 在时间序列数据中,一个常见的任务是比较两个序列的相似度,作为分类或聚类任务的基础。那么,时间序列的相似度应该如何计算呢?经典的时间序列相似性度量方法总体被分为两 类: 锁步度量(lock-step measures) 和弹性 ...
1.DTW
1.1 时序相似度
在时间序列数据中,一个常见的任务是比较两个序列的相似度,作为分类或聚类任务的基础。那么,时间序列的相似度应该如何计算呢?

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

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

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





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

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

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

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


约束条件


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

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的算法进行优化,不然时间复杂度很高

参考
《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
《时间序列数据挖掘的相似性度量综述》 ——陈海燕, 刘晨晖,孙 博
《时间序列数据挖掘中的动态时间弯曲研究综述》——李海林,梁叶,王少春

声明:文章收集于网络,版权归原作者所有,为传播信息而发,如有侵权,请联系小编删除,谢谢!

欢迎加入本站公开兴趣群
商业智能与数据分析群
兴趣范围包括:各种让数据产生价值的办法,实际应用案例分享与讨论,分析工具,ETL工具,数据仓库,数据挖掘工具,报表系统等全方位知识
QQ群:81035754

鲜花

握手

雷人

路过

鸡蛋

相关阅读

最新评论

热门频道

  • 大数据
  • 商业智能
  • 量化投资
  • 科学探索
  • 创业

即将开课

 

GMT+8, 2021-4-18 09:43 , Processed in 0.399589 second(s), 24 queries .