ESI Talents

Sujet de Stage N°: 429

Sujet de Stage
Validation

Sujet de stage N° 429

Type*

Specialites*

Organisme*

Coencadrants*

Promoteur*

Djahnit Hadjer

Email promoteur*

Tel promoteur

Intitule*

Sélection des mesures d’intérêts pour l’évaluation de la pertinence des patterns extrais lors d’une recherche non exhaustive : application au problème de recherche des liens conceptuels fréquents

Resume*

Les premières techniques mises en place par l’analyse des réseaux sociaux se basaient exclusivement sur des indicateurs issus de la théorie des graphes. Progressivement, des techniques de data mining prennent de plus en plus de la place dans l’extraction de modèles à partir des données relationnel.
Ces techniques dites de fouille de réseaux sociaux ou social mining, visent à extraire de la connaissance sur le réseau en appliquant les concepts de la fouille de données classique. Les tâches les plus courantes sont : le clustering, la recherche de motifs fréquents, l’analyse conceptuelle et les liens conceptuels fréquents. 
L’extraction de liens conceptuels fréquents (Frequent Conceptual Links-FCL) ou les liens conceptuels fréquents maximaux (Maximum FCL- MFCL) est une approche très récente qui combine à la fois les informations sur la structure du réseau et les attributs des nœuds afin de fournir une information sur les types de nœuds les plus connectés dans le réseau. Le terme conceptuel signifie que le lien n’existe pas réellement sur le réseau mais il représente un ensemble de liens reliant les groupes de nœuds tel que les nœuds de chaque groupe partagent des attributs communs.
Proposé en 2012 par Erick Stattner, la technique d’extraction de liens conceptuels fréquents n’a connu que quelques améliorations depuis sa première apparition. La solution la plus intuitive consiste à générer, à partir des attributs des nœuds, tous les itemsets possibles, ensuite vérifier la fréquence de chaque pair d’itemsets et ne retenir que les plus fréquents (ayant un support supérieur à un seuil prédéfini). Cependant, cette méthode dépend directement du nombre d’attributs, de leur valence et de la taille du réseau et conduit rapidement à l’explosion de l’espace de recherche : il s’agit d’un problème NP-difficile, pour lequel le balayage de tout l’espace de recherche s’avère impossible sur un large réseau.
Ainsi, d’autres travaux sont apparus, leur but étant de réduire l’espace de recherche tout en énumérant toutes ou le maximum des solutions disponibles. 
Parmi les implémentations du processus d’extraction des liens conceptuels fréquents maximaux, H-MFCLMin et D-MFCLMin ont mis en œuvre la notion de seuil de filtration des groupes de nœuds pour réduire l’espace de recherche ; ceci a permis d’améliorer les performances du processus de recherche avec en contrepartie une perte dans les patterns recherchés. Cette question est aussi posée lors du recours aux heuristiques puisque la perte est inévitable.
Le présent projet propose d’étudier la pertinence des patterns extrais lors d’une recherche non exhaustive. En effet, lorsqu’un seuil de support est fixé, comment être sûr que tous les MFCL sont extrais, ou évaluer le taux de perte de patterns, quels mesure d’intérêt mettre en œuvre pour avoir les meilleurs MFCL.
A titre d’exemple, lors des expériences de H-MFCLMin, les résultats sont comparés avec ceux obtenus dans un processus d’extraction complet, ce qui est impossible sur un large réseau. Une approche intéressante pourrait être de s’inspirer des mesures d’intérêt appliquées au problème de recherche des itemsets fréquents et d’étudier comment la perte de patterns évolue selon différentes mesures tel que la taille du réseau, la taille des données, le seuil de support…
Des tests sur des réseaux réels et/ou synthétiques seront effectuées afin de valider les performances de la solution proposée.

Objectifs*

L’objectif de ce PFE est de proposer des nouvelles mesures d’intérêt permettant d’évaluer la pertinence des patterns extrais lors d’une recherche non exhaustive des liens conceptuels fréquents. Cela nous permet de valider la solution obtenue sans avoir à comparer avec les résultats d’un processus d’extraction complet, notamment sur un large réseau.

Resultats attendus*

I – Faire une synthèse bibliographique sur les méthodes d’analyse des réseaux sociaux (analyse structurelle et en utilisant des attributs)
II – Etude bibliographique sur lu problème d’extraction des liens conceptuels fréquents dans les grands graphes
III – Etude bibliographique sur les mesures d’intérêt appliquées dans les processus d’extraction de connaissance
IV – Conception et implémentation d’une solution intelligente appliquant les mesures adéquats pour l’évaluation des liens conceptuels fréquents extrais
V-  Tester la méthode proposée sur différentes instances du problème

Antecedents

Moyens informatiques

Echeancier*

Etape 1	Etat de l’art	2.5 mois 
Etape 2	Conception de la méthode demandée	2 mois 
Etape 3	Implémentation 	2 mois 
Etape 4	Tests et analyse des résultats 	1.5 mois

Bibliographie

Statut validation*

Reponse aux experts

Reserve pour*

Projet recherche

Notification

Avis sur le Sujet de Stage

Intitule	Organisme	Debut	Fin	Avis	Commentaire
Sélection des mesures d’intérêts pour l’évaluation de la pertinence des patterns extrais lors d’une recherche non exhaustive : application au problème de recherche des liens conceptuels fréquents	LMCS : Laboratoire de Méthodes de Conception de Systèmes, Ecole nationale Supérieure d'Informatique	10/31/2020	11/01/2020	Avis favorable	—
Sélection des mesures d’intérêts pour l’évaluation de la pertinence des patterns extrais lors d’une recherche non exhaustive : application au problème de recherche des liens conceptuels fréquents	LMCS : Laboratoire de Méthodes de Conception de Systèmes, Ecole nationale Supérieure d'Informatique	10/31/2020	11/08/2020	Avis favorable	—
Sélection des mesures d’intérêts pour l’évaluation de la pertinence des patterns extrais lors d’une recherche non exhaustive : application au problème de recherche des liens conceptuels fréquents	LMCS : Laboratoire de Méthodes de Conception de Systèmes, Ecole nationale Supérieure d'Informatique	10/31/2020	11/01/2020	Avis favorable	—