这不再是真正的集群任务了。请参阅：聚类是关于发现结构，但您强制形式约束比结构强得多。

但是，您可以从不同的角度来看待它：

一个非常努力地将数据划分为不重叠、大小相等的“箱”的结构是平衡树。所以你可能想要一个空间树，比如 R*-tree。它将尝试将您的数据划分为相同大小的分区。

现在，特别是对于 2D 点数据，使用 STR 批量加载树比使用完整的 R 树要容易得多。另外，它实际上会让你得到同样大小的非重叠分区。常规的 R- 和 R*-trees 只会在某些阈值内执行此操作。

您需要的一般过程非常简单（这是您的“相等大小”约束的结果！）：当 k 是您想要的分区数时计算 sqrt(k)。按 x 轴对数据进行排序，并将其划分为 sqrt(k) 大小相等的分区。对于这些分区中的每一个，按 y 轴对这部分数据进行排序，然后将其再次划分为 sqrt(k) 分区。然后你有 sqrt(k)^2 = k 具有相同大小且不重叠的分区。另外，它只需要 O(n log n) 时间，而且这种方式比层次聚类要快得多。