# How to perform k-means clustering with only a distance function, not euclidean points?

I want to perform k-means clustering on some objects I have, but the objects aren't described by "points". However, I am able to compute the distance between any two objects (it is based on a similarity function). I've implemented K-means before, but it's not clear to me how to update the clusters to be the cluster "centers" without a point-representation. How would this normally be done?

-
What do you mean there are not described as points? –  curious Jan 7 at 14:35

Obviously, k-means needs to be able to compute means.

However, there is a well-known variation of it known as k-medoids or PAM (Partitioning Around Medoids), where the medoid is the existing object most central to the cluster. K-medoids only needs the pairwise distances.

-

You are exactly describing the problem setting of kernel $k$-means; when you cannot represent a data point as a Euclidean vector, but if you can still calculate (or define) the inner product between two data points then you can kernelize the algorithm. The following webpage provides brief description of the algorithm:

Kernel $k$-means page

This kernel trick is a very popular and fundamental idea in Statistics and machine learning.

Wiki page on the kernel trick

If you are interested, the book Learning with Kernels from by Bernhard Schölkopf and Alexander J. Smola will be a very nice introduction.

This note from Max Welling seems very nice; also, if you are using R you can take a look at this R package.

MDS might be a one way to solve your problem, but it does not directly attack the problem you want to solve; while kernel k-means does.

-
I wanted to include more links but couldn't due to low reputation. This note from Max Welling note seems very nice; also, if you are using R you can take a look at this R package –  d_ijk_stra Jul 24 '12 at 23:09
(+1) Welcome to the site. I have added the links in your comment to the body of the post as well as one to the Schölkopf and Smola text. –  cardinal Jul 24 '12 at 23:25

I certainly don't know how it's "normally" done, and for the record, I don't know much about cluster analysis. However, are you familiar with Multidimensional Scaling? (Here's another reference, the wiki, and you could search CV under the tag.) Multidimensional scaling takes in a matrix of pairwise distances, which sounds like your situation. From the MDS, you can get the locations of the objects in the lowest-dimensional space necessary to adequately represent them. I would guess you could use those locations to do a subsequent cluster analysis like k-means; alternatively, once you had the output, you might no longer need the CA.

I don't know if you use R, but here is the task view for Psychometrics, which includes a section on MDS in R. Hope that helps.

-

@gung is absolutely correct suggesting you multidimensional scaling (MDS) as a tool to create points X dimensions data out of distance matrix. I'm to add just few strokes. K-means clustering implies euclidean distances. MDS will give you points-in-dimensions coordinates thereby guaranteeing you euclidean distances. You should use metric MDS and request number of dimensions as large as possible, because your aim is to minimize error of reconstracting the data, not to map it in 2D or 3D.

What if you don't have MDS software at hand but have some matrix functions such as eigenvalue decomposition or singular-value decomposition? Then you could do simple metric MDS yourself - Torgerson MDS, also known as Principal Coordinates analysis. It amounts to a bit "twisted" Principal Components analysis. I won't be describing it here, although it is quite simple. You can read about it in many places, e.g. here.

-

Optimal Cluster Preserving Embedding of Nonmetric Proximity Data should fit your case. The paper shows how you can obtain a metric vector representation of your objects given only a matrix of pairwise dissimilarity function such that the cluster assignments will be preserved for a range of clustering algorithms, including $k$-means.

In your case, what you basically need to do is:

1. Have your dissimilarity matrix $D$ with zero self-dissimilarity.
2. In case it is not symmetric already, symmetrize by averaging $D_{ij}$ and $D_{ji}$.
3. center it (i.e. subtract row and column mean) to obtain $D^c$
4. Calculate $S^c = -\frac{1}{2}D^c$
5. Perform a spectral shift: Subtract the $S^c$'s smallest eigenvalue from $S^c$'s spectrum to ensure it becomes positive-semidefinite. Do this to obtain $\tilde S^c$.
6. Calculate the eigenvector decomposition of $\tilde S^c = V \Lambda V^\top$.
7. Restore a vector representation in a $n-1$-dimensional metric space of your data: $X = V\Lambda^{1/2}$.

This assumes that $n$ is not too large. If it is, additionally doing PCAwill give you a more meaningful representation of the data. (The paper describes how to do this, too).

-
The steps described are nothing less than Principal Coordinates Analysis which I mention in my answer. –  ttnphns Jul 30 '12 at 0:52
Please, exemplify your step 5. Substracting the last (negative) eigenvalue(s) from S matrix elements seem to not help make S positive semidefinite. –  ttnphns Jul 30 '12 at 2:26
@ttnphns: It basically is PCA, yes, but it doesn't require the distances to be metric. The description of step 5 was unfortunate, thanks for spotting it. Is it now clear? –  blubb Jul 30 '12 at 9:35
Subtracting the sum of negative eigenvalues from all the eigenvalues and then restoration S matrix is equivalent to subtracting that sum from the diagonal elements of S. This endeed makes S positive (semi)definite, but... –  ttnphns Jul 30 '12 at 12:03
...but this way is very bad in the sense that the resultant euclidean data X produce euclidean distances D_new which are very far from original dissimilarities D. So, I wouldn't recommend your step 5. It seems much better simply to set negative eigenvalues to 0 and skip to step 7. Or, slightly more fine approach: set negative eigenvalues to 0, rescale positive eigenvalues so that they sum be original (=trace(S)), and then skip to step 7. That's how it appears to me. –  ttnphns Jul 30 '12 at 12:10

Your data can also be viewed as a network, and you can use one of the many network clustering algorithms available. For this you would probably need to apply a threshold on the edge weights, and transform distances to similarities. It is not the 'statistics' way of doing things, but cluster analysis is an underspecified problem to begin with, and as explorative tools network clustering algorithms perform very well.

-

With regard to clustering and MDS I would suggest the following resources:

These references also nicely cover the topics of similarity and distance functions (proximity measures) for binary and continuous data.

-