K-mean clustering with unknown k How do I perform k-mean clustering with unknown k? I also need to provide a confidence interval for k. I am thinking in the line of putting a Poisson prior on k. Does that make sense? Does there exist any research on this topic?
Updated question: 
I have multinomial discrete data - yes/no/maybe. 1000 question answered by 100 people. I have to find number of distinct groups, and a CI for that number.
 A: When you do k-means, it should be noted that the more the number of clusters you consider, the better your fit necessarily is (to understand why note that the more the number of clusters, the closer you are going to be to one of the centers)
There is no theory behind how to pick k in k-means. It is more a heuristic. What people generally do is they keep increasing the number of clusters till they notice an "elbow" in the MSE improvement i.e. they keep including clusters until they find a cluster n such that the fit obtained on using n+1 clusters is not substantially better than the fit obtained using n clusters
A real tricky situation is when there is no clear elbow, in which case other (equally hand wavy) heuristics are used to infer k. 
I hope this convinces you that the question as it stands makes no sense.
A: You can use a quality mesure of k to choose it. 
The state of the art internal evaluation method (based on data used for clustering) is the "silhouette coefficient"
The silhouette coefficient is a value between -1 and 1, mesuring how similar an object is to its own cluster (cohesion) compared to other clusters (separation).
The silhouette coefficient for a point i is defined as 
(
the lowest average dissimilarity from i to any cluster other than that including i,
minus
the average of the dissimilarity from i to all points in its cluster
) divided by the max of both.
Consider dissimilarity as a distance.
The best k should be giving the best silhouette coefficient 
A confidence interval might be linked to the difference between the silhouette coef. of the best two K ...
Regarding variables including discrete data or not, it should be normalized before clustering, that is, converted into values on a comparable scale.
External evaluation methods might give better result and confidance but I can't say ...but would need to provide a reference dataset.
