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.
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 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.
Please see this article, written by one of my acquaintances ;)
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.
You can use Java Machine Learning Library. They have a K-Means implementation. One of the constructors accepts three arguments
- K Value.
- An object of that is an instance of the DistanceMeasure Class.
- 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.