Efficient Incremental Constrained Clustering

Clustering with constraints is an emerging area of data mining research. However, most work assumes that the constraints are given as one large batch. In this paper, the authors explore the situation where the constraints are incrementally given. In this way the user after seeing a clustering can provide positive and negative feedback via constraints to critique a clustering solution. They consider the problem of efficiently updating a clustering to satisfy the new and old constraints rather than re-clustering the entire data set. They show that the problem of incremental clustering under constraints is NP-hard in general, but identify several sufficient conditions which lead to efficiently solvable versions.