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?
2
-
4$\begingroup$ Exactly what would you mean by "clustering" without some way to quantify the similarity or "closeness" of points? $\endgroup$– whuber ♦Dec 31, 2014 at 6:59
-
2$\begingroup$ @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. $\endgroup$– gung - Reinstate MonicaJan 2, 2015 at 1:53
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
11
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. Vermunt and Magidson, 2003) 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:
- McLachlan, G. & Peel, D. (2000). Finite Mixture Models. John Wiley & Sons.
- Frühwirth-Schnatter, S. (2006). Finite Mixture and Markov Switching Models. Springer.
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.
-
1$\begingroup$ Do you have a good sense of what the different use cases might be? $\endgroup$ Dec 31, 2014 at 10:48
-
1$\begingroup$ It is just a different method with different ideas behind it. With FMM you also define a statistical model underlying the data, so if you assume such a model then the approach seems more appropriate. I recommend the McLachlan & Peel book - it is a really extensive review of the topic. $\endgroup$– Tim ♦Dec 31, 2014 at 15:33
-
1$\begingroup$ @caveman notes it's just a notational convention. It is a vector of vectors, that's all. $\endgroup$– Tim ♦Mar 28, 2016 at 7:04
-
1$\begingroup$ @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). $\endgroup$– Tim ♦Mar 28, 2016 at 16:24
-
1$\begingroup$ @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. $\endgroup$– Tim ♦Mar 28, 2016 at 16:54
$\begingroup$
$\endgroup$
3
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?
answered Jan 2, 2015 at 9:13
-
3$\begingroup$ +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. $\endgroup$– whuber ♦Jan 2, 2015 at 16:01
-
$\begingroup$ I think by "distance-based" he meant similarity metrics, which would include variance. $\endgroup$– en1Jul 31, 2015 at 14:27
-
1$\begingroup$ Why would variance be a similarity metric? It's related to square Euclidean distance; but not equivalent to arbitrary distances. $\endgroup$ Jul 31, 2015 at 18:54
$\begingroup$
$\endgroup$
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.
answered Jan 2, 2015 at 11:47
$\begingroup$
$\endgroup$
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.
