Robust semi supervised clustering with polyhedral and circular uncertainty

Dinler, Derya
Tural, Mustafa Kemal
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.
Citation Formats
D. Dinler and M. K. Tural, “Robust semi supervised clustering with polyhedral and circular uncertainty,” presented at the EURO 2016 :28th European Conference on Operational Research, July 3-6 2016, Poznań, Poland, 2016, Accessed: 00, 2021. [Online]. Available: