python - 给定坐标，如何获得 K 个最远的点？

Question

我们有 10000 行 ages (float), titles (enum/int), scores (float), ... 的无聊 CSV .

我们有 N 列，每列都有一个表中的 int/float 值。

你可以把它想象成 ND 空间中的点

我们想选择 K 个点，它们之间的距离最大化。

因此，如果我们在一个紧密排列的集群中有 100 个点，而在远处有 1 个点，我们会得到这样的三个点:
或这个

对于 4 点，它会变得更有趣并在中间选择一些点。
那么如何从 N(具有任何复杂性)中选择 K 个最远的行(点)？它看起来像一个具有给定分辨率的 ND 点云“三角测量”，但不适用于 3d 点。
我为 K=200 和 N=100000 和 ND=6(可能是基于 KDTree、SOM 或三角剖分的多重网格或人工神经网络......)寻找一种相当快速的方法(近似 - 不需要精确的解决方案)。

Answer 1

根据过去对非常相似问题的经验，计算每组 K 点内所有对的平均欧几里德距离然后取最大平均值的简单解决方案非常有效。正如上面有人指出的那样，可能很难避免所有组合(不是所有对)的循环。因此，所有这些的可能实现如下:

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

Npoints = 3 # or 4 or 5...
# making up some data:
data = np.matrix([[3,2,4,3,4],[23,25,30,21,27],[6,7,8,7,9],[5,5,6,6,7],[0,1,2,0,2],[3,9,1,6,5],[0,0,12,2,7]])
# finding row indices of all combinations:
c = [list(x) for x in itertools.combinations(range(len(data)), Npoints )]

distances = []
for i in c:    
    distances.append(np.mean(pdist(data[i,:]))) # pdist: a method of computing all pairwise Euclidean distances in a condensed way.

ind = distances.index(max(distances)) # finding the index of the max mean distance
rows = c[ind] # these are the points in question