Algorithme de fouille de flots de données

En informatique théorique, un algorithme de fouille de flots de données, ou algorithme de streaming de streaming algorithm en anglais, est un algorithme prenant en entrée un flot continu d'items. Ces algorithmes ont en général peu de mémoire à leur disposition (beaucoup moins que la taille du volume en entrée) et peu de temps à accorder à chaque item.

Ces contraintes peuvent impliquer qu'un tel algorithme fournit une réponse approchée fondée sur l'exploitation d'un résumé^[1] (« Summaries ») du flot de données en mémoire.

Modèle

Description

Différences avec les algorithmes onlines

Le modèle partage certains aspects avec les algorithmes onlines, mais les deux modèles sont différents. Dans un algorithmes de streaming la réponse peut être donnée de façon différée, et la difficulté est le peu d'espace disponible, il peut même y avoir plusieurs passes sur la donnée. Au contraire pour les algorithme online, les décisions doivent être prises au fur et à mesure de la réception des informations, et les ressources en espace et en temps de calcul ne sont pas limitées^[2].

Exemples de problèmes

Recherche de fréquences

Pour la recherche d'items fréquents^[3] dans un flot de données, il y a deux types d'algorithmes : les algorithmes fondés sur les comptages et les algorithmes axés sur les résumés (« Sketch »).

Comptages

Sticky Sampling et Lossy-Counting^[4] sont deux algorithmes importants dans ce domaine ne serait-ce que parce qu'ils sont des références. Ce sont tous les deux des algorithmes orientés faux-positifs (« false-positive ») à savoir, ils s'autorisent à présenter en résultat des items ou des itemsets fréquents alors qu'ils ne le sont pas, mais aucun faux-négatifs sont oubliés.

Lossy-Counting

Lossy-Counting^[5] est un des premiers algorithmes d'exploration des flots de données utilisant le modèle des fenêtres à drapeau (« landmark windows model »). C'est un algorithme paramétrique qui accepte deux paramètres de l'utilisateur : ${\displaystyle \epsilon \in [0,1]}$ et ${\displaystyle s\in [0,1]~{\text{avec}}~\epsilon \ll s}$ où ${\displaystyle \epsilon }$ est le taux d'erreur et s le seuil de support souhaités par l'analyste. Si N est le nombre d'items (itemsets) venant d'arriver, l'algorithme utilise des fenêtres de longueur 1/${\displaystyle \epsilon }$. La conception de l'algorithme garantit que tous les items (itemsets) dont la fréquence réelle est supérieure à sN (le support ${\displaystyle s_{i}}$ de i dans un ensemble de cardinalité N est égal à ${\displaystyle {\frac {f_{i}}{N}}}$ ) sont dans la liste de sortie, aucun item (itemset) dont la fréquence réelle est inférieure à ${\displaystyle sN-\epsilon N}$ sont dans la liste de sortie, et les fréquences estimées ne sont éloignées des fréquences réelles que d'un facteur au plus égal à ${\displaystyle \epsilon N}$.

Sticky Sampling

Sticky Sampling utilise des fenêtres de longueur fixe, et un taux d’échantillonnage r, ie il choisit un élément avec une probabilité égale à ${\displaystyle {\frac {1}{r}}}$. Il utilise trois paramètres ${\displaystyle \epsilon }$ - le taux d'erreur - s le seuil de support, et ${\displaystyle \delta }$ la probabilité d’échec souhaités par l'analyste. Si ${\displaystyle t={\frac {1}{\epsilon }}\log(\epsilon ^{-1}\delta ^{-1})}$, les t premiers arrivants sont choisis avec un taux r égal à 1, les 2t suivants avec un taux égal à 2, .... Si l'analyste demande la sortie des items (itemsets) au-dessus du seuil s, l'algorithme sort les éléments dont la fréquence ${\displaystyle f\geq (s-\epsilon )N}$.

DSM-FI

Data Stream Mining for Frequent Itemset^[6] est un algorithme créé par Hua-Fu Li, Suh-Yin Lee et Man-Kwan Shan pour explorer les itemsets fréquents dans un flot de données.

Arbres de décision

VFDT

« Very Fast Decision Trees learner »^[7] réduit le temps d'apprentissage pour les grands ensembles incrémentaux de données en sous-échantillonnant le flux de données. VFDT utilise un arbre de Hoeffding.

CVFDT

« Concept-adapting Very Fast Decision Trees learner »^[8] est une amélioration de l'algorithme précédent en ce qu'il tient compte de la Dérive conceptuelle (« Concept drift »).

Hoeffding tree

Un arbre de Hoeffding^{[9],[10],[11]} est un algorithme d'arbre de décision incrémental et perpétuel, capable d'apprentissage à partir d'un flots de données massif, avec l'hypothèse que la distribution des échantillons ne varie pas en fonction du temps - pas de dérive conceptuelle(« Concept drift »). Cet algorithme construit un arbre d'une manière incrémentale, en rassemblant dans les feuilles suffisamment d'informations pour pouvoir choisir à un moment donné quel est le meilleur attribut pour transformer ces feuilles en nœuds. La division de la feuille - qui transforme la feuille en nœud - en deux sous-feuilles s'effectue en utilisant l'inégalité de Hoeffding (« Hoeffding bound »), mesure statistique qui permet de savoir à partir de combien d'échantillons un estimateur est proche de la vraie valeur de la variable estimée avec une probabilité ${\displaystyle 1-\delta }$, si on se donne ${\displaystyle \delta }$ à priori.

Segmentation

BIRCH

BIRCH^[12],[13] (« balanced iterative reducing and clustering using hierarchies ») est un algorithme d'exploration de données non-supervisé utilisé pour produire une segmentation hiérarchisée sur des volumes de données particulièrement importants. Cet algorithme utilise des vecteurs de caractérisation de segment (« Clustering Feature ») composés de ${\displaystyle (\mathrm {N} ,\sum _{k=1}^{\mathrm {N} }\mathrm {X} _{i}^{2},\sum _{k=1}^{\mathrm {N} }\mathrm {X} _{i})}$ où chaque ${\displaystyle \mathrm {X} _{i}}$ est un vecteur, pour résumer les micro-segments (« micro-cluster ») afin de bâtir un arbre équilibré composé de ces micros-segments. Les informations contenues dans un vecteur CF sont suffisantes pour calculer les estimateurs de moyenne, variance, les centroids, et certaines distances. L'arbre CF possède trois paramètres : B le facteur de branche, T le seuil, L le nombre de feuilles maximum sous les derniers nœuds. Les feuilles sont reliées entre elles par des pointeurs prec et suiv. L'algorithme se déroule en trois phases : la première consiste à lire les données et à construire l'arbre CF dans la limite de la mémoire disponible. La deuxième phase sert à éliminer les aberrations (« outlier ») et un algorithme de segmentation est utilisé dans la phase trois pour segmenter les feuilles.

Bornes inférieures

Des bornes inférieures peuvent être calculées pour les algorithmes de streaming, notamment en utilisant les résultats de la complexité de communication.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Streaming algorithm » (voir la liste des auteurs).

1. ENST, Projet MIDAS
2. Claire Mathieu, « Support du cours « Algorithmes pour flux de données » au collège de France, le 16 janvier 2018 », sur Collège de France.
3. Nishad Manerikar, Themis Palpanas, Frequent Items in Streaming Data: An Experimental Evaluation of the State-of-the-Art
4. Gurmeet Singh Manku, Rajeev Motwani, Approximate Frequency Counts over Data Streams
5. Hervé Bronnimann, « Echantillonnage et Problèmes Géométriques en Ligne »^{(Archive.org • Wikiwix • Archive.is • Google • Que faire ?)}
6. Hua-Fu Li, Suh-Yin Lee et Man-Kwan, Shan« An Efficient Algorithm for Mining Frequent Itemsets over the Entire History of Data Streams »^{(Archive.org • Wikiwix • Archive.is • Google • Que faire ?)}
7. Pedro Domingos, Geoff Hulten, Mining High-Speed Data Streams
8. Pedro Domingos, Laurie Spencer, Geoff Hulten, Mining Time-Changing Data Streams
9. Pedro Domingos, Geoff Hulten, Mining High-Speed Data Streams
10. Albert Bifet, Geoff Holmes, Bernhard Pfahringer, Richard Kirkby, Ricard Gavaldà, New Ensemble Methods For Evolving Data Streams, page 4
11. Geoff Holmes, Bernhard Pfahringer, Richard Kirkby, Tie Breaking in Hoeffding Trees, page 2
12. Tian Zhang, Raghu Ramakrishnan, Miron Livny, BIRCH:An Efficient Data Clustering Method For Very Large Databases
13. Chun Wei, Clustering Data Streams

Voir aussi

Bibliographie

• R. Agrawal, S. P. Ghosh, T. Imielinski, B. R. Iyer, and A. N. Swami. An interval classifier for database mining applications. In VLDB '92, pages 560-573, 1992.
• R. Agrawal, T. Imielinski, and A. Swami. Database mining: A performance perspective. IEEE Trans. on Knowl. and Data Eng., 5(6):914-925, 1993.
• A. Asuncion and D. Newman. UCI machine learning repository, 2007

Liens externes

• (en) BIRCH sur Wiki anglophone

Articles connexes

• filtre de Bloom, utilisé pour tester la présences d'un élément dans certains algorithmes
• Algorithme de Flajolet–Martin