Clustering with Propagated Constraints
Eric R. Eaton · 2008
Background knowledge in the form of constraints can dramatically improve the qual-ity of generated clustering models. In constrained clustering, these constraints typically specify the relative cluster membership of pairs of points. They are tedious to specify and expensive from a user perspective, yet are very useful in large quantities. Existing con-strained clustering methods perform well when given large quantities of constraints, but do not focus on performing well when given very small quantities. This thesis focuses on providing a high-quality clustering with small quantities of constraints. It proposes a method for propagating pairwise constraints to nearby instances using a Gaussian function. This method takes a few easily specified constraints, and prop-agates them to nearby pairs of points to constrain the local neighborhood. Clustering with these propagated constraints can yield superior performance with fewer constraints than clustering with only the original user-specified constraints. The experiments compare the performance of clustering with propagated constraints to that of established constrained clustering algorithms on several real-world data sets. c ○ Copyright Eric Robert Eaton 2005