11
$\begingroup$

This has been inside my mind for at least a few hours. I was trying to find an optimal k for the output from the k-means algorithm (with a cosine similarity metric) so I ended up plotting the distortion as a function of the number of clusters. My dataset is a collection of 800 documents in a 600-dimensional space.

From what I understand, finding the knee point or the elbow point on this curve should tell me at least approximately the number of clusters I need to put my data into. I put the graph below. The point at which the red vertical line was drawn was obtained by using the maximum second derivative test. After doing all this, I was stuck at something much simpler: what does this graph tell me about the dataset?

Does it tell me that it is not worth clustering and that my documents lack structure or that I need to set a very high k? One strange thing though is that even with low k, I am seeing similar documents being clustered together so I am not sure why I am getting this curve. Any thoughts?

enter image description here

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ What I honestly don't understand is how you was able to employ k-means clustering with proximity matrix input (and that being cosine!). K-means clustering needs raw data (objects X variables) input and internally operates on euclidean distance. $\endgroup$ – ttnphns Jul 13 '11 at 8:46
  • 2
    $\begingroup$ @ttnphns: I hope I understood your point but to the best of my knowledge, we can use any distance metric with k-means isn't it? I am doing this in Python but looks like there is even a library available for R: cran.r-project.org/web/packages/skmeans/index.html The input was not a proximity matrix but rather a terms x document obtained after performing singular vector decomposition. Please correct me if I am mistaken. $\endgroup$ – Legend Jul 13 '11 at 17:53
  • $\begingroup$ Spherical k-means clustering, based on cosine measure, is new to me, I have to admit. I hope to read more about it one day. $\endgroup$ – ttnphns Jul 13 '11 at 18:58
  • $\begingroup$ @ttnphns: Thank you for getting back. Just wanted to make sure I wasn't using apples and oranges together :) $\endgroup$ – Legend Jul 13 '11 at 19:27
  • $\begingroup$ Unmodified k-means is only sensible for $L_p$-Norms. Because it computes mean vectors and that isn't an appropriate ML-estimation for other distance functions. $\endgroup$ – Anony-Mousse Dec 6 '11 at 9:25
12
$\begingroup$

In most situations, I would have thought that dsuch a plot basically means that there is no cluster structure in the data. However, clustering in very high dimensions such as this is tricky as for the Euclidean distance metric all distances tend to the same as the number of dimensions increases. See this Wikipedia page for references to some papers on this topic. In short, it may just be the high-dimensionality of the dataset that is the problem.

This is essentially "the curse of dimensionality", see this Wikipedia page as well.

A paper that may be of interest is Sanguinetti, G., "Dimensionality reduction of clustered datsets", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30 no. 3, pp. 535-540, March 2008 (www). Which is a bit like an unsupervised version of LDA that seeks out a low-dimensional space that emphasises the cluster structure. Perhaps you could use that as a feature extraction method before performing k-means?

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Oops sorry. I should have mentioned that I am using cosine similarity. $\endgroup$ – Legend Jul 13 '11 at 8:24
  • $\begingroup$ I think it is quite likely that the curse of dimensionality also applies to the cosine similarity. It basically says that you need (worst case) exponentially more patterns to define a distribution as the number of dimensions increases. In clustering what you are effectively doing is identifying distributions representing sub-populations, so clustering in high dimensions is likely to be inherently tricky. $\endgroup$ – Dikran Marsupial Jul 13 '11 at 8:29
  • $\begingroup$ +1 Thank you for the link. I will go through it and get back. I applied SVD on my original matrix before applying k-means to reduce the number of dimensions. $\endgroup$ – Legend Jul 13 '11 at 17:56
3
$\begingroup$

How exactly do you use cosine similarity? Is this what is refered to as spherical K-means? Your data set is quite small, so I would try to visualise it as a network. For this it is natural to use a similarity (indeed, for example the cosine similarity or Pearson correlation), apply a cut-off (only consider relationships above a certain similarity), and view the result as a network in for example Cytoscape or BioLayout. This can be very helpful to get a feeling for the data. Second, I would compute the singular values for your data matrix, or the eigenvalues of an appropriately transformed and normalised matrix (a document-document matrix obtained in some form). Cluster structure should (again) show up as a jump in the ordered list of eigenvalues or singular values.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ +1 Thank you for the pointers. I was not aware of Cytoscape. I will try that. And yes, it looks like k-means with cosine similarity is referred to as Spherical k-means. I applied this k-means after applying SVD and reducing the number of dimensions. The way I reduced the number of dimensions was to use the variance rule (pick the singular values that contribute to 95% of the variance in the original data). $\endgroup$ – Legend Jul 13 '11 at 17:58
  • $\begingroup$ If you don't mind, could you point to a tutorial that explains how to do this (or at least something like this). Once I generate the matrix, do I just export it and then import it into Cytoscape and perform what you suggested? What I am curious about is whether Cytoscape has built-in methods for cosine similarity or do I have to precompute some data format and give it as an input? $\endgroup$ – Legend Jul 13 '11 at 18:08
  • $\begingroup$ When I work with those programs, I compute all pairwise similarities externally, filter by threshold, and produce a file with format <label1> <label2> <similarity>. Either should be able to read that input. In BioLayout it has to have a .txt suffix I think; in CytoScape use 'import from table'. $\endgroup$ – micans Jul 13 '11 at 18:38
  • $\begingroup$ Understood. I will do that and get back soon. Thank you once again. $\endgroup$ – Legend Jul 13 '11 at 18:42
  • $\begingroup$ Sorry for the dumb question but I did format my data as <label1> <label2> <similarity> but am not able to figure out how to import it exactly. I did File->Import->Network from Table and selected my source and target columns. I left the interaction as default. But how am I supposed to import edge weights along with the edges? Would you have any suggestions please? $\endgroup$ – Legend Jul 13 '11 at 21:25
2
$\begingroup$

Generally yes, k-means might converge to very distinct solutions that might be judged as unsuitable. This happens in particular for clusters with irregular shapes.

That get more intuition you could also try another visualization approach: For k-means you could visualize several runs with k-means using Graphgrams (see the WEKA graphgram package - best obtained by the package manager or here. An introduction and examples can also be found here.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

If I understand the graph correctly it is a plot of the number of clusters, K on the x-axis and the within clusters distance on the y-axis?

Because your K-means objective function is to minimise the WCSS, this plot should always be monotonically decreasing. As you add more clusters, the distance between points in the cluster will always decrease. This is the fundamental problem of model selection, so you need to employ a bit more sophistication.

Perhaps try the Gap statistic: www-stat.stanford.edu/~tibs/ftp/gap.ps or others like it.

Furthermore, you may find that K-means isn't the right tool for the job. How many clusters do you expect to find? Using the variance rule for dimensionality reduction for clustering is not appropriate. See this paper for when projecting onto the first K-1 PCs is an appropriate preprocessing measure: http://people.csail.mit.edu/gjw/papers/jcss.ps

You can quickly see if this is the right thing to do by plotting the projection onto the first two principal components. If there is a clear separation then K-means should be ok, if not you need to look into something else. Perhaps K-subspaces or other subspace clustering methods. Bare in mind these methods apply for Euclidean distance. I'm not sure how this changes for cosine.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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