# Clustering based on distance matrices

Given a pre-computed distance matrix, obtained from arbitrary samples, such as graphs, I am currently looking for efficient clustering algorithms to deal with distance matrices, so that the algorithm indicates which sample indices (index from 0 to matrix_length-1, as each line corresponds to a distance from sample to all others) are the best clusters centers.

I have already implemented "fast k-medoids", from Park and Jun.

MeanShift can be implemented for this as well, but I am not sure if it could use ball trees or kd-trees to efficiently allow the algorithm to find nearest neighbors efficiently. To implement MeanShift for distance matrices, there is need for computing a "center" from some samples, which can be considered as the sample which minimizes the sum of distances to all others.

The problem on later ideia is how to calculate 'centers', because the samples doesn't belong to a n-dimensional space. KD-tree or ball-tree can be used in such scenario?

Edit: if it helps, I have a MeanShift that deals with distances matrices: https://github.com/icarocd/parallel-meanshift

If you can come up with similarity matrix, you can use Spectral methods like Laplacian Eigenmaps. Once solved, this will give you new feature vectors that respect the similarities. From there, you can cluster those feature vectors with classic k-means for example. The methods in this family are attractive in the cases when all you are given is a similarity matrix, not the original feature vectors.

A word of caution, the Spectral methods are computationally intensive. Anything bigger than couple of tens of thousands rows/columns in your similarity matrix can quickly put too much pressure on memory usage. If your similarity matrix is sparse, then it can be efficiently solved.

• Thanks for your answer. Unfortunately, I couldn't clearly understand the idea. Could you provide references about the use of spectral methods as a way of feature vector generation? "this will give you new feature vectors that respect the similarities". Is this one a valid reference of your idea? link.springer.com/chapter/10.1007%2F3-540-70659-3_8 – Ícaro Dourado May 14 '15 at 2:42

Here are two possibilities you can look into (I am sure there are several others but my bias reflects the models I have used)

1) You could use hierarchal clustering. There you are dealing directly with the distance matrix so construct the dendogram and chop it at the level corresponding to the number of clusters you want to find

2) The technique called gene shaving (http://genomebiology.com/2000/1/2/research/0003/) makes use of principal components and correlations between genes to do clustering (This is in the context of genetics, but here too, there is no natural definition of distance

• Your 1st idea is actually how I once clustered data using self-organizing maps (clustering of pre-trained neurons). How couldn't I remind that? =) Your answer is very helpful, thanks. – Ícaro Dourado May 13 '15 at 18:59