Welcome to the first lesson in our Unsupervised Learning module. In the previous parts of this course, we focused exclusively on supervised learning, where our goal was to predict a target variable based on labeled input data. We explored a wide range of algorithms, from linear models to complex ensembles and Support Vector Machines.
Now, we pivot to a different class of problems. In unsupervised learning, we work with data that has no predefined labels or target outcomes. The goal is not to predict, but to discover—to find hidden patterns, structures, and relationships within the data itself. One of the most fundamental tasks in this domain is clustering, which involves grouping similar data points together.
Today, we will begin our exploration of clustering with its most famous and foundational algorithm: K-Means. This lesson will explain the core mechanics of K-Means, including how it initializes its search for clusters, its iterative process of refining those clusters, and how it determines when the process is complete.
The Goal of K-Means: Finding Coherent Groups
At its heart, clustering is about partitioning a dataset. A good partition results in clusters where the data points within each cluster are very similar to each other (high intra-cluster similarity), and data points in different clusters are very dissimilar from each other (low inter-cluster similarity).
K-Means is a centroid-based algorithm. This means it represents each cluster by a central point, or centroid. The algorithm's objective is to find centroid positions and data point assignments that minimize the total distance between each data point and its assigned cluster's centroid. This distance is typically the squared Euclidean distance.
The article "K-Means Clustering: A Deep Dive into Unsupervised Learning" provides a clear definition of what K-Means tries to achieve.
K-Means Clustering: A Deep Dive into Unsupervised ...
This article introduces the core concepts and objectives of K-Means clustering.
First, read the introductory section "What is K-Means Clustering?" to get a formal definition. Next, scroll down to the "Objective of k means Clustering" section. Read the three bullet points that explain the algorithm's goals: grouping, minimizing within-cluster distance, and maximizing between-cluster distance. Finally, read the section that describes the two properties of good clusters. This will solidify your intuition about what the algorithm is trying to optimize.
The K-Means Algorithm: An Iterative Process
K-Means is an iterative algorithm, meaning it refines its clusters over several cycles until it reaches a stable solution. The entire process can be broken down into four main steps.
Let's break down each of these steps.
Step 1: Initialize Centroids
The first step is to decide on the number of clusters, K, that you want to find in your data. Once you have chosen K, the algorithm begins by placing K centroids in the feature space.
The simplest method is random initialization, where K data points are randomly selected from the dataset to serve as the initial centroids. While simple, this method can sometimes lead to poor results. More advanced techniques like K-Means++ (which we will touch upon later) place the initial centroids more strategically to improve convergence speed and quality.
Step 2: Assign Data Points (Assignment Step)
With the initial centroids in place, the algorithm iterates through every data point in the dataset. For each point, it calculates the distance to every one of the K centroids (usually using Euclidean distance). The data point is then assigned to the cluster of the closest centroid. After this step, you have K initial clusters, each consisting of all the data points assigned to its centroid.
Step 3: Update Centroids (Update Step)
Once all data points are assigned to a cluster, the "Update" step begins. For each cluster, the algorithm calculates a new centroid by taking the mean of all the data points assigned to that cluster. This new centroid represents the new center of the cluster.
Step 4: Repeat and Check for Convergence
The algorithm then repeats the Assignment and Update steps. Data points are reassigned to the new, updated centroids, and then the centroids are updated again based on these new assignments. This loop continues until a stopping condition, or convergence criterion, is met. Common convergence criteria are:
- The centroids no longer move: The change in centroid positions between iterations is negligible (below a small tolerance).
- Cluster assignments stabilize: No data points change their cluster assignment from one iteration to the next.
- Maximum iterations reached: The algorithm stops after a predefined number of iterations to prevent it from running indefinitely.
The following image provides a fantastic illustration of this iterative process.
The following resources provide more detail on these steps, including the simple mathematics behind them. Since your background is in computer science and algorithms, you will appreciate how this process is a form of iterative optimization.
The Math Behind K-Means Clustering
This article from Towards Data Science walks through the algorithm's steps with a focus on the underlying math, which is quite intuitive.
Please read the section "2.1: The Mathematics Behind K-Means". Focus on the four steps described: Initialization: How the initial centroids are chosen. Assignment: Understand that this step assigns each point x to the cluster Ci whose centroid μi has the minimum Euclidean distance. Updating: Note that the new centroid is simply the mean of all points within the cluster. Convergence: How the algorithm decides when to stop.
Bringing It All Together: A Visual and Code-Based Walkthrough
To see these steps in motion, the classic StatQuest video on K-Means is an excellent resource. It animates the entire process beautifully.
Josh Starmer's StatQuest provides a clear, animated explanation of the K-Means algorithm from start to finish.
Watch the video from the beginning. Pay attention to how the concepts we've just discussed are visualized: Initializing centroids and assigning points (Steps 1 & 2). Recalculating the centroids (Step 3). The iterative process and convergence (Step 4).
To connect these conceptual steps to implementation, the Dataquest channel offers a great tutorial on building K-Means from scratch in Python. Given your proficiency with Python and algorithms, seeing the logic translated into code will provide a deeper level of understanding.
K-means Clustering From Scratch In Python [Machine Learning Tutorial]
This "Dataquest" video demonstrates how to implement the K-Means algorithm in Python without relying on a library like scikit-learn.
Focus on the segments that correspond to the core algorithmic steps. You don't need to code along right now, but focus on how the logic is implemented: Algorithm Overview: A quick summary of the iterative steps. Centroid Initialization: See how random centroids are generated by sampling values from the data's feature ranges. Assignment Step: Observe the implementation of the Euclidean distance calculation and how it's used to assign a label (cluster index) to each data point. Update Step: Understand how groupby() and .mean() (or a variation for geometric mean in the video's case) are used to recalculate the centroid positions. The Main Loop: This is where it all comes together. Watch how the assignment and update steps are placed inside a while loop that runs until the centroids stop changing.
Conclusion
In this lesson, we transitioned into unsupervised learning and dissected the inner workings of the K-Means algorithm. You've learned that it's an iterative optimization process designed to partition data into a pre-specified number (K) of clusters.
Key Takeaways:
- Objective: K-Means aims to create clusters that are internally cohesive and externally separate by minimizing the sum of squared distances from each point to its cluster's centroid.
- Iterative Process: The algorithm follows a simple but powerful two-step loop:
- Assignment Step: Assign each data point to the nearest centroid.
- Update Step: Recalculate each centroid as the mean of the points assigned to it.
- Initialization: The process begins by selecting K initial centroids, often randomly from the data points.
- Convergence: The loop repeats until the cluster assignments or centroid positions stabilize, or a maximum number of iterations is reached.
What's Next:
We've answered how K-Means works, but we've deliberately ignored a crucial question: how do we choose the right value for K? This is one of the primary challenges when using this algorithm. In our next lesson, we will explore two popular techniques used to find the optimal number of clusters: the elbow method and the silhouette score.