k-Means Clustering

What is k-Means Clustering?

k-Means is the most popular unsupervised clustering algorithm.

Its goal is to group unlabelled data points into $k$ distinct clusters where points in the same cluster are as close to each other as possible, while points in different clusters are far apart.

  UNLABELLED DATA ──► [ K-MEANS CLUSTERING (k=3) ] ──► DISCOVERED CLUSTERS:
                                                        - Cluster 1 (Red Centroid)
                                                        - Cluster 2 (Blue Centroid)
                                                        - Cluster 3 (Green Centroid)

Lloyd's Algorithm (Step-by-Step)

To find $k$ clusters, Lloyd's algorithm executes four steps:

  1. INITIALIZATION: Pick k starting centroid points in feature space.
        │
        ▼
  2. ASSIGNMENT STEP: Assign each data point to its CLOSEST centroid (Euclidean distance).
        │
        ▼
  3. UPDATE STEP: Recalculate each centroid position as the MEAN of all assigned points.
        │
        ▼
  4. REPEAT Assignment + Update steps until centroids STOP MOVING (Convergence!).

Objective Function: Inertia (WCSS)

k-Means minimizes Within-Cluster Sum of Squares (Inertia):

$$J = \sum_{j=1}^k \sum_{x \in S_j} | x - \mu_j |^2$$

• $\mu_j$: Centroid mean vector for cluster $j$.
• $S_j$: Set of data points assigned to cluster $j$.

Inertia measures how tightly packed data points are around their assigned cluster centroids.

The k-Means++ Initialization Smart Trick

Standard random centroid initialization can place two starting centroids right next to each other, trapping the algorithm in bad local minima.

k-Means++ (Arthur & Vassilvitskii, 2007) fixes this:

1. Pick the first centroid $\mu_1$ randomly from the data points.
2. For each remaining data point $x$, calculate distance $D(x)$ to the nearest already chosen centroid.
3. Choose the next centroid with probability proportional to $D(x)^2$.

This ensures initial centroids start spread far apart across data space, speeding up convergence and guaranteeing $O(\log k)$ optimal cost bounds.

Limitations of k-Means

1. Assumes Spherical Clusters: Fails completely on non spherical shapes (e.g. concentric circles or elongated ribbons). Use DBSCAN or Spectral Clustering instead.
2. Requires Specifying k Upfront: You must manually choose cluster count $k$ (use the Elbow Method or Silhouette Analysis).
3. Sensitive to Outliers: A single extreme outlier drags the centroid mean far off center.

Say this out loud

k-Means partitions unlabelled data into k clusters by alternating between assigning points to the nearest centroid and updating centroids to be the mean of assigned points. It minimizes Within Cluster Sum of Squares. k-means++ smart initialization spreads starting centroids far apart to avoid bad local minima. k-Means assumes spherical clusters and requires feature scaling.

Followups to expect

1. What is Mini Batch k-Means? An optimized variant that updates centroids using small random mini batches of data points instead of the full dataset, running 10x faster on massive datasets.
2. Why is Feature Scaling mandatory before k-Means? Because k-Means measures distance using Euclidean distance $|x - \mu|^2$. Features with large scales dominate distance calculations, distorting cluster centroids.