获得最大平均距离点的子集

Question

我有N点。我知道他们的所有配对距离。我需要从它们中选择K点，这样平均成对距离将是最大的。我只有虚拟的想法来迭代每一个点。

你有更聪明的想法如何获得这样一个子集吗？

一般情况下解决这个问题是很好的，没有任何假设，但是如果有帮助的话：N在10^3-10^4，K在10^2左右。

我的虚拟想法：我从点#1开始搜索最遥远的点，所以我有一块2点，接下来我搜索第三个点，它与这2个点的平均距离最大，等等，直到我收集K点。对于所有N个点应重复此过程作为起始值。最后，我将得到N个K点阵列。从他们那里我可以选择一个平均距离最大的。

Answer 1

我不是百分之百肯定，但这听起来像是一个NP难题。

作为近似，您可以执行K-中值聚类并返回结果集群代表作为结果。聚类基本尝试

最小化属于同一集群的点的距离(这对您来说并不重要)，并使来自不同集群的点之间的距离最大化(这就是您想要的)。

编辑：

再想一想，我想，你应该尝试在数据集的外部极限上搜索点，以便最大限度地扩大平均成对距离。因此，您可以计算(凸包)壳和从中挑选点，也许可以重新计算船体，无论何时你选择一个点。或者，你可以从(a)点开始，从(a)点开始搜索最远点(b)，然后从(b)点开始搜索最远点(c)，以此类推(避免取两次点，也许在你选完点后移除)。这将确保您在数据集的边框中选择点。