A K-Means Variation based on Careful Seeding and Constrained Silhouette Coefficients

K-means is well-known clustering algorithm very often used for its simplicity and efficiency. Its properties have been thoroughly investigated. It emerged that K-means heavily depends on the seeding method used to initialize the cluster centroids and that, besides the seeding procedure, it mainly acts as a local refiner of the centroids and can easily become stuck around a local sub-optimal solution of the objective function cost. As a consequence, K-means is often repeated many times, always starting with a different centroids configuration, to increase the likelihood of finding a clustering solution near the optimal one. In this paper, the Hartigan & Wong variation of K-Means (HWKM) is chosen because of its increased probability to ending up near the optimal solution. HWKM is then enhanced with the use of careful seeding methods and by an incremental technique which constrains the movement of points among clusters according to their Silhouette coefficients. The result is HWKM+ which, through a small number of re-starts, is capable of generating a careful clustering solution with compact and well-separated clusters. The current implementation of HWKM+ rests on Java parallel streams. The paper describes the design and development of HWKM+ and demonstrates its abilities through a series of benchmark and real-world datasets.