將2d整數座標聚類爲最多N個點的集合

Question

我在相對較小的2維網格上有多個點，這兩個點在兩個維度中進行包裝。座標只能是整數。我需要把它們分成幾組最多N個相近的點，其中N將是一個很小的截止點，我最多可能有10個點。

我正在爲一款遊戲設計一個AI，並且我99％確定在所有遊戲作品中使用minimax會給我一個約1次移動的可用前瞻，如果這樣的話。然而，在我們通過大量動作向前看之前，遙遠的棋子應該無法互相影響，所以我想一次將棋局劃分爲N個子棋子。但是，我需要確保一次選擇合理的N個部分，即相互靠近的部分。

我不在乎離羣值是自己留下還是與最疏遠的羣集混雜在一起。打破大於N的自然簇是不可避免的，只需要合理。因爲這用於響應時間有限的遊戲AI，所以我正在尋找儘可能快的算法，並且願意爲了性能而犧牲準確性。

有沒有人有任何建議算法來看待適應？ K-means和親屬似乎並不合適，因爲我不知道我想找到多少個羣集，但是我對我想要的羣集有一定的限制。我已經看到一些證據，通過將點捕捉到網格來近似解決方案可以幫助一些聚類算法，所以我希望整數座標使問題更容易。基於分層距離的聚類將很容易適應環繞座標，因爲我只是插入不同的距離函數，並且相對容易限制聚類的大小。我還有其他想法嗎？

我比庫更感興趣的算法，雖然有良好的文件，他們如何工作的圖書館將受到歡迎。

編輯：我最初在提到Fall 2011 AI Challenge的一個條目時提出這個問題，我很遺憾沒有完成。我鏈接的頁面對遊戲具有合理簡短的合理高級描述。

兩個關鍵點是：

1. 每個球員都有一個潛在的大量螞蟻
2. 每隻螞蟻給出的訂單動輒，移動1格無論是北，南，東或西;這意味着遊戲的分支因子是O（4 ^螞蟻）。

在比賽中，每輪轉輪也有嚴格的時間限制。我曾經想過用minimax來接近比賽（這些轉折確實是同時發生的，但作爲一種啓發式，我認爲它會好起來的），但是我擔心如果我考慮整場比賽，就沒有時間展望很多動作了立刻。但是，由於每隻螞蟻每轉一圈只能移動一個方格，所以兩隻螞蟻在最短路線上不能分開N個空格，可能會互相干擾，直到我們向前看N/2個移動。

所以我尋找的解決方案是一個很好的方法來分別選擇較小的螞蟻羣和最小化每個羣。我希望這可以讓我更深入地搜索移動樹，而不會失去太多的準確性。但顯然使用非常昂貴的聚類算法作爲省時的啓發式算法毫無意義！

我對這個問題的答案仍然很感興趣，儘管我從技術中學到的東西比這個特定的比賽還要多，因爲它已經結束了！感謝所有迄今爲止的答案。

Answer 1

構造的曲線圖ģ =（V，È）在你的網格，並且對它進行分區。 既然你有興趣的算法，而不是圖書館，這裏是最近的一篇文章：

丹尼爾Delling，安德魯V.戈德堡，伊利亞Razenshteyn和雷納託F.韋爾內克。圖與天然切割分割。在第25屆國際並行和分佈式處理研討會上（IPDPS'11）。 IEEE計算機 學會，2011年[PDF]

從文本：

圖表分割問題的目標是到FI第二最小成本的分區P，使得每個小區的大小是以U爲界。

所以你會設置U = 10。

Answer 2

中值切割算法非常易於在2D中實現，並且在此處可以很好地工作。你的異常值最終會成爲你可以丟棄的任何1組。

請求的進一步解釋： 中值切割是一種量化算法，但所有量化算法都是特例聚類算法。在這種情況下，該算法非常簡單：找到包含所有點的最小邊界框，沿着其最長邊分割框（並縮小它以適合點），重複直到達到目標數量的框。

A more detailed description and coded example

Wiki on color quantization has some good visuals and links

Answer 3

可以計算最小生成樹和刪除最長的邊緣。然後你可以計算出k-means。刪除另一個長邊並計算k-means。沖洗並重復，直到你有N = 10。我相信這種算法被命名爲單鏈路k均值，並且該簇類似於voronoi圖：

「單鏈路k聚類算法...正好是Kruskal算法...相當於尋找MST和刪除k-1最昂貴的邊緣。「

例如，見這裏：https://stats.stackexchange.com/questions/1475/visualization-software-for-clustering

Answer 4

既然你正在編寫一個遊戲，（我認爲）只是個固定數量的每個clusering之間移動，你可以採取在線算法的優勢得到consant更新倍。

不鎖定自己到多個羣集的屬性被稱爲非平穩，我相信。

本文接縫有一個很好的算法與上述兩個屬性：Improving the Robustness of 'Online Agglomerative Clustering Method' Based on Kernel-Induce Distance Measures（你也許能夠在其他地方找到它）。

這裏是a nice video showing在作品中的算法：

Answer 5

考慮，你只需要兩個集羣的情況。如果你運行k-means，那麼你將得到兩個點，並且兩個集羣之間的劃分是一個與兩個集羣的中心之間的線正交的平面。您可以通過將其投影到線上，然後將其在線上的位置與閾值進行比較來找出某個點處於哪個聚類中（例如，獲取線與兩個聚類中心任一點的矢量之間的點積和點）。

對於兩個羣集，這意味着您可以通過移動閾值來調整羣集的大小。您可以沿着連接兩個聚類中心的線對它們的距離進行排序，然後相當容易地沿着線條移動閾值，通過聚類的整齊程度來平衡分割的不平等。

您可能沒有k = 2，但您可以通過分成兩個羣集，然後細分羣集來分層運行。

（後評論）

我不擅長與圖片，但這裏是一些相關的代數。

隨着K-手段，我們根據從聚類中心的距離分割點，所以對於一個點Xi和兩個中心Ai和Bi我們可能有興趣在

SUM_i（熙 - AI）^ 2 - SUM_i（夕 - 鉍）^ 2

這是SUM_i艾^ 2 - SUM_i鉍^ 2 + 2 SUM_i（鉍 - 艾）僖

因此，一個點被分配到依賴於K + 2的符號或者羣集（B - A）.X - 一個常數加上矢量與點之間的點積和連接兩個聚類圓的矢量之間的點積。在兩個維度中，結束於一個聚類中的平面上的點與結束於另一個聚類中的平面上的點之間的分界線是垂直於兩個聚類中心之間的線的線。我的建議是，爲了控制分割後的點數，可以爲每個點X計算（B - A）.X，然後選擇一個閾值，將一個聚類中的所有點從其他點中的所有點簇。這相當於將分界線向上或向下滑動到兩個聚類中心之間的線上，同時保持垂直於它們之間的線。一旦你有點產品Yi，其中Yi = SUM_j（Bj-Aj）Xij，衡量一個簇如何緊密分組的度量是SUM_i（Yi-Ym）^ 2，其中Ym是Yi的平均值集羣。我建議你使用這兩個數值的總和來表示你有多好的分組。爲了將點移入或移出集羣並獲得新的平方和，而無需從頭開始重新計算所有內容，請注意，SUM_i（Si + T）^ 2 = SUM_i Si^2 + 2T SUM_i Si + T^2，所以如果您跟蹤總和和平方和，當您爲每個組件添加或減去一個值時，可以計算出平方和總和會發生什麼情況，因爲在添加或刪除點時，羣集的平均值會發生變化。