← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

33 第33章 机器学习算法

Fourth edition · 核验版本的摘录快照 · 导入于 2026-10-23T08:18:08.772Z

he clusters returned to be empty, particularly if many of the input points are identical.

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

impractical. In practice, it sometimes suffices to terminate the procedure when the perce

此预览只包含定位所需的摘录和上下文。

原书定位详情

来源:a19c7933-4eda-4176-aebd-30fe7e1ad292

正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter033.xhtml

EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea