有效更新点间距离

Question

我有一个数据集，它有n行（观察值）和p列（特征）：

import numpy as np
from scipy.spatial.distance import pdist, squareform
p = 3
n = 5
xOld = np.random.rand(n * p).reshape([n, p])

我想得到一个nxn矩阵中这些点之间的距离，这个矩阵真的有n x (n-1)/2唯一的值

sq_dists = pdist(xOld, 'sqeuclidean')
D_n = squareform(sq_dists)

现在假设我得到了N额外的观察结果，并且想更新D_n。一种非常低效的方法是：

N = 3
xNew = np.random.rand(N * p).reshape([N, p])
sq_dists = pdist(np.row_stack([xOld, xNew]), 'sqeuclidean')
D_n_N = squareform(sq_dists)

但是，考虑到n~10000和n~100，这将是多余的。我的目标是更有效地使用D_n。为了做到这一点，我将D\n\n划分如下。我已经有了D_n，可以计算B [N x N]。然而，我想知道是否有一个好的方法来计算a（或转置），而不需要一堆for循环，并最终构造D_n_N

D_n (n x n)    A [n x N]
A.T [N x n]    B [N x N]

提前谢谢。你知道吗

Answer 1

很有趣的问题！在解决这个问题的过程中，我学到了一些新的东西。你知道吗

涉及的步骤：

• 首先，我们在这里介绍新的临时秘书处。所以，我们需要使用cdist来得到新旧pts之间的平方欧氏距离。在新的输出中，这些将被容纳在两个块中，一个位于旧距离的正下方，另一个位于旧距离的右侧。

• 我们还需要计算新pts中的pdist，并将其square-formed块放在新对角线区域的尾部。

示意性地放置新的D_n_N如下所示：

[   D_n      cdist.T
  cdist      New pdist squarefomed]

总而言之，实施过程将遵循以下思路——

cdists = cdist( xNew, xOld, 'sqeuclidean')

n1 = D_n.shape[0]
out = np.empty((n1+N,n1+N))
out[:n1,:n1] = D_n
out[n1:,:n1] = cdists
out[:n1,n1:] = cdists.T
out[n1:,n1:] = squareform(pdist(xNew, 'sqeuclidean'))

---

运行时测试

接近-

# Original approach
def org_app(D_n, xNew):
    sq_dists = pdist(np.row_stack([xOld, xNew]), 'sqeuclidean')
    D_n_N = squareform(sq_dists)
    return D_n_N    

# Proposed approach
def proposed_app(D_n, xNew, N):
    cdists = cdist( xNew, xOld, 'sqeuclidean')    
    n1 = D_n.shape[0]
    out = np.empty((n1+N,n1+N))
    out[:n1,:n1] = D_n
    out[n1:,:n1] = cdists
    out[:n1,n1:] = cdists.T
    out[n1:,n1:] = squareform(pdist(xNew, 'sqeuclidean'))
    return out

计时-

In [102]: # Setup inputs
     ...: p = 3
     ...: n = 5000
     ...: xOld = np.random.rand(n * p).reshape([n, p])
     ...: 
     ...: sq_dists = pdist(xOld, 'sqeuclidean')
     ...: D_n = squareform(sq_dists)
     ...: 
     ...: N = 3000
     ...: xNew = np.random.rand(N * p).reshape([N, p])
     ...: 

In [103]: np.allclose( proposed_app(D_n, xNew, N), org_app(D_n, xNew))
Out[103]: True

In [104]: %timeit org_app(D_n, xNew)
1 loops, best of 3: 541 ms per loop

In [105]: %timeit proposed_app(D_n, xNew, N)
1 loops, best of 3: 201 ms per loop

Answer 2

只需使用cdist：

D_OO=cdist(xOld,xOld)

D_NN=cdist(xNew,xNew)
D_NO=cdist(xNew,xOld)
D_ON=cdist(xOld,xNew) # or D_NO.T

最后：

D_=vstack((hstack((D_OO,D_ON)),(hstack((D_NO,D_NN)))))