Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.
up vote 2 down vote favorite
2

Can anyone point me out a k-means implementation (it would be better if in matlab) that can take the distance matrix in input? The standard matlab implementation needs the observation matrix in input and it is not possible to custom change the similarity measure.

Thanks.

share|improve this question
1  
You could try to generate raw data corresponding to your matrix of euclidean distances and input those to K-Means. Alternative easy approach could be to use Ward method of hierarchical clustering of the matrix: K-Means and Ward share similar ideology of what a cluster is. – ttnphns Jun 30 '11 at 6:22
additionally to ttnphns and Not Durrett you might find Is it ok to use Manhattan distance with Ward's inter-cluster linkage in hierarchical clustering? interesting – steffen Jun 30 '11 at 7:18
Not Matlab, but the page of python under is-it-possible-to-specify-your-own-distance-function-using-scikits-learn-k-mean‌​s can use any of the 20-odd metrics in scipy.spatial.distance. – Denis Jul 1 '11 at 8:36

3 Answers

up vote 2 down vote

Since k-means needs to be able to find the means of different subsets of the points you want to cluster, it does not really make sense to ask for a version of k-means that takes a distance matrix as input.

You could try k-medoids instead. There are some matlab implementations available.

share|improve this answer
Hi, thanks for the answer; instead of directly give the distance matrix would it be possible to give as input a custom distance metric? The point is that I have to compare two clusterings methods and, since in the second one I use a custom similarity matrix, I want to use the same approach with kmeans in order to get a fair comparison. – Eugenio Jun 30 '11 at 19:18
ELKI allows you to use arbitrary distance functions with k-means. Note that the algorithm may then fail to converge. K-means is really designed for squared euclidean distance (sum of squares). With other distances, the mean may no longer optimize, and boom, the algorithm will eventually not converge. Seriously, consider using k-medoids. It actually was written to allow using the k-means idea with arbirary distances. – Anony-Mousse Apr 27 at 19:10
up vote 1 down vote

You could turn your matrix of distances into raw data and input these to K-Means clustering. The steps would be as follows:

1) Distances between your N points must be squared euclidean ones. Perform "double centering" of the matrix: Substract row mean from each element; in the result, substract column mean from each element; in the result, add matrix mean to each element; divide by minus 2. The matrix you have now is the SSCP (sum-of-squares-and-cross-product) matrix between your points wherein the origin is put at geometrical centre of the cloud of N points.

2) Perform PCA (Principal component analysis) on that matrix and obtain NxN component loading matrix. Some of last columns of it are likely to be all 0, - so cut them off. What you stay with now is actually principal component scores, the coordinates of your N points onto principal components that pass, as axes, through your cloud. This data can be treated as raw data suitable for K-Means input.

P.S. If your distances aren't geometrically correct squared euclidean ones you may encounter problem: the SSCP matrix may be not positive (semi)definite. This problem can be coped with in several ways but with loss of precision.

share|improve this answer
Thanks for your answer! Actually I don't have a real distances matrix but a similarity matrix (0...1) among objects, and the similarities are not calculated exactly using euclidian distances but with a custom algorithm that take into consideration the raw data but not in the standard way. I guess in this case I can't apply your procedure, am I right? – Eugenio Jul 1 '11 at 0:07
You still can, after converting similarities to distances. The latter will probably be not true euclidean (and so the SSCP will have some negative eigenvalues); then try to add small constant to distances until the SSCP loses neg. eig. There also other ways exist to work around with the problem. And please remember that you double center matrix of squared distances. – ttnphns Jul 1 '11 at 5:59
P.S. And by the way. If your matrix is similarities, then, well, it's even better. You just treat it as that SSCP matrix I was talking about and do PCA with it. Still, the problem of possible negative eigenvalues remains. – ttnphns Jul 1 '11 at 6:07
up vote 0 down vote

Please see this article, written by one of my acquaintances ;)

http://arxiv.org/abs/1304.6899

It is about a generalized k-means implementation, which takes an arbitrary distance matrix as input. It can be any symmetrical nonnegative matrix with a zero diagonal. Note that it may not give sensible results for weird distance matrices. The program is written in C#.

Source code can be obtained by visiting the above link, then clicking Other Formats, then clicking Download Source. Then you will get a .tar.gz containing Program.cs. Alternatively, the source code can be copied out from the PDF as well.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.