1. Unsupervised Learning and the Clustering Problem

1.1 Finding Structure in Unlabeled Data

Unsupervised learning algorithms operate without target labels. The goal is not to predict a target class, but to discover underlying patterns, groupings, or structures within the input features. Clustering is the task of grouping data points such that points in the same group (a cluster) are more similar to each other than to points in other groups. It is widely used in customer segmentation (grouping users by purchasing behavior), anomaly detection (identifying outliers that do not fit into any cluster), and image compression (quantizing colors).

To cluster data, we must define what "similarity" means. Generally, similarity is modeled as a distance metric in a high-dimensional vector space. If two points lie close together, they are similar; if they are far apart, they are different. K-Means operates on this geometric assumption, aiming to group points into tight, spherical clusters by minimizing the distance between points and their group's central mean.

1.2 Hard vs Soft Clustering

Clustering algorithms generally fall into two categories: (1) **Hard Clustering**: each data point belongs to exactly one cluster (like in K-Means). (2) **Soft Clustering**: each data point is assigned a probability of belonging to each cluster (like in Gaussian Mixture Models). Hard clustering is simple and computationally efficient, but can be too rigid for points that lie directly on the boundary between two clusters. Choosing between hard and soft models depends on whether your application requires absolute group assignments or probabilistic uncertainty metrics.

Common Misconception — K-Means Can Find Clusters of Any Shape: A common misconception is that K-Means can successfully cluster any group of points. Because K-Means uses distance to centroids, it assumes that clusters are spherical and roughly equal in size. If your data contains elongated, crescent-shaped, or nested clusters, K-Means will fail to partition them correctly. In those cases, density-based algorithms like DBSCAN or spectral clustering must be used instead.

2. The K-Means Objective: Minimizing Within-Cluster Variance

2.1 The Mathematical Cost Function

Let $X = \{x_1, x_2, \dots, x_n\}$ be a set of $n$ observations in a $d$-dimensional vector space $\mathbb{R}^d$. K-Means aims to partition these observations into $k$ sets $S = \{S_1, S_2, \dots, S_k\}$ to minimize the sum of squares within each cluster. The cluster centroid $\mu_i$ is defined as the mean of the points assigned to cluster $S_i$. The objective function, also known as the **Within-Cluster Sum of Squares (WCSS)** or **Inertia**, is defined as:

Here, $\|x - \mu_i\|$ represents the Euclidean distance between a point $x$ and the centroid $\mu_i$. The algorithm seeks to find the partition $S$ that minimizes this cost function. Minimizing WCSS globally is an NP-hard optimization problem. To solve it in practice, we use an iterative heuristic called Lloyd's algorithm, which converges to a local minimum.

3. The Lloyd's Algorithm Cycle: Assignment and Update Steps

3.1 The Two-Step Loop

Lloyd's algorithm optimization cycle consists of two alternating steps: (1) **The Assignment Step**: assign each data point to its nearest centroid. Formally, we assign point $x_j$ to cluster $S_i$ if:

(2) **The Update Step**: recalculate the positions of the centroids to be the mathematical mean of all points assigned to that cluster:

The algorithm repeats these two steps until the centroid positions stop changing (convergence) or a maximum iteration limit is reached. Since each step reduces or maintains the total WCSS cost, the algorithm is guaranteed to converge, typically requiring fewer than 30 iterations in practice.

Mermaid Diagram: The iterative Lloyd's algorithm loop showing assignment, update, and convergence checks.

4. Distance Metrics: Euclidean Distance vs Other Vector Spaces

4.1 Euclidean Distance Properties

K-Means relies on the Euclidean distance metric (the $L_2$ norm) to measure similarity. The Euclidean distance between two vectors $p$ and $q$ in $d$-dimensional space is defined as:

Euclidean distance is isotropic (equal in all directions), which is why K-Means tends to generate spherical, circular clusters. This works well for spatial coordinate data, but has drawbacks in high-dimensional space due to the **curse of dimensionality**: as the number of features $d$ increases, the distance between any two points converges to a constant value, reducing clustering performance.

Pitfall — Using K-Means on Categorical Data: Applying Euclidean distance to categorical values (e.g. mapping "Red" to 1, "Blue" to 2) is a design mistake. The difference between 1 and 2 has no physical meaning, making the resulting centroid averages meaningless. For categorical data, you should use algorithms like **K-Modes** or convert features using binary encoding and calculate Jaccard distance metrics instead.

5. The Initialization Problem: Avoiding Bad Local Minima

5.1 Random Initialization Trap

The performance of K-Means depends heavily on the initial positions of the centroids. In the standard algorithm, centroids are initialized by picking $k$ random points from the dataset. If we get unlucky and initialize two centroids close together within the same natural cluster, the algorithm will likely partition that single cluster in half, while leaving another distinct cluster merged. Because Lloyd's algorithm only guarantees convergence to a *local* minimum, random initialization frequently gets stuck in poor layouts, requiring developers to run the algorithm multiple times with different random seeds to find the best layout.

6. Overcoming Randomness: K-Means++ Smart Initialization

6.1 The Probability-Weighted Selection

To solve the initialization problem, David Arthur and Sergei Vassilvitskii introduced **K-Means++** in 2007. Instead of choosing all centroids randomly, K-Means++ spreads them out across the dataset using a probability-weighted selection. The initialization steps are: (1) Choose the first centroid randomly from the data points. (2) For each data point $x$, calculate its distance $D(x)$ to the nearest already chosen centroid. (3) Select the next centroid randomly from the data points, where the probability of choosing point $x$ is proportional to its squared distance:

(4) Repeat steps 2 and 3 until $k$ centroids are chosen. By prioritizing points that are far from existing centroids, K-Means++ guarantees that the initial centroids are spread out across the natural clusters. This smart initialization accelerates convergence and guarantees a solution that is mathematically close to the optimal clustering layout, making it the default initialization method in scikit-learn.

7. Advanced: Scaling K-Means: Mini-Batch K-Means

7.1 Scaling to Large Datasets

When clustering datasets containing millions of observations, running standard K-Means is slow because the assignment step requires calculating distances between every single data point and all $k$ centroids on every iteration. To scale this, we use **Mini-Batch K-Means**. Instead of using the entire dataset, Mini-Batch K-Means uses small, random subsets (mini-batches) of the data on each iteration. Centroids are updated incrementally using a running average, reducing calculation times from $\mathcal{O}(n)$ to $\mathcal{O}(b)$ per iteration, where $b$ is the mini-batch size. This allows clustering of massive datasets with only a minor penalty to cluster quality.

7.2 Mini-Batch Update Formulation and Learning Rates

Unlike standard K-Means which recalculates centroids as the absolute mean of all assigned points at the end of the iteration, Mini-Batch K-Means updates centroids incrementally for each mini-batch $B$. For each point $x \in B$, we find its closest centroid $\mu_i$. We then update that centroid using a running average weighted by the number of points assigned to it over time. Let $v_i$ be the count of points assigned to centroid $\mu_i$ across all iterations. The update formula for a single point $x$ is:

Here, $\eta$ acts as a dynamically decaying **learning rate**. As more points are assigned to centroid $\mu_i$, the learning rate decreases, making the centroid positions increasingly stable and resilient to noise in later iterations. This stochastic gradient descent-like update allows the algorithm to converge significantly faster than standard batch K-Means while requiring only a fraction of the memory footprint. Below is a comparison table of standard K-Means vs Mini-Batch K-Means:

Pitfall — Over-shrinking Mini-Batch Sizes: While small mini-batches make the algorithm run fast, setting the batch size $b$ too low (e.g. $b < 50$) increases the variance of the updates. The centroids will jump around erratically and may fail to converge near the true cluster centers. The standard practice is utilizing a batch size between 512 and 4096, which balances high execution speed with stable convergence bounds.

8. Advanced: Non-Linear Clustering with Kernel K-Means

8.1 The Kernel Trick

Because K-Means uses Euclidean distance, it is restricted to finding linear boundaries between clusters. If the data contains nested circles (where one cluster surrounds another), K-Means cannot separate them. To solve this, we use **Kernel K-Means**. By utilizing a kernel function (like RBF or polynomial kernels), we implicitly project the data points into a higher-dimensional feature space where the non-linear boundaries become linearly separable. This allows us to cluster complex, non-linear patterns using the standard K-Means optimization steps.

8.2 High-Dimensional Projections and the RBF Kernel

The core logic of Kernel K-Means relies on mapping each data point $x$ to a high-dimensional feature space via a mapping function $\phi(x)$. Instead of calculating the standard Euclidean distance in the original low-dimensional space, we compute the distance in the projected space. Since calculating $\phi(x)$ directly can be computationally expensive or mathematically impossible (for example, the Radial Basis Function projects data into an infinite-dimensional space), we use the **Kernel Trick**. We replace the dot products $\langle \phi(x), \phi(y) \rangle$ with a kernel function $K(x, y)$:

Here, $\gamma$ is a scaling parameter that controls the width of the Gaussian curve. The distance between a point $\phi(x)$ and a cluster centroid $\mu_i$ in the high-dimensional space can be expanded and computed entirely using the kernel function, without ever calculating the explicit coordinates of the projected points. Let $N_i$ be the number of points in cluster $S_i$. The squared distance formula in the kernel space is:

By executing this distance calculation for every point during the assignment step, Kernel K-Means can identify ring-shaped, concentric, and highly nested clusters that are impossible to separate with standard K-Means. However, this power comes at a cost: because we must compute the kernel matrix $K(y, z)$ for all pairs of points within a cluster, the computational complexity increases to $\mathcal{O}(n^2)$ per iteration, making Kernel K-Means less suited for massive datasets unless combined with approximation methods like the Nyström method.

Pitfall — Overfitting with Small Gamma $\gamma$: Setting the scaling parameter $\gamma$ of the RBF kernel too high makes the kernel values decay extremely fast. The algorithm will treat almost every individual data point as its own isolated cluster center, leading to severe overfitting where the model fails to generalize to new data. Always tune $\gamma$ using cross-validation or grid search on a validation set.

9. Complete Python K-Means Implementation from Scratch

9.1 NumPy K-Means Code

The following complete Python class implements K-Means with K-Means++ smart initialization, utilizing NumPy for vector calculations:

10. Interactive: K-Means Iteration Simulator

Click "Step K-Means" to run iterations. Watch how the points are assigned to their nearest centroids, and how the centroids dynamically shift to the mean of their clusters, converging in 3 steps:

Elbow Method: Finding the Optimal K

The chart below displays the WCSS cost (inertia) as the number of clusters $k$ increases. The "elbow" point indicates the optimal balance between cluster tightness and model complexity:

12. Frequently Asked Questions