Clustering with cluster-level constraints

The task of clustering is to group data objects into clusters which exhibit internal cohesion and external isolation. The generated clusters provide useful knowledge to support decision making in many applications. However, clustering methods may fail to discover satisfactory results due to the lack of user involvement, especially in the form of supplying background knowledge about target domains and application needs. Normally, background knowledge can be captured by three types of constraints, i.e., instance-level constraints, cluster-level constraints, and model-level constraints. In this thesis, we study how cluster-level constraints are used to capture the background knowledge and users' special requirements in several real life clustering tasks, e.g., catalog segmentation, community identification, and privacy preservation etc. We design appropriate clustering models that integrate those constraints. We analyze the complexity of the proposed models, develop efficient clustering algorithms, and evaluate the clustering results on synthetic and real data sets.