6

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

我有 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 富有洞察力的评论，在优化问题陈述中将“返回（距离）总和”更改为“返回最小距离”。

4

2 回答 2

8

以下是您可以如何通过凸松弛来处理此组合优化问题。

让 D 是一个上三角矩阵，您的距离在上三角上。即其中 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 for all i, 1'*y = 10

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

您得到的 y 不必是（也可能不会是）二进制向量，但您可以通过多种方式将标量值转换为离散值。（最简单的可能是让 y_i 最高的 10 个条目中的 x 为 1，但您可能需要做一些更复杂的事情。）无论如何， y'*D*y 和 y 你得到的确实给出你是 x'*D*x 最优值的上限，所以如果你从 y 构造的 x 的 x'*D*x 非常接近 y'*D*y，你会对你的近似感到非常满意。

让我知道这是否不清楚，符号或其他。

于 2011-03-23T14:50:19.407 回答
2

好问题。

我不确定它是否可以以有效的方式准确解决，并且您基于集群的解决方案似乎是合理的。另一个值得关注的方向是局部搜索方法，例如模拟退火和爬山。

这是一个明显的基线，我会将任何其他解决方案与之进行比较：

  1. 重复 100 次：
  2. 贪婪地选择删除对目标函数影响最小的数据点并将其删除。
于 2011-03-23T05:56:25.787 回答