3

我正在尝试实现爬山算法，以根据特定标准从一组位置中选择哪些位置。多达 5000 个地点可供选择。

这些标准之一是地理分散，因此我需要能够为我的位置的任何子集分配一个代表分散的值。

每个位置都有纬度和经度数据。

速度是一个问题，这就是为什么我需要一些启发式方法来估计一组特定位置（即可能的解决方案）的分散程度。

我曾尝试将潜在解决方案中每个位置的成对距离相加，但这证明太慢了。

然后，我尝试了在我的潜在解决方案中与所有位置中心的距离总和，这被证明更快，但效果不佳。使用这种方法将有利于几个位置集群。

任何其他建议将不胜感激。

4

2 回答 2

0

首先，你能重申一下成对和的意思吗？我在问，因为听起来你形成了所有可能的配对，这将是非常低效的。如果是这种情况，如何首先找到 1) 最近的邻居，然后 2) 最长的路径？

1）如果我没记错的话，您可以在少于 O(n log n) 的时间内完成此操作。2）如果形成的树是断开的，你也必须找到树之间的最短距离。并且由于树，这不是一个 NP 完全问题，但实际上最短路径 alg 就足够了。

此刻，我非常怀疑我没有正确理解您的问题，在 geog 区域的出现次数上出现某种偏差怎么样，或者在极值点之间平均分配，或者使用一些先验的启发式方法选择。

您能否定义或进一步阐述色散概念？

于 2013-01-21T20:39:38.067 回答
0

考虑三种情况：

  1. 您的所有节点都在一个密集的集群中。
  2. 您的所有节点都在一个集群中，但集群很宽。
  3. 您的许多节点都在集群中，但少数节点远离集群。

您在所有成对距离上的总和很好地捕获了 (1) 和 (2)：紧密的集群比大型集群给出的结果更小。它对（3）有什么作用？这里，e节点总数的一部分N距离很远，平均距离为D。其他(1-e)N节点在平均距离为d.

现在，必须考虑多少成对连接？对于集群节点，有((1-e)N)^2=e^2*N^2-2*e*N^2+N^2这样的连接。对于遥远的节点，有e^2*N^2连接。

现在，将这些值乘以平均距离。这给出了 的总成对平均值(d*(e^2*N^2-2*e*N^2+N^2)+D*(e^2*N^2))/N。现在，假设它e很小，我们可以忽略包含 的项e^2。因此，平均值为d*(N^2-2*e*N^2)/N。

现在，考虑您的第二个指标：每个人与平均中心点的距离。这在 (1) 和 (2) 上也很好：紧密的集群比较大的集群具有更小的结果。3 的表现如何？用e同上来表示异常值的比例。现在，节点到中心点的平均距离由下式给出(d*(1-e)*N+D*e*N)/N。换句话说，集群节点的权重不再那么大。

有没有一种方法可以让您进行轻量级计算并且仍然更适当地加权集群节点？我认同。

我的建议是您从列表中选择随机节点对，计算节点间距离，然后对结果进行平均。对于 (1) 紧密集群，所有节点将靠近在一起，因此您绘制的所有随机对都将接近您在计算中得到的成对平均值。对于 (2)，松散簇，同样如此。对于 (3)，一个具有异常值的集群，您更有可能从集群内部绘制节点而不是从外部绘制节点，因此异常值最终会被忽略。

随着您增加采样节点的数量，集群将倾向于主导随机采样。我猜这将提供不错的准确性O(N)而不是O(N^2)时​​间。

于 2015-06-29T19:03:27.403 回答