Q&A
詳細な回答ありがとうございます
追記:python tutorすごいですね！大変勉強になりました
DTW(Dynamic Time Warping)の実装についての質問なのですが、以下の実装例を自分で解釈していたのですが
python
1def dtw(vec1, vec2): //vec1とvec2は長さの異なる整数型配列 2 import numpy as np 3 d = np.zeros([len(vec1)+1, len(vec2)+1]) 4 d[:] = np.inf 5 d[0, 0] = 0 6 for i in range(1, d.shape[0]): 7 for j in range(1, d.shape[1]): 8 cost = abs(vec1[i-1]-vec2[j-1]) 9 d[i, j] = cost + min(d[i-1, j], 10 d[i, j-1], 11 d[i-1, j-1]) 12 return d[-1][-1]
まずpythonの文法としてnp.infが何をしているのかが疑問です。d[:]には何が入っているのでしょうか
次にアルゴリズムについて単にcostの中身をd[i,j]に入れればいいのではと思ったのですがmin()を行うことの意味がよくわかりません。
どなたかご教授願えればと思います。
http://sinhrks.hatenablog.com/entry/2014/11/14/232603
https://en.wikipedia.org/wiki/Dynamic_time_warping 英Wiki
などを参考にしています。
回答2件
0
まずpythonの文法としてnp.infが何をしているのかが疑問です。d[:]には何が入っているのでしょうか
d = np.array([1,2,3])
d[:] = np.inf
で確かめてみましょう。
次にアルゴリズムについて単にcostの中身をd[i,j]に入れればいいのではと思ったのですがmin()を行うことの意味がよくわかりません。
DTWについて。
始点と終点をつなぐ経路のうち、累積コストが最小なパスを見つけているだけです。
５ｘ５マスくらいの単純な例を作って手計算をしてみれば何をしているのかすぐ理解できるはずです。
投稿2016/11/04 14:18
総合スコア1582
0
ベストアンサー
np.inf は Numpy で定義された値で infinity の略です。
d[:] = np.inf も Numpy のイデオムで、行列 d の要素を全て np.inf で埋める初期化処理です。
min の中では 左・上・左上の中から小さいものを選んでいます。
左、上の添字は -1 ですが、負の値の添字は言語・実装により様々。
Pythonでも末端からの要素と、意図しない要素を参照してしまう為、境界チェックが必要になります。
そこで len(vec1) x len(vec2) に対して +1 のサイズの行列を準備して、
初期化の際に上・左の端を inf で埋めて、左上を 0 とすることで、
境界チェックのコードを省けるように工夫しています。
このような inf の使われ方についてですが、アルゴリズムに置いては 番兵と呼ばれ、
inf に限らず実際のデータ中には現れない値が、境界を表す値として仮置きされます。
| 0 | inf | inf | inf |
| inf | ... | ... | ... |
| inf | ... | ... | ... |
i=1, j=1 の時に min に渡す 左・上・左上の値は (inf, inf, 0)
numpy のコードでは、全ての要素を inf で埋めて、左上の 0 を入れていますが、
Wiki の実装が想定する初期化後の行列は上記のような感じです。
ここで ... と表記した部分のデータは左上から順に埋まっていく為、
未定義のまま参照されることはないので、この時点ではなんでも構いません。
First を押した後 Foward を連打してステップ実行してみて下さい。
ここでは、inf は 仮に 適当なとにかく大きな値としています。
投稿2016/11/04 13:55
総合スコア8664
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。