Thèse de David Chatel

Partitionnement semi-supervisé dans les graphes

De nos jours, les processus de décision dans divers domaines (marketing, biologie, etc.) nécessitent le traitement de quantités croissantes de données de plus en plus complexes. Pour cette raison, il y a un intérêt croissant pour les techniques d'apprentissage automatique. Parmi ces techniques, il y a le partitionnement. 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. C'est une technique pilotée par les données. 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, même si elles sont présentées sous différentes formes. Parmi les différentes formes qu'une donnée peut prendre, la description d'un objet peut prendre la forme d'un vecteur de caractéristiques: une liste d'attributs qui prend une valeur. Les objets peuvent également être décrits par un graphe qui capture les relations que les objets ont entre eux. En plus de cela, 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.

Jury

Directeur de thèse : Marc Tommasi Rapporteurs : TELLIER Isabelle, GAUSSIER Eric Examinateurs : VRAIN Christel, DUCHIEN Laurence, TOMMASI Marc, DENIS Pascal

Thèse de l'équipe MAGNET soutenue le 07/12/2017