python - 大型 NumPy 数组的成对距离(分块？)

Question

问题:
我有一个大约为 [350000, 1] 的向量，我希望计算成对距离。这导致 [350000, 350000] 整数数据类型的矩阵不适合 RAM。我最终想得到一个 bool 值(适合 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]]

请注意，取绝对值时，只需要计算上三角形，因为它是对称的。

需要分块或替代解决方案的矢量化代码:
我找到了一种方法来计算使用广播在小矩阵上工作的所有点之间的距离(减法)，但需要一种方法来在不达到 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

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

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

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

如果您的 bool 数组适合内存，并且您尝试查找在特定范围内可以执行的值

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