Local search approach for the pairwise constrained clustering problem
Authors: Tran Khanh Hiep, Nguyen Minh Duc, Bui Quoc Trung
Abstract: The pairwise constrained clustering is the problem of partitioning a set of data points into clusters when we know in advance that some pairs of points should be in the same cluster and some pairs should not. Previous studies on this problem can be divided into three categories: modifying a traditional clustering algorithm to incorporate constraints, learning a distance measure or combining both approaches. Local search is a heuristic method for finding high-quality solutions for hard optimization problems in a reasonable computation time. It has been applied to the traditional clustering problem in many studies. However, it has never been used for the pairwise constrained clustering problem. Therefore, this paper proposes Tabu search algorithms for this problem, which were tested on several datasets. The experimental results show that these algorithms are very interesting in comparison with some state-of-the-art algorithms, COP K-means, MPC K-means and LCVQE.
Published: 08 December 2016
Download: https://dl.acm.org/doi/10.1145/3011077.3011114