ダイナミックタイム規則(Dynamic Time Warping)

4055 ワード
コード アルゴリズム matlab マシン学習
本論文の知識は簡単にDTWアルゴリズムの目的と実現を紹介する.具体的なDTWは文献を参照することができます.
離散シーケンスの一致計量方法:動的時間規則(DTW) http://blog.csdn.net/liyuefeilong/article/details/45748399
ダイナミック時間正規/仕様/曲げ(Dynamic time warping,DTW)  http://www.cnblogs.com/flypiggy/p/3603192.html
DTWは何をするものですか?
    動的時間規則アルゴリズムは、不思議なことに、同じタイプのものを表す二つの長いシーケンスを時間的に「揃える」ことです.例えば、DTWで一番よく使われているところは、音声認識の中で、同じ文字は、人によって発音されています.長さは間違いなく違っています.音声を記録した後、信号はきっと似ています.時間的にはあまり整然としていません.したがって、それらの間の誤差が最小になるように、一つの関数で長さを伸ばす必要があります.
     またスポーツキャプチャーを見てみます.例えば、今は速いボクシングの動作があります.また、タグをつけていない動作があります.ボクシングの動作かどうかを判断したいです.このタグを付けていない動作と既知のボクシングの動作の類似度を計算します.しかし、彼らの2つの動作の長さは違っています.例えば、1つは100フレーム、1つは200フレームです.このように直接各フレームを比較して、後ろに計算すると、誤差が大きいと思います.このようにして、二つの運動の類似度を計算し、閾値を設定して、未知の動作を「ボクシング」のラベルで満たします.
DTWはどう計算しますか
DTW動時間規則化アルゴリズムの簡単なステップをまとめます.
1.まず必ず二つ以上のシーケンスが知られていますが、二つの比較です.だから、私達は二つのシーケンスA={a 1,a 2,a 3,am}があると仮定します. B={b 1,b 2,b 3,...,bn}次元m>n
2.その後、欧式距離で各シーケンスの2点間の距離を計算し、D(ai、bj)のうち1≦i≦m、1≦j≦n
   下表を描く:
                                                           动态时间规整（Dynamic Time Warping）_第1张图片
3. 次は上の図に基づいて最短の経路を探し出すことです.D(a 1,a 2)からある経路に沿ってD(am,bn)に到達する.経路を探して満足する:もし現在ノードがD(ai,bj)であれば、次のノードはD(i＋1,j),D(i,j＋1)でなければならない.                D(i＋1、j＋1)の間で選択します.そして経路は最短でなければなりません.
4.次に経路を出力し、D(a 1,b 1)からD(am,bn)までです.彼らの合計は必要なDTW距離です.
はい、自分の書いたコードが悪いという意味ですが、他の人が恥ずかしくて貼ってくれます.参考すればいいです.間違っているところを教えてくれてありがとうございます.
matlabコード:
DW.m
function [route,distant]=DTW(a,b)
%      
m=size(a,1);
n=size(b,1);

for i=1:m
    for j=1:n
        D(i,j)=sqrt((a(i,:)-b(j,:))^2);
    end
end
D
%         
x=1;
y=1;
r=2;
route(1,1)=1;
route(1,2)=1;
route(1,3)=D(1,1);
distant=D(1,1);
for i=1:m-1
    for j=1:n-1
        if x<m && y<n
            value(1)=D(x+1,y);
            value(2)=D(x+1,y+1);
            value(3)=D(x,y+1);
            [maxvalue,index]=min(value);
            distant=distant+maxvalue;
            if index==1
                x=x+1;y=y;
                route(r,1)=x;
                route(r,2)=y;
                route(r,3)=D(x,y);
                r=r+1;
            end
            if index==2
                x=x+1;y=y+1;
                route(r,1)=x;
                route(r,2)=y;
                route(r,3)=D(x,y);
                r=r+1;
            end
            if index==3
                x=x;y=y+1;
                route(r,1)=x;
                route(r,2)=y;
                route(r,3)=D(x,y);
                r=r+1;
            end
        end
    end
end
%         
if x==m
    for i=y+1:n
        route(r,1)=m;  route(r,2)=i;route(r,3)=D(x,i);r=r+1;
        distant=distant+D(x,i);
    end
end
if y==n
    for i=x+1:m
        route(r,1)=i;  route(r,2)=n;route(r,3)=D(i,y);r=r+1;
        distant=distant+D(i,y);
    end
end 
end
DWtest.m
clear
clc
a=[8 9 1 9 6 1 3 5]';
b=[2 5 4 6 7 8 3 7 7 2]';
[route,distant]=DTW(a,b)
結果:
D =

     6     3     4     2     1     0     5     1     1     6
     7     4     5     3     2     1     6     2     2     7
     1     4     3     5     6     7     2     6     6     1
     7     4     5     3     2     1     6     2     2     7
     4     1     2     0     1     2     3     1     1     4
     1     4     3     5     6     7     2     6     6     1
     1     2     1     3     4     5     0     4     4     1
     3     0     1     1     2     3     2     2     2     3


route =

     1     1     6
     1     2     3
     2     2     4
     3     3     3
     4     4     3
     5     4     0
     5     5     1
     5     6     2
     6     7     2
     7     7     0
     8     7     2
     8     8     2
     8     9     2
     8    10     3


distant =

    33

>>
nodejs開発環jian境構築