AccueilđŸ‡«đŸ‡·Chercher

Fouille de flots de données

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 (pas nécessairement ou uniquement dans le big data).

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.

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 ; De nouveaux algorithmes ont donc Ă©tĂ© optimisĂ©s en temps de traitement et en occupation mĂ©moire pour rĂ©pondre Ă  cette contraintes d'exploration de donnĂ©es.

En outre, dans beaucoup d'applications, la distribution qui sous-tend les données ou les rÚgles sous-jacentes peuvent changer avec le 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 dénommé « dérive conceptuelle » (« Concept drift »).

Bien que les systĂšmes d'analyse soient de plus en plus automatisĂ©s, l'« analyse humaine » reste importante : un rapport de 2011 publiĂ© par le McKinsey Global Institute[2], prĂ©voyait que rien que pour les États-Unis, pour exploiter le « dĂ©luge de donnĂ©es » il faudrait 140 000 Ă  190 000 travailleurs supplĂ©mentaires experts en « analyse profonde des donnĂ©es » et 1,5 million de gestionnaires de donnĂ©es[3].

Résumés

La « technique de rĂ©sumĂ© ou synopsis » n'explore pas le flot entier, mais interroge des donnĂ©es sĂ©lectionnĂ©es dans le flux. En cela on accepte des rĂ©sultats avec une certaine approximation. Les fenĂȘtres temporelles[4] 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[4] (« Summaries »)) de flux de donnĂ©es et d'effectuer des fouilles dessus. Les rĂ©sumĂ©s servent aussi Ă  « ralentir » le flot de donnĂ©es quand il est trop rapide pour les machines effectuant l'analyse.

Parmi toutes les techniques de résumé figurent :

Échantillonnage alĂ©atoire

Il 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[5], on analyse le flot et remplace les Ă©lĂ©ments du rĂ©servoir-Ă©chantillon selon une certaine probabilitĂ©[6]. Si est la taille du rĂ©servoir, l'algorithme commence par stocker dans le rĂ©servoir les premiers Ă©lĂ©ments du flots. Ensuite, pour chaque Ă©lĂ©ment suivant , un nombre alĂ©atoire est gĂ©nĂ©rĂ© entre 0 et 1, et si , l'Ă©lĂ©ment remplace un Ă©lĂ©ment du rĂ©servoir. La probabilitĂ©, pour le iĂšme Ă©lĂ©ment, d'intĂ©grer le rĂ©servoir est Ă©gale Ă  et dĂ©croit avec le flots.

Sketching

Sketching[7] 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[8]. Les fonctions utilisées sont les fonctions aléatoires indépendantes {-1,+1} 4-wise[9] - [10] - [11], 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[6] sont une approximation de la distribution d'un ensemble de valeurs par une fonction constante par morceaux , de façon à minimiser la somme des carrés des erreurs . 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[12].

Ondelettes

Les ondelettes servent à approcher les données avec une incertitude établie à l'avance[13] - [14]. 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 meilleure approximation selon la norme L2.

Délestage de données

Le délestage de données (« Load shedding[15] »)) 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é[16].

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[17]. 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[18].

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[19] (« cluster »).

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

.

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

.

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

.

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

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[20] les algorithmes de segmentation (« Clustering ») en cinq groupes :

  • les algorithmes de partitionnement
Ce sont, par exemple l'algorithme STREAM[21], et les algorithmes basés sur les méthodes k-means (SPKMEANS) et k-médoids
  • les algorithmes de micro-segmentation (« Micro-Clustering »)
BIRCH[22], 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 tùche 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[23] qui utilise les fractales, STING, WaveCluster[24] qui utilise les ondelettes de Haar, Daubechies, ou Cohen-Debauchies-Feauveau, Hierarchical Grid Clustering.
  • les algorithmes basĂ©s sur les modĂšles
COBWEB, SOM[25] - [26]

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 obsolĂšte 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[27]). 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[28]


Calcul de fréquence

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

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

Applications

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[31] est devenu quelques annĂ©es plus-tard une sociĂ©tĂ© qui semble en plein essor. Hillol Kargupta a cofondĂ© Agnik[32] 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[33].

Recherche des similarités musicales

MusicMiner[34] 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[35]


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 CO2 dans l'atmosphÚre[36].

Logiciels

MOA

Moa[37] (« 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[38] (« 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.

SAMOA

SAMOA[39] (« Scalable Advanced Massive Online Analysis ») est un framework distribué d'apprentissage automatique à partir de flux de données continus. Il se déploie sur des technologies Big Data telles que Storm, Samza et S4. SAMOA est un projet incubator de la fondation Apache.

Notes et références

Notes

(en) Cet article est partiellement ou en totalitĂ© issu de l’article de WikipĂ©dia en anglais intitulĂ© « Data stream mining » (voir la liste des auteurs).
  1. Le plan de cet article est largement inspiré de celui de l'article de Mohamed Medhat Gaber, Arkady Zaslavsky et Shonali Krishnaswamy.
  2. voir Glossaire de l'exploration de données

Références

  1. Mohamed Medhat Gaber, Arkady Zaslavsky, Shonali Krishnaswamy, Mining Data Streams: A Review
  2. Deep analytical talent: Where are they now?, voir aussi : Big data: The next frontier for innovation, competition, and productivity ; Rapport Ă©crit par James Manyika, Michael Chui, Brad Brown, Jacques Bughin, Richard Dobbs, Charles Roxburgh, Angela Hung Byers ; McKinsey Global Institute, mai 2011 et Rapport complet
  3. Lohr, S. (2012). The age of big data ; articles du New York Times, 11.
  4. ENST, Projet MIDAS
  5. Jeffrey Scott Vitter. Random sampling with a reservoir. ACM Trans. Math. Softw., 11(1):37–57, 1985
  6. Dariusz BrzeziƄski, Mining data streams with concept drift
  7. Florin Rusu,Alin Dobra, Statistical Analysis of Sketch Estimators
  8. Florin Rusu, Alin Dobra, Sketching Sampled Data Streams
  9. Luca Trevisan, The Large Deviation of Fourwise Independent Random Variables
  10. 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
  11. AMS without 4-wise independence on product domains, page 4, Définition de fonctions aléatoires indépendantes k-wise
  12. Minos Garofalakis, Johannes Gehrke, Rajeev Rastogi, Querying and mining data streams : You Only Get One Look
  13. Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss, SurïŹngWavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries
  14. Sudipto Guha, Boulos Harb, Wavelet Synopsis for Data Streams: Minimizing Non-Euclidean Error
  15. Brian Babcock, Mayur Datar, Rajeev Motwani, Load Shedding for Aggregation Queries over Data Streams
  16. Yun Chi, Haixun Wang, Philip S. Yu, Loadstar: Load Shedding in Data Stream Mining
  17. Graham Cormode, S. Muthukrishnan, What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically, paragraphe 2 PrĂ©liminaires
  18. Sanghamitra Bandyopadhyay, Ujjwal Maulik, Lawrence B. Holder and Diane J. Cook, Advanced Methods for Knowledge Discovery from Complex Data page 319
  19. Maria E. Orlowska, Xingzhi Sun, Xue Li,Can Exclusive Clustering on Streaming Data be Achieved?
  20. Joao Gama [Knowledge Discovery from Data Stream] CRC Press Edition 2010, page 79 et suivantes
  21. Mohamed Elasmar, Prashant Thiruvengadachari, Javier Salinas Martin,Clustering Data Streams
  22. 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
  23. Daniel BarbarĂ , Ping Chen,Using the Fractal Dimension to Cluster Datasets
  24. Gholamhosein Sheikholeslami, Surojit Chatterjee, Aidong Zhang, WaveCluster:A Multiresolution Clustering Approach for Very Large Spatial Databases
  25. Madjid Khalilian, Norwati Mustapha, Data Stream Clustering: Challenges and Issues
  26. Mohamed Gaber, Joao Gama, STATE-OF-THE-ART IN DATA STREAM MINING - TUTORIAL NOTES FOR THE ECML/PKDD 2007 INTERNATIONAL CONFERENCE
  27. 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
  28. Albert Bifet, Adaptive Learning and Mining for Data Streams and Frequent Patterns.
  29. Joao Gama [Knowledge Discovery from Data Stream] CRC Press Edition 2010, page 103 et suivantes
  30. Joong Hyuk Chang, Won Suk Lee, estWin: adaptively monitoring the recent change of frequent itemsets over online data streams
  31. 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.
  32. Mine Fleet Site officiel
  33. Andry Rakotonirainy, Frederic Maire, context-aware driving behaviour model
  34. Databionic, MusicMiner Site officiel
  35. Hillol Kargupta, Byung-Hoon Park, Sweta Pittie, Lei Liu, Deepali Kushraj,Kakali Sarkar, MobiMine: Monitoring the Stock Market from a PDA.
  36. Hillol Kargupta, JoĂŁo Gama,Wei FanThe Next Generation of Transportation Systems,Greenhouse Emissions, and Data Mining.
  37. The University of Waikato, DATA STREAM MINING,A Practical Approach
  38. Geoff Hulten, Pedro Domingos, VFML Site officiel
  39. (en) « Apache SAMOA »

Voir aussi

Articles connexes

Bibliographie

  • A. Amal, J. Salma: “Novelty Detection In Data Stream Clustering Using The Artificial Immune System”, Proceedings of the 13th European Mediterranean & Middle Eastern Conference on Information Systems (EMCIS), Krakow, Poland, June, 2016.
  • 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
  • Auroop R. Ganguly, JoĂŁo Gama, Olufemi A. Omitaomu, Mohamed M. Gaber & Ranga R. Vatsavai (Eds), Knowledge Discovery from Sensor Data, CRC Press, 2008.
  • 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.
  • Hand D.J., Mannila H., and Smyth P. (2001) Principles of data mining, MIT Press.
  • JoĂŁo Gama, Knowledge Discovery from Data Streams, Chapman and Hall/CRC, 2010.
  • JoĂŁo Gama &Mohamed Medhat Gaber (Eds.), Learning from Data Streams: Processing Techniques in Sensor Networks, Springer, 2007.
  • 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.
  • Lughofer, Edwin, Evolving Fuzzy Systems - Methodologies, Advanced Concepts and Applications, Springer, Heidelberg, 2011.
  • Moamar Sayed-Mouchaweh & Edwin Lughofer (Eds.), Learning in Non-Stationary Environments: Methods and Applications, Springer, New York, 2012.

Liens externes

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent s’appliquer aux fichiers multimĂ©dias.