18
$\begingroup$

I am trying to perform document-level clustering. I constructed the term-document frequency matrix and I am trying to cluster these high dimensional vectors using k-means. Instead of directly clustering, what I did was to first apply LSA's (Latent Semantic Analysis) singular vector decomposition to obtain the U,S,Vt matrices, selected a suitable threshold using the scree plot and applied clustering on the reduced matrices (specifically Vt because it gives me a concept-document information) which seemed to be giving me good results.

I've heard some people say SVD (singular vector decomposition) is clustering (by using cosine similarity measure etc.) and was not sure if I could apply k-means on the output of SVD. I thought it was logically correct because SVD is a dimensionality reduction technique, gives me a bunch of new vectors. k-means, on the other hand, will take the number of clusters as the input and divide these vectors into the specified number of clusters. Is this procedure flawed or are there ways in which this can be improved? Any suggestions?

Improve this question
$\endgroup$
2
  • $\begingroup$ good question. personally i have been thinking about these stuff. but don't have a good answer. $\endgroup$
    – suncoolsu
    Jul 10, 2011 at 2:05
  • 1
    $\begingroup$ There are methods that simultaneously perform dimensionality reduction and clustering. These methods seek an optimally chosen low-dimensional representation so as to facilitate the identification of clusters. For example, see clustrd package in R and the associated references. $\endgroup$
    – Nat
    Oct 3, 2018 at 19:46

2 Answers 2

Reset to default
8
$\begingroup$

This is by no means a complete answer, the question you should be asking is "what kind of distances are preserved when doing dimensionality reduction?". Since clustering algorithms such as K-means operate only on distances, the right distance metric to use (theoretically) is the distance metric which is preserved by the dimensionality reduction. This way, the dimensionality reduction step can be seen as a computational shortcut to cluster the data in a lower dimensional space. (also to avoid local minima, etc)

There are many subtleties here which I will not pretend to understand, (local distances vs global distances, how relative distances are distorted, etc) but I think this is the right direction to to think about these things theoretically.

Improve this answer
$\endgroup$
2
  • $\begingroup$ +1 That's a very interesting take on the question. In that case, can Euclidean be considered one such metric? As the dimensionality is reduced, the points are projected into a lower dimensional space but that could mean the notion of distance can be lost. I am having a hard time to see how distances can be preserved when using reductions like this. $\endgroup$
    – Legend
    Jul 11, 2011 at 1:56
  • 1
    $\begingroup$ I think this answer is basically right. You want to find some embedding in a smaller space that preserves distances (for some notion of distance). Two good algorithms to check out are Isomap and Locally-Linear Embedding. The "neighborhood preservation" seems like a good approach if your goal is clustering. $\endgroup$
    – Stumpy Joe Pete
    Sep 1, 2012 at 4:59
6
$\begingroup$

In reply to your title "When do we combine dimensionality reduction with clustering?" rather than the full question. One possible reason is obvious: when we want to secure agaist outliers. K-means algo, if without initial centers hint, takes k most apart points in the cloud as initial centers, and right these are likely to be outliers. Preacting by PCA neutralizes outliers which lie along junior components - by projecting them onto the few senior components which are retained in PCA.

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.