如何让DTW跑得更快？

Question

我有一个长度为1800的4500个向量的矩阵，为此我需要计算矩阵中每2个向量之间的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天。

我不知道向量化是如何工作的。但是，是否有一种方法可以将我的代码向量化，使其运行得更快？还有一个内置的函数，我可以插入所有的向量并自动生成dist矩阵吗？

Answer 1

不，在Matlab中没有明显的方法将代码向量化以使其更快。您需要大量的计算(~4500^2 /2 DTW计算)，无论您做什么，都可能需要时间。但你有一些选择：

• 如果您只需要计算一次，只需运行它并等待四天。如果你在一所学校或公司，你可能可以运行在计算机上，而不是你的个人电脑。
• 您可以尝试在调用dtw中使用pdist2作为自定义距离函数。这可能会稍微快一些。
• 您可以在Matlab中编写自己的DTW，并尝试在那里节省时间。一个明显的加速是，每个对dtw的调用都必须分配一个1800x1800矩阵。在您自己的代码中，您可以分配它一次并重用它。
• 您可以用另一种语言编写自己的DTW，也可以使用其他语言的DTW代码。它们可以通过MEX从Matlab调用，并且可能会更快，这取决于语言和实现。
• 你可以接受近似值。例如，选择一个参考信号x0，并计算4500个向量中的每个向量的dtw(x0, xi)。然后进行近似，即dtw(xi, xj) = dtw(x0, xi) + dtw(x0, xj)。这样做比你提议的要快4500倍。