X軸に非線形の歪みがある2つの見積もりチャートの比較 - ページ 6

 

この問題は、DTW(例)を介してどのように解決されるのでしょうか。

  1. 極端な100本のバーと同じような状況を履歴から見つける必要があります。
  2. 使用可能な履歴は1 000 000バーです。
  3. まず、50小節のシーケンスを1,000,000個取り、DTWを通してパターンと比較した。
  4. 次に、55本の小節からなる100万本の配列を取り出し、テンプレートとDTWで比較しました。
  5. 今回は60小節です。
  6. .....
  7. 100気圧のとき。
  8. .....
  9. 300バーそして、ここでやめることができるのです。

合計で50,000,000回の比較をDTWアルゴリズムで行いましたが、その計算量はO(N^2)です。つまり、非常にざっくりと5 * 10^11(5000億)回の素数計算が行われたことになる。

今、新しいバーが 来た。また5000億回の計算をしたんだ。

一番外側の元素の200 000から、履歴で実行することにしました。大体、20万回5000億回ずつ計算すると1回になる。合計で10^17回の計算ですね。

仮にトリッキーな最適化があったとしても、2桁以上の利得は得られないでしょう。つまり、最大で10^15回の計算をしなければならないのです。

 
hrenfx:

この課題をDTWで解決する方法(例)。

この時点では、DTWをどのように適用するかよりも、DTWそのものに興味があるのですね。
 
hrenfx: この課題をDTWでどのように解決するか(例)。

もし差し支えなければ、この問題の解決策をコードで示してください。実用的な興味というより、スポーツ的な興味です。

 

まともな神経の持ち主なら、結果を待てないようなアルゴリズムを実装することはないだろう。

同じピアソンQCでも、DTWは計算量がO(N^2)なので不向きでしょう。しかし、複雑さO(N * log(N))のPearson QC計算の アルゴリズムの重要な最適 化があり、この問題を合理的な時間で解決できる可能性があるのです。本アルゴリズムの実装はCodebaseに掲載されています。提起された問題を解決するためには、同じアルゴリズムをZigZag変換されたZVRの集合に適用することが残されています。

 
hrenfx:

まともな神経の持ち主なら、結果を待てないようなアルゴリズムを実装することはないだろう。

同じピアソンQCでも、DTWは計算量がO(N^2)なので不向きでしょう。しかし、複雑さO(N * log(N))のPearson QC計算のアルゴリズムの重要な最適化があり、この問題を合理的な時間で解決できる可能性があるのです。本アルゴリズムの実装はCodebaseに掲載されています。提起された問題を解決するためには、同じアルゴリズムをZigZag変換されたZVRの集合に適用することが残されています。


まずは著者が抱えている問題とその答えを読み取るべきでしょう。
 
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: 信号の類似度は、行列の右下のセルの値で決まり、それが大きいほど、信号が異なることを意味する。
OK、ありがとうございます。非常にわかりやすく説明していただきました。もう一つ質問ですが、データを正規化したり、同じ順番に減らすことは必要でしょうか、結果に影響はありますか?
 
IgorM:
OK、ありがとうございます、非常に明確でした、もう一つ質問です:データを正規化または並べ替える必要性はありますか、それは結果に影響しますか?
dtw[n][m]はスケールに依存するので、一対の比較が多い場合はスケールアップして、できればセンタリングした方が良い。