A binary linear programming-based k-means algorithm for clustering with must-link and cannot-link constraints

Baumann, Philipp (2020). A binary linear programming-based k-means algorithm for clustering with must-link and cannot-link constraints. In: 2020 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM) (pp. 324-328). IEEE 10.1109/IEEM45057.2020.9309775

Text A_Binary_Linear_Programming-Based_K-Means_Algorithm_For_Clustering_with_Must-Link_and_Cannot-Link_Constraints.pdf - Published Version Restricted to registered users only Available under License Publisher holds Copyright. Download (4MB)

Clustering is probably the most extensively studied problem in unsupervised learning. Traditional clustering algorithms assign objects to clusters exclusively based on features of the objects. Constrained clustering is a generalization of traditional clustering where additional information about a dataset is given in the form of constraints. It has been shown that the clustering accuracy can be improved substantially by accounting for these constraints. We consider the constrained clustering problem where additional information is given in the form of must-link and cannot-link constraints for some pairs of objects. Various algorithms have been developed for this specific clustering problem. We propose a binary linear programming-based k-means approach that can consider must-link and cannot-link constraints. In a computational experiment, we compare the proposed algorithm to the DILS CC algorithm, which represents the state-of-the-art. Our results on 75 problem instances indicate that the proposed algorithm delivers better clusterings than the DILS CC algorithm in much shorter running time.

Interest & Impact

Downloads

4 since deposited on 23 Jul 2021
0 in the past 12 months

Citations

5 Citations in Web of Science ®
6 Citations in Scopus

Search

in Google Scholar™

Services

Actions (login required)

Edit item

Actions (login required)

Edit item