I have a question regarding the **kmeans algorithm**. I know kmeans is a randomized algorithm, but how random is it and what results can I expect. Suppose you have clustered a dataset into $4$ clusters, where each point has identity $1$, $2$, $3$, or $4$ (which tells you what cluster it belongs to). You then perform a second clustering on the same dataset with the same criteria.

1. Will all the points in a specific cluster say during the first clustering be in the same cluster the next time you apply the kmeans algorithm?
2. If not, will they most likely be in the same cluster and is there some measure for this likelihood?

By some output I received in R, I believe that 1. does not hold as I get different cluster sizes for different runs on the same dataset.

All help is greatly appreciated!