Using real data means as centroids for clustering Suppose we have a data set generated from k different distributions.
In k-means, the data classification step (in which we associate each data point to the nearest centroid) uses the current centroids to generate new data clusters. We can say that the better the centroids positions are, the better the classification is.
My doubts comes when we talk about the relation between centroids and the real data means. We can't say that k-means will always find the real means, but the resulting centroids after a full execution of this method will certainly be close to them.
Considering that the classification step means only associating each point to the closest centroid, can we say that the real means are the average optimal centroid positions for data classification (classifying data only once, with no centroid update)?
I thought the real mean of a distribution is the point that minimizes the sum of squared error when we generate a high amount of data points with that distribution, so I guessed it would be reasonable to say that.
I would appreciate if you guys could point me any references about this point. Thanks in advance!
 A: It seems like you are asking "When does k-means converge to the true set of cluster centroids?"
The limit on k-means' (or any clustering algorithm's) performance can be analyzed in terms of two factors: 1) separation between the true clusters and 2) the amount of data in the sample. 
If the true clusters are not well separated or not enough sample data exists, then a clustering algorithm will not be able to converge to the correct result.
See Srebro et. al. and their references for a more-detailed explanation.
A: First, to be clear, the term "centroid" is just another way of saying the "mean". K-means clustering, when performed in accordance to its definition, should always be redefining the mean of the cluster exactly as the real mean of all the data points that were categorized into that cluster on that iteration. It seems like your point of confusion is on the re-classification step, but I'm not completely sure what your question is. 
Yes, when re-classifying, you are using the mean of one distinct set of points in order to define a cluster of another distinct set of points - whose mean will likely be different from the mean of the first set of points. But these centroids/means are always the correct "real" mean of a particular set of points (after all, that's how you find these points), except perhaps your first assignments.
I hope that helps, and that I'm not just restating a bunch of stuff you may already know. Perhaps try to clarify your question a little more.
There are other algorithms similar to k-means that don't always necessarily use the means - like k-medians, for example.
