Résumé de flux de données

Concepts de base des flux de données

Une définition d’un flux de données est présentée par Golab et Özsu : « A data stream is a real-time, continuous, ordered (implicitly by arrival time or explicitly by timestamp) sequence of items. It is impossible to control the order in which items arrive, nor is it feasible to locally store a stream in its entirety. Likewise, queries over streams run continuously over a period of time and incrementally return new results as new data arrive. These are known as long-running, continuous, standing, and persistent queries. »
Une deuxième définition est aussi proposée : « Un flux de données est une séquence de données structurées que l’on peut considérer comme infinie d’éléments générés de façon continue à un rythme rapide et parfois variable. « Rapide » signifie que la vitesse d’arrivée des nouveaux éléments est grande devant les capacités de traitement et de stockage disponibles ».
Plusieurs définitions peuvent être proposées, néanmoins, toutes s’accordent sur les principales caractéristiques de ces évènements. Nous distinguons dans ce qui suit la notion d’évènement qui représente un élément du flux et la notion de données qui est la description contenue dans les évènements.
Continues : les évènements arrivent d’une manière continue et séquentielle. Rapides : les évènements sont produits à un rythme rapide par rapport aux capacités de traitement du système qui les reçoit (e.g. ‘ 100K messages par seconde dans le marché des transactions par Internet) ;
Ordonnés : l’ordre des évènements est généralement défini par rapport au temps soit implicitement par temps d’arrivée ou explicitement par une estampille temporelle de production à la source (timestamp). En fonction de la représentation du temps dans le flux, cette estampille est soit physique (e.g. une date), soit logique (e.g. un nombre incrémental associé aux évènements).
Volume illimité : le nombre d’évènements dans un flux de données est potentiellement infini (e.g. communications téléphoniques de l’AT&T : 1Go / heure). La mémorisation de la totalité des données est non-envisageable. Cependant, des techniques d’archivage peuvent être déployées en parallèle du traitement classique du flux.
A caractère push : les évènements se présentent d’eux-mêmes. Les sources sont programmées afin d’envoyer régulièrement leurs mesures. Le système recevant le flux n’a aucun contrôle sur ces sources.
Sources incontrôlables : aucun contrôle n’est possible sur le débit des sources de données. Le débit peut varier de quelques kilo octets par seconde (e.g. évènements provenant des capteurs) à des giga octets par seconde (e.g. évènements circulant sur un canal OC-768 pour la transmission des données par fibres optiques). Les évènements n’arrivent pas à un rythme constant. Le débit avec lequel ils arrivent contribue dans le choix du système de gestion de flux de donnés utilisé. Incertitude : les évènements qui arrivent au système sont fiables. Cependant, l’imprécision porte sur la sémantique du flux (e.g. l’ordonnancement et la complétude des évènements). Il peut en effet manquer quelques évènements, avoir des duplications, etc. Ces perturbations peuvent être liées à une déficience de la source, à des problèmes de transmission ou à des problèmes de réseau, etc.

Modèle de communication

Le système classique de traitement de l’information se base sur un modèle dit « data-pull », dans lequel la collecte des données est réalisée par des commandes liées aux Système de Gestion des Bases de Données. Dans ce modèle, il faut aller chercher et collecter l’information à partir de différentes sources (base de données, systèmes pair-à-pair, etc.).
L’augmentation du volume de données a amené à la création de très grandes bases de données et par la suite à des entrepôts de données.
D’un point de vue général, la principale fonction d’un entrepôt de données concerne l’intégration et l’historisation des données. L’alimentation de ces entrepôts se fait de façon périodique par l’utilisation d’un ETL 7. Une première étape consiste à collecter les informations à partir de plusieurs bases de production. Ces informations sont par la suite utilisées afin d’alimenter l’entrepôt de données en respectant les étapes suivantes :
Découverte des données : il s’agit d’identifier, à partir des sources, les données à conserver dans l’entrepôt. Une sélection judicieuse de ces données est nécessaire. Un mauvais choix peut considérablement compliquer les phases suivantes de l’alimentation ;
Extraction des données : il s’agit de collecter les données utiles dans les systèmes de production. Une phase d’identification des données modifiées est importante afin d’importer le minimum d’information dans l’entrepôt ;
Transformation des données : cette étape permet, à l’aide de filtres, de rendre les données cohérentes avec la structure de l’entrepôt.
Les informations stockées dans l’entrepôt font l’objet d’interrogation et/ou de fouille. L’analyse et le traitement des données se font traditionnellement dans les entrepôts où elles sont agrégées. Pour alléger les opérations de fouille, l’utilisation de bases d’études (Datamarts ou magasins de données) est souhaitée. Une base d’étude représente une vue partielle de l’entrepôt mais orientée métier ce qui permet de réduire le nombre d’opérations sur les bases de production.
Avec l’émergence des flux, les données sont produites à une vitesse et dans des quantités telles que la technologie actuelle ne permet pas de les traiter de façon satisfaisante poussant ainsi ce modèle classique de communication à être re-visité. L’architecture doit s’adapter à la distribution et l’hétérogénéité des données, à leur volumétrie croissante et à leur taux d’arrivée. Les méthodes d’extraction, de transformation et d’analyse doivent être étendues à la logique des flux où les données arrivent d’elles mêmes avec une vitesse très importante selon un modèle dit « data-push ». L’utilisation de méthodes et de techniques de traitements en temps réel devient nécessaire. Pour les traitement « rapides » supportant l’imprécision, il est possible de passer par des entre pôts résumés appelés « mini entrepôt de données ». Cependant, à terme, cette structure devient à son tour énorme tandis que l’entrepôt de données de départ devient impossible à maintenir. La logique de cette nouvelle architecture, consiste à traiter les données à la volée sous forme de flux et à appliquer en temps réel les opérations d’analyse et de contrôle. Afin de satisfaire ces contraintes, de nouveaux outils appelés Systèmes de Gestion de Flux de Données (SGFD) sont apparus. Dans ces systèmes, les données issues de différentes sources sont transitoires et temporairement stockées dans la mémoire centrale du SGFD. Afin d’appliquer des analyses a posteriori sur les données des flux, des techniques de résumé permettant de conserver une trace de l’histoire du flux peuvent être prévues. Les bases de résumé ainsi construites contiennent les informations nécessaires pour effectuer des requêtes d’agrégats ou des analyses statistiques sur les données, mais sous une forme plus compacte. La qualité des résultats est ajustée en fonction des ressources disponibles. Ces résumés sont périodiquement remontés jusqu’aux entrepôts (au moyen d’un ETL) et par la suite transformés en base d’étude sur lesquelles se font des opérations d’analyse.

Flux de données distribués

Avec le développement des technologies de l’information et de la communication, de plus en plus d’informations sont générées et échangées par les applications localisées sur différents nœuds physiquement distribués. De nouvelles architectures sont à prévoir afin de gérer efficacement les contraintes liées à cette diversité. Certains systèmes ont adopté une architecture centralisée tandis que d’autres sont basés sur une architecture distribuée.
Dans le modèle centralisé, les données sont envoyées par les différentes sources (i.e. nœuds) vers un coordinateur avant de passer au système central (i.e.SGFD). A l’aide d’index , le coordinateur peut accéder rapidement aux données. L’analyse de ces données est réalisée localement dans le SGFD. L’avantage de cette architecture consiste à minimiser les coûts par rapport à une architecture distribuée et permet de faciliter les jointures entre les flux. Cependant, celle-ci présente plusieurs inconvénients :
Des temps de réponses importants étant donné que l’ensemble des tâches d’analyse est envoyé vers un système unique ;
Une saturation du réseau : le fait d’utiliser un système centralisé restreint les capacités disponibles en bandes passantes provoquant ainsi des goulots d’étranglements et par conséquent l’indisponibilité du système ;
L’architecture centralisée est moins adaptée aux flux ayant des débits importants et variables. Ces flux bloquent l’arrivée des données vers le nœud central et empêchent le système d’intégration de collecter l’information et de l’acheminer vers le système central (cette contrainte dépend du nombre de flux différents) .
Pour pallier les limitations d’une architecture centralisée, plusieurs travaux  ont proposé un modèle qui prend en considération l’aspect distribué des sources de données, des ressources de calcul et des liens de communication.
Dans une architecture distribuée, une partie des calculs est effectuée sur les différents nœuds et les résultats sont envoyés vers le coordinateur (i.e. distribution du traitement et centralisation du résultat). Les avantages de ce système sont multiples :
Réduction de temps de réponse : cette architecture fournit un grand degré de parallélisme ce qui minimise les temps de latences ;
Réduction de la charge : le traitement et l’analyse des données sont partagés ce qui conduit à une charge plus faible destinée aux SGFD. Par ailleurs, si des erreurs de traitement surgissent, celles-ci peuvent être localisées et contrôlées directement sur le nœud en question. Par conséquent, le système reste toujours opérationnel ;
La réduction de la charge de communication entraîne une réduction de la consommation d’énergie étant donné que chaque nœud sera réservé à une source (i.e. parallélisme au niveau de la bande passante).

Tâches de fouille sur flux de données

Les algorithmes de fouille sur les flux de données ont été élaborés afin d’extraire des connaissances à partir des données des flux. La conception de ces algorithmes doit tenir compte de la variabilité du débit des flux ainsi que du caractère infini de ce dernier. Nous présentons dans cette section une liste non exhaustive des principaux travaux élaborés pour différentes tâches de fouille de flux de données.

Détection d’anomalie dans un flux de données

Dans plusieurs tâches d’analyse, on est face à un nombre considérable de variables qui seront sauvegardées ou échantillonnées. Une des premières étapes pour obtenir des analyses cohérentes serait la détection des anomalies. Les anomalies sont considérées comme une erreur ou un bruit. Ce sont des données aberrantes qui peuvent engendrer des estimations biaisées et des résultats incorrects. Il est ainsi important de les identifier avant de commencer l’analyse .
Une définition exacte d’une anomalie dépend souvent de plusieurs hypothèses sur la structure des données et de la méthode de détection appliquée. Cependant, certaines définitions sont considérées suffisamment générales pour faire face à divers types de données et de méthodes . Dans , Hawkins définit une anomalie comme une observation qui s’écarte tellement des autres observations au point d’éveiller les soupçons.
Les techniques actuelles de détection d’anomalies peuvent être divisées en quatre catégories : méthodes statistiques méthodes basées sur le calcul des distances  méthodes basées sur la densité et méthodes basées sur la classification. La plupart de ces méthodes souffrent de l’hypothèse sur la distribution ainsi que de la multidimensionnalité des données. C’est l’exemple des histogrammes qui sont efficaces lors de l’analyse d’un seul attribut mais qui perdent leur efficacité pour les données ayant de grandes dimensions, car ils n’ont pas la capacité d’analyser simultanément plusieurs caractéristiques . De plus, la plupart de ces techniques supposent que la distribution des données est stationnaire or cette caractéristique ne peut pas être appliquée aux données du flux (concept drift 10).
La nature infinie du modèle de flux de données signifie qu’il est impossible de stocker toutes les données ou de réaliser plusieurs passes sur elles. Pour cela, les algorithmes de détection de changements doivent satisfaire les contraintes suivantes : les besoins en mémoire doivent être constants ou augmenter logarithmiquement, et l’algorithme doit se limiter à un seul passage sur les données. Nous les avons classés selon la dimensionnalité et le type de données utilisé dans chaque technique.

Recherche d’évènements fréquents dans un flux

Les évènements fréquents (en anglais Frequent Items ou Heavy hitters ou Hot items) sont les éléments qui apparaissent le plus souvent dans un flux de données. Un utilisateur définit un seuil sur la fréquence de ces évènements. Les évènements considérés comme fréquents sont ceux qui apparaissent avec une fréquence supérieure à celle définie par l’utilisateur.
Il existe plusieurs algorithmes utilisés pour la recherche des évènements fréquents tels que Apriori, Eclat, FPgrowth, etc . Ces méthodes ne peuvent pas être appliquées dans le cadre des flux de données étant donné qu’elles nécessitent plusieurs passes pour calculer les évènements les plus fréquents.
Trouver exactement les évènements fréquents en un seul passage requiert O(min(|A|, N)) (A : l’alphabet du flux. Souvent |A| n’est pas connu à l’avance. N : taille du flux) en espace mémoire. Les évènements fréquents peuvent être définis sur la totalité du flux ou sur des fenêtres de taille fixe ou variable. Avoir des solutions exactes au problème des évènements fréquents engendre des coûts élevés. C’est pourquoi, dans plusieurs travaux, les auteurs ont opté pour des solutions approchées.

Table des matières

Introduction générale
1 Résumé généraliste de flux de données
2 Interrogation des résumé de flux de données
3 Plan du manuscrit
1 Les flux de données
1.1 Introduction
1.2 Concepts de base des flux de données
1.2.1 Définition
1.2.2 Structure et types de données
1.2.2.1 Flux de données structurées
1.2.2.2 Flux de données semi-structurées
1.2.2.3 Flux de données non-structurées
1.2.2.4 Types de données dans un flux
1.3 Modèles de données
1.3.1 Modèle des séries temporelles
1.3.2 Modèle de la caisse enregistreuse
1.3.3 Modèle probabiliste
1.3.4 Modélisation temporelle des flux de données
1.4 Modèle de communication
1.5 Flux de données distribués
1.6 Tâches de fouille sur flux de données
1.6.1 Détection d’anomalie dans un flux de données
1.6.2 Recherche d’évènements fréquents dans un flux
1.6.3 Classification non supervisée d’un flux de données
1.6.4 Classification supervisée d’un flux de données
1.7 Systèmes de gestion de flux de données
1.7.1 Applications de bases de données Vs. applications de flux de données
1.7.2 Caractéristiques attendues d’un SGFD
1.7.2.1 Exigences sur les fonctionnalités des systèmes
1.7.2.2 Exigences sur la performance des systèmes
1.7.3 Gestion du temps et fenêtrage
1.7.4 SGFD Vs. Systèmes de gestion d’événements complexes (SGEC)
1.7.4.1 Systèmes traditionnels de gestion de flux de données
1.7.4.2 Systèmes de gestion d’événements complexes
1.8 Domaines d’application
1.8.1 Télécommunications
1.8.2 Analyses financières
1.8.3 Réseaux de capteurs
1.8.4 Télésurveillance médicale
1.9 Synthèse
2 Résumé de flux de données
2.1 Introduction
2.2 Définition d’un résumé de flux de données
2.3 Conception d’un résumé de flux de données
2.3.1 Conception simple d’un résumé de flux de données
2.3.1.1 Échantillonnage
2.3.1.2 Histogrammes
2.3.1.3 Sketchs
2.3.2 Conception complexe d’un résumé de flux de données
2.3.2.1 Organisation temporelle complexe
2.3.2.2 Algorithmes de résumés généralistes
2.4 Synthèse
3 Traitement des requêtes continues
3.1 Introduction
3.2 Traitement de requêtes continues dans les SGBD
3.2.1 Requêtes continues dans Tapestry
3.2.2 Requêtes continues dans OpenCQ
3.2.3 Requêtes continues dans NiagaraCQ
3.2.4 Requêtes continues dans Oracle
3.3 Traitement de requêtes continues dans les SGFD
3.3.1 File d’attente et stratégie de planification
3.3.2 Requêtes continues sur fenêtres glissantes
3.3.3 Expiration des données
3.3.4 Traitement des requêtes continues dans Esper
3.3.5 Notion de requêtes hybrides continues sur flux de données
3.3.5.1 Définition d’une requête hybride
3.3.5.2 Évaluation des requêtes hybrides
3.4 Synthèse et positionnement
4 Etude des résumés de flux : cas de StreamSamp et CluStream
4.1 Introduction
4.2 Résumé de StreamSamp
4.2.1 Structure du résumé
4.2.1.1 Pondération
4.2.1.2 Effet des paramètres
4.2.2 Persistance des résumés
4.2.3 Tâches d’analyse
4.2.3.1 Constitution de l’échantillon final
4.2.3.2 Tâches de requête
4.2.3.3 Tâches de fouille
4.2.4 Limites de StreamSamp
4.2.5 StreamSamp+
4.2.5.1 Structure de données
4.2.5.2 Réponse aux requêtes
4.3 Résumé de CluStream
4.3.1 Structure du résumé
4.3.1.1 Système de clichés dans CluStream
4.3.1.2 Paramétrage
4.3.1.3 Persistance des résumés
4.3.2 Tâches d’analyses
4.3.2.1 Reconstitution de l’horizon temporel
4.3.2.2 Requêtes d’agrégats
4.3.2.3 Tâches de fouille
4.4 Expérimentations
4.4.1 Vitesse d’exécution et volume occupé
4.4.2 Évaluation des requêtes d’agrégat
4.4.2.1 Évaluation de la moyenne
4.4.2.2 Évaluation de la médiane
4.4.3 Évaluation sur les tâches de fouille
4.4.3.1 Évaluation de la classification non supervisée
4.4.3.2 Évaluation de la classification supervisée
4.4.4 Discussion
4.5 Synthèse
5 Résumé Hybride de flux de données
5.1 Introduction
5.2 Performances de StreamSamp et CluStream
5.3 Principe de l’approche hybride
5.3.1 Critères de passage
5.3.1.1 Critère de variance
5.3.1.2 Critère de position des barycentres
5.3.2 Processus de passage
5.3.2.1 Poids des évènements
5.3.2.2 Ordre de passage des événenements
5.4 Utilisation d’une réserve
5.4.1 Taille de la réserve
5.4.2 Règles de passage
5.5 Résumé hybride
5.5.1 Paramétrage de l’approche
5.5.2 Tâches d’analyse
5.5.2.1 Réponse aux requêtes
5.6 Expérimentations
5.6.1 Vitesse d’exécution
5.6.2 Évaluation des requêtes d’agrégat
5.6.2.1 Évaluation de la moyenne
5.6.2.2 Évaluation de la médiane
5.6.3 Évaluation sur des tâches de fouille
5.6.3.1 Évaluation de la classification non supervisée
5.6.3.2 Évaluation de la classification supervisée
5.7 Synthèse
6 Exploitation de résumés de flux de données
6.1 Introduction
6.2 Formulation du problème
6.3 Gestion des résumés
6.4 Exploitation statique des résumés
6.4.1 Cas des fenêtres physiques
6.4.2 Cas des fenêtres logiques
6.4.3 Implémentation de l’approche
6.4.4 Limites de l’approche
6.5 Exploitation dynamique des résumés
6.5.1 Architecture du système DSi
6.5.2 Module de régénération
6.5.2.1 Cas des fenêtres physiques
6.5.2.2 Cas des fenêtres logiques
6.5.3 Processus de synchronisation
6.5.3.1 Cas des fenêtres physiques
6.5.3.2 Cas des fenêtres logiques
6.6 Contraintes de fonctionnement des approches
6.7 Requêtes de sélection
6.8 Expérimentations
6.8.1 Environnement de développement
6.8.2 Étude des performances des deux architectures
6.8.3 Expérimentation sur le module du résumé
6.8.3.1 Calcul de l’espace disque utilisé pour un taux maximum d’erreur
6.8.3.2 Etude de la sensibilité des algorithmes à la variation du délai
6.8.4 Etude de complexité
6.9 Synthèse
7 Conclusion
7.1 Perspectives
7.1.1 Perspectives liées à la construction de résumés généralistes
7.1.2 Perspectives liées à l’intégration des résumés dans les SGFD
Annexe
A Jeux de données
A.1 KDD CUP 99
A.2 Cover Type
A.3 France Télécom
B Algorithmes de résumé
B.1 Échantillonnage
B.1.1 Échantillonnage réservoir
B.1.2 Échantillonnage réservoir biaisé
B.1.3 Échantillonnage périodique
B.1.4 Échantillonnage avec réserve
B.1.5 Échantillonnage chaîné
B.2 Sketchs
B.2.1 Flajolet Martin
B.2.2 Count Min
B.2.3 Count
C Interrogation d’une requête : approche statique et approche dynamique
C.1 Fichier de configuration
C.2 Approche statique
C.3 Approche dynamique
Publications
Bibliographie

Télécharger le rapport complet