document: 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 we 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 . We consider the problem of efficiently updating a clustering to satisfy the new and old constraints rather than reclustering the entire data set . We 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 . These translate into a set of rules on the types of constraints thatcan be added and constraint set properties that must be maintained . We demonstrate that this approach is more efficient than re-clustering the entire data set and has several other advantages .
doc_bio_tags: O O O B B O B O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O B O O O O O O O O O O O O B O O O O O O O B O O O B O O O O O O O O O O B O O O O O O B O O O O O O O O O O O O O O O B O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O