Comparing Clustering Algorithms • Hacker News Board

Re: Comparing Clustering Algorithms

#31

Post by jey » Mon, May 02, 2016, 4:46 PM UTC

This is very specific to 2D data. I bet the story is a lot different for high-dimensional data. The challenges you encounter with this sort of clumping in 2D is unlikely to occur in high-dimensional data due to the "curse" of dimensionality. Clustering in high dimensions has its own quirks and gotchas too, but they're quite distinct from the gotchas of low-dimensionality.

Here's more from an actual expert: http://research.microsoft.com/en-US/people/kannan/book-chapt...

Re: Comparing Clustering Algorithms

#32

Post by rm999 » Mon, May 02, 2016, 4:48 PM UTC

makmanalp wrote: post #27

These all look like clustering based on a 2d space, but does anyone know methods to tackle clustering on a network? Is it just a matter of tweaking the definition of density / distance to the number of hops, or is it a different problem entirely? I can see how with 0 or 1 hops the data would be a very smushed distribution, versus 2d distance is much more rich and spread out.

Looks at spectral clustering. Spectral methods usually take the distances between points to generate a graph, then operate directly on that graph. If you already have a graph/network, you can use those methods directly on it.

Re: Comparing Clustering Algorithms

#33

Post by makmanalp » Mon, May 02, 2016, 5:03 PM UTC

PeterisP wrote: post #29

makmanalp wrote: post #27

These all look like clustering based on a 2d space, but does anyone know methods to tackle clustering on a network? Is it just a matter of tweaking the definition of density / distance to the number of hops, or is it a different problem entirely? I can see how with 0 or 1 hops the data would be a very smushed distribution, versus 2d distance is much more rich and spread out.

Clustering algorithms generally only need a distance metric. Here 2d space is used for illustration just because it is easy to visualize. For n-dimensional space, geometric distance is often (but not always) used, but you can just use # of hops instead of that.

Brilliant, that's what I figured, thank you!

Re: Comparing Clustering Algorithms

#34

Post by lmcinnes » Mon, May 02, 2016, 5:04 PM UTC

makmanalp wrote: post #27

These all look like clustering based on a 2d space, but does anyone know methods to tackle clustering on a network? Is it just a matter of tweaking the definition of density / distance to the number of hops, or is it a different problem entirely? I can see how with 0 or 1 hops the data would be a very smushed distribution, versus 2d distance is much more rich and spread out.

If you want to use an HDBSCAN algorithm on graphs then I suggest you look into Spectral Clustering (which traditionally uses K-Means, but could use HDBSCAN instead. Otherwise you may want to consider graph specific algorithms such as Louvain.

Re: Comparing Clustering Algorithms

#35

Post by lmcinnes » Mon, May 02, 2016, 5:48 PM UTC

jey wrote: post #31

This is very specific to 2D data. I bet the story is a lot different for high-dimensional data. The challenges you encounter with this sort of clumping in 2D is unlikely to occur in high-dimensional data due to the "curse" of dimensionality. Clustering in high dimensions has its own quirks and gotchas too, but they're quite distinct from the gotchas of low-dimensionality. Here's more from an actual expert: http://res…

The examples are all in 2D because it allows someone to visualise what's going on. In higher dimensions things get messier and you have to rely on cluster quality measures ... which are often bad (or, more often, defined to be the objective function that a particular clustering algorithm optimizes, and hence give a false sense of how "well" the clustering has done). I've worked with HDBSCAN quite successfully on mid-range dimensionality data (50 to 100 dimensions). I agree that it doesn't work as well on truly high dimensional data, but then little can once the curse of dimensionality truly kicks in. Your best bet, at that point, is the assume that your data actually lies on some lower dimensional manifold (i.e. the intrinsic dimensionality is much lower) and apply suitable dimension reduction techniques (t-SNE, Robust PCA, etc.) and then cluster.

Re: Comparing Clustering Algorithms

#36

Post by danvoell » Mon, May 02, 2016, 5:56 PM UTC

mattnedrich wrote: post #16

I wrote an article about mean-shift a while back if anyone is interested in more details about it - https://spin.atomicobject.com/2015/05/26/mean-shift-clusteri... Some comments on K-Means - one large limitation of K-Means is that it assumes spherical shaped clusters. It will fail terribly for any other cluster shape. It's interesting that the author compared results on the same data set for the different algorithms.…

"It would be interesting to compare them across several different data sets to get a better feel for strengths/weaknesses, etc." I agree. I think that would be the logical next step for this article. Show various real world examples and describe why certain clusters might be better for these types of problems. But all in all, awesome article, thanks for the education.

Re: Comparing Clustering Algorithms

#37

Post by dweinus » Mon, May 02, 2016, 6:19 PM UTC

Great article! Does anyone know of an implementation of HDBSCAN for R?

Re: Comparing Clustering Algorithms

#38

Post by lmcinnes » Mon, May 02, 2016, 6:30 PM UTC

Wei-1 wrote: post #25

Why not use Density Cluster based on this 2014 Science Paper? http://science.sciencemag.org/content/344/6191/1492

Desnity Peak clustering is an interesting idea, but is still centroid based and will have many of the same issues as K-Means (but may pick better centroids for this case). It also involves a little bit of parameter tuning (particularly with regard to bandwidth), and can be relatively slow if not suitably accelerated with space indexing structures such as kd-trees or cover-trees.

Re: Comparing Clustering Algorithms

#39

Post by lmcinnes » Mon, May 02, 2016, 6:41 PM UTC

dweinus wrote: post #37

Great article! Does anyone know of an implementation of HDBSCAN for R?

I don't know of any implementations yet. On the other hand it isn't that hard to get the basics working (see http://nbviewer.jupyter.org/github/lmcinnes/hdbscan/blob/mas... for an explanation of the algorithm). The trickier part is getting good performance, but for small datasets that doesn't really matter. Hopefully someone will put together an implementation for R soon.

Re: Comparing Clustering Algorithms

#40

Post by dweinus » Mon, May 02, 2016, 8:15 PM UTC

lmcinnes wrote: post #39

dweinus wrote: post #37

Great article! Does anyone know of an implementation of HDBSCAN for R?

I don't know of any implementations yet. On the other hand it isn't that hard to get the basics working (see http://nbviewer.jupyter.org/github/lmcinnes/hdbscan/blob/mas... for an explanation of the algorithm). The trickier part is getting good performance, but for small datasets that doesn't really matter. Hopefully someone will put together an implementation for R soon.

Thank you for the response and also all of your hard work in the Python package!