31
$\begingroup$

I want to perform K-means clustering on objects I have, but the objects aren't described as points in space, i.e. by objects x features dataset. However, I am able to compute the distance between any two objects (it is based on a similarity function). So, I dispose of the distance matrix objects x objects.

I've implemented K-means before, but that was with points dataset input; and with distance matrix input 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? Are there versions of K-means or methods close to it, for that?

Improve this question
$\endgroup$
2

8 Answers 8

Reset to default
31
$\begingroup$

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.

Improve this answer
$\endgroup$
25
$\begingroup$

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.

Improve this answer
$\endgroup$
0
11
$\begingroup$

@gung is absolutely correct suggesting you multidimensional scaling (MDS) as a preliminary 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 (PCoA). 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.

Finally, it is possible to program "K-means for distance matrix input" directly - without calling or writing functions doing PCoA or another metric MDS. We know, that (a) the sum of squared deviations from centroid is equal to the sum of pairwise squared Euclidean distances divided by the number of points; and (b) know how to compute distances between cluster centroids out of the distance matrix; (c) and we further know how Sums-of-squares are interrelated in K-means. All it together makes the writing of the algorithm you want a straightforward and not a complex undertaking. One should remember though that K-means is for Euclidean distances / euclidean space only. Use K-medoids or other methods for non-euclidean distances.

A similar question.

Improve this answer
$\endgroup$
8
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • $\begingroup$ The steps described are nothing less than Principal Coordinates Analysis which I mention in my answer. $\endgroup$
    – ttnphns
    Commented Jul 30, 2012 at 0:52
  • $\begingroup$ Please, exemplify your step 5. Substracting the last (negative) eigenvalue(s) from S matrix elements seem to not help make S positive semidefinite. $\endgroup$
    – ttnphns
    Commented Jul 30, 2012 at 2:26
  • $\begingroup$ @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? $\endgroup$
    – blubb
    Commented Jul 30, 2012 at 9:35
  • $\begingroup$ 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... $\endgroup$
    – ttnphns
    Commented Jul 30, 2012 at 12:03
  • $\begingroup$ ...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. $\endgroup$
    – ttnphns
    Commented Jul 30, 2012 at 12:10
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

I don't know why it is so uncommon in literature, however the solution suggested by @gung and @ttnphns (first projecting your pairwise distances into a Euclidean space using Principal Coordinates Analysis, for example through this package if you use R, and then doing K-means usual way) is simple and doesn't require specialized algorithms. I personally used it here embedded in an optimization framework and it worked fairly well.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.