k-表示空簇

Question

我尝试将k-means作为家庭作业来实施.我的练习单给了我关于空中心的以下评论:

在迭代期间,如果任何集群中心没有与之关联的数据点,请将其替换为随机数据点.

这让我感到困惑,首先是维基百科或我读过的其他资料根本没有提及.我进一步阅读了"为数据选择一个好的k"的问题 - 如果我开始为空的集群设置新的中心,我的算法应该如何收敛.

如果我忽略空簇,我会在30-40次迭代后收敛.忽略空集群是错误的吗？

Answer 1

看看这个空集群如何发生的例子:http://www.ceng.metu.edu.tr/~tcan/ceng465_f1314/Schedule/KMeansEmpty.html 它基本上意味着1)力量中的随机震颤,或2 )簇k的数量是错误的.您应该迭代k的几个不同的值并选择最佳值.如果在迭代期间您遇到空簇,请将随机数据点放入该簇中并继续.我希望这对你去年的家庭作业有所帮助.

Answer 2

处理空簇不是 k 均值算法的一部分，但可能会带来更好的簇质量。谈到收敛性，它永远不能精确地保证，而只是启发式地保证，因此收敛的标准通过包括最大迭代次数来扩展。

关于解决这个问题的策略，我想说，随机分配一些数据点给它并不是很聪明，因为我们可能会影响集群的质量，因为到其当前分配的中心的距离或大或小。对于这种情况，一种启发式方法是选择距最大簇最远的点并移动空簇，然后这样做，直到没有空簇为止。