Capacitated Clustering via Majorization-Minimization and Collaborative Neurodynamic Optimization.

Abstract

This paper addresses capacitated clustering based on majorization-minimization and collaborative neurodynamic optimization (CNO). Capacitated clustering is formulated as a combinatorial optimization problem. Its objective function consists of fractional terms with intra-cluster similarities in their numerators and cluster cardinalities in their denominators as normalized cluster compactness measures. To obviate the difficulty in optimizing the objective function with factional terms, the combinatorial optimization problem is reformulated as an iteratively reweighted quadratic unconstrained binary optimization problem with a surrogate function and a penalty function in a majorization-minimization framework. A clustering algorithm is developed based on CNO for solving the reformulated problem. It employs multiple Boltzmann machines operating concurrently for local searches and a particle swarm optimization rule for repositioning neuronal states upon their local convergence. Experimental results on ten benchmark datasets are elaborated to demonstrate the superior clustering performance of the proposed approaches against seven baseline algorithms in terms of 21 internal cluster validity criteria.