User Tools

Site Tools


Sidebar

Practical Information:

Teaching:

Bâtiment Nautibus
43, Bd du 11 Novembre 1918
69622 Villeurbanne Cedex.
☏: +33(0)472 43 16 35
email: marc.plantevit-at-univ-lyon1.fr

Research:

Bureau 501.319
Bâtiment Blaise Pascal
7, Avenue Jean Capelle
69621 Villeurbanne Cedex
☏: +33(0)472 43 84 87
Fax: +33(0)472 43 87 13
email: marc.plantevit-at-liris.cnrs.fr

pom18antichaine

Analyse et visualisation de données hiérarchiques (décrivant des phénomènes réels)

<note> Thèmes : fouille de données (data mining), apprentissage statistique (machine learning), problème d'énumération, big data, data science

Encadrant(s) : Marc Plantevit, Anes Bendimerad

Laboratoire : LIRIS

Equipe : DM2L </note>

Contexte :

Les taxonomies (hiérarchies) sur des ensembles d'attributs se présentent dans plusieurs bases de données réelles. Par exemple dans le réseau social Foursquare, chaque lieu est décrit par sa catégorie qui peut être plus ou moins spécifique (restaurant, restaurant italien, université…). Une hiérarchie est bien définie sur les catégories des lieux sur Foursquare : https://developer.foursquare.com/docs/resources/categories L'analyse de ces hiérarchies peut avoir un grand intérêt dans plusieurs cas d'applications. Par exemple, les distributions des catégories des lieux Foursquare dans deux villes peuvent être remarquablement différentes, la comparaison de ces hiérarchies permet d'apprendre beaucoup sur chacune des villes (e.g., quelles sont les activités prévalantes sur chaque ville). Cependant, une défi consiste à choisir le niveau d'hiérarchie à considérer pour l'analyse. Plus le niveau d'hiérarchie est détaillé, plus il permet d'apprendre sur la base de données, mais plus il est difficile à analyser car il peut contenir des centaines de types différents. Exemple : le niveau 3 de Foursquare contient plus de 300 types.

Existant :

Dans l'état de l'art, il existe une méthode qui vise à identifier le niveau d'hiérarchie d'une base de données mais pour un objectif particulier : améliorer la tâche de prédiction [1].

Objectif :

L'objectif est de pouvoir identifier une anti-chaine qui décrit une hiérarchie, au lieu de choisir un niveau précis. En d'autres termes, l'idée consiste à identifier un ensemble de noeuds qui peuvent provenir de niveaux différents de l'hiérarchie, mais qui décrivent des concepts différents. Un exemple d'anti-chaine sur Foursquare est : {(1) College & University, (2) Event, (3) American Restaurant, (4) Asian Restaurant}, (1) et (2) sont des noeuds du niveau 1, alors que (3) et (4) sont du niveau 2.

Travail attendu :

Le travail consiste à :

  1. Développer une (ou plusieurs) méthode(s) d'identification d'anti-chaines qui décrivent bien une hiérarchie,
  2. Appliquer cette méthodes sur quelques bases de données réelles (e.g., hiérarchies Foursquare pour des villes différentes),
  3. Développer un outil de visualisation et comparaison des résultats obtenues.

Références :

[1] Gemma C. Garriga, Antti Ukkonen, and Heikki Mannila. Feature Selection in Taxonomies with Applications to Paleontology. In International Conference on Discovery Science 2008.

pom18antichaine.txt · Last modified: 2018/10/25 11:01 by mplantev

CNRS INSA de Lyon Université Lyon 1 Université Lyon 2 École centrale de Lyon