MCMSTClustering

MCMSTClustering is a density-based clustering algorithm that detects arbitrary-shaped clusters in datasets containing outliers, imbalanced class distributions, and varying-density regions — all simultaneously.

Şenol, A. (2023). MCMSTClustering: defining non-spherical clusters by using minimum spanning tree over KD-tree-based micro-clusters. Neural Computing and Applications, 35, 13239–13259. https://doi.org/10.1007/s00521-023-08386-3

How It Works

The algorithm runs in three stages:

1. Micro-cluster formation — A KD-Tree is built over the data. Range searches of radius r group dense regions into micro-clusters; a candidate region must contain at least N points.

2. Macro-cluster construction — Prim's Minimum Spanning Tree is run on the micro-cluster centroids. Edges longer than 2 × r are excluded (sparse graph), keeping runtime practical. Connected components with at least n_micro micro-clusters become macro-clusters.

3. Cluster regulation — Unassigned points within distance 2 × r of any micro-cluster centroid are absorbed, closing gaps between micro-clusters of the same macro-cluster.

Points remaining unassigned are labelled -1 (noise/outlier).

Installation

pip install mcmst-clust

Or install from source:

git clone https://github.com/senolali/MCMSTClustering.git
cd MCMSTClustering
pip install -e .

Quick Start

import numpy as np
from sklearn.preprocessing import MinMaxScaler
from mcmstclustering import MCMSTClustering

# Generate two-blob dataset
rng = np.random.default_rng(42)
X = np.vstack([
    rng.normal([0.2, 0.2], 0.05, (150, 2)),
    rng.normal([0.8, 0.8], 0.05, (150, 2)),
])

# Normalise to [0, 1] — strongly recommended
X = MinMaxScaler().fit_transform(X)

# Fit
model = MCMSTClustering(N=5, r=0.08, n_micro=2)
labels = model.fit_predict(X)

print(f"Clusters found : {model.n_clusters_}")
print(f"Micro-clusters : {len(model.micro_clusters_)}")
print(f"Noise points   : {(labels == -1).sum()}")

Parameters

Tip: Normalise your data to [0, 1] with sklearn.preprocessing.MinMaxScaler before fitting. The paper uses this normalisation throughout all experiments.

Attributes (after fitting)

Scikit-learn Compatibility

MCMSTClustering extends sklearn.base.BaseEstimator and ClusterMixin, so it works seamlessly with scikit-learn utilities:

from sklearn.pipeline import Pipeline
from sklearn.preprocessing import MinMaxScaler
from mcmstclustering import MCMSTClustering

pipe = Pipeline([
    ("scaler", MinMaxScaler()),
    ("clustering", MCMSTClustering(N=5, r=0.06, n_micro=3)),
])
labels = pipe.fit_predict(X)

Example — Visualisation

import matplotlib.pyplot as plt
import numpy as np
from sklearn.datasets import make_moons
from sklearn.preprocessing import MinMaxScaler
from mcmstclustering import MCMSTClustering

X, _ = make_moons(n_samples=400, noise=0.07, random_state=0)
X = MinMaxScaler().fit_transform(X)

model = MCMSTClustering(N=5, r=0.08, n_micro=3).fit(X)

plt.figure(figsize=(6, 4))
plt.scatter(X[:, 0], X[:, 1], c=model.labels_, cmap="tab10", s=10)
plt.title(f"MCMSTClustering — {model.n_clusters_} clusters found")
plt.tight_layout()
plt.savefig("moons_result.png", dpi=150)
plt.show()

Comparison with State-of-the-Art

From the original paper (22 datasets, 4 indices: ARI, Accuracy, Purity, NMI):

Citation

If you use MCMSTClustering in your research, please cite:

@article{senol2023mcmstclustering,
  title     = {MCMSTClustering: defining non-spherical clusters by using
               minimum spanning tree over KD-tree-based micro-clusters},
  author    = {{\c{S}}enol, Ali},
  journal   = {Neural Computing and Applications},
  volume    = {35},
  pages     = {13239--13259},
  year      = {2023},
  publisher = {Springer},
  doi       = {10.1007/s00521-023-08386-3}
}

License

MIT License — see LICENSE for details.