Algorithme de fouille de flots de données

Cet article est une ébauche concernant les probabilités et la statistique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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[modifier | modifier le code]

Description[modifier | modifier le code]

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Différences avec les algorithmes onlines[modifier | modifier le code]

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[modifier | modifier le code]

Recherche de fréquences[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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 : $\epsilon \in [0,1]$ et $s\in [0,1]~{\text{avec}}~\epsilon \ll s$ où $\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/ $\epsilon$ . La conception de l'algorithme garantit que tous les items (itemsets) dont la fréquence réelle est supérieure à sN (le support $s_{i}$ de i dans un ensemble de cardinalité N est égal à ${\frac {f_{i}}{N}}$ ) sont dans la liste de sortie, aucun item (itemset) dont la fréquence réelle est inférieure à $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 à $\epsilon N$ .

Sticky Sampling[modifier | modifier le code]

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 à ${\frac {1}{r}}$ . Il utilise trois paramètres $\epsilon$ - le taux d'erreur - s le seuil de support, et $\delta$ la probabilité d’échec souhaités par l'analyste. Si $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 $f\geq (s-\epsilon )N$ .

DSM-FI[modifier | modifier le code]

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[modifier | modifier le code]

VFDT[modifier | modifier le code]

« 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[modifier | modifier le code]

« 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[modifier | modifier le code]

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é $1-\delta$ , si on se donne $\delta$ à priori.

Segmentation[modifier | modifier le code]

BIRCH[modifier | modifier le code]

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 $(\mathrm {N} ,\sum _{k=1}^{\mathrm {N} }\mathrm {X} _{i}^{2},\sum _{k=1}^{\mathrm {N} }\mathrm {X} _{i})$ où chaque $\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[modifier | modifier le code]

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[modifier | modifier le code]

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

↑ ENST, Projet MIDAS
↑ 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.
↑ Nishad Manerikar, Themis Palpanas, Frequent Items in Streaming Data: An Experimental Evaluation of the State-of-the-Art
↑ Gurmeet Singh Manku, Rajeev Motwani, Approximate Frequency Counts over Data Streams
↑ Hervé Bronnimann, « Echantillonnage et Problèmes Géométriques en Ligne »^{(Archive.org • Wikiwix • Archive.is • Google • Que faire ?)}
↑ 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 ?)}
↑ Pedro Domingos, Geoff Hulten, Mining High-Speed Data Streams
↑ Pedro Domingos, Laurie Spencer, Geoff Hulten, Mining Time-Changing Data Streams
↑ Pedro Domingos, Geoff Hulten, Mining High-Speed Data Streams
↑ Albert Bifet, Geoff Holmes, Bernhard Pfahringer, Richard Kirkby, Ricard Gavaldà, New Ensemble Methods For Evolving Data Streams, page 4
↑ Geoff Holmes, Bernhard Pfahringer, Richard Kirkby, Tie Breaking in Hoeffding Trees, page 2
↑ Tian Zhang, Raghu Ramakrishnan, Miron Livny, BIRCH:An Efﬁcient Data Clustering Method For Very Large Databases
↑ Chun Wei, Clustering Data Streams

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

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[modifier | modifier le code]

(en) BIRCH sur Wiki anglophone

Articles connexes[modifier | modifier le code]

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

[midas-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

[NEMEDS-10] Albert Bifet, Geoff Holmes, Bernhard Pfahringer, Richard Kirkby, Ricard Gavaldà, New Ensemble Methods For Evolving Data Streams, page 4

[TBHR-11] Geoff Holmes, Bernhard Pfahringer, Richard Kirkby, Tie Breaking in Hoeffding Trees, page 2

[12] Tian Zhang, Raghu Ramakrishnan, Miron Livny, BIRCH:An Efﬁcient Data Clustering Method For Very Large Databases

[Wei-13] Chun Wei, Clustering Data Streams

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

v · m Exploration de données
Type	Fouille de données spatiales Fouille du web Fouille de flots de données Fouille de textes Fouille d'images Fouille audio
Généralités	Algorithmes Logiciels
Glossaire

v · m Big data
Méthodes	Algorithme de fouille de flots de données Analyse des données Parallélisme
Services	Centre de données Cloud computing Opinion mining Opt in Opt out
Exploration de données	Fouille de données spatiales Fouille du web Fouille de flots de données Fouille de textes Fouille d'images Fouille audio Glossaire de l'exploration de données
Outils	Base de données relationnelle Hadoop Logiciels de fouille de données Robot d'indexation Système de gestion de base de données NoSQL NewSQL Technologies matérielles dédiées
Organismes	Union internationale des télécommunications
Histoire d'Internet Révolution numérique Science des données Données ouvertes