根据过去关于类似问题的经验，一种简单的解决方案非常有效，该解决方案可以计算每对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,9],[5,5,6,7],[0,1,2],[3,9,5],12,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

我提出一个近似的解决方案。这个想法是从我将在下面解释的方式中选择的K个点开始，然后反复遍历这些点，将当前点替换为该点，在不属于该点的N-K + 1个点中，包括当前值，它使距集合点的距离之和最大。此过程将导致一组K点，其中任何单个点的替换都将导致该组点之间的距离之和减小。

为开始该过程，我们获取最接近所有点均值的K个点。这样，我们很有可能在第一个循环中将K点的集合散布到接近其最佳点的位置。随后的迭代将朝着距离总和的最大值调整K点集，对于当前的N，K和ND值，仅需几秒钟即可达到。为了防止在极端情况下出现过多的循环，我们仍然限制了循环次数。

当迭代不能改善K点之间的总距离时，我们将停止迭代。当然，这是局部最大值。在不同的初始条件下，或一次允许多个替换，可以达到其他局部最大值，但我认为这不值得。

必须调整数据，以使每个维度中的单位位移具有相同的重要性，即，使欧几里得距离有意义。例如，如果您的维度是薪水和未调整的孩子数，则该算法可能会得出集中在极端薪水区域的结果，而忽略那个有10个孩子的人。为了获得更实际的输出，您可以将薪水和孩子的数量除以他们的标准差，或者除以其他估算值，使薪金差异与孩子数量的差异可比。

为了能够绘制随机高斯分布的输出，我在代码中设置了ND = 2，但是根据您的要求设置ND = 6没问题（除非您无法绘制它）。

import matplotlib.pyplot as plt
import numpy as np
import scipy.spatial as spatial

N,K,ND = 100000,200,2
MAX_LOOPS = 20

SIGMA,SEED = 40,1234
rng = np.random.default_rng(seed=SEED)
means,variances = [0] * ND,[SIGMA**2] * ND
data = rng.multivariate_normal(means,np.diag(variances),N)

def distances(ndarray_0,ndarray_1):
    if (ndarray_0.ndim,ndarray_1.ndim) not in ((1,2),(2,1)):
        raise ValueError("bad ndarray dimensions combination")
    return np.linalg.norm(ndarray_0 - ndarray_1,axis=1)

# start with the K points closest to the mean
# (the copy() is only to avoid a view into an otherwise unused array)
indices = np.argsort(distances(data,data.mean(0)))[:K].copy()
# distsums is,for all N points,the sum of the distances from the K points
distsums = spatial.distance.cdist(data,data[indices]).sum(1)
# but the K points themselves should not be considered
# (the trick is that -np.inf ± a finite quantity always yields -np.inf)
distsums[indices] = -np.inf
prev_sum = 0.0
for loop in range(MAX_LOOPS):
    for i in range(K):
        # remove this point from the K points
        old_index = indices[i]
        # calculate its sum of distances from the K points
        distsums[old_index] = distances(data[indices],data[old_index]).sum()
        # update the sums of distances of all points from the K-1 points
        distsums -= distances(data,data[old_index])
        # choose the point with the greatest sum of distances from the K-1 points
        new_index = np.argmax(distsums)
        # add it to the K points replacing the old_index
        indices[i] = new_index
        # don't consider it any more in distsums
        distsums[new_index] = -np.inf
        # update the sums of distances of all points from the K points
        distsums += distances(data,data[new_index])
    # sum all mutual distances of the K points
    curr_sum = spatial.distance.pdist(data[indices]).sum()
    # break if the sum hasn't changed
    if curr_sum == prev_sum:
        break
    prev_sum = curr_sum

if ND == 2:
    X,Y = data.T
    marker_size = 4
    plt.scatter(X,Y,s=marker_size)
    plt.scatter(X[indices],Y[indices],s=marker_size)
    plt.grid(True)
    plt.gca().set_aspect('equal',adjustable='box')
    plt.show()

输出：

将数据拆分为3个等距的高斯分布，输出为：

假设您将具有N（10000）行和D维（或特征）的csv文件读入N*D martixX。您可以计算每个点之间的距离并将其存储在距离矩阵中，如下所示：如下：

import numpy as np
X = np.asarray(X) ### convert to numpy array
distance_matrix = np.zeros((X.shape[0],X.shape[0]))
for i in range(X.shape[0]):
    for j in range(i+1,X.shape[0]): 
    ## We compute triangle matrix and copy the rest. Distance from point A to point B and distance from point B to point A are the same. 
        distance_matrix[i][j]= np.linalg.norm(X[i]-X[j]) ## Here I am calculating Eucledian distance. Other distance measures can also be used.

        #distance_matrix = distance_matrix + distance_matrix.T - np.diag(np.diag(distance_matrix)) ## This syntax can be used to get the lower triangle of distance matrix,which is not really required in your case.
        K = 5 ## Number of points that you want to pick

        indexes = np.unravel_index(np.argsort(distance_matrix.ravel())[-1*K:],distance_matrix.shape)

        print(indexes)

最下面的底线：处理多个等距的点和“维数的诅咒”将是比仅找到点更大的问题。剧透警报：结局出人意料。

我认为这是一个有趣的问题，但我对某些答案感到困惑。我认为部分原因是由于提供了草图。毫无疑问，您注意到答案看起来很相似-2d，带有群集-即使您指出需要更大的范围。因为其他人最终会看到这种情况，所以我将慢慢地思考一下，所以请尽我所能。

从一个简化的示例开始，看看我们是否可以使用易于掌握的数据来概括一个解决方案，而线性2D模型则是最简单的。

但是，我们不需要计算所有 距离。我们只需要那些极端。这样我们就可以采用顶部和底部的几个值：

right = lin_2_D.nlargest(8,['x'])
left = lin_2_D.nsmallest(8,['x'])

graph = sns.scatterplot(x="x",y="y",data=lin_2_D,color = 'gray',marker = '+',alpha = .4)
sns.scatterplot(x = right['x'],y = right['y'],color = 'red')
sns.scatterplot(x = left['x'],y = left['y'],color = 'green')

fig = graph.figure
fig.set_size_inches(8,3)

到目前为止，我们所拥有的：在100点中，我们不再需要计算它们之间84点之间的距离。通过将结果放在一侧并检查与另一侧之间的距离，我们可以进一步删除剩下的内容。

您可以想象这样一种情况，您有几个数据点偏离趋势线，这些数据点可以通过取最大或最小y值来捕获，并且所有这些点看起来都像Walter Tross的顶部图。再加上几个额外的群集，您会得到他底图的外观，看来我们在提出相同的观点。

在此处停止的问题是您提到的要求是您需要适用于任意尺寸的解决方案。

不幸的是，我们遇到了四个挑战：

挑战1：：当您增加尺寸时，可能会遇到很多情况，其中在寻找中点时会有多种解决方案。因此，您正在寻找 k 最远的点，但是有大量同样有效的可能解决方案，并且无法对它们进行优先排序。这里有两个超级简单的例子说明了这一点：

A）在这里，我们只有四个点，只有两个维度。您真的比这更容易，对吗？从红色到绿色的距离很小。但是，尝试找到下一个最远的点，您会看到两个黑点都与红色和绿色点等距。想象一下，您希望使用第一个图形获得最远的六个点，您可能有20个或更多等距的点。

编辑：我只是注意到红色和绿色的点位于圆的边缘而不是中心，稍后我将进行更新，但要点相同。

B）这是非常容易想象的：想像D＆D 4面模具。三维空间中的四个数据点都是等距的，因此被称为基于三角形的金字塔。如果您正在寻找最接近的两个点，哪两个？您有4种选择2（又名6）的组合。摆脱有效的解决方案可能会有点问题，因为您总是会遇到诸如“为什么我们要摆脱这些而不是这个？”之类的问题。

挑战2： The Curse of Dimensionality。纳夫·赛义德（Nuff Said）。

挑战3 维度诅咒的复仇因为您要寻找最远的点，所以必须为每个点设置x，y，z ... n坐标，否则就必须进行插补他们。现在，您的数据集更大，更慢。

挑战4 因为您正在寻找最远的点，所以诸如ridge和套索之类的降维技术将无用。

那么，该怎么办？

没事。

等等。 什么？！？

并非完全，准确，也没有什么。但是没有什么疯狂的。取而代之的是，依靠一种可理解且计算容易的简单启发式方法。保罗·凯南（Paul C. Kainen）说得很好：

直觉上，当情况足够复杂或不确定时， 只有最简单的方法才有效。但是令人惊讶的是， 基于这些可靠适用技术的常识启发法 可以产生几乎肯定是最佳的结果。

在这种情况下，您没有维数的诅咒，而是维数的祝福。的确，您有很多点，并且当您寻找其他等距点（ k ）时，它们会线性缩放，但是空间的总维数将增加至维数。最远的 k 个点对总点数无关紧要。随着维数的增加，甚至 k ^ 2 也变得微不足道。

现在，如果您的尺寸较小，我会选择它们作为解决方案（NumPy或Pandas中使用嵌套嵌套循环的除外）。

如果我处于您的位置，我会在思考如何将这些其他答案中的代码用作基础，并且也许想知道为什么我应该信任它，而不是它为如何布局提供了框架思考这个话题。当然，应该有一些数学运算，也许有人要说同样的话。

让我参考Computer Intensive Methods in Control and Signal Processing的第18章，并通过类推与一些沉重的（-ish）数学进行类推。从上图（边缘带有彩色圆点的图形）中可以看出，删除了中心，特别是如果您遵循了删除极端y值的想法。尽管你在盒子里放了一个气球。您也可以在多维数据集中的球体中执行此操作。将其提升为多个维度，您将在超立方体中拥有一个超球体。您可以在read more about that relationship这里。

最后，让我们开始试探：

• 选择每个维度上具有最大或最小值的点。当/如果您用尽了它们，则在最小值/最大值中没有一个值时，请选择与那些值接近的值。本质上，您是在选择框的角。对于2D图形，您有四个点，对于3D图形，您具有框的8个角（2 ^ 3）。

更准确地说，这将是投影到3d的4d或5d（取决于您如何分配标记的形状和颜色）。但是您可以轻松地看到此数据云如何为您提供所有维度。

这里是学习的快速检查；为了简便起见，请忽略颜色/形状方面：很容易以图形的方式暗示您对 k 个点没有任何问题，而无需确定可能会更接近的点。如果您拥有 k k +1）处于质心。因此，这里是检查：如果您有更多积分，它们将在哪里？我想我必须把它放在最底下-减价的限制。

因此，对于6D数据云， k 的值小于64（非常好，我们将在稍后看到65）点非常容易。但是...

• 如果您没有数据云，但具有线性关系的数据，则将获得2 ^（D-1）点。因此，对于线性2D空间，您有一条直线，对于线性3D空间，您将有一个平面。然后是菱形等。即使您的形状是弯曲的，也是如此。我不是自己制作这张图，而是使用Inversion Labs在Best-fit Surfaces for 3D Data
上的一篇很棒的帖子中的一个

• 如果点数 k 小于2 ^ D，则需要一个过程来确定不使用的内容。 Linear discriminant analysis应该在您的候选清单中。也就是说，您可以通过随机选择一个解决方案来满足该解决方案。

• 对于一个附加点（k = 1 + 2 ^ D），您正在寻找一个与边界空间的中心尽可能近的点。

• 当k> 2 ^ D时，可能的解决方案将不按几何比例而是按比例缩放。这似乎并不直观，所以让我们回到两个圈子。对于2D，您只有两点可以等距。但是，如果那是3D空间并围绕直线旋转点，则现在环形的任何点都可以作为 k 的解决方案。对于3D示例，它们将是一个球体。从其上的超球（n球）。同样，2 ^ D缩放。

最后一件事：如果您还不熟悉xarray，应该认真看一下。

希望所有这些都对您有所帮助，我也希望您能阅读链接。值得的。

*它将是相同的形状，位于中心，顶点在1/3标记处。就像有27个六面骰子，形状像一个巨大的立方体。每个顶点（或最接近它的点）将解决该问题。您原来的 k +1也必须重新定位。因此，您将在8个顶点中选择2个。最后一个问题：是否值得计算这些点之间的距离（记住对角线比边缘稍长），然后将其与原始2 ^ D点进行比较？坦率地说，不。 Satifice解决方案。

如果您有兴趣获取最远的点，则可以利用为最近的邻居开发的所有方法，只需提供一个不同的“度量”即可。

例如，使用scikit-learn的最近邻居和距离指标工具，您可以执行以下操作

import numpy as np
from sklearn.neighbors import BallTree
from sklearn.neighbors.dist_metrics import PyFuncDistance
from sklearn.datasets import make_blobs
from matplotlib import pyplot as plt


def inverted_euclidean(x1,x2):
    # You can speed this up using cython like scikit-learn does or numba
    dist = np.sum((x1 - x2) ** 2)
    # We invert the euclidean distance and set nearby points to the biggest possible
    # positive float that isn't inf
    inverted_dist = np.where(dist == 0,np.nextafter(np.inf,0),1 / dist)
    return inverted_dist

# Make up some fake data
n_samples = 100000
n_features = 200
X,_ = make_blobs(n_samples=n_samples,centers=3,n_features=n_features,random_state=0)

# We exploit the BallTree algorithm to get the most distant points
ball_tree = BallTree(X,leaf_size=50,metric=PyFuncDistance(inverted_euclidean))

# Some made up query,you can also provide a stack of points to query against
test_point = np.zeros((1,n_features))
distance,distant_points_inds = ball_tree.query(X=test_point,k=10,return_distance=True)
distant_points = X[distant_points_inds[0]]

# We can try to visualize the query results
plt.plot(X[:,0],X[:,1],".b",alpha=0.1)
plt.plot(test_point[:,test_point[:,"*r",markersize=9)
plt.plot(distant_points[:,distant_points[:,"sg",markersize=5,alpha=0.8)
plt.show()

将绘制以下内容：

您可以在以下几点上进行改进：

1. 我使用numpy实现了inverted_euclidean距离函数，但是您可以尝试做scikit-learn do with their distance functions的同事并在cython中实现它们。您也可以尝试使用numba对其进行编译。
2. 也许欧几里德距离不是您想要用来找到最远点的度量，所以您可以自由地实现自己的目标，也可以随意滚动scikit-learn provides。

使用球树算法（或KdTree算法）的好处是，对于每个查询点，您必须进行log(N)比较才能找到训练集中最远的点。我想建立球树本身，还需要进行log(N)比较，因此最后如果您想在球树训练集中（{{1 }}），其复杂度几乎为X（其中O(D N log(N))是要素数量），随着D的增加，复杂度将增加到O(D N^2)。