證明k-means總是收斂嗎？

Question

我明白k-均值算法步驟。 但是我不確定算法是否總是會收斂？或者觀察結果是否始終從一個質心切換到另一個質心？

Answer 1

的算法總是收斂（通過清晰度），但不一定全局最優。

該算法可以從質心切換到質心，但是這是該算法的參數（precision或delta）。這有時refered爲「循環」。一會兒週期通過質心後的算法。有兩種解決方案（兩者都可以同時使用）。 Precision參數，maximum number of iterations參數。

Precision參數，如果質心的變化量小於閾值delta，則停止算法。

Max Num Iterations，如果算法達到這個數字的迭代停止算法。

注意上述方案不破壞算法的收斂特性。它仍然會收斂但不一定是全局最優（這與所用方案無關，就像許多優化算法中一樣）。

您可能對stats.SE Cycling in k-means algorithm和referenced proof of convergence

有關的問題感興趣