Recentering updates each cluster centroid by replacing it with the center of mass of its assigned points. In k-means, this follows point classification and prepares the next assignment step. section 12.2
A recentering pass proceeds as follows:
- Group points by their assigned cluster. section 12.2
- Compute the coordinate-wise mean of each cluster’s points. section 12.2
- Move each centroid to its computed center, then repeat classification and recentering until assignments stop changing or the iteration limit is reached. 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.
Follow the k-means diagram to see centroids move toward the centers of their assigned point groups across repeated passes. section 12.2
