Result of K-Means Algorithm Not Desired

Question

I am learning about K-means algorithm, and I have generated a dataset with 150000 data points, with 10000 points per cluster. (Scatter plot at the bottom)

When I run K-means on the dataset, I first randomly pick 15 data points as initial centers, and then use the traditional iterative approach to update the centers until convergence. However, this gives undesired results, a sample as follows:

Cluster 0: 14.136004, 48.625093
Cluster 1: 82.353156, 43.582929
Cluster 2: 45.823547, 61.650882
Cluster 3: 58.467780, 90.994505
Cluster 4: 79.734026, 78.028310
Cluster 5: 58.467912, 91.018907
Cluster 6: 89.781302, 26.638219
Cluster 7: 75.079899, 97.764001
Cluster 8: 63.669296, 73.583218
Cluster 9: 41.334973, 19.812627
Cluster 10: 75.589260, 97.997850
Cluster 11: 73.342196, 63.601545
Cluster 12: 81.802223, 43.727663
Cluster 13: 93.317351, 91.788683
Cluster 14: 82.203258, 44.138953

I have two questions:

1. Note that Cluster 1, 12, and 14 correspond to the same cluster, yet the algorithm converges there. Is this normal for the outcome of K-means algorithm?

2. Is it possible that when we re-calculate the location of a new center, the set of points we average over is empty? i.e. for all data points, they are nearer to some other center than the particular center we try to calculate?

Answer 1

1. Yes, perfectly normal. I don't think this can be avoided if you choose random starting points.

2. Yes, in principle. In R, if this happens and you try to run k-means clustering, it will throw an error as in this example:

   x <- matrix(c(1,2,1.1,1.1,1,1,2,1.1,1,1.1), nc=2) kmeans(x, 4, centers=matrix(rnorm(8), nc=2)) -> out # random starting points Error: empty cluster: try a better set of initial centers

However, I don't think this can happen if you assign the cluster centres to be random points in the dataset, which is the default behaviour of the kmeans function in R.

x <- matrix(c(1,2,1.1,1.1,1,1,2,1.1,1,1.1), nc=2)
kmeans(x, 4)