CE40 - Mathématiques, informatique théorique, automatique et traitement du signal

Fondations des algorithmes de clustering – FOCAL

Résumé de soumission

Partitionner un jeu de données de sorte que les éléments dans la même partpartagent les mêmes propriétés est un problème fondamental qui se pose dans un vaste champ d'applications. Ce problème est même central dans plusieurs domaines: en apprentissage ou dans l'analyse de données par exemple, un tel partitionnement est utilisé pour extraire de l'information du jeu de données.
Dans l'étude des réseaux sociaux, le jeu de données sous-jacent est un graphe de relations et un tel partitionnement permet d'identifier des communautés.
Lorsque l'on chercher à définir des collège électoraux représentatifs, le jeu de données est le réseau routier connectant les habitations est un bon partitionnement rassemble dans le même district, les habitants vivant proche les uns des autres.

Ainsi, calculer un bon partitionnement est un problème majeur dans de nombreux domaines de recherche
qui requiert donc une profonde compréhension de sa complexité ainsi que le développement de nouvelles techniques qui tiennent compte des applications sous-jacentes. Notre projet vise à faire un progrès significatif dans cette direction.

Tout d'abord, pour modéliser les entrées rencontrées en apprentissage et les réseaux sociaux, nous allons considérer
les modèles de graphes aléatoires tel que le modèle de la partition plantée. Ce modèle a par le passé permis le
développement d'algorithmes compétitifs en pratique; il capture correctement certaines propriétés importantes des
réseaux sociaux et des entrées venant par exemple de l'apprentissage.
Mous allons considérer l'une des heuristiques les plus populaires pour le partitionnement de graphes,
l'heuristique de Kernighan-Lin, et tenter d'expliquer son succès sur des instances du monde réel
en prouvant qu'elle fonctionne bien sur les graphes générés par le
modèle de la partition plantée. De plus, nous allons considérer le scénario où le jeu des données est
massif. Dans ce contexte, l'algorithme doit traiter un flux de données et donc
nous viserons à concevoir de nouvelles techniques pour trouver un bon partitionnement
à partir d'un flux de donnée généré par le modèle de la partition plantée.

Deuxièmement, nous considérerons le scénario auquel sont confrontés divers fournisseurs de services en ligne.
Étant donné un jeu de données évolutif - où les éléments de données sont insérés et/ou supprimés -
comment maintenir un bon partitionnement des données? Nous allons
réunir des techniques de la théorie de l'apprentissage et des algorithmes d'approximation et
viser à fournir des algorithmes qui offrent les meilleures garanties possibles.
Notre approche a un potentiel d'impact à la fois fondamental et appliqué:
Nous considérerons des scénarios qui n'ont été que peu pris en compte
par la communauté et nous tenterons de développer des techniques adaptées
à l'application sous-jacente.

Enfin, motivé par le problème du redécoupage électoral, nous étudierons
des problèmes tels que trouver la coupe la plus creuse ou la meilleure coupe équilibrée.
Parce que trouver de bons districts est souvent basé sur le réseau routier reliant les habitations, nous
nous concentrerons sur des graphes plongés sur des surfaces de genre borné.
Comment partitionner un graphe plongé en districts de taille égale de sorte que les points
dans le même district soient proches les uns des autres? Nous allons nous attaquer à ce
problème ouvert de longue date en utilisant des outils que nous avons développés dans plusieurs
travaux récents.

Par conséquent, notre projet aborde des problèmes ouverts ambitieux et possède
un potentiel d'impact élevé pour de nombreuses communautés. Nous pensons que
notre expertise sur les algorithmes de partitionnement, les graphes plongés,
l'analyse au delà du pire cas et les techniques de recherche locales feront de ce
projet un succès. Finalement, nous pensons que le projet aidera à construire un
réseau de chercheurs issus de diverses communautés à travailler sur un problème clé.

Coordination du projet

Vincent Cohen-Addad (Laboratoire d'informatique de Paris 6)

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.

Partenaire

LIP6 Laboratoire d'informatique de Paris 6

Aide de l'ANR 171 720 euros
Début et durée du projet scientifique : septembre 2018 - 48 Mois

Liens utiles

Explorez notre base de projets financés

 

 

L’ANR met à disposition ses jeux de données sur les projets, cliquez ici pour en savoir plus.

Inscrivez-vous à notre newsletter
pour recevoir nos actualités
S'inscrire à notre newsletter