如何按照鄰近性對一組中的對象進行分組？

Question

我有一套包含數千個地址。如果我能得到每個地址的經度和緯度，我該如何按照鄰近度將這個集合分組？

此外，我可能要重試根據不同的規則的「聚類」：

• N個組，每組
• M個地址的基團中的任意地址之間
• 最大距離

Answer 1

你可以試試k-means clustering算法。

Answer 2

「N組」和「每個組的M個地址」限制是相互排斥的。一個暗示另一個。

Answer 3

你想矢量量化：

http://en.wikipedia.org/wiki/Vector_quantization

「它通過將一大組點（矢量）的成具有大約相同數目的最接近他們點的組，每組由下式表示它的質心點，如k-means和其他一些聚類算法「

這裏的向量是每個地址的地理座標，並且可以根據你的約束條件給你的算法提供其他參數（proximity，gr大小，組數......）。

您可以從k-means開始，但根據我的經驗，基於Voronoi的算法更加靈活。一個很好的介紹here。

Answer 4

1. 構建所有地址之間的距離矩陣。
2. 從一個隨機地址開始，按照該地址的上升距離對矩陣進行排序
3. 隨着您的移動，從矩陣中刪除地址，將距離起始地址最近的地址放入一個新組，直到達到您的標準組的大小或最大距離）。
4. 一旦一個組被填滿，選擇另一個隨機地址，並通過距離到該地址
5. 繼續這樣做，直到所有地址都被取出矩陣。

如果地址是均勻分佈的，每個組的起始地址周圍都會有一種圓形的形狀。當起始地址靠近現有組時，問題就出現了。發生這種情況時，如果停止標準僅爲組大小，新組將圍繞舊組進行排序，甚至可以將其圈起來。如果使用最大距離約束，那麼這不會發生（假設沒有其他約束）。

我不知道這是否是一種很好的做法，但這是我的嘗試。我相信很多優化是必需的。特別是對於邊緣地址。

Answer 5

這取決於你想要聚類的數據的規模。蠻力方法是計算距離數組中所有點組合的距離。得到的數組是N^2，並且由於A到B的距離與B到A的距離相同，所以只需要一半，所以得到的集合是N^2/2。

對於相對接近的緯度座標，有時可以使用lat long作爲x，y網格並計算笛卡爾距離。由於現實世界不平坦，笛卡爾距離將會出現錯誤。如果您的地址位於全國各地，則應使用更精確的計算方法，請參閱this link from Mathforum.com。

如果你沒有規模來處理整個距離矩陣，你需要做一些算法編程來提高效率。