Does k-means have any advantages over HDBSCAN expect for runtime?

I have recently learned about HDBSCAN (a fairly new method for clustering, not yet available in scikit-learn) and am really surprised at how good it is. The following picture illustrates that the predecessor of HDBSCAN - DBSCAN - is already the only algorithm that performs perfectly on a sample of different clustering tasks:

With HDBSCAN, you do not even need to set the distance parameter of DBSCAN, making it even more intuitive. I have tried it out on a few custom clustering tasks myself, and it always performed better than any other algorithm I have tried so far.

So my question is: Except for computation time, where k-means is still superior to all, is there any case were k-means might be superior? High-dimensional data for example, or a weird combination of clusters? I honestly can't really think of anything...

1. Randomization can be valuable. You can run k-means several times to get different possible clusters, as not all may be good. With HDBSCAN, you will always get the same result again.

2. Classifier: k-means yields an obvious and fast nearest-center classifier to predict the label for new objects. Correctly labeling new objects in HDBSCAN isn't obvious

3. No noise. Many users don't (want to) know how to handle noise in their data. K-means gives a very simple and easy to understand result: every object belongs to exactly one cluster. With HDBSCAN, objects can belong to 0 clusters, and clusters are actually a tree and not flat.

4. Performance and approximation. If you have a huge dataset, you can just take a random sample for k-means, and statistics says you'll get almost the same result. For HDBSCAN, it's not clear how to use it only with a subset of the data.

But don't get me wrong. IMHO k-means is very limited, hard to use, and often badly used on inappropriate problems and data. I do admire the HDBSCAN algorithm (and the original DBSCAN and OPTICS). On Geo data, these just work a thousand times better than k-means. K-means is totally overused (because too many classes do not teach anything except k-means), and mini-batch k-means is the worst version of k-means, it does not make sense to use it when your data fits into memory (hence it should be removed from sklearn IMHO).

• Thanks for your input. Regarding 1.: Randomization is certainly useful to improve a bad algorithm, but is it really better than having an algorithm that gets consistently good results? In my opinion, randomization in most cases is bad, because I can never be sure I ran enough rounds to get a "good" result... – Thomas Aug 6 '18 at 7:44
• Regarding 2.: HDBSCAN in it's Python implementation has a predict() method, just like k-means - Correctly labelling new objects is therefore pretty obvious :) – Thomas Aug 6 '18 at 7:45
• "Consistently good" may not be possible, and then you only have consistently bad. From an explorative point of view, different results mean mostly that you have more than one chance. Ten attempts with a chance of 10% is probably better than 1 attempt with a chance of 80%. – Has QUIT--Anony-Mousse Aug 6 '18 at 16:43
• The predict of Python HDBSCAN likely isn't as well supported by theory as it is with k-means. I don't recall this from the original paper - so it probably is an extension or a hack. Oe.g., simply using the nearest neighbor. But from a theoretical point of view, adding a single point can merge two clusters, and I doubt the predict function can do this - so a theoretically well supported predict may be difficult and have a really hard to use API. It probably does not guarantee to give the same result as if you'd run HDBSCAN on the dataset + the new point. – Has QUIT--Anony-Mousse Aug 6 '18 at 16:47
• But overall, I'd always try HDBSCAN on a data set. I agree that it very often works just great & much better than k-means. – Has QUIT--Anony-Mousse Aug 6 '18 at 16:50