20 Newsgroups

18,846 posts, MiniLM-384d sentence embeddings, k=20 hierarchical topics.

text

medium

embeddings

hierarchical

If Digits was k-means’s home court — ten roughly-convex blobs, exactly the geometry k-means was born to carve — 20 Newsgroups is an away game. Sentence embeddings produce curved topic manifolds that share vocabulary at their borders: comp.sys.ibm.pc.hardware and comp.sys.mac.hardware bleed into each other; talk.politics.mideast and talk.religion.misc share a substantial amount of language. K-means has to slice straight Voronoi lines through those seams. DYF can follow the curve.

That’s the prediction. Let’s see whether it pans out.

Load 20 Newsgroups

Code

from sklearn.datasets import fetch_20newsgroups

data = fetch_20newsgroups(
    subset="all",
    remove=("headers", "footers", "quotes"),  # strip boilerplate so the model scores on content
)
print(f"{len(data.data):,} posts across {len(data.target_names)} classes")
print(f"Examples: {data.target_names[:4]} ...")

18,846 posts across 20 classes
Examples: ['alt.atheism', 'comp.graphics', 'comp.os.ms-windows.misc', 'comp.sys.ibm.pc.hardware'] ...

Embed with MiniLM-L6-v2 (384d)

Sentence embeddings, not TF-IDF. This is the standard “turn text into semantic vectors” move and it’s what downstream RAG / retrieval systems actually use. Cached to /tmp on first run so re-renders are cheap.

Code

import os
import numpy as np
import time

CACHE = "/tmp/twenty_ng_minilm.npz"

if os.path.exists(CACHE):
    z = np.load(CACHE)
    X, y = z["X"], z["y"]
    print(f"Cache hit: {X.shape[0]:,} × {X.shape[1]}d embeddings")
else:
    from sentence_transformers import SentenceTransformer
    model = SentenceTransformer("sentence-transformers/all-MiniLM-L6-v2")
    t0 = time.time()
    X = model.encode(data.data, show_progress_bar=False, batch_size=64)
    X = np.ascontiguousarray(X, dtype=np.float32)
    y = np.asarray(data.target)
    print(f"Embedded {X.shape[0]:,} posts in {time.time() - t0:.1f}s → {X.shape[1]}d")
    np.savez(CACHE, X=X, y=y)

Cache hit: 18,846 × 384d embeddings

Run DYF (parameter-free)

Same call as every other notebook in this gallery — no arguments tuned for text.

Code

import sys
sys.path.insert(0, ".")
from _gallery import run_dyf, run_kmeans, plot_single, metrics_table

result = run_dyf(X, y)

print(f"Recovered k: {result.recovered_k}  (true k = {result.true_k})")
print(f"AMI:         {result.ami:.3f}")
print(f"ARI:         {result.ari:.3f}")

Recovered k: 12  (true k = 20)
AMI:         0.499
ARI:         0.341

Oracle k-means baseline

Code

kmeans = run_kmeans(X, y)
print(f"k-means AMI={kmeans['ami']:.3f}, ARI={kmeans['ari']:.3f} (told k={result.true_k})")

k-means AMI=0.505, ARI=0.345 (told k=20)

What about HDBSCAN?

Skipped here. On 18,846 × 384d, HDBSCAN’s defaults take ~2.5 minutes of wall clock and then flag 84% of points as noise — it’s scoring AMI on only the 16% of posts it was willing to cluster. The comparison becomes unfair in the other direction (HDBSCAN is allowed to pick its battles), and the notebook render balloons by 2+ minutes for a mostly uninformative number. The digits notebook keeps HDBSCAN because the noise fraction is small there; here it’s not a useful reference.

Figures

Three views of the same UMAP layout: ground-truth classes, DYF’s parameter-free partition, and k-means given the oracle k=20.

Code

plot_single(result.umap_2d, y, title=f"Ground truth (k={result.true_k})")

Figure 1: Ground truth — 20 newsgroup classes.

Code

plot_single(result.umap_2d, result.labels, title=f"DYF (recovered k={result.recovered_k})")

Figure 2: DYF — parameter-free, no k supplied.

Code

plot_single(result.umap_2d, kmeans["labels"], title=f"k-means (told k={result.true_k})")

Figure 3: K-means given the oracle k=20.

Metrics

Code

print(metrics_table(result, kmeans, None))

Method	Recovered k	AMI	ARI	% discarded	wall (s)
DYF (parameter-free)	12	0.499	0.341	0%	1.11
k-means (oracle k=20)	20	0.505	0.345	0%	0.20

Wall time: DYF 1.11 s (tree build + index write + Louvain) vs k-means 0.20 s (one k-means++ init at the oracle k) — DYF 5.6× slower here. The shared UMAP layout is not counted for either.

Twelve communities for twenty classes — which twenty?

DYF stopped at 12. That is well short of the flat label’s count, and it could mean two very different things: the community-detection stage under-resolved the leaf graph (as it does on Digits, a much smaller dataset), or DYF landed on a coarser real level of the newsgroup hierarchy. 20 Newsgroups has seven top-level buckets — alt, comp, misc, rec, sci, soc, talk — so the second reading is testable: score the same partition against the top-level label.

Code

from sklearn.metrics import adjusted_rand_score, normalized_mutual_info_score

top_names = sorted({n.split(".")[0] for n in data.target_names})
y_top = np.asarray([top_names.index(data.target_names[t].split(".")[0]) for t in y])

def score(lab):
    return normalized_mutual_info_score(y_top, lab), adjusted_rand_score(y_top, lab)

print(f"{len(top_names)} top-level groups: {top_names}\n")
print(f"{'partition':32s}   AMI    ARI   (vs top-level label)")
for name, lab in [(f"DYF raw (k={result.recovered_k})", result.labels),
                  ("k-means (told k=20)", kmeans["labels"])]:
    n_, a_ = score(lab)
    print(f"{name:32s}  {n_:.3f}  {a_:.3f}")

7 top-level groups: ['alt', 'comp', 'misc', 'rec', 'sci', 'soc', 'talk']

partition                          AMI    ARI   (vs top-level label)
DYF raw (k=12)                    0.450  0.313
k-means (told k=20)               0.426  0.214

Compare the two rows to the same methods scored against the 20-class label above. The answer is both readings at once. DYF’s twelve communities keep the top-level structure better than k-means’s twenty do — ARI 0.313 vs 0.214 against the seven buckets, AMI 0.450 vs 0.426 — and DYF’s ARI is close whether you judge it by buckets (0.313) or by the 20 classes (0.341), which is what a partition sitting between two levels of a hierarchy looks like. But AMI 0.45 against seven buckets is not a clean seven-way split either. The twelve communities are coarser than the leaves and finer than the branches, and they respect the branches about as well as anything here does.

Walking down the hierarchy

Whatever the reading, DYF’s 12 communities are the top of a partition hierarchy that can be collapsed further:

Code

from _gallery import merge_walk, merge_walk_table

walk = merge_walk(result, X, y, targets=[25, 20, 10, 7, 4])
print(merge_walk_table(walk, result))

Resolution	Actual k	AMI	ARI
Raw DYF	12	0.499	0.341
merge → 25	12	0.499	0.341
merge → 20	12	0.499	0.341
merge → 10	10	0.474	0.297
merge → 7	7	0.417	0.207
merge → 4	4	0.322	0.125

Targets above 12 are no-ops. merge → 7 is the interesting row: seven is the number of top-level newsgroup buckets. Collapsing to it costs 0.08 AMI and 0.13 ARI against the 20-class label — a real loss, but a smaller one than k-means’s twenty clusters suffer when judged at the bucket level (ARI 0.345 → 0.214 in the cell above). The coarse structure is in the tree; it is just not the level DYF stopped at.

How DYF and k-means disagree — and why

Compare this to the Digits notebook:

Dataset	k-means AMI	DYF AMI	Gap
Digits	0.773	0.668	0.105
20 Newsgroups	0.505	0.499	0.006

The gap all but closed. On text, oracle-tuned k-means is under a hundredth of AMI ahead of DYF-with-no-knobs, at 12 clusters to its 20. Two things changed between the notebooks:

1. The manifold started to bend. Sentence embeddings for comp.sys.ibm.pc.hardware and comp.sys.mac.hardware overlap — they share vocabulary (“driver”, “boot”, “RAM”), writing style, question types. In UMAP those classes don’t sit as disjoint blobs; they bleed into each other along a curved seam. K-means has to plant a Voronoi boundary somewhere in that seam, and wherever it plants it, it misclassifies the items near the line. DYF’s density-based cut can follow the seam instead of cutting straight across it.

2. The tree is bigger. Digits hands community detection ~190 leaf centroids and gets under-split to 8 for 10. Here the tree has several times as many leaves and DYF recovers 12 for 20 — still coarse, but the label it is coarse against is itself a two-level hierarchy, which is why the top-level cell above exists. On MNIST (70,000 points, thousands of leaves) the same code recovers 12 for 10. Leaf count, not sample count, is the axis to watch.

The home-court / away-game framing, continued

K-means is a superb algorithm when the problem matches its inductive bias: “minimize within-cluster Euclidean variance, and I’ll tell you how many clusters there are.” Digits satisfies both conditions perfectly — ten convex blobs, k handed over. Text embeddings break both conditions at once: the geometry isn’t convex, and the real number of semantic communities isn’t even well-defined (there are 7 top-level topic groups, 20 flat labels, and a debatable number of sub-topics).

On its home court k-means wins by 0.105 AMI. On the away game it wins by 0.006. The remaining notebooks — Olivetti Faces (40 identities, 10 examples each, very non-convex in pixel space) and CMU MoCap (continuous motion manifolds, no single right k) — push both methods into regimes where neither does well, for different reasons.

Pros and cons recap

	DYF (parameter-free)	K-means (oracle k=20)
Needs `k`?	No.	Yes — given 20 upfront.
Behavior on curved manifolds	Follows density; can trace seams.	Cuts straight Voronoi lines across them.
Behavior when true structure is hierarchical	Stops at one level of it (12 here); the merge walk gives the coarser ones.	Forced to a flat 20-partition; can’t express hierarchy.
Behavior when embedding noise is high	Tree leaves absorb some noise before Louvain merges.	Sensitive — outliers pull centroids.
Tree output	Yes — can re-cut at coarser resolution post-hoc.	No — flat at exactly `k`.

What to take away

DYF comes within 0.01 AMI of oracle k-means on text, without k and with 12 clusters to its 20.
The recovered 12 is coarse against the 20-class label, and half-right against the 7-bucket one. It keeps the top-level structure better than oracle k-means’s twenty clusters (ARI 0.31 vs 0.21) without being a clean seven-way split. Read the two scores together; either alone tells a tidier, wrong story.
Embedding dominates the clock. Encoding 18,846 posts takes tens of seconds; either clusterer then finishes in about a second (wall (s) above), with DYF the slower of the two. On a real corpus the embedding step is the cost to plan around.
HDBSCAN doesn’t scale here. 144 seconds and 84% discarded is a dealbreaker at 18K+ documents, which is small by real-world RAG standards.
Parameter-free is getting cheaper to justify. On digits the oracle gave k-means a 0.105 AMI edge; here it bought 0.006. The cost of not knowing k drops as the geometry gets harder — which is the regime you’re in whenever you don’t already know what’s in your corpus.
Earlier versions of this page reported 23–34 communities and read them as sub-topic hierarchy. That count came from a single-level Louvain in dyf-rs before 0.12.0 that could not merge communities (dyf KNOWN_ISSUES.md, issue 10); the numbers here are from the corrected optimiser.

--- title: "20 Newsgroups" subtitle: "18,846 posts, MiniLM-384d sentence embeddings, k=20 hierarchical topics." order: 4 image: twenty-newsgroups_files/figure-html/fig-dyf-output-1.png categories: [text, medium, embeddings, hierarchical] true-k: 20 format: html: code-fold: show code-tools: true execute: warning: false message: false --- If Digits was k-means's home court — ten roughly-convex blobs, exactly the geometry k-means was born to carve — 20 Newsgroups is an away game. Sentence embeddings produce *curved* topic manifolds that share vocabulary at their borders: `comp.sys.ibm.pc.hardware` and `comp.sys.mac.hardware` bleed into each other; `talk.politics.mideast` and `talk.religion.misc` share a substantial amount of language. K-means has to slice straight Voronoi lines through those seams. DYF can follow the curve. That's the prediction. Let's see whether it pans out. ## Load 20 Newsgroups ```{python} #| label: load from sklearn.datasets import fetch_20newsgroups data = fetch_20newsgroups( subset="all", remove=("headers", "footers", "quotes"), # strip boilerplate so the model scores on content ) print(f"{len(data.data):,} posts across {len(data.target_names)} classes") print(f"Examples: {data.target_names[:4]} ...") ``` ## Embed with MiniLM-L6-v2 (384d) Sentence embeddings, not TF-IDF. This is the standard "turn text into semantic vectors" move and it's what downstream RAG / retrieval systems actually use. Cached to `/tmp` on first run so re-renders are cheap. ```{python} #| label: embed import os import numpy as np import time CACHE = "/tmp/twenty_ng_minilm.npz" if os.path.exists(CACHE): z = np.load(CACHE) X, y = z["X"], z["y"] print(f"Cache hit: {X.shape[0]:,} × {X.shape[1]}d embeddings") else: from sentence_transformers import SentenceTransformer model = SentenceTransformer("sentence-transformers/all-MiniLM-L6-v2") t0 = time.time() X = model.encode(data.data, show_progress_bar=False, batch_size=64) X = np.ascontiguousarray(X, dtype=np.float32) y = np.asarray(data.target) print(f"Embedded {X.shape[0]:,} posts in {time.time() - t0:.1f}s → {X.shape[1]}d") np.savez(CACHE, X=X, y=y) ``` ## Run DYF (parameter-free) Same call as every other notebook in this gallery — no arguments tuned for text. ```{python} #| label: run-dyf import sys sys.path.insert(0, ".") from _gallery import run_dyf, run_kmeans, plot_single, metrics_table result = run_dyf(X, y) print(f"Recovered k: {result.recovered_k} (true k = {result.true_k})") print(f"AMI: {result.ami:.3f}") print(f"ARI: {result.ari:.3f}") ``` ## Oracle k-means baseline ```{python} #| label: kmeans kmeans = run_kmeans(X, y) print(f"k-means AMI={kmeans['ami']:.3f}, ARI={kmeans['ari']:.3f} (told k={result.true_k})") ``` ## What about HDBSCAN? Skipped here. On 18,846 × 384d, HDBSCAN's defaults take ~2.5 minutes of wall clock and then flag **84% of points as noise** — it's scoring AMI on only the 16% of posts it was willing to cluster. The comparison becomes unfair in the other direction (HDBSCAN is allowed to pick its battles), and the notebook render balloons by 2+ minutes for a mostly uninformative number. The digits notebook keeps HDBSCAN because the noise fraction is small there; here it's not a useful reference. ## Figures Three views of the same UMAP layout: ground-truth classes, DYF's parameter-free partition, and k-means given the oracle `k=20`. ::: {.gallery-fluid} ```{python} #| label: fig-truth #| fig-cap: "Ground truth — 20 newsgroup classes." plot_single(result.umap_2d, y, title=f"Ground truth (k={result.true_k})") ``` ```{python} #| label: fig-dyf #| fig-cap: "DYF — parameter-free, no k supplied." plot_single(result.umap_2d, result.labels, title=f"DYF (recovered k={result.recovered_k})") ``` ```{python} #| label: fig-kmeans #| fig-cap: "K-means given the oracle k=20." plot_single(result.umap_2d, kmeans["labels"], title=f"k-means (told k={result.true_k})") ``` ::: ## Metrics ```{python} #| label: metrics #| output: asis print(metrics_table(result, kmeans, None)) ``` ## Twelve communities for twenty classes — which twenty? DYF stopped at 12. That is well short of the flat label's count, and it could mean two very different things: the community-detection stage under-resolved the leaf graph (as it does on [Digits](digits.qmd), a much smaller dataset), or DYF landed on a *coarser real level* of the newsgroup hierarchy. 20 Newsgroups has seven top-level buckets — `alt`, `comp`, `misc`, `rec`, `sci`, `soc`, `talk` — so the second reading is testable: score the same partition against the top-level label. ```{python} #| label: top-level from sklearn.metrics import adjusted_rand_score, normalized_mutual_info_score top_names = sorted({n.split(".")[0] for n in data.target_names}) y_top = np.asarray([top_names.index(data.target_names[t].split(".")[0]) for t in y]) def score(lab): return normalized_mutual_info_score(y_top, lab), adjusted_rand_score(y_top, lab) print(f"{len(top_names)} top-level groups: {top_names}\n") print(f"{'partition':32s} AMI ARI (vs top-level label)") for name, lab in [(f"DYF raw (k={result.recovered_k})", result.labels), ("k-means (told k=20)", kmeans["labels"])]: n_, a_ = score(lab) print(f"{name:32s} {n_:.3f} {a_:.3f}") ``` Compare the two rows to the same methods scored against the 20-class label above. The answer is *both readings at once*. DYF's twelve communities keep the top-level structure better than k-means's twenty do — ARI 0.313 vs 0.214 against the seven buckets, AMI 0.450 vs 0.426 — and DYF's ARI is close whether you judge it by buckets (0.313) or by the 20 classes (0.341), which is what a partition sitting between two levels of a hierarchy looks like. But AMI 0.45 against seven buckets is not a clean seven-way split either. The twelve communities are coarser than the leaves and finer than the branches, and they respect the branches about as well as anything here does. ## Walking down the hierarchy Whatever the reading, DYF's 12 communities are the top of a partition hierarchy that can be collapsed further: ```{python} #| label: merge-walk #| output: asis from _gallery import merge_walk, merge_walk_table walk = merge_walk(result, X, y, targets=[25, 20, 10, 7, 4]) print(merge_walk_table(walk, result)) ``` Targets above 12 are no-ops. `merge → 7` is the interesting row: seven is the number of top-level newsgroup buckets. Collapsing to it costs 0.08 AMI and 0.13 ARI against the 20-class label — a real loss, but a smaller one than k-means's twenty clusters suffer when judged at the bucket level (ARI 0.345 → 0.214 in the cell above). The coarse structure is in the tree; it is just not the level DYF stopped at. ## How DYF and k-means disagree — and why Compare this to the Digits notebook: | Dataset | k-means AMI | DYF AMI | Gap | |----------|------------:|--------:|------:| | Digits | 0.773 | 0.668 | 0.105 | | **20 Newsgroups** | **0.505** | **0.499** | **0.006** | **The gap all but closed.** On text, oracle-tuned k-means is under a hundredth of AMI ahead of DYF-with-no-knobs, at 12 clusters to its 20. Two things changed between the notebooks: **1. The manifold started to bend.** Sentence embeddings for `comp.sys.ibm.pc.hardware` and `comp.sys.mac.hardware` overlap — they share vocabulary ("driver", "boot", "RAM"), writing style, question types. In UMAP those classes don't sit as disjoint blobs; they bleed into each other along a curved seam. K-means has to plant a Voronoi boundary *somewhere* in that seam, and wherever it plants it, it misclassifies the items near the line. DYF's density-based cut can follow the seam instead of cutting straight across it. **2. The tree is bigger.** Digits hands community detection ~190 leaf centroids and gets under-split to 8 for 10. Here the tree has several times as many leaves and DYF recovers 12 for 20 — still coarse, but the label it is coarse *against* is itself a two-level hierarchy, which is why the top-level cell above exists. On [MNIST](mnist.qmd) (70,000 points, thousands of leaves) the same code recovers 12 for 10. Leaf count, not sample count, is the axis to watch. ### The home-court / away-game framing, continued K-means is a superb algorithm when the problem matches its inductive bias: *"minimize within-cluster Euclidean variance, and I'll tell you how many clusters there are."* Digits satisfies both conditions perfectly — ten convex blobs, k handed over. Text embeddings break both conditions at once: the geometry isn't convex, and the real number of semantic communities isn't even well-defined (there are 7 top-level topic groups, 20 flat labels, and a debatable number of sub-topics). On its home court k-means wins by 0.105 AMI. On the away game it wins by 0.006. The remaining notebooks — Olivetti Faces (40 identities, 10 examples each, *very* non-convex in pixel space) and CMU MoCap (continuous motion manifolds, no single right `k`) — push both methods into regimes where neither does well, for different reasons. ### Pros and cons recap | | **DYF (parameter-free)** | **K-means (oracle k=20)** | |----------------------------|----------------------------------------------------------------------|---------------------------------------------------------| | Needs `k`? | No. | Yes — given 20 upfront. | | Behavior on curved manifolds | Follows density; can trace seams. | Cuts straight Voronoi lines across them. | | Behavior when true structure is hierarchical | Stops at one level of it (12 here); the merge walk gives the coarser ones. | Forced to a flat 20-partition; can't express hierarchy. | | Behavior when embedding noise is high | Tree leaves absorb some noise before Louvain merges. | Sensitive — outliers pull centroids. | | Tree output | Yes — can re-cut at coarser resolution post-hoc. | No — flat at exactly `k`. | ## What to take away - **DYF comes within 0.01 AMI of oracle k-means on text**, without `k` and with 12 clusters to its 20. - **The recovered 12 is coarse against the 20-class label, and half-right against the 7-bucket one.** It keeps the top-level structure better than oracle k-means's twenty clusters (ARI 0.31 vs 0.21) without being a clean seven-way split. Read the two scores together; either alone tells a tidier, wrong story. - **Embedding dominates the clock.** Encoding 18,846 posts takes tens of seconds; either clusterer then finishes in about a second (`wall (s)` above), with DYF the slower of the two. On a real corpus the embedding step is the cost to plan around. - **HDBSCAN doesn't scale here.** 144 seconds and 84% discarded is a dealbreaker at 18K+ documents, which is small by real-world RAG standards. - **Parameter-free is getting cheaper to justify.** On digits the oracle gave k-means a 0.105 AMI edge; here it bought 0.006. The cost of not knowing `k` drops as the geometry gets harder — which is the regime you're in whenever you don't already know what's in your corpus. - **Earlier versions of this page reported 23–34 communities** and read them as sub-topic hierarchy. That count came from a single-level Louvain in `dyf-rs` before 0.12.0 that could not merge communities (dyf `KNOWN_ISSUES.md`, issue 10); the numbers here are from the corrected optimiser.