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].
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[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
- ↑ Le plan de cet article est largement inspiré de celui de l'article de Mohamed Medhat Gaber, Arkady Zaslavsky et Shonali Krishnaswamy.
- ↑ a b et c voir Glossaire de l'exploration de données
Références
- ↑ a et b Mohamed Medhat Gaber, Arkady Zaslavsky, Shonali Krishnaswamy, Mining Data Streams: A Review
- ↑ 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
- ↑ Lohr, S. (2012). The age of big data ; articles du New York Times, 11.
- ↑ a et b ENST, Projet MIDAS
- ↑ Jeffrey Scott Vitter. Random sampling with a reservoir. ACM Trans. Math. Softw., 11(1):37–57, 1985
- ↑ a et b Dariusz Brzeziński, Mining data streams with concept drift
- ↑ Florin Rusu,Alin Dobra, Statistical Analysis of Sketch Estimators
- ↑ Florin Rusu, Alin Dobra, Sketching Sampled Data Streams
- ↑ Luca Trevisan, The Large Deviation of Fourwise Independent Random Variables
- ↑ 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
- ↑ AMS without 4-wise independence on product domains, page 4, Définition de fonctions aléatoires indépendantes k-wise
- ↑ Minos Garofalakis, Johannes Gehrke, Rajeev Rastogi, Querying and mining data streams : You Only Get One Look
- ↑ Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss, SurfingWavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries
- ↑ Sudipto Guha, Boulos Harb, Wavelet Synopsis for Data Streams: Minimizing Non-Euclidean Error
- ↑ Brian Babcock, Mayur Datar, Rajeev Motwani, Load Shedding for Aggregation Queries over Data Streams
- ↑ Yun Chi, Haixun Wang, Philip S. Yu, Loadstar: Load Shedding in Data Stream Mining
- ↑ Graham Cormode, S. Muthukrishnan, What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically, paragraphe 2 Préliminaires
- ↑ Sanghamitra Bandyopadhyay, Ujjwal Maulik, Lawrence B. Holder and Diane J. Cook, Advanced Methods for Knowledge Discovery from Complex Data page 319
- ↑ Maria E. Orlowska, Xingzhi Sun, Xue Li,Can Exclusive Clustering on Streaming Data be Achieved?
- ↑ Joao Gama [Knowledge Discovery from Data Stream] CRC Press Edition 2010, page 79 et suivantes
- ↑ Mohamed Elasmar, Prashant Thiruvengadachari, Javier Salinas Martin,Clustering Data Streams
- ↑ 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
- ↑ Daniel Barbarà, Ping Chen,Using the Fractal Dimension to Cluster Datasets
- ↑ Gholamhosein Sheikholeslami, Surojit Chatterjee, Aidong Zhang, WaveCluster:A Multiresolution Clustering Approach for Very Large Spatial Databases
- ↑ Madjid Khalilian, Norwati Mustapha, Data Stream Clustering: Challenges and Issues
- ↑ Mohamed Gaber, Joao Gama, STATE-OF-THE-ART IN DATA STREAM MINING - TUTORIAL NOTES FOR THE ECML/PKDD 2007 INTERNATIONAL CONFERENCE
- ↑ 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
- ↑ Albert Bifet, Adaptive Learning and Mining for Data Streams and Frequent Patterns.
- ↑ Joao Gama [Knowledge Discovery from Data Stream] CRC Press Edition 2010, page 103 et suivantes
- ↑ Joong Hyuk Chang, Won Suk Lee, estWin: adaptively monitoring the recent change of frequent itemsets over online data streams
- ↑ 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.
- ↑ Mine Fleet Site officiel
- ↑ Andry Rakotonirainy, Frederic Maire, context-aware driving behaviour model
- ↑ Databionic, MusicMiner Site officiel
- ↑ Hillol Kargupta, Byung-Hoon Park, Sweta Pittie, Lei Liu, Deepali Kushraj,Kakali Sarkar, MobiMine: Monitoring the Stock Market from a PDA.
- ↑ Hillol Kargupta, João Gama,Wei FanThe Next Generation of Transportation Systems,Greenhouse Emissions, and Data Mining.
- ↑ The University of Waikato, DATA STREAM MINING,A Practical Approach
- ↑ Geoff Hulten, Pedro Domingos, VFML Site officiel
- ↑ (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
- (en) Mining Data Streams Bibliography maintenue par Mohamed Medhat Gaber
- (en) Stream Mining Bibliography maintenue par Haixun Wang, Microsoft Research
v · m | |
---|---|
Type |
|
Généralités | |
Glossaire |
v · m | |
---|---|
Méthodes | |
Services | |
Exploration de données |
|
Outils | |
Organismes | |
Portail de l’informatique
Portail des probabilités et de la statistique