~/learn/Machine Learning · Classical algorithms
Clustering & distance
K-means, DBSCAN, choosing k, and the curse of dimensionality.
why this matters
Segmentation and anomaly questions test whether you know each clustering method's assumptions, not just its name.
K-means alternates two steps: assign each point to its nearest centroid, then move each centroid to the mean of its points. It assumes roughly spherical, similar-sized clusters, needs k up front and is sensitive to initialization (use k-means++) and to scale.
DBSCAN groups points that have enough neighbours within radius ε. It finds arbitrary shapes, labels outliers as noise and doesn't need k — but struggles when clusters have very different densities. Pick k for k-means with the elbow method or silhouette score.
Shape assumptions
k-means: ● ● ● ○ ○ ○ round blobs, every point assigned DBSCAN: ●●●●●●~~~~ × any shape, × = noise
Interview trap
In very high dimensions, distances between all points become nearly equal (curse of dimensionality), so nearest-neighbour and clustering methods degrade. Reduce dimensions first (PCA, embeddings).
key takeaways
- K-means needs k and assumes round clusters.
- DBSCAN finds any shape and flags noise.
- High dimensions break distance-based methods.
check your understanding
Your clusters are crescent-shaped and the data has outliers. Which method fits?