Optimization Methods to Enhance Constraint-Based Semi-Supervised Clustering

Clustering is an essential unsupervised data analysis technique for automatically retrieving data underlying structures. In the past two decades, it has been demonstrated that the clustering performance can be significantly improved when the task is assisted by side information, which is usually provided by domain experts. As a consequence, clustering in the presence of background knowledge should yield solutions that better suit the experts assumptions regarding the data distribution, thus yielding a more reliable data description. This technique, which has recently attracted much interest, is known as semi-supervised clustering. A common way of expressing side information is by means of pairwise constraints, namely must-link and cannot-link constraints, which indicate whether a pair of data objects must or must not be in the same cluster. In this thesis, we studied and proposed novel analytical techniques and algorithms that enhance the performance of constraint-based semi-supervised clustering models.

Résumé

Le clustering est une technique importante de l'analyse des données non supervisée qui per- met de récupérer automatiquement la structure sous-adjacente des données. Au cours des deux dernières décennies, il a été démontré que les performances des modèles de clustering peuvent être considérablement améliorées lorsque la tâche est assistée par des informations secondaires, généralement fournies par des experts du domaine. Par conséquent, faire du clustering en présence de connaissances supplémentaires devrait produire des solutions plus conformes aux hypothèses des experts concernant la distribution des données, et ainsi per- mettre d'obtenir une description des données plus fiable. Cette technique, qui a suscité beaucoup d'intérêt ces dernières années, est connue sous le nom de clustering semi-supervisé. Une manière courante d'exprimer les informations secondaires est au moyen de contraintes sur les paires d'objets, appelées formellement contraintes de must-link et de cannot-link, qui in- diquent si une paire d'objets doit être ou ne doit pas être dans les mêmes clusters. Dans cette thèse, nous avons étudié et proposé des techniques analytiques et des algorithmes qui peuvent être utilisés pour améliorer les performances des modèles de clustering semi-supervisés basés.