12
$\begingroup$

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:

Clustering

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...

$\endgroup$
1

2 Answers 2

7
$\begingroup$
  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).

$\endgroup$
5
  • $\begingroup$ 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... $\endgroup$
    – Thomas
    Aug 6, 2018 at 7:44
  • $\begingroup$ Regarding 2.: HDBSCAN in it's Python implementation has a predict() method, just like k-means - Correctly labelling new objects is therefore pretty obvious :) $\endgroup$
    – Thomas
    Aug 6, 2018 at 7:45
  • $\begingroup$ "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%. $\endgroup$ Aug 6, 2018 at 16:43
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 6, 2018 at 16:47
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 6, 2018 at 16:50
1
$\begingroup$

Yes, there is an example: The iris dataset is nearly perfectly clustered by k-means regarding its three classes, while hdbscan is most likely not going to be able to recover those three classes. Of course you need to know that there are three classes.

However, I would argue that this task is not what clustering is about - it would be some sort of "unsupervised classification" task which is basically nonsense. However, an unfortunate amount of researcher are evaluating their papers like that (as in "trying if the clustering can recover labels"). The reason is simple: It is inherently difficult to evaluate unsupervised learning - I know, because I am a researcher of clustering myself. So this is an inherently invalid, but simple to understand "evaluation approach". If anyone is interested in more information on that, I can deliver, but I am not sure whether anyone care at this point.

Scientifically speaking there is no "good" or "bad" clustering technique. There are only different techniques following different definitions of what a "cluster" is in the first place. However, the definition that k-means follows is usually not the definition that you want - that is why k-means is usually not the method you want and thus k-means use is limited. The definition is very opinionated. In fact, it looks such that I am not even sure if I would call k-means a clustering method or rather a vector quantization method - as many others have called it as well.

And here we see a very useful application of k-means (and frankly the one I would use k-means for): To tessellate a space. Since k-means is also so very fast, it is very useful for some sort of "multidimensional histogram" or "pre-clustering" for speedups and these sort of things. Unfortunately this often means you want a large "k" and then k-means becomes slow (quadratic runtime), which kind of defeats the purpose. Fortunately, this is where dual trees come into play - they are able to make k-means fast even for large "k".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.