Python - 给定数组中给定长度的所有子序列对的欧几里德距离

Question

假设我有一个 numpy 数组 [5,7,2,3,4,6] 并且我选择子序列的长度为 3。

我想获得此类子序列的欧几里得距离。

可能的子序列是：

1. [5,7,2]
2. [7,2,3]
3. [2,3,4]
4. [3,4,6]

子序列 1. 和 3. 之间的距离将计算为 (5-2)^2 + (7-3)^2 + (2-4)^2。我想对所有子序列对执行此操作。

有没有办法避免循环？

我的真实数组很长，所以解决方案也应该是内存高效的。

编辑>

详细说明：我有一个大小为 10^5 到 10^8 元素的时间序列

时间序列正在增长。每次添加新点时，我需要取 L 个最新点，并在数据集的过去点中找到与这些点最接近的匹配。（但我希望所有距离值不仅要找到最接近的匹配项）

无需重复整个计算。“以前最新的L点”的距离可以更新，只能通过减去年龄L+1的点和加上年龄0的点（最新的）来修改。

例如，假设时间序列的大小当前为 100 且 L=10。我计算子序列 A[90:100] 到所有先前子序列的距离。当第 101 个点到达时，我可以重复使用这些距离，并且只能通过从时间序列中添加第 101 个点的距离平方并减去第 90 个点的平方来更新它们。

编辑 2>

非常感谢您的想法，看起来很神奇。我还有一个想法，特别是对于添加 tiem 系列的新元素时的在线时间序列，它可能是有效的。

我正在考虑这种更新距离的方式。要计算长度为 L=4 的第一个子序列到矩阵的距离，我们需要有以下矩阵的前 4 列（顶部和底部的三角形可以省略）。然后将距离平方并求和，如颜色所示。

为了获得 L=4 的第二个子序列的距离，我们实际上可以重用先前计算的距离并从中减去第一列（平方）并添加第四列（平方）。对于 L=4，它可能没有意义，但对于 L=100，它可能没有意义。一个距离必须从头开始计算。（实际上，如果时间序列的大小增加，则必须计算 2）。

这样我可以只保留一个子序列的距离并更新它们以获得下一个子序列的距离。

你认为这对 numpy 有效吗？有没有简单的方法来实现它？

Answer 1

假设A作为输入数组和L子序列的长度，您可以获得Awith的滑动二维数组版本，broadcasting然后pdist从 scipy.spatial.distance使用，就像这样 -

# Get sliding 2D array version of input array
A2D = A[np.arange(A.size-L+1)[:,None] + np.arange(L)]

# Get pairwise distances with pdist
pairwise_dist = pdist(A2D,'sqeuclidean') 

请注意，如果你的意思是欧几里得距离，你需要更换'sqeuclidean'具有'euclidean'或只留下了这样的说法，因为它是默认的。

样品运行 -

In [209]: # Inputs
     ...: A = np.array([5,7,2,3,4,6])
     ...: L = 3
     ...: 

In [210]: A2D = A[np.arange(A.size-L+1)[:,None] + np.arange(L)]

In [211]: A2D
Out[211]: 
array([[5, 7, 2],
       [7, 2, 3],
       [2, 3, 4],
       [3, 4, 6]])

In [212]: pdist(A2D,'sqeuclidean')
Out[212]: array([ 30.,  29.,  29.,  27.,  29.,   6.])
          # [1] element (= 29) is (5-2)^2 + (7-3)^2 + (2-4)^2

要获得相应的 ID，您可以np.triu_indices像这样使用-

idx1,idx2 = np.triu_indices(A2D.shape[0],1)

并且，最后像这样在距离旁边显示 ID -

ID_dist = np.column_stack((idx1,idx2,pairwise_dist))

样品运行 -

In [201]: idx1,idx2
Out[201]: (array([0, 0, 0, 1, 1, 2]), array([1, 2, 3, 2, 3, 3]))

In [202]: np.column_stack((idx1,idx2,pairwise_dist))
Out[202]: 
array([[  0.,   1.,  30.],
       [  0.,   2.,  29.], # This was your (5-2)^2 + (7-3)^2 + (2-4)^2
       [  0.,   3.,  29.],
       [  1.,   2.,  27.],
       [  1.,   3.,  29.],
       [  2.,   3.,   6.]])

对于这种情况，当您处理数百万个元素A和L数百个元素时，最好在循环中为此类子序列的每个成对微分执行计算，如下所示 -

# Get pairiwise IDs
idx1,idx2 = np.triu_indices(A.size-L+1,1)

# Store range array for L as would be used frequently in loop
R = np.arange(L)

# Initialize output array and start computing
pairwise_dist = np.empty(len(idx1))
for i in range(len(idx1)):
    pairwise_dist[i] = ((A[R+idx2[i]] - A[R+idx1[i]])**2).sum()

您还可以使用np.einsum在每次迭代时为我们获取平方和，就像这样 -

diffs = A[R+idx2[i]] - A[R+idx1[i]]
pairwise_dist[i] = np.einsum('i,i->',diffs,diffs)