Fouille de flots de données

Fouille de flots de données
Exploration de données
Articles principaux
Exploration de données
Fouille de données spatiales
Fouille du web
Fouille de flots de données
Fouille de textes
Fouille d'images
Fouille audio
Articles annexes
Logiciels de fouille de données
Algorithme de fouille de flots de données
Aide
Glossaire du data mining
Contextes liés
Probabilités et statistiques
Information géographique
Imagerie numérique
Informatique
Linguistique
Internet

La Fouille de flots de données[Note 1],[1] (« Data stream mining ») est le processus d'extraction des connaissances de flux de données continus. Un flux/flot de données est une séquence ordonnée d'instances lisibles une seule fois - ou un nombre de fois très faible - dans un système limité en capacité mémoire et en capacité de stockage. Les flux sont continus, illimités, arrivent avec une grande rapidité, et ont une distribution qui change avec le temps. Le trafic réseau, les conversations téléphoniques, les transactions ATM, les recherches sur le web, et les données des capteurs sont des flux/flots de données.

Sommaire

Principes

Lorsqu'il s'agit de requêter un flux de données continu, rapide et sans fin, il n'est pas envisageable d'interroger la totalité du flux, sous peine de créer des contingences et de stopper le flux ; il faut donc inventer de nouveaux algorithmes optimisés en temps de traitement et en occupation mémoire pour répondre aux contraintes de ce type de mining. En outre, dans beaucoup d'applications, la distribution qui sous-tend les données ou les règles sous-jacentes peuvent changer au cours du temps, c'est-à-dire que le but de la prédiction, la classe ou la valeur cible à prédire peuvent évoluer. Ce problème dont doivent tenir compte les techniques de fouille de flots de données est appelé la dérive conceptuelle (« Concept drift »).

Résumés

La technique de résumé ou synopsis permet de ne pas explorer le flot entier, en sélectionnant les données dans le flux. On interroge une partie du flux et en cela on accepte d'obtenir des résultats avec une certaine approximation. Les fenêtres temporelles[2] sont une des techniques pour travailler sur un ensemble restreint du flux et en extraire des motifs (items, itemsets et motifs séquentiels (« Sequential pattern »)) porteurs de connaissance. D'autres techniques telles que les histogrammes, la compression, les sketches, l'échantillonnage statistiques.... permettent elles aussi de créer des résumés[2] (« Summaries »)) de flux de données et d'effectuer des fouilles dessus. Les résumés servent aussi à ralentir le flot de données lorsque celui-ci est trop rapide pour les machines sur lesquelles l'analyse est faite. Parmi toutes les techniques de résumé on trouve donc celles-ci :

Echantillonage aléatoire

L'échantillonnage aléatoire consiste à choisir au hasard dans le flot de données celles qui seront traitées. Par exemple, en utilisant l'algorithme d’échantillonnage à réservoir (« reservoir sampling algorithm »)) de Jeffrey Scott Vitter[3], on analyse le flot et remplace les éléments du réservoir-échantillon selon une certaine probabilité[4]. Si n est la taille du réservoir, l'algorithme commence par stocker dans le réservoir les n premiers éléments du flots. Ensuite, pour chaque éléments suivants t, un nombre aléatoire r est généré entre 0 et 1, et si r*t \le n, l'élément t remplace un élément du réservoir. La probabilité, pour le tième élément, d'intégrer le réservoir est égale à \frac{n}{t} et décroit avec le flots.

Sketching

Sketching[5] est la technique qui permet de résumer le flot de données en utilisant un petit nombre de variables aléatoires créées par projection du domaine du flux sur un domaine restreint à l'aide de fonctions aléatoires[6]. Les fonctions utilisées sont les fonctions aléatoires indépendantes {-1,+1} 4-wise[7],[8],[9], les fonctions de hachage,...

Histogrammes

Les histogrammes sont des structures qui agrègent la distribution des données du flot en découpant le domaine de l'histogramme en paniers/paquets (« buckets ») selon une règle pré-définie. Les histogrammes les plus utilisés en fouille de flot de données sont les histogrammes équi-variants (« V-optimal »), les histogrammes équi-distribués, les end-biased histogrammes. Les histogrammes équi-variants[4] sont une approximation de la distribution d'un ensemble de valeurs v_1, v_2, \cdots, v_n par une fonction constante par morceaux \hat v(i), de façon à minimiser la somme des carrés des erreurs \sum_{k=1}^n(v_i-\hat v(i))^2. Les histogrammes équi-distribués sont découpés en paniers de telle sorte que la somme des 'barres' des histogrammes soient égales (approximativement) d'un panier à l'autre[10].

Ondelettes

Les ondelettes servent à approcher les données avec une incertitude établie à l'avance[11],[12]. Les coefficients d'ondelettes sont la projection du signal sur une base orthogonale. Les vecteurs de base les plus utilisées sont les ondelettes de Haar. Avec ces ondelettes la reconstruction du signal est la meilleur approximation selon la norme L2.

Délestage de données

Le délestage de données (« Load shedding[13] »)) est la technique qui consiste à réduire de flot de données en entrée de l'algorithme de DM en écartant des données du flots, généralement en fonction d'une certaine probabilité[14].

Techniques d'optimisation

Algorithmes d'approximation

Ce sont des techniques probabilistes qui donnent un résultat dans une limite donnée à l'avance. Toutes les méthodes de Monte-Carlo et l'algorithme de las Vegas en font partie[15]. Ces algorithmes donnent des résultats approchés avec des erreurs contenues dans des limites pré-établies.

Fenêtres Glissantes

Les fenêtres glissantes servent à restreindre l'analyse sur les éléments les plus récents du flot de données. C'est une méthode déterministe.

Granularité de sortie d'algorithme

La granularité de sortie d'algorithme (« Algorithm output granularity ») sert de paramètres pour piloter les sorties en fonction de la mémoire disponible, du débit du flux de données et du temps restant pour remplir la mémoire. Cet algorithme est donc conscient des ressources qu'il a sa disposition et agit en fonction de ces ressources. La granularité de sortie est la quantité de résultats générés dont l'approximation par rapport à la valeur exacte est dans les limites d'une mesure prédéfinie[16].

Micro-segment

La caractérisation d'un segment (« Clustering Feature »), appelé aussi « Micro-cluster » permet de mémoriser les principales mesures d'un segment sans pour cela mémoriser toutes les observations, ou données, contenues dans le segment[17] (« cluster »).

définition 1 : soit C un segment (« cluster ») composé de n vecteurs Χi (i=1..n) tels que \Chi_i=(\Chi_i^1, \Chi_i^2,..,\Chi_i^d). On appelle caractérisation du segment C, le tuple noté

CF=(n,ls^1,ls^2,.., ls^d,ss) \mathrm{~ o\grave u~ }ls^j=\sum_{i=1}^n \Chi_i^j \scriptscriptstyle\text{ (j=1,2,..d)} \displaystyle\text{, et } ss=\sum_{i=1}^n \sum_{j=1}^d (\Chi_i^j)^2

.

définition 2 : le centre c et le rayon r du segment (« cluster ») C composé de n variables Χi (i=1..n) sont donnés par :

c=\biggl(\frac{ls^1}{n},\frac{ls^2}{n},..,\frac{ls^d}{n}\biggr) \text{ et } r=\biggl(\frac{ss}{n} - \frac{\sum_{j=1}^d (ls^j)^2}{n^2}\biggr)^{1/2}

.

propriété d'additivité : soient C et C' deux segments sur un espace à d dimensions. on a

C \cup C' = \biggl(n+n', ls^1+ls'^1,ls^2+ls'^2,..,ls^d+ls'^d, ss+ss' \biggr)

.

Avec cette représentation et cette propriété, un segment peut être maintenu de manière incrémental, ce qui est un point fort pour la fouille de flots de données.

Techniques et Algorithmes

Article principal : Algorithme de fouille de flots de données

On applique un algorithme de data mining sur un résumé ou sur le flux de données régulé par une technique d'optimisation[1]. Les algorithmes dépendent du problème étudié. Trois techniques sont employées pour la fouille des flux de données.

Segmentation

On peut classer[18] les algorithmes de segmentaton (« Clustering ») en cinq groupes :

  • les algorithmes de partitionnement
Ce sont, par exemple l'algorithme STREAM[19], et les algorithmes basés sur les méthodes k-means (SPKMEANS) et k-médoids
  • les algorithmes de micro-segmentation (« Micro-Clustering »)
BIRCH[20], CluStream qui utilisent la caractérisation d'un segment par les CF-vecteurs (voir caractérisation d'un segment), et deux processus, un en temps réel et local pour construire les micro-clusters, l'autre en tache de fond pour construire la segmentation globale.
  • les algorithmes fondées sur les fonctions de densité
DBSCAN, OPTICS
  • les algorithmes à structure de grille
Fractal Clustering[21] qui utilise les fractales, STING, WaveCluster[22] qui utilise les ondelettes de Haar, Daubechies, ou Cohen-Debauchies-Feauveau, Hierarchical Grid Clustering.
  • les algorithmes basés sur les modèles
COBWEB, SOM[23],[24]

Classification

Le but de la classification dans la fouille de flots/flux de données est d'apprendre un modèle à partir des données du passé déjà classées et classer les futures arrivées en utilisant ce modèle. La difficulté dans ce processus vient de la dérive conceptuelle (« Concept drift »), qui rend le modèle obsolette s'il n'évolue pas. Une des façons de prendre en compte la dérive conceptuelle est d'utiliser un ensemble de modèles formés sur autant d'ensembles de données différents provenant du flux, en remplaçant le modèle ayant le plus d'erreurs par un nouveau modèle (voir par exemple DXminer[25]). On trouve parmi les principaux algorithmes de classification tenant compte de la dérive conceptuelle, les algorithmes tels que FLORA, SVM adapté aux flux de données, Last, CVFDT, UFFT[26]...

Calcul de Fréquence

On peut distinguer trois techniques permettant d'aborder la recherche des itemsets fréquents en fouilles de flot de données[27] :

  • Les techniques tenant compte des transactions passées aussi bien que les transactions récentes
Les algorithmes utilisant cette approche utilise des fenêtres à jalon[Note 2]. Parmi ces algorithmes on compte lossy-counting, sticky sampling et DSM-FI qui utilise aussi un FP-tree.
  • Les techniques tenant plus compte des transactions récentes que celles du passé
Les algorithmes utilisant cette approche utilise des fenêtres glissantes ou des fenêtres pondérées [Note 2]. estWin[28] est un de ses algorithmes.
  • Les techniques tenant compte de différentes granularités temporelles
Les algorithmes utilisant cette approche utilise des fenêtres dilatées (« tilted time window ») [Note 2].Parmi ceux-ci l'algorithme FP-Stream utilise aussi un FP-tree.

Applications

Quelques exemples permettent de voir que la fouille de flots de données est en constante relation avec la vie de tous les jours.

Suivi de véhicules

Une idée émise en 2004 pour contrôler en temps réel une flotte de véhicules et leurs conducteurs[29] est devenu quelques années plus-tard une société qui semble en plein essor. Hillol Kargupta a co-fondé Agnik[30] pour proposer aux assureurs le logiciel MineFleet™ qui est une application d'exploration de flots de données dont le principal but est de surveiller la santé des véhicules (poids-lourds) ainsi que le comportement des conducteurs en vue de réduire les coûts d'entretien et d'assurances.

On peut aussi noter ce prototype développé par Frédéric Maire et Andry Rakotonirainy permettant d'expliquer et de prévoir le comportement d'un conducteur au volant[31].

Recherche des audios similarités

MusicMiner[32] est un logiciel libre permettant entre autres de détecter des similarités entre plages musicales.

Suivi du marché des actions

Pour suivre une liste de valeurs mobilières[33]...

Réduction de l'émission de CO2 par les moyens de transport

Il s'agit ici plutôt d'une reflexion sur l'apport potentiel de la fouille de flux de données sur la réduction des émissions de C0² dans l'atmosphère[34]

Logiciels

MOA

Moa[35] (« Massive Online Analysis »), outre le nom d'un oiseau disparu originaire de Nouvelle-Zélande, est le nom du petit frère de Weka pour la fouille de flots de données (« Data stream mining »). C'est une plateforme spécialisée, mise à disposition par l'université de Waikato, Nouvelle-Zélande, permettant la mise en œuvre d'algorithmes en vue d'explorer les flux de données continus.

RapidMiner™

RapidMiner™ de Rapid-I peut intégrer un plug-in pour analyser les flux de données.

VFML

VFML[36] (« Very Fast Machine Learning ») est une suite d'outils destinés à explorer les flux de données rapides et changeants et les grosses bases de données, proposée par Geoff Hulten et Pedro Domingos sous licence libre. Ce sont des outils écrits en Langage C et en Python.

Voir aussi

Glossaires

Glossaire du data mining

Notes

  1. ↑ Le plan de cet article est largement inspiré de celui de l'article de Mohamed Medhat Gaber, Arkady Zaslavsky et Shonali Krishnaswamy.
  2. ↑ a, b et c voir Glossaire du data mining

(en) Cet article est partiellement ou en totalité issu de l’article en anglais intitulé « Data stream mining » (voir la liste des auteurs)

Références

  1. ↑ a et b Mohamed Medhat Gaber, Arkady Zaslavsky, Shonali Krishnaswamy, Mining Data Streams: A Review
  2. ↑ a et b ENST, Projet MIDAS
  3. ↑ Jeffrey Scott Vitter. Random sampling with a reservoir. ACM Trans. Math. Softw., 11(1):37–57, 1985
  4. ↑ a et b Dariusz Brzeziński, Mining data streams with concept drift
  5. ↑ Florin Rusu,Alin Dobra, Statistical Analysis of Sketch Estimators
  6. ↑ Florin Rusu, Alin Dobra, Sketching Sampled Data Streams
  7. ↑ Luca Trevisan, The Large Deviation of Fourwise Independent Random Variables
  8. ↑ Minos Garofalakis, Johannes Gehrke, Rajeev Rastogi, Querying and mining data streams : You Only Get One Look, page 66, construction de fonctions aléatoires indépendantes k-wise
  9. ↑ AMS without 4-wise independence on product domains, page 4, Définition de fonctions aléatoires indépendantes k-wise
  10. ↑ Minos Garofalakis, Johannes Gehrke, Rajeev Rastogi, Querying and mining data streams : You Only Get One Look
  11. ↑ Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss, SurfingWavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries
  12. ↑ Sudipto Guha, Boulos Harb, Wavelet Synopsis for Data Streams: Minimizing Non-Euclidean Error
  13. ↑ Brian Babcock, Mayur Datar, Rajeev Motwani, Load Shedding for Aggregation Queries over Data Streams
  14. ↑ Yun Chi, Haixun Wang, Philip S. Yu, Loadstar: Load Shedding in Data Stream Mining
  15. ↑ Graham Cormode, S. Muthukrishnan, What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically, paragraphe 2 Préliminaires
  16. ↑ Sanghamitra Bandyopadhyay, Ujjwal Maulik, Lawrence B. Holder and Diane J. Cook, Advanced Methods for Knowledge Discovery from Complex Data page 319
  17. ↑ Maria E. Orlowska, Xingzhi Sun, Xue Li,Can Exclusive Clustering on Streaming Data be Achieved?
  18. ↑ Joao Gama [Knowledge Discovery from Data Stream] CRC Press Edition 2010, page 79 et suivantes
  19. ↑ Mohamed Elasmar, Prashant Thiruvengadachari, Javier Salinas Martin,Clustering Data Streams
  20. ↑ Tian Zhang, Raghu Ramakrishnan et al: BIRCH: An Efficient Data Clustering Method for Very Large Databases, Technical Report, Computer Sciences Dept., Univ. of Wisconsin-Madison, 1995
  21. ↑ Daniel Barbarà, Ping Chen,Using the Fractal Dimension to Cluster Datasets
  22. ↑ Gholamhosein Sheikholeslami, Surojit Chatterjee, Aidong Zhang, WaveCluster:A Multiresolution Clustering Approach for Very Large Spatial Databases
  23. ↑ Madjid Khalilian, Norwati Mustapha, Data Stream Clustering: Challenges and Issues
  24. ↑ Mohamed Gaber, Joao Gama, STATE-OF-THE-ART IN DATA STREAM MINING - TUTORIAL NOTES FOR THE ECML/PKDD 2007 INTERNATIONAL CONFERENCE
  25. ↑ Mohammad M. Masud, Qing Chen, Jing Gao, Latifur Khan, Jiawei Han, Bhavani Thuraisingham, Classification and Novel Class Detection of Data Streams in A Dynamic Feature Space
  26. ↑ Albert Bifet, Adaptive Learning and Mining for Data Streams and Frequent Patterns
  27. ↑ Joao Gama [Knowledge Discovery from Data Stream] CRC Press Edition 2010, page 103 et suivantes
  28. ↑ Joong Hyuk Chang, Won Suk Lee, estWin: adaptively monitoring the recent change of frequent itemsets over online data streams
  29. ↑ Hillol Kargupta, Ruchita Bhargava, Kun Liu, Michael Powers, Patrick Blair, Samuel Bushra, James Dull, Kakali Sarkar, martin Klein, Mitesh Vasa, David Handy VEDAS : A Mobile and Distributed Data Stream Mining System for Real-Time Vehicle Monitoring.
  30. ↑ Mine Fleet Site officiel
  31. ↑ Andry Rakotonirainy, Frederic Maire, context-aware driving behaviour model
  32. ↑ Databionic, MusicMiner Site officiel
  33. ↑ Hillol Kargupta, Byung-Hoon Park, Sweta Pittie, Lei Liu, Deepali Kushraj,Kakali Sarkar, MobiMine: Monitoring the Stock Market from a PDA
  34. ↑ Hillol Kargupta, João Gama,Wei FanThe Next Generation of Transportation Systems,Greenhouse Emissions, and Data Mining
  35. ↑ The University of Waikato, DATA STREAM MINING,A Practical Approach
  36. ↑ Geoff Hulten, Pedro Domingos, VFML Site officiel


Bibliographie

  • ] C. Aggarwal, J. Han, J. Wang, P. S. Yu, A Framework for Clustering Evolving Data Streams, Proc. 2003 Int. Conf. on Very Large Data Bases, Berlin, Germany, Sept. 2003
  • Klinkenberg, Ralf: Learning Drifting Concepts: Example Selection vs. Example Weighting. In Intelligent Data Analysis (IDA), Special Issue on Incremental Learning Systems Capable of Dealing with Concept Drift, Vol. 8, No. 3, pages 281—300, 2004.
  • P. Domingos and G. Hulten. Mining High-Speed Data Streams. In Proceedings of the Association for Computing Machinery Sixth International Conference

on Knowledge Discovery and Data Mining, 2000.





Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Fouille de flots de données de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

  • Algorithme de fouille de flots de données — Exploration de données Articles principaux Exploration de données Fouille de données spatiales Fouille du web Fouille de flots de données Fouille de textes …   Wikipédia en Français

  • Fouille de données spatiales — Exploration de données Articles principaux Exploration de données Fouille de données spatiales Fouille du web Fouille de flots de données Fouille de textes …   Wikipédia en Français

  • Fouille du web — Exploration de données Articles principaux Exploration de données Fouille de données spatiales Fouille du web Fouille de flots de données Fouille de textes …   Wikipédia en Français

  • Fouille de textes — Exploration de données Articles principaux Exploration de données Fouille de données spatiales Fouille du web Fouille de flots de données Fouille de textes …   Wikipédia en Français

  • Fouille d'images — Exploration de données Articles principaux Exploration de données Fouille de données spatiales Fouille du web Fouille de flots de données Fouille de textes …   Wikipédia en Français

  • Fouille audio — Exploration de données Articles principaux Exploration de données Fouille de données spatiales Fouille du web Fouille de flots de données Fouille de textes …   Wikipédia en Français

  • Exploration de données — Articles principaux Exploration de données Fouille de données spatiales Fouille du web Fouille de flots de données Fouille de textes …   Wikipédia en Français

  • Logiciels de fouille de données — Exploration de données Articles principaux Exploration de données Fouille de données spatiales Fouille du web Fouille de flots de données Fouille de textes …   Wikipédia en Français

  • Glossaire du data mining — Exploration de données Articles principaux Exploration de données Fouille de données spatiales Fouille du web Fouille de flots de données Fouille de textes …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”