大型 NumPy 数组的成对距离（分块？）

Question

问题： 我有一个大约为 [350000, 1] 的向量，我希望计算成对距离。这会导致不适合 RAM 的整数数据类型的 [350000, 350000] 矩阵。我最终想得到一个布尔值（适合 RAM），所以我目前一次只做一个元素，但这不是很省时。

编辑：标准的 sklearn 和 scipy 函数由于数据的大小而不起作用——但如果我能以某种方式将其分块以使用硬盘，那么我应该能够使用这些。

可视化问题： [a_1, a_2, a_3]^t -> [[a_1 - a_1, a_1 - a_2, a_1 - a_3], [a_2 - a_1, a_2 - a_2, a_2 - a_3], [a_3 - a_1, a_3 - a_2, a_3 - a_3]]

注意取abs值时只需要计算上三角因为它是对称的

需要分块或替代解决方案的矢量化代码： 我找到了一种方法来计算使用广播在小矩阵上工作的所有点之间的距离（减法），但需要一种方法能够在不影响 RAM 限制的情况下在更大的矩阵上执行此操作。

或者可以建议一种更快的 MWE 更好方法？

distMatrix = np.absolute((points[np.newaxis, :, :] - points[:, np.newaxis, :])[:, :, 0])

其他尝试： 我试过使用 dask 和 memmap 但仍然出现内存错误，所以一定是做错了什么。我还尝试了 memmap 并手动对数据进行分块，但没有获得完整的结果集，因此非常感谢您的帮助。

当前方法的 MWE：


## Data ##
#Note that the datatype and code may not match up exactly as just creating to demonstrate. Essentially want to take first column and create distance matrix with itself through subtracting, and then take 2nd and 3rd column and create euclidean distance matrix.

data = np.random.randint(1, 5, size=[350001,3])
minTime = 3
maxTime = 4
minDist = 1
maxDist = 2

### CODE ###
n = len(data)

for i in trange(n):
    for j in range(i+1, n):
        #Within time threshold?
        if minTime <= (data[j][idxT] - data[i][idxT]) <= maxTime:
            #Within distance threshold?
            xD = math.pow(data[j][idxX] - data[i][idxX], 2)
            yD = math.pow(data[j][idxY] - data[i][idxY], 2)
            d = math.sqrt(xD + yD)
            #If within  threshold then
            if minDist <= d <= maxDist:
                #DO SOMETHING

原因： 我有时间，x_coordinate，y_coordinate 向量大约 350000 点。我想计算所有时间点之间的距离（简单减法）和每个 (x,y) 点之间的欧氏距离。然后，我希望能够识别在彼此产生布尔值的时间和距离发生阈值内的所有点对。

Answer 1

您可以将数组拆分为更小的数组，并分别计算每对数组的距离。

splits = np.array_split(data, 10)
for i in range(len(splits)):
    for j in range(i, len(splits)):
        m = scipy.spatial.distance.cdist(splits[i], splits[j])
        # do something with m

因为大多数计算发生在 scipy 中，python 循环的开销将是最小的。

如果你的布尔数组适合内存并且你试图找到你可以做的特定范围内的值

import numpy as np
import scipy.spatial.distance


boolean = np.zeros((350, 350), dtype=np.bool_)
a = np.random.randn(350, 2)
splits = np.array_split(a, 10)
shift = splits[0].shape[0]
minDist = -0.5
maxDist = +0.5
for i in range(len(splits)):
    for j in range(i, len(splits)):
        m = scipy.spatial.distance.cdist(splits[i], splits[j])
        masked = (minDist <= m) & (m <= maxDist)
        boolean[i * shift: (i + 1) * shift, j * shift : (j + 1) * shift] = masked
        boolean[j * shift : (j + 1) * shift, i * shift: (i + 1) * shift] = masked.T

大型 NumPy 数组的成对距离（分块？）

Pairwise Distance with Large NumPy Arrays (Chunking?)

python

numpy

distance

chunking