A heuristic algorithm for solving the minimum sum-of-squares clustering problems

WOS: 000349247800009Clustering is an important task in data mining. It can be formulated as a global optimization problem which is challenging for existing global optimization techniques even in medium size data sets. Various heuristics were developed to solve the clustering problem. The global -means and modified global -means are among most efficient heuristics for solving the minimum sum-of-squares clustering problem. However, these algorithms are not always accurate in finding global or near global solutions to the clustering problem. In this paper, we introduce a new algorithm to improve the accuracy of the modified global -means algorithm in finding global solutions. We use an auxiliary cluster problem to generate a set of initial points and apply the -means algorithm starting from these points to find the global solution to the clustering problems. Numerical results on 16 real-world data sets clearly demonstrate the superiority of the proposed algorithm over the global and modified global -means algorithms in finding global solutions to clustering problems.Australian Research CouncilAustralian Research Council [DP140103213]; Scientific and Technological Research Council of Turkey (TUBITAK)Turkiye Bilimsel ve Teknolojik Arastirma Kurumu (TUBITAK)This paper was written during the visit of Dr. Burak Ordin to the University of Ballarat supported by The Scientific and Technological Research Council of Turkey (TUBITAK). The research by Adil M. Bagirov was supported under Australian Research Council's Discovery Projects funding scheme (Project No. DP140103213). The authors are grateful to two anonymous referees for their criticism and comments which helped the authors to significantly improve the quality of the paper