Hi @ssimontacchi,

What you are describing is a common problem of KMeans (not only when the custom variant to timeseries but also the scikit-learn variant has these issues). Therefore, the KMeans algorithm is often ran multiple times with different random initializations, some score such as silhouette_score is then used to decide which of all those random restarts was the most qualitative.

On the other hand, the algorithm definitely should not hang indeed... I'll label this with "bug" for now!

Would it be possible to construct some minimal example with a small dataset? This would help a lot to debug

One important question is which init method are you using ?
Then what would you suggest Gilles when a cluster is empty ? Does anyone know what sklearn does in this case ?

Good question... I think some check is required that checks if the total number of unique clusters is equal to the specified number of clusters, if that is not the case, some warning should be raised that the number of clusters is probably not set well (and perhaps also display the number of clusters with the highest silhouette that we found over the random initializations).

Sklearn will just assign some random values to the cluster in case there is an empty cluster apparently. (source)

Sklearn will just assign some random values to the cluster in case there is an empty cluster apparently. (source)

In the link you provide, they state that it's not chosen at random btw:

A problem with k-means is that one or more clusters can be empty. However, this problem is accounted for in the current k-means implementation in scikit-learn. If a cluster is empty, the algorithm will search for the sample that is farthest away from the centroid of the empty cluster. Then it will reassign the centroid to be this farthest point.

We'll have to check.

Hi, I have tried to make a minimal example but am having trouble recreating it (and can't share the datasets doing it, unfortunately). I believe the example in the colab is the general situation though.

Again, it should be pretty fast on these datasets but just seems to hang. My guess of what is happening is that it's reassigning empty clusters indefinitely, but I'm not sure. Here is what the log looks like:

WARNING: QApplication was not created in the main() thread.
Resumed because of empty cluster
Resumed because of empty cluster
Resumed because of empty cluster
Resumed because of empty cluster
Resumed because of empty cluster
Resumed because of empty cluster
Resumed because of empty cluster
Resumed because of empty cluster
Resumed because of empty cluster
Resumed because of empty cluster

It only shows "Resumed because of empty cluster" 10 times though, and I'm not sure why that would happen either if it were failing to reassign clusters infinitely.

I'm trying to figure out what's different about this data and I'll let you know when I figure it out. Thanks!

I'm really having a hard time getting it to hang but found that a lot, though not all, that were having this problem have tiny amounts of data. If you run it with only a few data points you will definitely get lots of empty cluster messages.

I guess the question is figuring out if there is some condition that could cause it not to converge?