Degeneracy on K-means clustering

The local search algorithm for K-means clustering could be degenerated. In other words, it could finish at a solution with less clusters than desired. These degenerate solutions impact the algorithm's quality and speed. In this paper I show that the local search algorithm for K-means clustering degenerates with some counter examples. I then suggest a method to remove degeneracy during the execution of the K-means algorithm. I also provide computational results for some familiar datasets to compare the solutions after removing degeneracy.