ON SOME INCREMENTAL ALGORITHMS FOR THE MINIMUM SUM-OF-SQUARES CLUSTERING PROBLEM. PART 1: ORDIN AND BAGIROV'S INCREMENTAL ALGORITHM

摘要

Solution methods for the minimum sum-of-squares clustering (MSSC) problem are analyzed and developed in this paper. Based on the DCA (Difference-of-Convex functions Algorithms) in DC programming and recently established qualitative properties of the MSSC problem [11], we suggest several improvements of the incremental algorithms of Ordin and Bagirov [23] and of Bagirov [4]. Properties of the new algorithms are obtained and preliminary numerical tests of those on real-world databases are shown. Finite convergence, convergence, and the rate of convergence of solution methods for the MSSC problem are presented for the first time in our paper. This Part 1 is devoted to the incremental heuristic clustering algorithm of Ordin and Bagirov and the modified version proposed herein.