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

Question

给定地球表面一组n个位置的(lat,lon)坐标，求一个(lat,lon)点c ，以及 r > 0 的值，这样 我们最大化每平方位置的密度 d 英里，比方说，在由 c 和 r.

定义的圆所描述和包含的表面积中

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

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

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

Answer 1

步骤：

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

---

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

---

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

---

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