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

知识卡片

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

劳埃德迭代只保证局部条件

理解等级:高级

劳埃德过程反复更新分组与中心,直到每个点属于最近中心且每组中心取该组均值。

这些条件是全局最优的必要条件,但不足以保证全局最优;结果可能停在局部极小。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第33章 机器学习算法 · 查看原书依据

      Although we know of no polynomial-time algorithm that finds the global minimum over all clusterings (according to equation (33.2)), we can find a local minimum. Lloyd [304] proposed a simple procedure that finds a sequence C of k centers that yields a local minimum of f(S, C). A local minimum in the k-means problem satisfies two simple properties: each cluster has an optimal center (defined below), and each point is assigned to the cluster (or one of the clusters) with the closest center. Lloyd’s procedure finds a good clustering—possibly optimal—that satisfies these two properties. These properties are necessary, but not sufficient, for optimality. Optimal center for a given cluster In an optimal solution to the k-means problem, each center

    参考来源

    - 位置:《算法导论(第4版)》第33章《机器学习算法》(OEBPS/chapter033.xhtml,文本字符[10000,15000))。 - 结论依据:原文第33章导言和33.1节的学习任务、聚类定义、目标函数与局部最优说明;公式及图已核对。 - 原始内容:Although we know of no polynomial-time algorithm that finds the global minimum over all clusterings (according to equation (33.2)), we can find a local minimum. Lloyd [ 304 ] proposed a simple procedure that finds a sequence C of k centers that yields a local minimum of f ( S , C ). A local minimum in the k -means problem satisfies two simple properties: each cluster has an optimal center (defined below), and each point is assigned to the cluster (or one of the clusters) with the closest center. Lloyd’s procedure finds a good clustering—possibly optimal—that satisfies these two properties. These properties are necessary, but not sufficient, for optimality. Optimal center for a given cluster In an optimal solution to the k -means problem, each center