Comparaison et coopération d’approches en analyse de concepts formels pour les données relationnelles

When:
10/07/2022 – 11/07/2022 all-day
2022-07-10T02:00:00+02:00
2022-07-11T02:00:00+02:00

Offre en lien avec l’Action/le Réseau : – — –/Doctorants

Laboratoire/Entreprise : ICube Strasbourg et IRISA Rennes
Durée : 36 mois
Contact : florence.leber@engees.unistra.fr
Date limite de publication : 2022-07-10

Contexte :
Dans les données disponibles pour l’analyse, beaucoup ont un caractère relationnel : données spatiales, temporelles, ou décrivant des liens entre individus. Les méthodes traditionnelles ne sont pas adaptées à ce type de données, qui nécessitent des approches spécifiques, incluant des techniques d’agrégation. Parmi ces approches, l’analyse relationnelle de concepts et l’analyse conceptuelle de graphes sont dérivées de l’analyse de concepts formels (ACF) [1], qui est une méthode mathématique de classification, largement appliquée sur différents types de données et dans de nombreux domaines (par exemple [2,3]). Elle consiste, à partir d’une table (appelée contexte) décrivant des objets par des attributs, à construire un treillis de concepts, i.e. des couples (extension ; intension) d’ensembles fermés décrivant les objets et les attributs qui les définissent.
L’analyse relationnelle de concepts (ARC) [4] considère deux types de contextes, des contextes objets-attributs et des contextes objets-objets décrivant les relations entre objets. L’ARC étend les contextes objets-attributs par des attributs relationnels de la forme qrC, où q est un quantificateur, r une relation et C un concept issu du co-domaine de r. Le résultat de l’ARC est une famille de treillis (un par contexte objets-attributs) reliés entre eux par ces attributs relationnels : un concept d’un treillis représente un groupe d’objets caractérisé par des attributs simples et des attributs relationnels renvoyant à des concepts d’un autre treillis.
L’analyse conceptuelle de graphes (Graph-FCA) [5] a pour contextes des hypergraphes où les nœuds sont les objets et où les hyperarcs sont étiquetés par des attributs. Un hyper-arc unaire a(o) correspond à la description d’un objet par un attribut, comme dans l’ACF. Un hyper-arc binaire a(o1,o2) correspond à une relation ‘a’ de o1 vers o2, comme les attributs relationnels dans RCA. Les relations n-aires sont représentées par des hyperarcs n-aires a(o1,…,oN). Un concept de graphe représente un ensemble de tuples d’objets (extension) qui peuvent être vus comme les réponses exhaustives à une requête conjonctive (intension), par exemple (x,y) ← a1(x,z), a2(y,z), et où cette requête exprime tout ce que ces tuples ont en commun.

Sujet :
Cette thèse s’inscrit dans le cadre de l’ANR SmartFCA, qui regroupe 5 équipes françaises travaillant dans le domaine de l’ACF et dont l’objectif est de mettre à disposition une plateforme rassemblant les différentes variantes de cette méthode. Plusieurs ingénieurs seront affectés au développement de cette plateforme.

Objectifs de la thèse : Cette thèse a pour but de mener une comparaison théorique et expérimentale des deux approches ARC et Graph-FCA, de proposer des éléments pour faire coopérer les deux approches, et de définir un guide méthodologique d’usage (modélisation des données, valeurs des paramètres, choix des algorithmes, etc.). Les résultats, algorithmes et guide méthodologique, seront intégrés dans la plateforme développée dans le cadre du projet ANR SmartFCA.
Les liens entre les deux approches ont déjà été abordés [6,7,8] et la thèse doit approfondir ces travaux. II s’agira dans un premier temps d’étudier et de comparer les deux approches, à partir des outils existants, en les testant sur des jeux de données relationnels fournis par les partenaires du projet. On s’intéressera en particulier à proposer un modèle déclaratif de l’ARC qui est actuellement définie de manière itérative. On s’intéressera aussi à la coopération entre l’ARC et Graph-FCA par la définition des structures de données permettant de les rendre interopérables.
Le caractère explosif des approches fondées sur l’ACF conduit à utiliser des algorithmes ne calculant qu’une sous-partie des concepts ou des treillis : AOC-poset [9], approches exploratoires, calcul de voisinages, estimation des résultats à partir du choix des paramètres [10,11] … Ces variantes seront aussi étudiées et permettront de définir un cadre méthodologique d’utilisation de l’ARC et de Graph-FCA incluant ces différentes options ainsi que des éléments pour guider leur usage. Le travail sera mené en coopération avec un ingénieur chargé des développements dans la plateforme.

Apports attendus :
• Avancées théoriques sur les méthodes ACF
• Développements méthodologiques
• Expérimentations et validation sur des données réelles

Profil du candidat :
Informatique, science des données, formalisation
• Curiosité, capacité à appréhender différents domaines et à interagir avec les experts de ces domaines

Formation et compétences requises :

• Master 2 en Informatique ou équivalent
• Formation en logique, représentation de connaissances et programmation

Adresse d’emploi :
ICube UMR 7357 – Laboratoire des sciences de l’ingénieur, de l’informatique et de l’imagerie
300 bd Sébastien Brant – CS 10413 – F-67412 Illkirch Cedex –

Document attaché : 202205301313_these_RCA_GraphFCA.pdf