Robust semi-supervised clustering with polyhedral and circular uncertainty


NEUROCOMPUTING, vol.265, pp.4-27, 2017 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 265
  • Publication Date: 2017
  • Doi Number: 10.1016/j.neucom.2017.04.073
  • Journal Name: NEUROCOMPUTING
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.4-27
  • Middle East Technical University Affiliated: Yes


We consider a semi-supervised clustering problem where the locations of the data objects are subject to uncertainty. Each uncertainty set is assumed to be either a closed convex bounded polyhedron or a closed disk. The final clustering is expected to be in accordance with a given number of instance level constraints. The objective function considered minimizes the total of the sum of the violation costs of the unsatisfied instance level constraints and a weighted sum of squared maximum Euclidean distances between the locations of the data objects and the centroids of the clusters they are assigned to. Given a cluster, we first consider the problem of computing its centroid, namely the centroid computation problem under uncertainty (CCPU).. We show that the CCPU can be modeled as a second order cone programing problem and hence can be efficiently solved to optimality. As the CCPU is one of the key ingredients of the several algorithms considered in this paper, a subgradient algorithm is also adopted for its faster solution. We then propose a mixed-integer second order cone programing formulation for the considered clustering problem which is only able to solve small-size instances to optimality. For larger instances, approaches from the semi-supervised clustering literature are modified and compared in terms of computational time and quality. (C) 2017 Elsevier B.V. All rights reserved.