大型矩阵排序，然后找出最小的元素及其索引成一个列表。

Question

我有一个比较大的矩阵M。我试图找到前5位最近的距离，以及他们的指数。

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

dst成为一个巨大的矩阵，我正试图有效地对它进行排序，或者使用枕木或滑雪板来找到最近的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]]

现在，前5位距离最小到最大的是：

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

如您所见，有三个元素具有距离2，三个元素具有距离1。从这些元素中，我想随机选择一个具有距离2的元素，因为我只想要顶部的f元素，在本例中是f=5。

这只是一个样本，因为这个矩阵可能很大。除了使用基本的排序函数之外，是否有一种有效的方法来完成上述工作？我找不到任何滑雪板或乐土来帮助我。

Answer 1

下面是一个完全矢量化的解决方案：

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.        ]])