Max stable set problem to found the initial centroids in clustering problem

Awatif Karim (University Sidi Mohamed Ben Abdellah)
Chakir Loqman (University Sidi Mohamed Ben Abdellah)
Youssef Hami (University Abd El Malek Essaadi)
Jaouad Boumhidi (University Sidi Mohamed Ben Abdellah)

Indonesian Journal of Electrical Engineering and Computer Science
Vol 25, No 1: January 2022

In this paper, we propose a new approach to solve the document-clustering using the K-Means algorithm. The latter is sensitive to the random selection of the k cluster centroids in the initialization phase. To evaluate the quality of K-Means clustering we propose to model the text document clustering problem as the max stable set problem (MSSP) and use continuous Hopfield network to solve the MSSP problem to have initial centroids. The idea is inspired by the fact that MSSP and clustering share the same principle, MSSP consists to find the largest set of nodes completely disconnected in a graph, and in clustering, all objects are divided into disjoint clusters. Simulation results demonstrate that the proposed K-Means improved by MSSP (KM_MSSP) is efficient of large data sets, is much optimized in terms of time, and provides better quality of clustering than other methods.