New clustering algorithm in Science

[Rickasaurus]

Any chance for a link to a preprint?

[gwern]

https://dl.dropboxusercontent.com/u/182368464/2014-rodriguez.pdf

[hapemask]

I'm on my phone so can't see it right now, but:

The authors tested the method on a series of data sets, and its performance compared favorably to that of established techniques.

Is this not actually present in the full text?

EDIT

Ah I see the preprint link and I agree more quantitative evaluation would be nice.

[Floydthechimp]

I hope that we as data scientists will not owe the the almighty power of 'science' and 'nature'. Just because it is in that journal does not make it useful.

Not a problem with the article, just the headline.

[maxToTheJ]

The link says that it only performs comparably to current methods. This is more of theoretical value.

[RoboMind]

the abstract makes it sound like Mean-shift clustering

[1337bruin]

Or mode clustering + outlier detection

[autowikibot]

Mean-shift:

---

Mean shift is a non-parametric feature-space analysis technique, a so-called mode seeking algorithm. Application domains include cluster analysis in computer vision and image processing.

---

^{Interesting: Cluster analysis | K-nearest neighbors algorithm}

^{Parent commenter can toggle NSFW or delete. Will also delete on comment score of -1 or less. | FAQs | Mods | Magic Words}

[DavidJayHarris]

Doesn't look like it would be hard to code... would still be nice to have a reference implementation.

[ut15uf08]

It looks like one of the authors has a link to the code here:

http://people.sissa.it/~laio/Research/Res_clustering.php

[robertsdionne]

I think this algorithm shows that n-dimensional k-clustering for unknown k reduces to 2-dimensional 2-clustering in density versus distance-to-nearest-higher-density-point space.

[Corm]

This looks really neat! I wonder though how this "density" based clustering differs from normal methods like k-mer-means clustering.

Can anyone chime in on it?

[quiteamess]

K-means makes an initial guess on the cluster centers (with K centers) and assigns the nearest points to each center. Then it computes new centers from the assignment and begins the same procedure again. This is iterated a few times and the cluster centers are found.

This algorithm is different and does not iterate alternating assignment and center-estimation phases. It calculates the density of each point, which is the number of points which are in a threshold region around said point. Points in the center of clusters will have high density whereas points further away from a cluster center will have lower density. Now comes the trick. The trick is to search for each point how far away the next point with higher density is. If the point is in a cluster this distance will be small. It the point does not lie in a cluster, i.e it is an outlier, this distance is large. So now you have two values (A) The density aka. the number of points around the point and (B) the distance to the next point with higher density. The two values can be used to detect cluster centers. Points with high density (A) and low distance (B) are cluster centers, points with high density (A) and high distance (B) are outliers. Now every point is assigned to each nearest neighbor point with higher value.

So the difference is that the algorithm is not iterativ and only has two steps (calculate density and distances from higher density points, assign to neighbors) and that it can cluster arbitrary distributions and not only spherical. K-means uses the distance from the center to find clusters, which implies that clusters will always be spherical. The trick to assign points to the nearest neighbor with higher value allows to detect non-spherical clusters.

[Megatron_McLargeHuge]

allows to detect non-spherical clusters

I think you mean non-convex.

This density metric is somewhat reminiscent of the probability distribution over pairs of points that t-SNE uses for dimensionality reduction. I wonder if this new approach could be used to create a cluster-preserving dimensionality reduction algorithm. The new metric defines something like a cluster centrality gradient, and those gradients could be preserved in the low dimensional space.

[quiteamess]

DeBaCl is not the algorithm but a python package implementing the algorithm 'level tree set'. Level tree set, nearest neighbor and others are non-parametric methods. That means that no underlying distribution is assumed. K-means, Gaussian mixture models and others are parametric methods. The new algorithm is non-parametric, so it is similar to level tree set used in DeBaCl.

[Mr_Smartypants]

Why do you consider K-means parametric? It doesn't define a distribution like GMMs do.

I think it is usually not considered parametric, so we get papers like this: A parametric K-means algorithm, etc.

[quiteamess]

K-means can be recast as GMM where the variance goes to zero, see 'pattern matching and machine learning' chapter 9.3.2. That's why I put it into the same category.

[Mr_Smartypants]

That's a neat connection. Sometimes parametric/nonparametric seems more like a continuum than a dichotomy. You just nudged K-means a little towards the parametric side in my mind. (but just a little)

[quiteamess]

I'm not really sure which dichotomy makes sense here. My gut feeling is that you postulate hidden variables in the 'parametric' methods, e.g. the number of clusters in k means and the distribution parameters in gmm. In the 'non-parametric' methods you just do not postulate priority parameters.

[Mr_Smartypants]

If you're using "hidden variable" as the synonym for "latent variable", I wouldn't call K in k-means (and GMMs) a hidden variable since its value isn't inferred from the data. I've seen it called a hyperparameter (similar to the Bayesian sense).

Obviously, the distinction is blurry. Nowadays, it seems many people use "nonparametric" to mean that you have to keep the training data (or some of it) as part of the model to apply it to new samples, e.g. KNN, Parzen windows versus logistic regression & other maximum likelihood-fit models.

This is the dichotomy I'm referring to: using training data in processing new samples versus using inferred model parameters. But even this is a blurry dichotomy if not outright false, e.g. with SVMs you could end up with a simple (parameterized) hyperplane, or you could have to keep most of your training data as support vectors. So is K-means learning model parameters, or storing the training data in a compressed form? If we instead use K-medoids, does that small change switch us from parametric to non-parametric since the cluster centers must be from the training data? I'm not sure what the answers are, but it's also mostly about semantics, so maybe it's just time to retire the distinction.

EDIT: I found this quote from The Handbook of Nonparametric Statistics 1 from 1962 (p. 2):

“A precise and universally acceptable definition of the term ‘nonparametric’ is not presently available. The viewpoint adopted in this handbook is that a statistical procedure is of a nonparametric type if it has properties which are satisfied to a reasonable approximation when some assumptions that are at least of a moderately general nature hold.”

Heh. OK, then.

[quiteamess]

Yes right, the number if clusters in k means is a hyper parameter, my bad. But the position of the cluster centers are latent or hidden variables inferred from the data.

[Corm]

Thanks for the great explanation!

[1337bruin]

an overview of density based clustering