如何得到n个点中距离最大的m对点

Question

假设我在一维中定义了以下点 space:

x = np.array([[0.70710678],
             [0.70710678],
             [0.        ],
             [1.41421356]])

我想在这 n 个点中得到 m 对点，它们之间的欧氏距离最长（如果 m 是 1 在这种情况下将是 1.4142 和 0 ）

我尝试通过 :

获取成对距离

from scipy.spatial.distance import pdist, cdist

cdist(x,x, 'seuclidean')

从这部分开始，我不确定如何完成其余部分。

Answer 1

要将每个点与其最远的对应点配对，您可以使用：

np.dstack((x, x[cdist(x,x, 'seuclidean').argmax(axis=-1)]))

#array([[[0.70710678, 0.        ]],
#
#       [[0.70710678, 0.        ]],
#
#       [[0.        , 1.41421356]],
#
#       [[1.41421356, 0.        ]]])

Answer 2

我们可以利用 np.argpartition 的扁平化距离 cdist 结果 -

dists = np.triu(cdist(x,x, 'seuclidean'),1)
s = dists.shape
idx = np.vstack(np.unravel_index(np.argpartition(dists.ravel(),-m)[-m:],s)).T

idx 将是最远的 m 对索引，即 idx 的每一行将代表来自 x.[=23= 的一对索引]

样本运行-

# with m = 1
In [144]: idx
Out[144]: array([[2, 3]])

# with m = 2    
In [147]: idx
Out[147]: 
array([[1, 2],
       [2, 3]])

# with m = 3        
In [150]: idx
Out[150]: 
array([[0, 3],
       [1, 2],
       [2, 3]])

2D 数组上的示例运行 -

In [44]: x
Out[44]: 
array([[1.25, 1.25],
       [1.25, 1.25],
       [1.87, 1.87],
       [0.62, 0.62],
       [0.62, 0.62],
       [1.25, 1.25],
       [0.  , 0.  ],
       [0.62, 0.62]])

In [45]: m = 2

In [46]: dists
Out[46]: 
array([[0.  , 0.  , 1.58, 1.58, 1.58, 0.  , 3.16, 1.58],
       [0.  , 0.  , 1.58, 1.58, 1.58, 0.  , 3.16, 1.58],
       [0.  , 0.  , 0.  , 3.16, 3.16, 1.58, 4.74, 3.16],
       [0.  , 0.  , 0.  , 0.  , 0.  , 1.58, 1.58, 0.  ],
       [0.  , 0.  , 0.  , 0.  , 0.  , 1.58, 1.58, 0.  ],
       [0.  , 0.  , 0.  , 0.  , 0.  , 0.  , 3.16, 1.58],
       [0.  , 0.  , 0.  , 0.  , 0.  , 0.  , 0.  , 1.58],
       [0.  , 0.  , 0.  , 0.  , 0.  , 0.  , 0.  , 0.  ]])

In [47]: idx
Out[47]: 
array([[0, 6],
       [2, 6]])

请注意，由于 argpartition 的工作方式，idx 可能没有按距离排序的索引。要以这种方式强制执行，我们可以这样做 -

idx[dists[tuple(idx.T)].argsort()]

如何得到n个点中距离最大的m对点

How to get m pair of points among n points that have the largest distance between them

python

numpy

distance

euclidean-distance