Convergence occurs when repeated updates stop changing an assignment or solution. In an iterative algorithm, it supplies a practical stopping condition: halt when the latest classification matches the previous one, or when a maximum iteration limit is reached. section 12.2
Use convergence as an operational check rather than as proof of a globally optimal answer:
- Compare successive assignments or solution states; k-means stops when no point switches clusters. section 12.2
- Bound the work with a maximum iteration count, since a poor initialization can slow convergence and force an early stop. section 12.2
- Treat convergence as convergence to a local or near-optimal result, not a guarantee of the best possible solution. section 12.2 section 18.2
- Control update size when approximating a smallest enclosing sphere; shortening each move after an iteration ensures convergence. section 10.5.2
K-means assignment and recentering
Initialize centroids, assign every point to its nearest centroid, recompute each centroid as its cluster’s center of mass, and repeat. If the new cluster indices equal the previous indices, return the centroids and assignments; otherwise continue until the iteration limit. section 12.2
Figure 12.3 An example of the k-means algorithm with k==3. Dataset points are initially lightly shaded. Step 1: k centroids (shaped as pentagons) are randomly created. Each centroid is assigned a different color: RGB. Step 2: For each point, measure the distance to all centroids, and assign the point to the closest one. At the end, each centroid C will define a cluster, a sphere centered at C and whose radius is the distance to the furthest point assigned to C. The clusters are highlighted in the same color as their centroids. Step 3: Update the centroids: for each cluster, compute its center of mass. Step 4: Repeat steps 2 and 3 j times. Some points will switch to a different cluster.
Trace convergence visually as points move between clusters while centroids are repeatedly reassigned to cluster centers. section 12.2
