聚類是一種將具有相似特征的數據點進行分組的方法。它廣泛應用于探索性數據分析，并已被證明在模式識別、市場和客戶細分、推薦系統、數據壓縮以及生物數據分析等許多應用中都發揮著重要作用。

盡管聚類算法種類繁多，但沒有一種能夠生成點數均衡的聚類。這種大小均衡的聚類在某些領域非常重要，例如在“最后一英里”配送領域，大量訂單可以聚合成大小均衡的組，從而優化配送路線并最大限度地提高車輛利用率。

考慮到需要實現等大小的聚類，我和幾位同事擴展了所謂的譜聚類，以生成點數均衡的聚類。這種新算法基于數據點的地理信息構建具有相似點數的聚類。

完整代碼可在此GitHub 倉庫中找到。它旨在為數據科學社區做出貢獻。如果您需要在地圖上創建相等的點簇，不妨嘗試一下！

等大小譜聚類：算法

等大小聚類由三個步驟組成：聚類初始化、計算每個聚類的鄰居以及平衡每個聚類中的點。讓我們詳細回顧一下每個步驟。

聚類初始化

第一步，我們使用Scikit-learn 的譜聚類算法實現來創建聚類。譜聚類在聚合空間數據方面非常強大，因為它可以根據連接節點的邊來識別圖中節點的社群。譜聚類算法在對遵循圓對稱性的點進行聚類時尤其有用。如果您想了解更多關于此方法的信息，可以閱讀 William Fleshman 撰寫的這篇精彩文章：

進行聚類初始化需要兩個超參數：nclusters，表示?所需聚類的數量；nneighbors，表示每個數據點的鄰居數量。譜聚類使用最后一個參數來構建親和度矩陣。 的良好值nneighbors?介于數據點的 7% 到 15% 之間。

步驟1：利用譜聚類算法創建聚類。這些聚類中的點數并不相等。

計算每個聚類的鄰居

創建聚類后，算法的第二步是計算每個聚類的鄰居。這個計算是如何進行的呢？通過估計每個數據點最近鄰居的聚類標簽的眾數。例如，如果點x屬于聚類A，而其大多數最近鄰居屬于聚類B，則意味著聚類B是聚類A的鄰居。

每個簇的鄰居的計算極其重要，因為簇的平衡是通過在相鄰簇之間交換點來實現的。

步驟2：左圖：估計每個聚類的鄰居。在此示例中，我們可以看到聚類 A 和 B 是聚類 C 的鄰居。右圖：通過在相鄰聚類之間交換點來實現聚類的平衡。

平衡每個聚類上的點

算法的最后一步是平衡每個聚類中的點。如上所述，我們通過在相鄰聚類之間交換點來實現這一點。較大的聚類會將點轉移到較小的相鄰聚類。在平衡過程中，我們的目標是使聚類大小大致等于N /ncluster，其中N是數據點的總數。

為了平衡簇的大小，我們定義了超參數equity_fraction。equity_fraction是一個定義在區間 (0,1] 內的數字，它限制了生成的簇必須達到的相等程度。如果equity_fraction為零，則簇將保持相同的初始大小。如果equity_fraction為一，則生成的簇的大小大致等于N /ncluster。

步驟 3：最終的聚類規模取決于 equity_fraction。左圖：如果 equity_fraction 為 0，聚類將保持其初始規模。右圖：如果 equity_fraction 為 1，聚類的點數大致相同。

讓我們用一個小括號來定義一個叫做簇離散度（cluster diffraction）的量。簇離散度定義為簇內點距離的標準差。你可以把它看作是簇內距離的稍微修改版本。

這equity_fraction會影響初始聚類分散度，因為點的交換會增加聚類內點之間的距離。在這種情況下，我建議您使用優化算法來找到最小化聚類分散度的最佳聚類超參數。在下一節中，我將討論如何從 Python 代碼中去除聚類分散度。

其他功能

需要記住的是，等大小譜聚類可用于創建空間點的聚合。存儲庫附帶繪圖功能，可在您擁有數據點坐標的情況下使用。在下一節中，我們將看到此功能的實際應用。

用例：阿姆斯特丹的餐館集群

假設您是荷蘭一家農場的主人，您想將新鮮優質的食材配送到阿姆斯特丹的眾多餐廳。您有6輛容量相同的車輛，這意味著它們能夠配送到大致相同數量的餐廳。

為了充分利用車輛的容量，您可以使用等大小聚類對餐廳進行分組，以便每輛車不會從一家餐廳行駛到另一家餐廳太多。

我們先來看看餐廳的位置：

restaurants_in_amsterdam.csv文件包含阿姆斯特丹中央火車站周圍 8 公里范圍內餐廳位置的列表。您可以在GitHub 倉庫的datasets文件夾中找到此文件。

根據數據框中列出的位置coords，可以估算出一個包含每對點之間行程距離的矩陣。該矩陣的形狀為 (n_samples, n_samples)，并且必須是對稱的。該矩陣是等大小聚類的輸入。

現在我們可以運行等大小譜聚類了。這就像調用類一樣簡單SpectralEqualSizeClustering：

在此示例中，我們創建了 6 個聚類。我們選擇鄰居數量nneighbors為輸入數據集中點數的 10%。由于我們希望聚類盡可能均等，因此我們將 設置?equity_fraction為 1。

您可以看到如何通過調用該方法獲取每個數據點的聚類標簽fit。重要提示：用于預測原始數據中不存在的點的聚類標簽的函數尚未實現。如果您覺得此代碼對您的工作有用，我鼓勵您開發此功能！

可以將上面獲得的聚類標簽添加到數據框中，coords以便在地圖上繪制生成的聚類：

通過運行上面的代碼，我們得到一個包含所有聚類的交互式圖，如圖所示：

使用等大小譜聚類代碼創建的聚類。

在該圖中，您可以選擇每個集群以分別進行可視化：

?

在上述用例中，超參數優化并非必需。然而，正如我之前提到的，如果需要，可以使用優化方法。在這種情況下，您可以將屬性clustering.total_cluster_dispersion（即所有聚類離散度的總和）用作優化指標。通過最小化該量，?生成的聚類將更加緊湊。

帶回家的信息

在這篇博客中，我介紹了一種譜聚類代碼的修改，它可以生成點數均衡的聚類。該算法可以用來生成空間點的均等聚合，并且可能有助于改進“最后一英里”配送領域的某些流程。

等大小譜聚類的重要考慮因素如下：

• 輸入數據必須是與數據點坐標相關的對稱距離矩陣。
• 聚類代碼的超參數包括所需聚類的數量 (?nclusters)、每個數據點的鄰居數量 (?nneighbors) 以及決定聚類大小均勻程度的分數 (?equity_fraction)。您可以使用任何優化算法來找到最小化總體聚類離散度 ( ) 的最佳參數total_cluster_dispersion。
• 等大小聚類也可用于非空間數據，但尚未針對此目的進行測試。如果您想嘗試一下，請定義一個度量來創建代碼所需的對稱距離矩陣作為輸入。請務必先對變量進行歸一化或標準化。
• 該代碼還沒有prediction方法，但如果您發現該代碼有用，歡迎您做出貢獻。