Metadata-Version: 2.4
Name: scikit-clarans
Version: 0.3.0
Summary: A scikit-learn compatible implementation of CLARANS clustering algorithm
Home-page: https://github.com/ThienNguyen3001/scikit-clarans
Author: Ngọc Thiện Nguyễn
Author-email: thiennguyen03001@gmail.com
License: MIT
Keywords: clustering sklearn scikit-learn clarans k-medoids
Classifier: Development Status :: 3 - Alpha
Classifier: Environment :: Console
Classifier: Intended Audience :: Developers
Classifier: Intended Audience :: Science/Research
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Topic :: Scientific/Engineering
Requires-Python: >=3.9
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy
Requires-Dist: scikit-learn
Requires-Dist: scipy
Provides-Extra: dev
Requires-Dist: pytest; extra == "dev"
Requires-Dist: pytest-cov; extra == "dev"
Requires-Dist: flake8; extra == "dev"
Requires-Dist: pandas; extra == "dev"
Requires-Dist: sphinx>=5.0; extra == "dev"
Requires-Dist: sphinx-rtd-theme; extra == "dev"
Requires-Dist: sphinx-copybutton; extra == "dev"
Requires-Dist: sphinx-autodoc-typehints; extra == "dev"
Requires-Dist: cython; extra == "dev"
Provides-Extra: test
Requires-Dist: pytest; extra == "test"
Requires-Dist: pytest-cov; extra == "test"
Requires-Dist: flake8; extra == "test"
Requires-Dist: pandas; extra == "test"
Provides-Extra: docs
Requires-Dist: sphinx>=5.0; extra == "docs"
Requires-Dist: sphinx-rtd-theme; extra == "docs"
Requires-Dist: sphinx-copybutton; extra == "docs"
Requires-Dist: sphinx-autodoc-typehints; extra == "docs"
Dynamic: author
Dynamic: author-email
Dynamic: classifier
Dynamic: description
Dynamic: description-content-type
Dynamic: home-page
Dynamic: keywords
Dynamic: license
Dynamic: license-file
Dynamic: provides-extra
Dynamic: requires-dist
Dynamic: requires-python
Dynamic: summary

# scikit-clarans

> A scikit-learn compatible implementation of **CLARANS** and **FastCLARANS** for scalable $k$-medoids clustering.

[![License](https://img.shields.io/github/license/ThienNguyen3001/scikit-clarans)](LICENSE)
[![DOI](https://zenodo.org/badge/DOI/10.5281/zenodo.18366801.svg)](https://doi.org/10.5281/zenodo.18366801)
[![Python 3.9+](https://img.shields.io/badge/python-3.9+-blue.svg)](https://www.python.org/downloads/)
[![Docs Build](https://img.shields.io/github/actions/workflow/status/ThienNguyen3001/scikit-clarans/docs-build.yml?branch=main&label=Docs%20Build)](https://github.com/ThienNguyen3001/scikit-clarans/actions/workflows/docs-build.yml)
[![Test Suite](https://img.shields.io/github/actions/workflow/status/ThienNguyen3001/scikit-clarans/test_suite.yml?branch=main&label=Test%20Suite)](https://github.com/ThienNguyen3001/scikit-clarans/actions/workflows/test_suite.yml)
[![Quality Check](https://img.shields.io/github/actions/workflow/status/ThienNguyen3001/scikit-clarans/lint_cov_check.yml?branch=main&label=Quality%20Check)](https://github.com/ThienNguyen3001/scikit-clarans/actions/workflows/lint_cov_check.yml)
[![PyPI version](https://img.shields.io/pypi/v/scikit-clarans.svg)](https://pypi.org/project/scikit-clarans/)
[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/drive/194aBBu0wZotnun25dXqlOrDj3HYHKo-a?usp=sharing)

> [!NOTE]
> **Educational & Research Scope**: `scikit-clarans` is developed primarily for **learning, algorithmic study, and small-to-medium academic research**. It pairs a high-performance **Cython C-extension core** (with pure Python fallback) with an $O(n)$ memory footprint, substantially more scalable and accessible than classic $O(n^2)$ PAM.

**scikit-clarans** brings scalable $k$-medoids clustering to Python with a native scikit-learn API. Unlike $k$-means which computes artificial centroids (means), $k$-medoids picks **actual data points** as cluster centers.

### Why k-Medoids over k-Means?
* **Outlier Robust**: Minimizes absolute distance ($\sum d$) rather than squared Euclidean distance ($\sum d^2$), so extreme values won't skew cluster centers.
* **Custom Distance Metrics**: Works with `cosine`, `manhattan`, `euclidean`, or any valid metric—unlike $k$-means which is strictly Euclidean.
* **Directly Interpretable**: Medoids are real observations from your dataset (e.g., representative user profiles, real molecules, exemplary documents).

### CLARANS vs. FastCLARANS: Which one to use?
* **`FastCLARANS` (Recommended for most workloads)**: Uses FastPAM1 delta calculations (Schubert & Rousseeuw, 2021) to evaluate all $k$ medoids at once. Explores $k$ graph edges in the time CLARANS explores one, yielding substantial speedups with $O(n)$ memory and native C-extension acceleration.
* **`CLARANS`**: Randomized search (Ng & Han, 2002) with optional distance caching (`cost_evaluation='delta'`, default) for fast $O(n)$ swap evaluations, or classic brute-force cost recalculation (`cost_evaluation='brute_force'`).

---

## Features

* **Scikit-Learn Native**: Inherits from `BaseEstimator` and `ClusterMixin`. Plug-and-play in scikit-learn `Pipeline`, `GridSearchCV`, and clustering evaluations.
* **Cython & C-Accelerated**: Core delta cost updates and cache tracking are accelerated with compiled C-extensions (Cython), with seamless fallback to pure Python/NumPy if C extensions are unavailable.
* **Cascading Distance Engine**: Automatically routes distance computations through the fastest available engine: SciPy `cdist` (C-kernel for dense arrays), Scikit-Learn `DistanceMetric` (for sparse CSR matrices & callables), or `pairwise_distances`.
* **Memory Efficient**: Computes distances on-the-fly ($O(n)$ memory overhead) to easily scale to tens of thousands of samples without blowing up RAM ($O(n^2)$).
* **Flexible Seeding**: Supports multiple initialization strategies (`k-medoids++`, `build`, `heuristic`, `random`, or custom array).

## Installation

Install simply via pip:
```bash
pip install scikit-clarans
```
Or install from source:
```bash
pip install .
```
For development
```bash
pip install -e ".[dev]"
```

## Quick Start
### CLARANS
```python
from clarans import CLARANS
from sklearn.datasets import make_blobs

# 1. Create dummy data
X, _ = make_blobs(n_samples=1000, centers=5, random_state=42)

# 2. Initialize CLARANS
#    - n_clusters: 5 clusters
#    - num_local: 3 restarts for better quality
#    - init: 'k-medoids++' for smart starting points
#    - cost_evaluation: 'delta' (default) for fast O(n) swap evaluations; 'brute_force' for classic baseline
clarans = CLARANS(n_clusters=5, num_local=3, init='k-medoids++', cost_evaluation='delta', random_state=42)

# 3. Fit
clarans.fit(X)

# 4. Results
print("Medoid Indices:", clarans.medoid_indices_)
print("Labels:", clarans.labels_)
```
### FastCLARANS

**FastCLARANS** implements the faster variant from Schubert & Rousseeuw (2021). It evaluates swaps with all k medoids simultaneously using FastPAM1 delta formulas, exploring k edges of the search graph in the time CLARANS explores one:

```python
from clarans import FastCLARANS

# FastCLARANS computes distances on-the-fly (memory efficient)
# and samples max(250, 2.5% of non-medoid points) per iteration
fast_model = FastCLARANS(n_clusters=5, num_local=3, random_state=42)
fast_model.fit(X)
```

**Key differences from CLARANS:**
- Samples only non-medoid candidates (not medoid-candidate pairs)
- Evaluates swap with all k medoids at once (O(k) speedup per evaluation)
- Memory efficient: O(n) instead of O(n²)

## Examples

This repository includes a number of runnable examples in the `examples/` folder showing common usage patterns and integrations. Run any example with:

```bash
python examples/01_quick_start.py
```

## Documentation

For full API reference and usage guides, please see the [Documentation](https://scikit-clarans.readthedocs.io/en/latest/index.html).

## Contributing

Contributions are welcome! Please check out [CONTRIBUTING.md](CONTRIBUTING.md) for guidelines.

## Citation

If you use `scikit-clarans` in your software or research, please cite:

```bibtex
@software{scikit_clarans,
  author       = {Nguyen, Ngoc Thien},
  title        = {scikit-clarans: A Python Library for CLARANS Clustering},
  year         = {2026},
  publisher    = {Zenodo},
  doi          = {10.5281/zenodo.18366801},
  url          = {https://github.com/ThienNguyen3001/scikit-clarans}
}
```

### Academic References

The core algorithms implemented in this package originate from:

* **CLARANS:**
  > Ng, R. T., & Han, J. (2002). *CLARANS: A method for clustering objects for spatial data mining.* IEEE Transactions on Knowledge and Data Engineering, 14(5), 1003-1016. [doi:10.1109/TKDE.2002.1033770](https://doi.org/10.1109/TKDE.2002.1033770)
* **FastCLARANS & FastPAM1:**
  > Schubert, E., & Rousseeuw, P. J. (2021). *Fast and eager k-medoids clustering: O(k) runtime improvement of the PAM, CLARA, and CLARANS algorithms.* Information Systems, 101, 101804. [doi:10.1016/j.is.2021.101804](https://doi.org/10.1016/j.is.2021.101804)
* **Seeding & Initialization:**
  > Initialization strategies (`k-medoids++`, `heuristic`, `build`) are adapted from the [scikit-learn-extra KMedoids](https://scikit-learn-extra.readthedocs.io/en/stable/generated/sklearn_extra.cluster.KMedoids.html) implementation.

## License

This project is licensed under the MIT License - see the [LICENSE](LICENSE) file for details.
