Clustering
K-Means
Lloyd's algorithm partitions n points into exactly k clusters by alternating between assigning each point to its nearest centroid and recomputing each centroid as the mean of its cluster. Convergence is guaranteed but the solution may be a local minimum.
Assign each point to the nearest centroid. Place k centroids at random. Every point joins the cluster whose centroid is closest under Euclidean distance.
Within-Cluster Sum of Squares
K-Means minimises — the total squared distance from each point to its assigned centroid . Each alternating step is guaranteed to decrease or maintain , so the algorithm converges, though not necessarily to the global minimum. Multiple random restarts mitigate this.
The elbow method plots against k. Beyond the true cluster count, adding more clusters yields diminishing returns — the curve “elbows” at the natural k.
▶sklearn — KMeans
from sklearn.cluster import KMeans
model = KMeans(n_clusters=3, random_state=42, n_init='auto')
labels = model.fit_predict(X)
print('WCSS:', model.inertia_)
# Elbow
wcss = [KMeans(n_clusters=k, n_init='auto').fit(X).inertia_ for k in range(1, 8)]Hierarchical Clustering
Agglomerative clustering builds a full merge hierarchy bottom-up. No k is required upfront — choose the number of clusters after the fact by cutting the dendrogram at a chosen height.
Start with each point as its own cluster. Every observation is its own singleton cluster. The distance matrix records pairwise distances between all n points.
Average Linkage Distance
Linkage defines inter-cluster distance. Single linkage uses the minimum pairwise distance — prone to chaining. Complete uses the maximum — produces compact clusters. Average uses the mean, balancing both tendencies and is often the most robust choice.
The dendrogram height at each merge corresponds to the linkage distance at that step. A horizontal cut at height h yields clusters whose internal maximum distance is at most h.
▶sklearn — AgglomerativeClustering
from sklearn.cluster import AgglomerativeClustering
from scipy.cluster.hierarchy import dendrogram, linkage
import matplotlib.pyplot as plt
model = AgglomerativeClustering(n_clusters=4, linkage='average')
labels = model.fit_predict(X)
# Dendrogram
Z = linkage(X, method='average')
dendrogram(Z)
plt.show()DBSCAN
Density-Based Spatial Clustering of Applications with Noise discovers clusters of arbitrary shape and explicitly marks outliers — no k required, no assumption of convexity.
Core points have ≥ MinPts neighbors within radius ε. For each point, draw a circle of radius ε. Points with at least MinPts neighbors inside the circle (including themselves) are core points.
ε-Neighborhood
Point is a core point if . A border point lies within of a core but is not dense itself. Noise points are neither core nor reachable from any core.
Choosing and MinPts requires domain knowledge. A k-distance plot (sort distances to k-th nearest neighbor, look for the elbow) is a common heuristic for .
▶sklearn — DBSCAN
from sklearn.cluster import DBSCAN
model = DBSCAN(eps=0.5, min_samples=5)
labels = model.fit_predict(X)
# labels == -1 are noise
noise_count = (labels == -1).sum()
print(f'Clusters: {labels.max() + 1}, Noise: {noise_count}')