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

ORDİN B. , Bagirov A. M.

JOURNAL OF GLOBAL OPTIMIZATION, cilt.61, ss.341-361, 2015 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 61 Konu: 2
  • Basım Tarihi: 2015
  • Doi Numarası: 10.1007/s10898-014-0171-5
  • Sayfa Sayıları: ss.341-361


Clustering 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.