A Binary Optimization Approach for Constrained K-Means Clustering



Le, Huu, Eriksson, Anders, Do, Thanh-Toan ORCID: 0000-0002-6249-0848 and Milford, Michael
(2019) A Binary Optimization Approach for Constrained K-Means Clustering. .

Access the full-text of this item by clicking on the Open Access link.

Abstract

K-Means clustering still plays an important role in many computer vision problems. While the conventional Lloyd method, which alternates between centroid update and cluster assignment, is primarily used in practice, it may converge to solutions with empty clusters. Furthermore, some applications may require the clusters to satisfy a specific set of constraints, e.g., cluster sizes, must-link/cannot-link. Several methods have been introduced to solve constrained K-Means clustering. Due to the non-convex nature of K-Means, however, existing approaches may result in sub-optimal solutions that poorly approximate the true clusters. In this work, we provide a new perspective to tackle this problem by considering constrained K-Means as a special instance of Binary Optimization. We then propose a novel optimization scheme to search for feasible solutions in the binary domain. This approach allows us to solve constrained K-Means clustering in such a way that multiple types of constraints can be simultaneously enforced. Experimental results on synthetic and real datasets show that our method provides better clustering accuracy with faster run time compared to several existing techniques.

Item Type: Conference or Workshop Item (Unspecified)
Depositing User: Symplectic Admin
Date Deposited: 18 Feb 2020 10:39
Last Modified: 19 Jan 2023 00:02
DOI: 10.1007/978-3-030-20870-7_24
Open Access URL: https://arxiv.org/abs/1810.10134
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3075414