知识卡片
劳埃德迭代只保证局部条件
劳埃德过程反复更新分组与中心,直到每个点属于最近中心且每组中心取该组均值。
这些条件是全局最优的必要条件,但不足以保证全局最优;结果可能停在局部极小。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 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