Decomposition Methods for Robustified k-Means Clustering Problems: If Less Conservative Does Not Mean Less Bad

Jan Pablo Burgard(burgardjuni-trier.de)
Carina Moreira Costa(costauni-trier.de)
Schmidt Martin(martin.schmidtuni-trier.de)

Abstract: k-means clustering is a classical method of unsupervised learning with the aim of partitioning a given number of measurements into k clusters. In many modern applications, however, this approach suffers from unstructured measurement errors because the k-means clustering result then represents a clustering of the erroneous measurements instead of retrieving the true underlying clustering structure. We resolve this issue by applying techniques from robust optimization to hedge the clustering result against unstructured errors in the observed data. To this end, we derive the strictly and Gamma-robust counterparts of the k-means clustering problem. Since the nominal problem is already NP-hard, global approaches are often not feasible in practice. As a remedy, we develop tailored alternating direction methods by decomposing the search space of the nominal as well as of the robustified problems to quickly obtain feasible points of good quality. Our numerical results reveal an interesting feature: the less conservative Gamma-approach is clearly outperformed by the strictly robust clustering method. In particular, the strictly robustified clustering method is able to recover clusterings of the original data even if only erroneous measurements are observed.

Keywords: k-means clustering, Alternating direction methods, Robust optimization, Strict robustness, Gamma-robustness

Category 1: Robust Optimization

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation:

Download: [PDF]

Entry Submitted: 05/17/2020
Entry Accepted: 05/17/2020
Entry Last Modified: 05/17/2020

Modify/Update this entry