11  Similarity, Clustering and Topic Discovery

Chapter status: drafted. Every number on this page was measured on the same Turkish product-review corpus, with the same seed and the same deduplication as Chapter 4 — though, as Section 11.1 explains, not on the same 50,000 rows — and with the sentiment labels held back until the final section. Software: scikit-learn 1.9.0, sentence-transformers 5.7.0, datasketch 2.0.0, umap-learn 0.5.12, PyTorch 2.13.0 on Python 3.14.5, encoders on an Apple M-series GPU. One result — the five-pair probe in Section 11.2 — is a hand-written diagnostic rather than a benchmark, and is labelled as such where it appears.

Learning objectives. After this chapter you can:

11.1 The corpus you cannot read

Chapter 4 competed seven representations on 40,000 labelled Turkish reviews and produced a leaderboard. Chapter 5 then asked where those labels came from and found that a 2% wobble in the test labels is enough to push the winner’s score below a rival’s measured on clean labels. Both chapters had labels. This one asks the question that comes before both: you have the documents, you have no labels at all, and somebody has to decide what is worth labelling.

That is the ordinary situation. A support inbox, a year of survey free-text, a scrape of product reviews — the documents arrive without a sentiment column, and the budget conversation from Chapter 5 (“1,000 clean labels tie with 40,000 at 10% noise”) cannot even begin until somebody knows what is in there.

So the setup is deliberately the same corpus, the same seed, and the labels locked in a drawer:

rows as downloaded   235,165
after deduplication 233,508   (1,657 exact duplicates)
label 1 (positive)   218,747   93.7%
label 0 (negative)    14,761    6.3%

stratified subsample  50,000   46,839 positive   3,161 negative
length, words         median 19   mean 22.1   p95 55   max 305
length, characters    median 132  mean 157.3  p95 393
distinct word forms   86,245

Same source, same seed, same deduplication as Chapter 4 — and, we discovered while setting up Chapter 12, not the same 50,000 rows. Chapter 4 drew its subsample with one stratified train_test_split; this chapter drew it group by group. Both are stratified, both use seed 42, both give exactly 46,839 positive and 3,161 negative — and they share 23,819 documents, 47.6%. “Same seed” is not the same thing as “same sample”, and the only way to find that out is to intersect the two and count.

The tokenizer differs too, this time on purpose. Chapter 4 used a Turkish-aware tr_lower and the pattern [a-zçğıöşü]+; this chapter deliberately uses stock str.lower() and a bare \w+, which is what you get if you do not think about it. The lowercasing half changes nothing on this corpus, which ships already lowercased; the pattern half does, because \w+ also keeps digits, _ and letters outside the Turkish alphabet. That difference is one of two reasons the form counts here (86,245) and there (74,317) are not comparable; the other is that 52.4% of the rows are different documents. Two confounded causes, and we can name both only because we went and intersected the samples. Neither pattern treats a combining mark as a letter, and that shared blind spot is the whole subject of Section 11.9.

The labels exist, and no model on this page is fitted against them: not the representations, not \(k\), not the algorithms. “Used only for scoring” would still be too tidy, so here is the exact position. The labels appear in two places. First, they are the answer key for the adjusted Rand index reported across the whole \(k\)-sweep below. Second, Section 11.10 scores the triage curve against them — and there they also decide something: the order the clusters are read in. That makes the second result an oracle one, meaning it used information a real user would not have. Section 11.10 says so where it reports the number. That discipline is the whole experiment: it is very easy to tune an “unsupervised” pipeline until it reproduces a label you have been peeking at, and the result is a number that will not survive contact with a corpus that has no labels.

Here is what the chapter will end up reporting, so you can read the middle knowing where it goes:

What this chapter measured
what we asked what came back
How many near-duplicates survive exact deduplication? 0.30% of documents, but 1.06% if you move the threshold by 0.1
Does clustering recover the sentiment labels? No. Best ARI anywhere: 0.0083
Do the internal validity indices agree on how many clusters there are? No. Three representations gave 50, 4 and 2
Does a density-based method find clusters? No. Never more than 3, on 53–100% noise
Does the best topic-coherence score mark the best topic? No. The top-scoring topic was tokenizer debris
So the clustering was worthless? No — and that is the interesting part
What did it actually find? A shipping Unicode bug, and 56% of the complaints for 13% of the reading

The last two rows are not a rhetorical trick. Four of the seven headline answers above are a flat negative, and the chapter still ends with a clustering pipeline that does real work. Getting from one to the other requires changing the question, and learning to notice when the question is wrong is more transferable than any of the algorithms below.

What we will look at. First the question every clustering method answers badly if you skip it: what “similar” means for your documents. Then the cheapest win in the chapter — removing the near-duplicates — before any clustering runs. Then k-means and its four assumptions, an honest sweep that does not go the way the tutorials suggest, and what to do when the shape is wrong. Then topic models, and finally the thing this chapter is really about: what a failed clustering is still worth.

11.2 What “similar” has to mean before you can cluster

Every algorithm in this chapter is a way of grouping points that are close together. None of them defines “close”. You do, when you pick a representation and a distance, and that choice determines the answer far more than the choice of clustering algorithm does.

Three distances, and what each one assumes

For documents represented as vectors, three measures cover almost all practice.

\[ \operatorname{cos}(a, b) = \frac{a \cdot b}{\lVert a \rVert \, \lVert b \rVert} \qquad d_{\text{euc}}(a, b) = \lVert a - b \rVert_2 \qquad J(A, B) = \frac{|A \cap B|}{|A \cup B|} \]

Cosine measures the angle and ignores the length. That is usually what you want for text, because a 300-word review and a 30-word review about the same thing should be similar, and their raw count vectors differ in magnitude by a factor of ten. Euclidean distance takes length seriously, which makes it the honest choice when magnitude carries meaning — and note that between two unit vectors the two rank pairs identically, so for ranking purposes the distinction disappears.1 Jaccard works on sets rather than vectors, which is what makes it the basis of the near-duplicate machinery in Section 11.3.

cosine similarity — the cosine of the angle between two vectors; 1 means the same direction, 0 means perpendicular. Ignores how long the vectors are, which is usually a feature for text and occasionally a bug. ↩︎

A cosine of 0.98 does not mean what you think

Here is the trap that costs the most time in practice. The raw value of a cosine similarity is not interpretable on its own. It is only interpretable against the distribution of similarities that the same model produces for unrelated documents.

We took 3,000 random reviews and scored all 4,498,500 pairs among them, in each of four spaces:

Two unrelated Turkish reviews, scored by four representations
space dims mean cosine sd 1st–99th percentile
tf-idf (sparse) 23,971 0.0182 0.0287 0.000 – 0.130
LSA (SVD to 256) 256 0.0654 0.0794 −0.026 – 0.330
MiniLM 384 0.3051 0.1503 −0.009 – 0.669
multilingual-E5 768 0.8547 0.0278 0.783 – 0.916
The same cosine means four different things
SPACE WHERE TWO UNRELATED REVIEWS LAND 0.0 0.25 0.50 0.75 1.0 cosine similarity 0.8 “similar” threshold tf-idf 23,971 dims mean 0.018 LSA 256 dims mean 0.065 MiniLM 384 dims mean 0.305 E5 768 dims mean 0.855 Bands cover the 1st–99th percentile of 4,498,500 random pairs. Tick = mean.

Read the dashed line. A dashboard that flags document pairs above 0.8 as “similar” flags almost nothing under tf-idf, LSA or MiniLM, and almost the entire corpus under E5 — where two unrelated reviews already score 0.855. The threshold did not change. The geometry did.

Two reviews with nothing in common score 0.855 on average under E5, and 98% of all random pairs land between 0.78 and 0.92. A dashboard that flags “similar documents” above 0.8 would flag almost the entire corpus. The absolute number is a property of how the encoder was trained — its anisotropy, the tendency of all its vectors to point in roughly the same direction, so that even unrelated texts share a large common component. This is the same geometry that Chapter 3 measured on word vectors and reported to be even stronger in contextual models. It is not a property of your documents at all.

Notice also that the usable range is not the same as the nominal range. Both E5 and tf-idf put 98% of their random pairs inside a window about 0.13 wide — but E5’s window is nominally an interval of length 2, of which it uses 6.6%, and it sits bunched up at the far right. tf-idf’s window starts at zero, so a score of 0.13 really is near the top of what that space produces. Same width, completely different meaning, and only one of them behaves like the fraction it resembles.

Calibrate before you threshold. Before choosing any similarity cutoff, score a few thousand random pairs from your own corpus with your own encoder and look at the distribution. If you skip this, you are picking a threshold against a scale you have not measured. Steck et al. (2024) makes the stronger version of this argument: for some models the cosine similarity does not correspond to any meaningful notion of similarity at all, and the fact that it is bounded in \([-1, 1]\) lends it a false air of being a percentage.

The pair that has now defeated three chapters

Chapter 4 ended on a failure. Two Turkish reviews, four words each, opposite meanings, and both unigram tf-idf and averaged word vectors scored them identical (word bigrams, as that chapter notes, do tell them apart — but only because the order happens to fit inside a two-word window):

a = "kalite iyi fiyat kötü"      (quality good, price bad)
b = "kalite kötü fiyat iyi"      (quality bad, price good)

Chapter 6 fixed it, because an n-gram model reads order and a bag of words does not. The obvious expectation is that sentence embeddings — trained on meaning, on dozens and up to about a hundred languages, with attention over the whole sentence — also fix it.

They do not. We measured five hand-written pairs designed to separate the things a clustering pipeline needs separated. Each score is reported twice: as a raw cosine, and as a \(z\)-score against that model’s own random-pair distribution from the table above, which is the only way to compare across models whose scales differ this much.

A \(z\)-score restates a raw number as “how many standard deviations above average is this?”: \(z = (x - \mu)/\sigma\). Here \(\mu\) and \(\sigma\) are the mean and spread of the random-pair cosines in the table above. So \(z = 4\) means the pair is far more similar than two documents picked at random, whatever the model’s raw scale happens to be. E5’s 0.9894 and tf-idf’s 1.0000 look alike as cosines and are worlds apart as \(z\)-scores.

A five-pair diagnostic. Five hand-written pairs are a probe, not a benchmark — read the direction, not the decimals.
pair tf-idf MiniLM E5
cos \(z\) cos \(z\) cos \(z\)
contradiction same words, opposite claims 1.0000 34.2 0.9649 4.4 0.9894 4.8
paraphrase same claim, different words 0.5349 18.0 0.9479 4.3 0.9827 4.6
polarity flip one word changes the verdict 0.5687 19.2 0.6518 2.3 0.9525 3.5
negation one suffix changes the verdict 0.4999 16.8 0.7201 2.8 0.9528 3.5
unrelated different subject, same sentiment 0.1626 5.0 0.1871 −0.8 0.8785 0.9

Read the first row against the second. In all three representations the contradiction pair scores higher than the genuine paraphrase. Two sentences that assert opposite things are judged more similar than two sentences that assert the same thing in different words — by tf-idf, by MiniLM, and by E5.

Three observations, in increasing order of how much they should change your behaviour:

  1. Sentence embeddings did not repair the Chapter 4 failure. E5 scores the contradiction pair 0.9894. The problem was never sparsity, and it was never vocabulary. Word order still carries the meaning and the pooled sentence vector still mostly does not.
  2. On these five pairs, MiniLM separates polarity more sharply than E5. MiniLM drops 2.0 \(z\) from its paraphrase score to the polarity flip and 1.5 \(z\) to the negation; E5 drops 1.1 \(z\) to both. Resist the obvious conclusion. Five pairs cannot rank two models, and Section 11.10 measures the opposite at corpus scale: E5 concentrates negative reviews 4.23× against MiniLM’s 2.79×. This is the chapter’s own rule biting the chapter — when a probe and a measurement disagree, believe the measurement. What survives is the weaker, more useful claim: a model can be better overall and worse on the one axis you happen to care about, so the axis is worth measuring separately.
  3. tf-idf ranks the polarity flip above the paraphrase (0.5687 against 0.5349) and is the only representation to get that pair backwards, which is exactly what a method with no notion of word meaning should do: kargo çok hızlı geldi and kargo çok yavaş geldi share three words out of four.

Hold on to point 1. It predicts, before we run a single clustering algorithm, that sentiment is not the direction any of these geometries will split on first — and Section 11.5 is where that prediction gets tested.

On the honesty of this table. Five pairs written by one person to make a point is the weakest kind of evidence in this book, and it is here because it explains a corpus-scale result rather than replacing it. Of the three observations above, only the first survives contact with the corpus-scale numbers: Section 11.5 confirms that none of the three geometries splits on sentiment, while Section 11.10 directly contradicts the model ranking in observation 2. That is the correct outcome for a probe. It generates hypotheses; it does not settle them. When a probe and a measurement disagree, believe the measurement — including when the probe is one you wrote yourself and like.

11.3 Near-duplicates: the cheapest win available

Before clustering anything, remove the documents that are already copies of each other. Section 11.1 removed 1,657 exact duplicates by comparing strings. Exact matching is a weak test — one changed character defeats it — and a cluster built on repeated boilerplate is measuring the boilerplate.

Shingling, MinHash, and why you do not compare every pair

Comparing all pairs of 50,000 documents means \(1.25 \times 10^9\) comparisons. The standard escape has three steps (Broder 1997):

  1. Shingle. Turn each document into a set of overlapping \(k\)-grams. We used character 5-grams rather than word shingles on purpose: Turkish agglutination means two near-identical reviews can differ in several word forms while sharing nearly every character run.
  2. MinHash. Hash the set 128 times and keep the minimum under each hash. The probability that two documents share a given minimum equals their Jaccard similarity, so 128 numbers estimate \(J\) without storing the sets.
  3. Band and bucket (LSH) (Indyk and Motwani 1998). Split the 128 values into bands, hash each band, and only compare documents that collide in at least one band. Pairs below the threshold almost never collide, so almost all of the \(10^9\) comparisons never happen.

MinHash — a fixed-length sketch of a set, built so that the chance two sketches agree in a position equals the Jaccard similarity of the original sets. Lets you estimate overlap without keeping the sets. ↩︎

Why 1.25 billion comparisons never happen
1 · document kargo çok hızlı geldi 50,000 of these 2 · shingle {“kargo”, “argo ”, …} character 5-grams 3 · MinHash [17, 4, 92, …] 128 integers, P(agree) = J 4 · band + bucket hash each band, compare only colliding pairs 5 · verify exact Jaccard, then union-find 131 groups COMPARISONS ACTUALLY PERFORMED all pairs 1.25 × 10⁹ pairs LSH candidates a sliver of that — 27.4 seconds, single core The bands are the whole trick: pairs below the threshold almost never collide, so they are never scored.

Stages 2 and 3 turn a set of unknown size into a fixed 128 numbers, which is what makes stage 4 possible. Stage 5 computes the exact Jaccard on the survivors, so LSH never changes what you conclude about a pair it hands you — it changes which pairs it hands you.

Where the approximation actually lives, and it is not where you would guess. Stage 4 produces no false positives that survive stage 5, but it does produce false negatives: a genuinely similar pair can fail to collide in every band and is then never scored at all. How often? datasketch splits our 128 hashes into \(b\) bands of \(r\) rows to balance the two error types at the threshold you asked for, subject to \(b \cdot r \le 128\), and a pair of Jaccard similarity \(J\) collides with probability \(1 - (1 - J^{r})^{b}\). At threshold=0.8 it picks \(b=9\), \(r=13\) — which uses 117 of the 128 permutations and discards the remaining eleven, worth knowing if you are counting your hash budget:

   J     P(pair is even looked at)
  0.9              0.93
  0.8              0.40
  0.7              0.08

A pair sitting exactly at the threshold has a 40% chance of being found. That is not a bug — it is the deliberate design point, the steepest part of the S-curve, where the method trades recall for the speed that makes it possible at all. But it means the counts in the next table are lower bounds, and they are loosest precisely at the boundary you nominated. Report near-duplicate counts as “at least”, never as “exactly”.

We then ran union-find over the surviving candidate pairs, so a chain of near copies counts as one group rather than several pairs. Union-find is the standard bookkeeping for “these things are all connected”: every document starts in its own group, each surviving pair merges two groups into one, and a chain \(a \sim b \sim c\) ends as a single group of three even though \(a\) and \(c\) were never compared with each other.

The count depends on the threshold, and not gently

One number decides how much you delete, and it is a number nobody can hand you: at what Jaccard similarity are two reviews “the same review”? Move it and watch the answer move with it.

Near-duplicates surviving exact deduplication, 50,000 documents
Jaccard threshold groups redundant docs share of corpus largest group time
≥ 0.9 57 60 0.12% 3 28.0s
≥ 0.8 131 151 0.30% 6 27.4s
≥ 0.7 265 529 1.06% 61 28.4s

Moving the threshold from 0.8 to 0.7 multiplies the redundant-document count by 3.5 and the largest group by ten. That is not a bug in the method; it is what the corpus looks like. Here are three groups at \(J \ge 0.8\):

group 1   "teşekkürler hepsiburada.com ;)"
          "teşekkürler hepsiburada!"
          "teşekkürler hepsiburada....."

group 2   "güzel tavsiye ederim"
          "ürün çok güzel tavsiye ederim."
          "isıtması çok güzel tavsiye ederim"

group 3   "herkese tavsiye ederim"
          "herkese tavsiye ederim,fiy"
          "herkese tavsiye ederim :)"

Group 1 is boilerplate and should go. Group 2 is three different people saying a generic thing about three different products, and deleting two of them throws away real data. At a low enough threshold, “near-duplicate” and “short and generic” become the same category, which is why the largest group jumps to 61 at \(J \ge 0.7\).

A defensible default. Deduplicate at \(J \ge 0.8\), then read the largest five groups before accepting the result. If the largest group is short generic text rather than boilerplate, raise the threshold. This chapter kept \(J \ge 0.8\), leaving 49,849 documents, and every number after this point is computed on that set.

Section 8.2 treats deduplication as a measured quality lever for pretraining corpora, where the stakes are much higher and where Lee et al. (2022) found real gains — and where Penedo et al. (2024) found that the most aggressive deduplication made the data worse. The same tension appears here in miniature at a corpus five orders of magnitude smaller.

SimHash (Charikar 2002) solves the same problem with a different sketch: it produces one bit-vector per document and measures Hamming distance, which makes it cheaper to store and a natural fit when you need to check a new document against a large existing index. Manku et al. (2007) is the account of running it at web scale. For a one-off corpus audit, MinHash with LSH is easier to reason about and datasketch implements it in a dozen lines.

11.4 Three representations, and what they cost

Everything from here runs on the same 49,849 documents in three geometries, chosen to span what a practitioner actually picks between in 2026.

The three geometries, on one laptop GPU
representation dims build time notes
tf-idf → LSA 256 2.6s word tf-idf, SVD to 256; no GPU, fully deterministic
MiniLM 384 40s paraphrase-multilingual-MiniLM-L12-v2, 117.7M params, 1,246 docs/s
multilingual-E5 768 104s intfloat/multilingual-e5-base, 278.0M params, 478 docs/s

Two details worth stating because they change results and are easy to skip.

The SVD is not optional. Raw tf-idf here is 23,971 dimensions with 19.3 non-zero entries per document. The diagnostic that matters is relative contrast — for a given document, how much further away its farthest neighbour is than its nearest one, \((d_{\max} - d_{\min}) / d_{\min}\). If that number is near zero, “nearest” is not meaningfully different from “farthest” and every distance-based method is running on noise. Measured over 300 query documents:

                 median relative contrast
tf-idf                   0.539
LSA (256)                2.116
MiniLM                   4.911
E5                       3.009

Fifty-one documents live at the origin. min_df=3, max_df=0.5 deleted every token that 51 of the 49,849 documents contained, so their LSA rows are exactly zero and cannot be \(\ell_2\)-normalised. They sit at the origin, get swept into whichever cluster is nearest it, and are counted in every LSA table in this chapter. Fifty-one out of fifty thousand does not move a number, but “my vectors are all unit length” was still false, and we only knew that because we checked.

For 0.6% of tf-idf queries some other document sits at cosine distance exactly 0, which makes \(d_{\min} = 0\) and the ratio infinite. Distance zero means cosine similarity one: two reviews whose tf-idf vectors are proportional, which on 19-word reviews happens whenever two people write the same short sentence. (The opposite case — no shared terms at all, which is common here — gives cosine similarity 0 and distance 1, and is harmless: it lands in \(d_{\max}\).) Those are excluded from the median rather than patched with an epsilon, because they are a real property of the space. Reducing to 256 dimensions with truncated SVD recovers 29.9% of the variance and multiplies the contrast by four. (Truncated SVD is PCA without the mean-centring step: it keeps the directions that explain the most variance, and skipping the centring keeps the sparse matrix sparse.) That reduction is itself a topic model, and it has a name — latent semantic analysis (Deerwester et al. 1990) — which is why Section 11.8 can reuse it for free.

Note that E5 needs no such repair despite its 1st-to-99th band being 0.133 wide, about the same as tf-idf’s 0.130. Band width alone does not diagnose the problem; contrast does. Contrast is computed on distances (\(1 - \cos\)), and there the two bands trade places: E5’s random-pair distances sit close to zero (0.08–0.22), so a 0.13 spread is large relative to them, while tf-idf’s sit near one (0.87–1.00), where the same spread is small.

E5 needs its prefix. The multilingual-E5 models are trained with query: and passage: markers and behave measurably differently without them (Wang et al. 2024). For a symmetric task like clustering, the model card prescribes query: on both sides, which is what we used. Forgetting this is one of the most common silent errors in embedding pipelines: nothing crashes, the numbers are simply worse.

The ablation this chapter owes E5, and did not run. A random-pair mean of 0.8547 says these embeddings share one dominant direction. Removing it is one line — subtract the corpus mean, then re-normalise: X -= X.mean(0); X /= np.linalg.norm(X, axis=1, keepdims=True) — and it is the obvious control for every negative result that follows. If the flat silhouette curve in Section 11.6 and the 99.5% HDBSCAN noise rate in Section 11.7 survive centring, they are properties of the corpus. If they do not, they were properties of the encoder’s anisotropy and we would have been reporting an artefact of the instrument as a finding about the data. Stronger versions of the same control exist: removing the top few principal components as well (“all-but-the-top”, Mu et al. (2018)), or whitening (rotating and rescaling so the covariance becomes the identity). We ran none of them, and every negative result below should be read with that gap in view; it is the first thing to run before quoting any of them.

11.5 k-means, and the four assumptions it makes for you

k-means is the default for a reason: it is simple, it is fast, and Lloyd’s algorithm (Lloyd 1982) converges in a handful of passes. Pick \(k\) centres, assign every point to its nearest centre, move each centre to the mean of its assigned points, repeat.

Writing down its objective makes the assumptions visible. k-means minimises

\[ \sum_{i=1}^{k} \sum_{x \in C_i} \lVert x - \mu_i \rVert^2 \]

and in doing so commits you to four things, none of which anyone chose:

  1. Clusters are spherical. The objective only measures distance to a centre, so it cannot represent an elongated or curved group.
  2. Clusters have similar extent. A tight cluster and a diffuse one are scored on the same scale, so the diffuse one gets torn up and its pieces handed to its neighbours.
  3. Every point belongs to a cluster. There is no outlier class. A document that resembles nothing gets assigned anyway, to whichever centre is least wrong.
  4. You already know \(k\). It is an input, not an output.

k-means — partitions points into \(k\) groups by repeatedly assigning each point to the nearest group centre and recomputing the centres. Fast, and commits you to spherical, similarly-sized, all-inclusive groups. ↩︎

The four assumptions, drawn
1 · spherical one group, cut in two 2 · similar extent the diffuse one gets torn up 3 · no outliers assigned anyway, no noise label 4 · you know k k = ? 2 · 10 · 50 an input, not an output Everyone worries about panel 4. On text corpora it is panels 2 and 3 that do the damage.

None of these are bugs — they are the objective working correctly. Minimising squared distance to a centre is the assumption that groups are round, equally spread, and exhaustive. If your data disagrees, the algorithm will not tell you; it will simply return a partition.

Assumption 4 is the one everybody worries about; assumptions 2 and 3 are the ones that actually break text corpora.

One property of the algorithm, as opposed to the objective, also matters. Lloyd’s algorithm only walks downhill from wherever it starts, so it stops at a local minimum of the objective, and different starting centres can give different partitions. That is why implementations run it several times (n_init) and keep the run with the lowest objective. Use k-means++ initialisation (Arthur and Vassilvitskii 2007), which picks each new starting centre with probability proportional to its squared distance from the centres already chosen, so the starts are spread out. It is scikit-learn’s default and it removes the worst of this dependence on lucky starting points — but note that it addresses none of the four assumptions.

The sweep

We ran \(k\) at fourteen values spanning 2 to 50 on all three representations, scoring each partition four ways. Three of the scores are internal: they use only the vectors, so you can compute them on a corpus with no labels, which is the situation this chapter is about. The fourth is external: it compares the partition against the hidden sentiment labels, and it is the answer key.

Fourteen values of \(k\), three representations, four scores

The shape to notice is the absence of one. No curve has a knee, no silhouette reaches 0.11, and on the ARI setting every line lies flat on zero. Switch the radio and read the four scores against each other rather than each on its own.

Switch the radio to adjusted Rand index and note the dashed line at zero. ARI is corrected for chance, so 0 is what a random partition scores. All three curves sit on it.

Reading the sweep

A table with three representations and fourteen values of \(k\) can be read several ways, and most of them flatter somebody. Here is the reading that does not.

The external verdict first, because it is unambiguous. The best adjusted Rand index anywhere in the sweep is 0.0083, at MiniLM with \(k=3\). ARI is chance-corrected, so 0.0 is what random assignment scores and 1.0 is a perfect match. Several entries are negative. Normalised mutual information tops out at 0.0416. Across 42 clusterings and three representations, none of them recovered the sentiment label.

Section 11.2 predicted this. If a representation scores a contradiction pair above a paraphrase, polarity is not the dominant axis of variation in that geometry — and \(k\)-means partitions along dominant axes, so it will cut on something else. Note the exact strength of the claim: polarity has not vanished from the geometry. Section 11.10 extracts a 4.23× signal from these same E5 vectors, and Chapter 4 got 76.21 macro-F1 out of a bag of words. A supervised method can go looking for a minor direction because the labels tell it which one to find. An unsupervised one cannot, and so it reports the major direction instead. The clustering did not fail; it faithfully reported the structure it was given.

The internal indices do not agree with each other, or with themselves. This is the more troubling result, because internal indices are all you have on a genuinely unlabelled corpus:

Where each internal index puts its optimum, over \(k \in [2, 50]\)
representation silhouette says \(k\) = Calinski-Harabasz says Davies-Bouldin says
LSA 50, and still rising 2 50
MiniLM 4 2 40
E5 2 2 4

Calinski-Harabasz picks \(k=2\) every time. It is a variance ratio, and on data with no strong cluster structure it tends to fall as \(k\) grows — a tendency these three sweeps show, not a theorem. It is not guaranteed monotone, and a corpus with genuine structure at some \(k\) can put a peak there, which is what the index is for. Davies-Bouldin drifts the other way, toward large \(k\), for the mirror-image reason — but only where it moves at all.

That last clause is the important one, so read the actual values rather than the argmin. On E5 the whole sweep from \(k=2\) to \(k=50\) lies between 4.44 and 4.77, which makes the “optimum” at \(k=4\) a 7% wobble on a flat line. MiniLM does move at first — from 4.24 at \(k=2\) to 3.33 at \(k=10\) — and then goes flat: everything from \(k=20\) upward sits between 3.23 and 3.28, so its “optimum” at \(k=40\) is a 1% wobble on a plateau.

For two of these three, the differences around the chosen \(k\) are too small to support choosing it at all — the argmin is real, and it is not a decision.

Only LSA keeps falling all the way, and even it wanders before it commits: 6.38 at \(k=2\), up to 7.17 at \(k=4\), back down to 6.41, up again to 6.52 at \(k=6\), and only then falling without interruption to 4.105 at \(k=50\).

A 43% fall from its peak, against a 7% wobble on E5 and a 1% wobble across MiniLM’s plateau. That is what the difference between a trend and noise looks like when you plot it instead of taking the argmin.

That is the real lesson of the table, and it is worse than mere disagreement: the three indices do not just pick different \(k\), they pick numbers that in two cases out of three are not distinguishable from the neighbouring values. An index that reports an argmin will always report one. It is on you to check whether the surface it is minimising over has any shape.

Every silhouette in this table is small. The scale runs to 1.0; the best value anywhere in the sweep is 0.1042. A silhouette near zero means the average point is about as close to its neighbouring cluster as to its own. That is not a mediocre clustering, it is a corpus with no well-separated clusters in this geometry — and the number is telling you so.

Watch the largest-cluster column. At \(k=2\) on LSA, one cluster holds 81.1% of the corpus. That is the classic degenerate outcome: k-means, forbidden from declaring outliers, produces one enormous bag and a much smaller cluster. The partition is technically valid and completely useless.

11.6 How many clusters?

Given the table above, the honest answer to “what is the right \(k\)” for this corpus is there isn’t one, and the rest of this section is about how to tell that apart from “I have not looked hard enough”.

What the indices actually measure

All three indices claim to say in one number how “good” a clustering is (higher is better for silhouette and CH, lower for DB), which is exactly the kind of claim worth opening up. What is each one actually rewarding?

\[ s(i) = \frac{b(i) - a(i)}{\max\{a(i),\, b(i)\}} \]

The silhouette of point \(i\) compares \(a(i)\), its mean distance to points in its own cluster, against \(b(i)\), its mean distance to points in the nearest other cluster (Rousseeuw 1987). It runs from \(-1\) to \(1\), and the score for a clustering is the mean over all points. Two implementation details that change the number and are almost never reported: it is \(O(n^2)\), so on 49,849 documents we computed it on a fixed random sample of 10,000 (seed 42), which makes every silhouette here an estimate with its own error bar; and “distance” is metric="cosine" throughout, matching the geometry the clustering was actually done in. A silhouette quoted without its metric and its sample size is not a reproducible number.

silhouette — for each point, how much closer it is to its own cluster than to the next-nearest one, scaled to \([-1, 1]\). Near 0 means the point sits on a boundary; a whole corpus near 0 means there are no boundaries. ↩︎

Calinski-Harabasz is a variance ratio carrying an explicit correction for \(k\):

\[ \mathrm{CH} = \frac{\operatorname{tr}(B_k)}{\operatorname{tr}(W_k)} \times \frac{n-k}{k-1} \]

with \(B_k\) and \(W_k\) the between- and within-cluster dispersion matrices. That \((n-k)/(k-1)\) factor is the main reason it falls as \(k\) grows on data with no real structure: the dispersion ratio improves slowly and the correction shrinks fast. Davies-Bouldin takes, for each cluster, the worst of its pairings and then averages:

\[ \mathrm{DB} = \frac{1}{k}\sum_{i=1}^{k} \max_{j \neq i} \frac{s_i + s_j}{d(\mu_i, \mu_j)} \]

with \(s_i\) the mean spread inside cluster \(i\); lower is better. Because it is a max over pairs, it tends to improve as \(k\) rises and clusters get individually tighter — the mirror image of CH’s bias, which is exactly why the two disagree in our sweep. Both are cheap, both are \(O(n)\) in the number of points, and — as the sweep shows — both are close to monotone in \(k\) on data without real cluster structure, which makes their “optimum” an artefact of the range you happened to search.

One caveat the sweep table hides, and it is our own rule being bent. silhouette_score takes a metric argument and ours was "cosine"; calinski_harabasz_score and davies_bouldin_score take none. Both are defined on squared Euclidean dispersion around raw centroids, and scikit-learn ships no cosine variant of either. On \(\ell_2\)-normalised vectors that is less damaging than it sounds for points, since \(d^2 = 2 - 2\cos\) makes the two an affine reparametrisation of each other; it is not harmless for centroids, which are means of unit vectors and so are not themselves unit vectors. So read the CH and DB columns as Euclidean measurements of a cosine clustering. That is exactly the mismatch Section 11.13 warns you about, and the honest reason we tolerated it is that the alternative was implementing both indices ourselves. Part of “the indices disagree” may be the metric disagreeing rather than the indices.

One qualification before you carry “silhouette below 0.11” anywhere else. It is tempting to blame E5’s low values on its tiny distances — its random-pair cosine distances all live between roughly 0.08 and 0.22 — but that is not an explanation. The silhouette is a ratio, \(b - a\) over \(\max\{a, b\}\), so multiplying every distance by the same constant leaves it exactly unchanged. What the silhouette does depend on is how the distances are arranged: whether a point’s own cluster is much closer than the next one, relative to the distances themselves. That arrangement can change when the representation changes — removing the shared direction behind E5’s 0.855 mean moves some documents more than others — so recomputing the silhouette after mean-centring is still the check to run, and we did not run it. The relative contrast in Section 11.4 asks a different question and gives a different answer: E5 scores 3.009 there, which says the neighbour ranking carries structure that a partition into \(k\) groups does not capture. Read the silhouette as a within-representation comparison across \(k\). Treat any cross-representation comparison with suspicion, and never give it an absolute meaning.

We also owe you the error bar we promised. We did not compute one: every silhouette here is a single estimate from a single 10,000-document sample, so the third decimal is not a quantity anyone should act on, and the gap between MiniLM’s “optimum” at \(k=4\) (0.1042) and its neighbour at \(k=3\) (0.1018) is not a gap we can defend. Five disjoint samples would give a standard deviation in an afternoon. Until they do, what survives is only the statement that every value in the table sits far below 0.2 — which happens to be the only part of the column the argument needs.

The elbow method deserves its reputation

The oldest recipe is to plot inertia against \(k\) and look for the bend. Inertia is just the k-means objective from Section 11.5 evaluated at the solution — \(\sum_i \sum_{x \in C_i} \lVert x - \mu_i \rVert^2\), the total squared distance from every point to its own centre.

It is popular because it always produces an answer. Which is also exactly the problem.

Inertia decreases monotonically in the optimum — more centres can only bring every point closer to the nearest one. That is not a promise of a bend: a straight declining line is monotone and has no elbow at all, and where you think you see one depends on your axis limits. (Run k-means independently at each \(k\) and the measured curve can tick upward, because each run lands in its own local solution; that is a symptom of the restart lottery, not a counter-example to the elbow’s uselessness.) Schubert (2023) makes the case at length, and the summary is blunt: the elbow criterion should not be used, and it survives because it is easy to draw rather than because it is informative.

A better default than any index. Cluster at three or four values of \(k\), sample 20 documents from each cluster, and read them. If you cannot write a one-line description of a cluster that a colleague could then use to sort new documents, that cluster is not real, whatever the silhouette says. The criterion “the number of groups a human can act on” is not an evasion — it is the only criterion that is connected to why you are clustering at all.

When you do have labels, use them

If some labelled subset exists, external validation is far more informative than any internal index. Three standard measures, starting with the simplest:

  • Purity gives each cluster the label of its majority and counts the share of documents that end up correctly labelled that way. It is easy to explain and easy to fool. One document per cluster scores a perfect 1.0, and on a corpus that is 93.7% positive any partition scores at least 0.937, because every cluster’s majority can simply be “positive”. On our data, purity cannot tell a good clustering from a random one.
  • Adjusted Rand index (Hubert and Arabie 1985) counts pairs of documents that the two partitions agree about — both in the same group, or both in different groups — and corrects that count for chance: \(\mathrm{ARI} = (\mathrm{RI} - \mathbb{E}[\mathrm{RI}]) / (\max \mathrm{RI} - \mathbb{E}[\mathrm{RI}])\), where RI is the raw share of agreeing pairs. So random agreement scores 0, a perfect match scores 1, and a negative ARI means the partitions agree less than chance.
  • Normalised mutual information asks how much knowing the cluster tells you about the label: the mutual information \(I(C; L)\) between clusters \(C\) and labels \(L\), divided by an average of their entropies \(H(C)\) and \(H(L)\) so that it lies between 0 and 1. V-measure (Rosenberg and Hirschberg 2007) is the same quantity under a particular normalisation — v_measure_score is normalized_mutual_info_score with average_method="arithmetic", not a separate measure. Neither is corrected for chance, so both can reward a partition merely for having more clusters. The correction has a name and ships in the same module: adjusted mutual information (Vinh et al. 2010), which subtracts what a random partition of the same shape would have scored, exactly as ARI does for pair counts. Report AMI, not NMI, whenever \(k\) varies across the runs you are comparing. Note that the bias is not visible in our own sweep — MiniLM’s NMI falls from 0.0392 at \(k=2\) to 0.0142 at \(k=50\), and E5’s peaks at \(k=6\) — which is the right reason to use the corrected estimator rather than to argue about whether the bias showed up this time.

All of them answer the question is this partition the label partition? Keep that phrasing in mind, because Section 11.10 is going to show it is the wrong question.

11.7 When the shape is wrong: density-based clustering

Every k-means result above is subject to assumption 3: every point belongs to a cluster. On a corpus of product reviews that is plainly false. A good share of reviews are short, generic praise and belong to nothing in particular. A method that is allowed to say noise should therefore do better — and it is worth running precisely because the way it fails is more informative than the way k-means fails.

HDBSCAN builds a hierarchy of density levels and then extracts the clusters that persist longest across that hierarchy (Campello et al. 2013; McInnes and Healy 2017). It has no \(k\). Its main knob is min_cluster_size: the smallest group you are willing to call a cluster. Everything not dense enough to qualify is labelled \(-1\) and left out. It is the hierarchical successor of DBSCAN (Ester et al., 1996), which asks you for a single radius eps and so assumes one density level for the whole corpus. HDBSCAN removes that knob and lets each region have its own density.

HDBSCAN — finds clusters as regions denser than their surroundings, at whatever density each region happens to have, and labels the rest noise. No \(k\) required, and no obligation to assign every point. ↩︎

We swept min_cluster_size at three values on each representation, leaving min_samples at its default. State what that default is, because it is the single most consequential thing about the table below: in both sklearn.cluster.HDBSCAN and the hdbscan package, min_samples=None means min_samples = min_cluster_size. So these are not three points on one axis — each row moves the density estimate and the cluster-size floor together, and the noise rate responds mostly to the first. The result is the same in every cell, and it is not a subtle one.

HDBSCAN on 49,849 documents. Every setting either swallows half the corpus in one blob or throws almost all of it away
representation min_cluster_size clusters noise largest cluster time
LSA 25 2 52.9% 47.0% 674s
LSA 100 2 97.1% 2.4% 219s
LSA 500 0 100.0% — 198s
MiniLM 25 2 55.1% 44.8% 285s
MiniLM 100 3 90.0% 9.2% 248s
MiniLM 500 0 100.0% — 1495s
E5 25 2 99.5% 0.3% 612s
E5 100 0 100.0% — 1530s
E5 500 0 100.0% — 2631s

Read each representation’s three rows together. On LSA and MiniLM, min_cluster_size = 25 finds two clusters, one of which holds roughly half of everything and the other of which is a rounding error; the remaining half is noise. That is not a discovery of structure, it is a description of one big lump. Raise the threshold to 100 and the lump stops qualifying as dense, so 90–100% of the corpus becomes noise. Raise it to 500 and there is no cluster anywhere in 49,849 documents at any density level.

E5 is the extreme case and the most instructive one. Even at min_cluster_size = 25 — the most permissive setting we tried — it calls 99.5% of the corpus noise and returns a largest cluster of 0.3%. Raise the threshold at all and it finds nothing whatsoever — zero clusters, 100% noise, after 44 minutes of work at min_cluster_size = 500.

Why E5, of all spaces? Section 11.4 already warned that band width diagnoses nothing, and by the contrast measure it prefers, E5 (3.009) is a better space than LSA (2.116). The tempting next answer is E5’s compressed scale: its random-pair cosine has a standard deviation of 0.0278, against MiniLM’s 0.1503 — a fifth of the spread. That answer does not survive a second look. With the default cluster_selection_epsilon=0, HDBSCAN returns exactly the same clusters if every distance is multiplied by the same constant, because core distances, mutual reachability distances and cluster stabilities all scale together. A small absolute scale therefore explains nothing on its own. Measured against its own mean distance (\(1 - 0.8547 \approx 0.145\)), E5’s spread is about 0.19 — close to MiniLM’s 0.22, and more than twice LSA’s 0.085. What HDBSCAN actually needs is variation in local density: regions where each point’s min_samples-th nearest neighbour is much closer than it is elsewhere. In E5 that variation is evidently too weak, and we have not measured why. The two obvious suspects are the shared direction (the centring ablation in Section 11.4 would test it) and the way distances in general bunch together in high-dimensional spaces. A large gap between a point’s nearest and farthest neighbour does not guarantee that density varies from one region to another, and density-based methods need the second. Note the irony: E5 is the representation that performed best in Section 11.10 and the one where density-based clustering fails most completely. Those are not in tension — they measure different things — but a practitioner who tried only HDBSCAN would have discarded the winning model.

Noise rates of 90–100% are a measurement, not a failure. HDBSCAN is telling you something true and specific: at the scale of hundreds of documents, this corpus has no regions that are meaningfully denser than their surroundings. It is one cloud with gradients, not a set of islands. k-means could not tell you that, because k-means is required to return \(k\) clusters whether or not any exist.

That is the honest reading, and it also explains the k-means sweep. The silhouette never rose above 0.1042 not because we searched the wrong \(k\) but because there are no boundaries to find. Two methods with completely different assumptions agree, which is worth more than either result alone.

How far that claim is entitled to go. HDBSCAN has three consequential dials and we moved one of them. min_samples sets the tightness of the density estimate and is what the noise rate mostly responds to; cluster_selection_epsilon is a flat distance floor that stops over-fragmentation; cluster_selection_method chooses between "eom" and "leaf" extraction. A sweep that separates the first from min_cluster_size — hold min_samples at 5 or 10 while min_cluster_size varies — and a non-zero epsilon are the two follow-ups we owe this table. Until they are run, “this corpus has no density structure” is a claim about three points on one axis of a three-dimensional parameter space, supported by the k-means agreement above rather than by the sweep alone.

Note also the cost. The min_cluster_size = 500 run on MiniLM took 1,495 seconds — 25 minutes — to conclude that there is nothing there. Density-based clustering on high-dimensional data is not cheap, and its running time is not monotone in min_cluster_size — which is itself a symptom of the coupling above, since raising min_cluster_size raises min_samples, and min_samples is the \(k\) of the core-distance nearest-neighbour query that dominates the cost.

The standard workaround, and its cost. The usual advice is to run UMAP (McInnes et al. 2018) down to 5–15 dimensions first, then HDBSCAN on the projection. This is what BERTopic does by default (Grootendorst 2022), and it does produce clusters. Be clear about why: UMAP is a non-linear method that manufactures local density by pulling neighbours together and pushing everything else apart. Clusters found in a UMAP projection are partly a property of UMAP. They can still be useful — but “HDBSCAN found clusters after UMAP” is not evidence that the original space had them, and the numbers above are what the original space actually looks like.

The same caution applies to the 2-D pictures people draw with UMAP or t-SNE. They keep who is next to whom reasonably well, but the size of a blob and the gap between two blobs in the plot are largely set by the method and its settings, not by the data (Wattenberg et al., 2016). Use such a plot to decide which documents to read, never as a measurement. PCA is the linear alternative: a projection onto the directions of largest variance, which squashes distances but never stretches one region more than another. It is less dramatic, and on text it often shows a single cloud; when the other evidence says there are no islands, that is the more faithful picture.

Two families we did not run, and why you might

Agglomerative clustering merges the closest pair of groups repeatedly and hands you a dendrogram instead of a \(k\). That is a direct answer to Section 11.6: rather than taking an index’s argmin, you look at where the merge distances jump. The linkage setting decides what “closest pair of groups” means: their closest members (single), their farthest members (complete), the average over all cross-group pairs (average), or the smallest increase in within-group variance (Ward, Euclidean only). Single linkage tends to chain everything into one long group; average and Ward give rounder groups. It also takes metric="cosine", linkage="average" natively, so unlike Calinski-Harabasz and Davies-Bouldin it can be scored in the same geometry the clustering was done in. The cost is \(O(n^2)\) memory, which on 49,849 documents means clustering a sample.

A \(k\)-nearest-neighbour graph plus Leiden (Traag et al. 2019) is the recipe that has become standard for embedding clustering outside NLP, notably in single-cell genomics (Seurat, Scanpy), and it has the best claim on this corpus of anything we did not try. It relies mainly on who neighbours whom rather than on the absolute scale of distances (some implementations do weight edges by distance). E5’s relative contrast (3.009) says its nearest neighbours stand clearly apart from its farthest — a sign the neighbourhood information may be usable, not a guarantee. And it does not need density to vary from region to region, which is what HDBSCAN needs and did not find. If you take one experiment from this section into your own work, take that one. It is the natural third assumption set. If a third method also finds no clear structure, the evidence strengthens; if it finds structure, you learn why the first two agreeing was misleading. Either outcome is informative.

11.8 Classical and embedding-era topic models

Clustering gives you a label per document. A topic model gives you a list of words per group, which is what you actually show a stakeholder. The two are not competitors so much as two halves of the same deliverable, and in 2026 there are three families worth knowing, in increasing order of how much they cheat.

LDA: the generative story

Latent Dirichlet allocation (Blei et al. 2003) posits that each document is a mixture over \(K\) topics and each topic is a distribution over the vocabulary, both drawn from Dirichlet priors, and then asks which topics best explain the words you observed. It is genuinely probabilistic: a document is 60% topic 3 and 30% topic 7, not assigned to one bucket. It dominated topic modelling for fifteen years and it is still the thing people mean when they say “topic model”.

Its assumptions are also worth stating, because they fit our corpus badly. LDA is a bag-of-words model over documents, and it needs each document to contain enough words to estimate a mixture from. The median review here is 19 words. Estimating a ten-way mixture from 19 tokens is asking a lot.

NMF: the same shape, without the priors

Non-negative matrix factorisation (Lee and Seung 1999) factors the document-term matrix \(V \approx WH\) under the single constraint that \(W\) and \(H\) have no negative entries. Because nothing can cancel, the parts it finds are additive, and on text that tends to produce readable word lists. It has no generative story and no priors — it is a matrix decomposition — which turns out not to matter much in practice, and it is usually run on tf-idf rather than raw counts, which suits short documents better.

Cluster, then describe: c-TF-IDF

The third family skips the modelling entirely. You already have clusters from Section 11.5. Treat each cluster as one long document, concatenate everything in it, and score its words by term frequency within the cluster against inverse frequency across clusters:

\[ W_{t,c} = \operatorname{tf}_{t,c} \times \log\!\left(1 + \frac{A}{\operatorname{tf}_t}\right) \]

where \(\operatorname{tf}_{t,c}\) is term \(t\)’s frequency in cluster \(c\), \(A\) the average number of words per cluster, and \(\operatorname{tf}_t\) the term’s frequency across the whole corpus. This is c-TF-IDF, the trick at the centre of BERTopic (Grootendorst 2022). The words it ranks highest are those frequent in this cluster and infrequent corpus-wide — which is nearly but not exactly “common here and rare elsewhere”, since \(\operatorname{tf}_t\) includes cluster \(c\)’s own contribution. For a small cluster the difference is negligible. For a cluster holding half the corpus it is not, and its characteristic words get penalised for being characteristic of it. Worth knowing before you wonder why your largest cluster’s label is so bland.

It is worth being clear about what has happened here. c-TF-IDF is not a topic model; it is a labelling procedure applied to somebody else’s clustering. All the modelling was done by the embedding and by k-means. Nor did BERTopic invent the family: top2vec (Angelov 2020) embeds documents and words into one space, clusters the documents with HDBSCAN, and reads the word vectors nearest each cluster centroid as the topic — the same skeleton with a different labelling step, two years earlier. Leaving the modelling to the embedding is a feature — it means the semantic work is done by a model trained on far more text than your corpus contains — but it also means the topics inherit every flaw of the clustering, as Section 11.9 is about to demonstrate at our expense.

Scoring them

To compare, we need a number. Topic coherence measures whether a topic’s top words actually co-occur in real documents. The standard variant is NPMI (Bouma 2009):

\[ \operatorname{NPMI}(w_i, w_j) = \frac{\log \dfrac{P(w_i, w_j)}{P(w_i)\,P(w_j)}}{-\log P(w_i, w_j)} \]

averaged over all word pairs in a topic’s top-10 list, then over topics. It runs from \(-1\) to \(1\); positive means the words appear together more than chance.

The formula is not computable until you say what “together” means, and the answer changes the numbers substantially, so state it: co-occurrence here is at the document level. \(P(w_i)\) is the fraction of the 49,849 reviews containing \(w_i\) at least once, and \(P(w_i, w_j)\) the fraction containing both — a review is one context, and repeats inside it do not count twice. The alternative convention, a sliding window of 10 or 20 tokens, is standard for long documents and makes no sense on a 19-word review. Pairs that never co-occur are \(\varepsilon\)-smoothed to \(-1\) rather than allowed to diverge. All probabilities come from the corpus itself over a fixed 8,651-term vocabulary with a hand-written Turkish stop-word list, so the five methods are scored on exactly the same footing.

One note on which coherence, because you will meet a different one. gensim.CoherenceModel’s most-used setting — and the default in most BERTopic tutorials — is C_v, not NPMI. C_v wraps NPMI in an indirect cosine confirmation step over context vectors, which made it correlate slightly better with human ratings in the original evaluation (Röder et al. 2015) and made it considerably harder to reason about: its values are not comparable across vocabularies, it is known to be unstable, and the documentation of Palmetto — the tool from the team that defined C_v — itself came to advise against using it. We use NPMI because we can write down what it computes in one line, which is the only thing that makes the next table checkable.

Ten topics, one corpus, one coherence measure. LDA is both the slowest and the least coherent
method NPMI fit time what it needs
LDA, \(K=10\) +0.0737 133.1s raw counts
NMF, \(K=10\) +0.1183 1.0s tf-idf
c-TF-IDF on LSA \(k\)=10 +0.1340 0.03s an existing clustering
c-TF-IDF on MiniLM \(k\)=10 +0.1002 0.02s an existing clustering
c-TF-IDF on E5 \(k\)=10 +0.1064 0.02s an existing clustering

The headline is uncomfortable for the classical method. LDA is 133× slower than NMF and scores lower on coherence — with the implementation named, because at this margin the implementation is half the story. sklearn.decomposition.LatentDirichletAllocation by default fits by batch variational Bayes (learning_method="batch") and stops after max_iter=10 passes, and we left doc_topic_prior and topic_word_prior at their defaults of \(1/K\). Collapsed Gibbs sampling (MALLET; in Python, tomotopy or the lda package — gensim’s LdaModel uses online variational Bayes, not Gibbs) is slower still and usually produces better topics, and lowering \(\alpha\) is the standard short-text remedy for exactly the problem diagnosed below. So read the row as scikit-learn’s default LDA loses to scikit-learn’s default NMF on 19-word reviews — which is the comparison a practitioner actually faces, but not a verdict on the model family.

The direction is what the short-text literature reports, and that literature exists for a reason: if your documents are short, the Dirichlet mixture has almost nothing to estimate a per-document topic distribution from. Models built for this regime — the biterm topic model (Yan et al. 2013), which models word pairs pooled across the corpus rather than documents, and the Dirichlet multinomial mixture (Yin and Wang 2014), which assigns one topic per document instead of a mixture — are the principled answer; a plain matrix factorisation on tf-idf is the cheap one. If you have inherited an LDA pipeline on short text, running NMF beside it takes an afternoon and will probably end the argument.

The three c-TF-IDF rows cost effectively nothing, because the clustering was already paid for. And they produce recognisably different word lists. Here is what E5 plus c-TF-IDF returns for three of its ten clusters:

topic 2  koku  kokusu  parfüm  kalıcı  güzel  tavsiye  parfümü  aldım
topic 3  kitap kitabı  tavsiye  güzel  ederim  sürükleyici  okudum  akıcı
topic 9  telefon  iyi  şarj  yok  güzel  telefonu  gayet  ürün  var

Perfume, books, phones. Nobody told the model these categories exist. This is the thing clustering is genuinely good at, and note that it is a product category structure — not the sentiment structure we were secretly hoping for in Section 11.5, which is why the ARI was zero.

Coherence is a proxy, and it is a weak one. Chang et al. (2009) ran the experiment everybody should have run first: they asked humans to spot the intruder word in a topic’s word list, and found that the models with the best held-out likelihood produced the least interpretable topics — an automated metric diverging from human judgement. Their metric was likelihood, not coherence; NPMI-based coherence came later. For coherence measures, a more recent meta-evaluation, Hoyle et al. (2021), shows that automated coherence measures do not reliably track human judgements of topic quality, and that evaluation practice in the field is inconsistent enough that published comparisons often are not comparable to each other; Doogan and Buntine (2021) reaches the same conclusion from the applied side. Automatic topic metrics are convenient, not trustworthy. The next section is a case where our own coherence number was not merely imprecise but pointed in exactly the wrong direction.

11.9 The bug the clustering found

Look again at the scoreboard. c-TF-IDF on LSA scored +0.1340, the best of the five. Coherence is supposed to reward topics whose words genuinely go together, so the natural next step is to read the topic that earned it. Here are the per-topic scores for that run:

topic    0       1       2       3       4       5       6       7       8       9
NPMI  .1095   .0654   .0566   .0591   .1059   .0933   .1022   .5075   .1879   .0523

Topic 7 scores +0.5075 — nearly three times the next best, and the single highest per-topic coherence anywhere in the experiment. Its words:

topic 7   bi  ye  fi  tavsi  çi  ederi  si  ni  li  yi

Those are not words. They are fragments. And the method scored them as the most coherent topic in the chapter, because they are extremely coherent — they co-occur almost perfectly, since they are all produced by the same defect in the same documents.

Tracing it

The chain is short and every link is checkable in a REPL:

>>> "TAVSİYE".lower()
't a v s i ̇ y e'                     # spaced out here: 8 codepoints, not 7
>>> [f"U+{ord(c):04X}" for c in "TAVSİYE".lower()]
['U+0074','U+0061','U+0076','U+0073','U+0069','U+0307','U+0079','U+0065']

İ is U+0130, LATIN CAPITAL LETTER I WITH DOT ABOVE — a normal letter in Turkish, where dotted and dotless i are different letters. Python’s str.lower() is not locale-aware. It lowercases U+0130 to i (U+0069) followed by U+0307, COMBINING DOT ABOVE, because a plain i already carries a dot and Unicode has no precomposed “i with an extra dot above” to fold into.

One fact about this corpus changes where the chain starts. As Chapter 4 found, the reviews ship already lowercased: there is no uppercase letter left in them, so our own str.lower() call creates nothing here. The combining dots were already in the text when it reached us — most likely left by exactly this default lowercasing somewhere upstream. The REPL lines above show how such a mark is born; the steps below show why nothing downstream removes it.

Now the second link. Normalisation does not save you:

>>> "\u0307" in unicodedata.normalize("NFC",  "TAVSİYE".lower())    # True
>>> "\u0307" in unicodedata.normalize("NFKC", "TAVSİYE".lower())    # True

Both NFC and NFKC leave the sequence intact, for the reason above: there is no composed form to normalise to. The habit of “just NFKC everything” is exactly what lets this survive to production.

The third link is the tokenizer. scikit-learn’s default token pattern is (?u)\b\w\w+\b, and a combining mark is not a word character, so:

>>> re.findall(r"(?u)\b\w\w+\b", "TAVSİYE".lower())
['tavsi', 'ye']
>>> re.findall(r"(?u)\b\w\w+\b", "tavsiye")
['tavsiye']

Tavsiye, “recommendation” — a word that appears in 19.8% of the documents in this corpus, the single most frequent review-specific word in it — silently splits in two, but only in the documents whose text carries the stray mark — presumably those where somebody once typed it with a capital İ.

Four steps from a capital letter to a broken vocabulary
1 · the source TAVSİYE İ = U+0130 7 codepoints 2 · .lower() t a v s i + U+0307 8 codepoints, not 7 3 · normalise NFC → unchanged NFKC → unchanged nothing to compose to 4 · tokenize \w\w+ ['tavsi','ye'] one word became two AND k-MEANS FOUND IT WITHOUT BEING TOLD LSA cluster 7 1,365 docs 94.7% contain U+0307 everywhere else 48,484 docs 6.0% → 15.8× enrichment The clustering was given 256 LSA dimensions and no information about Unicode whatsoever.

Step 3 is the one that catches people. “We normalise everything to NFKC” feels like it should cover this, and it does not — there is no precomposed character for an i carrying an extra dot, so normalisation has nothing to do and reports success.

The one-line fix, and why neither .lower() nor .casefold() is it. Deleting the combining mark after lowercasing — s.replace("\u0307", ""), written as an escape because the character is invisible in print — restores ['tavsiye']. Note that str.casefold() does not help. It is not locale-aware either and produces the identical eight codepoints, which is worth knowing because “use casefold instead of lower” is the usual folk fix and it is wrong here. Python’s standard library has no Turkish casing at all; for real locale-aware casing you need ICU (PyICU: icu.UnicodeString(s).toLower(icu.Locale("tr"))). For most pipelines the cheaper and fully sufficient answer is to map the two Turkish letters yourself before lowercasing — which is exactly what Chapter 4’s tr_lower does. Keep the two jobs apart, though. tr_lower stops your code from creating the mark; it cannot remove a mark that is already in the text, as it is in this corpus. Only the replace above repairs text you were given. Whatever you choose, the test to keep in your suite is assert tokenize("TAVSİYE") == tokenize("tavsiye").

A second guard catches the same class of failure without knowing any Turkish: flag any topic whose top-10 list is more than half short tokens — sum(len(w) <= 3 for w in top10) > 5. Topic 7 scores 8 out of 10 on that test. It will raise occasional false alarms on languages with genuinely short content words, and looking at them costs one line.

What it cost

The bug is interesting. What it cost is the part worth putting in front of anybody who thinks a leakage check is optional.

The damage, measured
measurement value
documents containing U+0307 4,183 (8.39% of corpus)
share of those inside LSA cluster 7 30.9%
cluster 7 size 1,365 documents
cluster 7 documents affected 94.7%
affected everywhere else 6.0%
enrichment inside the cluster 15.8×
vocabulary types that exist only because of the bug 1,607
net vocabulary change once fixed 86,196 → 85,224

The vocabulary here is 86,196, not the 86,245 reported at the top of the chapter. Two unrelated reasons, and it took a re-run to separate them: 45 of the 49 are one-character tokens — digits, _, and single letters — that scikit-learn’s actual default pattern \b\w\w+\b discards and the setup’s bare \w+ kept; the other 4 died with the 151 near-duplicates removed in Section 11.3. Neither decision was made consciously. Count your vocabulary the same way twice, or do not compare the numbers.

Read the middle rows carefully, because they are the point of this section. k-means was given no information about Unicode. It was given 256 LSA dimensions. It nevertheless assembled a cluster that is 94.7% affected against a 6.0% background — it found the bug, precisely and unprompted, and it did so because a systematic text defect is a real axis of variation in the data, and the clustering’s job is to find real axes of variation.

The invented vocabulary is 1,607 types that no Turkish speaker ever wrote: alişveri, acti, alternati, alabi. That is 1,607 features in a tf-idf matrix spent on nothing, and every one of them dilutes the document frequency of the real word it was cut from.

The net change is smaller than 1,607, and the gap is worth a sentence because it is easy to get backwards. Repairing the text removes those 1,607 fragments and creates 635 types that had never appeared in one piece before — alişverişim, acemiliğini, admin — words that existed in this corpus only in broken form. So the vocabulary goes 86,196 → 85,224, a net shrink of 972, which is 1,607 removed minus 635 restored. The fix does not merely delete; it gives you back words you did not know you were missing.

Not all of them come back correctly spelled, though: alişverişim is still wrong. When ALIŞVERİŞ was lowercased upstream, the dotless capital I became i (not ı) along with the İ. Deleting U+0307 does not undo that second error, and since I → i leaves no marker behind, this route cannot even find it; the IŞIK check in the lab (Section 11.15) is how you catch it in your own pipeline.

This is the argument for clustering, stated honestly. The clustering scored ARI ≈ 0 against the labels. By the metric of Section 11.6 it found nothing. It also isolated a real defect in the text — in a language with 80 million speakers — from 256 numbers per document and no instruction to look for one. Unsupervised methods are how you find out what is in your data, including the parts you did not put there on purpose.

Be precise about what is impressive here, because the tempting version of this story is false. Chapter 4 did not miss this bug. It documents the "İYİ".lower() failure explicitly, defines tr_lower so that its own code cannot cause it, counts the stray U+0307 marks already in the text, and sets an exercise asking you to strip them and measure the damage. That chapter knew, because a human who speaks Turkish knew and wrote it down.

What is worth noticing is that the clustering rediscovered it. Chapter 4 needed a Turkish speaker; \(k\)-means needed nothing but the vectors, and it will do the same on a corpus in a language nobody on your team reads. That is the transferable claim, and it is the smaller of the two — which is exactly why it is the one to keep. A method that only finds bugs you already knew about is worthless; a method that finds them without being told what a bug looks like is a tool you can point at anything.

And it is an extreme case, on our own numbers, of an automated metric diverging from human judgement (Chang et al. (2009) showed this for likelihood, Hoyle et al. (2021) for coherence measures). The topic with the best coherence in the entire chapter was the topic with no meaning at all. Drop it and average the nine that remain: LSA’s c-TF-IDF coherence falls from +0.1340 to +0.0925, below both MiniLM (+0.1002) and E5 (+0.1064), which moves it from first place to last among the three c-TF-IDF rows. The metric did not merely fail to notice the garbage — it ranked the method first because of it.

Strictly, +0.0925 is a nine-topic mean being compared against ten-topic means, so it is not a like-for-like swap. It does not need to be: the point is the size of the move. One topic out of ten, and one that a human would reject in two seconds, was carrying enough of the average to reverse the ranking.

11.10 The payoff: what a “failed” clustering is worth

Time to answer the question the chapter has deferred twice. ARI ≈ 0 says the partition is not the label partition. It does not say the partition is useless, and conflating those two is the most common way people talk themselves out of a result that would have helped them.

So ask a question a practitioner actually has. You have a labelling budget. You can read 5,000 of these 49,849 reviews. Does knowing a document’s cluster change which 5,000 you should read?

The corpus is 93.66% positive, so 6.34% negative. Read at random and 6.34% of what you read is a complaint. Now unhide the labels and measure the positive rate inside each cluster at \(k=10\) — a diagnostic we could only run because this corpus happens to have labels; the clustering never saw them.

The number in the last column is lift: the negative rate inside a cluster divided by the negative rate in the corpus as a whole. Lift 1.0 means the cluster is no better than reading at random; lift 4.0 means a document drawn from it is four times as likely to be a complaint. It is the direct answer to “where should I spend my reading budget”, which is why we want it and not ARI.

Clusters are far from label-pure — and far from uninformative
representation positive rate, lowest cluster → highest negative lift in the worst cluster
LSA 89.4% → 98.9% 1.67×
MiniLM 82.3% → 99.4% 2.79×
E5 73.2% → 99.5% 4.23×

E5’s worst cluster is 26.8% negative against a 6.34% base rate. It holds 13.25% of the corpus — 6,605 documents — so that rate carries a 95% Wilson interval of 25.7%–27.9% and the lift runs 4.06×–4.40×. Print the interval, and print the cluster size that produces it: a lift quoted without its denominator is a number nobody can check, and Section 11.15 asks you for exactly this on your own corpus. The interval is narrow enough that the effect is not in doubt — every document you pull from that cluster is about four times as likely to be a complaint as one drawn at random. That is a large effect, and ARI could not see any of it, because ARI asks whether the whole partition reproduces the whole labelling and the answer to that is no.

Notice what just happened to the model ranking. Under ARI the three representations were indistinguishable — all ≈ 0, best 0.0083. Under the decision-relevant measure they separate cleanly and in the order you would expect: 1.67× / 2.79× / 4.23×. The metric was not measuring nothing; it was measuring the wrong thing.

Same three clusterings, two questions, opposite answers
THE QUESTION ARI ASKS “is this the label partition?” LSA MiniLM E5 0 −0.0094 −0.0007 +0.0075 verdict: indistinguishable THE QUESTION A PRACTITIONER ASKS “where should I spend my reading?” LSA MiniLM E5 1.67× 2.79× 4.23× verdict: a clean ranking Both columns are computed from exactly the same cluster assignments. Nothing was re-run. Left: adjusted Rand index at k = 10. Right: how much denser negatives are in the worst cluster.

This is the figure to remember from the chapter. A single set of cluster assignments can be simultaneously worthless by the standard evaluation and valuable by the one attached to your actual decision. Which of the two you report is a choice you make, and most people make it without noticing.

The whole curve, not just its first point

One cluster is one point on a curve. The real question is what happens if you sort all ten clusters by their negative rate and read them worst-first: at every stopping point, what fraction of the corpus have you read, and what fraction of its complaints have you found?

Read worst-cluster-first, and the curve leaves the diagonal

The left-hand end is the only part that matters, because that is where a fixed reading budget sits. E5 buys 56% of the complaints for 13% of the reading; LSA needs 35.6% of the corpus for the same recall.

The dashed diagonal is what reading in random order gets you: read 40% of the corpus, find 40% of the complaints. Every curve above it is value the clustering created.

The single number to take away:

Reading 13.3% of the corpus — the one E5 cluster with the worst positive rate — surfaces 56.0% of every negative review in it.

That is a 4.2× improvement in the return on a fixed reading budget, from a clustering that never saw a label. If your actual job is “find the complaints so we can fix the product”, this clustering did the job, and the ARI of 0.0075 that it scored on the way is irrelevant to that job.

Read that as a descriptive result, not as a validated policy. The clusters are unsupervised, but the order they are read in is not: the ten clusters were sorted by the negative rate computed from all 49,849 gold labels, and then the recall was measured against those same labels. That is an oracle ordering scored on its own answer key, and it tells you the clusters are separable enough to be worth ranking — not how well a ranking you could actually build would do. The deployable version costs a few hundred labels: rank the clusters on a small labelled development sample, then measure recall on a disjoint test sample. Exercise 8 is that experiment, and the gap between it and this number is the honest cost of the shortcut taken here.

The ranking mostly holds along the whole curve, not just at the first point. MiniLM is above LSA at every budget, and E5 is above both over the entire range that anyone would actually operate in. LSA has to read 35.6% of the corpus to reach the recall E5 reaches at 13.3% — about 2.7 times the reading for the same result.

The honest caveat is in the tail: between roughly 76% and 85% read, MiniLM creeps above E5 by about 0.1 percentage points of recall. That is a real crossing in the data and not worth a decision, because by then both have found 97% of the negatives and you are choosing between reading three-quarters of the corpus and reading four-fifths of it. Triage curves are for the left-hand end.

What the cluster actually contains

Metrics are cheap; read the documents. Five negative reviews drawn at random from E5’s worst cluster, with translations:

ürün paslandı. almanızı tavsiye etmem
  "The product rusted. I would not recommend buying it."

hiçbir işe yaramıyor. hatta dahada kötü hale getiriyor. kesinlikle alınmaz.
  "It does nothing. It actually makes things worse. Absolutely do not buy."

ürün çok çabuk ısınıyor ve çok yavaş
  "The product overheats very quickly and is very slow."

kalitesiz, arka plaka fotoğraftaki gibi tek parça değil, montajı zor.
  "Poor quality, the back plate is not one piece like in the photo,
   hard to assemble."

hiç beklediğim gibi değildi, yorumlardaki tüm olumsuzluklar aynen çıktı.
  "Not at all what I expected; every negative thing in the reviews
   turned out to be true."

These are not subtle. They are the reviews a product manager needs on Monday morning, and the clustering put a disproportionate share of them in one bucket without being told that “complaint” is a category.

The transferable lesson. Before you report that a clustering “failed”, write down the decision the clustering was supposed to support and measure that. Purity, ARI and NMI answer “did you recover my labels”. Lift, recall at a budget, and time-to-first-insight answer “did you help”. They are different questions and they can have opposite answers on the same run.

11.11 Naming clusters with a language model

c-TF-IDF gives you ten words. A stakeholder wants a phrase. This is the one place in the pipeline where an LLM is unambiguously the right tool, and it is worth being precise about why: naming is a low-stakes, high-volume, verifiable task. Ten labels, each checkable in thirty seconds against the documents. Using language models on topics is now a documented approach rather than a trick: Pham et al. (2024) lets a model both propose the topics and assign documents to them, and compares the result with LDA and BERTopic. We use the model for only the second, safer half of that job, which is the division of labour this chapter argues for: the embedding groups, the language model describes.

The prompt follows the principle Chapter 17 develops in full — give the model the evidence, not the task description alone:

Below are the 10 most distinctive words for a cluster of Turkish product
reviews, and 8 reviews sampled from it.

Distinctive words: koku, kokusu, parfüm, kalıcı, güzel, tavsiye, parfümü,
aldım, ederim, var

Reviews:
1. ...
2. ...

Give a 2-5 word English label naming what this cluster is about. If the
reviews do not share a coherent subject, answer exactly: NO COHERENT THEME.

Three details make the difference between this being useful and being a liability:

  1. Sample the documents, do not only pass the words. The words are already a lossy summary; an LLM given only bi ye fi tavsi çi will confabulate a theme for it, which is precisely the failure Section 11.9 is about.
  2. Give it an escape hatch. The NO COHERENT THEME option is what turns the model from a label generator into a weak detector of junk clusters. A cluster the model refuses to name is a cluster you should look at yourself.
  3. Sample from the whole cluster, not just near the centroid. Centroid documents are the most typical, so a centroid-only sample makes every cluster look tidier than it is, and hides exactly the heterogeneity you want to know about before you name it.

The one number this section owes you, and does not have. Rule 2 is a claim about a detector, and this chapter’s own rule is that you do not trust a detector until you have measured it (Section 11.9 is the cautionary tale). The test is sitting right here and costs eleven prompts: run this template on all ten E5 clusters and on LSA cluster 7 — the ten tokenizer fragments with no meaning at all — and record how many E5 labels survive a 20-document spot check, how often NO COHERENT THEME fires, and whether it fires on LSA 7. We have not run it, so treat rule 2 as a design principle rather than a measured safeguard. That last cell is the one worth carrying into your own pipeline: an escape hatch that never fires is not a detector, it is decoration.

A generated label is a hypothesis, not a finding. The model has seen ten words and eight documents out of five thousand. It will produce a fluent, plausible name for a cluster that is actually three unrelated things stuck together, because producing fluent plausible names is what it does. Spot-check every label against 20 documents you sampled yourself before any of them reaches a slide.

11.12 Intuition checks

Answer each one before you open it. All six are questions this chapter settled with a measurement rather than an argument, so the answers carry numbers you can check.

Nobody can tell you yet, including you, until the random-pair background is on the table. Under tf-idf two unrelated reviews in this corpus average 0.0182 and the 99th percentile of 4.5 million random pairs is 0.1300 — so 0.91 is far off the end of the scale and “near-duplicate” is the right reading. Under E5 the same corpus has a random-pair mean of 0.8547 with a standard deviation of 0.0278 and a 99th percentile of 0.9155. There, 0.91 sits about two standard deviations above the mean of documents that have nothing to do with each other, and a duplicate detector thresholded at 0.90 would flag more than 1% of all random pairs (the 99th percentile is above it) — more than ten million pairs in a corpus of 49,849 documents.

Same number, opposite conclusions. The only thing separating them is four lines of code, run once, before you look at a single similarity.

Those two numbers say the partition is not well separated and is not the label partition. Neither of them says it is worthless, and treating them as if they did is the most common way people talk themselves out of a usable result.

The same \(k=10\) E5 clustering that scored ARI +0.0075 has a cluster that is 26.8% negative against a 6.34% base rate — a 4.23× lift — and reading 13.3% of the corpus in oracle cluster order finds 56.0% of its complaints. The clustering did not change between those two sentences; the question did.

So the honest diagnosis is rarely “the clustering failed”. It is “I scored it against a question nobody was asking”. Write down the decision the clustering was supposed to support, measure that, and only then decide.

Because k-means moves each centre to the mean of its members, so sixty copies of one sentence cast sixty votes on where that centre lands. A duplicate group is a weight, not a row. The same argument applies to every idf you fit and every topic model you run downstream.

The second reason is that the count is a free diagnostic of your collection pipeline. Ours came back at 151 redundant documents at \(J \geq 0.8\), in 27 seconds, without performing any meaningful share of the \(1.25 \times 10^9\) pairwise comparisons. Had it come back at 20% you would have stopped and gone to read the scraper, and that would have been a better use of the afternoon than any clustering.

One caveat to state whenever you report the number: it is a lower bound. At threshold=0.8, datasketch bands the 128 hashes so that a pair sitting exactly at 0.8 is examined with probability 0.40. “At least 151”, never “exactly 151”.

That the sentence is true and that it is not evidence. UMAP optimises a low-dimensional layout to preserve a \(k\)-nearest-neighbour graph, and squeezing a corpus into five dimensions manufactures density contrast whether or not the original space had any. Clusters appearing after UMAP is the expected outcome of running UMAP, not a discovery about your data.

What would turn it into a finding is a check UMAP never saw: do the groups predict something held out, do they survive a change of n_neighbors and random_state, do they survive on a random half of the corpus. Our own evidence points the other way — HDBSCAN found no region of the original E5 space that was clearly denser than its surroundings, and k-means found no boundaries either, so there is little density variation for UMAP to reveal; what appears after it was mostly made by it.

None of which forbids shipping the UMAP pipeline. Ship it on the strength of the downstream number, not on the strength of the picture.

Read it. Ours was bi ye fi tavsi çi ederi si ni li yi — ten tokenizer fragments, all manufactured by the same Unicode defect in the same documents, which is precisely why they co-occur almost perfectly and why NPMI scored them +0.5075, the highest per-topic coherence anywhere in the chapter. Coherence rewards co-occurrence, and a systematic bug is the most reliable co-occurrence in any corpus.

The damage was not confined to that one topic either. Dropping it takes LSA’s mean from +0.1340 to +0.0925 — from first place to last among the three c-TF-IDF rows. One topic in ten, of a kind a human rejects in two seconds, was carrying the ranking. Chang et al. (2009) showed in 2009 that an automated metric (likelihood) can diverge from human judgement; Hoyle et al. (2021) reported the same for coherence measures. Our case is an extreme instance.

When you do not yet know what the classes are. That is the core of it: a classifier needs a label set, and clustering is one of the few honest ways to discover what that set should be. “Run k-means, read 20 documents per cluster, draft the guidelines from what you read” is a real and cheap way to open an annotation project — Chapter 5 is the chapter that then tells you how to check the guidelines hold up.

Three other cases: you have far more documents than anyone will ever read and must choose which to read (Section 11.10); you must describe a corpus to somebody who will not read it either (Section 11.8); or you want to know what is actually in your data, including the parts nobody put there on purpose (Section 11.9).

And the converse, which matters just as much: if you already know the classes and can afford to label, label. Clustering is not a cheaper classifier and it will not become one.

11.13 Interview questions

On attribution — the same caution as Chapter 2. These are questions that recur across the two credible public sources, both free: Introduction to Machine Learning Interviews by Chip Huyen (Huyen 2021) and AIMLInterviews. Be wary of pages that list “the questions company X asks” without a source; attributing a question to a company takes a source you can check.

  1. How do you choose the number of clusters? The answer interviewers are listening for begins by refusing the premise. Internal indices disagree — ours put the optimum at 50, 2 and 50 on one representation and 2, 2 and 4 on another — and in two of three cases the “optimum” was a 1–7% wobble on a flat line. Say what you would do instead: cluster at three or four values of \(k\), read 20 documents per cluster, and keep the \(k\) whose clusters you can each describe in one line. Then mention the elbow method only to say you do not use it, and why — optimal inertia falls monotonically by construction, which guarantees nothing about a usable bend, and where you read one depends on your axis limits (Schubert 2023).

  2. k-means or HDBSCAN? k-means assumes spherical clusters of similar extent, no outliers, and a known \(k\); on text it is assumptions 2 and 3 that hurt, not the one everybody names. HDBSCAN drops all four and adds a noise class, which is the right shape for a corpus where most documents belong to nothing in particular. The catch is that it can decline to answer, and on this corpus it did: 53–100% noise depending on min_cluster_size, never more than three clusters at any setting, and even at its lowest noise rate (53–55% on LSA and MiniLM) it put nearly all of the rest in a single lump holding 45–47% of everything. A strong answer says “run both, because they disagree in informative ways” — two methods with different assumptions both reporting no structure is much stronger evidence than either alone.

  3. Why cosine and not Euclidean on text? Because raw length carries document length rather than topic, and you almost never want to cluster by length. The part worth knowing beyond that: on \(\ell_2\)-normalised vectors the two are monotonically related, \(d^2 = 2 - 2\cos\), so they induce the same nearest neighbours — but not the same k-means, because the arithmetic mean of unit vectors is not a unit vector, so from the second iteration the two procedures diverge. The practical rule is to normalise, then keep the metric consistent between the algorithm and every score you report. A silhouette computed with Euclidean distance on a clustering fitted with cosine is not measuring your clustering.

  4. Find the near-duplicates in a billion documents. Shingle, MinHash, band, bucket, verify — and then say what the approximation actually costs, which is where most answers stop short. LSH produces no false positives that survive exact verification, but it does produce false negatives: with 128 hashes in 9 bands of 13 at a 0.8 threshold, a pair at \(J = 0.9\) is examined with probability 0.93, one at \(J = 0.8\) with probability 0.40, and one at \(J = 0.7\) with probability 0.08. That is the deliberate design point, not a defect, and it is why duplicate counts are reported as lower bounds. Mention SimHash (Charikar 2002) as the alternative when you need to check new documents against a standing index rather than audit a fixed corpus.

  5. How do you evaluate a clustering when you have no labels? Start with the internal indices and their limits, then get to the real answer: evaluate the decision, not the partition. Sample and read; check that a human can name each cluster; and where a downstream use exists, measure it directly. Our own numbers are the argument — ARI could not separate three representations, all ≈ 0, while lift in the worst cluster ranked them 1.67× / 2.79× / 4.23× from the identical assignments. If you have any labelled subset at all, however small, it buys you more than every internal index combined.

  6. LDA, or something newer? State the assumption that decides it: LDA is a bag-of-words mixture model that needs enough words per document to estimate a mixture from. On our 19-word median reviews it was 133× slower than NMF and less coherent (+0.0737 against +0.1183). For short text, NMF on tf-idf is the better classical default, and the modern default is cluster-then-describe — embed, cluster, and label with c-TF-IDF (Grootendorst 2022), which costs nothing once the clustering exists. The trade to name out loud: c-TF-IDF inherits all of the embedding’s semantics and all of the clustering’s mistakes, and it is a labelling procedure rather than a topic model. LDA is still the right answer when documents are long and you genuinely need a per-document mixture rather than an assignment.

11.14 The 2026 toolbox

Everything in this chapter ran on one laptop with the versions below. Pinning versions in a book is risky, because they date quickly, but not pinning them is worse — the numbers here are only reproducible against a stated stack.

The stack these numbers came from. Python 3.14.5, Apple Silicon
library version used what it is for here
scikit-learn 1.9.0 TfidfVectorizer, TruncatedSVD, KMeans, HDBSCAN, LatentDirichletAllocation, NMF, and every metric
sentence-transformers 5.7.0 loading and batching MiniLM and E5
torch 2.13.0 the MPS backend the embeddings ran on
numpy / scipy 2.5.2 / 1.18.0 dense and sparse linear algebra
pandas 3.0.5 corpus handling, Parquet round-trip
datasketch 2.0.0 MinHash and the LSH index for Section 11.3
umap-learn 0.5.12 the projection discussed in Section 11.7

Versions are half of reproducibility; hyperparameters are the other half, and this chapter under-reports them. Three gaps to close before you rerun any of this. KMeans is randomised through k-means++, so its random_state and n_init decide the partition — and n_init has defaulted to "auto" since scikit-learn 1.4, which means the default itself is version-dependent. HDBSCAN has min_samples, metric, cluster_selection_method and cluster_selection_epsilon beside the min_cluster_size we swept (Section 11.7). LatentDirichletAllocation has learning_method, max_iter and the two Dirichlet priors. Fix all of them explicitly in your own runs and print them beside the numbers — including the ones you did not change, because “we used the default” is only a statement if you say which version’s default.

Worth knowing about, not used above:

The wider ecosystem, versions as of writing
library current version when you would reach for it
bertopic 0.17.4 the whole embed → UMAP → HDBSCAN → c-TF-IDF pipeline as one object, with topic merging, hierarchies and LLM naming built in. The fastest way to a demo; read Section 11.7 before trusting the clusters
faiss-cpu 1.15.0 approximate nearest neighbours once brute-force neighbour search gets expensive — roughly past a hundred thousand documents (a dense \(n \times n\) float32 similarity matrix is already ~10 GB at this chapter’s 49,849 documents)
usearch 2.26.0 a lighter, newer alternative to FAISS with the same job
gensim 4.4.0 the classical topic-model toolkit; still the reference implementation for LDA variants and CoherenceModel
top2vec 1.0.36 joint document/word embeddings with automatic topic count; conceptually close to BERTopic and predates it
chromadb 1.5.9 when the vectors need to persist and be queried by an application rather than a script — the bridge to Chapter 20

Choosing, in one line each. Under ~100k documents, scikit-learn does everything in this chapter and you should write the twenty lines yourself so you can see what each step did. Over that, add FAISS or usearch for the neighbour search. Reach for BERTopic when you want the polished artefact rather than the understanding — and having read Section 11.9, you now know which of its defaults to distrust.

11.15 Lab: build a triage curve for a corpus you own

The deliverable is one sentence of the form “reading X% of the corpus finds Y% of the Z”, plus the curve that justifies it. That sentence is what makes clustering fundable, and it is worth far more than a silhouette score.

What you need

Any corpus of a few thousand short documents in a domain you understand — support tickets, survey free-text, issue titles, exam answers. It needs one binary property you care about (complaint / not, urgent / not, off-topic / not) that you can label on a sample, not on all of it. Labelling 300 documents is enough and is the whole point: the lab simulates having a small budget.

scikit-learn and sentence-transformers do everything. The E5 pass on 50k documents took 104 seconds on a laptop GPU (Apple Silicon, mps); on CPU expect roughly an order of magnitude more, so budget a few minutes for 5k documents and start it before you read the rest of this section.

Step 1 — deduplicate first, and count what you removed

Run MinHash + LSH at \(J \geq 0.8\) before anything else, exactly as in Section 11.3. Report the number of groups and the largest group. If more than about 5% of your corpus is near-duplicate, stop and find out why — you have probably discovered a data-collection bug, and that is already a result worth reporting.

Step 2 — embed twice, deliberately

Build both a tf-idf → SVD(256) representation and a sentence-embedding one. Two representations is the minimum that lets you say anything comparative, and the comparison is the interesting part. Before clustering, compute the random-pair background: sample 2,000 documents, take all pairwise cosines, and record the mean and standard deviation for each space. You will need these to interpret every similarity you look at afterwards, and computing them takes four lines.

Step 3 — sweep \(k\), and expect to be disappointed

Run k-means at \(k \in \{2, 5, 10, 20, 50\}\) on both representations. Record silhouette (on a fixed sample if the corpus is large), the size of the largest cluster, and the fit time. Plot silhouette against \(k\).

If your curve is flat and low, you have reproduced our result and you should not conclude that you did it wrong. Note the largest-cluster column: a “clustering” whose biggest group holds 60% of the corpus is one lump and a scattering, whatever \(k\) you asked for.

Step 4 — label 300 documents, stratified by cluster

This is the step people skip. At your chosen \(k\), sample 30 documents from each of 10 clusters rather than 300 at random, and label your binary property by hand. Stratifying is what makes the next step possible at this budget: a random sample of 300 would put only a handful of documents in your rarest cluster and give you a per-cluster rate you cannot trust.

Write down the per-cluster positive rate and a 95% interval for each. At \(n=30\) those intervals are wide — roughly \(\pm 17\) points near 50% — so treat them as “is this cluster different from the corpus at all?” rather than as point estimates.

Step 5 — the curve, and the sentence

Sort the clusters by their measured rate, worst first. Walk down the list accumulating the share of the corpus read against the share of your property found, using the cluster sizes you know exactly and the rates you estimated. Plot it against the diagonal, as in Section 11.10.

Then write the sentence. If your curve lies on the diagonal, the honest sentence is “clustering does not help triage this property in this corpus” — which is a finding, cost you an afternoon, and has saved you from building a pipeline on it.

Going further

  • Rerun step 5 with the other representation. Our LSA and E5 differed by 2.5× in lift while being indistinguishable under ARI. Yours may too, and if so you have just chosen your embedding model on evidence.
  • Run the Unicode check from Section 11.9 on your own text, whatever language it is in: assert that lowercasing then tokenising is idempotent, that İSTANBUL lowercases to istanbul and IŞIK to ışık, and count the vocabulary types that vanish when you normalise properly.
  • Name your clusters with an LLM using the recipe in Section 11.11, then check every label against 20 documents you sampled yourself. Count how many labels survive. That ratio is your calibration for trusting the next batch.

11.16 Exercises

  1. The metric that was measuring nothing. In Section 11.5 the best adjusted Rand index anywhere in the sweep was 0.0083, and in Section 11.10 the same clusterings separated cleanly at 1.67×, 2.79× and 4.23×. Both numbers are correct. Explain, in terms of what ARI counts, how a partition can carry that much decision-relevant signal and still score zero. Then construct a small worked example — ten documents, two labels, two clusters — where ARI is exactly 0 and the lift in one cluster is 2×.

  2. A background you have not computed. A colleague reports that two documents in their corpus have a cosine similarity of 0.91 under E5 and concludes they are near-duplicates. Using the numbers in Section 11.2, say what is wrong with the inference, what single quantity they should compute before making it, and what value of that quantity would make their conclusion reasonable.

  3. The tokenizer test you do not have. Section 11.9 found a defect that survives exact deduplication and both NFC and NFKC normalisation. Chapter 4 wrote tr_lower so that its own code would not create it, but could not undo the marks already in the text it was given. (a) Explain why a classifier trained and tested on the same defective pipeline shows little or no visible accuracy loss. (b) Name the deployment change that would suddenly make it visible. (c) Write the three-line property test you would add to a CI suite to catch this class of bug in a language you do not speak — noting that assert tokenize(s.upper()) == tokenize(s) is the wrong answer, and saying why.

  4. Density, honestly. HDBSCAN called 97% of the corpus noise on LSA and 99.5% on E5. A teammate proposes running UMAP to 5 dimensions first, “because then it finds clusters”. (a) Explain what UMAP changes about the input that makes clusters appear. (b) Design an experiment that would distinguish “UMAP revealed structure that was there” from “UMAP created structure that was not”. (c) Say which result would make you willing to ship the UMAP pipeline anyway.

  5. The coherence trap, in your own data. Take the highest-coherence topic from any topic model you have run and read 20 documents that scored highest on it. If the topic is real, write the one-line description a colleague could use to sort new documents into it. If it is not, identify what the model actually latched onto. Report which happened — and note that in this chapter the highest-coherence topic in the entire run was the second case.

  6. The claim in a footnote that we did not measure. The footnote on distances in Section 11.2 says Euclidean k-means on \(\ell_2\)-normalised vectors and spherical k-means “usually land in similar places on text”, and admits that is folklore. Settle it. Write spherical k-means — Lloyd’s algorithm with the centroids re-normalised to unit length after every update — run both at \(k=10\) on the same vectors, and report the ARI between the two partitions for each representation. Then check whether the worst-cluster lift in Section 11.10 moves. Say which of the two results would make you change the footnote, and how.

  7. Choosing \(k\) without an index. You have 40,000 support tickets and a support team of six people who will each own one category. Argue for a value of \(k\) using no internal validation index at all. State what would make you revise it, and explain why this reasoning is better founded than an elbow plot rather than merely more convenient.

  8. Turn the triage result into a policy you could deploy. Section 11.10 ranks the ten clusters by a negative rate computed from every gold label, then scores recall against those same labels. Redo it honestly: hold out a random test half, label a development sample of 300 documents from the other half, rank the clusters by the negative rate in that sample only, and then read the triage curve on the test half. Report how much of the 56.0%-at-13.3% result survives, and how the answer moves as you shrink the development sample to 100 and grow it to 1,000.

11.17 Where to go deeper

Before any paper: run your clustering twice with different seeds and compare the assignments. If they disagree, every interpretation you were about to write is about the seed.

Beyond the papers
resource what it is
BERTopic documentation unusually good docs — the “best practices” page is a short course in what goes wrong
UMAP documentation: “Using UMAP for Clustering” states the pitfalls of clustering on UMAP output plainly (density is not fully preserved, false tears can appear in clusters), which is the most common failure in this chapter’s territory
scikit-learn clustering guide the algorithms side by side, with the assumptions each one makes stated plainly
hdbscan read the noise-handling section; it explains why so much of your corpus comes back unlabelled
Sentence Transformers the embeddings everything here is built on, with a clear guide to picking one
Visualizing High-Dimensional Space — Google four minutes on what a projection does and does not preserve; watch it before trusting any UMAP plot
The primary sources
topic source
the topic model everyone starts with Blei et al. (2003)
and what humans actually see in its output Chang et al. (2009)
embeddings plus clustering instead Grootendorst (2022)
density clustering that can say “noise” Campello et al. (2013); McInnes and Healy (2017)
the projection you are probably over-reading McInnes et al. (2018)
choosing k, and why the indices disagree Rousseeuw (1987); Schubert (2023)
comparing partitions properly Hubert and Arabie (1985); Rosenberg and Hirschberg (2007)
coherence, and its limits Bouma (2009)
near-duplicate detection at scale Broder (1997); Charikar (2002); Manku et al. (2007)
why deduplication matters upstream Lee et al. (2022); Penedo et al. (2024)
cosine similarity, read too literally Steck et al. (2024)

11.18 What to remember

  • Clustering is what you do when you cannot read the corpus and do not have labels. It is not a weaker form of classification; it answers a different question, and the metrics that judge classifiers judge it badly.
  • Similarity is a property of the geometry, not of the documents. A cosine of 0.98 means nothing until you know what two random documents score. In our four spaces the random-pair mean ranged from 0.018 to 0.855, so the same number means “near-duplicate” in one space and “unremarkable” in another. Always compute the background.
  • Deduplicate before you do anything else. It is cheap, it is the highest return per line of code in the chapter, and the count you get is a diagnostic of your collection pipeline. At \(J \geq 0.8\) we removed 151 documents in 27 seconds without comparing all 1.25 billion pairs.
  • k-means makes four assumptions on your behalf — spherical clusters, similar extent, no outliers, and a known \(k\) — and on text corpora it is numbers 2 and 3 that hurt, not the one everybody worries about.
  • A flat silhouette curve is a finding. Ours never exceeded 0.1042 across 42 runs, and HDBSCAN independently called 53–100% of the same corpus noise depending on min_cluster_size, never returning more than three clusters at any setting — and even at its lowest noise rate (53–55% on LSA and MiniLM) it put the rest in one lump holding roughly 45% of the corpus. Two methods with different assumptions agreeing that there are no boundaries is stronger evidence than either alone.
  • Do not use the elbow method. A monotone curve is not a promise of a usable bend, where you read one depends on your axis limits, and Schubert (2023) sets out the case at length.
  • Short documents break LDA. On 19-word reviews it was 133× slower than NMF and less coherent. If you have inherited an LDA pipeline on short text, run NMF beside it before defending the incumbent.
  • Cluster-then-describe is the modern default. c-TF-IDF costs nothing once you have clusters, it inherits all of the embedding’s semantics, and it inherits all of the clustering’s mistakes.
  • Topic coherence can be maximised by garbage. Our highest-scoring topic in the whole chapter, at +0.5075, was ten tokenizer fragments. Removing it moved its method from first place to last. That an automated metric can diverge from human judgement was shown by Chang et al. (2009) for likelihood and by Hoyle et al. (2021) for coherence; ours is an extreme case.
  • Unsupervised methods find what is actually in your data, including the parts you did not put there. k-means assembled a cluster that was 94.7% affected by a Unicode defect against a 6.0% background, having been told nothing about Unicode. Chapter 4 knew about that defect because a Turkish speaker did; the clustering found it without one.
  • str.lower() is not Turkish-aware, and NFKC will not save you. "TAVSİYE".lower() tokenises to ['tavsi', 'ye']. Pin the cases you care about — assert tokenize("TAVSİYE") == tokenize("tavsiye") — rather than asserting a general round-trip. tokenize(s.upper()) == tokenize(s) looks tidier and fails on correct code, because Python’s str.upper() is not Turkish-aware either: it sends i to I instead of İ, so iyi comes back as ıyı no matter how good your lowercaser is.
  • Measure the decision, not the partition. ARI could not distinguish our three representations; the triage curve ranked them cleanly and in the expected order. Under an ordering chosen from the full set of gold labels, reading 13.3% of the corpus found 56.0% of its complaints — a 4.2× return on a fixed budget from a clustering that scored zero on every external index. A policy you can deploy still needs that ordering chosen on one sample and measured on another.
  • “The clustering failed” is almost always premature. Write down the decision it was supposed to support, measure that, and only then decide.

  1. If \(\lVert a \rVert = \lVert b \rVert = 1\) then \(d_{\text{euc}}(a,b)^2 = 2 - 2\cos(a,b)\), so ranking by one ranks by the other. Do not over-extend this. It licenses “the same nearest neighbours”, not “the same algorithm”: Lloyd’s k-means replaces each centre with the arithmetic mean of its members, and a mean of unit vectors is not itself a unit vector, so from the second iteration onward Euclidean k-means on normalised embeddings and spherical k-means are genuinely different procedures. They are usually reported to land in similar places on text, and we did not check it here — the honest status of that sentence is folklore, not measurement. Twenty lines of spherical k-means (re-normalise the centroids each iteration) scored against scikit-learn’s KMeans on the same vectors, compared by ARI at \(k=10\), would settle it for this corpus in an afternoon, and Section 11.16 asks you to. Every embedding in this chapter is \(\ell_2\)-normalised before clustering and every silhouette is computed with metric="cosine", so the assignment step agrees with the scoring step.↩︎