k-Means Clustering

$k$-Means is an unsupervised partition-based clustering algorithm that divides a dataset of $n$ observations into $k$ distinct, non-overlapping clusters where each observation belongs to the cluster with the nearest mean (centroid).

Objective Function

The objective is to minimize the Within-Cluster Sum of Squares (WCSS), also known as Inertia:

$$J = \sum_{j=1}^{k} \sum_{i \in C_j} \| x_i - \mu_j \|^2$$

Where:

• $k$ is the number of clusters.
• $C_j$ is the set of points belonging to cluster $j$.
• $\mu_j$ is the centroid (mean vector) of cluster $j$.
• $\| x_i - \mu_j \|^2$ is the squared Euclidean distance between point $x_i$ and centroid $\mu_j$.

Algorithm Steps (Lloyd's Algorithm)

1. Initialization: Select $k$ initial centroids $\mu_1, \mu_2, \dots, \mu_k$.
2. Assignment Step: Assign each data point $x_i$ to the closest centroid: $$c^{(i)} = \arg\min_j \| x_i - \mu_j \|^2$$
3. Update Step: Recompute the centroid of each cluster as the mean of all points assigned to it: $$\mu_j = \frac{1}{|C_j|} \sum_{i \in C_j} x_i$$
4. Convergence Check: Repeat steps 2 and 3 until centroids stabilize (movement $< \epsilon$) or maximum iterations are reached.

Initialization Strategies

• Random Initialization: Randomly chooses $k$ data points as initial centroids. Prone to converging to poor local optima.
• $k$-Means++: Chooses the first centroid uniformly at random, then chooses subsequent centroids with probability proportional to the squared distance to the nearest existing centroid ($D(x)^2$). This ensures well-spaced initial centroids and substantially faster convergence.

Determining Optimal $k$

1. Elbow Method: Plot Inertia (WCSS) against different values of $k$. Look for the "elbow point" where the rate of decrease sharpens to a plateau.
2. Silhouette Score: Measures how similar a point is to its own cluster compared to other clusters (values range from $-1$ to $+1$, where higher indicates well-separated clusters): $$s(i) = \frac{b(i) - a(i)}{\max(a(i), b(i))}$$ where $a(i)$ is mean intra-cluster distance and $b(i)$ is mean nearest-cluster distance.

Python Example (scikit-learn)

from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler

# Standardize features (crucial for distance-based algorithms)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# Fit KMeans with k-means++ initialization
kmeans = KMeans(n_clusters=3, init='k-means++', random_state=42, n_init=10)
labels = kmeans.fit_predict(X_scaled)
centroids = kmeans.cluster_centers_

Strengths & Limitations

• Strengths:
  • Simple, scalable ($O(n \cdot k \cdot d \cdot i)$ time complexity), and easy to interpret.
  • Guaranteed to converge to a local optimum.
• Weaknesses:
  • Assumes spherical, equally sized clusters with isotropic variance.
  • Vulnerable to outliers (which distort the cluster means).
  • Struggles with complex, non-convex cluster geometries (better handled by DBSCAN or Spectral Clustering).
  • Requires specifying $k$ in advance.