Are there cases where there is no optimal k in k-means? 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?

 A: 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.
A: 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.
A: 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?
A: 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.
