從給定集合中查找具有最大點密度的最小圓點

Question

給定地球表面上一組n位置的（經度，緯度）座標，找到（經緯度）點c，和- [R> 0，使得 的值，我們最大化密度，d，每平方 英里，比如說位置，在由ç和- [R限定的圓描述和包含在表面區域。

起初我想也許你可以用線性規劃解決這個問題。但是，密度取決於面積取決於r的平方。二次項。所以，我認爲問題不適用於線性規劃。

有沒有一種解決這類事情的已知方法？假設您將問題簡化爲笛卡爾平面上的（x，y）座標。這是否使它更容易？

你有兩個變量Ç和[R你試圖找到以最大化密度，這是Ç和[R的功能（和位置，這是一個常數）。那麼也許爬山，梯度下降或模擬退火方法可能會起作用？你可以爲你的第一個價值做一個很好的猜測。只需使用位置的質心。我認爲你從那裏達到的本地最大值將是全球最大值。

Answer 1

步驟：

• 集羣使用的是基於密度聚類算法你的觀點;
• 計算每個簇的密度;
• 以遞歸方式（或迭代地）對最密集簇中的點進行子聚類;
  • 該算法必須忽略異常值並將它們作爲自己的羣集。這樣，所有高密度的異常值將被保留，並且低密度的異常值將被斷開。
• 跟蹤到目前爲止觀察到的密度最高的聚類。當您最終到達由單點組成的集羣時返回。

---

當你有如下所示的遞歸的探索將產生類似形狀的集羣的那些集羣這種算法纔有效：

---

算法將因爲你可以看到，儘管當你計算甜甜圈形狀的密度時三角形的密度最高，他們會報告一個很遠的距離較低的密度WRT圓在[0,0]爲中心：

---

^{1.一種基於密度的羣集算法，將工作爲你是DBSCAN。}