1
$\begingroup$

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!

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I do not understand your question. Yes, k-means uses means, i.e. least squares estimators. If your data is generated by k distributions that have the same variance and are well separated, k-means will likely converge to the best (as in: least squares) estimation of the true cluster centers. In reality, your data will however not be this simple. $\endgroup$
    – Has QUIT--Anony-Mousse
    Feb 15, 2014 at 18:42

2 Answers 2

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I talked about k-means just to give an example, but I'll try to clarify my question without using it. Consider k distributions with k different means. If I used the real means of the distributions (the means used to generate the data points) and do ONE classification step (associating each data point to the nearest mean) I would have a classification of the data. This can possibly not be the best classification, but in average (classifying many data sets generated with the same distribution and mean, and specifically comparing to the average of k-means results), would it be? $\endgroup$
    – Chesco
    Feb 16, 2014 at 4:17
  • $\begingroup$ What do you mean by "best classification"? Remember that k-means is a method used for clustering, not classification, and we could never guarantee a perfect clustering into some hidden classifications (say you're generating some normal distributions with set mean/variance) because there is no way to be certain. I feel like I'm not getting to whatever question you have though, and I feel like the answer to this question is "yes" - but it still doesn't make sense - perhaps motivation to the question may help. $\endgroup$
    – Dave
    Mar 2, 2014 at 7:23
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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