Analyse des propriétés stationnaires et des propriétés émergentes dans les flux d'information changeant au cours du temps, Analysis of stationary and emerging properties in information flows changing over time

De
Publié par

Sous la direction de Frédéric Alexandre
Thèse soutenue le 11 mai 2009: Nancy 1
De nombreuses applications génèrent et reçoivent des données sous la forme de flux continu, illimité, et très rapide. Cela pose naturellement des problèmes de stockage, de traitement et d'analyse de données qui commencent juste à être abordés dans le domaine des flux de données. Il s'agit, d'une part, de pouvoir traiter de tels flux à la volée sans devoir mémoriser la totalité des données et, d'autre part, de pouvoir traiter de manière simultanée et concurrente l'analyse des régularités inhérentes au flux de données et celle des nouveautés, exceptions, ou changements survenant dans ce même flux au cours du temps. L'apport de ce travail de thèse réside principalement dans le développement d'un modèle d'apprentissage - nommé ILoNDF - fondé sur le principe de la détection de nouveauté. L'apprentissage de ce modèle est, contrairement à sa version de départ, guidé non seulement par la nouveauté qu'apporte une donnée d'entrée mais également par la donnée elle-même. De ce fait, le modèle ILoNDF peut acquérir constamment de nouvelles connaissances relatives aux fréquences d'occurrence des données et de leurs variables, ce qui le rend moins sensible au bruit. De plus, doté d'un fonctionnement en ligne sans répétition d'apprentissage, ce modèle répond aux exigences les plus fortes liées au traitement des flux de données. Dans un premier temps, notre travail se focalise sur l'étude du comportement du modèle ILoNDF dans le cadre général de la classification à partir d'une seule classe en partant de l'exploitation des données fortement multidimensionnelles et bruitées. Ce type d'étude nous a permis de mettre en évidence les capacités d'apprentissage pures du modèle ILoNDF vis-à-vis de l'ensemble des méthodes proposées jusqu'à présent. Dans un deuxième temps, nous nous intéressons plus particulièrement à l'adaptation fine du modèle au cadre précis du filtrage d'informations. Notre objectif est de mettre en place une stratégie de filtrage orientée-utilisateur plutôt qu'orientée-système, et ceci notamment en suivant deux types de directions. La première direction concerne la modélisation utilisateur à l'aide du modèle ILoNDF. Cette modélisation fournit une nouvelle manière de regarder le profil utilisateur en termes de critères de spécificité, d'exhaustivité et de contradiction. Ceci permet, entre autres, d'optimiser le seuil de filtrage en tenant compte de l'importance que pourrait donner l'utilisateur à la précision et au rappel. La seconde direction, complémentaire de la première, concerne le raffinement des fonctionnalités du modèle ILoNDF en le dotant d'une capacité à s'adapter à la dérive du besoin de l'utilisateur au cours du temps. Enfin, nous nous attachons à la généralisation de notre travail antérieur au cas où les données arrivant en flux peuvent être réparties en classes multiples.
-classification supervisée et non supervisée
-analyse des données multidimensionnelles
-dérive de concept
-flux de données
-filtrage basé sur le contenu
-modélisation utilisateur
-détection de nouveauté
Many applications produce and receive continuous, unlimited, and high-speed data streams. This raises obvious problems of storage, treatment and analysis of data, which are only just beginning to be treated in the domain of data streams. On the one hand, it is a question of treating data streams on the fly without having to memorize all the data. On the other hand, it is also a question of analyzing, in a simultaneous and concurrent manner, the regularities inherent in the data stream as well as the novelties, exceptions, or changes occurring in this stream over time. The main contribution of this thesis concerns the development of a new machine learning approach - called ILoNDF - which is based on novelty detection principle. The learning of this model is, contrary to that of its former self, driven not only by the novelty part in the input data but also by the data itself. Thereby, ILoNDF can continuously extract new knowledge relating to the relative frequencies of the data and their variables. This makes it more robust against noise. Being operated in an on-line mode without repeated training, ILoNDF can further address the primary challenges for managing data streams. Firstly, we focus on the study of ILoNDF's behavior for one-class classification when dealing with high-dimensional noisy data. This study enabled us to highlight the pure learning capacities of ILoNDF with respect to the key classification methods suggested until now. Next, we are particularly involved in the adaptation of ILoNDF to the specific context of information filtering. Our goal is to set up user-oriented filtering strategies rather than system-oriented in following two types of directions. The first direction concerns user modeling relying on the model ILoNDF. This provides a new way of looking at user's need in terms of specificity, exhaustivity and contradictory profile-contributing criteria. These criteria go on to estimate the relative importance the user might attach to precision and recall. The filtering threshold can then be adjusted taking into account this knowledge about user's need. The second direction, complementary to the first one, concerns the refinement of ILoNDF's functionality in order to confer it the capacity of tracking drifting user's need over time. Finally, we consider the generalization of our previous work to the case where streaming data can be divided into multiple classes.
Source: http://www.theses.fr/2009NAN10027/document
Publié le : vendredi 28 octobre 2011
Lecture(s) : 12
Nombre de pages : 269
Voir plus Voir moins




AVERTISSEMENT

Ce document est le fruit d'un long travail approuvé par le
jury de soutenance et mis à disposition de l'ensemble de la
communauté universitaire élargie.

Il est soumis à la propriété intellectuelle de l'auteur. Ceci
implique une obligation de citation et de référencement lors
de l’utilisation de ce document.

D’autre part, toute contrefaçon, plagiat, reproduction
illicite encourt une poursuite pénale.


➢ Contact SCD Nancy 1 : theses.sciences@scd.uhp-nancy.fr




LIENS


Code de la Propriété Intellectuelle. articles L 122. 4
Code de la Propriété Intellectuelle. articles L 335.2- L 335.10
http://www.cfcopies.com/V2/leg/leg_droi.php
http://www.culture.gouv.fr/culture/infos-pratiques/droits/protection.htm ´D´epartement de formation doctorale en informatique Ecole doctorale IAEM Lorraine
UFR STMIA
Analyse des propri´et´es stationnaires et
des propri´et´es ´emergentes dans les flux
d’informations changeant au cours
du temps
`THESE
presentee et soutenue publiquement le 11 mai 2009
pour l’obtention du
Doctorat de l’universit´e Henri Poincar´e – Nancy 1
(sp´ecialit´e informatique)
par
Randa Kassab
Composition du jury
Pr´esident : Anne Boyer Professeur, Universite Nancy 2
Rapporteurs : Youn`es Bennani Professeur, Universite Paris 13
Patrick Gallinari Professeur, Universite Paris 6
Examinateurs : Nacer Boudjlida Professeur, Universite Nancy 1
Eric Gaussier Professeur, Universite Joseph Fourier
Directeur : Frederic Alexandre Directeur de recherche, INRIA
Laboratoire Lorrain de Recherche en Informatique et ses Applications — UMR 7503Mis en page avec la classe thloria.i
Remerciements
En premier lieu, je tiens à remercier mon directeur de thèse, Frédéric Alexandre, pour son
aide et tous ses conseils, son écoute, sa patience et sa disponibilité. Je le remercie particulière-
ment pour la liberté qu’il m’a laissée pour mener à terme ce travail, le soutien qu’il m’a apporté
dans les moments les plus difficiles, et le temps qu’il a consacré à lire et à corriger ce manuscrit.
Mes remerciements s’adressent également aux membres du jury de thèse pour le temps qu’ils
ont consacré à l’évaluation de ce travail. Je remercie Anne Boyer d’avoir bien voulu présider ce
jury et d’avoir toujours montré son soutien et son intérêt à mon travail. Je tiens à remercier tout
particulièrement YounèsBennani etPatrick Gallinari, d’avoir acceptélacharged’être lesrappor-
teursdecetravaildethèse,malgrétouteslesresponsabilitésqu’ilsassument.Leurscommentaires
et suggestions me furent très précieux. De même, je tiens à remercier Nacer Boudjlida et Éric
Gaussier, pour leur intervention en tant qu’examinateurs et pour l’intérêt qu’ils ont manifesté à
l’égard de mon travail.
Je tiens ensuite à remercier l’ensemble des membres actuels et anciens de l’équipe CORTEX
pour leur gentillesse, leur aide et leur soutien durant toutes ces années. De même, je tiens à
remercier tous les partenaires du projet Sat-N-Surf qu’ils soient ingénieurs, étudiants, ou cher-
cheurs, pour leur collaboration et les nombreuses discussions.
Je voudrais aussi remercier tous mes professeurs de l’université de Damas qui ont contri-
bué, peut-être de manière indirecte mais importante, à la réalisation de cette thèse. Je pense,
particulièrement, à mon superviseur Faysal Al-Abbas. Je le remercie pour ses conseils, ses en-
couragements et son aide précieuse sur le plan administratif.
Mes pensés vont également à ceux de mes proches, ma famille, et mes amis qui ont toujours
été là pour moi et qui savent combien ils comptent pour moi. Je destine un remerciement tout
spécial à mes parents à qui je dois beaucoup de ce que je suis aujourd’hui.. et je leur dédie cette
thèse.iiRésumé
De nombreuses applications génèrent et reçoivent des données sous la forme de flux continu,
illimité, et très rapide. Cela pose naturellement des problèmes de stockage, de traitement et
d’analyse de données qui commencent juste à être abordés dans le domaine des flux de données.
Il s’agit, d’une part, de pouvoir traiter de tels flux à la volée sans devoir mémoriser la totalité
des données et, d’autre part, de pouvoir traiter de manière simultanée et concurrente l’analyse
des régularités inhérentes auflux dedonnées etcelle des nouveautés, exceptions, ou changements
survenant dans ce même flux au cours du temps.
L’apport de ce travail de thèse réside principalement dans le développement d’un modèle
d’apprentissage — nommé ILoNDF — fondé sur le principe de la détection de nouveauté. L’ap-
prentissage de ce modèle est, contrairement à sa version de départ, guidé non seulement par la
nouveauté qu’apporteunedonnéed’entrée maiségalement parladonnéeelle-même. Decefait,le
modèle ILoNDF peut acquérir constamment de nouvelles connaissances relatives aux fréquences
d’occurrence des données et de leurs variables, ce qui le rend moins sensible au bruit. De plus,
doté d’un fonctionnement en ligne sans répétition d’apprentissage, ce modèle répond aux exi-
gences les plus fortes liées au traitement des flux de données.
Dans un premier temps, notre travail se focalise sur l’étude du comportement du modèle
ILoNDFdanslecadregénéraldelaclassificationàpartird’uneseuleclasseenpartantdel’exploi-
tation des données fortement multidimensionnelles et bruitées. Ce type d’étude nous a permis de
mettreenévidenceles capacités d’apprentissage puresdumodèleILoNDFvis-à-visdel’ensemble
des méthodes proposées jusqu’à présent. Dans un deuxième temps, nous nous intéressons plus
particulièrement à l’adaptation fine du modèle au cadre précis du filtrage d’informations. Notre
objectif est de mettre en place une stratégie de filtrage orientée-utilisateur plutôt qu’orientée-
système, et ceci notamment en suivant deux types de directions. La première direction concerne
la modélisation utilisateur à l’aide du modèle ILoNDF. Cette modélisation fournit une nouvelle
manière de regarder le profil utilisateur en termes de critères de spécificité, d’exhaustivité et
de contradiction. Ceci permet, entre autres, d’optimiser le seuil de filtrage en tenant compte de
l’importance que pourrait donner l’utilisateur à la précision et au rappel. La seconde direction,
complémentaire de la première, concerne le raffinement des fonctionnalités du modèle ILoNDF
en le dotant d’une capacité à s’adapter à la dérive du besoin de l’utilisateur au cours du temps.
Enfin, nous nous attachons à la généralisation de notre travail antérieur au cas où les données
arrivant en flux peuvent être réparties en classes multiples.
Mots-clés: apprentissage automatique, réseaux de neurones, classification supervisée et non su-
pervisée, détection de nouveauté, flux de données, dérive de concept, filtrage basé sur le contenu,
modélisation utilisateur, analyse des données multidimensionnelles, applications en Intelligence
ArtificielleAbstract
Many applications produce and receive continuous, unlimited, and high-speed data streams.
This raises obvious problems of storage, treatment and analysis of data, which are only just be-
ginning to betreated inthe domain of data streams. On the one hand, itis a question of treating
data streams on the fly without having to memorize all the data. On the other hand, it is also
a question of analyzing, in a simultaneous and concurrent manner, the regularities inherent in
thedatastreamaswellasthenovelties,exceptions,orchangesoccurringinthisstreamovertime.
The main contribution of this thesis concerns the development of a new machine learning ap-
proach — called ILoNDF — which is based on novelty detection principle. The learning of this
model is,contrary to that of its former self, driven not only by the novelty part in the input data
but alsoby the data itself.Thereby, ILoNDFcan continuously extract newknowledge relating to
the relative frequencies of the data and their variables. This makes it more robust against noise.
Being operated in an on-line mode without repeated training, ILoNDF can further address the
primary challenges for managing data streams.
Firstly, we focus on the study of ILoNDF’s behavior for one-class classification when dealing
withhigh-dimensional noisy data.This studyenabled us tohighlight thepurelearning capacities
of ILoNDF with respect to the key classification methods suggested until now. Next, we are
particularly involved intheadaptation of ILoNDFtothe specificcontextof information filtering.
Ourgoalistosetupuser-orientedfilteringstrategiesratherthansystem-orientedinfollowingtwo
typesofdirections.ThefirstdirectionconcernsusermodelingrelyingonthemodelILoNDF.This
providesanewwayoflookingatuser’sneedintermsofspecificity,exhaustivityandcontradictory
profile-contributing criteria. These criteria go on to estimate the relative importance the user
might attach to precision and recall. The filtering threshold can then be adjusted taking into
account this knowledge about user’s need. The second direction, complementary to the first one,
concerns the refinement of ILoNDF’s functionality in order to confer it the capacity of tracking
drifting user’s need over time. Finally, we consider the generalization of our previous work to the
case where streaming data can be divided into multiple classes.
Keywords: machine learning, neural networks, supervised and unsupervised classification, nov-
elty detection, data streams, concept drift, content-based filtering, user modeling, multidimen-
sional data analysis, Artificial Intelligence applicationsTable des matières
Introduction
Chapitre 1
Définitions et éléments clés d’analyse de données
1.1 Qu’est qu’un flux de données? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Représentation du temps dans un flux de données . . . . . . . . . . . . . . . . . . 7
1.2.1 Types de datation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.2 Notion de fenêtrage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Modèles de flux de données : cas spéciaux . . . . . . . . . . . . . . . . . . . . . . 9
1.4 Généralités sur l’analyse de données multidimensionnelles . . . . . . . . . . . . . 11
1.4.1 Les données et types de variables . . . . . . . . . . . . . . . . . . . . . . . 11
1.4.2 Analyse statistique de données . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4.3 Apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4.4 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.4.5 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.4.6 Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.5 Modalités et critères d’évaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.5.1 Évaluation supervisée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.5.2 Évaluation non supervisée . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.6 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Chapitre 2
Panorama sur les méthodes d’analyse de flux de données
2.1 Structures de synthèse de flux de données . . . . . . . . . . . . . . . . . . . . . . 31
2.1.1 Échantillonnage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.1.2 Histogrammes, Sketches, et Ondelettes . . . . . . . . . . . . . . . . . . . . 33
2.1.3 Maintenance en ligne des micro-clusters . . . . . . . . . . . . . . . . . . . 36
2.1.4 Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.2 Clustering de flux de données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
vii

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.

Diffusez cette publication

Vous aimerez aussi