大型2D numpy数组中相同元素的高效成对计算

Question

我有一个二维numpy数组，有数十万行和大约一千列（假设它是一个N x P数组，其中N = 200,000，P = 1000）。目标是计算每对行向量之间相同元素的数量，最好使用numpy数组魔术来完成，而不需要对199,999 * 100,000这样的对执行循环。由于可能无法存储一个200,000 x 200,000的数组，因此输出可能以Nx3稀疏坐标格式为例，例如如果输入形式如下：

5 12 14 200   0 45223
7 12 14   0 200 60000
7  6 23   0   0 45223
5  6 14 200   0 45223

生成的（密集的）NxN矩阵M将是（不考虑对角线元素）：

0 2 2 4
2 0 2 1
2 2 0 3
4 1 3 0

其中Mij包含了初始行i和初始行j之间相同元素的数量，假设索引从0开始。 因此，预期的稀疏输出等效结果为:

0 1 2
0 2 2
0 3 4
1 2 2 
1 3 1
2 3 3

一个天真、效率极低的实现方式是：

import itertools
import numpy as np

def pairwise_identical_elements(small_matrix):
    n, p = small_matrix.shape
    coordinates = itertools.combinations(range(n), 2)
    sparse_coordinate_matrix = []
    for row1, row2 in itertools.combinations(small_matrix, 2):
        idx1, idx2 = next(coordinates)
        count = p - np.count_nonzero(row1 - row2)
        sparse_coordinate_matrix.append([idx1, idx2, count])
    return sparse_coordinate_matrix

我研究了诸如scipy和sklearn中的Jaccard相似度等距离度量实现，但它们都假设输入的行向量必须是二进制的。我也尝试添加第三个维度使得条目变为二进制（例如，一个条目“9”会变成一个零元素向量，第九个位置上有一个1），但存在明显的内存问题（一个条目“45223”需要第三个维度扩展这么多元素）。

是否有一种有效、可扩展和/或Pythonic的解决方案使用numpy或scipy，我可能错过了？

编辑：在进一步研究scipy后，我找到了与我试图做的事情非常接近的东西，即使用汉明度量的scipy.sparse.distance.pdist。然而，它以“压缩”形式返回输出，因为我们正在尝试避免将其转换为完整的稠密数组以节省内存，所以问题可能变为：如何将压缩的距离矩阵转换成稀疏矩阵？

- lurena

---

请提供一些代码，以便更好地了解您的意图。 - Abr001am

当然，我添加了一个小片段来实现我试图以一种天真的方式做的事情。输入被假定为标准的numpy数组。 - lurena

那么这里的关键在哪里？空间复杂度？还是时间问题？ - Abr001am

内存是一个明显的问题（因为Python在处理太多对象时往往会崩溃），但是与scipy.sparse.distance模块中上述pdist函数相同数量级的任何运行时间都可以接受。 - lurena

@lurena，你能解释一下问题中的例子吗？因为使用你的函数运行该示例输入会得到不同的输出。 - Saullo G. P. Castro

糟糕。该函数假定基于0的索引，而我的示例使用了基于1的索引。希望现在更清楚了。 - lurena

Answer 1

如评论中所述，使用scipy的pdist和'hamming'是解决此问题最简单有效的方法，无论是对于空间考虑还是CPU时间。

您将无法比其压缩输出更节省内存。 实际上，在写入您的“稀疏”格式时，您需要一个(N*(N-1)/2, 3)矩阵，而不是pdist返回的N*(N-1)/2向量。

- M1L0U