Probabilistic Semi-Supervised Clustering with Constraints

Abstract

Abstract This chapter discusses a problem resulting from certain clustering tasks from which limited supervision is obtained in the form of pairwise constraints—semi-supervised clustering. Semi-supervised clustering is an instance of semi-supervised learning stemming from a traditional unsupervised learning setting. Several algorithms exist for enhancing clustering quality by using supervision in the form of constraints. These algorithms typically utilize the pairwise constraints to either modify the clustering objective function or to learn the clustering distortion measure. This chapter describes an approach that employs hidden Markov random fields (HMRFs) as a probabilistic generative model for semi-supervised clustering, thereby providing a principled framework for incorporating constraint-based supervision into prototype-based clustering. The HMRF-based model allows the use of a broad range of clustering distortion measures, including Bregman divergences and directional distance measures, making it applicable to a number of domains.