K-means: Assignment & Update Cycle

Introduction

Welcome to our first lesson on clustering! In the previous module, we explored Principal Component Analysis (PCA), an unsupervised technique for dimensionality reduction. You learned how to find new, more informative axes in your data to create compact representations.

Now, we'll shift our focus to another major pillar of unsupervised learning: clustering. Instead of compressing data, our goal here is to discover inherent groupings within it. We'll start with one of the most popular and intuitive clustering algorithms: K-means.

Today's learning outcome is to describe the K-means algorithm's iterative process of cluster assignment and centroid updates. By the end of this lesson, you will understand the simple, yet powerful, step-by-step logic that K-means uses to partition data into distinct groups.

The Goal of K-Means

Imagine you have a scatter plot of data points. Without any labels, your eyes might naturally see a few distinct "clumps" or groups. The goal of K-means is to get a machine to identify these clumps automatically.

It does this by trying to find a user-defined number of cluster centers, or centroids, and assigning each data point to the nearest one. The "K" in K-means simply refers to the number of clusters you want to find. The algorithm's job is to figure out the best placement for these K centroids and which points belong to each cluster.

The K-Means Iterative Process

K-means is an iterative algorithm. This means it starts with a guess and repeatedly refines it until it finds a good solution. The process can be broken down into a few simple steps that are repeated until the cluster assignments stabilize.

Let's look at a visual overview of the entire process.

K-means Clustering Iterative Process Visualization — This sequence illustrates the core iterative nature of K-means. (a) We start with unlabeled data. (b) We initialize K centroids (here, K=2). (c) **Assignment Step:** Each point is assigned to its nearest centroid. (d) **Update Step:** The centroids are moved to the mean of their assigned points. (e-f) The process repeats until the assignments no longer change, and the clusters have converged.

As the image shows, the algorithm hinges on two alternating steps: assigning points and updating centroids. Let's formalize this.

The Algorithm in Steps:

Initialization: Choose the number of clusters, K, and randomly place K centroids in the data space.
Assignment Step: For each data point, calculate its distance (typically Euclidean distance) to every centroid. Assign the data point to the cluster of the nearest centroid.
Update Step: For each cluster, recalculate its centroid by taking the mean of all the data points assigned to it.
Repeat: Go back to the Assignment Step and repeat the process. The algorithm has converged when the cluster assignments no longer change between iterations.

To get a clear textual explanation of this two-step loop, let's turn to a short reading.

Visualizing K-Means Clustering

The article 'Visualizing K-Means Clustering' provides an excellent, concise explanation of the algorithm's two alternating parts.

Please read the two sections under the 'K-Means Algorithm' heading. The first section introduces the 'Reassign Points' (Assignment) and 'Update Centroids' (Update) steps. The second section elaborates on how this process leads to convergence.

Seeing the Algorithm in Action

Reading about the process is helpful, but seeing it animated really solidifies the intuition. The following video from StatQuest provides a wonderfully clear, step-by-step visualization of the K-means algorithm at work.

StatQuest: K-means clustering

This video, 'StatQuest: K-means clustering', will walk you through the entire iterative process on a simple dataset, making the assign-and-update loop very clear.

Please watch from 00:54 to 04:04. This segment demonstrates: Step 1 (00:54 - 01:30): Choosing K and randomly initializing the centroids. Steps 2 & 3 (01:30 - 02:44): The first Assignment Step (measuring distances and assigning points) followed by the first Update Step (calculating the mean to move the centroids). Step 4 (02:44 - 04:04): How the algorithm repeats these steps until the cluster assignments stop changing (convergence). Notice how the algorithm runs multiple times with different random starting points to find a better result.

The video highlights a key aspect of K-means: the process is deterministic after the initial random placement of centroids. However, because the starting positions are random, different runs can produce different final clusters. This is why standard implementations often run the algorithm multiple times with different random initializations and pick the best result.

As the video also briefly touches upon, the distance metric used is typically the Euclidean distance. Given your background, you'll recognize this as the straight-line distance between two points, calculated using the Pythagorean theorem. For a point $p$ and a centroid $c$ in an n-dimensional space, the distance is:

d (p, c) = (p_{1} - c_{1})^{2} + (p_{2} - c_{2})^{2} + \dots + (p_{n} - c_{n})^{2}

This is how the algorithm determines which centroid is "nearest" during the assignment step.

Conclusion

In this lesson, you've learned the fundamental mechanics of the K-means clustering algorithm. It's a simple but powerful iterative process for partitioning data into a predefined number of groups.

Key Takeaways:

K-means is an unsupervised clustering algorithm that groups data into K clusters.
The core of the algorithm is a two-step iterative process:
1. Assignment Step: Each data point is assigned to the cluster of its nearest centroid.
2. Update Step: Each cluster's centroid is moved to the mean of the points assigned to it.
This process is repeated until the cluster assignments no longer change, a state known as convergence.
The initial random placement of centroids can influence the final result.

Preview of the Next Lesson

Now that you understand the "what" and "why" behind the K-means process, the next logical step is to see it in action with code. In the next lesson, you will implement K-means using scikit-learn and tackle a crucial practical question: how do you choose the optimal number of clusters (K)? We will explore a common heuristic called the elbow method to help make that decision.