2

我有点N。我知道他们的所有成对距离。我需要从中选择K点，以使平均成对距离最大。我只有一个愚蠢的想法来遍历每个点。

您是否有更聪明的想法如何获得这样的子集？

一般地解决这个问题会很好，没有任何假设，但如果有帮助的话：N大约是 10^3-10^4，K大约 10^2。

我的虚拟想法： 我从点＃1开始搜索最远的点，所以我有一大块2点，接下来我搜索第三个点，它与这两个点的平均距离最大，依此类推，直到我将收集 K 点。应将所有 N 个点作为起始值重复此过程。最后我会得到 N 个 K 点的数组。我可以从中选择一个平均距离最大的。

4

2 回答 2

1

我不是 100% 确定，但这听起来像是一个 NP-Hard 问题。

作为近似值，您可以执行K 中值聚类并返回结果聚类代表作为结果。聚类基本上试图
最小化属于同一聚类的点的距离（这对你来说并不重要），并最大化来自不同聚类的点之间的距离（这就是你想要的）。

编辑：

我想，再想一想，你会想尝试在数据集的外部边界上搜索点，以最大化平均成对距离。因此，您可以计算（凸）外壳并从那里选择点，也许在您选择一个点时重新计算外壳。或者您可以从点 (a) 开始，从 (a) 搜索最远的点 (b)，然后从 (b) 搜索最远的点 (c)，依此类推（避免选择两次点，可能通过删除在你挑选它们之后）。这将确保您在数据集的边界处选择点。

于 2017-12-13T08:25:04.227 回答
1

这可以看作是具有 N 个顶点的完整图上的最重 k 子图问题的一个特例，其中权重满足三角不等式。

问题的一般情况是 NP-hard，我猜测上述限制不足以使其成为多项式，尽管它们当然可以承认一些启发式方法。

对于近似解决方案，您是否评估了贪心解决方案或贪心随机抽样解决方案？

附录

我最近遇到了一篇论文，讨论了权重满足三角不等式的情况下的最大分散和最重子图问题：

Hassin 等人，最大色散的近似算法，运筹学快报21（1997），第 3 期。3, 133–137, DOI 10.1016/S0167-6377(97)00034-5。

本文第 3 节针对该问题对应的情况提供了一个简单的近似 O( n 2 ) 贪心算法，作者证明该结果至少是最大值的 1/2。

于 2017-12-13T14:37:50.910 回答