Robust semi-supervised clustering with polyhedral and circular uncertainty


DİNLER D. , TURAL M. K.

NEUROCOMPUTING, cilt.265, ss.4-27, 2017 (SCI İndekslerine Giren Dergi) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 265
  • Basım Tarihi: 2017
  • Doi Numarası: 10.1016/j.neucom.2017.04.073
  • Dergi Adı: NEUROCOMPUTING
  • Sayfa Sayıları: ss.4-27

Özet

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.