在 K-means 中,如果质心永远不是最接近任何点会发生什么?

数据挖掘 聚类 k-均值
2022-02-15 17:51:29

我正在从头开始实施 K-Means,这个练习提出了一个问题。

要更新我的质心,对于每个质心,我必须找到该质心最接近的点。

在某些情况下,尤其是当质心数量较多而实例数量较少时(即 k=20 和 100 个实例),我会发现没有任何点将它们作为最接近的质心的质心。换句话说,它们成为“孤儿”,因为没有实例分配给它们。

Xs 是质心,Os 是实例

在上面的示例中,顶部的两个质心 (X) 显然都具有最接近质心的点。但在任何情况下,底部的质心都不是最近的质心。

我该如何处理?

  • 孤独的质心应该保持不动吗?
  • 我应该移动那个质心吗?如果是,如何?
  • 我应该删除它吗?

有没有标准的方法来处理这个?

- - - - - - 编辑: - - - - - - -

在 Github 上,我发现了这个:

https://github.com/klebenowm/cs540/blob/master/hw1/KMeans.java

这表明如果质心成为“孤儿”,则应将其分配到离质心最远的点。

这似乎是一种合理的方法,是否有任何论文或理论支持这一点?

3个回答

您应该保持单独的质心不动。在下一次迭代中,集群中心可能已经以这样的方式移动,现在有一些实例最接近孤立的质心,并且它可以被拾取。在 k-means 算法结束时,您可以删除没有关联实例的集群,但这并不重要。

归根结底,以您描述的方式使用 k-means 可能不是一个好主意,我们不应该期望它一定会产生好的结果。

它通常表示起始质心不良。

如果它发生在该过程的后期,则可能表明 kmeans 在此数据上效果不佳,因为很容易找到稳定的聚类。

您不必担心,正如我们所知,在 k-means 聚类中,您只需选择初始质心。这将创建集群的第一次迭代。在下一次迭代中,质心将移动到新创建的集群的中心。这整个过程将一直持续到你收敛。现在,首先选择的质心数量是好还是不好,是一个单独的问题。此外,我们也知道,k-means 的结果取决于初始选择的质心,我们有多种选择初始质心的方法,但只需在此处回答您的问题,运行完整的算法,您就不会在算法结束。