[](https://github.com/dstein64/kmeans1d/actions)
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](https://pypi.python.org/pypi/kmeans1d) is available on PyPI, the Python Package Index.
```sh
$ pip3 install kmeans1d
```
Example Usage
-------------
```python
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/](https://github.com/dstein64/kmeans1d/blob/master/tests).
```sh
# Run tests
$ python3 -m unittest discover tests -v
```
License
-------
The code in this repository has an [MIT License](https://en.wikipedia.org/wiki/MIT_License).
See [LICENSE](https://github.com/dstein64/kmeans1d/blob/master/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.
Raw data
{
"_id": null,
"home_page": "https://github.com/dstein64/kmeans1d",
"name": "kmeans1d",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.6",
"maintainer_email": "",
"keywords": "k-means,machine learning,optimization",
"author": "Daniel Steinberg",
"author_email": "ds@dannyadam.com",
"download_url": "https://files.pythonhosted.org/packages/08/2f/5e51cd14e496220e1188f2319e4d757a8498f3d4321a2804089ed72c8786/kmeans1d-0.3.1.tar.gz",
"platform": "",
"description": "[](https://github.com/dstein64/kmeans1d/actions)\n\nkmeans1d\n========\n\nA Python library with an implementation of *k*-means clustering on 1D data, based on the algorithm\nin (Xiaolin 1991), as presented in section 2.2 of (Gronlund et al., 2017).\n\nGlobally optimal *k*-means clustering is NP-hard for multi-dimensional data. Lloyd's algorithm is a\npopular approach for finding a locally optimal solution. For 1-dimensional data, there are polynomial time\nalgorithms. The algorithm implemented here is a *O(kn + n log n)* dynamic programming algorithm for finding\nthe globally optimal *k* clusters for *n* 1D data points.\n\nThe code is written in C++, and wrapped with Python.\n\nRequirements\n------------\n\n*kmeans1d* supports Python 3.x.\n\nInstallation\n------------\n\n[kmeans1d](https://pypi.python.org/pypi/kmeans1d) is available on PyPI, the Python Package Index.\n\n```sh\n$ pip3 install kmeans1d\n```\n\nExample Usage\n-------------\n\n```python\nimport kmeans1d\n\nx = [4.0, 4.1, 4.2, -50, 200.2, 200.4, 200.9, 80, 100, 102]\nk = 4\n\nclusters, centroids = kmeans1d.cluster(x, k)\n\nprint(clusters) # [1, 1, 1, 0, 3, 3, 3, 2, 2, 2]\nprint(centroids) # [-50.0, 4.1, 94.0, 200.5]\n```\n\nTests\n-----\n\nTests are in [tests/](https://github.com/dstein64/kmeans1d/blob/master/tests).\n\n```sh\n# Run tests\n$ python3 -m unittest discover tests -v\n```\n\nLicense\n-------\n\nThe code in this repository has an [MIT License](https://en.wikipedia.org/wiki/MIT_License).\n\nSee [LICENSE](https://github.com/dstein64/kmeans1d/blob/master/LICENSE).\n\nReferences\n----------\n\n[1] Wu, Xiaolin. \"Optimal Quantization by Matrix Searching.\" Journal of Algorithms 12, no. 4\n(December 1, 1991): 663\n\n[2] Gronlund, Allan, Kasper Green Larsen, Alexander Mathiasen, Jesper Sindahl Nielsen, Stefan Schneider,\nand Mingzhou Song. \"Fast Exact K-Means, k-Medians and Bregman Divergence Clustering in 1D.\"\nArXiv:1701.07204 [Cs], January 25, 2017. http://arxiv.org/abs/1701.07204.",
"bugtrack_url": null,
"license": "MIT",
"summary": "A Python package for optimal 1D k-means clustering",
"version": "0.3.1",
"split_keywords": [
"k-means",
"machine learning",
"optimization"
],
"urls": [
{
"comment_text": "",
"digests": {
"md5": "45f08a73535d4a7d0f657ffc95d4cc7f",
"sha256": "406864212b3ae3ba3ebe4e10ab1d40ff12d95148da08148df8bf1a04c9254655"
},
"downloads": -1,
"filename": "kmeans1d-0.3.1-cp310-cp310-macosx_10_14_x86_64.whl",
"has_sig": false,
"md5_digest": "45f08a73535d4a7d0f657ffc95d4cc7f",
"packagetype": "bdist_wheel",
"python_version": "cp310",
"requires_python": ">=3.6",
"size": 16027,
"upload_time": "2021-10-10T04:59:54",
"upload_time_iso_8601": "2021-10-10T04:59:54.515810Z",
"url": "https://files.pythonhosted.org/packages/48/81/bf772068eda793b87a7d7fc189aa0cccc5fe7330235e5b90c7ad60247499/kmeans1d-0.3.1-cp310-cp310-macosx_10_14_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"md5": "6ff380d7df0f1b6fa2450f478a4aa75b",
"sha256": "62deac12e3dce7ea869f1b8742e43845d10226eac878cc00dd5bc88cc5dc3ff2"
},
"downloads": -1,
"filename": "kmeans1d-0.3.1-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl",
"has_sig": false,
"md5_digest": "6ff380d7df0f1b6fa2450f478a4aa75b",
"packagetype": "bdist_wheel",
"python_version": "cp310",
"requires_python": ">=3.6",
"size": 102401,
"upload_time": "2021-10-10T04:59:55",
"upload_time_iso_8601": "2021-10-10T04:59:55.746168Z",
"url": "https://files.pythonhosted.org/packages/59/b8/f2070570394b2303279d6c367f8dbccb5eed592ceebf35c719b9cbd74b6c/kmeans1d-0.3.1-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"md5": "1c279c57a3da9f7a004f8381c536b1ee",
"sha256": "22b052d7ee2eb6fc24d8391e3b1dcfb55335a4ed746a75cc17de7854cebf4da0"
},
"downloads": -1,
"filename": "kmeans1d-0.3.1-cp310-cp310-win_amd64.whl",
"has_sig": false,
"md5_digest": "1c279c57a3da9f7a004f8381c536b1ee",
"packagetype": "bdist_wheel",
"python_version": "cp310",
"requires_python": ">=3.6",
"size": 18021,
"upload_time": "2021-10-10T04:59:57",
"upload_time_iso_8601": "2021-10-10T04:59:57.401504Z",
"url": "https://files.pythonhosted.org/packages/1e/81/1444e88b846db05772fc999b3230896b5c6df5295c12ec06a1b8d7d7d09b/kmeans1d-0.3.1-cp310-cp310-win_amd64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"md5": "e292ca9cb4b93b19c3b17082d0358767",
"sha256": "e80bf6107ee86a3b33f6eb0e89b197f03b75d0a2f1a366cd00b6eb94801d76d1"
},
"downloads": -1,
"filename": "kmeans1d-0.3.1-cp36-cp36m-macosx_10_14_x86_64.whl",
"has_sig": false,
"md5_digest": "e292ca9cb4b93b19c3b17082d0358767",
"packagetype": "bdist_wheel",
"python_version": "cp36",
"requires_python": ">=3.6",
"size": 15802,
"upload_time": "2020-08-25T04:59:30",
"upload_time_iso_8601": "2020-08-25T04:59:30.975015Z",
"url": "https://files.pythonhosted.org/packages/92/c8/8883a62d0910e148163cc094c67298ea498ce15d7c2ed0801444273096c0/kmeans1d-0.3.1-cp36-cp36m-macosx_10_14_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"md5": "b5befcbadeac45bc32a8c876f805cc71",
"sha256": "7362144e0b7cbe92d116c88c4f25e85a872d9ca317bb5b22c8422f8131914599"
},
"downloads": -1,
"filename": "kmeans1d-0.3.1-cp36-cp36m-manylinux2014_x86_64.whl",
"has_sig": false,
"md5_digest": "b5befcbadeac45bc32a8c876f805cc71",
"packagetype": "bdist_wheel",
"python_version": "cp36",
"requires_python": ">=3.6",
"size": 93498,
"upload_time": "2020-08-25T04:59:32",
"upload_time_iso_8601": "2020-08-25T04:59:32.145132Z",
"url": "https://files.pythonhosted.org/packages/b7/3d/9154a7ba17176d14c6c0e46e2e8fd53cd9645616f5ed412ca36022ba0c95/kmeans1d-0.3.1-cp36-cp36m-manylinux2014_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"md5": "480e62f048815ecd327912db96046a4d",
"sha256": "09c6c97c3b63b5dc074c2b0a6fbc8f6e2dac252fd6bd4a7500b73fdfab5d5ef3"
},
"downloads": -1,
"filename": "kmeans1d-0.3.1-cp36-cp36m-win_amd64.whl",
"has_sig": false,
"md5_digest": "480e62f048815ecd327912db96046a4d",
"packagetype": "bdist_wheel",
"python_version": "cp36",
"requires_python": ">=3.6",
"size": 17929,
"upload_time": "2020-08-25T04:59:33",
"upload_time_iso_8601": "2020-08-25T04:59:33.317800Z",
"url": "https://files.pythonhosted.org/packages/e0/bc/30a15f109da401fa6ef30a1632d7f0ae23a73a85a26c7c535aaa756e2144/kmeans1d-0.3.1-cp36-cp36m-win_amd64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"md5": "b424f363dab0daaa645319bacbaa9d16",
"sha256": "80f476241037e7ff33767848a28ca8c587596828fee4031c58e1d2608ad8e357"
},
"downloads": -1,
"filename": "kmeans1d-0.3.1-cp37-cp37m-macosx_10_14_x86_64.whl",
"has_sig": false,
"md5_digest": "b424f363dab0daaa645319bacbaa9d16",
"packagetype": "bdist_wheel",
"python_version": "cp37",
"requires_python": ">=3.6",
"size": 15801,
"upload_time": "2020-08-25T04:59:34",
"upload_time_iso_8601": "2020-08-25T04:59:34.757824Z",
"url": "https://files.pythonhosted.org/packages/b8/15/ec7669817ab574bbcd3c9e31dbad07f929c4972abfed65d8f7f4b24d5340/kmeans1d-0.3.1-cp37-cp37m-macosx_10_14_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"md5": "14f9afdd94ea2fc4fd3ec89eed90ea0d",
"sha256": "1cbb7043c9e1282e5136620840d2e92dadae0747e776e96efd8460475ae289c2"
},
"downloads": -1,
"filename": "kmeans1d-0.3.1-cp37-cp37m-manylinux2014_x86_64.whl",
"has_sig": false,
"md5_digest": "14f9afdd94ea2fc4fd3ec89eed90ea0d",
"packagetype": "bdist_wheel",
"python_version": "cp37",
"requires_python": ">=3.6",
"size": 93469,
"upload_time": "2020-08-25T04:59:35",
"upload_time_iso_8601": "2020-08-25T04:59:35.809667Z",
"url": "https://files.pythonhosted.org/packages/f5/c5/c89bd26504c57f0b0c5e0dff7514e5e64d55dc9cc04d85e5ae112a9239b6/kmeans1d-0.3.1-cp37-cp37m-manylinux2014_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"md5": "31b0653f1b96ccd8f39b03ef52f54a77",
"sha256": "4953c04dfe811bc04d0898653d42dae404e42b1ad6dd70a63647bde96796a88e"
},
"downloads": -1,
"filename": "kmeans1d-0.3.1-cp37-cp37m-win_amd64.whl",
"has_sig": false,
"md5_digest": "31b0653f1b96ccd8f39b03ef52f54a77",
"packagetype": "bdist_wheel",
"python_version": "cp37",
"requires_python": ">=3.6",
"size": 17931,
"upload_time": "2020-08-25T04:59:37",
"upload_time_iso_8601": "2020-08-25T04:59:37.320873Z",
"url": "https://files.pythonhosted.org/packages/d0/8d/06edaec9ee4ce5199d69ea17991a772d376f688deadb460efe0d12aabb56/kmeans1d-0.3.1-cp37-cp37m-win_amd64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"md5": "5505be3f6bd5d4449f0a102d69b4c7af",
"sha256": "e765af47931aa197cf7734492ac1222f7c02cbf9e1f4824ae105f8b1ac733490"
},
"downloads": -1,
"filename": "kmeans1d-0.3.1-cp38-cp38-macosx_10_14_x86_64.whl",
"has_sig": false,
"md5_digest": "5505be3f6bd5d4449f0a102d69b4c7af",
"packagetype": "bdist_wheel",
"python_version": "cp38",
"requires_python": ">=3.6",
"size": 15796,
"upload_time": "2020-08-25T04:59:38",
"upload_time_iso_8601": "2020-08-25T04:59:38.291232Z",
"url": "https://files.pythonhosted.org/packages/ac/46/7c2f7648340f296d3d859173036dc842a10599efc900c9814098f12a2483/kmeans1d-0.3.1-cp38-cp38-macosx_10_14_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"md5": "856573a6f434b4e41f974183fd821b20",
"sha256": "5015efd3d6381e61b57da033d80ae64b8ea1e06a92efbc8afbcd473ccebc80e6"
},
"downloads": -1,
"filename": "kmeans1d-0.3.1-cp38-cp38-manylinux2014_x86_64.whl",
"has_sig": false,
"md5_digest": "856573a6f434b4e41f974183fd821b20",
"packagetype": "bdist_wheel",
"python_version": "cp38",
"requires_python": ">=3.6",
"size": 93624,
"upload_time": "2020-08-25T04:59:39",
"upload_time_iso_8601": "2020-08-25T04:59:39.695876Z",
"url": "https://files.pythonhosted.org/packages/44/89/774ea15cf99731335b46877425cf7ea0b1bf901d77c134f0fa17e1ccd296/kmeans1d-0.3.1-cp38-cp38-manylinux2014_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"md5": "841e483bf75e6de5c198562544c2c6a9",
"sha256": "b62e6d5648ba1eaf9ed012528fdbd179f67cfc70fb42b0d9cae19b2a36fb4ef9"
},
"downloads": -1,
"filename": "kmeans1d-0.3.1-cp38-cp38-win_amd64.whl",
"has_sig": false,
"md5_digest": "841e483bf75e6de5c198562544c2c6a9",
"packagetype": "bdist_wheel",
"python_version": "cp38",
"requires_python": ">=3.6",
"size": 17996,
"upload_time": "2020-08-25T04:59:41",
"upload_time_iso_8601": "2020-08-25T04:59:41.054067Z",
"url": "https://files.pythonhosted.org/packages/b3/8c/5b3c3341fe469fdba0ad1198721f8e7c5423e72948cedfbb0a6c69c1ae17/kmeans1d-0.3.1-cp38-cp38-win_amd64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"md5": "c4934d05c669cf833847fc0ea9c611b1",
"sha256": "06eb99f10bbd6e7056a829ed06678aa60e911c023f6c088c66623bdd42c1f389"
},
"downloads": -1,
"filename": "kmeans1d-0.3.1-cp39-cp39-macosx_10_14_x86_64.whl",
"has_sig": false,
"md5_digest": "c4934d05c669cf833847fc0ea9c611b1",
"packagetype": "bdist_wheel",
"python_version": "cp39",
"requires_python": ">=3.6",
"size": 16073,
"upload_time": "2020-12-07T20:11:30",
"upload_time_iso_8601": "2020-12-07T20:11:30.000224Z",
"url": "https://files.pythonhosted.org/packages/fd/36/7a70c62380083aa9e1c79e1a078ec0148e8e368f39bc11c6a2c70870e866/kmeans1d-0.3.1-cp39-cp39-macosx_10_14_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"md5": "70081ce99faad90ba3442a4ff168fc68",
"sha256": "da880390b1419f8f2c8d0c2d6cd1794a0613006bf9b347ca677394406b832687"
},
"downloads": -1,
"filename": "kmeans1d-0.3.1-cp39-cp39-manylinux2014_x86_64.whl",
"has_sig": false,
"md5_digest": "70081ce99faad90ba3442a4ff168fc68",
"packagetype": "bdist_wheel",
"python_version": "cp39",
"requires_python": ">=3.6",
"size": 93524,
"upload_time": "2020-12-07T20:11:31",
"upload_time_iso_8601": "2020-12-07T20:11:31.309550Z",
"url": "https://files.pythonhosted.org/packages/b0/1c/f9ee0a17a46ebb956ec541daab947cad1685a462279b49cd8d8e8960929a/kmeans1d-0.3.1-cp39-cp39-manylinux2014_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"md5": "896d9b0daf30268b40a4f858aed5142f",
"sha256": "1b1f00bb9dc59625b70967ec3ddd7472039968adae2b36a973a60d91257d3c4e"
},
"downloads": -1,
"filename": "kmeans1d-0.3.1-cp39-cp39-win_amd64.whl",
"has_sig": false,
"md5_digest": "896d9b0daf30268b40a4f858aed5142f",
"packagetype": "bdist_wheel",
"python_version": "cp39",
"requires_python": ">=3.6",
"size": 18000,
"upload_time": "2020-12-07T20:11:32",
"upload_time_iso_8601": "2020-12-07T20:11:32.492021Z",
"url": "https://files.pythonhosted.org/packages/0c/78/7378c9a497c23c2e9fd9409d201e6b110aa1d658fdb2b917bd639bd2a1fe/kmeans1d-0.3.1-cp39-cp39-win_amd64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"md5": "657551c5f07ef79ddaeded34ad8cf813",
"sha256": "dbe3604460968e3d31b743ac8f6167a48cdf1b8717c86e7fe2a93e117fdf1836"
},
"downloads": -1,
"filename": "kmeans1d-0.3.1.tar.gz",
"has_sig": false,
"md5_digest": "657551c5f07ef79ddaeded34ad8cf813",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.6",
"size": 6181,
"upload_time": "2020-08-24T04:15:23",
"upload_time_iso_8601": "2020-08-24T04:15:23.469031Z",
"url": "https://files.pythonhosted.org/packages/08/2f/5e51cd14e496220e1188f2319e4d757a8498f3d4321a2804089ed72c8786/kmeans1d-0.3.1.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2020-08-24 04:15:23",
"github": true,
"gitlab": false,
"bitbucket": false,
"github_user": "dstein64",
"github_project": "kmeans1d",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "kmeans1d"
}
JSON
