ndanielsen/same-size-k-means

A k-means variation that produces clusters of the same size utilizing the scikit-learn API and related utilities

Equal Groups K-Means Clustering

This is a k-means variation that produces clusters of the same size utilizing the scikit-learn Kmeans methods and associated utilities.

The same-size k-Means logic is the same as found in the Elki Same-size k-Means Variation tutorial.

https://elki-project.github.io/tutorial/same-size_k_means

Please note that this implementation only works in scikit-learn 17.X as later versions having breaking changes to this implementation. Also sparse matrices are not yet supported.

Usage

Use just like you would utilize the scikit-learn Kmeans class

from clustering.equal_groups import EqualGroupsKMeans

import numpy as np

X = np.array([[1, 2], [1, 4], [1, 0], [4, 2], [4, 4], [4, 0]])

clf = EqualGroupsKMeans(n_clusters=2)

clf.fit(X)

clf.labels_

Performance

The performance of this implementation is very slow. It is relatively quick if the number observations is less than 500.

Optimizations are readily accepted via pull-requests.

To Dos

• More test coverage
• Add support for sparse matrices
• Package for pypi
• Potentially speed up with cython
• scikit-learn 18.X implementation

same-size-k-means's Issues

Cluster size are not equal when I use the sparse matrix

My program can run successfully , but the result of my cluster size are not equal when I use the sparse matrix , the form below is the form of my sparse matrix :

(0,1) 0.23485
(0,2) 0.53663
......

Please tell me how to figure this problem ^^

Input contains NaN, infinity or a value too large for dtype('float64').

Sometimes after fitting the model, and applying transform method (or the fit_transform) we get the following error. If run again with everything the same, sometimes work and sometimes dont. I noticed that when I got this bug, the cluster_centers_ has NaNs in it and maybe its due to some convergence issue on the algorithm

OBS: beforehad I already checked if on the input of it has any Nans or inf values a alread treat it

Is the clustering result stable?

For the same input, is the clustering result given by this code stable? That is, whether the output result of multiple runs is the same clustering result.

Bug ?

Thanks for the repo. It fails funnily at times : see below

flat=np.random.random((64,9))
kmeans = EqualGroupsKMeans(n_clusters=3).fit(flat)
=> IndexError: index 62 is out of bounds for axis 0 with size 1

flat=np.random.random((6,2))
kmeans = EqualGroupsKMeans(n_clusters=3).fit(flat)
=> no error!!!

Not really same size k-means

Hi,

I am facing an issue, where the clusters are far different in size.
Please find my dataset and code enclosed.
For the initial centroid initialization, I am using kmeans++.
All of the requirements from requirements.txt are fulfilled.

Here is the output:
Cluster 1 : 13
Cluster 2 : 13
Cluster 3 : 10
Cluster 4 : 13
Cluster 5 : 12
Cluster 6 : 13
Cluster 7 : 13
Cluster 8 : 13
Cluster 9 : 0
Cluster 10 : 0
Total : 100

Is this a normal behavior or is it a bug?
For my case the cluster size is crucial, so I need the sizes to differ in max 1-2 objects.
Is this possible?
Can a more balanced sizing be achieved?

Thanks in advance!

dataset and code.zip

Error raised

Hi,

The following error keep being raised:

/Users/------/Documents/------/equal_groups.py:498: RuntimeWarning: overflow encountered in true_divide
  centers = _k_means._centers_dense(X, sample_weight, labels, n_clusters, distances)
/anaconda3/envs/env/lib/python3.7/site-packages/numpy/core/fromnumeric.py:86: RuntimeWarning: overflow encountered in reduce
  return ufunc.reduce(obj, axis, dtype, out, **passkwargs)
/anaconda3/envs/env/lib/python3.7/site-packages/numpy/core/fromnumeric.py:86: RuntimeWarning: invalid value encountered in reduce
  return ufunc.reduce(obj, axis, dtype, out, **passkwargs)
/anaconda3/envs/env/lib/python3.7/site-packages/sklearn/metrics/pairwise.py:273: RuntimeWarning: overflow encountered in multiply
  distances = - 2 * safe_sparse_dot(X, Y.T, dense_output=True)
/anaconda3/envs/env/lib/python3.7/site-packages/sklearn/metrics/pairwise.py:274: RuntimeWarning: invalid value encountered in add
  distances += XX

Any idea how to solve it? :)

IndexError in sklearn.cluster._k_means._centers_dense

Hi guys, thank you for a great solution, I was trying to use it for my dataset of 1092 points and encountered the following error:

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/code/Same-Size-K-Means/clustering/equal_groups.py", line 171, in fit
    n_jobs=self.n_jobs)
  File "/code/Same-Size-K-Means/clustering/equal_groups.py", line 386, in k_means
    x_squared_norms=x_squared_norms, random_state=random_state, sample_weight=sample_weight)
  File "/code/Same-Size-K-Means/clustering/equal_groups.py", line 504, in _kmeans_single
    centers = _k_means._centers_dense(X, sample_weight, labels, n_clusters, distances)
  File "sklearn/cluster/_k_means.pyx", line 330, in sklearn.cluster._k_means._centers_dense (sklearn/cluster/_k_means.c:11044)
IndexError: index 990 is out of bounds for axis 0 with size 1

Could you help me resolve it?

Steps to reproduce:

1. Use docker image with scikit-learn (version 0.20.1 is currently stated in the requirements file): docker run --rm -it smizy/scikit-learn:0.20.1-alpine sh
2. Inside the docker container:
3. apk add git && git clone https://github.com/ndanielsen/Same-Size-K-Means.git && cd Same-Size-K-Means
4. python
5. Inside Python shell:
   1. from clustering.equal_groups import EqualGroupsKMeans
   2. import numpy as np
   3. X = …, prepare data, see below
   4. clf = EqualGroupsKMeans(n_clusters=X.shape[0] // 12) — each cluster has to have size 12.
   5. clf.fit(X) — this causes the above mentioned error.

Here is the data:

X = np.array([[10.96028444,3.2149,9.57],[10.95426311,3.2139,9.328],[11.05052533,3.2142,9.526],[10.83867378,3.2145,9.861],[10.74038933,3.2149,9.38],[10.82460622,3.2145,9.59],[10.87308,3.2139,9.364],[10.86195111,3.2142,9.37],[10.905293,3.2139,9.665],[10.787405,3.2133,9.336],[10.909092,3.2133,9.572],[10.875735,3.2114,9.361],[10.985459,3.213,9.348],[10.830052,3.2118,9.358],[10.621248,3.2152,9.283],[10.97302,3.2158,9.64],[10.896704,3.2155,9.595],[10.87915022,3.1969,9.483],[10.80988356,3.2139,9.57],[11.11480089,3.2149,9.267],[11.11233422,3.2136,9.449],[10.99250844,3.1959,9.364],[10.95529956,3.2142,9.347],[10.95687644,3.2152,9.284],[10.79412978,3.2149,9.613],[10.91260267,3.1938,9.25],[10.93472533,3.213,9.097],[10.89810222,3.2133,9.492],[10.99407556,3.213,9.77],[10.84041867,3.2133,9.153],[10.88539111,3.2111,9.586],[10.88757333,3.2118,9.546],[10.69065244,3.2155,9.070],[10.63244622,3.2167,9.636],[10.68687111,3.2161,9.714],[10.67953867,3.2145,9.681],[10.65424889,3.2167,9.605],[10.72436978,3.2161,9.82],[10.62482667,3.2149,9.346],[10.81533156,3.213,9.32],[10.635184,3.2142,9.501],[10.68521689,3.2133,9.233],[10.73347378,3.2124,9.494],[10.69879467,3.213,9.472],[10.89282133,3.2127,9.59],[10.86379644,3.2142,9.093],[10.76518044,3.2145,9.635],[10.81013156,3.2133,9.667],[10.895136,3.209,9.465],[10.73784711,3.2152,9.644],[10.89956089,3.2136,9.587],[10.90604089,3.2149,9.328],[10.79766756,3.2102,9.457],[10.77603111,3.2142,9.734],[10.74956,3.2149,9.614],[10.82417422,3.2152,9.242],[10.76885778,3.2124,9.235],[10.69138667,3.2139,9.329],[10.74858222,3.2111,9.314],[10.84456444,3.209,9.189],[10.84613333,3.2139,9.64],[10.83802844,3.2155,9.576],[10.68917511,3.2142,9.266],[10.753968,3.2145,9.496],[10.66664533,3.2158,9.32],[10.64808178,3.2145,9.345],[10.66048089,3.2145,9.673],[10.71777956,3.2145,9.681],[10.67583467,3.2152,9.44],[10.77796356,3.2149,9.201],[10.84499022,3.2152,9.388],[10.92894222,3.2142,9.577],[10.79465422,3.2167,9.715],[10.74447289,3.2149,9.206],[10.40968889,3.2127,9.38],[10.62292622,3.2167,9.509],[10.94600533,3.2018,9.7101],[10.535168,3.2155,9.392],[10.56211022,3.218,9.413],[10.575528,3.2155,9.553],[10.644848,3.213,9.387],[10.732648,3.2152,9.345],[10.69985689,3.2145,9.579],[10.67368444,3.2149,9.12],[10.67696444,3.2142,9.406],[10.95435378,3.2139,9.408],[10.73104089,3.2127,9.707],[10.64029867,3.2152,9.776],[10.84933156,3.213,9.301],[11.013472,3.2133,9.8],[11.12312711,3.213,9.096],[11.08705244,3.2127,9.267],[11.02759911,3.2149,9.176],[10.95539378,3.2149,9.679],[10.81568444,3.2139,9.672],[10.94879022,3.2158,9.451],[10.63380089,3.208,9.542],[10.45305778,3.217,9.361],[10.61649067,3.213,9.337],[10.69108089,3.2152,9.664],[10.86590756,3.2149,9.482],[10.56538489,3.2145,9.709],[10.72236089,3.2158,9.424],[10.61661689,3.2136,9.57],[10.80174578,3.2059,9.329],[10.879848,3.2127,9.181],[10.85956622,3.2133,9.303],[10.94561333,3.2127,9.456],[10.85168356,3.2124,9.435],[10.75878044,3.2136,9.729],[10.86533333,3.2142,8.991],[11.13199022,3.2145,9.39],[10.60729689,3.2111,9.808],[10.55780533,3.2139,9.558],[10.63920178,3.2145,9.448],[10.73741156,3.2133,9.37],[10.65642667,3.2136,9.182],[10.70298489,3.2096,9.511],[10.633376,3.2142,9.682],[10.67414311,3.2145,9.551],[11.359616,3.209,9.226],[11.136232,3.2071,9.205],[11.31781511,3.2105,9.13],[11.24415289,3.2096,9.62],[11.23117422,3.2136,9.667],[11.24832533,3.2118,9.248],[11.06003111,3.1981,9.377],[11.167744,3.2145,9.745],[10.840248,3.2121,9.551],[10.79541333,3.2108,9.214],[10.82109511,3.2133,9.284],[10.84460889,3.2145,9.431],[10.85002311,3.213,9.605],[10.79989689,3.2142,9.467],[10.77602133,3.2145,9.451],[10.82065956,3.2149,9.079],[10.87194489,3.2152,9.407],[10.80938578,3.213,9.017],[10.75796622,3.2142,9.08],[10.84509333,3.2124,9.395],[11.01297244,3.2149,9.442],[10.90067111,3.2145,9.651],[10.86627022,3.2145,9.299],[10.87840089,3.2145,9.41],[10.82096533,3.2142,9.361],[10.854224,3.2155,9.499],[10.76855911,3.2149,9.267],[10.898096,3.2121,9.43],[10.83293333,3.2139,9.654],[10.80949422,3.2145,9.237],[10.75846222,3.2142,9.354],[10.85486222,3.2133,9.484],[10.77263289,3.2124,9.338],[10.70087111,3.2145,9.423],[10.80806667,3.2124,9.08],[10.89859556,3.2136,9.378],[10.96691111,3.2139,9.537],[10.82141333,3.2149,9.471],[10.65455111,3.2133,9.241],[10.859752,3.2139,9.442],[10.83871911,3.2145,9.595],[10.80769778,3.2158,9.258],[10.87930489,3.209,9.664],[10.78280889,3.2139,9.525],[10.80500356,3.2149,9.329],[10.809632,3.2145,9.425],[10.84289333,3.2152,9.646],[10.86771378,3.2145,9.234],[10.701728,3.2133,9.215],[10.79563467,3.2139,9.291],[10.82147733,3.2139,9.089],[10.75580889,3.2145,9.405],[10.35902667,3.2127,9.192],[10.75025778,3.2198,9.211],[10.82972622,3.2155,9.472],[10.89028889,3.2133,9.315],[10.75562222,3.2136,9.533],[10.67033333,3.2152,9.156],[10.631672,3.2149,9.456],[10.697328,3.2139,9.542],[10.80464178,3.2145,9.457],[10.74501778,3.2149,9.322],[10.84319644,3.2145,9.371],[10.62382311,3.2158,9.526],[10.83743289,3.2043,9.338],[10.74027467,3.2133,9.455],[10.75102933,3.2139,9.244],[10.89068889,3.2149,9.222],[10.99084889,3.213,9.209],[10.79195111,3.2142,9.031],[10.739904,3.2149,9.499],[10.73413244,3.2127,9.426],[10.68378667,3.2149,9.431],[10.71135022,3.2139,9.397],[10.78112711,3.2127,9.509],[10.79761333,3.2105,9.75],[10.75938489,3.2034,9.51],[10.75830667,3.2145,9.536],[10.86767111,3.1814,9.465],[10.76303644,3.2127,9.551],[10.77658222,3.2111,9.157],[10.73163644,3.2136,9.274],[10.84100444,3.2142,9.417],[11.00464533,3.2152,9.516],[11.10975911,3.2108,9.176],[11.07155644,3.2105,9.429],[10.78489244,3.2118,9.249],[10.724944,3.1888,9.607],[10.62243022,3.2145,9.698],[10.65296889,3.2152,9.628],[10.83979111,3.2145,9.629],[10.80965333,3.2158,9.697],[10.74902933,3.2139,9.682],[10.75151911,3.2133,9.528],[10.67991022,3.2155,9.535],[10.69885689,3.2142,9.329],[10.76719022,3.2155,9.449],[10.74338844,3.2133,9.181],[10.83557689,3.2145,9.667],[10.84684267,3.2139,9.491],[10.91728,3.2161,9.66],[10.86929244,3.2149,9.446],[10.81520978,3.2142,9.299],[10.821752,3.2158,9.304],[10.70183644,3.2152,9.484],[10.74994489,3.2139,9.508],[10.74360356,3.2158,9.665],[10.85768089,3.2145,9.172],[10.86100622,3.2145,9.819],[10.79702933,3.2149,9.458],[10.76424089,3.2152,9.451],[10.77678933,3.2155,9.69],[10.789088,3.2145,9.485],[10.47040711,3.2145,9.517],[10.65789333,3.2127,9.4],[10.59507644,3.2145,9.637],[10.58991911,3.2145,9.382],[10.61494667,3.2142,9.548],[10.68064711,3.2136,9.455],[10.62981244,3.2155,9.668],[10.67800356,3.2009,9.465],[10.77952978,3.2152,9.645],[10.73259911,3.213,9.415],[10.73639911,3.2149,9.628],[10.88965156,3.2145,9.518],[10.81355556,3.2127,9.401],[10.78407022,3.2142,9.397],[10.759592,3.2025,9.542],[10.72380889,3.2124,9.682],[10.87234578,3.2124,9.284],[10.79386222,3.208,9.631],[10.92843378,3.2124,9.447],[10.93758311,3.2065,9.599],[11.006568,3.2105,9.265],[10.84356267,3.2009,9.619],[10.70282311,3.2028,9.468],[11.03605778,3.2136,9.301],[10.96230311,3.2105,9.345],[11.08654756,3.2124,9.071],[10.99814756,3.2149,9.206],[10.92855467,3.2145,9.165],[10.88712444,3.2139,9.503],[11.02688356,3.213,9.494],[11.29518044,3.2136,9.501],[10.81121244,3.2114,9.226],[10.97814133,3.1975,9.14],[11.04703111,3.213,9.15],[11.1822,3.2127,9.492],[11.10048178,3.213,9.201],[10.99449778,3.2142,9.412],[10.91383911,3.2096,9.636],[10.95871111,3.2142,8.995],[10.78531911,3.2152,9.148],[10.71579378,3.2142,9.267],[10.86672089,3.2139,9.242],[10.85933689,3.2145,9.689],[10.87522756,3.2142,9.769],[10.81571111,3.2152,9.683],[10.93892444,3.2149,9.502],[10.94324889,3.2155,9.551],[10.69299378,3.2155,9.707],[10.76744711,3.2152,9.57],[10.90104178,3.2133,9.4],[10.87562756,3.2164,9.767],[11.043752,3.2127,9.426],[10.92608444,3.2145,9.367],[10.64397244,3.2136,9.549],[10.90996267,3.2139,9.401],[10.636448,3.2142,9.731],[10.619112,3.2142,9.628],[10.72140889,3.2152,9.837],[10.72149333,3.1975,9.620],[10.865688,3.2105,9.346],[10.86514489,3.2133,9.553],[10.76423822,3.2108,9.786],[10.856392,3.2114,9.242],[10.60428533,3.2139,9.785],[10.64384178,3.2139,9.595],[10.64081689,3.2114,9.442],[10.872672,3.2111,9.653],[10.91905867,3.2139,9.685],[10.64693511,3.2102,9.893],[10.74336356,3.2124,9.397],[10.89230044,3.2149,9.488],[10.62013244,3.2158,9.156],[10.72011467,3.2155,9.353],[10.66351822,3.2167,9.595],[10.746064,3.2158,9.242],[10.70565778,3.2161,9.880],[10.73680444,3.2127,9.631],[10.79850844,3.2152,9.622],[10.75295022,3.2139,9.637],[10.73190667,3.2155,9.646],[10.75611556,3.2167,9.473],[10.98543911,3.2139,9.228],[10.79179911,3.2136,9.731],[10.89586578,3.2145,9.590],[10.955272,3.2142,9.507],[10.616408,3.2114,9.472],[11.20109156,3.2145,9.331],[10.37548356,3.2192,9.129],[10.51767822,3.2145,9.541],[10.35038311,3.2211,9.587],[10.69038756,3.2139,9.406],[10.67267378,3.2142,9.199],[10.80026222,3.2152,9.348],[10.84134756,3.2142,9.310],[11.19948267,3.2149,9.484],[10.53145689,3.2192,9.596],[10.487832,3.2149,9.155],[10.5528,3.2139,9.442],[10.68541867,3.2139,9.500],[10.76190667,3.2139,9.849],[10.81270133,3.2142,9.351],[10.76195467,3.2149,9.455],[10.71215289,3.2139,9.537],[10.48007644,3.218,9.275],[10.44868533,3.2173,9.827],[10.60799022,3.2152,9.362],[10.69118311,3.2145,10.075],[10.66745778,3.2167,9.310],[10.68742578,3.2152,9.487],[10.76744533,3.2149,9.466],[10.71599644,3.2152,9.629],[10.53099556,3.2164,9.371],[10.51221867,3.2152,9.258],[10.67493156,3.2155,9.089],[10.62780089,3.2142,9.299],[10.76881689,3.2149,9.467],[10.75251911,3.2149,9.376],[10.65357689,3.2142,9.462],[10.79912356,3.2145,9.229],[10.44356356,3.2164,9.587],[10.67290222,3.2161,9.447],[10.80576889,3.2155,9.387],[10.80683733,3.2152,9.386],[10.708752,3.2158,9.415],[10.84044978,3.2152,9.270],[10.70607111,3.2142,9.449],[10.722128,3.2149,9.456],[10.43891467,3.2161,9.560],[10.49500089,3.217,9.095],[10.79514311,3.2155,9.364],[10.68200889,3.2136,9.197],[10.76484,3.2164,9.553],[10.57166933,3.2155,9.531],[10.67945867,3.2167,9.783],[10.80383822,3.2149,9.692],[10.55116978,3.2173,9.665],[10.49416444,3.2164,9.577],[10.50789333,3.2167,9.750],[10.52252267,3.2158,9.492],[10.62215556,3.2149,9.595],[10.637768,3.2145,9.417],[10.901968,3.2142,9.149],[10.63729778,3.2145,9.422],[10.50656089,3.2167,9.785],[10.69731022,3.2145,9.299],[10.64056178,3.2152,9.744],[10.95361244,3.2149,9.516],[10.88884889,3.2145,9.639],[10.80069422,3.2142,9.186],[10.77149511,3.2149,9.376],[10.79296533,3.2142,9.365],[10.66731111,3.2158,9.870],[10.57991644,3.2161,9.714],[10.65575289,3.2155,9.801],[10.70405244,3.2152,9.300],[10.78213778,3.2152,9.605],[10.66875467,3.2127,9.623],[10.73638756,3.2133,9.544],[10.75359111,3.2145,9.492],[10.57206756,3.2149,9.604],[10.59298133,3.2149,9.689],[10.73713422,3.2136,9.302],[10.672608,3.217,9.730],[10.75648089,3.2127,9.545],[10.65842578,3.2127,9.576],[10.68630756,3.2145,9.697],[10.81335556,3.2155,9.520],[10.62839911,3.2145,9.501],[10.83693244,3.2121,9.783],[10.64759111,3.2133,9.559],[10.92110756,3.2118,9.447],[10.77723644,3.2136,9.251],[10.71336,3.2139,9.417],[10.745744,3.2124,9.208],[10.71794311,3.2105,9.723],[10.337808,3.2158,9.432],[10.389472,3.2149,9.714],[10.46381867,3.2133,9.150],[10.512368,3.2139,9.775],[10.62709867,3.2158,9.898],[10.61141867,3.2149,9.671],[10.55889067,3.2145,9.611],[10.64350578,3.2158,9.787],[10.62823911,3.2145,9.363],[10.61989156,3.2136,9.722],[10.64113867,3.2136,9.776],[10.78760178,3.213,9.817],[10.77411733,3.2111,9.707],[10.89368711,3.2139,9.832],[10.72132,3.213,9.552],[10.73799022,3.2142,9.792],[10.57569778,3.2149,9.502],[10.67772622,3.2155,9.628],[10.79775289,3.2152,9.734],[10.67783111,3.213,9.447],[10.88028089,3.2139,9.39],[10.54700533,3.2152,9.824],[10.60764089,3.2127,9.414],[10.81916356,3.2133,9.143],[10.57603733,3.2136,9.517],[10.74569867,3.2152,9.621],[10.80672356,3.2145,9.492],[10.92368711,3.1925,9.431],[10.77732622,3.2059,9.379],[10.83373867,3.2096,9.512],[10.74977867,3.2083,9.666],[10.98290133,3.2136,9.235],[10.73513956,3.2136,9.552],[10.83817778,3.2142,9.484],[10.79489956,3.2133,9.700],[10.90192711,3.2108,9.672],[11.038872,3.2127,9.512],[10.82752533,3.2133,9.815],[11.00999022,3.213,9.422],[10.95055289,3.2077,9.280],[10.69447644,3.2155,9.398],[10.77072711,3.2145,9.422],[10.64540889,3.2021,9.596],[10.78038222,3.2093,9.673],[10.73884089,3.2068,9.666],[10.76994578,3.2152,9.640],[10.85936,3.213,9.380],[10.73018844,3.2142,9.776],[10.65945867,3.2139,9.501],[10.74778222,3.2124,9.156],[10.85079111,3.2136,9.158],[10.96637422,3.2114,9.387],[10.86816178,3.2102,9.323],[10.740232,3.2142,9.282],[10.91329333,3.2149,9.405],[11.05871022,3.213,9.202],[10.66038756,3.2152,9.629],[10.84914311,3.2124,9.474],[10.77939911,3.2083,9.260],[10.90865956,3.2149,9.817],[10.77812533,3.2114,9.639],[10.89901778,3.2127,9.726],[11.07939022,3.2118,9.365],[10.886928,3.213,9.322],[10.78694311,3.2152,9.441],[10.89914222,3.2133,9.501],[11.03582311,3.2136,9.389],[10.88630133,3.2136,9.472],[10.981792,3.213,9.496],[10.880992,3.2102,9.635],[10.890768,3.2145,9.775],[10.89256889,3.2121,9.488],[10.85690133,3.2155,9.346],[10.79497244,3.2139,9.422],[11.2334,3.2105,9.638],[10.95213422,3.2127,9.776],[11.03523111,3.2077,9.613],[10.96489244,3.2118,9.348],[10.98420978,3.2149,9.310],[10.87306222,3.2105,9.638],[10.59831822,3.2142,9.793],[10.56945956,3.2108,9.517],[10.60906311,3.2127,9.408],[10.66462756,3.2139,9.395],[10.86062044,3.213,9.132],[10.75059022,3.1959,9.737],[10.71163467,3.2136,9.627],[10.78932444,3.2145,10.124],[10.94668978,3.1987,9.535],[10.98905778,3.2127,9.510],[10.70786489,3.1801,9.424],[11.08786489,3.1773,9.551],[11.0514,3.2111,9.191],[11.004128,3.1736,9.401],[11.04140356,3.1811,9.754],[10.99352444,3.2012,9.638],[10.93830667,3.2133,9.527],[10.83400178,3.2037,9.312],[10.83605689,3.2065,9.562],[10.91385422,3.1959,9.587],[11.10268,3.2121,9.615],[10.93567556,3.2056,9.412],[10.86350044,3.1783,9.111],[10.97673422,3.2077,9.521],[10.62532622,3.2152,9.645],[10.82510044,3.2152,9.628],[10.81017867,3.2158,9.285],[10.71121244,3.2149,9.362],[10.747272,3.2102,9.675],[10.66917511,3.2105,9.581],[10.73804267,3.2145,9.528],[10.69882844,3.213,9.519],[10.50773333,3.2167,9.604],[10.58402667,3.2136,9.484],[10.768,3.2133,9.073],[10.84398044,3.2149,9.301],[10.88300356,3.2133,9.848],[10.67777067,3.2149,9.585],[10.82215289,3.2142,9.688],[10.73832444,3.2145,9.660],[10.76423467,3.2155,9.801],[10.74702044,3.2142,9.672],[10.83949689,3.2142,9.732],[10.74713067,3.2105,9.620],[10.85797422,3.2142,9.683],[10.83990133,3.2136,9.779],[10.72000533,3.2043,9.640],[10.90339111,3.2136,9.794],[10.77957333,3.2145,9.983],[10.82912978,3.2118,9.656],[10.91697244,3.2133,9.590],[10.88240089,3.2118,9.516],[10.94340978,3.2124,9.632],[10.90788,3.2059,9.876],[10.84594844,3.2133,9.595],[10.91919822,3.204,9.763],[10.57648356,3.2155,9.888],[10.86711822,3.2145,9.613],[10.871424,3.1935,9.424],[10.860176,3.2031,9.440],[10.82044,3.2145,9.905],[10.70783822,3.2121,9.443],[10.817744,3.2114,9.365],[10.96910756,3.1938,9.630],[10.86270311,3.2155,9.441],[10.75553867,3.2136,9.801],[10.81788978,3.2105,9.709],[11.0236,3.2142,9.501],[11.031984,3.2124,9.582],[10.98782044,3.2074,9.274],[10.87791911,3.208,9.077],[10.89748356,3.2121,9.574],[10.77116,3.2152,9.543],[10.78197778,3.2133,9.871],[10.91737422,3.2149,9.743],[10.81258222,3.2139,9.415],[10.90839822,3.1956,9.432],[10.87205333,3.2121,9.649],[10.93827111,3.2149,9.484],[10.98652089,3.2145,9.638],[10.80276089,3.2152,9.658],[10.81918311,3.2149,9.759],[10.85547556,3.2139,9.426],[11.15095822,3.2127,9.559],[11.08256178,3.2149,9.710],[10.95578844,3.2155,10.057],[10.81239644,3.2102,9.551],[10.99205867,3.2142,9.427],[10.51702222,3.2145,10.162],[10.62269689,3.2093,9.964],[10.62844356,3.2139,9.784],[10.63038311,3.2145,9.320],[10.703552,3.2152,9.527],[10.71558222,3.2142,9.976],[10.68443556,3.2133,10.250],[10.65450222,3.2139,9.723],[10.57228978,3.2161,10.207],[10.59390578,3.2142,9.320],[10.77814933,3.2149,10.397],[10.85233778,3.2152,9.681],[10.92855289,3.2155,9.685],[10.76620978,3.2145,9.635],[10.76561333,3.2127,10.136],[10.89830044,3.2161,11.140],[10.71708444,3.2149,9.518],[10.71469156,3.2111,9.828],[10.82511556,3.209,9.629],[10.84620089,3.2099,9.156],[10.82797778,3.1808,9.321],[10.82076444,3.2121,9.648],[10.87540533,3.2139,9.322],[10.78877511,3.2077,9.724],[10.72107644,3.2142,9.724],[10.61474578,3.2118,9.542],[10.80858756,3.2114,9.262],[10.77443733,3.213,9.587],[10.72275644,3.2136,9.640],[10.86783822,3.213,9.585],[10.852952,3.2105,9.664],[10.84690133,3.2127,9.316],[10.80449689,3.2152,9.776],[10.71633333,3.2145,9.629],[10.79593956,3.1873,9.621],[10.80836356,3.2145,9.656],[10.933712,3.2149,9.924],[10.90735022,3.2136,9.442],[10.76639022,3.2145,9.504],[10.86586133,3.2139,9.261],[10.668992,3.2149,10.070],[10.642336,3.2124,9.509],[10.84760533,3.2139,9.795],[10.91560978,3.2127,9.447],[10.87062933,3.2139,10.099],[10.91632533,3.2139,9.712],[10.63913956,3.1997,9.491],[10.94310578,3.2142,9.537],[10.79372978,3.2158,9.542],[10.64747378,3.2136,9.474],[10.860976,3.2149,9.551],[10.890128,3.2111,9.809],[10.83485689,3.213,10.337],[10.87723378,3.204,9.771],[10.97283467,3.2114,9.648],[10.93697778,3.2145,9.227],[10.80158667,3.2152,9.744],[10.93556356,3.2142,9.362],[10.9434,3.213,9.709],[10.84966756,3.2152,10.017],[11.06359822,3.2133,9.443],[10.91774933,3.2133,9.298],[10.86157422,3.2105,9.742],[10.90596533,3.2114,9.402],[10.64355733,3.2158,9.501],[10.711448,3.2161,9.250],[10.66215822,3.2155,9.595],[10.83432444,3.2139,9.465],[10.69281867,3.213,9.449],[10.79299378,3.2121,9.676],[10.74346578,3.2124,9.302],[10.74797422,3.2145,9.706],[10.507648,3.2124,9.302],[10.45126133,3.2077,9.104],[10.42033333,3.2145,9.330],[10.67639111,3.2133,9.542],[10.79097956,3.2149,9.763],[10.64388622,3.2139,9.728],[10.558256,3.2018,9.274],[10.67894044,3.2136,9.435],[10.68507378,3.2149,9.863],[10.75761689,3.2114,9.621],[10.81980889,3.2114,9.768],[10.82228533,3.2133,9.267],[10.87512978,3.2136,9.630],[10.84581867,3.2145,9.401],[11.00710222,3.2145,9.716],[10.74432978,3.2121,9.941],[10.84727822,3.2149,9.372],[10.82851911,3.2108,9.742],[10.87497867,3.2127,9.917],[10.98257956,3.2105,9.826],[10.90667111,3.2139,10.054],[10.81749511,3.2108,9.790],[10.83884533,3.2025,9.783],[10.91212356,3.2145,9.176],[10.87407911,3.2068,10.104],[10.77906489,3.2155,9.940],[10.88324978,3.2127,9.776],[10.94899556,3.2149,9.845],[10.76909689,3.2133,9.914],[10.78176978,3.213,9.632],[10.85901156,3.2145,9.561],[10.72389689,3.2105,9.794],[10.61562489,3.2149,9.785],[10.69453333,3.213,9.570],[10.87216889,3.2127,9.787],[10.89398667,3.2124,9.990],[10.988048,3.2105,9.849],[10.72652622,3.2136,10.705],[10.772048,3.2093,9.999],[10.97454044,3.213,9.865],[10.69799111,3.2127,9.465],[10.72767289,3.2139,9.493],[10.84833333,3.2121,9.199],[10.88315733,3.2133,9.501],[11.00365689,3.2139,9.519],[10.97017422,3.2124,9.373],[10.83552356,3.2127,9.409],[11.061648,3.213,9.733],[10.77375556,3.2139,10.027],[10.8656,3.2133,9.448],[10.85765333,3.1866,9.503],[10.94957689,3.2093,10.076],[10.89989244,3.2087,9.899],[10.73831822,3.2118,9.954],[11.00355556,3.2136,9.447],[10.931312,3.2142,9.779],[10.60006667,3.2158,9.510],[10.61396978,3.2152,9.613],[10.50477867,3.2142,9.449],[10.830688,3.2133,9.817],[10.666232,3.2114,9.838],[10.67648889,3.2142,9.451],[10.633424,3.2145,9.529],[10.56904444,3.2028,9.494],[10.73922844,3.2145,9.285],[10.70258311,3.2124,9.484],[10.86380356,3.213,9.794],[10.90395467,3.2133,9.518],[10.95375289,3.1888,9.201],[10.85326667,3.2145,9.421],[10.78870578,3.2093,9.672],[10.82146844,3.2111,9.591],[10.721288,3.2121,10.077],[10.84366756,3.2139,9.829],[10.93352533,3.2139,9.493],[10.94072356,3.2145,9.559],[10.86467022,3.1984,9.363],[10.83479556,3.2071,9.754],[10.85483378,3.2149,9.622],[10.89481244,3.2142,9.699],[10.79826489,3.2102,9.958],[10.78801867,3.2111,9.587],[10.64192889,3.2127,10.520],[10.88292,3.2139,10.190],[10.93267111,3.2108,9.762],[10.87155467,3.213,9.376],[10.858752,3.213,9.516],[10.99308889,3.2127,9.908],[10.567992,3.2158,9.829],[10.75346578,3.2152,9.267],[10.56870222,3.2074,9.345],[10.65139644,3.2118,9.612],[10.781352,3.2149,9.639],[10.67002489,3.2121,9.389],[10.54931911,3.2139,9.762],[10.55646133,3.2012,9.284],[10.67834756,3.2161,9.441],[10.69052356,3.213,9.665],[10.78397422,3.2139,9.761],[11.03883911,3.2136,9.206],[10.93643022,3.2114,9.504],[10.88946756,3.2133,9.248],[10.814712,3.2111,9.205],[10.91854222,3.2136,9.348],[10.72662756,3.2142,9.829],[10.73086667,3.2114,10.010],[10.83085156,3.2139,9.551],[10.87401689,3.2114,9.731],[10.91981689,3.2065,10.079],[10.93720356,3.1792,9.537],[10.96368978,3.2142,9.442],[10.90901778,3.1739,9.658],[10.73274311,3.213,10.035],[10.82757156,3.2111,9.579],[10.79488978,3.2118,9.667],[10.87572978,3.209,10.223],[11.06738667,3.2139,9.255],[10.8744,3.213,9.556],[10.82283467,3.2062,9.861],[10.99480978,3.2108,9.710],[10.70512178,3.2149,9.699],[10.66239644,3.2155,9.697],[10.80201333,3.2149,9.732],[10.81823556,3.2127,9.845],[10.79346489,3.2121,9.699],[10.69534756,3.2121,9.323],[10.80726044,3.2071,9.716],[10.80178222,3.2121,9.933],[10.84039289,3.2139,9.916],[10.64348,3.2136,9.854],[10.81618667,3.2136,9.401],[10.77690133,3.209,9.518],[10.899984,3.2149,9.796],[10.73704444,3.2127,9.971],[10.77460622,3.2152,9.730],[10.84765333,3.2118,9.919],[10.67545956,3.2152,9.723],[10.71872978,3.2139,9.595],[10.72263644,3.213,9.888],[10.83207111,3.2087,9.879],[10.74792356,3.204,9.675],[10.69827911,3.2102,9.684],[10.62971733,3.2142,9.088],[10.76834222,3.2133,9.916],[10.84329867,3.2152,9.465],[10.70547111,3.2139,9.879],[10.79615644,3.2136,9.303],[10.83495911,3.213,9.845],[10.94881067,3.2133,9.562],[10.80140267,3.2121,9.404],[10.872224,3.2145,9.688],[10.86933511,3.2161,9.908],[10.33241778,3.2152,9.698],[10.721776,3.2142,9.206],[10.81493156,3.213,9.517],[10.80871644,3.2136,9.777],[10.39883556,3.2142,9.433],[10.75765156,3.213,9.786],[10.80697778,3.2149,9.656],[10.51780267,3.2149,9.888],[10.52327111,3.2124,9.570],[10.73830133,3.2133,9.364],[10.73045244,3.2152,9.611],[10.76106311,3.2127,9.631],[10.63922133,3.2121,10.006],[10.820992,3.2142,9.180],[10.80665244,3.2142,9.693],[10.92962578,3.2142,9.81],[10.84452267,3.2015,9.58],[10.84308533,3.2034,9.699],[11.04148089,3.2118,9.509],[10.84380889,3.2105,9.51],[10.84328444,3.2136,9.71],[11.11467644,3.2093,9.741],[11.146048,3.2142,9.63],[10.669008,3.2139,9.51],[10.66494044,3.2133,9.379],[10.71417689,3.2118,9.38],[10.93262933,3.1835,9.353],[11.02334311,3.2059,9.237],[10.82424533,3.2145,9.696],[10.80994578,3.2025,9.508],[10.94755556,3.213,9.754],[10.54894933,3.2167,9.448],[10.79564267,3.2133,9.661],[10.80433422,3.2149,10.018],[10.90209956,3.2136,9.697],[10.83531111,3.2145,9.285],[10.779424,3.2124,9.623],[10.95002667,3.2149,9.302],[10.88122667,3.2083,9.387],[10.63976444,3.2152,9.732],[10.64839022,3.213,9.62],[10.76187378,3.2124,9.278],[10.83268444,3.2142,9.423],[10.95585867,3.2152,9.804],[10.83549867,3.213,9.576],[10.89558933,3.2145,9.92],[10.97518044,3.2124,9.323],[10.76907911,3.2161,9.99],[10.93912978,3.213,9.346],[10.90199022,3.2114,9.542],[10.83319822,3.1832,9.715],[10.93452622,3.1677,9.199],[10.89234844,3.2127,9.159],[10.92905778,3.2121,9.668],[10.82011556,3.2037,9.855],[10.77831644,3.2142,9.658],[10.83103111,3.2124,9.448],[10.81488978,3.2111,9.236],[10.911288,3.1767,9.465],[11.04644978,3.2118,9.821],[10.93133156,3.2139,9.117],[10.873248,3.1978,9.197],[10.94023644,3.1556,9.427],[10.54275378,3.2145,9.379],[10.69542311,3.2155,9.225],[10.78066578,3.2074,9.484],[10.79645867,3.2133,9.25],[10.80249778,3.2133,9.655],[10.78693156,3.2136,10.029],[10.77832178,3.2108,9.804],[10.83759556,3.213,9.32],[10.67899644,3.2139,9.207],[10.63654578,3.2139,9.902],[10.85730844,3.2121,9.425],[10.90496178,3.2121,9.603],[10.88468356,3.2136,9.356],[10.82856178,3.2145,9.662],[10.83995378,3.1947,9.352],[10.93693244,3.2108,9.701],[10.82076444,3.1885,9.637],[10.86415467,3.2142,9.493],[10.82016533,3.2096,9.534],[11.07271911,3.213,10.008],[10.89999644,3.1969,9.778],[0.057479583,3.2062,9.779],[10.95181422,3.2121,9.96],[10.81379644,3.2,9.596],[10.85274756,3.2145,9.76],[10.79027378,3.213,9.742],[10.965592,3.2127,9.425],[10.92191022,3.2136,9.439],[11.05067111,3.2145,9.366],[10.84714756,3.2105,9.471],[10.939536,3.2114,9.405],[10.87629244,3.2096,10.149],[10.67752,3.2149,9.706],[10.69108978,3.2136,9.776],[10.68329067,3.2139,9.69],[10.65320178,3.2133,9.948],[10.62512711,3.2046,10.045],[10.63029689,3.2105,9.521],[10.728472,3.2121,10.088],[10.75449689,3.2102,11.803],[10.65037156,3.2124,9.665],[10.61956089,3.2065,9.484],[10.702088,3.2136,9.708],[10.773288,3.213,9.759],[10.97906489,3.2065,9.873],[10.59837867,3.1811,9.186],[10.66035644,3.2111,9.774],[10.61899022,3.2155,11.708],[10.64136889,3.2152,9.37],[10.74076089,3.2145,9.361],[10.61294044,3.2046,9.923],[10.72981244,3.2012,9.586],[10.85524444,3.2139,9.752],[10.8374,3.2124,9.804],[10.94422311,3.2108,9.725],[10.85340889,3.2102,9.587],[10.72752089,3.2155,9.638],[10.58561067,3.2145,9.354],[10.58302756,3.213,9.13],[10.88925244,3.2133,9.361],[10.99625333,3.2145,9.84],[10.75603644,3.2149,9.867],[10.73556089,3.2149,9.602],[10.84886756,3.209,9.537],[10.38817867,3.2145,9.604],[10.654928,3.2161,9.541],[10.61890133,3.2152,9.656],[10.75947911,3.2133,9.578],[10.64597156,3.2149,9.301],[10.65622311,3.2142,9.606],[10.69119822,3.2136,9.855],[11.03068089,3.2145,9.628],[10.537208,3.2164,9.329],[10.78610667,3.2145,9.414],[10.54702044,3.2118,9.503],[10.78655111,3.2145,9.439],[10.93320089,3.2149,9.303],[10.73404267,3.2149,9.231],[10.79951556,3.2136,9.584],[10.78911556,3.2149,9.606],[10.71838133,3.2124,9.895],[10.78426756,3.2142,9.414],[10.84919556,3.2043,9.637],[10.98519022,3.2145,9.886],[11.04808089,3.2102,9.424],[10.91977689,3.191,9.562],[10.90343644,3.1634,9.397],[10.87804356,3.1941,9.692],[10.83498578,3.2142,9.638],[10.80337778,3.2139,9.817],[10.87086133,3.2142,9.647],[11.07468,3.2133,9.361],[11.12761244,3.2136,9.71],[10.83973778,3.213,9.076],[11.03112178,3.209,9.722],[11.06599822,3.2127,9.633],[10.49167111,3.2155,9.422],[10.68866578,3.2158,9.791],[10.74854756,3.2167,9.784],[10.703984,3.2149,9.431],[11.01198311,3.2139,9.543],[10.79618667,3.213,9.598],[10.69777778,3.213,9.76],[10.82515733,3.2139,9.456],[10.56142044,3.2164,9.629],[10.55462044,3.2158,9.895],[10.73604889,3.2142,9.485],[10.79608,3.2142,9.792],[10.914672,3.2145,9.546],[10.76413778,3.2142,9.47],[10.74235556,3.2136,9.834],[10.77621333,3.2167,11.141],[10.41827644,3.2176,9.578],[10.45249867,3.217,9.783],[10.595664,3.2149,9.68],[10.55447911,3.2158,9.644],[10.60395467,3.2149,9.646],[10.61387733,3.2155,9.286],[10.65555556,3.2142,9.637],[10.51477333,3.2139,9.49],[10.46970756,3.2149,9.645],[10.534592,3.2142,9.722],[10.66444267,3.2155,9.819],[10.77694578,3.2142,9.689],[10.7364,3.2136,9.709],[10.61188533,3.2152,9.765],[10.63562489,3.213,9.395],[10.90779556,3.2139,29.941],[10.15888356,3.2204,9.792],[10.47196889,3.2192,9.463],[10.56094756,3.2158,9.18],[10.57098489,3.2189,9.463],[10.83333422,3.2173,9.682],[10.60042667,3.213,9.458],[10.82082756,3.2145,9.415],[10.556848,3.2149,9.618],[10.47101511,3.2167,9.484],[10.38997511,3.2164,9.689],[10.55506844,3.2192,9.113],[10.78296356,3.2155,9.602],[10.76022667,3.2139,9.33],[10.56539378,3.2155,9.678],[10.50053778,3.2145,9.385],[10.65299111,3.2149,9.735],[10.37195022,3.2158,9.663],[10.77059556,3.2158,9.557],[10.62727911,3.2155,9.697],[10.77035022,3.217,9.558],[10.96378489,3.2152,9.588],[10.89047111,3.2139,9.458],[10.65715644,3.2152,9.786],[10.53344356,3.2142,9.643],[10.41389689,3.2183,9.338],[10.47309778,3.2173,9.439],[10.62448533,3.2136,9.175],[10.63903644,3.2155,9.664],[10.77224444,3.2152,9.734],[10.58689956,3.2149,9.29],[10.736064,3.2149,9.472],[10.69129422,3.2167,9.684],[10.47216711,3.2176,9.43],[10.610544,3.2353,9.602],[10.53421778,3.2158,9.508],[10.51770489,3.217,9.93],[10.59056889,3.2152,9.406],[10.45395733,3.2145,9.503],[10.54525422,3.217,9.423],[10.59443733,3.2161,9.722],[10.32336089,3.2207,9.493],[10.42745244,3.2189,9.32],[10.45095644,3.2152,9.466],[10.58342933,3.2164,9.534],[10.67664,3.2145,9.622],[10.42391556,3.2152,9.712],[10.54994756,3.2152,9.325],[10.515264,3.2155,9.409],[10.40418133,3.2155,9.87],[10.22966044,3.2158,9.902],[10.426712,3.2186,9.55],[10.57306311,3.2183,9.611],[10.66938222,3.2155,9.464],[10.56372622,3.2167,9.615],[10.57630667,3.2145,9.81],[10.60111822,3.2155,9.524],[10.44649778,3.217,9.707],[10.44720444,3.2155,9.57],[10.55296089,3.2149,9.399],[10.57644,3.2155,9.602],[10.58541422,3.2158,9.804],[10.46030756,3.2145,9.565],[10.52768711,3.2173,9.29],[10.52273422,3.2173,9.926],[10.31597867,3.2176,9.697],[10.29205778,3.2223,9.413],[10.51974756,3.2164,9.508],[10.48708444,3.2161,9.988],[10.51263289,3.2173,9.706],[10.61491644,3.2164,9.7],[10.58665778,3.2176,9.292],[10.55445422,3.2152,9.954],[10.34962133,3.2195,9.509],[10.32187556,3.2155,9.413],[10.52815911,3.2176,9.055],[10.66924,3.217,9.319],[10.61943467,3.218,10.003],[10.57875911,3.2164,9.728],[10.42455644,3.2183,9.678],[10.47373244,3.2158,9.959],[10.45888978,3.2158,9.541],[10.55650578,3.2173,9.482],[10.43208978,3.2149,9.455],[10.48201778,3.2155,9.422],[10.46896178,3.2155,9.534],[10.49138222,3.2149,9.4],[10.57489956,3.2164,9.568],[10.60192089,3.2149,9.54],[10.47162756,3.2164,9.501],[10.60269333,3.2152,9.627],[10.63650756,3.2149,9.38],[10.55516978,3.2155,9.577],[10.58079556,3.2152,9.573],[10.50724533,3.2149,9.679],[10.52804089,3.2149,9.654],[10.76811022,3.2149,9.38],[10.396896,3.2223,9.397],[10.208784,3.2152,9.327],[10.25289867,3.2155,9.541],[10.43683556,3.217,9.869],[10.43636889,3.2152,9.723],[10.40657689,3.2139,9.769],[10.21144356,3.2145,9.543],[10.41271911,3.2161,9.55],[10.36957778,3.2158,9.448],[10.27348356,3.2176,9.319],[10.45912178,3.2195,9.158],[10.42537333,3.2155,9.586],[10.56468978,3.2164,9.553],[10.207456,3.2173,9.938],[10.48705067,3.2189,9.42],[10.547248,3.2186,9.71],])
X = X[:X.shape[0] // 12 * 12]  # make sure there are 12-sized clusters

The bug is floating. It is always reproduced on the full dataset and often fails on 36 data points. So you may reduce X to X = X[:36] and it will reduce the feedback loop.

TypeError: _centers_dense() takes exactly 5 positional arguments (4 given)

_k_means._centers_sparse and _k_means_centers_dense in _kmeans_single() now requires sample_weight parameter

https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/cluster/_k_means.pyx

ImportError: cannot import name '_k_means' from 'sklearn.cluster'

I think the version of scikit-learn being used is old in this repo, could you please update it according to the lastest version scikit-learn==0.23

Duplicate code

I think that there is duplicate codes in _labels_inertia_precompute_dense function.
initial_assignment function and below for loop is doing same thing.

labels, mindist = initial_assignment(labels, mindist, n_samples, all_distances, max_cluster_size)
all_points = np.arange(n_samples)

for point in all_points:
    for point_dist in get_best_point_distances(point, all_distances):
        cluster_id, point_dist = point_dist
        # initial assignment
         if not is_cluster_full(cluster_id, max_cluster_size, labels):
            labels[point] = cluster_id
            mindist[point] = point_dist
            break

Following code is initial_assignment function.

def initial_assignment(labels, mindist, n_samples, all_distances, max_cluster_size):
    """Initial assignment of labels and mindist"""
    all_points = np.arange(n_samples)
    for point in all_points:
        for point_dist in get_best_point_distances(point, all_distances):
            cluster_id, point_dist = point_dist
            # initial assignment
            if not is_cluster_full(cluster_id, max_cluster_size, labels):
                labels[point] = cluster_id
                mindist[point] = point_dist
                break
    return labels, mindist