betula-cluster 0.1.0

Fast, numerically stable BETULA clustering with a Rust core

betula-cluster

Fast, memory-bounded clustering for large tabular & embedding data. A numerically stable BETULA CF-tree with a full set of clustering heads — k-means · GMM (diagonal & full) · Ward · HDBSCAN · Mapper — plus streaming partial_fit and a scikit-learn API. From-scratch Rust core, PyO3 bindings, no LAPACK, no SciPy at runtime.

pip install betula-cluster

At a glance — honest benchmarks

Measured against scikit-learn on StandardScaler-normalized data, each method in its own subprocess with peak RSS sampled from /proc/self/statm. Full methodology, every metric, and all tables (wins and losses) live in bench/RESULTS.md.

• 🎯 Quality at parity. betula's k-means / GMM / Ward land within ≈0.01 ARI of their scikit-learn counterparts; full-covariance GMM recovers anisotropic clusters just as well (0.90 vs 0.90); HDBSCAN-on-CF nails non-convex moons & circles (ARI 1.00).
• ⚡ 15–40× faster at N = 1 000 000. betula-kmeans labels a million points in 0.20 s vs scikit-learn KMeans 3.3 s (17×), Birch 8.0 s (40×), GaussianMixture 5.5 s (27×).
• 🪶 Bounded memory. Streaming 10 M points peaks at ~57 MB — flat in N — while an in-core KMeans must hold the array and peaks at ~5 GB (≈88× less, and the gap grows without limit).
• 🌍 Real data, not just blobs. Matches scikit-learn on digits (k-means 0.53 vs 0.47) and clusters full covtype (581 k rows) ~7× faster at better ARI; in very high dimensions (MNIST, 784-D) normalize=True beats scikit-learn (k-means 0.44 vs 0.32) — full table, and the honest trade-offs, in bench/RESULTS.md.

Phase-3 clusters only the ~2 000 leaf microclusters, not the raw points, so every head finishes 1 M points in under ⅓ s.	The CF-tree is capped by max_leaves, so streaming memory stays flat — it clusters data larger than RAM.

Why

Clustering libraries tend to either not scale (full GMM/HDBSCAN on raw points), lose precision (classic BIRCH computes variance as SS − ‖LS‖²/n, which catastrophically cancels far from the origin), or blow up in memory (BIRCH-family subcluster explosion in high dimensions). betula-cluster addresses all three:

• Numerically stable — clustering features (n, μ, S) via Welford / Chan updates; the covariance is PSD by construction. Classic BIRCH loses all digits near coordinate 1e7; betula does not.
• Memory-bounded by design — the CF-tree caps its leaves (max_leaves) and rebuilds, so it never explodes; streaming memory is flat in N and clusters data larger than RAM.
• Complete — one stable engine spanning k-means / GMM (diag & full) / Ward / HDBSCAN-style / Mapper, with streaming partial_fit, a scikit-learn API, and dataset-structure inspection.

The math (stable CF, the expected-log GMM E-step, distance derivations, relation to BIRCH/BETULA) is written up — verified symbolically and numerically — in docs/MATH.md.

Quick start

import numpy as np
import betula_cluster

X = np.random.default_rng(0).normal(size=(100_000, 10))

labels = betula_cluster.fit_predict(X, n_clusters=10, method="kmeans")
labels = betula_cluster.fit_predict(X, n_clusters=0, feature="full", method="gmm-full")  # auto-k via BIC
labels = betula_cluster.fit_predict(X, method="hdbscan", min_cluster_size=25)             # -1 == noise

Streaming / out-of-core — feed chunks, finalize, predict; memory stays bounded by max_leaves:

est = betula_cluster.Betula(method="gmm", memory_budget_mb=512)
for chunk in stream_of_arrays:        # each chunk is a 2-D float32/float64 array
    est.partial_fit(chunk)
est.partial_fit()                     # finalize the global clustering over everything seen
labels = est.predict(X_query)

Constraints (COP-KMeans), mixed numeric+categorical (KPrototypes), streaming density (DenStream / DbStream), quantile sketches, scipy.sparse input, soft assignment / coresets / diagnostics, the Rust API, and the CLI — all in the usage guide.

Capabilities

• Clustering heads — weighted k-means, GMM (diagonal & full covariance, BIC auto-k), exact Ward HAC, HDBSCAN-style density over CF microclusters, and a Mapper topological skeleton.
• Streaming — partial_fit at bounded memory; DenStream & DbStream for evolving streams; mergeable KllSketch / DdSketch quantiles.
• Data types — dense f32/f64, scipy.sparse (never densified), O(nnz) sparse-native, and mixed numeric+categorical (k-prototypes).
• Beyond labels — predict_proba, coresets, diagnostics, outliers / near-duplicates / representatives, drift snapshots, COP-KMeans constraints, and robust (Huber) insertion.
• Engineering — scikit-learn API (Pipeline / clone / GridSearchCV), typed abi3 wheel, save / load + pickle, a dependency-free CLI, and a reusable Rust core.

Full reference: docs/FEATURES.md.

Examples

Twelve executed, plotted notebooks — one per capability — live in examples/ (render on GitHub):

• Core — quickstart, embeddings & inspection, streaming & persistence, method comparison, Mapper topology.
• Streaming density — DenStream & DbStream.
• Mixed data — KPrototypes.
• Sketches — KllSketch & DdSketch.
• Semi-supervised — must-link / cannot-link.
• Sparse / high-dim — scipy.sparse + fit_predict_sparse.
• Soft assignment & coresets — predict_proba, coresets, diagnostics.
• Production ops — drift, active learning, robust, memory budgets.

And three end-to-end use cases (each scored against ground truth):

• 🧹 Embedding dedup — collapse a repost-heavy corpus to representatives.
• 🚨 Log anomaly detection — batch outlier scoring + streaming DbStream flags.
• 👥 Customer segmentation — mixed RFM + categorical personas with KPrototypes.
• 🧠 RAG corpus curation — junk removal, topic coherence, and topic-leakage detection via Mapper.
• 🔢 Real-data clustering — handwritten digits, ARI parity + centroid/exemplar inspection.

Documentation

• Usage guide — runnable snippets for every interface.
• Features — full capability reference + crate architecture.
• Math — stable CF, GMM E-step, distance derivations, relation to BIRCH/BETULA.
• Benchmarks — methodology, every metric, all tables, honest wins & losses.
• Design — internal design, invariants, and testing strategy.

Verified: 129 Rust unit/integration tests + a 123-case Python suite at 100% wrapper coverage (Rust ≥95%, CI-enforced), clippy -D warnings + fmt clean across all feature sets, on Python 3.11–3.14 (single abi3 wheel).

Known limitations

Honest scope — inherent to a CF-compression + streaming design, not bugs:

1. Insertion-order sensitive — like every BIRCH-family streaming method, the labels depend on the order points arrive (the parallel build differs from the serial one, as a different order would).
2. threshold / max_leaves are real hyperparameters — they trade compression against resolution; n_rebuilds_ / threshold_ expose thrashing / over-coarsening.
3. CF-level heads approximate raw-data clustering — Phase-3 runs on the M ≪ N microclusters; quality degrades when clusters overlap at the compression scale. Mitigation: more leaves.
4. HDBSCAN-on-CF ≠ raw-point HDBSCAN — mass-aware HDBSCAN over microclusters: fast and close, but an approximation (weaker on overlapping blobs; see the benchmarks).
5. The expected-log GMM optimizes a CF-level objective, not pointwise EM (a deliberate, measured choice for coarse CFs).
6. Frequent-Directions is an approximate low-rank covariance (exact only up to its rank ℓ).

License

MIT.