Semi-supervised clustering in graphs - Archive ouverte HAL Access content directly
Theses Year : 2017

Semi-supervised clustering in graphs

Partitionnement semi-supervisé dans les graphes

(1)
1

Abstract

Nowadays, decision processes in various areas (marketing, biology, etc) require the processing of increasing amounts of more and more complex data. Because of this, there is a growing interest in machine learning techniques. Among these techniques, there is clustering. Clustering is the task of finding a partition of items, such that items in the same cluster are more similar than items in different clusters. This is a data-driven technique. Data come from different sources and take different forms. One challenge consists in designing a system capable of taking benefit of the different sources of data, even when they come in different forms. Among the different forms a piece of data can take, the description of an object can take the form of a feature vector: a list of attributes that takes a value. Objects can also be described by a graph which captures the relationships objects have with each others. In addition to this, some constraints can be known about the data. It can be known that an object is of a certain type or that two objects share the same type or are of different types. It can also be known that on a global scale, the different types of objects appear with a known frequency. In this thesis, we focus on clustering with three different types of constraints: label constraints, pairwise constraints and power-law constraint. A label constraint specifies in which cluster an object belong. Pairwise constraints specify that pairs of object should or should not share the same cluster. Finally, the power-law constraint is a cluster-level constraint that specifies that the distribution of cluster sizes are subject to a power-law. We want to show that introducing semi-supervision to clustering algorithms can alter and improve the solutions returned by unsupervised clustering algorithms. We contribute to this question by proposing algorithms for each type of constraints. Our experiments on UCI data sets and natural language processing data sets show the good performance of our algorithms and give hints towards promising future works.
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.
Fichier principal
Vignette du fichier
Chatel.pdf (1.2 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

tel-01667429 , version 1 (19-12-2017)

Identifiers

  • HAL Id : tel-01667429 , version 1

Cite

David Chatel. Semi-supervised clustering in graphs. Artificial Intelligence [cs.AI]. Université de Lille, 2017. English. ⟨NNT : ⟩. ⟨tel-01667429⟩
238 View
546 Download

Share

Gmail Facebook Twitter LinkedIn More