Identifying and Generating Easy Sets of Constraints for Clustering

Proceedings of the AAAI Conference on Artificial Intelligence, 21

Volume

Technical Papers

Machine Learning

Clustering under constraints is a recent innovation in the artificial intelligence community that has yielded significant practical benefit. However, recent work has shown that for some negative forms of constraints the associated subproblem of just finding a feasible clustering is NP-complete. These worst case results for the entire problem class say nothing of where and how prevalent easy problem instances are. In this work, we show that there are large pockets within these problem classes where clustering under constraints is easy and that using easy sets of constraints yields better empirical results. We then illustrate several sufficient conditions from graph theory to identify a priori where these easy problem instances are and present algorithms to create large and easy to satisfy constraint sets.