14
$\begingroup$

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.

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Eugenio Jun 30 '11 at 19:18
  • 2
    $\begingroup$ 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. $\endgroup$ – Anony-Mousse Apr 27 '13 at 19:10
  • $\begingroup$ There is also pyclustering a python/C++ library that lets you supply a custom metric function: github.com/annoviko/pyclustering/issues/417 $\endgroup$ – CpILL Aug 7 '18 at 13:11
7
$\begingroup$

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. (Read explanation of the double centering here.)

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Eugenio Jul 1 '11 at 0:07
  • $\begingroup$ 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. $\endgroup$ – ttnphns Jul 1 '11 at 5:59
  • $\begingroup$ 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. $\endgroup$ – ttnphns Jul 1 '11 at 6:07
  • $\begingroup$ @ttnphns, sorry I am missing your explanation for step 1. The distance matrix X (let's say N*N) is going to be symmetric, so colMeans(X) =rowMeans(X) and once you subtract row or col means:Y=X-rowMeans(X), mean(Y) is 0. $\endgroup$ – Zhubarb May 14 '15 at 13:14
  • 1
    $\begingroup$ @Zhubarb, when I say You could turn your matrix of distances into raw data (points 1 and 2) I refer, essentially, to Torgerson's multidimensional scaling (MDS) , in which double centering is the initial step. Please search this site (and Google as well) about that procedure. "Double centering" is the conversion of (squared) distances into the corresponding scalar product matrix defined over the origin put into the centroid of the cloud of the points. $\endgroup$ – ttnphns May 14 '15 at 14:47
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

You can use Java Machine Learning Library. They have a K-Means implementation. One of the constructors accepts three arguments

  1. K Value.
  2. An object of that is an instance of the DistanceMeasure Class.
  3. Number of iterations.

One can easily extend the DistanceMeasure class to achieve the desired result. The idea is to return values from a custom distance matrix in the measure(Instance x, Instance y) method of this class.

K-Means is guarnateed to converge assuming certain properties of the distance metric. Euclidean distance, Manhattan distance or other standard metrics satisfy these assumptions. Since a custom distance metric may not satisfy these assumptions, the constructor has a third parameter specifying the number of iterations to run for building the clusterer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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