How K-Means Finds Clusters

Okay, we've introduced the K-Means algorithm as a way to group unlabeled data into $K$ distinct clusters. But how does it actually do this? K-Means doesn't magically know where the clusters are; it finds them through an iterative process, essentially refining its guess over several steps until it settles on a reasonable grouping.

Think of it like trying to set up $K$ service centers in a neighborhood to minimize the average travel distance for residents. You might start by placing the centers randomly, then figure out which center is closest to each resident. Next, you'd move each center to the average location of the residents assigned to it. You'd repeat this process, and likely, the centers would naturally move towards the middle of actual population clusters. K-Means works in a very similar way.

The process involves two main steps that are repeated until the clusters stabilize:

1. The Assignment Step: Assign each data point to its nearest centroid.
2. The Update Step: Recalculate the position of each centroid based on the points assigned to it.

Let's break down these steps in more detail.

The K-Means Iterative Process

1. Initialization: First, we need starting points for our $K$ centroids. A common way is to simply pick $K$ data points randomly from the dataset and designate them as the initial centroids. Alternatively, they can be placed randomly within the data space. Where we start can influence the final clusters, but for now, just imagine we have $K$ initial centroid locations.

2. Assignment Step: Now, go through every data point in your dataset. For each data point, calculate its distance to each of the $K$ centroids. The most common way to measure distance here is the standard Euclidean distance (think of the straight-line distance between two points on a graph). Assign the data point to the cluster represented by the closest centroid. After doing this for all data points, you'll have formed $K$ initial groups or clusters.

3. Update Step: The initial centroids were just guesses. We can improve them. For each cluster, calculate the mean (average position) of all the data points currently assigned to that cluster. Move the centroid for that cluster to this newly calculated mean position. This new position effectively becomes the center of gravity for the points currently in that cluster.

4. Repeat: Now, with the updated centroid positions, the assignments might change. A data point that was closest to centroid A might now be closer to centroid B after B moved. So, we repeat the process:

   • Go back to the Assignment Step: Reassign all data points to their nearest new centroid.
   • Perform the Update Step: Recalculate the positions of the $K$ centroids based on the new assignments.

5. Convergence: Keep repeating the Assignment and Update steps. The algorithm has converged (finished) when the assignments no longer change significantly between iterations, meaning the centroids stop moving much, or when a predefined maximum number of iterations is reached. At this point, the centroids represent the centers of the discovered clusters, and the assignments indicate which cluster each data point belongs to.

The iterative process of the K-Means algorithm: Initialize centroids, then repeatedly assign points and update centroids until convergence.

This iterative refinement is how K-Means "finds" the underlying groups in the data. By repeatedly adjusting the cluster centers based on the current members and then reassigning members based on the new centers, the algorithm gradually pulls the centroids towards the dense areas of data points, eventually stabilizing to define the final clusters.