Any suggestion for clustering method for unknown number of clusters and non-Euclidean distance?

Question

I need some suggestion for clustering (unsupervised classification) method for a consulting project. I am looking for a method that hopefully has the following properties:

1. The subject of my study has three properties. One is represented by a (non-Euclidean) distance matrix and the other two are in the form of vectors in Euclidean space. The distance matrix comes from sequences and can be in the form of percent of dissimilarity or other measurement of distance of sequences. The algorithm should be able to take both vectors in euclidean space and non-euclidean distance as input. For example, K-medoids can work with a distance matrix but K-means can not.

2. I would like the algorithm to select the number of clusters and the weight for three properties automatically (with prior knowledge and constraint).

3. I have information of previously identified “centers of clusters”. I would like to incorporate it as prior or initial values.

4. As a statistician, I would prefer the method to have a clear likelihood or loss function.

The closest thing I can think of is fitting a mixture model in Bayesian framework using reverse jump MCMC to determine the number of clusters. The vectors in R^d can be easily formulated into a normal likelihood but how to deal with the distance matrix is unclear to me. I can restrict the mean of normal likelihood to be at each of the observation of get the MCMC running but that does not have a clear mathematical / statistical meaning.

Does anyone have experience with a similar problem? Suggestion to references will be highly appreciated!

Answer 1

I think that using a MAP/Bayesian criterion of in combination with a mixture of Gaussians is a sensible choice. Points

You will of course object that MOGs require Euclidean input data. The answer is to find a set of points that give rise to the distance matrix you are given. An example technique for this is multidimensional scaling: $\text{argmin}_{\lbrace x_i \rbrace} \sum_{i, j}(||x_i - x_j||_2 - D_{ij})^2$ where $D_{ij}$ is the distance of point $i$ to point $j$.

Answer 2

I dealt with a problem for my thesis where I had to do clustering on a data set for which I only had a similarity (= inverse distance) matrix. Although I 100% agree that a Bayesian technique would be best, what I went with was a discriminative model called Symmetric Convex Coding (link). I remember it working quite nicely.

On the Bayesian front, perhaps you could consider something similar to clustering, but not? I'm thinking along the lines of Latent Dirichlet Allocation -- a really marvelous algorithm. Fully generative, developed in the context of modeling topic contents in text document corpora. But it finds plenty of applications in other types of unsupervised machine learning problems. Of course, the distance function isn't even relevant there...

Answer 3

DBSCAN works without knowing the number of clusters ahead of time, and it can apply a wide range of distance metrics.

Answer 4

You could use affinity propagation or better adaptive affinity propagation. Here is the Wikipedia link.

There are two main advantages for your case and another third one that I think is an advantage but may not be of importance to you.

1. You do not supply the number of clusters. The final number of clusters depends on the preference value and the similarity matrix values. The easiest way to work with the preference values is either to use the minimum value of the similarity matrix (that isn't zero) to get the smallest number of clusters, then try e.g. the maximum for the most clusters possible and continue with the median value and so on... OR Use the adaptive affinity propagation algorithm and have the preference determined by the algorithm.

2. You can supply any similarity measure you can come up with or take the inverse of a distance measure (maybe guard against dividing by zero when you do that).

3.(extra point) The algorithm chooses an exemplar representing each cluster and which examples belong to it. This means the algorithm doesn't give you an arbitrary average but an actual datapoint. However you can still calculate averages later of course. AND this also means that the algorithm doesn't used intermittent averages!

Software: There are several packages listed for Java, Python and R on the Wikipedia page. If you love MATLAB, like I do, then here is an implementation.