cluster-analysis - 在欧几里得空间中寻找“最紧”的子集

Question

我在点 x_1, x_2, ... x_n \in R^d 中给出。我希望找到 k 点的子集，使得这些 k 点之间的距离之和最小。天真地这是一个 O(n 选择 k) 问题，但我正在寻找一种更快的算法。

我可以想到两种替代的等效公式：

1. 最小边权团问题：将点视为一个图，边权重是距离，并找到最小权重团。这相当于最大边权重问题，已知它是 NP 完全的。但是，我知道我的图表嵌入在 R^d 中，并且所有权重都是正数，所以这可能会有所帮助吗？

2. 最小无约束子矩阵问题：给定对称距离矩阵，我想找到一个总和最小的 kXk 次要。

我会很感激这方面的任何帮助。

Answer 1

最明显的优化实际上并不需要任何不同的公式。

首先贪婪地找到一个接近最佳的候选人。尝试通过交换成员在线性时间内对其进行细化。然后进行详尽的搜索，但只要新候选者比贪婪的候选者更差，就停止以修剪搜索空间。

例如

1. 计算平均值
2. 按与均值的平方距离对对象进行排序
3. 依次测试所有长度为 k 的 nk 个区间，选择最好的
4. 对于任何未选择的对象，尝试将其与选择的对象之一交换，如果它提高了分数

现在你应该有一个相当好的修剪候选者。

然后做一个详尽的搜索，只要它比这个候选人更差就停下来。

注意：步骤 1-3 是从快速凸包算法中获得的灵感。