Semi-supervised clustering in graphs

David Chatel 1
1 MAGNET - Machine Learning in Information Networks
CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189, Inria Lille - Nord Europe
Résumé : 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.
Type de document :
Thèse
Artificial Intelligence [cs.AI]. Université de Lille, 2017. English
Liste complète des métadonnées

Littérature citée [91 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/tel-01667429
Contributeur : Team Magnet <>
Soumis le : mardi 19 décembre 2017 - 13:12:47
Dernière modification le : mercredi 25 juillet 2018 - 01:22:23

Fichier

Chatel.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : tel-01667429, version 1

Citation

David Chatel. Semi-supervised clustering in graphs. Artificial Intelligence [cs.AI]. Université de Lille, 2017. English. 〈tel-01667429〉

Partager

Métriques

Consultations de la notice

186

Téléchargements de fichiers

168