algorithm - 从给定的集合中找到具有最大点密度的最小圆

Question

给定地球表面一组 n 个位置的 (lat, lon) 坐标，找到一个 (lat, lon) 点 c，以及r> 0 的值使得 我们最大化每平方位置的密度 d 英里，比方说，在由 c 和 r 定义的圆所描述和包含的表面积中。

起初我想也许你可以使用线性规划来解决这个问题。但是，密度取决于面积取决于 r 平方。二次项。所以，我认为问题不适合线性规划。

是否有解决此类问题的已知方法？假设您将问题简化为笛卡尔平面上的 (x, y) 坐标。这样会更容易吗？

你有两个变量 c 和 r ，你试图找到它们以使密度最大化，这是 c< 的函数/em> 和 r(以及位置，这是一个常数)。那么也许爬山法、梯度下降法或模拟退火法可能奏效？您可以很好地猜测您的第一个值。只需使用位置的质心。我认为您从那里达到的局部最大值将是全局最大值。

Answer 1

步骤:

• 使用基于密度的聚类算法对您的点进行聚类¹；
• 计算每个簇的密度；
• 递归地(或迭代地)对最密集的簇中的点进行子聚类；
  • 算法必须忽略异常值并使它们成为自己的一个集群。这样，将保留所有高密度异常值，并淘汰低密度异常值。
• 跟踪迄今为止观察到的密度最高的星团。当您最终到达由单个点组成的集群时返回。

---

此算法仅在您具有如下所示的集群时才有效，因为递归探索将产生类似形状的集群:

---

对于像这样形状笨拙的簇，该算法将失败，因为正如您所看到的，即使在计算 donut 形状的密度时三角形放置得最密集，它们也会报告以 [ 为中心的圆的密度要低得多0, 0]:

---

^{1。一种适合您的基于密度的聚类算法是 DBSCAN .}