Clustering: K-Means, Hierarchical, DBSCAN

TL;DR: Clustering partitions unlabeled data by similarity. Reach for k-means when clusters are roughly round and you know k, DBSCAN when shapes are weird or there is noise to reject, and hierarchical when you want a dendrogram and no committed k. The hard part is not running the algorithm, it is choosing the distance metric, picking k honestly, and validating with something like silhouette instead of eyeballing a 2D projection.

K-means: minimize within-cluster variance

K-means assigns each point to the nearest of k centroids, then recomputes each centroid as the mean of its members, and repeats. It is minimizing the sum of squared Euclidean distances from points to their centroid (within-cluster sum of squares). That objective bakes in strong assumptions: clusters are convex, roughly equal in size, and isotropic (round blobs). Elongated or nested shapes break it.

Two choices dominate the result. First, k. The objective always drops as k grows, so you cannot just minimize it. Use the elbow on the inertia curve as a rough guide, but prefer the silhouette score, which rewards points that sit close to their own cluster and far from the next. Second, the distance metric: plain k-means assumes Euclidean, which is why you almost always standardize features first. A feature in dollars (range 0 to 100000) will otherwise dominate one in years (range 0 to 60). For text or embedding vectors, cosine distance fits better, so people use spherical k-means or normalize vectors to unit length.

Worked numbers: one k-means iteration is O(n * k * d). At n=100000, k=10, d=50 that is 50M ops per pass, converging in 10 to 30 passes. Initialization matters: k-means++ seeds centroids spread apart so you avoid the bad local minima that random init falls into.

Hierarchical: build a tree, cut it later

Agglomerative clustering starts with every point as its own cluster and repeatedly merges the two closest, producing a dendrogram. You do not commit to k upfront; you cut the tree at whatever height gives a sensible number of clusters. The linkage rule sets behavior: Ward minimizes variance increase (similar to k-means, gives compact clusters), single-linkage chains nearby points (finds stringy shapes but suffers chaining noise), complete-linkage favors tight balls. It is O(n^2) memory and worse in time, so it does not scale past tens of thousands of points without approximation.

DBSCAN: density and noise

DBSCAN defines a cluster as a dense region: a point is a core point if at least min_samples neighbors sit within radius eps. Clusters grow by linking core points and their reachable neighbors; points in no dense region are labeled noise (-1). This is the one to use when clusters are non-convex (two interleaving moons, a ring) or when outliers should be rejected rather than forced into a group. The cost is parameter sensitivity: eps is unintuitive and a single density threshold fails when clusters have very different densities (HDBSCAN fixes that by varying density). Tune eps with a k-distance plot, looking for the knee.

Validating clusters

Without labels, you cannot use accuracy. Internal metrics: silhouette (range -1 to 1, higher is better separation), Davies-Bouldin (lower better). With a holdout label set, use adjusted Rand index or normalized mutual information. The strongest validation is stability: re-cluster on bootstrap samples and check assignments hold. A cluster that dissolves under resampling is an artifact.

Why interviewers probe this

They want to know you match the algorithm to the data geometry, not default to k-means for everything. The strong-answer move is to name the assumption that bites: k-means assumes round equal-size clusters and Euclidean distance, so you standardize and you do not use it for crescent shapes. The held-back follow-up is usually validation ("how do you know k?") or the metric ("why standardize?"). A second favorite trap is k-means versus kNN: candidates conflate them because both involve k and nearest neighbors.

Common misconceptions

• "K-means and kNN are related." They are not. K-means is unsupervised clustering; kNN is supervised classification or regression that labels a new point by its labeled neighbors. The shared letter k means different things.
• "Lower inertia means a better clustering." Inertia falls monotonically with k, so minimizing it picks k = n. Use silhouette or the elbow, not raw inertia.
• "DBSCAN needs k." It does not. It finds the count from density. It needs eps and min_samples instead, which are their own tuning problem.
• "The 2D scatter shows the clusters." That plot is usually a t-SNE or UMAP projection that distorts distances. Validate in the original space; never trust separation seen only after nonlinear projection.

Key takeaways

• K-means: fast, assumes round equal-size blobs and Euclidean distance, so standardize features and use k-means++ init.
• DBSCAN finds arbitrary shapes and labels noise; tune eps via a k-distance knee, use HDBSCAN for varying density.
• Hierarchical gives a dendrogram and no fixed k, but is O(n^2) and caps near 10k points.
• Validate with silhouette or cluster stability under resampling; k-means is clustering, kNN is classification.