18
$\begingroup$

I want to cluster a massive dataset for which I have only the pairwise distances. I implemented a k-medoids algorithm, but it's taking too long to run so I would like to start by reducing the dimension of my problem by applying PCA. However, the only way I know to perform this method is using the covariance matrix which I don't have in my situation.

Is there a way to apply PCA knowing the pairwise distances only?

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ So, you have a big square matrix of distances between the points you want to cluster. (BTW what distance? Euclidean?) What makes you think that it is the number of dimensions these points span, and not the number of points themselves (cardinality), that impedes the clustering? $\endgroup$
    – ttnphns
    Commented Feb 24, 2014 at 17:50
  • 1
    $\begingroup$ The number of points is not "very big" (few thousands). The distance I am using is the pearson correlation between these points $\endgroup$
    – bigTree
    Commented Feb 25, 2014 at 8:19
  • 2
    $\begingroup$ But my question was: do you really want to reduce dimensionality (and if yes, why?) or cardinality (the number of points)? Because your question is unclear. $\endgroup$
    – ttnphns
    Commented Feb 25, 2014 at 10:46
  • 1
    $\begingroup$ @ttnphns: Oh boy, of course I simply mistyped my previous comment. In order to remove the possible confusion, I will now delete that comment and repeat what I said here with correct wording: "Reducing cardinality in this case means making your $N \times N$ distance matrix smaller (decreasing $N$). Reducing dimensionality means making it lower rank, without changing $N$. PCA amounts to the latter and does not really help with the former goal". $\endgroup$
    – amoeba
    Commented Feb 25, 2014 at 11:49
  • 1
    $\begingroup$ I think that the easiest way for you is to use such (a)clustering method or (b) such its implementation or (c) such strong (enough RAM) computer that will take and classify 6000 objects (I don't know why your medoid program finds it difficult. 6000 is large, but not very large.). Some methods (such as K-means) requires objects X features data. You could create such data out of objects distance matrix via metric MDS (if, again, your computer/MDS program will permit 6000 objects). $\endgroup$
    – ttnphns
    Commented Feb 25, 2014 at 14:44

4 Answers 4

Reset to default
14
$\begingroup$

Update: I entirely removed my original answer, because it was based on a confusion between Euclidean distances and scalar products. This is a new version of my answer. Apologies.

If by pairwise distances you mean Euclidean distances, then yes, there is a way to perform PCA and to find principal components. I describe the algorithm in my answer to the following question: What's the difference between principal components analysis and multidimensional scaling?

Very briefly, the matrix of Euclidean distances can be converted into a centered Gram matrix, which can be directly used to perform PCA via eigendecomposition. This procedure is known as [classical] multidimensional scaling (MDS).

If your pairwise distances are not Euclidean, then you cannot perform PCA, but still can perform MDS, which is not going to be equivalent to PCA anymore. However, in this situation MDS is likely to be even better for your purposes.

Improve this answer
$\endgroup$
4
  • $\begingroup$ The distance I am using is a correlation (Pearson correlation) and is therefore not the Euclidian distance. Would that work similarly? $\endgroup$
    – bigTree
    Commented Feb 25, 2014 at 8:20
  • 1
    $\begingroup$ @bigTree: If it's not Euclidean distance, there is no way you can run PCA. However, you can use multi-dimensional scaling which is a dimensionality reduction technique that uses precisely the matrix of pairwise distances (it can be any distance). Another note: under certain assumptions about the original data-points (which you don't have) correlations can be transformed into Euclidean distances. Assumptions are: (1) having zero mean, (2) having fixed, e.g. unit, length. Is it by any chance true for your data? $\endgroup$
    – amoeba
    Commented Feb 25, 2014 at 11:37
  • $\begingroup$ None of these is true or my data, but I'll try MDS thanks $\endgroup$
    – bigTree
    Commented Feb 25, 2014 at 14:09
  • 1
    $\begingroup$ can't you use kernel PCA? I imagine that would need only pairwise dot products, but I don't know much about the issue, so I don't know if it makes sense $\endgroup$
    – rep_ho
    Commented Nov 22, 2016 at 21:54
6
$\begingroup$

PCA with a distance matrix exists, and it is called Multi-dimensional scaling (MDS). You can learn more on wikipedia or in this book.

You can do it in R with mds function cmdscale. For a sample x, you can check that prcomp(x) and cmdscale(dist(x)) give the same result (where prcomp does PCA and dist just computes euclidian distances between elements of x)

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

This looks like a problem that spectral clustering could be applied to. Since you have the pairwise distance matrix, you can define a fully connected graph where each node has N connections, corresponding to its distance from every other node in the graph. From this, you can compute the graph Laplacian (if this sounds scary, don't worry--it's an easy computation) and then take eigenvectors of the smallest eigenvalues (this is where it differs from PCA). If you take 3 eigenvectors, for example, you will then have an Nx3 matrix. In this space, the points should (hopefully) be well-separated because of some neat graph theory which suggests that this is an optimal cut for maximizing flow (or distance, in this case) between clusters. From there, you could use a k-means or similar algorithm to cluster in 3-space. I recommend checking out this awesome walkthrough for more insight:

http://arxiv.org/abs/0711.0189

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

The pairwise distances also form a square matrix just like the co-variance matrix. PCA is just SVD (http://en.wikipedia.org/wiki/Singular_value_decomposition) applied to the co-variance matrix. You should still be able to do dimension reduction using SVD on your data. I'm not exactly sure how to interpret your output but it is definitely something to try. You could use clustering methods such as k-means or hierarchical clustering. Also take a look at other dimension reduction techniques such as multidimensional scaling. What are you trying to get out of your clusters?

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Andrew Cassidy's answer is actually valid. If your distance measure is pearson correlation, you're just a standardizing factor "too far" from actually having a covariance matrix. Thus, applying SVD is basically the same thing as doing PCA. $\endgroup$
    – Matthew Anthony
    Commented Nov 22, 2016 at 18:15

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.