k-means implementation with custom distance matrix in input 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.   
 A: 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.
A: 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.
A: 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.
A: You could turn your matrix of distances into raw data and input these to K-Means clustering. The steps would be as follows:

*

*Distances between your N points must be squared euclidean ones. Perform "double centering" of the matrix:
From each element, substract its row mean of elements, substract its column mean of elements, add matrix mean of elements, and divide by minus 2. (The row, column, and matrix means are from the initial squared distance matrix. The vectors of row means and the column means contain, of course, the same values, because the distance matrix is symmetric. The matrix mean scalar should be based on all matrix elements, including diagonal.)$^1$
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.)


*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.
$^1$ It is easy to show that the subtrahend from $d_{ij}^2$, the [rowmean + colmean - matrixmean], equals $h_i^2+h_j^2$ of the euclidean space's law of cosines: $d_{ij}^2 = h_i^2+h_j^2-2 s_{ij}$, where $s_{ij}$ is the scalar product similarity between the two vectors. Thus, the double centration operation is the reversing a (euclidean) distance into the corresponding angular similarity by that law. Specifically, it is a particular case of that law, the case when we put (via the specific subtrahend) the origin into the centroid of the bunch of points (the vectors' endpoints).
