聚类是一种将具有相似特征的数据点进行分组的方法。它广泛应用于探索性数据分析,并已被证明在模式识别、市场和客户细分、推荐系统、数据压缩以及生物数据分析等许多应用中都发挥着重要作用。
尽管聚类算法种类繁多,但没有一种能够生成点数均衡的聚类。这种大小均衡的聚类在某些领域非常重要,例如在“最后一英里”配送领域,大量订单可以聚合成大小均衡的组,从而优化配送路线并最大限度地提高车辆利用率。
考虑到需要实现等大小的聚类,我和几位同事扩展了所谓的谱聚类,以生成点数均衡的聚类。这种新算法基于数据点的地理信息构建具有相似点数的聚类。
完整代码可在此GitHub 仓库中找到。它旨在为数据科学社区做出贡献。如果您需要在地图上创建相等的点簇,不妨尝试一下!
等大小谱聚类:算法
等大小聚类由三个步骤组成:聚类初始化、计算每个聚类的邻居以及平衡每个聚类中的点。让我们详细回顾一下每个步骤。
聚类初始化
第一步,我们使用Scikit-learn 的谱聚类算法实现来创建聚类。谱聚类在聚合空间数据方面非常强大,因为它可以根据连接节点的边来识别图中节点的社群。谱聚类算法在对遵循圆对称性的点进行聚类时尤其有用。如果您想了解更多关于此方法的信息,可以阅读 William Fleshman 撰写的这篇精彩文章:
谱聚类
基础与应用
towardsdatascience.com
进行聚类初始化需要两个超参数: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
方法,但如果您发现该代码有用,欢迎您做出贡献。