動的タイムワーピング（DTW）の代替方法

Question

私は、時系列データを比較する方法をいくつか研究しています。このタイプのデータを照合するために使用されているアルゴリズムの1つは、DTW（動的時間ワーピング）アルゴリズムです。

私が持っているデータは、次の構造に似ている（これは、1つのパスとすることができる）：

Path Event  Time   Location (x,y) 
    1  1  2:30:02    1,5 
    1  2  2:30:04    2,7 
    1  3  2:30:06    4,4 
... 
... 

を今、Iは、与えられた最も近い一致を見つけることが適しているであろう他のアルゴリズムが存在するかどうかを疑問に思いましたパス。

Answer 1

2つの経路が同じ長さである場合は、nはを言って、その後、彼らは本当に2N次元空間にポイントです。最初の場所は最初の2つのディメンションを決定し、2番目の場所は次の2つのディメンションを決定します。たとえば、あなたの例で3点を取るだけであれば、パスは1つの6次元点（1,5,2,7,4,4）として表現できます。これを別の3点経路と比較したい場合は、ユークリッド距離（2点間の距離ごとの二乗和の平方根）またはマンハッタン距離（次元ごとの差の合計）。

たとえば、すべての3回にわたって（0,0）にとどまるボーリング経路は、6次元の点（0,0,0,0,0,0）になります。そして、この点とあなたの例のパスの間のユークリッド距離はsqrt((1-0)^2 + (5-0)^2 + (2-0)^2 + (7-0)^2 + (4-0)^2 + (4-0)^2) = sqrt(111) = 10.54です。マンハッタンの距離はabs(1-0) + abs(5-0) + abs(2-0) + abs(7-0) + abs(4-0) + abs(4-0) = 23です。このようなメトリクスの違いは珍しいことではありません。マンハッタンの距離は少なくともユークリッド距離ほど大きいからです。

もちろん、このアプローチの1つの問題は、すべてのパスが同じ長さになるわけではないことです。ただし、長い方のパスを短い方のパスと同じ長さに簡単に切り捨てたり、2つのパスのうちの短い方を同じ場所にとどめること、または両方のパスが同じ長さになるまで測定終了後に同じ方向に移動することができます。いずれのアプローチでもいくつかの不正確さが導入されますが、あなたが何をしていても、短い道のりでデータが欠落していて、何とかそれを補う必要があるという事実に対処しなければなりません。

EDIT：

path1とpath2ポイントを含む両方のList<Tuple<int, int>>オブジェクトであると仮定すると、私たちのように短いリストを一致させるために長いリストを遮断することができますすることができます、そして、

// Enumerable.Zip stops when it finishes one of the sequences 
List<Tuple<int, int, int, int>> matchingPoints = Enumerable.Zip(path1, path2, 
    (tupl1, tupl2) => 
     Tuple.Create(tupl1.Item1, tupl1.Item2, tupl2.Item1, tupl2.Item2)); 

マンハッタンの距離を見つけるには、次のコードを使用します。

int manhattanDistance = matchingPoints 
    .Sum(tupl => Math.Abs(tupl.Item1 - tupl.Item3) 
       + Math.Abs(tupl.Item2 - tupl.Item4)); 

int euclideanDistanceSquared = matchingPoints 
    .Sum(tupl => Math.Pow(tupl.Item1 - tupl.Item3, 2) 
       + Math.Pow(tupl.Item2 - tupl.Item4, 2)); 
double euclideanDistance = Math.Sqrt(euclideanDistanceSquared); 

Answer 2

いくつかの助けになるかもしれない別の質問hereあります：としてマンハッタン距離と同じ仮定では、我々は、ユークリッド距離を生成することができます。既に指定されたパスがある場合は、クロストラック距離アルゴリズムを使用して最も近い一致を見つけることができます。一方、パターン認識の問題を実際に解決したい場合は、Levenshtein distanceとElastic Matchingについて詳しく調べることをお勧めします（「弾性マッチングは2次元ワーピングの最適化問題として定義できます」

Answer 3

あなたが探しているキーワードは、 "（dis-）類似度測定"です。

Adam Mihalcin（最初の解答）が指すユークリッド距離（ED）は、簡単に計算可能であり、何らかの形で、自然言語の単語距離の自然な理解を反映しています。しかし、2つの時系列を比較する場合、特に現実世界のデータに適用する場合、DTWが優先されます。

1）EDは、同じ長さのシリーズにのみ適用できます。したがって、ポイントが欠落している場合、EDは計算可能ではありません（他のシーケンスをカットしないと、情報が失われます）。

2）EDは、DTWに基づくすべてのアルゴリズムとは対照的に、タイムシフトまたはタイムワーピングを許可しません。

したがって、要件と制限がはるかに高いため、EDはDTWの本当の代替手段ではありません。しかし、あなたの質問に答えるために、私はあなたに、この講義をお勧めしたい：

時系列クラスタリング - 十年のレビュー サイードAghabozorgi、アリセイェドShirkhorshidi、テー英ワウ http://www.sciencedirect.com/science/article/pii/S0306437915000733

本稿ではおよそ概要を説明します時系列クラスタリングで使用される類似（dis-）類似性指標を提供する。