Robust Optimization for Clustering

摘要

In this paper, we investigate the robust optimization for the minimum sum-of squares clustering (MSSC) problem. Each data point is assumed to belong to a box-type uncertainty set. Following the robust optimization paradigm, we obtain a robust formulation that can be interpreted as a combination of MSSC and k-median clustering criteria. A DCA-based algorithm is developed to solve the resulting robust problem. Preliminary numerical results on real datasets show that the proposed robust optimization approach is superior than MSSC and k-median clustering approaches.