Constrained Clustering: Current and New Trends

International audienceClustering is an unsupervised process which aims to discover regularities and underlying structures in data. Constrained clustering extends clustering in such a way that expert knowledge can be integrated through the use of user constraints. These guide the clustering process towards a more relevant result. Different means of integrating constraints into the clustering process exist. They consist of extending classical clustering algorithms, such as the well-known k-means algorithm; modelling the constrained clustering problem using a declarative framework; and finally, by directly integrating constraints into a collaborative process that involves several clustering algorithms. A common point of these approaches is that they require the user constraints to be given before the process begins. New trends in constrained clustering highlight the need for better interaction between the automatic process and expert supervision. This chapter is dedicated to constrained clustering. In particular, after a brief overview of constrained clustering and associated issues, it presents the three main approaches in the domain. It also discusses exploratory data mining by presenting models that develop interaction with the user in an incremental and collaborative way. Finally, moving beyond constraints, some aspects of user implicit preferences and their capture are introduced