# Are there any non-distance based clustering algorithms?

It seems that for K-means and other related algorithms, clustering is based off calculating distance between points. Is there one that works without it?

• Exactly what would you mean by "clustering" without some way to quantify the similarity or "closeness" of points? – whuber Dec 31 '14 at 6:59
• @Tim's answer below is very good. You may want to consider upvoting &/or accepting it, if it has helped you; it is a nice way to say 'thanks'. Extending his idea, there is latent class analysis, which applies a similar approach to categorical data. A non-parametric approach to FMMs can be used via the heights of a multivariate kernel density estimate. See Clustering via Nonparametric Density Estimation: The R Package pdfCluster (pdf) for more. – gung Jan 2 '15 at 1:53

## 4 Answers

One example of such a method are Finite Mixture Models (e.g. here or here) used for clustering. In FMM you consider the distribution ($f$) of your variable $X$ as a mixture of $K$ distributions ($f_1,...,f_k$):

$$f(x, \vartheta) = \sum^K_{k=1} \pi_k f_k(x, \vartheta_k)$$

where $\vartheta$ is a vector of parameters $\vartheta = (\pi', \vartheta_1', ..., \vartheta_k')'$ and $\pi_k$ is a proportion of $k$'th distribution in the mixture and $\vartheta_k$ is a parameter (or parameters) of $f_k$ distribution.

A specific case for discrete data is Latent Class Analysis (e.g. here) defined as:

$$P(x, k) = P(k) P(x|k)$$

where $P(k)$ is probability of observing latent class $k$ (i.e. $\pi_k$), $P(x)$ is probability of observing an $x$ value and $P(x|k)$ is probability of $x$ being in class $k$.

Usually for both FMM and LCA EM algorithm is used for estimation, but Bayesian approach is also possible, but a little bit more demanding because of problems such as model identification and label switching (e.g. Xi'an's blog).

So there is no distance measure but rather a statistical model defining the structure (distribution) of your data. Because of that other name of this method is "model-based clustering".

Check the two books on FMM:

One of the most popular clustering packages that uses FMM is mclust (check here or here) that is implemented in R. However, more complicated FMM's are also possible, check for example flexmix package and it's documentation. For LCA there is an R poLCA package.

• Do you have a good sense of what the different use cases might be? – shadowtalker Dec 31 '14 at 10:48
• As in, "when should I use this instead of, say, partitioning around medoids?" Very nice answer anyway – shadowtalker Dec 31 '14 at 15:27
• @caveman notes it's just a notational convention. It is a vector of vectors, that's all. – Tim Mar 28 '16 at 7:04
• @caveman there is $k$ different distributions $f_1,...,f_k$ that are in the mixture, each of them with their own parameters (that is why we have vectors of parameters). – Tim Mar 28 '16 at 16:24
• @caveman most typical case is that you have $k$ e.g. normal distributions, with different means and sd's. But they can differ, see 3.1 example in cran.r-project.org/web/packages/flexmix/vignettes/… that shows mixture two different regression models. – Tim Mar 28 '16 at 16:54

K-means isn't "really" distance based. It minimizes the variance. (But variance $\sim$ squared Euclidean distances; so every point is assigned to the nearest centroid by Euclidean distance, too).

There are plenty of grid-based clustering approaches. They don't compute distances because that would often yield quadratic runtime. Instead, they partition the data and aggregate it into grid cells. But the intuition behind such approaches is usually very closely related to distances.

There are a number of clustering algorithms for categorical data such as COOLCAT and STUCCO. Distances aren't easy to use with such data (one-hot encoding is a hack, and does not yield particularly meaningful distances). But I haven't heard of anyone using these algorithms...

There are clustering approaches for graphs. But either they reduce to classic graph problems such as clique or near-clique finding and graph coloring, or they are closely connected to distance-based clustering (if you have a weighted graph).

Density-based clustering like DBSCAN has a different name, and isn't focused around minimizing distances; but "density" is usually specified with respect to a distance, so technically these algorithms are either distance-based or grid-based.

The essential part of your question that you left out is what is your data?

• +1: I appreciate that you show how any clustering algorithm uses some implicit (perhaps) generalized sense of "distance" or "similarity," and that you do so while offering a survey of many such algorithms. – whuber Jan 2 '15 at 16:01
• I think by "distance-based" he meant similarity metrics, which would include variance. – en1 Jul 31 '15 at 14:27
• Why would variance be a similarity metric? It's related to square Euclidean distance; but not equivalent to arbitrary distances. – Anony-Mousse Jul 31 '15 at 18:54

In addition to previous nice answers, I would suggest considering Dirichlet mixture models and Bayesian-based hierarchical Dirichlet process models. For a rather comprehensive and general overview of approaches and methods for determining an optimal number of clusters, please see this excellent answer on StackOverflow: https://stackoverflow.com/a/15376462/2872891.

A purely discriminative approach is "regularized information maximisation" by Gomes et al. There is no notion of similarity/distance involved in it whatsoever.

The idea is to have a logistic regression like model that puts points into bins. But instead of training it to maximise some form of log-likelihood of the class labels, the objective function is one that puts points into different clusters.

To control the amount of clusters used by the model, an additional regularisation term weighted by the hyper parameter $\lambda$ is used. It boils down to a the inverse variance of a Gaussian prior over the weights.

Extension to kernel methods or neural networks for non-linear clustering is straightforward.