返回主题:经典算法与业务建模

知识卡片

普通读书笔记卡 · 3710.b.2.b.1.c.1

劳埃德收敛源于严格下降

理解等级:高级

重算质心不会增大平方误差;只有严格更近才把点换组,所以非末轮的分组变化会严格降低目标值。可能的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

    参考来源

    - 位置:《算法导论(第4版)》第33章《机器学习算法》(OEBPS/chapter033.xhtml,文本字符[15000,20000))。 - 结论依据:原文第33.1–33.2节质心和分配定理、劳埃德过程、假设优化框架、色彩量化示例或专家预测引理。 - 原始内容: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 k n ), 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 k n iterations, it would be