Efficient incremental constrained clustering

摘要: Clustering with constraints is an emerging area of data mining research. However, most work assumes that the are given as one large batch. In this paper we explore situation where incrementally given. way user after seeing a clustering can provide positive and negative feedback via to critique solution. We consider problem efficiently updating satisfy new old rather than reclustering entire set. show incremental under NP-hard in general, but identify several sufficient conditions which lead solvable versions. These translate into set rules on types thatcan be added constraint properties must maintained. demonstrate approach more efficient re-clustering has other advantages.