forest-clustering

Tree-based and random-partition clustering for mixed-type tabular data.

forest-clustering provides sklearn-style estimators that convert tabular rows into tree or partition embeddings, compute sample-to-sample similarities, and then run a downstream clustering algorithm. It is designed for practical unsupervised learning on mixed numerical/categorical data where Euclidean distance is often a poor default.

What to expect — and what not to expect

This package is a clustering toolkit and representation family, not a universally superior clustering algorithm. Its main practical advantage is the ability to consume mixed numerical and categorical tables without requiring users to design an encoding and scaling pipeline first. That convenience does not guarantee better clusters than a well-preprocessed sklearn baseline.

The repository examples currently support the following, more limited conclusions:

• ForestClusterer with a fixed cluster count and its default KMeans downstream step can be a strong mixed-type baseline. On synthetic data generated from well-separated Gaussian centres it performs well, but a properly scaled KMeans or Ward clustering can perform better because those methods match the data-generating geometry directly.
• Quantile-based cuts can reduce sensitivity to extreme values, but robustness is dataset-, seed-, contamination-level-, and downstream-clusterer-dependent. Refitting after adding outliers changes the sampled partitions and may change the final clusters. Treat robustness as something to measure on the same uncontaminated rows across repeated runs, not as a guaranteed property.
• Louvain and Leiden discover communities in a k-nearest-neighbour graph; they do not infer a uniquely correct number of clusters and they do not accept a target cluster count. Sparse or disconnected graphs can produce dozens or hundreds of communities. n_neighbors and resolution require validation, and lowering resolution cannot merge disconnected graph components.
• Random-forest and ExtraTrees proximity estimators provide useful alternative representations, but they do not consistently outperform KMeans, Ward, or the random-partition estimator on internal metrics. The interpretable binary tree is useful when explicit rules matter, not because it is guaranteed to maximise clustering quality.
• AutoTreeClusterer selects the best candidate in the supplied search space according to an internal proxy. It cannot establish that the selected partition is meaningful, unique, or useful for a downstream decision.

Current notebook results illustrate these trade-offs: the centroid path is generally competitive on the mixed-type examples, while the graph and some tree-proximity paths can be materially worse than simple baselines. They should be treated as candidate models to evaluate, not automatic upgrades.

Minimum evaluation checklist

Before describing a result as good or using it in production:

1. Compare against at least KMeans on an imputed/scaled/one-hot representation; add Ward or another appropriate baseline when dataset size permits.
2. Compare like with like: use the same rows, the same target number of clusters when the algorithms support it, and the same noise-handling rule.
3. Evaluate multiple random seeds and report variability. A single favourable seed is not evidence of stability.
4. Report cluster sizes, noise share, stability under resampling or contamination, and at least one internal metric in a clearly stated feature space or distance metric.
5. Inspect cluster profiles for practical interpretability. Silhouette, Calinski-Harabasz, Davies-Bouldin, Gap, and Hopkins are diagnostics rather than proof of a true segmentation.
6. If an external label is used for ARI or NMI, do not include that label among the clustering features. Classification labels are often only a partial clustering reference.

For graph clustering, also inspect graph connectivity. The number of non-singleton connected components is a hard lower bound on the number of non-noise communities unless a separate cross-component merge step is introduced.

What is included

Estimator	Core idea	Best use case
ForestClusterer	Random feature partitions produce an integer embedding; Hamming similarity measures co-partitioning.	Fast mixed-type candidate and random-partition baseline; benchmark it against standard preprocessing.
UnsupervisedRandomForestClusterer	Breiman-style unsupervised random forest: real rows vs synthetic null rows, then same-leaf proximity.	Random-forest proximity candidate when interactions or a non-Euclidean representation are plausible.
ExtraTreesProximityClusterer	ExtraTrees version of the synthetic-null forest; more randomized splits and fast leaf proximity.	Highly randomized tree-proximity candidate; validate quality against simpler baselines.
UnsupervisedBinaryTreeClusterer	Greedy interpretable binary tree that recursively splits rows to reduce within-leaf variance.	Explainable cluster rules and small/medium tabular datasets.
AutoTreeClusterer	Tries several tree-based estimators, cluster counts, parameter grids and random restarts; selects the best by internal score/stability.	Practical autoparameter selection when you do not know the best algorithm or k.
ForestTransformer	Transformer-only wrapper around ForestClusterer.	sklearn pipelines and custom downstream models.

The package also includes weighted Hamming distances, graph helpers, adaptive bins, KDE-based cut points, permutation importance, clusterability checks, and significance utilities.

Autotuning in 0.6.x

The 0.6 release line adds AutoTreeClusterer, a sklearn-style meta-estimator for simple, practical autoparameter selection. It can search across algorithms, cluster counts, small algorithm-specific grids and random restarts. Version 0.6.1 fixes an important model-selection issue: internal silhouette scoring now uses leak-safe feature representations by default instead of distances that may be derived from the candidate final labels.

from forest_clustering import AutoTreeClusterer

model = AutoTreeClusterer(
    algorithms=("forest", "urf", "extratrees", "binary_tree"),
    k_range=range(2, 8),
    scoring="combined",          # leak-safe silhouette + stability
    scoring_space="auto",         # default; avoids label-derived distance leakage
    n_restarts=3,
    estimator_params={
        "forest": {"n_iterations": [100, 200], "n_bins": ["auto", 4]},
        "urf": {"n_estimators": [100]},
        "extratrees": {"n_estimators": [100]},
        "binary_tree": {"max_depth": [None, 6]},
    },
    add_missing_indicators=True,
    rare_category_min_count=5,
    coerce_numeric_strings=True,
    random_state=42,
)

labels = model.fit_predict(X)
print(model.best_algorithm_, model.best_n_clusters_, model.best_score_)
print(model.cv_results_.head())

Supported scoring modes are "silhouette", "calinski_harabasz", "davies_bouldin", "stability", and "combined". By default, scoring_space="auto" uses leak-safe feature-space scoring: weighted partition features for ForestClusterer, one-hot leaf features for URF/ExtraTrees, and the preprocessed feature matrix for UnsupervisedBinaryTreeClusterer. scoring_space="proximity" is available only as an explicit compatibility mode. The selected estimator is available as model.best_estimator_, and matrix APIs delegate to it: similarity_matrix(), pairwise_distance(), and transform(X).

Quality fixes in 0.5.1

The 0.5.1 release focuses on practical clustering quality and safer defaults:

• auto_tune_dbscan=False by default: DBSCAN parameters are no longer silently changed.
• cluster_input="auto" | "embedding" | "onehot" | "distance" | "similarity": explicit downstream input control.
• add_missing_indicators=True: append binary missingness indicators.
• rare_category_min_count / rare_category_min_freq: group rare and unseen categories into a stable rare bucket.
• coerce_numeric_strings=True: treat numeric object/string columns as numeric features.
• n_bins="auto": simple sample-size-aware bin selection.

from forest_clustering import ForestClusterer

model = ForestClusterer(
    n_bins="auto",
    n_clusters=3,
    add_missing_indicators=True,
    rare_category_min_count=5,
    coerce_numeric_strings=True,
    cluster_input="auto",
    random_state=42,
)
labels = model.fit_predict(X)

Installation

pip install forest-clustering

Python >=3.10 is required.

Quick start

import pandas as pd
from forest_clustering import ForestClusterer

X = pd.DataFrame({
    "age": [22, 38, 26, 35, 54, 2],
    "fare": [7.25, 71.28, 7.92, 53.10, 51.86, 21.08],
    "sex": ["male", "female", "female", "female", "male", "male"],
    "pclass": [3, 1, 3, 1, 1, 3],
})

model = ForestClusterer(
    n_iterations=200,
    n_bins=3,
    cut_strategy="quantile",
    random_state=42,
)

labels = model.fit_predict(X)
embedding = model.get_embedding()
distance = model.pairwise_distance()
similarity = model.similarity_matrix()

Tree-proximity clustering

Breiman-style unsupervised random forest

from forest_clustering import UnsupervisedRandomForestClusterer

urf = UnsupervisedRandomForestClusterer(
    n_estimators=300,
    n_clusters=4,
    synthetic="permute_marginals",
    random_state=42,
)

labels = urf.fit_predict(X)
proximity = urf.proximity_matrix()
leaf_ids = urf.transform(X)
leaf_onehot = urf.transform_onehot(X)

The estimator builds a synthetic null dataset, trains a random forest to separate observed rows from synthetic rows, and uses same-leaf co-occurrence as a proximity score.

ExtraTrees proximity clustering

from forest_clustering import ExtraTreesProximityClusterer

xt = ExtraTreesProximityClusterer(
    n_estimators=300,
    n_clusters=4,
    synthetic="uniform_box",
    random_state=42,
)

labels = xt.fit_predict(X)

This estimator uses the same synthetic-null idea as URF, but with ExtraTreesClassifier, producing more randomized split geometry.

Interpretable binary tree clustering

from forest_clustering import UnsupervisedBinaryTreeClusterer

bt = UnsupervisedBinaryTreeClusterer(
    n_clusters=4,
    max_depth=5,
    min_samples_leaf=10,
    random_state=42,
)

labels = bt.fit_predict(X)
rules = bt.rules()

Use this when you need human-readable cluster rules instead of only a proximity matrix.

Automatic parameter selection

from forest_clustering import AutoTreeClusterer

auto = AutoTreeClusterer(
    algorithms=("forest", "urf", "extratrees"),
    k_range=(2, 3, 4, 5),
    scoring="combined",
    n_restarts=3,
    random_state=42,
)

labels = auto.fit_predict(X)
best_model = auto.best_estimator_
results = auto.cv_results_

AutoTreeClusterer is deliberately conservative: it does not claim to find a universally true clustering. It automates the practical choices users normally tune by hand: algorithm family, cluster count, selected hyperparameters and seed robustness.

Using custom downstream clusterers

All estimators keep a sklearn-like interface. For proximity-based tree estimators, downstream clusterers with metric="precomputed" receive a distance matrix. Other clusterers receive a sparse one-hot leaf embedding, not raw leaf ids.

from sklearn.cluster import AgglomerativeClustering, KMeans
from forest_clustering import UnsupervisedRandomForestClusterer

# Distance-matrix downstream clustering
agg = AgglomerativeClustering(n_clusters=3, metric="precomputed", linkage="average")
model = UnsupervisedRandomForestClusterer(clusterer=agg, random_state=0)
labels = model.fit_predict(X)

# Feature-matrix downstream clustering
km = KMeans(n_clusters=3, n_init="auto", random_state=0)
model = UnsupervisedRandomForestClusterer(clusterer=km, random_state=0)
labels = model.fit_predict(X)

sklearn pipeline usage

from sklearn.pipeline import make_pipeline
from sklearn.cluster import MiniBatchKMeans
from forest_clustering import ForestTransformer

pipe = make_pipeline(
    ForestTransformer(n_iterations=300, n_bins=3, random_state=42),
    MiniBatchKMeans(n_clusters=5, random_state=42),
)

labels = pipe.fit_predict(X)

Practical recommendations

Goal	Recommendation
Fast baseline	ForestClusterer(n_iterations=100, n_bins=3)
Mixed-type candidate with possible extreme values	Start with ForestClusterer(cut_strategy="quantile", corr_threshold=0.8), then test stability against a non-quantile configuration and standard baselines.
Canonical tree proximity	UnsupervisedRandomForestClusterer(n_estimators=300)
Faster randomized tree proximity	ExtraTreesProximityClusterer(n_estimators=300)
Explainable clusters	UnsupervisedBinaryTreeClusterer(n_clusters=k)
Unknown algorithm / cluster count	Use AutoTreeClusterer(k_range=range(2, 8), scoring="combined") for candidate selection, then review stability, profiles, and baseline comparisons.
Unknown number of clusters but fixed algorithm	Pair proximity/distance with DBSCAN, HDBSCAN, or graph clustering; expect sensitivity to density, connectivity, and resolution parameters.
Large data	Prefer MiniBatchKMeans on embeddings; graph/LSH helpers are optional candidates whose connectivity and community count must be checked.

API summary

Most estimators implement:

fit(X, y=None)
fit_predict(X, y=None)
fit_transform(X, y=None)
transform(X)
pairwise_distance(...)
similarity_matrix(...)

AutoTreeClusterer additionally exposes best_estimator_, best_algorithm_, best_n_clusters_, best_score_, best_params_, cv_results_, and search_results_.

Tree-proximity estimators also implement:

proximity_matrix(X=None, Y=None)
transform_onehot(X)   # URF and ExtraTrees

UnsupervisedBinaryTreeClusterer also implements:

predict(X)
rules()

Development

python -m pip install -e ".[dev]"
python -m pytest -q

Build and deploy

Build distribution archives:

python -m pip install --upgrade build twine
rm -rf dist build *.egg-info
python -m build
python -m twine check dist/*

Upload to TestPyPI first:

python -m twine upload --repository testpypi dist/*

Upload to PyPI after verifying the TestPyPI package:

python -m twine upload dist/*

Use API tokens rather than account passwords. For token-based uploads, username is usually __token__ and the password is the token value.

Documentation

See ALGORITHM.md for the mathematical and implementation details.

License

MIT

Explaining clusters and assigning new samples

Version 0.7.0 adds a supervised explanation layer. The clusterer still defines the segmentation; the classifier learns to reproduce those labels for deployment and interpretation.

from forest_clustering import AutoTreeClusterer, ClusterLabelClassifier, ClusterSurrogateTree

clusterer = AutoTreeClusterer(
    algorithms=("forest", "urf", "extratrees", "binary_tree"),
    k_range=range(2, 8),
    scoring="combined",
    random_state=42,
)

assigner = ClusterLabelClassifier(
    clusterer=clusterer,
    cv=5,
    confidence_threshold=0.60,
    unknown_policy="reject",
    random_state=42,
)
assigner.fit(X)

labels = assigner.labels_              # labels from the clusterer
new_labels = assigner.predict(X_new)    # -1 for low-confidence rows when reject mode is enabled
proba = assigner.predict_proba(X_new)
print(assigner.fidelity_summary())
print(assigner.explain_clusters())

For compact rules, fit a shallow surrogate decision tree:

explainer = ClusterSurrogateTree(
    clusterer=clusterer,
    max_depth=4,
    min_samples_leaf=20,
    random_state=42,
).fit(X)

print(explainer.explain_rules(min_purity=0.70))
print(explainer.rules_dataframe())

Visualization helpers return matplotlib axes and can be used in notebooks:

assigner.plot_cluster_sizes()
assigner.plot_embedding()
assigner.plot_feature_importances(top_n=15)
assigner.plot_fidelity_confusion_matrix(normalize=True)
explainer.plot_tree()

The reported accuracy, balanced accuracy and F1 are fidelity metrics: they measure how well the supervised surrogate reproduces cluster labels. They are not external clustering-quality scores.

Prototype sampling and subsampled clustering

Version 0.8.0 added a conservative compression layer for large datasets. The goal is not to throw rows away blindly; the sampler builds weighted prototypes and stores the map from every original row back to its prototype.

from forest_clustering import PrototypeSampler, SubsampledClusterer, AutoTreeClusterer

sampler = PrototypeSampler(
    method="leaf_signature",
    compression=0.20,          # keep roughly up to 20% prototypes
    n_partitions=128,
    n_bins="auto",
    preserve_rare=True,        # protect tiny buckets / rare groups
    rare_bucket_min_size=3,
    random_state=42,
)

X_proto, weights = sampler.fit_resample(X)
print(sampler.compression_summary())

clusterer = AutoTreeClusterer(k_range=range(2, 8), random_state=42)
model = SubsampledClusterer(sampler=sampler, clusterer=clusterer)
labels = model.fit_predict(X)          # labels for all original rows
labels_new = model.predict(X_new)      # assigned through nearest prototype

Two sampler modes are provided:

Method	Idea	Use when
leaf_signature	Use the library's random partition signatures, group rows with the same coarse signature, keep representative rows plus weights.	Mixed-type tabular data, many duplicates or near-duplicates, tree-clustering workflows.
birch	Use sklearn BIRCH on a numeric encoded feature space and keep medoid prototypes for subclusters.	Dense numeric data or already well-encoded features.

The sampler exposes diagnostics and plots:

sampler.plot_compression()
sampler.plot_prototype_weights()
sampler.plot_reconstruction_error()

Important: prototype sampling can speed up expensive clustering, especially when pairwise proximity matrices would otherwise be large. It can also damage rare microclusters if configured aggressively. Keep preserve_rare=True unless you are deliberately compressing noise.

Diagnostics and visualisation

Version 0.9.0 adds a diagnostic workflow for checking whether a clustering result is usable.

from forest_clustering import AutoTreeClusterer, ClusterDiagnosticsReport

model = AutoTreeClusterer(k_range=range(2, 8), random_state=42).fit(X)
report = ClusterDiagnosticsReport(model, X)

print(report.summary())
print(report.health_checks())
print("\n\n".join(report.cluster_cards()))

report.plot_overview()
report.plot_proximity_heatmap()
report.plot_cluster_profiles()

For stochastic algorithms, inspect stability:

from forest_clustering import StabilityAnalyzer

stability = StabilityAnalyzer(model, n_runs=10, random_state=42).fit(X)
print(stability.summary())
stability.plot_score_distribution()

For model comparison:

from forest_clustering import compare_clusterings, ForestClusterer, UnsupervisedRandomForestClusterer
from sklearn.cluster import KMeans

comparison = compare_clusterings(X, {
    "forest": ForestClusterer(n_clusters=3, random_state=42),
    "urf": UnsupervisedRandomForestClusterer(n_clusters=3, random_state=42),
    "kmeans": KMeans(n_clusters=3, n_init=10, random_state=42),
})

print(comparison.rank())
comparison.plot_scores()
comparison.plot_pairwise_agreement()

The diagnostics are practical warning signals, not mathematical proof that a segmentation is uniquely correct. Treat health checks, stability and cluster cards as a review process before using clusters in production.

compare_clusterings() automatically retries ordinary sklearn estimators on a robust encoded feature matrix when they cannot consume mixed string/categorical columns. This makes baseline comparisons convenient without changing the native preprocessing of forest-clustering estimators.