Size Matters: Cardinality-Constrained Clustering and Outlier Detection via Conic Optimization

Plain vanilla K-means clustering is prone to produce unbalanced clusters and suffers from outlier sensitivity. To mitigate both shortcomings, we formulate a joint outlier-detection and clustering problem, which assigns a prescribed number of datapoints to an auxiliary outlier cluster and performs cardinality-constrained K-means clustering on the residual dataset. We cast this problem as a mixed-integer linear program (MILP) that admits tractable semidefinite and linear programming relaxations. We propose deterministic rounding schemes that transform the relaxed solutions to high quality solutions for the MILP. We prove that these solutions are optimal in the MILP if a cluster separation condition holds. To our best knowledge, we propose the first tractable solution scheme for the joint outlier-detection and clustering problem with optimality guarantees.


Published in:
SIAM Journal on Optimization, 29, 2, 1211-1239
Year:
2019
Keywords:
Note:
Available from Optimization Online
Laboratories:




 Record created 2017-05-23, last modified 2019-06-04

External link:
Download fulltext
URL
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)