1

我正在寻找以下问题的有效解决方案：对于 n 维欧几里得空间中的给定点集，找到该集合中的此类成员，以最小化与集合中其他点的总距离。

明显的幼稚方法是二次的，所以我正在寻找不那么二次的方法。

我的第一个想法是，我所需要的只是找到边界球的中心，然后在集合中找到离该点最近的点。但这实际上是不正确的，想象一下直角三角形 - 它的所有顶点都与这样的中心等距，但是，恰好一个顶点符合我们的要求。

如果有人能对这个问题有所了解，那就太好了。

4

2 回答 2

2

我正在编造这个，但是凸优化中“集合的最佳点”和“最佳点”之间似乎存在密切联系。

您的得分函数是距离的总和。每个距离都是凸 U 形（在这种情况下是 V 形），因此它们的总和是凸 U 形。特别是除了集合中的点外，它在任何地方都有一个非常好的导数，而且这个导数是乐观的——如果你取一个点的值及其导数，忽略你正在查看的点的任何点，那么基于这个的预测将是乐观的 - 使用导数形成的线几乎完全位于正确答案的下方，但在一个点上掠过它。

这导致以下算法：

反复

随机选择一个点，看看是否是迄今为止最好的点。如果是这样，请注意它。取此时距离之和的导数。使用这个和那个点的值来计算出每个其他点的预测距离总和，并尽可能地丢弃这个预测比最佳答案差的点（尽管你仍然需要考虑它们在计算距离和导数时）。这些将是通过垂直于导数的所选点绘制的平面远端上的点。

现在也放弃选择的点作为竞争者，如果还有需要考虑的点，请重复。

我希望这在随机选择的点上类似于 n log n。但是，如果点集形成 n 维的正多边形的顶点，那么它将花费 N^2，每次仅丢弃所选点 - 实际上 N 个点中的任何一个都是正确的答案，并且它们都具有相同的彼此距离的总和。

我当然会投票赞成任何能够确认或否认在凸目标函数下找到一组给定点中最好的这一一般原则的人。

好的——我对此很感兴趣，可以对其进行编程——所以如果有人关心的话，我有 200 多行 Java 代码可以在这里转储。在 2 维中它非常快，但是在 20 维中，您仅获得两倍左右 - 这是可以合理理解的 - 每次迭代都通过将问题投影到一条线上并切掉线外的一小部分点来切断点. 一个随机选择的点距离中心的距离大约是其他点的一半 - 并且非常粗略地，您可以预期投影会切断除 1/2 的第 d 根的某个倍数之外的所有内容，以便 d 增加分数您可以在每次迭代中丢弃的点数减少。

于 2013-08-31T11:47:26.567 回答
2

最小化到所有点的距离是它们的平均值。只是一个猜测，但在你找到平均值之后，你可以找到最接近它的点。正如评论中正确指出的那样，中位数而不是平均值实际上会使距离最小化（平均值将使平方距离最小化）。中位数也可以计算O(n)。对于高维数据集，这个解决方案当然是，维数O(n*m)在哪里。m

还有一些链接：

在此处查看已接受的答案：查找距位置最小总距离的点的算法

以及 mcdowella 提供的链接：http ://en.wikipedia.org/wiki/Geometric_median

于 2013-08-31T07:56:57.740 回答