Partitionnement semi-supervisé dans les graphes
David Chatel · theses.fr (ABES) · 2017
Le partitionnement consiste à rechercher une partition d'éléments, de sorte que les éléments d'un même cluster soient plus similaires que les éléments de différents clusters. Les données proviennent de différentes sources et prennent des formes différentes. L'un des défis consiste à concevoir un système capable de tirer parti des différentes sources de données. Certaines contraintes peuvent être connues sur les données. On peut savoir qu'un objet est d'un certain type ou que deux objets partagent le même type ou sont de types différents. On peut également savoir qu'à l'échelle globale, les différents types d'objets apparaissent avec une fréquence connue. Dans cette thèse, nous nous concentrons sur le partitionnement avec trois types de contraintes: les contraintes d'étiquettes, les contraintes de paires et les contraintes de lois de puissance. Une contrainte d'étiquette spécifie dans quel cluster appartient un objet. Les contraintes par paire spécifient que les paires d'objets doivent ou ne doivent pas partager le même cluster. Enfin, la contrainte de loi de puissance est une contrainte globale qui spécifie que la distribution des tailles de cluster est soumise à une loi de puissance. Nous voulons montrer que l'introduction de la semi-supervision aux algorithmes de clustering peut modifier et améliorer les solutions retournées par des algorithmes de clustering non supervisés. Nous contribuons à cette question en proposant des algorithmes pour chaque type de contraintes. Nos expériences sur les ensembles de données UCI et les jeux de données en langage naturel montrent la bonne performance de nos algorithmes et donnent des indications pour des travaux futurs prometteurs.