寻找k个距离最远的点的子集。

Question

寻找k个距离最远的点的子集。

3

我有一组N个点（特别是二进制字符串），对于每个点，我都有一个离散度量（汉明距离），即给定两个点i和j，Dij是第i个点和第j个点之间的距离。我想找到一个k元素的子集（当然k< N），使得这k个点之间的距离尽可能大。换句话说，我想找到一种“边界点”，它覆盖了点空间中最大的区域。如果k=2，答案显然是可以在距离矩阵中查找两个最远的元素，但是如果k>2，我该如何推广这个问题呢？有什么建议吗？这是一个NP难问题吗？谢谢回答

- Dario Alise

你是否有一个特定的目标函数，其值域是完全有序的？（例如，您是否知道自己更喜欢[1,3,5]还是[2,3,4]这样的距离？） - user380772

不，我没有特定的目标函数：我只想选择这k个点，使它们彼此之间最远。我最初考虑了一种朴素的方法，但不幸的是它效果不佳：我只是将距离其他点最远的点作为起始点，然后找到距离该点最远的点，再计算剩余点与这两个点的距离，取平均值，并选择已选择的两个点中平均距离最大的点，直到选出k个点。 - Dario Alise

4个回答

1

这个问题被称为最大最小多样性问题（MMDP）。已知它是NP难的。然而，有一些算法可以在合理的时间内给出良好的近似解，例如这个算法。

我回答这个问题是因为几年前我也在寻找解决同样问题的算法，但是甚至都不知道该怎么称呼它。

- Tom

0

@mcdowella，我认为我可能没有很好地解释我的问题。在我的问题中，我有二进制字符串，并且对于每个字符串，我都可以使用汉明距离计算其与其他字符串之间的距离。通过这种方式，我得到了一个距离矩阵D，其中每个元素D（i，j）都有一个有限值。我可以将这个距离矩阵看作一个图：事实上，每一行都是图中的一个顶点，在列中，我有连接顶点Vi和Vj的弧的权重。由于我所解释的原因，这个图是完全的，它本身就是一个团。因此，如果我从原始图中随机选择k个顶点，我会得到一个子图，该子图也是完全的。从所有可能的顺序为k的子图中，我想选择最好的一个。什么是最好的呢？是一张图，使得顶点之间的距离尽可能大，但也尽可能均匀。假设我在我的子图中有两个顶点v1和v2，它们之间的距离为25，我还有另外三个顶点v3、v4和v5，使得d（v1，v3）=24，d（v1，v4）=7，d（v2，v3）=5，d（v2，v4）=22，d（v1，v5）=14，d（v1，v5）=14。

根据这些距离，我发现v3离v1太远了，但是离v2很近，而v4则与v2相距太远，但却靠近v1。因此，我更倾向于将顶点v5添加到我的子图中，因为它与其他两个顶点的距离更加均匀。希望现在我的问题已经清楚了。您认为您的表述已经正确了吗？

- Dario Alise

我回答了你的问题“这是一个NP难问题吗？” 我已经证明了它是的，因为我展示了一个解决你的问题的程序可以用来找到团。寻找团是NP难问题，因此这表明你的问题至少与团一样难。由于它是NP难问题，最好的选择是寻找某种启发式解决方案或近似解。我刚刚添加了另一个示例，为当您尝试最大化k个点之间距离总和的情况提供了一个示例。我认为这可能不是您想要的，但我不确定您确切想要什么。 - mcdowella

0

我声称找到k个点，使得这些点之间的最小距离或这些点之间距离的总和尽可能大的问题是NP完全问题，因此没有多项式时间的确切答案。这表明我们应该寻找某种启发式解决方案，因此这里有一个基于聚类思想的解决方案。我将描述如何最大化总距离。我认为它也可以用于最大化最小距离以及其他目标。

选择k个任意点，并记录每个点到其他点的距离之和。对于数据中的每个其他点，查看到k个选定点的距离之和，并查看是否用该点替换任何选定点会增加距离之和。如果是，则替换增加距离之和最多的点并继续。不断尝试，直到没有点可用于增加距离之和。这只是局部最优解，因此请使用另一组k个任意/随机点重复操作，以期找到更好的解决方案，直到您感到厌倦。

这继承了其聚类祖先的以下属性，对于测试至少可能有用：如果可以将点分成k类，使得同一类中任意两点之间的距离始终小于不同类中任意两点之间的距离，则当您找到k个点时，其中没有局部改进是可能的，这k个点应该都来自不同的类别（因为如果不是这样，从同一类中一对点中交换一个点会增加它们之间距离的总和）。

- mcdowella

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mcdowella · Accepted Answer

一种常见的概括是“找到k个点，使得这k个点中任意两点之间的最小距离尽可能大”。不幸的是，我认为这很困难，因为如果您能有效地做到这一点，您就可以有效地找到团。假设有人给您一个距离矩阵，并要求您找到一个k-团。创建另一个矩阵，在原始矩阵的无限位置上输入1，在原始矩阵具有任何有限距离的位置上输入1000000。现在，新矩阵中一组k个点，其中该组中任意两点之间的最小距离为1000000，对应于原始矩阵中一组k个点，它们彼此相连 - 一个团。

这种构造没有考虑到点对应于比特向量，它们之间的距离是汉明距离，但我认为可以扩展来处理这个问题。为了证明能够解决原始问题的程序可以用于查找团，我需要展示：给定邻接矩阵，我可以为每个点构造一个比特向量，使得在图中相连的点（邻接矩阵中为1）之间的距离大约为A，而不相连的点之间的距离为B，其中A > B。请注意，A可能非常接近B。事实上，三角不等式将强制执行这种情况。一旦我展示了这一点，距离彼此都为A的k个点（因此最小距离为A，距离总和为k(k-1)A/2）将对应于一个团，因此找到这样的点的程序将找到团。

为了实现这一点，我将使用长度为kn(n-1)/2的位向量，其中k将随着n的增长而增加，因此位向量的长度可能高达O(n^3)。我可以这样做是因为这仍然只是n的多项式。我将把每个位向量分成n(n-1)/2个字段，每个字段的长度为k，其中每个字段负责表示两个点之间的连接或无连接。我声称存在一个长度为k的位向量集合，使得它们之间的所有距离都大致相同，除了其中两个比其他位向量更接近。我还声称存在一个长度为k的位向量集合，使得它们之间的所有距离都大致相同，除了其中两个比其他位向量更远。通过在这两个不同的集合之间进行选择，并通过将更近或更远的一对分配给当前位向量中的n(n-1)/2个字段所拥有的两个点，我可以创建一个具有所需距离模式的位向量集合。

我认为这些存在是因为有一种构造方式可以高概率地创建出这样的模式。创建长度为k的n个随机比特向量，任意两个比特向量之间的期望海明距离为k/2，方差为k/4，标准差为sqrt(k)/2。对于较大的k，我们预计不同距离之间会相当相似。要在该集合中创建非常接近的两个点，请将一个点复制为另一个点。要创建非常远的两个点，请使其中一个成为另一个的反码（一个比特向量中为0的位在另一个中为1，反之亦然）。

给定任意两个点，它们彼此之间的期望距离为(n(n-1)/2 - 1)k/2 + k（如果它们应该很远）和(n(n-1)/2 -1)k/2（如果它们应该很接近）。我声称，通过使k足够大，期望距离将胜过随机变异性，我将得到与我要求的A和B非常相似的距离，但没有证明。