两张在X轴上有非线性扭曲的报价图的比较 - 页 6

新评论
 

这个问题是如何通过DTW（例子）来解决的。

  1. 我们需要在历史上找到类似于极端100条的情况。
  2. 可用的历史记录是1 000 000条。
  3. 首先，我们取了1,000,000个50条的序列，通过DTW与模式进行比较。
  4. 然后，我们又取了1,000,000个55条的序列，通过DTW与模板进行比较。
  5. 这一次是60条。
  6. .....
  7. 在100巴时。
  8. .....
  9. 300条。而这是我们可以停止的地方。

我们总共使用DTW算法做了50,000,000次比较，其复杂度为O(N^2)。这大约是进行了5*10^11（5000亿）次的基本计算操作。

现在，新的一栏 已经到来--我们又做了5000亿次的计算。

决定在历史上运行，从最外层的20万个元素开始。粗略地说，每个人需要200,000次5000亿次的计算才能完成一次运行。这总共是10^17次的计算。

即使有一个棘手的优化，也不会产生超过两个数量级的收益。也就是说，它最多要进行10^15次计算。

 
hrenfx:

如何通过DTW解决这个任务（例子）。

你看，在这一点上，我们对DTW本身比对如何应用它更感兴趣。
 
hrenfx: 这个任务是如何用DTW解决的（例子）。

如果你不介意的话，请在代码中显示这个问题的解决方案，这并不是什么实际的兴趣，而是体育方面的兴趣。

 

没有人在头脑正常的情况下会承诺实施一种算法，其结果根本无法等待。

同样的Pearson QC也不适合，DTW也不适合，因为其计算复杂度也是O(N^2)。但皮尔逊QC计算 有一个重要的算法优化，其复杂度为O(N * log(N))，可以在合理时间内解决这个问题。这个算法的实现已经发布在Codebase上。为了解决所提出的问题，仍然需要将同样的算法应用于ZigZag-transformed ZVRs的集合。

 
hrenfx:

没有人在头脑正常的情况下会承诺实施一种算法，其结果根本无法等待。

同样的Pearson QC也不适合，DTW也不适合，因为其计算复杂度也是O(N^2)。但皮尔逊QC计算有一个重要的算法优化，其复杂度为O(N * log(N))，可以在合理时间内解决这个问题。这个算法的实现已经发布在Codebase上。为了解决所提出的问题，仍然需要将同样的算法应用于ZigZag-transformed ZVRs的集合。


你应该首先阅读作者所面临的问题和他的答案。
 
Integer:


我试过了。我也不明白如何使用它。输出应该是一个转换路径或转换后的数据。

该算法的输出是一个 "累积成本矩阵"（而不仅仅是图中所示的局部距离矩阵），该方法返回右下角单元格的值（根据结构，它是整个矩阵的最大值）。现在要找到路径，我们只需要从单元格（n,m）向单元格（1,1）移动，每次都选择价值最低的选项。

1: path[] <- new array
2: i =rows(dtw)
3: j =columns(dtw)
4: while(i>1) & (j>1)do
5:    if (i == 1) then
6:       j = j-1
7:    else if (j == 1) then
8:       i = i-1
9:    else
10:     if dtw(i-1;j) == min{dtw(i-1;j); dtw(i;j-1); dtw(i-1; j-1)} then 
11:        i = i-1
12:     else if dtw(i;j-1) == min{dtw(i-1;j); dtw(i;j-1); dtw(i-1;j-1)} then
13:        j = j-1
14:     else
15:     i = i-1; j = j-1
16:     end if
17:   path:add(i;j)
18:   end if
19: end while
20: return path
 
由此产生的路径阵列包含了将一个信号转换为另一个信号的最佳路径。这可以从任何一个方向进行。
 
信号的相似程度由矩阵的右下角单元格的值决定，它越大，信号就越不同。
 
alsu: 信号的相似程度由矩阵的右下角单元格的值决定，它越大，信号就越不同。
好的，谢谢你，你已经解释得很清楚了，还有一个问题：是否有必要将数据归一化或减少到相同的顺序，是否会影响结果？
 
IgorM:
好的，谢谢你，这很清楚，还有一个问题：是否需要对数据进行规范化或重新排序，是否会影响结果？
dtw[n][m]取决于规模，所以如果有很多配对比较，我们应该把它的规模扩大，最好是居中。
123456789101112
新评论