Как получить m пару точек среди n точек, которые имеют наибольшее расстояние между ними

Question

Скажите, у меня есть следующие точки, определенные в одномерном пространстве:

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

Я хочу получить m пар точек среди этих n точек, которые имеют наибольшее евклидово расстояние между ними (если m равно 1в этом случае будет 1,4142 и 0)

Я попытался получить попарное расстояние с помощью:

from scipy.spatial.distance import pdist, cdist

cdist(x,x, 'seuclidean')

из этой части, однако я не уверен, как сделать остальное.

Answer 1

Мы могли бы использовать 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.

Пример выполнения -

# 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()]

Answer 2

Чтобы связать каждую точку с ее самым дальним аналогом, вы можете использовать:

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

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