K均值聚类：评估新的聚类中心

Question

在每次迭代所有数据点之后，或者在将聚类分配给每个数据点之后，评估新的聚类中心会更好吗？为了澄清，这两种方法是优选的：

1. 您将所有的数据点，以不同的集群，然后找到新的聚类中心
2. 或者，你的下一个数据点分配到最近的聚类和发现新的群集中心，移动到下一个点作为重复...

Answer 1

这些都或多或少的两种主要方法

1. 它或多或少劳埃德方法 - 你遍历所有数据点，将每个分配给最近的簇，然后相应地移动所有中心，重复。
2. 它或多或少是一种Hartigan方法 - 您遍历每个数据点并查看是否更好地将其移动到其他群集（它是否最小化能量/使群集更“密集”），重复直到没有可能的更改。

哪两个比较好？实证研究表明Hartigan方法具有多重优势。特别是人们可以证明，Hartigan不会比劳埃德工作得更差（每个Hartigan optima也是劳埃德最优的，但不是相反）。在http://ijcai.org/papers13/Papers/IJCAI13-249.pdf中有一个很好的理论和实践分析表明，应该遵循第二种方法，特别是如果数据中存在许多可能不相关的特征。