How do you choose between k-means and DBSCAN for clustering document embeddings?

## What each algorithm actually optimizes **k-means** partitions n points into exactly k groups so as to minimize the total squared distance from each point to its cluster's centroid. The usual algorithm alternates two steps: assign every point to the nearest centroid, then recompute each centroid as the mean of its members. It needs k as an input, it assigns *every* point, and its implicit model is that clusters are convex blobs of similar size and spread. Initialization matters (k-means++ seeding is the standard remedy), and different random seeds can give different partitions on data with no strong structure. **DBSCAN** takes no k. It takes a neighbourhood radius (`eps`) and a minimum neighbour count (`min_samples`). A point with at least `min_samples` neighbours inside `eps` is a *core point*; core points within `eps` of each other are chained into the same cluster; points reachable from a core point but not themselves core become border members; everything else is **noise**, reported in scikit-learn as label `-1`. The number of clusters is an output, cluster shapes may be arbitrary rather than spherical, and outliers are a first-class result instead of being absorbed. ## The decision rule that matters Ask whether "belongs to no cluster" is an acceptable answer. If downstream you must route every document somewhere — every ticket to a queue, every item to a shelf — a partition is what you want, and k-means (or a hierarchical cut) gives it directly. If your goal is to *find the dense pockets and ignore the rest*, density clustering is the honest tool. App-store reviews make the difference concrete. Suppose you embed a month of reviews. A few hundred are the same complaint — the login flow loops after a password reset — and they sit in a tight, dense neighbourhood. The remaining thousands are scattered one-off remarks about pricing, a typo, a feature wish. DBSCAN returns the login cluster and marks most of the tail as noise, which is exactly the summary a product manager wants. k-means with k=8 has no concept of an outlier: every scattered review is pulled into some cluster, centroids drift toward the mean of unrelated text, and the resulting groups are much harder to name. ## Why density clustering is harder on raw embedding vectors DBSCAN's `eps` is a single global distance threshold. In a space with hundreds or thousands of dimensions, the spread between nearest and farthest neighbour distances narrows, so the window in which one `eps` separates "dense" from "sparse" is narrow and hard to find. Real corpora also have clusters of genuinely different densities — a boilerplate-heavy topic is much tighter than a discursive one — and plain DBSCAN cannot use two thresholds at once. The standard mitigations, in the order people try them: - **L2-normalize the vectors** and cluster with cosine distance, so document length and verbosity do not dominate. - **Reduce to roughly 5–50 dimensions first** (UMAP is the common choice) purely as a preprocessing step for the clustering, then run density clustering there. This is the pipeline popular topic-modelling tooling uses. - **Use HDBSCAN**, the hierarchical variant, which builds a hierarchy over density levels and extracts clusters that persist across it. You give it a minimum cluster size instead of a radius, it tolerates varying density, and it still returns a noise label plus per-point membership strengths. k-means has its own scaling notes: it is cheap and linear in n per iteration, minibatch variants handle millions of vectors, and on L2-normalized vectors minimizing squared Euclidean distance ranks assignments the same way maximizing cosine similarity does — which is why "spherical k-means" on normalized embeddings is a reasonable default. ## How you know the choice went wrong With k-means: one giant catch-all cluster holding a third of the corpus, centroids that all sit near the global mean, or assignments that reshuffle substantially when you change the seed. With DBSCAN: 70% of documents labelled noise (`eps` too small or `min_samples` too high), or a single mega-cluster swallowing everything (`eps` too large). Both symptoms are diagnostic, and both are cheap to check before you show anyone a chart. ## Neighbouring options Agglomerative hierarchical clustering needs no k either: it merges bottom-up and gives you a dendrogram you can cut at whatever granularity a human finds useful, at the cost of quadratic time and memory, so it suits tens of thousands of documents rather than millions. And the most under-used answer is not to cluster at all: if the real question is "what else looks like this document?", nearest-neighbour retrieval answers it directly without committing to any global partition.