Constrained Clustering Algorithms: Practical Issues and Applications
Thesis, Tese De Doutoramento · 2013
Recently a new fashion of semi-supervised clustering algorithms, coined as Constrained Clustering, has emerged. These algorithms can incorporate some a priori domain knowledge to the clustering process, allowing the user to guide the method and improve the quality of the partitions. Up to this date, the research on this topic has been focused on developing new algorithms, mostly overlooking certain practical questions whose importance is capital in realworld problems. In this thesis we identify and study two of these issues, constraint extraction and robustness to noise. In this thesis we perform an analysis of the robustness of some Constrained Clustering algorithms to noisy sets of constraints, designing an experiment in which their behaviour is tested with synthetic sets of inaccurate constraints created with two noise models, one of them based on intuitions about the nature of real errors in the constraints. The strengths and weaknesses of each algorithm are discussed and used to conclude the scenarios in which using it is the best decision. Moreover, we likewise propose in this work two schemes to automatically extract constraints in two important domains: web pages and text in general. In the former we use information external to the web pages (their social tags), whereas in the later we use information which is not taken into account by the usual text representation schemes (the order of the words). Both methods are tested in thorough experiments over reference collections and compared with suitable baselines. Lastly, and keeping with the practical focus of this thesis, we have as well analysed how to apply Constrained Clustering to tackle an existing real-world problem, the Avoiding Bias task, proposing a scheme that uses constraints to codify the partition to be avoided. We study as well how to improve the quality of the alternative partitions, proposing two approaches which use spectral clustering techniques.