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.
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ 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. $\endgroup$– ttnphnsCommented Jun 30, 2011 at 6:22
-
$\begingroup$ 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 $\endgroup$– steffenCommented Jun 30, 2011 at 7:18
-
$\begingroup$ Not Matlab, but the page of python under is-it-possible-to-specify-your-own-distance-function-using-scikits-learn-k-means can use any of the 20-odd metrics in scipy.spatial.distance. $\endgroup$– denisCommented Jul 1, 2011 at 8:36
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
3
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.
-
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$– EugenioCommented Jun 30, 2011 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$ Commented Apr 27, 2013 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$– CpILLCommented Aug 7, 2018 at 13:11
$\begingroup$
$\endgroup$
7
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).
-
$\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$– EugenioCommented Jul 1, 2011 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$– ttnphnsCommented Jul 1, 2011 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$– ttnphnsCommented Jul 1, 2011 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, socolMeans(X) =rowMeans(X)and once you subtract row or col means:Y=X-rowMeans(X),mean(Y)is 0. $\endgroup$– ZhubarbCommented May 14, 2015 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$– ttnphnsCommented May 14, 2015 at 14:47
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
