k-means-constrained

What it is and what it does

k-means-constrained is a variant of k-means clustering that enforces minimum and maximum size constraints on each cluster. Instead of the standard assignment step, it formulates cluster assignment as a minimum cost flow optimization problem solved by ortools' cost-scaling push-relabel algorithm. This ensures that every cluster respects the specified size bounds while minimizing overall distance, making it useful when balanced or size-controlled partitioning is required.

The package implements a scikit-learn-compatible API and depends on ortools, scipy, numpy, six, and joblib. It trades computational speed for constraint satisfaction: the time complexity is substantially higher than vanilla k-means, scaling as O((n³c + n²c² + nc³)log(n+c)) versus O(nc) for standard k-means. The package is actively maintained, supports Python 3.10–3.13 with recent free-threading beta support, and has no known vulnerabilities.

Use it for:

• Partition customer data into balanced segments for fair resource allocation or stratified analysis
• Create evenly-sized geographic clusters or facility assignments where each region must serve a minimum/maximum population
• Generate balanced train/test splits or cross-validation folds with size guarantees
• Cluster time-series or sensor data where each cluster must contain a minimum viable sample size for statistical validity

Worth the install?

AI-flagged interpretation of the facts on this page — verify before relying

K-means clustering with enforced minimum and maximum cluster sizes, using a minimum cost flow algorithm to solve the constrained assignment step.

Yes, if you need size-constrained clustering and can tolerate higher computational cost. The package is stable (Production/Stable status), actively maintained, permissively licensed, and has no security vulnerabilities. Install friction is medium due to compiled wheels, but pre-built binaries for modern Python versions (3.10–3.13) and multiple platforms are available. Not recommended if you need vanilla k-means performance on large datasets or if cluster size constraints are not a hard requirement.

Install

k-means-constrained on PyPI

pip install k-means-constrained

uv add k-means-constrained

poetry add k-means-constrained

Installing k-means-constrained

Before you install

Medium install friction due to compiled wheels across multiple Python versions and platforms. Active maintenance with recent release (40 days ago); repository shows steady development with 236 stars and no archived status.

License in practice

BSD 3-Clause permissive license allows commercial and private use with minimal restrictions; attribution and license notice required in distributions.

Quickstart

pip install k-means-constrained
from k_means_constrained import KMeansConstrained
import numpy as np
X = np.array([[1, 2], [1, 4], [1, 0], [4, 2], [4, 4], [4, 0]])
clf = KMeansConstrained(n_clusters=2, size_min=2, size_max=5, random_state=0)
clf.fit_predict(X)

Verify before relying

• Whether performance degradation at scale is acceptable for your data size and cluster count
• Compatibility with free-threaded Python (3.14t) given ortools' GIL re-enablement behavior

Package facts

Evidence: k_means_constrained-0.9.1-cp310-cp310-macosx_10_9_x86_64.whl; k_means_constrained-0.9.1-cp310-cp310-macosx_11_0_arm64.whl; k_means_constrained-0.9.1-cp310-cp310-manylinux2014_aarch64.manylinux_2_17_aarch64.manylinux_2_28_aarch64.whl; k_means_constrained-0.9.1-cp310-cp310-manylinux2014_x86_64.manylinux_2_17_x86_64.manylinux_2_28_x86_64.whl; k_means_constrained-0.9.1-cp310-cp310-win_amd64.whl; k_means_constrained-0.9.1-cp311-cp311-macosx_10_9_x86_64.whl; k_means_constrained-0.9.1-cp311-cp311-macosx_11_0_arm64.whl; k_means_constrained-0.9.1-cp311-cp311-manylinux2014_aarch64.manylinux_2_17_aarch64.manylinux_2_28_aarch64.whl; k_means_constrained-0.9.1-cp311-cp311-manylinux2014_x86_64.manylinux_2_17_x86_64.manylinux_2_28_x86_64.whl; k_means_constrained-0.9.1-cp311-cp311-win_amd64.whl; k_means_constrained-0.9.1-cp312-cp312-macosx_10_13_x86_64.whl; k_means_constrained-0.9.1-cp312-cp312-macosx_11_0_arm64.whl; k_means_constrained-0.9.1-cp312-cp312-manylinux2014_aarch64.manylinux_2_17_aarch64.manylinux_2_28_aarch64.whl; k_means_constrained-0.9.1-cp312-cp312-manylinux2014_x86_64.manylinux_2_17_x86_64.manylinux_2_28_x86_64.whl; k_means_constrained-0.9.1-cp312-cp312-win_amd64.whl; k_means_constrained-0.9.1-cp313-cp313-macosx_10_13_x86_64.whl; k_means_constrained-0.9.1-cp313-cp313-macosx_11_0_arm64.whl; k_means_constrained-0.9.1-cp313-cp313-manylinux2014_aarch64.manylinux_2_17_aarch64.manylinux_2_28_aarch64.whl; k_means_constrained-0.9.1-cp313-cp313-manylinux2014_x86_64.manylinux_2_17_x86_64.manylinux_2_28_x86_64.whl; k_means_constrained-0.9.1-cp313-cp313-win_amd64.whl

Tags

More Scientific/Engineering packages