找到两个巨大的 CSR 矩阵的行之间的欧氏距离

Question

我有两个稀疏矩阵，A 和 B。A 是 120000*5000，B 是 30000*5000。我需要找到 B 中每一行与 A 中所有行之间的欧氏距离，然后找到 A 中与 B 中所选行的距离最短的 5 行。因为这是一个非常大的数据，我正在使用 CSR，否则我得到内存错误。很明显，对于 A 中的每一行，它计算 (x_b - x_a)^2 5000 次并对它们求和，然后得到一个 sqrt。这个过程需要非常非常长的时间，比如 11 天！有什么办法可以更有效地做到这一点？我只需要与 B 中每一行的距离最短的 5 行。

我正在实施 K 最近邻，A 是我的训练集，B 是我的测试集。

Answer 1

好吧 - 我不知道您是否可以 'vectorize' 那个代码，这样它就会运行在本机代码中而不是 Python。 speed-up numpy 和 scipy 的诀窍总是得到它。

如果您可以运行在 1GHz CPU 的本机代码中编写该代码，并使用 1 个用于时钟 cicle 的 FP 指令，您将在不到 10 小时的时间内完成。 (5000 * 2 * 30000 * 120000) / 1024 ** 3

将其提高到 1.5Ghz x 2 CPU 物理内核 x 4 路 SIMD 指令与乘法 + 累加（Intel AVX 扩展，在大多数 CPUs 中可用），你可以得到这个数字 c 运行在普通的核心 i5 机器上以 2 x 100% 的速度缩短到一小时。但这需要在本机代码中进行完整的 SIMD 优化——远非一项微不足道的任务（尽管，如果你决定走这条路，关于 S.O 的进一步问题可能会得到人们的帮助，或者在 SIMD 编码中弄湿他们的手： -) ) - 使用 cython 在 C 中将这段代码与 Scipy 连接并不难，例如（你只需要那部分就可以达到上面的 10 小时数字）

现在...至于算法优化，并保留东西Python :-)
事实是，您不需要完全计算 A 中行的 all 距离 - 您只需要保留 5 个较低行的排序列表 - 并且任何时候总和的累积的正方形变得大于第 5 个最近的行（到目前为止），您只需中止该行的计算。

您可以为此使用 Python' heapq 操作：

import heapq
import math

def get_closer_rows(b_row, a):
    result = [(float("+inf"), None)  * 5]
    for i, a_row in enumerate(a):
        distance_sq = 0
        count = 0
        for element_a, element_b in zip(a_row, b_row):
            distance_sq += element_a * element_b
            if not count % 64 and distance_sq > result[4][0]:
                break
            count += 1
        else:
            heapq.heappush(result, (distance, i))
            result[:] = result[:5]
    return [math.sqrt(r) for r in result]

closer_rows_to_b = []
for row in b:
    closer_rows_to_b.append(get_closer_rows(row, a))

请注意辅助 "count" 以避免所有乘法的值的昂贵检索和比较。现在，如果您可以运行使用 pypy 而不是常规 Python 这段代码，我相信它可以充分利用 JITting，如果您运行在纯 Python 中使用代码（即：非 numpy/scipy 向量化代码）。

找到两个巨大的 CSR 矩阵的行之间的欧氏距离

Find euclidean distance between rows of two huge CSR matrices

csr

sparse-matrix

knn

euclidean-distance

python-3.x