Skip to main content

A Python package for optimal 1D k-means clustering

Project description

Build Status

kmeans1d

A Python library with an implementation of k-means clustering on 1D data, based on the algorithm in (Xiaolin 1991), as presented in section 2.2 of (Gronlund et al., 2017).

Globally optimal k-means clustering is NP-hard for multi-dimensional data. Lloyd's algorithm is a popular approach for finding a locally optimal solution. For 1-dimensional data, there are polynomial time algorithms. The algorithm implemented here is a O(kn + n log n) dynamic programming algorithm for finding the globally optimal k clusters for n 1D data points.

The code is written in C++, and wrapped with Python.

Requirements

kmeans1d supports Python 3.x.

Installation

kmeans1d is available on PyPI, the Python Package Index.

$ pip3 install kmeans1d

Example Usage

import kmeans1d

x = [4.0, 4.1, 4.2, -50, 200.2, 200.4, 200.9, 80, 100, 102]
k = 4

clusters, centroids = kmeans1d.cluster(x, k)

print(clusters)   # [1, 1, 1, 0, 3, 3, 3, 2, 2, 2]
print(centroids)  # [-50.0, 4.1, 94.0, 200.5]

Tests

Tests are in tests/.

# Run tests
$ python3 -m unittest discover tests -v

License

The code in this repository has an MIT License.

See LICENSE.

References

[1] Wu, Xiaolin. "Optimal Quantization by Matrix Searching." Journal of Algorithms 12, no. 4 (December 1, 1991): 663

[2] Gronlund, Allan, Kasper Green Larsen, Alexander Mathiasen, Jesper Sindahl Nielsen, Stefan Schneider, and Mingzhou Song. "Fast Exact K-Means, k-Medians and Bregman Divergence Clustering in 1D." ArXiv:1701.07204 [Cs], January 25, 2017. http://arxiv.org/abs/1701.07204.

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

kmeans1d-0.3.1.tar.gz (6.2 kB view hashes)

Uploaded Source

Built Distributions

kmeans1d-0.3.1-cp312-cp312-win_amd64.whl (17.9 kB view hashes)

Uploaded CPython 3.12 Windows x86-64

kmeans1d-0.3.1-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (128.6 kB view hashes)

Uploaded CPython 3.12 manylinux: glibc 2.17+ x86-64

kmeans1d-0.3.1-cp312-cp312-macosx_10_9_universal2.whl (28.0 kB view hashes)

Uploaded CPython 3.12 macOS 10.9+ universal2 (ARM64, x86-64)

kmeans1d-0.3.1-cp311-cp311-win_amd64.whl (17.9 kB view hashes)

Uploaded CPython 3.11 Windows x86-64

kmeans1d-0.3.1-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (128.9 kB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ x86-64

kmeans1d-0.3.1-cp311-cp311-macosx_10_9_universal2.whl (28.0 kB view hashes)

Uploaded CPython 3.11 macOS 10.9+ universal2 (ARM64, x86-64)

kmeans1d-0.3.1-cp310-cp310-win_amd64.whl (18.0 kB view hashes)

Uploaded CPython 3.10 Windows x86-64

kmeans1d-0.3.1-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (102.4 kB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ x86-64

kmeans1d-0.3.1-cp310-cp310-macosx_10_14_x86_64.whl (16.0 kB view hashes)

Uploaded CPython 3.10 macOS 10.14+ x86-64

kmeans1d-0.3.1-cp39-cp39-win_amd64.whl (18.0 kB view hashes)

Uploaded CPython 3.9 Windows x86-64

kmeans1d-0.3.1-cp39-cp39-manylinux2014_x86_64.whl (93.5 kB view hashes)

Uploaded CPython 3.9

kmeans1d-0.3.1-cp39-cp39-macosx_10_14_x86_64.whl (16.1 kB view hashes)

Uploaded CPython 3.9 macOS 10.14+ x86-64

kmeans1d-0.3.1-cp38-cp38-win_amd64.whl (18.0 kB view hashes)

Uploaded CPython 3.8 Windows x86-64

kmeans1d-0.3.1-cp38-cp38-manylinux2014_x86_64.whl (93.6 kB view hashes)

Uploaded CPython 3.8

kmeans1d-0.3.1-cp38-cp38-macosx_10_14_x86_64.whl (15.8 kB view hashes)

Uploaded CPython 3.8 macOS 10.14+ x86-64

kmeans1d-0.3.1-cp37-cp37m-win_amd64.whl (17.9 kB view hashes)

Uploaded CPython 3.7m Windows x86-64

kmeans1d-0.3.1-cp37-cp37m-manylinux2014_x86_64.whl (93.5 kB view hashes)

Uploaded CPython 3.7m

kmeans1d-0.3.1-cp37-cp37m-macosx_10_14_x86_64.whl (15.8 kB view hashes)

Uploaded CPython 3.7m macOS 10.14+ x86-64

kmeans1d-0.3.1-cp36-cp36m-win_amd64.whl (17.9 kB view hashes)

Uploaded CPython 3.6m Windows x86-64

kmeans1d-0.3.1-cp36-cp36m-manylinux2014_x86_64.whl (93.5 kB view hashes)

Uploaded CPython 3.6m

kmeans1d-0.3.1-cp36-cp36m-macosx_10_14_x86_64.whl (15.8 kB view hashes)

Uploaded CPython 3.6m macOS 10.14+ x86-64

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page