基于时间规整算法下的搜索挖掘大数量级的时间子序列 职业生涯

信息发布员 6月前 91

论文:Searching and Mining Trillions of Time Series Subsequences under Dynamic Time Warping

作者:Thanawin Rakthanmanon, University of California Riverside

1. 引言

本文提出解决时间序列问题中子序列相似度搜索里面的计算遇到的瓶颈,尚未有任何时间序列的子序列搜索研究能够拓展到trillion级别的数据。并且传统的time series子序列问题都是用较为易于计算的ED欧式距离算法来检测相似度,而本文则提出在trillion级别的数据中,使用DTW算法实际上要比简单的ED欧氏距离算法来的要快速。

作者提出了三个假设,第一,时间序列子序列必须进行normalization,要规范且统一;第二,DTW算法是在执行子序列搜索任务上最好的方法;第三,任意长度的搜索没办法进行标注。

3.背景知识

作者首先引入了三个重要的定义,分别是时间序列,时间序列子序列,和欧式距离在搜索上的定义。这里作者也进一步介绍了什么是DTW,他指出ED距离是一对一的,可以看作是DTW的一种特殊情况,在DTW里面我们允许一对多的对应。

4.算法

首先讨论的是已知优化算法中基于ED、DTW的顺序搜索:

使用平方距离、lower bounding、Early Abandoning

接着提出了最新优化算法:The UCR Suite : Early Abandoning Z-Normalization Reordering Early Abandoning、 Reversing the Query/Data Role in LB_keogh、Cascading Lower Bounds(这部分非常智慧,作者使用了一种由宽到松的方式渐进地改变LB,很经济)

5、6 总结

DWT可以应用于脑电图数据、DNA数据、手势识别数据、以及帮现有的data mining任务进行加速,速度快而且可以解决到trillion级别的数据。作者解释了自己的DTW模型比别人的ED模型还快的原因。

启发:动态规划这样看似复杂的算法,只要能进行很好的加速手段,仍然是能让他超过当前很多最优模型的。复杂的问题也需要从细节入手优化。



少客联盟- 版权声明 1、本主题所有言论和图片纯属会员个人意见,与少客联盟立场无关。
2、本站所有主题由该帖子作者发表,该帖子作者信息发布员少客联盟享有帖子相关版权。
3、少客联盟管理员和版主有权不事先通知发贴者而删除本文。
4、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者信息发布员少客联盟的同意。
5、帖子作者须承担一切因本文发表而直接或间接导致的民事或刑事法律责任。
6、本帖部分内容转载自其它媒体,但并不代表本站赞同其观点和对其真实性负责。
7、如本帖侵犯到任何版权问题,请立即告知本站,本站将及时予与删除并致以最深的歉意。
8、官方反馈邮箱:chinasuc@chinasuc.cn


上一篇:疫情期间“在家学”,视界云全面升级在线教育云服务解决方案
下一篇:DTW算法初步理解
人生的价值,并不是用时间,而是用深度去衡量的。
最新回复 (0)
    • 少客联盟
      2
        登录 注册 QQ登录(停用)
返回