Infinite Loop in K-means when relocating empty clusters

### Describe the bug

Relocating empty clusters in Kmeans is not working as expected in this edge case, where :
- There is duplicate entries.
- The number of clusters is equal to the number of entries.
- Very particular initial positions.

Kmeans is stuck in a infinite loop, and the only way to end it is the max number of iterations. 

I have suggestions to improve the relocation of empty clusters : 
- When selecting an entry to fill an empty cluster (the entry that has max_dist), we should not select an entry in a cluster that contains only 1 entry.
- After each relocation of an empty clusters, Centers needs to be updated.

### Steps/Code to Reproduce

```python
import numpy as np
from sklearn.cluster import KMeans

X = np.array([
    [100, 100], [100, 102], [106, 100], [107, 101], [107, 101], [108, 100]
])
init = np.array([
    [98, 104], [103, 100], [109, 102], [110, 100], [111, 100], [112, 100]
])
kmeans = KMeans(
    n_clusters=6,
    init=init,
    random_state=0,
    verbose=True,
    algorithm='lloyd',
    max_iter=10_000
).fit(X)
```

### Expected Results

We should only perform 1 iteration

```
Initialization complete
Iteration 0, inertia 40.0.
Iteration 1, inertia 0.0.
```

### Actual Results

Kmeans is stuck in an infinite loop

```
Initialization complete
Iteration 0, inertia 40.0.
Iteration 1, inertia 0.0.
Iteration 2, inertia 0.0.
Iteration 3, inertia 0.0.
Iteration 4, inertia 0.0.
Iteration 5, inertia 0.0.
Iteration 6, inertia 0.0.
Iteration 7, inertia 0.0.
Iteration 8, inertia 0.0.
Iteration 9, inertia 0.0.
Iteration 10, inertia 0.0.
Iteration 11, inertia 0.0.
Iteration 12, inertia 0.0.
Iteration 13, inertia 0.0.
Iteration 14, inertia 0.0.
Iteration 15, inertia 0.0.
Iteration 16, inertia 0.0.
Iteration 17, inertia 0.0.
Iteration 18, inertia 0.0.
Iteration 19, inertia 0.0.
```

### Versions

```shell
System:
   python: 3.9.0
   machine: Windows-10

Python dependencies:
      sklearn: 1.3.2
          pip: 20.2.3
   setuptools: 49.2.1
        numpy: 1.25.1
        scipy: 1.11.4
       Cython: None
       pandas: 2.0.3
   matplotlib: 3.7.2
       joblib: 1.3.2
threadpoolctl: 3.2.0

Built with OpenMP: True

threadpoolctl info:
       user_api: blas
   internal_api: openblas
    num_threads: 12
         prefix: libopenblas
        version: 0.3.23
threading_layer: pthreads

       user_api: openmp
   internal_api: openmp
    num_threads: 12
         prefix: vcomp
        version: None

       user_api: blas
   internal_api: openblas
    num_threads: 12
         prefix: libopenblas
        version: 0.3.21.dev
threading_layer: pthreads
```

COMMENT:
After debugging, I believe the "empty" centroid is changing label because after each Kmeans iteration, each "empty" centroid needs to find at least one sample to become "non empty". But while doing this, we do not verify that the sample does not come from a cluster that has only one sample, and this will generate another "empty" centroid.

Example : We have 3 clusters: one empty cluster `C_1`, one cluster that has only 1 sample `C_2` , and one cluster that has 2 identical samples `C_3`. 
When relocating empty clusters, `C_1` will look for samples in `C_2` and `C_3`, and it can happen that `C_1` will take the sample from `C_2`, so `C_2` will become empty, and `C_1` will have one sample. Therefore the empty centroid will change label and become `C_2`.

Initializing with 0 is not the root cause I believe, because initializing with other values will cause the same bug (except if we initialize the empty centroid with the position of another non empty centroid, this will have a different behavior).

I see 2 possible solutions to this:
1- Before the algorithm Kmeans start, check that the number of non duplicate samples is greater or equal the number of clusters. (and as you said, this can be very expensive). If it is not the case, we can throw a warning and reduce the number of clusters used internally.
2- If we have an empty cluster, and we can not find a sample with a distance greater than 0 to its centroid, then the relocation should stop, and the empty centroid should still empty. But in this case, we should not initialize its position with 0 because it results in an invalid centroid position. We should initialize it with +inf, or if we can do it, just delete the centroid.

Labels: Bug