8
IRUS Total
Downloads

Size matters: cardinality-constrained clustering and outlier detection via conic optimization

File Description SizeFormat 
SizeMattersCardinalityConstrainedClustering.pdfPublished version569.68 kBAdobe PDFView/Open
Title: Size matters: cardinality-constrained clustering and outlier detection via conic optimization
Authors: Rujeerapaiboon, N
Schindler, K
Kuhn, D
Wiesemann, W
Item Type: Journal Article
Abstract: Plain vanilla K-means clustering has proven to be successful in practice, yet it suffers from outlier sensitivity and may produce highly unbalanced clusters. 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-constrainedK-means clustering on the residual dataset, treating the cluster cardinalities as a given input. We cast this problem as a mixed-integer linear program (MILP) that admits tractable semidefinite and linear programming relaxations. We propose deterministic rounding schemes thattransform the relaxed solutions to feasible solutions for the MILP. We also prove that these solutions areoptimal in the MILP if a cluster separation condition holds.
Issue Date: 1-Jan-2019
Date of Acceptance: 22-Jan-2019
URI: http://hdl.handle.net/10044/1/67236
DOI: https://doi.org/10.1137/17M1150670
ISSN: 1052-6234
Publisher: Society for Industrial and Applied Mathematics
Start Page: 1211
End Page: 1239
Journal / Book Title: SIAM Journal on Optimization
Volume: 29
Issue: 2
Copyright Statement: Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
Sponsor/Funder: Engineering & Physical Science Research Council (E
Funder's Grant Number: EP/M028240/1
Keywords: Science & Technology
Physical Sciences
Mathematics, Applied
Mathematics
semidefinite programming
K-means clustering
outlier detection
optimality guarantee
NP-HARDNESS
SEMIDEFINITE
Operations Research
0102 Applied Mathematics
0103 Numerical and Computational Mathematics
Publication Status: Published online
Online Publication Date: 2019-04-30
Appears in Collections:Imperial College Business School