A Binary Optimization approach for constrained K-Means clustering

Huu M. Le, Anders Eriksson, Thanh-Toan Do, Michael Milford

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearch

1 Citation (Scopus)


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.

Original languageEnglish
Title of host publicationComputer Vision – ACCV 2018
Subtitle of host publication14th Asian Conference on Computer Vision Perth, Australia, December 2–6, 2018 Revised Selected Papers, Part IV
EditorsC.V. Jawahar, Hongdong Li, Greg Mori, Konrad Schindler
Place of PublicationCham Switzerland
Number of pages16
ISBN (Electronic)9783030208707
ISBN (Print)9783030208691
Publication statusPublished - 2019
Externally publishedYes
EventAsian Conference on Computer Vision 2018 - Perth, Australia
Duration: 2 Dec 20186 Dec 2018
Conference number: 14th
https://link.springer.com/book/10.1007/978-3-030-20887-5 (Proceedings)

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceAsian Conference on Computer Vision 2018
Abbreviated titleACCV 2018
Internet address

Cite this