Fouille de flots de données

La fouille de flots de données^, (« 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, 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.

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 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 (« 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, on analyse le flot et remplace les éléments du réservoir-échantillon selon une certaine probabilité. Si ${\displaystyle n}$ est la taille du réservoir, l'algorithme commence par stocker dans le réservoir les ${\displaystyle n}$ premiers éléments du flots. Ensuite, pour chaque élément suivant ${\displaystyle t}$, un nombre aléatoire ${\displaystyle r}$ est généré entre 0 et 1, et si ${\displaystyle r*t\leq n}$, l'élément ${\displaystyle t}$ remplace un élément du réservoir. La probabilité, pour le ${\displaystyle t}$^ième élément, d'intégrer le réservoir est égale à ${\displaystyle {\frac {n}{t}}}$ et décroit avec le flots.

Sketching

Sketching 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. Les fonctions utilisées sont les fonctions aléatoires indépendantes {-1,+1} 4-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 (« 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 sont une approximation de la distribution d'un ensemble de valeurs ${\displaystyle v_{1},v_{2},\cdots ,v_{n}}$ par une fonction constante par morceaux ${\displaystyle {\hat {v}}(i)}$, de façon à minimiser la somme des carrés des erreurs ${\displaystyle \sum _{i=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.

Ondelettes

Les ondelettes servent à approcher les données avec une incertitude établie à l'avance^,. 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 »)) 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é.

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. 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.

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

définition 1 : soit ${\displaystyle C}$ un segment (« cluster ») composé de n vecteurs ${\displaystyle \mathrm {X} _{i}}$ (i=1..n) tels que ${\displaystyle \mathrm {X} _{i}=(\mathrm {X} _{i}^{1},\mathrm {X} _{i}^{2},..,\mathrm {X} _{i}^{d})}$. On appelle caractérisation du segment ${\displaystyle C}$, le tuple noté

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

.

définition 2 : le centre c et le rayon r du segment (« cluster ») ${\displaystyle C}$ composé de n variables ${\displaystyle \mathrm {X} _{i}}$ (i=1..n) sont donnés par :

${\displaystyle 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 ${\displaystyle C{\text{ et }}C'}$ deux segments sur un espace à d dimensions. on a

${\displaystyle 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

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

• les algorithmes de partitionnement

Ce sont, par exemple l'algorithme STREAM, et les algorithmes basés sur les méthodes k-means (SPKMEANS) et k-médoids

• les algorithmes de micro-segmentation (« Micro-Clustering »)

BIRCH, 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 qui utilise les fractales, STING, WaveCluster qui utilise les ondelettes de Haar, Daubechies, ou Cohen-Debauchies-Feauveau, Hierarchical Grid Clustering.

• les algorithmes basés sur les modèles

COBWEB, SOM^,

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). 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…

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 :

• 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. 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 . estWin 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 ») . 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 est devenu quelques années plus-tard une société qui semble en plein essor. Hillol Kargupta a cofondé Agnik 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.

Recherche des similarités musicales

MusicMiner 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…

Réduction de l'émission de CO₂ 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 CO₂ dans l'atmosphère.

Logiciels

MOA

Moa (« 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 (« 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 (« 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

Références

Voir aussi

Articles connexes

• Glossaire du data mining

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

• Portail de l’informatique
• Portail des probabilités et de la statistique