如何让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倍。