聚类是一种将具有相似特征的数据点进行分组的方法。它广泛应用于探索性数据分析，并已被证明在模式识别、市场和客户细分、推荐系统、数据压缩以及生物数据分析等许多应用中都发挥着重要作用。

尽管聚类算法种类繁多，但没有一种能够生成点数均衡的聚类。这种大小均衡的聚类在某些领域非常重要，例如在“最后一英里”配送领域，大量订单可以聚合成大小均衡的组，从而优化配送路线并最大限度地提高车辆利用率。

考虑到需要实现等大小的聚类，我和几位同事扩展了所谓的谱聚类，以生成点数均衡的聚类。这种新算法基于数据点的地理信息构建具有相似点数的聚类。

完整代码可在此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方法，但如果您发现该代码有用，欢迎您做出贡献。