动态时间弯曲距离 dynamic time warping

1.What is 动态时间弯曲距离

 
 

在日常的生活中我们最经常使用的距离毫无疑问应该是欧式距离,但是对于一些特殊情况,欧氏距离存在着其很明显的缺陷,比如说时间序列,举个比较简单的例子,序列A:1,1,1,10,2,3,序列B:1,1,1,2,10,3,如果用欧氏距离,也就是distance[i][j]=(b[j]-a[i])*(b[j]-a[i])来计算的话,总的距离和应该是128,应该说这个距离是非常大的,而实际上这个序列的图像是十分相似的,这种情况下就有人开始考虑寻找新的时间序列距离的计算方法,然后提出了DTW算法,这种方法在语音识别,机器学习方便有着很重要的作用。

这个算法是基于动态规划(DP)的思想,解决了发音长短不一的模板匹配问题,简单来说,就是通过构建一个邻接矩阵,寻找最短路径和。

还以上面的2个序列作为例子,A中的10和B中的2对应以及A中的2和B中的10对应的时候,distance[3]以及distance[4]肯定是非常大的,这就直接导致了最后距离和的膨胀,这种时候,我们需要来调整下时间序列,如果我们让A中的10和B中的10 对应 ,A中的1和B中的2对应,那么最后的距离和就将大大缩短,这种方式可以看做是一种时间扭曲,看到这里的时候,我相信应该会有人提出来,为什么不能使用A中的2与B中的2对应的问题,那样的话距离和肯定是0了啊,距离应该是最小的吧,但这种情况是不允许的,因为A中的10是发生在2的前面,而B中的2则发生在10的前面,如果对应方式交叉的话会导致时间上的混乱,不符合因果关系。

接下来,以output[6][6](所有的记录下标从1开始,开始的时候全部置0)记录A,B之间的DTW距离,简单的介绍一下具体的算法,这个算法其实就是一个简单的DP,状态转移公式是output[i][j]=Min(Min(output[i-1][j],output[i][j-1]),output[i-1][j-1])+distance[i][j];最后得到的output[5][5]就是我们所需要的DTW距离.

2.动态时间弯曲距离程序

Matlab  C++

3.在金融工程中的应用

根据动态时间距离方法预测市场走势 理论基础:历史重复,使用模式匹配方法,寻找历史中与现在最接近的时段!!

(1)基于日线–动态时间距离方法预测市场走势(每日自动更新)

(2)基于日线列出最相似T0p5–动态时间距离方法预测市场走势(每日自动发送)

(3)基于交易量与价格等等。。。。

6 thoughts on “动态时间弯曲距离 dynamic time warping

  1. Pingback: [repost ]【机器学习中的相似性度量】 » New IT Farmer

  2. sanshui

    自己把这个实现了一下,但是出现一个问题。
    比如要查找和最近30天相似的历史,那我就将历史日数据从2005年开始一天一天的以30天为窗口不断滚动计算DTW distance,然后按照这个结果来排序。此时问题就来了,由于我是一天一天的滚动计算DTW distance,所以最相似的第2、第3、第4其实只是把最相似的第1往后顺延一两天,但实质上还是同一时间段,怎样避免这个问题呢?

  3. sanshui

    我自己用dtw以2012年全年的数据为测试样本,2005年到2011年的数据为历史数据,搜索出了相似的历史时段,但是用历史数据作出的预测基本就是个50%的准确率,不知道您2012年怎么会有那么高的准确率

  4. Ariszheng Post author

    2012年还是不错的,正确率仅为涨跌,比较简单的测算。
    今天正确率较低不少!

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>