巨型矩阵排序后，在列表中找到最小元素及其索引

Question

巨型矩阵排序后，在列表中找到最小元素及其索引

3

我有一个相当大的矩阵M。我正在尝试找出最接近的前5个距离以及它们的索引。

M = csr_matrix(M)
dst = pairwise_distances(M,Y=None,metric='euclidean')

< p > dst 变成了一个巨大的矩阵，我正在尝试高效地对其进行排序或使用scipy或sklearn找到最接近的5个距离。

这是我想做的事情的示例：

X = np.array([[2, 3, 5], [2, 3, 6], [2, 3, 8], [2, 3, 3], [2, 3, 4]])

我将计算dst如下：

[[ 0.  1.  3.  2.  1.]
 [ 1.  0.  2.  3.  2.]
 [ 3.  2.  0.  5.  4.]
 [ 2.  3.  5.  0.  1.]
 [ 1.  2.  4.  1.  0.]]

因此，第0行到自身的距离为0.，第0行到第1行的距离为1.，... 第2行到第3行的距离为5.，以此类推。我想找出这些最近的5个距离，并将它们与相应的行放入列表中，例如[距离，行，行]。我不想要任何对角线元素或重复元素，因此我取上三角矩阵如下：

[[ inf   1.   3.   2.   1.]
 [ nan  inf   2.   3.   2.]
 [ nan  nan  inf   5.   4.]
 [ nan  nan  nan  inf   1.]
 [ nan  nan  nan  nan  inf]]

现在，距离从小到大的前五名是：

[1, 0, 1], [1, 0, 4], [1, 3, 4], [2, 1, 2], [2, 0, 3], [2, 1, 4]

如您所见，有三个距离为2的元素和三个距离为1的元素。我想从中随机选择一个距离为2的元素作为保留项，因为我只需要前f个元素，其中f=5。这只是一个示例，因为这个矩阵可能非常大。除了使用基本排序函数，还有没有更有效的方法来完成上述操作？我找不到任何可以帮助我完成此操作的sklearn或scipy。

- Mike El Jackson

你应该看一下dask。 - Zeugma

看起来很不错，我会去查看的。 - Mike El Jackson

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tonechas · Accepted Answer

这是一个完全矢量化的解决方案，适用于您的问题：

import numpy as np
from scipy.spatial.distance import pdist

def smallest(M, f):
    # compute the condensed distance matrix
    dst = pdist(M, 'euclidean')
    # indices of the upper triangular matrix
    rows, cols = np.triu_indices(M.shape[0], k=1)
    # indices of the f smallest distances
    idx = np.argsort(dst)[:f]
    # gather results in the specified format: distance, row, column
    return np.vstack((dst[idx], rows[idx], cols[idx])).T

注意np.argsort(dst)[:f]返回按升序排序的压缩距离矩阵dst中最小的f个元素的索引。

以下演示重现了您的玩具示例结果，并展示了函数smallest如何处理一个相当大的矩阵

的整数。

In [59]: X = np.array([[2, 3, 5], [2, 3, 6], [2, 3, 8], [2, 3, 3], [2, 3, 4]])

In [60]: smallest(X, 5)
Out[60]: 
array([[ 1.,  0.,  1.],
       [ 1.,  0.,  4.],
       [ 1.,  3.,  4.],
       [ 2.,  0.,  3.],
       [ 2.,  1.,  2.]])

In [61]: large_X = np.random.randint(100, size=(10000, 2000))

In [62]: large_X
Out[62]: 
array([[ 8, 78, 97, ..., 23, 93, 90],
       [42,  2, 21, ..., 68, 45, 62],
       [28, 45, 30, ...,  0, 75, 48],
       ..., 
       [26, 88, 78, ...,  0, 88, 43],
       [91, 53, 94, ..., 85, 44, 37],
       [39,  8, 10, ..., 46, 15, 67]])

In [63]: %time smallest(large_X, 5)
Wall time: 1min 32s
Out[63]: 
array([[ 1676.12529365,  4815.        ,  5863.        ],
       [ 1692.97253374,  1628.        ,  2950.        ],
       [ 1693.558384  ,  5742.        ,  8240.        ],
       [ 1695.86408654,  2140.        ,  6969.        ],
       [ 1696.68853948,  5477.        ,  6641.        ]])