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

2017-05-22 · Napat Rujeerapaiboon, Kilian Schindler, Daniel Kuhn, Wolfram Wiesemann

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-constrained K-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 that transform the relaxed solutions to feasible solutions for the MILP. We also prove that these solutions are optimal in the MILP if a cluster separation condition holds.

📄 PDF Abstract BibTeX arXiv:1705.07837

Code (0)

등록된 구현이 없습니다.

Tasks

ClusteringConstrained ClusteringOutlier Detection

Methods 이 논문이 사용한 방법론

k-Means Clustering k-Means Clustering is a clustering algorithm that divides a training set into $k$ different clusters of examples that are near each other. It works by initializing $k$…

Global Optimization for Cardinality-constrained Minimum Sum-of-Squares Clustering via Semidefinite Programming

2022-09-19 · Veronica Piccialli, Antonio M. Sudoso

The minimum sum-of-squares clustering (MSSC), or k-means type clustering, has been recently extended to exploit prior knowledge on the cardinality of each cluster. Such knowledge is used to increase performance as well a…

Clustering global-optimization

Constrained Clustering: General Pairwise and Cardinality Constraints

2019-07-24 · Adel Bibi, Ali Alqahtani, Bernard Ghanem

We study constrained clustering, where constraints guide the clustering process. In existing works, two categories of constraints have been widely explored, namely pairwise and cardinality constraints. Pairwise constrain…

Clustering Constrained Clustering

Dynamic Submodular Maximization

2020-12-01 · NeurIPS 2020 12 · Morteza Monemizadeh

One of the basic primitives in the class of submodular optimization problems is the submodular maximization under a cardinality constraint. Here we are given a ground set $V$ that is endowed with a monotone submodular fu…

Clustering Combinatorial Optimization Feature Compression Recommendation Systems+1

Tight FPT Approximation for Constrained k-Center and k-Supplier

2021-10-27 · Dishant Goyal, Ragesh Jaiswal

In this work, we study a range of constrained versions of the $k$-supplier and $k$-center problems such as: capacitated, fault-tolerant, fair, etc. These problems fall under a broad framework of constrained clustering. A…

Clustering Constrained Clustering

On Learning to Solve Cardinality Constrained Combinatorial Optimization in One-Shot: A Re-parameterization Approach via Gumbel-Sinkhorn-TopK

2021-09-29 · Runzhong Wang, Li Shen, Yiting Chen, Junchi Yan 외

Cardinality constrained combinatorial optimization requires selecting an optimal subset of $k$ elements, and it will be appealing to design data-driven algorithms that perform TopK selection over a probability distributi…

Combinatorial Optimization One-Shot Learning Self-Supervised Learning