知识卡片
劳埃德收敛源于严格下降
重算质心不会增大平方误差;只有严格更近才把点换组,所以非末轮的分组变化会严格降低目标值。可能的k分组数量有限,因此不会无限重复,最终停止在局部最优分配。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第33章 机器学习算法 · 查看原书依据
Lloyd’s procedure always terminates. By Theorem 33.1, recomputing the centers of each cluster as the cluster centroid cannot increase f(S, C). Lloyd’s procedure ensures that a point is reassigned to a different cluster only when such an operation strictly decreases f(S, C). Thus each iteration of Lloyd’s procedure, except the last iteration, must strictly decrease f(S, C). Since there are only a finite number of possible k-clusterings of S (at most kn), the procedure must terminate. Furthermore, once one iteration of Lloyd’s procedure yields no decrease in f, further iterations would not change anything, and the procedure can stop at this locally optimum assignment of points to clusters. If Lloyd’s procedure really required kn iterations, it would be