K-Means Empty Cluster Example
Consider the
following example for which we want the number of clusters to be 3. The shapes
of the points have no meaning for now. They are just selected to show that
there are actually 2 natural clusters. But we do not know the natural number of
clusters in general before running a K-means algorithm, so in this case assume
we have chosen k to be 3.
And let us
assume that we have chosen points 3, 5, and 6 as our initial cluster centers.
At the end of first iteration points 3, 1, 2, and 7 will be in one cluster. 4
and 5 will be in another cluster. And 6 will be in the last cluster. Note here
that the distance between 3 and 4 is larger than the distance between 4 and 5
and so 4 is assigned to the cluster represented by 5. Before we begin the
second iteration we update the cluster centers and the following picture shows
the centers (approximately) and the clusters at the end of first step.
Now, the
cluster center for the red cluster moved closer to point 4 due to 1, 2, and 7.
And the cluster center for the blue cluster moved away from 5 due to point 4.
In the next iteration point 4 will decide that it is closer to the red cluster
and point 5 will decide that it is closer to the green cluster. This will cause
blue cluster to be empty as shown below.