elsara 0.2.0

EquaL-size SpectrAl clusteRing Algorithm

ELSARA: EquaL-size SpectrAl clusteRing Algorithm

This is a modification of the spectral clustering algorithm that builds clusters balanced in the number of points. A detailed explanation of the model can be found in this Medium blog post.

Prerequisities

• Python 3.13
• Poetry (in MAC: brew install poetry)

Setup

Install dependencies and register the git hooks:

poetry install
make install-hooks

Code formatting

This project uses ruff and black for code formatting. To format all files manually, run:

make format

Formatting also runs automatically on every commit via pre-commit.

Toy datasets

In the folder datasets we have provided you with a toy dataset so you can run the clustering code right away.

• restaurants_in_amsterdam.csv: A table with locations of restaurants in the city of Amsterdam
• symmetric_distr_tr.npy: A file with the travel distance between the restaurants

You can find more specification on how to use these datasets in the project's blog post.

Examples

• example1.py: From a set of hyperparameters, you obtain clusters with sizes roughly equal to N / nclusters
• example2.py: From a range of cluster sizes, you obtain the clusters hyperparameters to run the clustering code.

Usage

Example 1: fixed hyperparameters

Provide nclusters, nneighbors, and equity_fraction directly. Each cluster will contain roughly N / nclusters points.

import pandas as pd
import numpy as np
from elsara import SpectralEqualSizeClustering, visualise_clusters

# coords is used only for visualization
coords = pd.read_csv("datasets/restaurants_in_amsterdam.csv")
dist_tr = np.load("datasets/symmetric_dist_tr.npy")

clustering = SpectralEqualSizeClustering(
    nclusters=6, nneighbors=int(dist_tr.shape[0] * 0.1), equity_fraction=1, seed=1234
)

labels = clustering.fit(dist_tr)

coords["cluster"] = labels
clusters_figure = visualise_clusters(
    coords,
    longitude_colname="longitude",
    latitude_colname="latitude",
    label_col="cluster",
    zoom=11,
)
clusters_figure.show()

Example 2: derive hyperparameters from a target size range

Specify the desired min/max cluster size and let the algorithm derive the hyperparameters automatically.

import pandas as pd
import numpy as np
from elsara import SpectralEqualSizeClustering, visualise_clusters

coords = pd.read_csv("datasets/restaurants_in_amsterdam.csv")
dist_tr = np.load("datasets/symmetric_dist_tr.npy")

min_range, max_range = 50, 70  # desired number of points per cluster

npoints = coords.shape[0]
avg_range = (max_range + min_range) / 2.0
nclusters = int(npoints / avg_range)
equity_fraction = 1 - ((avg_range - min_range) / avg_range)
nneighbors = int(npoints * (avg_range / npoints))

clustering = SpectralEqualSizeClustering(
    nclusters=nclusters, nneighbors=nneighbors, equity_fraction=equity_fraction, seed=1234
)

labels = clustering.fit(dist_tr)

coords["cluster"] = labels
clusters_figure = visualise_clusters(
    coords,
    longitude_colname="longitude",
    latitude_colname="latitude",
    label_col="cluster",
    zoom=11,
)
clusters_figure.show()

License

This project is licensed under the MIT License.