大多数相互远离的k元素(聚类？)

Question

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

我有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的深刻见解,在优化问题陈述中将"返回总和(距离)"更改为"返回最小距离".

Answer 1

以下是通过采用凸松弛来解决这种组合优化问题的方法.

设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表示所有i,1'*y = 10

这是(道德上)一个二次方案.(如果我们用D + D'代替D,它将成为一个真正的二次方案,你得到的y应该没有什么不同.)你可以使用一个现成的QP求解器,或者只是插入它您选择的凸优化求解器(例如cvx).

你得到的y不一定是(也可能不是)二进制向量,但是你可以通过多种方式将标量值转换为离散值.(最简单的可能是让y在y_i最高的10个条目中为1,但你可能需要做一些更复杂的事情.)无论如何,y'*D*y与你得到的y确实给出了你是x'*D*x的最佳值的上界,所以如果从y构造的x具有非常接近y'*D*y的x'*D*x,你可以对你的近似非常满意.

如果有任何不清楚,符号或其他原因,请告诉我.