如何讓DTW跑得更快？

Question

我有一個包含4500個長度爲1800的向量的矩陣，爲此我需要計算矩陣中每兩個向量之間的DTW（動態時間翹曲）距離。

我已經使用一個嵌套循環填滿一個4500x4500矩陣（其看起來像一個三角形）的一半：

matr = zeros(4500,4500); %initializing empty matrix to fill dtw distance 
for i=1:4500 
    x = new(i,:); %new is where the data lies 
    for j = i+1:4500 
     y = new(j,:); 
     matr(i,j) = dtw(x,y); 
    end 
end 

的問題是，代碼運行極爲緩慢。根據我的計算，我需要4天的時間才能在我的電腦上運行。

我不知道矢量化如何工作。但有沒有辦法我的代碼可以矢量化，以便運行速度更快？還有沒有內置的功能，我可以插入所有的向量，並獲得自動生成的DTW dist矩陣？

Answer 1

不，沒有明顯的方法來在Matlab中矢量化您的代碼以使其更快。您要求進行大量計算（〜4500^2/2個DTW計算），無論您做什麼，都可能需要時間。但是你有一些選擇：

• 如果你只需要做一次這個計算，就運行它並等待四天。如果您在學校或公司，您可能可以在個人計算機以外的計算機上運行它。
• 您可以嘗試在pdist2的調用中使用dtw作爲自定義距離函數。這可能會稍微快一點。
• 你可以在Matlab中編寫自己的DTW，並儘量節省時間。一個明顯的加速是，每個dtw的調用都必須分配一個1800x1800矩陣。在你自己的代碼中，你可以分配一次並重用它。
• 您可以使用其他語言編寫自己的DTW，或使用其他語言的其他DTW代碼。這些可以從Matlab通過MEX調用，並且可能會更快，具體取決於語言和實現。
• 你可以解決一個近似值。例如，選擇一個參考信號x0，併爲每個4500矢量計算dtw(x0, xi)。然後進行近似，即dtw(xi, xj) = dtw(x0, xi) + dtw(x0, xj)。這樣做比您提議的快大約4500倍。