最相距的 k 个元素（聚类？）

我有一个简单的机器学习问题：

我有 n (~110) 个元素，以及所有成对距离的矩阵。我想选择相距最远的 10 个元素。也就是说，我想要

Maximize:
  Choose 10 different elements.
  Return min distance over (all pairings within the 10).

我的距离度量是对称的并且遵循三角不等式。

我可以使用什么样的算法？我的第一直觉是执行以下操作：

1. 将 n 个元素聚类为 20 个 集群。
2. 将每个簇替换为 该簇的元素是 距平均元素最远 原来的n.
3. 使用蛮力来解决 剩下20个的问题 候选人。幸运的是，20选10是 只有 184,756。

编辑：感谢 etarion 的富有洞察力的评论，将优化问题陈述中的“返回（距离）总和”更改为“返回最小距离”。

以下是如何通过采用凸松弛来解决这个组合优化问题。

令 D 为上三角矩阵，距离位于上三角上。 IE。其中 i

那么您的目标是最大化 x'*D*x，其中 x 是二进制值，其中 10 个元素设置为 1，其余元素设置为 0。（将 x 中的第 i 个条目设置为 1 类似于选择第 i 个元素作为您的10 个元素。）

处理这样的组合问题的“标准”凸优化是放宽约束，使得 x 不需要是离散值。这样做会给我们带来以下问题：

最大化 y'*D*y 满足：0

这是（道德上）一个二次规划。 （如果我们用 D + D' 替换 D，它将成为一个真正的二次规划，并且您得到的 y 应该没有什么不同。）您可以使用现成的 QP 求解器，或者只需将其插入到您选择的凸优化求解器（例如 cvx）。

您得到的 y 不需要（并且可能不会）是二进制向量，但您可以通过多种方式将标量值转换为离散值。 （最简单的可能是让 x 在 y_i 最高的 10 个条目中为 1，但您可能需要做一些更复杂的事情。）在任何情况下，y'*D*y 与您得到的 y 确实给出您为 x'*D*x 的最佳值设定了上限，因此，如果您从 y 构造的 x 的 x'*D*x 非常接近 y'*D*y，您会对您的近似值感到非常满意。

如果有任何不清楚的地方，无论是符号还是其他，请告诉我。