動態時間規整（DTW）方法的替代

我正在對比較時間序列數據的方法進行一些研究。我發現用於匹配這種類型數據的算法之一是DTW（動態時間規整）算法。動態時間規整（DTW）方法的替代

我有數據，類似於下面的結構（這可以是一個路徑）：

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 
... 
...

現在，我想知道是否有其他的算法，這將是適合以找到給出最接近的匹配路徑。

來源

2012-01-13 user496607

這裏需要提供更多的信息。決定「匹配」的邏輯是什麼？如果我使用手勢識別的情況和例如繪製數字'6'的路徑的例子，則根據路徑的形狀（即：大6應該'匹配'小'6'縮放比例），路徑的拓撲結構（即小寫的希臘語「西格瑪」匹配'6'匹配'b'等），路徑的速度（即：快速繪製的6與慢速繪製的不匹配） - 你想達到什麼目的？以什麼準確度？用什麼重量？像這樣的問題需要更多的參數。 – 2012-01-17 19:31:44

如果兩個路徑的長度相同，說ñ，那麼他們在一個2N維空間真正指向。第一個位置確定前兩個維度，第二個位置確定下一個維度，依此類推。例如，如果我們只在您的示例中使用三個點，則路徑可以表示爲單個6維點（1,5,2,7,4,4）。如果我們想將它與另一個三點路徑進行比較，我們可以計算歐幾里德距離（兩點之間每維距離的平方和的平方根）或曼哈頓距離（每維度差的和）。

例如，所有三次停留在（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。這些指標之間的差異並不罕見，因爲曼哈頓距離可證明至少與歐幾里得距離一樣大。

這種方法當然有一個問題，並不是所有的路徑長度都是相同的。但是，您可以很容易地將較長的路徑切割成與較短路徑相同的長度，或者考慮將兩條路徑中較短的一條留在同一位置或在測量結束後沿相同方向移動，直到兩條路徑長度相同。這兩種方法都會帶來一些不準確的結果，但無論你做什麼，你都必須處理這樣一個事實，即你在短路徑上缺少數據，必須以某種方式彌補它。

編輯：

假設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);

來源

2012-01-18 21:53:48

我也有這個想法，但我無法應用它，主要是由於路徑永遠不相等（某些路徑可能是其他路徑長度的10倍），因此窗口函數會很耗時。 – user496607 2012-01-19 01:02:46

不一定。正如我上面提到的那樣，您可以切斷較長的路徑以匹配較短路徑的長度，然後簡單計算距離的距離。不需要窗口功能。 – 2012-01-19 22:44:37

這是否考慮點的順序？如果我在一個方向上走PATH A，它不應該匹配另一個方向上的相同路徑（返回） – user496607 2012-01-21 00:25:40

還有另一個問題here可能會有所幫助。如果您已經有了給定的路徑，則可以使用交叉軌跡距離算法找到最接近的匹配項;另一方面，如果您確實想要解決模式識別問題，您可能需要了解有關Levenshtein距離和彈性匹配的更多信息（來自Wikipedia：「彈性匹配可以定義爲指定二維扭曲的優化問題相關像素之間的相應像素「

來源

2012-01-18 22:24:18 casals

您正在尋找的關鍵字是」（dis-）相似性度量「。

Adam Mihalcin提到的歐幾里德距離（ED）很容易計算，它以某種方式反映了自然語言中對單詞距離的自然理解。然而，當比較兩個時間序列時，DTW將被優先考慮 - 尤其是當應用於真實世界的數據時。

1）ED只能應用於等長的系列。因此，當缺少點時，ED根本無法計算（除非也切斷其他序列，從而丟失更多信息）。 2）ED不允許與基於DTW的所有算法相對的時間偏移或時間偏移。

因此ED不是DTW的真正替代品，因爲要求和限制要高得多。但是，爲了回答你的問題，我想向你推薦本次講座：

時間序列集羣 - 十年回顧賽義德Aghabozorgi，阿里·賽義德Shirkhorshidi，德英華 http://www.sciencedirect.com/science/article/pii/S0306437915000733

本文介紹了有關的概述（dis-）相似性度量，用於時間序列聚類。這裏一個小片段來激勵你的實際讀取的文件：

來源

2016-04-22 12:58:33

此答案不回答實際問題，但它作爲對接受答案的反應完美起作用。你是完全正確的，教育署根本不是DTW的替代選擇。非常感謝，+1解釋。 – 2016-04-27 18:30:14

動態時間規整（DTW）方法的替代

回答

相關問題