Projet de thèse sur le sujet Techniques d'optimisation et de recherche opérationnelle pour la Fouille

Département Informatique

Informations

• Publié par: Phaen
• Nombre de lectures: 32
• Langue: Français

Extrait

Ecole Doctorale :

ÉCOLE DOCTORALE INFORMATIQUE, AUTOMATIQUE, ÉLECTRONIQUE-

ÉLECTROTECHNIQUE, MATHÉMATIQUES (IAEM)

Laboratoire

: LITA (EA 3097) : Laboratoire d’Informatique Théorique et Appliquée

Equipe :

Algorithme et Optimisation

Thème :

Fouille de données

Localisation :

LITA, Metz

Boudjeloud-Assala Lydia, Maître de conférences à l’IUT de metz, LITA

[e-mail]

François Brucker, Maître de conférences habilité à l'université de Metz, LITA

[e-mail]

Sujet de thèse : Techniques d'optimisation et de recherche opérationnelle pour la Fouille et la

visualisation des données évolutives

- Objectif :

L'objectif de cette thèse est d'étudier les possibilités offertes par les méthodes automatiques

d'optimisation pour les algorithmes de fouille de données en coopération avec des méthodes de

visualisation de données pour le traitement de grands ensembles de données évolutives (qui évoluent

dans le temps, éventuellement pour des applications sur des données issue d’Internet : traces de

navigations sur Internet, données comportementales, ..)

- Contexte scientifique :

Nous sommes confrontés aujourd’hui à des volumes de données de plus en plus importants et qu’il est

nécessaire de pouvoir analyser le plus efficacement possible. Souvent ces données sont non seulement

nombreuses mais également ordonnées dans le temps. Elles apparaissent donc sous la forme de flux et

de volumes très importants. Les techniques de classification de données et d’apprentissage doivent

s’adapter afin de pouvoir être applicables à ce type de problématiques. Les méthodes de visualisation

utilisées actuellement dans le domaine de la fouille de données et de la visualisation d'informations

sont nombreuses et variées. Plusieurs classifications de ces méthodes graphiques ont été présentées, la

plus cité distingue trois catégories :

- les méthodes exploratoires,

- les méthodes pour confirmer ou infirmer des hypothèses et

- les méthodes de présentation de résultats.

A ces trois catégories, nous en ajoutons une quatrième apparue depuis peu : la fouille visuelle de

données, où l'algorithme de fouille (graphique et interactif) est piloté par l'utilisateur du système en

utilisant ses capacités cognitives de traitement de l'information (par exemple en reconnaissance de

formes). Nous nous focaliserons sur la première et les deux dernières catégories. La première partie

de cette thèse consiste à étudier ou optimiser des méthodes de fouille de données pour pouvoir traiter

des données évolutives. La seconde partie consiste à étudier les possibilités offertes par les outils

graphiques de visualisation (travaillant éventuellement en collaboration avec des méthodes

automatiques optimisées de fouille de données) pour la fouille et la représentation de données

évolutives.

- Théories et procédés proposés :

Une première difficulté est de pouvoir traiter et de représenter un grand nombre de données sur un

support de taille restreinte ainsi que de représenter l'aspect évolutionnaire de ces données en temps

réel. Plusieurs solutions peuvent être envisagées. Dans cette optique l'étude de méthodes incrémentales

et aux techniques de résumé de données semble être intéressant pour ce type de problème. Un des

objectifs de cette thèse est de pouvoir traiter plutôt le million de données et au-delà en temps réel.

Pour cela, l'utilisation des méthodes incrémentales semble permettre de classifier (en non supervisé)

des données sur une fenêtre temporelle et ainsi d’établir une classification non supervisée dynamique

évoluant dans le temps. Une autre difficulté est de trouver une représentation adéquate des résultats

obtenus par les algorithmes de fouille de données.

Les outils d'interprétation graphique et de

visualisation de données de résultats devraient permettre une meilleure compréhension ou une

compréhension par un plus grand nombre d'utilisateurs. L’aspect visualisation est de nouveau

important dans ce contexte car il peut aider l’utilisateur à percevoir facilement l’évolution de son flux

de données (apparition de clusters, fusion de clusters, etc).

Une première approche est de s’inspirer

des méthodes de visualisation de graphes et les algorithmes de ressorts. Les travaux de recherche sur

les algorithmes de ressorts commencent avec Tutte (1963) et se poursuivent avec Eades (1984). Ce

dernier utilise l’analogie suivante pour expliquer la visualisation dynamique de graphes : il compare

les arêtes dans un graphe à des ressorts. Le système, ainsi considéré, engendre des forces entre les

sommets. Ce qui provoque naturellement des déplacements de sommets. Les sommets s’attirent et se

repoussent. La notion d’attraction entre sommets se réalise grâce aux arêtes qui cherchent à atteindre

une distance cible associée. Eades (1984) ajoute la notion de forces de répulsion aux sommets. La

condition d’arrêt initialement proposée pour un tel système est un nombre maximum d’itérations

(évolution du graphe dans le temps). Plusieurs recherches ont ensuite été consacrées au domaine.

Nous pouvons citer entre autres Kamada et Kawai (1989), Frick et al. (1994) et Fruchterman et

Reingold (1991). Ces différentes propositions ont amené à l’établissement de plusieurs modèles de

visualisation dynamique de graphes. A partir des ces méthodes nous pouvons facilement imaginer de

représenter l’ensemble de données avec l’algorithme de force et de ressort à l’instant t, et à l’instant

t+1 lorsqu’une nouvelle données intervient dans le traitement elle va s’accrocher sur le cluster ou

l’élément le plus similaire qu’on pourrait facilement interpréter à l’aide des ressort. On peut aussi bien

envisager d’autres méthodes de représentation de données évolutives et temporelles, tels que les

données comportementales issue de fichier logs à partir de navigation de pages web (figure suivante),

l’idée traitée sur cette visualisation est issue d’un traitement de fichiers logs à partir d’une plate forme

d’apprentissage, les couleurs représentent les intervenants dans cette plate forme et la taille du carrée

le temps passé à communiquer entre les différents intervenants. On pourrait éventuellement s’inspirer

de ce type de représentation pour des fichiers de très grandes tailles par exemple.

Figure 1 : Visualisation d’une plateforme d’apprentissage

- Méthodologie utilisée :

Etat de l'art sur les méthodes incrémentales, état de l'art sur les méthodes de visualisation de graphes

dynamiques, développement d'une méthode de fouille de données temporelles, implémentation et tests

de la méthode, Comparaisons et évaluation de la méthode.

- I

ntérêt scientifique général et caractère novateur du projet, en particulier à la lumière des

développements récents dans le domaine concerné :

Très peu de travaux ont été menés dans cette direction. Les domaines d’application de ces techniques

sont nombreux et peuvent aller du traitement de flux réseau en vue de détecter des intrusions, en

passant par la recherche d’information

sur le web, ainsi que la catégorisation et l’étude

comportementale des usagers du web.

Résultats escomptés

Développement d'une méthode pouvant traiter des données temporelle qui évoluent dans le temps

développer une méthode de visualisation de ce type de données, pouvant prendre en compte l'aspect

temps réel éventuellement les faire coopérer permettant de faire de la fouille visuelle de données

temporelles.

Connaissance et compétence requises :

Gout pour la recherche, et le développement.