From Instance-level Constraints to Space-Level Constraints: Making the Most of Prior Knowledge in Data Clustering
Dan Klein, Sepandar D. Kamvar, Christopher D. Manning · 2002
We present an improved method for clustering in the presence of very limited supervisory information, given as pairwise instance constraints. By allowing instance-level constraints to have spacelevel inductive implications, we are able to successfully incorporate constraints for a wide range of data set types. Our method greatly improves on the previously studied constrained-means algorithm, generally requiring less than half as many constraints to achieve a given accuracy on a range of real-world data, while also being more robust when over-constrained. We additionally discuss an active learning algorithm which increases the value of constraints even further. 1.