我正在尋找一種方法來根據它們的相對距離對一組專案進行分類。
例如假設我們有 4 個城市并且我們知道它們的相對距離：
| 城市1 | 城市2 | 城市3 | 城市4 |
|---|---|---|---|
| 0 | 2.1 | 2.2 | 3.4 |
| 2.1 | 0 | 2.2 | 2.1 |
| 2.2 | 2.2 | 0 | 1.4 |
| 3.4 | 2.1 | 1.4 | 0 |
如果我們嘗試將這 4 個城市分為兩類，直覺上我們會得到
(city1, city2) and (city3, city4)
通過最小化城市之間的內部距離。
根據我對 K-Means 的理解，當我們有一個共同的距離度量來表示 X 軸時，這種方法有效。在這里，我們不知道距離是如何計算的，因此沒有一種明確的方法可以將距離分解為一些共同點。
有沒有辦法對這些城市進行分類？
uj5u.com熱心網友回復：
您可以嘗試將任務作為圖形問題來解決。以城市為頂點，以城市間的道路為邊。然后您可以使用最小生成樹聚類：您開始構建最小生成樹，但是當您需要數量的集群時，在程序中間停止。
讓我們借助Kruskal 演算法來完成
- 我們從4 個集群開始：
{city1}, {city2}, {city3}, {city4} - 我們得到最短邊，它是
city3 - city4(1.4)，我們消除它并有3 個集群：{city1}, {city2}, {city3, city4} - 我們得到的下一個最短邊：它要么
city1 - city1或city2 - city4（既有2.1取決于領帶解析度長度），我們有2群：要么{city1, city2}, {city3, city4}或{city1}, {city2, city3, city4} - 在這里（在2 個集群處）我們停止并獲得
{city1, city2}, {city3, city4}或{city1}, {city2, city3, city4}集群化
您可以使用效率稍低但易于編碼的方法：
- 通過任何庫（例如，）通過任何演算法（Kruskal 的，Prim 的）構建最小生成樹
scipy - 現在您擁有一個集群中的所有城市
- 開始從這棵樹中洗掉最長的邊：洗掉一個最長的邊，您將得到2 個簇（子樹），洗掉k 個最長邊 - k 1 個簇。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/354984.html