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

Question

I want to perform k-means clusteirng 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?

Answer 1

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.

Answer 2

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.

Answer 3

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 multidimensional-scaling 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.

Answer 4

@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.

Answer 5

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.

Answer 6

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).

Answer 7

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

• Numerical Ecology (Pierre Legendre and Louis Legendre): http://www.sciencedirect.com/science/bookseries/01678892/20 or http://tinyurl.com/cgrdfqk (google books) -- chapter on 'Ecological resemblance'
• Cluster Analysis (Brian S. Everitt, Sabine Landau, Morven Leese, Daniel Stahl): http://tinyurl.com/bld7k8h (google books) -- chapter on 'Measurement of proximity'
• Course 'Biostatistics-II, Multivariate Methods' by Prof. Brian C. McCarthy at Ohio University: http://www.ohio.edu/plantbio/staff/mccarthy/multivariate/multivariate.htm

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