最后，我只是按照我的计划实施了解决方案，并在Medium post 中描述了它。这是“实心多边形的 K-Means”。我在我的github.io上做了一个操场。

更多关于实体聚类方法的细节。

K-Means 的复杂度是O(nkdi)或O(nk)每次迭代没有d，

• n是d维向量的数量（要聚类）
• k聚类数
• i收敛前所需的迭代次数。

实体聚类的复杂度估计

假设聚类多边形没有自相交。

• k - 簇数
• m - 聚集多边形中的点数（不与 K-Means n混合）。

步骤复杂度估计

1. 使用Fortune 算法为k个中心构建 Voronoi 图：O(k log(k))。期望您有中心和单元格作为结果。

2. 将每个 Voronoi 单元与聚类多边形相交。我使用多边形裁剪包中的算法。

从描述：

“Martinez-Rueda-Feito 多边形裁剪算法用于在O((n+k) log(n))时间内计算结果，其中 n 是所有涉及的多边形中的边总数，k 是交叉点的数量边缘之间。”

我们的边总数是m和 Voronoi 单元Tmp中的边。在复多边形情况下m >> Tmp。我不知道如何估计交叉点的数量，但我认为大m可以忽略不计。

所以这个步骤的完整估计O(m log(m) k)。

3. 多边形面积和重心的复杂度为O(m)。

多边形点估计的数量是多少？

在最坏的情况下，一个 Voronoi 单元多边形具有(k-1) 条边。聚类多边形有m条边。正如我可以想象的那样，在最坏的 Voronoi 单元和最坏的多边形的最坏情况下相交会产生3n/2边多边形。因此，这一步的上限是O(nk)。

4. 重心是新的重心 - 转到第 1 步。

最终的复杂度估计是O(k log(k) + m log(m) k + mk) => O(m log(m) k)每次迭代。

这是什么意思？

如果我们想用 K-Means 解决同样的实体多边形聚类问题，那么我们需要将原始多边形离散化为 K-Means 点。

1. K-Means 结果将不太准确。

2. 如果n >> m log(m)则 K-Means 将比固体聚类慢。

有趣的点

1. K-Means 将密度作为聚类过程的一部分。有些点可能比其他点重。实体聚类忽略密度，因此所有聚类点的权重相等。

2. 我们可以看到实体聚类中的瓶颈效应。聚类试图分散聚类中心以具有相等的密度。但是簇中心不能跳出它的多边形，所以它慢慢地从密集区域移动到空间。在某些情况下，我们可以在 K-Means 中看到相同的效果。

3. 我认为这个瓶颈问题可能会随着中心跳跃而显着减少 - 将最小集群的中心跳到最大的集群。

K-means 不能很好地工作，因为您如何计算和使用“均值”？如何确保收敛？此外，距离计算将很昂贵并且不能重复使用。

相反，请使用可与距离矩阵一起使用的任何算法。例如：层次聚类、PAM（k-medoids，类似于 k-means 但使用任意距离矩阵）和 DBSCAN。

只计算一次距离矩阵，因为这将相当昂贵。然后尝试不同的算法和参数。