给定相同的数据集,k-means 聚类会收敛到相同的结果吗?

数据挖掘 聚类 k-均值
2022-02-19 07:54:02

我对 k-means 聚类算法做了一些研究。似乎唯一不确定的部分是质心 - 初始化。

假设我有 10k 个数据点和给定的 k. 然后我在每次尝试中随机初始化初始质心:

Try_1:初始 k 质心随机使用 seed_1。然后不断更新质心直到收敛(假设我们可以多次使用 10k 个数据点)

Try_2:使用 seed_2 随机初始 k 质心。然后不断更新质心直到收敛(假设我们可以多次使用 10k 个数据点)

Try_3:使用 seed_3 随机初始 k 质心。然后不断更新质心直到收敛(假设我们可以多次使用 10k 个数据点)

Try_4:使用 seed_4 随机初始 k 质心。然后不断更新质心直到收敛(假设我们可以多次使用 10k 个数据点)

Try_5:使用 seed_5 随机初始 k 质心。然后不断更新质心直到收敛(假设我们可以多次使用 10k 个数据点)

在这 5 次尝试中,最终的聚类结果会相同吗?

1个回答

它们不一定相同。考虑均匀分布在一个圆(半径 = 1)上的观测值。根据初始质心,算法将收敛于不同的解决方案。例如,考虑两个质心最初位于圆直径之一的每一侧的情况。这些可以是任何一对点,并且算法已经与不同的解决方案收敛。

但是,存在算法必然会收敛到相同解决方案的情况。例如,考虑在一个 2 簇问题中平均分布在一个段上的点。很清楚(虽然有点难以解释)任何初始化最终都会收敛到相同的解决方案(这实际上需要附加假设,例如至少没有点位于两个集群的边缘)。

在您的示例中,结构更复杂,问题更难分析。有一些问题可能每次都会给出相同的结果,而其他问题可能会产生不同的结果。但无论如何,在一般情况下,您不能确定它会退回到单一解决方案。