In recent years, clustering has been extended to constrained clustering, so as to integrate knowledge on objects or on clusters, but adding such constraints generally requires to develop new algorithms. We propose a declarative and generic framework, based on Constraint Programming, which enables to design clustering tasks by specifying an optimization criterion and some constraints either on the clusters or on pairs of objects. In our framework, several classical optimization criteria are considered and they can be coupled with different kinds of constraints. Relying on Constraint Programming has two main advantages: the declarativity, which enables to easily add new constraints and the ability to find an optimal solution satisfying all the constraints (when there exists one). On the other hand, developping dedicated global constraints for clustering tasks allows to improve the efficiency of the framework.
[1] Thi-Bich-Hanh Dao, Khanh-Chuong Duong and Christel Vrain. A Declarative Framework for Constrained Clustering. In European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML/PKDD), pages 419-434, 2013. Preprint.
[2] Thi-Bich-Hanh Dao, Khanh-Chuong Duong and Christel Vrain. A Filtering Algorithm for Constrained Clustering with Within-Cluster Sum of Dissimilarities Criterion. In IEEE International Conference on Tools with Artificial Intelligence (ICTAI)- 2013, pages 1060-1067, 2013. Preprint.
[3] Thi-Bich-Hanh Dao, Khanh-Chuong Duong and Christel Vrain. Un nouveau modèle pour la classification non supervisée sous contraintes. Revue d'Intelligence Artificielle, 28 (5), pages 523-545, 2014. Preprint.
[4] Thi-Bich-Hanh Dao, Khanh-Chuong Duong and Christel Vrain. Constrained Minimum Sum of Squares Clustering by Constraint Programming. In Proc. of the 21st Int. Conf. on Principles and Practice of Constraint Programming (CP), pages 557-573, 2015. Preprint.
[5] Thi-Bich-Hanh Dao, Khanh-Chuong Duong and Christel Vrain. Constrained Clustering by Constraint Programming. Artificial Intelligence, to appear, DOI. Preprint.
[6] Thi-Bich-Hanh Dao, Christel Vrain, Khanh-Chuong Duong and Ian Davidson. A Framework for Actionable Clustering using Constraint Programming. In Proc. of the 22nd European Conference on Artificial Intelligence (ECAI), 2016. Preprint.
[7] Tias Guns, Thi-Bich-Hanh Dao, Christel Vrain, Khanh-Chuong Duong. Repetitive Branch-and-Bound using Constraint Programming for Constrained Minimum Sum-of-Squares Clustering. In Proc. of the 22nd European Conference on Artificial Intelligence (ECAI), 2016. Preprint.
1. Install Gecode (4.3.3) at http://gecode.org
2. Download
For any question, please contact: thi-bich-hanh.dao (at) univ-orleans (dot) fr