有不止一种 k-means 算法。

您可能参考了Lloyds algorithm，它仅取决于初始聚类中心。但也有 MacQueen 的，它取决于顺序，即点的顺序。然后是 Hartigan，Wong，Forgy，...

当然，不同的实现可能会有实现和优化的差异。他们也可能以不同的方式对待关系！例如，许多简单的实现总是在绑定时将元素分配给第一个或最后一个集群。其他人将保留当前的聚类分配。因此，当对整数值进行聚类时，在这种情况下关联更为常见，但在 Iris 数据集上也是如此，您可能会看到由此引起的伪影和差异。

此外，在完成 k-means 之后，集群最终可能会按内存地址重新排序，因此即使 k-means 在第一次迭代后收敛，您也不能安全地假设集群 1 仍然是集群 1。其他人将按集群大小重新排序集群（这实际上对 k-means 有意义，因为这更有可能在不同的随机初始化时返回相同的结果）

但是假设所有迭代 Lloyd 直到收敛（原始的 MacQueen k-means 没有！）它们至少都应该达到局部最优。只会有那么多的局部最优...

例如，考虑由生成的数据集，让可以被。会有很多局部最优解。使用不同的随机种子运行 k-means 确实会给您非常不同的解决方案。对于适当的参数，我相信同一簇中的两个不同元素在另一个结果中再次出现在同一簇中的机会将在。在更高的维度上，您可能可以进一步减少这个数字。例如在维数据集中，对于和$p_j=(\sin(2\pi \frac{j}{n}), \cos(2\pi \frac{j}{n}))$$n$$j$$50\%$$n$$p_{jj}=1$$p_{ij}=0$$i\neq j$，所有点都是等距的。很容易看出这会对 k-means 造成严重破坏......

K-means 仅在其起始中心随机化。一旦确定了初始候选中心，在该点之后它就是确定性的。根据您对 kmeans 的实施，可以每次选择相同的中心、每次相似的中心或每次完全随机的中心。使用 MATLAB/R 实现，选择是随机的，但您得到的结果是从 50 组左右的初始中心选择中获得的最佳结果。注意 R stats::kmeans 函数，默认是只运行一组初始中心（即 nstart = 1）。根据您的数据，增加此值可能会稳定跨运行的集群分配，通常建议这样做。

要回答您的第一个问题，这实际上取决于您拥有什么样的数据。如果它被很好地分成球形簇，那么你通常会得到非常相似的簇。如果没有，那么您每次可能会得到相当随机的集群。

对于处于同一集群中的“可能性”没有通用度量，但如果您需要一个，您可以根据任何实例与其他实例的相似度/距离与它们与其他点的相似度/距离相比得出一个。或者，也许您可​​以先运行一个链接（单个或完整）算法，然后通过它们与最低共同祖先的距离来衡量它们在同一个集群中的“可能性”。或者还有很多其他的，你可以根据你的数据是什么样的以及应用程序是什么来做到这一点。