artificial-intelligence - 最相距的 k 个元素(聚类？)

Question

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

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

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

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

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

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

<小时/>

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

Answer 1

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

设 D 为上三角矩阵，距离位于上三角形上。 IE。其中 i < j，D_i,j 是元素 i 和 j 之间的距离。 (想必，对角线上也会有零。)

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

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

最大化 y'*D*y 服从:0 <= y_i <= 1 对于所有 i，1'*y = 10

这是(道德上)一个二次规划。 (如果我们将 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，您会对您的近似值感到非常满意。

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