数据集中两点之间的最大距离并识别这些点

Question

我有一个由几个点的 x,y,z 坐标组成的矩阵。我想找到极值点，即相距最远的两点。

我可以在 matlab 中找到一种方法，但我需要在 Python 中使用它

这是matlab中的代码

A = randint(500,3,[-5 5]);
D=pdist(A);
D=squareform(D);
[N,I]=max(D(:));
[I_row, I_col] = ind2sub(size(D),I);

pdist 给出点对（i，j）之间的距离。squareform 给出矩阵输出 在最后两个步骤中，我尝试找到矩阵 I_row、I_col 的索引。

点 I_row 和 I_col 具有最大距离..

任何人都可以建议我在 python 中使用一种有效的方法，因为我所有的其他代码都在 python 中。

Answer 1

这里的所有其他答案都需要O(N^2) 的时间和空间。这太可怕了。

相反，要认识到数据集中最远的两个点位于集合的凸包上。由于船体可以在 3D 中以O(N log N)时间计算，这形成了有效的预过滤器。在我对具有 16,000,000 个点的数据集的测试中，凸包仅包含 420 个点。

船体上最远的点可以在O(H log H)时间内找到，尽管这在 Python 中更难实现。所以我们可以在那个时候回退到O(N^2) cdist 解决方案。

import numpy as np
from scipy.spatial import ConvexHull
from scipy.spatial.distance import cdist

N = 16000000

# Find a convex hull in O(N log N)
points = np.random.rand(N, 3)   # N random points in 3-D

# Returned 420 points in testing
hull = ConvexHull(points)

# Extract the points forming the hull
hullpoints = points[hull.vertices,:]

# Naive way of finding the best pair in O(H^2) time if H is number of points on
# hull
hdist = cdist(hullpoints, hullpoints, metric='euclidean')

# Get the farthest apart points
bestpair = np.unravel_index(hdist.argmax(), hdist.shape)

#Print them
print([hullpoints[bestpair[0]],hullpoints[bestpair[1]]])

Answer 2

如果有scipy，那么您就拥有了大多数 Matlab 核心函数的完全相同的功能：

from numpy import random, nanmax, argmax, unravel_index
from scipy.spatial.distance import pdist, squareform

A = random.randint(-5,5, (500,3))
D = pdist(A)
D = squareform(D);
N, [I_row, I_col] = nanmax(D), unravel_index( argmax(D), D.shape )

您还可以使用以下命令在纯 python 中获取它itertools：

from itertools import combinations
from random import randint

A = [[randint(-5,5) for coord in range(3)] for point in range(500)]

def square_distance(x,y): return sum([(xi-yi)**2 for xi, yi in zip(x,y)])    

max_square_distance = 0
for pair in combinations(A,2):
    if square_distance(*pair) > max_square_distance:
        max_square_distance = square_distance(*pair)
        max_pair = pair