原书出处
Introduction to Algorithms, Fourth Edition
33 第33章 机器学习算法
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