Metadata-Version: 2.4
Name: mcmst-clust
Version: 1.2.0
Summary: MCMSTClustering: Non-spherical cluster detection via Minimum Spanning Tree over KD-Tree-based micro-clusters
Author-email: Ali Şenol <alisenol@tarsus.edu.tr>
License: MIT License
        
        Copyright (c) 2023 Ali Şenol
        
        Permission is hereby granted, free of charge, to any person obtaining a copy
        of this software and associated documentation files (the "Software"), to deal
        in the Software without restriction, including without limitation the rights
        to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
        copies of the Software, and to permit persons to whom the Software is
        furnished to do so, subject to the following conditions:
        
        The above copyright notice and this permission notice shall be included in all
        copies or substantial portions of the Software.
        
        THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
        IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
        FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
        AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
        LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
        OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
        SOFTWARE.
        
Project-URL: Homepage, https://github.com/senolali/MCMSTClustering
Project-URL: Repository, https://github.com/senolali/MCMSTClustering
Project-URL: Bug Tracker, https://github.com/senolali/MCMSTClustering/issues
Project-URL: Documentation, https://github.com/senolali/MCMSTClustering#readme
Project-URL: Paper, https://doi.org/10.1007/s00521-023-08386-3
Keywords: clustering,minimum spanning tree,kd-tree,micro-cluster,arbitrary-shaped clusters,density-based clustering,machine learning,unsupervised learning
Classifier: Development Status :: 5 - Production/Stable
Classifier: Intended Audience :: Science/Research
Classifier: Intended Audience :: Developers
Classifier: License :: OSI Approved :: MIT License
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Topic :: Scientific/Engineering :: Artificial Intelligence
Classifier: Topic :: Scientific/Engineering :: Information Analysis
Classifier: Operating System :: OS Independent
Requires-Python: >=3.9
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy>=1.23
Requires-Dist: scipy>=1.9
Requires-Dist: scikit-learn>=1.1
Provides-Extra: dev
Requires-Dist: pytest>=7.0; extra == "dev"
Requires-Dist: pytest-cov>=4.0; extra == "dev"
Requires-Dist: black>=23.0; extra == "dev"
Requires-Dist: isort>=5.12; extra == "dev"
Requires-Dist: flake8>=6.0; extra == "dev"
Requires-Dist: mypy>=1.0; extra == "dev"
Provides-Extra: examples
Requires-Dist: matplotlib>=3.5; extra == "examples"
Requires-Dist: pandas>=1.5; extra == "examples"
Dynamic: license-file

# MCMSTClustering

[![PyPI version](https://badge.fury.io/py/mcmst-clust.svg)](https://badge.fury.io/py/mcmst-clust)
[![Python 3.9+](https://img.shields.io/badge/python-3.9+-blue.svg)](https://www.python.org/downloads/)
[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT)

**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](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

```bash
pip install mcmst-clust
```

Or install from source:

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

---

## Quick Start

```python
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

| Parameter | Type | Default | Description |
|-----------|------|---------|-------------|
| `N` | int | 5 | Minimum points required to form a micro-cluster |
| `r` | float | 0.05 | Search radius for micro-cluster formation (Euclidean) |
| `n_micro` | int | 3 | Minimum micro-clusters to form a macro-cluster |

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

---

## Attributes (after fitting)

| Attribute | Description |
|-----------|-------------|
| `labels_` | Cluster label per sample; `-1` = noise |
| `n_clusters_` | Number of macro-clusters found |
| `micro_clusters_` | List of index arrays, one per micro-cluster |
| `micro_cluster_centers_` | Centroid array of shape `(n_mc, n_features)` |
| `n_features_in_` | Number of features seen during fit |

---

## Scikit-learn Compatibility

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

```python
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

```python
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):

| Algorithm | Best results (out of 88 tests) |
|-----------|-------------------------------|
| **MCMSTClustering** | **62** |
| MST_Clustering | 51 |
| genieclust | 48 |
| DBSCAN | 45 |
| Agglomerative | 17 |
| k-means | 17 |
| Spectral | 9 |

---

## Citation

If you use MCMSTClustering in your research, please cite:

```bibtex
@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](LICENSE) for details.
