找到k个最远点的子集

Question

我有一组N个点(特别是这个点是二进制字符串)，并且对于它们中的每个点，我都有一个离散的度量(汉明距离)，使得给定两个点，i和j，Dij是第i个点和第j个点之间的距离。我希望找到k个元素的子集(当然，k2时，我如何推广这个问题？有什么建议吗？这是NP难问题吗？谢谢你的回答

Answer 1

一种概括是“找到k个点，使得这k个点中的任何两个之间的最小距离尽可能大”。

不幸的是，我认为这很难，因为我认为如果你能有效地做到这一点，你就可以有效地找到集团。假设有人给了你一个距离矩阵，让你找一个k-团。创建另一个矩阵，其中原始矩阵具有无穷大的项1，以及原始矩阵具有任意有限距离的项1000000。现在，新矩阵中任何两个点之间的最小距离为1000000的k个点的集合对应于原始矩阵中的k个点的集合，这些点都相互连接-一个集团。

这种构造没有考虑到这样一个事实，即点对应于位向量，并且它们之间的距离是汉明距离，但我认为它可以扩展以应对这一点。为了证明能够解决原始问题的程序可以用来寻找集团，我需要证明，给定一个邻接矩阵，我可以为每个点构造一个位向量，使得图中连接的点对，因此邻接矩阵中的1，彼此之间的距离大致为A，而图中未连接的点对彼此之间的距离为B，其中A> B。请注意，A可能非常接近B。事实上，三角形不等式将迫使这种情况发生。一旦我证明了这一点，k个点彼此之间的距离A(因此最小距离A，距离之和为k(k-1)A/2)将对应于一个集团，因此找到这些点的程序将找到集团。

为此，我将使用长度为kn( n -1)/2的位向量，其中k将随n增长，因此位向量的长度可以达到O(n^3)。我会将每个位向量分成n (n-1)个/2字段，每个字段的长度为k，其中每个字段负责表示两点之间的连接或缺少连接。我声称有一组长度为k的比特向量，使得这些k长的比特向量之间的所有距离都大致相同，除了它们中的两个比其他的更近。我还声称有一组长度为k的位向量，因此它们之间的所有距离都大致相同，除了其中两个比其他的距离更远。通过在这两个不同的集合之间进行选择，并且通过将更近的或更远的对分配给拥有比特矢量内的n(n-1)个/2字段的当前比特字段的两个点，我可以创建具有所需距离模式的比特矢量集合。

我认为这些是存在的，因为我认为有一种结构可以很高概率地创建这样的模式。创建n个长度为k的随机位向量。任何两个这样的位向量的预期汉明距离为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的距离。

Answer 2

@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添加到我的子图中，因为它以一种更统一的方式与其他两个顶点相距较远。我希望现在我的问题清楚了。你认为你的提法已经正确了吗？

Answer 3

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

选取k个任意点，并记下每个点到其他点的距离之和。对于数据中的每个其他点，查看到k个选定点的距离总和，并查看用该点替换任何选定点是否会增加总和。如果是，则替换增加总和最多的任何点并继续。继续尝试，直到没有一个点可以用来增加总和。这只是一个局部最优，所以重复使用另一组k个任意/随机的点，希望找到一个更好的，直到你厌倦为止。

这继承了它的聚类先于以下属性，这可能至少对测试有用:如果点可以被分成k个类，使得同一类中的任何两个点之间的距离总是小于不同类中任何两个点之间的距离，那么，当您找到k个不可能进行局部改进的点时，这k个点应该都来自不同的类(因为如果不是这样，交换来自同一类的一对点中的一个将增加它们之间的距离之和)。