densoc

Synthetic dataset generator for density-based clustering benchmarks.

Generates configurable synthetic datasets for evaluating density clustering algorithms (DBSCAN, HDBSCAN, etc.) using an evolutionary approach — random-walk cluster growth with simulated annealing. Supports non-convex clusters, controlled density variation, and configurable noise.

---

Features

• Overlapping-ball union as cluster model — supports arbitrary non-convex shapes
• Low-density inter-cluster gaps — ensures clean separation for boundary tests
• Equal & multi-density modes — uniform or varied cluster densities
• Simulated annealing — jointly optimizes cluster shapes and point counts
• Importance-weighted rejection sampling — eliminates overlap bias in multi-ball unions

---

Installation

pip install densoc

Or for development:

git clone https://github.com/djw-easy/densoc.git
cd densoc
pip install -e ".[dev,viz]"

Requirements: Python ≥ 3.10, NumPy ≥ 1.24, SciPy ≥ 1.10.

---

Quick Start

from densoc import generate_dataset, GeneratorConfig

cfg = GeneratorConfig(d=2, k=4, N=1000, p_noise=0.1, seed=42)
X, y = generate_dataset(cfg)

# X.shape == (1000, 2)
# y: 0 = noise, 1..k = cluster labels

Generate multiple datasets

from densoc import generate_datasets

datasets = generate_datasets(
    num=10,
    config=cfg,
    seeds=list(range(100, 110)),
)

Multi-density mode

cfg = GeneratorConfig(
    d=2, k=5, N=1200,
    equal_density=False,   # enable multi-density
    density_cv=1.2,       # target coefficient of variation
    seed=123,
)
X, y = generate_dataset(cfg)

---

Configuration

Parameter	Default	Description
d	2	Data dimension (1–10)
l	100.0	Domain side length, Ω = [0, l]^d
k	4	Number of clusters
r_min, r_max	2.0, 12.0	Ball radius range
intersection_ratio	0.2	Connectivity depth (higher → tighter overlap required)
target_balls_min/max	3, 12	Balls per cluster
separation	5.0	Minimum inter-cluster surface distance
noise_buffer	3.0	Minimum distance from noise points to cluster boundary
N	1000	Total sample count
p_noise	0.1	Noise proportion (0–0.5)
equal_density	True	True = equal density; False = multi-density
density_cv	0.5	Target density CV in multi-density mode
sa_steps	200	Annealing steps (0 = skip)
concentration	0.0	Radial concentration (0 = uniform volume)
seed	None	Random seed for reproducibility

---

Architecture

densoc/
├── __init__.py       # Public API: generate_dataset, generate_datasets, GeneratorConfig
├── config.py         # Configuration dataclass + validation
├── geometry.py       # Ball, UnionBallCluster, volume/connectivity primitives
├── growth.py         # Random-walk cluster growth (initialize_clusters, grow_clusters)
├── annealing.py      # Simulated annealing (shape + point-count co-optimisation)
├── sampling.py       # Importance-weighted rejection sampling + noise generation
├── generator.py      # Top-level pipeline (single + batch generation)
└── utils.py         # Halton sequence, cooling schedule, cone sampling

---

Algorithm Overview

1. Seed placement — place k mutually-separated seed balls in Ω
2. Random-walk growth — each cluster grows via a walker that adds balls subject to connectivity, isolation, and boundary constraints; directional bias encourages chain-like non-convex shapes
3. Point allocation — assign initial point counts proportional to cluster volume and density weight
4. Simulated annealing — jointly perturb ball geometry and point counts, accepting moves via Metropolis criterion; constraints enforced as hard rules (boundary, connectivity, isolation)
5. Sampling — importance-weighted rejection sampling inside ball unions; Halton-sequence sampling in the low-density noise region

---

Demo

Run the interactive notebook:

cd examples
jupyter notebook demo.ipynb

---

License

MIT