La fouille de flots de donnéesLe plan de cet article est largement inspiré de celui de l'article de Mohamed Medhat Gaber, Arkady Zaslavsky et Shonali Krishnaswamy. () 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 » ().
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 InstituteDeep 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, prévoyait que rien que pour les États-Unis, pour exploiter le il faudrait à travailleurs supplémentaires experts en « analyse profonde des données » et 1,5 million de gestionnaires de donnéesLohr, S. (2012). The age of big data ; articles du New York Times, 11..
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 ENST, Projet MIDAS sont une des techniques pour travailler sur un ensemble restreint du flux et en extraire des motifs (items, itemsets et motifs séquentiels ()) 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 ()) 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 » ()) de Jeffrey Scott VitterJeffrey Scott Vitter. Random sampling with a reservoir. ACM Trans. Math. Softw., 11(1):37–57, 1985, on analyse le flot et remplace les éléments du réservoir-échantillon selon une certaine probabilitéDariusz Brzeziński, Mining data streams with concept drift. 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 SketchingFlorin Rusu,Alin Dobra, Statistical Analysis of Sketch Estimators 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éatoiresFlorin Rusu, Alin Dobra, Sketching Sampled Data Streams. Les fonctions utilisées sont les fonctions aléatoires indépendantes {-1,+1} 4-wise Luca Trevisan, The Large Deviation of Fourwise Independent Random VariablesMinos 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-wiseAMS without 4-wise independence on product domains, page 4, Définition de fonctions aléatoires indépendantes k-wise, 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 () 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 (), les histogrammes équi-distribués, les end-biased histogrammes. Les histogrammes équi-variants 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'autreMinos Garofalakis, Johannes Gehrke, Rajeev Rastogi, Querying and mining data streams : You Only Get One Look.
Ondelettes Les ondelettes servent à approcher les données avec une incertitude établie à l'avanceAnna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss, SurfingWavelets on Streams: One-Pass Summaries for Approximate Aggregate QueriesSudipto Guha, Boulos Harb, Wavelet Synopsis for Data Streams: Minimizing Non-Euclidean Error. 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 ()) 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éYun Chi, Haixun Wang, Philip S. Yu, Loadstar: Load Shedding in Data Stream Mining.
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 partieGraham Cormode, S. Muthukrishnan, What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically, paragraphe 2 Préliminaires. 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 () 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éfinieSanghamitra Bandyopadhyay, Ujjwal Maulik, Lawrence B. Holder and Diane J. Cook, Advanced Methods for Knowledge Discovery from Complex Data page 319. Micro-segment La caractérisation d'un segment (), appelé aussi permet de mémoriser les principales mesures d'un segment sans pour cela mémoriser toutes les observations, ou données, contenues dans le segmentMaria E. Orlowska, Xingzhi Sun, Xue Li,Can Exclusive Clustering on Streaming Data be Achieved? (). définition 1 : soit un segment () 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 () 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'optimisationMohamed Medhat Gaber, Arkady Zaslavsky, Shonali Krishnaswamy, Mining Data Streams: A Review. Les algorithmes dépendent du problème étudié. Trois techniques sont employées pour la fouille des flux de données.
Segmentation On peut classerJoao Gama [Knowledge Discovery from Data Stream] CRC Press Edition 2010, page 79 et suivantes les algorithmes de segmentation () en cinq groupes : les algorithmes de partitionnement Ce sont, par exemple l'algorithme STREAMMohamed Elasmar, Prashant Thiruvengadachari, Javier Salinas Martin,Clustering Data Streams, et les algorithmes basés sur les méthodes k-means (SPKMEANS) et k-médoids les algorithmes de micro-segmentation () BIRCHTian 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, 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 ClusteringDaniel Barbarà, Ping Chen,Using the Fractal Dimension to Cluster Datasets qui utilise les fractales, STING, WaveClusterGholamhosein Sheikholeslami, Surojit Chatterjee, Aidong Zhang, WaveCluster:A Multiresolution Clustering Approach for Very Large Spatial Databases qui utilise les ondelettes de Haar, Daubechies, ou Cohen-Debauchies-Feauveau, Hierarchical Grid Clustering. les algorithmes basés sur les modèles COBWEB, SOMMadjid Khalilian, Norwati Mustapha, Data Stream Clustering: Challenges and IssuesMohamed Gaber, Joao Gama, STATE-OF-THE-ART IN DATA STREAM MINING - TUTORIAL NOTES FOR THE ECML/PKDD 2007 INTERNATIONAL CONFERENCE
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 (), 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 DXminerMohammad 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). 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, UFFTAlbert Bifet, Adaptive Learning and Mining for Data Streams and Frequent Patterns.…
Calcul de fréquence On peut distinguer trois techniques permettant d'aborder la recherche des itemsets fréquents en fouille de flot de donnéesJoao Gama [Knowledge Discovery from Data Stream] CRC Press Edition 2010, page 103 et suivantes : Les techniques tenant compte des transactions passées aussi bien que les transactions récentes