K均值聚類：評估新的聚類中心

Question

在每次迭代所有數據點之後，或者在將聚類分配給每個數據點之後，評估新的聚類中心會更好嗎？爲了澄清，這兩種方法是優選的：

1. 您將所有的數據點，以不同的集羣，然後找到新的聚類中心
2. 或者，你的下一個數據點分配到最近的聚類和發現新的羣集中心，移動到下一個點作爲重複...

Answer 1

這些都或多或少的兩種主要方法

1. 它或多或少勞埃德方法 - 你遍歷所有數據點，將每個分配給最近的簇，然後相應地移動所有中心，重複。
2. 它或多或少是一種Hartigan方法 - 您遍歷每個數據點並查看是否更好地將其移動到其他羣集（它是否最小化能量/使羣集更「密集」），重複直到沒有可能的更改。

哪兩個比較好？實證研究表明Hartigan方法具有多重優勢。特別是人們可以證明，Hartigan不會比勞埃德工作得更差（每個Hartigan optima也是勞埃德最優的，但不是相反）。在http://ijcai.org/papers13/Papers/IJCAI13-249.pdf中有一個很好的理論和實踐分析表明，應該遵循第二種方法，特別是如果數據中存在許多可能不相關的特徵。