Voir la source de Algorithme de fouille de flots de données

{{ébauche|statistiques}}

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 (informatique)|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é<ref name=midas> [[Télécom ParisTech|ENST]], [http://midas.enst.fr/wakka.php?wiki=PresentatioN Projet MIDAS]</ref> ({{Citation étrangère|lang=en|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 [[algorithme online|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<ref>{{lien web|titre=Support du cours « Algorithmes pour flux de données » au collège de France, le 16 janvier 2018 |auteur=[[Claire Mathieu]]| site=[[Collège de France]]|url=www.college-de-france.fr/media/claire-mathieu/UPL928987789321184108_Cours_CDF_16_janvier_2018.compressed.pdf}}.</ref>.

== Exemples de problèmes ==

=== Recherche de fréquences ===
Pour la recherche  d'items fréquents<ref>Nishad Manerikar, Themis Palpanas, [http://disi.unitn.it/~themis/frequentitems/dke09.pdf Frequent Items in Streaming Data: An Experimental Evaluation of the State-of-the-Art]</ref> 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 ({{Citation étrangère|lang=en|Sketch}}).

==== Comptages ====  
''Sticky Sampling'' et ''Lossy-Counting''<ref>Gurmeet Singh Manku, [[Rajeev Motwani]], [http://ece.ut.ac.ir/dbrg/seminars/SpecialDB/2006/Ghadimi-Abbasi-Pashaei/references/Approximate%20Frequency%20Counts%20over%20Data%20Streams.pdf.pdf  Approximate Frequency Counts over Data Streams]</ref> 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 ({{Citation étrangère|lang=en|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<ref>Hervé  Bronnimann, {{lien brisé|url=http://photon.poly.edu/~hbr/publi/JGA1.pdf |titre=Echantillonnage et Problèmes Géométriques en Ligne }}</ref>'' est un des premiers algorithmes d'exploration des flots de données utilisant le modèle des fenêtres à drapeau ({{Citation étrangère|lang=en|landmark windows model}}). C'est un algorithme paramétrique qui accepte deux paramètres de l'utilisateur : <math>\epsilon \in [0,1]</math> et <math>s \in [0,1] ~\text{avec}~ \epsilon \ll s </math> où  <math>\epsilon</math> 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/<math>\epsilon</math>. La conception de l'algorithme garantit que tous les items (itemsets) dont la fréquence réelle est supérieure à sN (le support <math>s_i</math> de i dans un ensemble de cardinalité N est égal à <math> \frac {f_i}{N}</math> ) sont dans la liste de sortie, aucun item (itemset) dont la fréquence réelle est inférieure à <math> sN - \epsilon N</math> 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 à <math>\epsilon N</math>.

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

===== DSM-FI =====
''Data Stream Mining for Frequent Itemset''<ref> Hua-Fu Li, Suh-Yin Lee et Man-Kwan, Shan{{lien brisé|url=http://selab.iecs.fcu.edu.tw/wiki/images/4/46/An_efficient_algorithm_for_mining_frequent_itemsets_over_the_entire_history_of_data_streams.pdf |titre=An Efficient Algorithm for Mining Frequent Itemsets over the Entire History of Data Streams }}</ref> 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 ====
{{Citation étrangère|lang=en|Very Fast Decision Trees learner}}<ref>Pedro Domingos, Geoff Hulten, [http://www.ir.iit.edu/~dagr/DataMiningCourse/Research_Papers/p71-domingos.pdf Mining High-Speed Data Streams]</ref> 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 ====
{{Citation étrangère|lang=en|Concept-adapting Very Fast Decision Trees learner}}<ref>Pedro Domingos, Laurie Spencer, Geoff Hulten, [http://www.cs.uiuc.edu/class/fa05/cs591han/papers/domingos01.pdf Mining Time-Changing Data Streams]</ref> est une amélioration de l'algorithme précédent en ce qu'il tient compte de la [[Dérive conceptuelle]] ({{Citation étrangère|lang=en|Concept drift}}).

==== Hoeffding tree ====
Un [[arbre de Hoeffding]]<ref>Pedro Domingos, Geoff Hulten, [http://www.cs.washington.edu/homes/pedrod/papers/kdd00.pdf Mining High-Speed Data Streams]</ref>{{,}}<ref name=NEMEDS>Albert Bifet, Geoff Holmes, Bernhard Pfahringer, Richard Kirkby, Ricard Gavaldà, [http://researchcommons.waikato.ac.nz/bitstream/10289/3982/1/New%20Ensemble%20methods.pdf New Ensemble Methods For Evolving Data Streams], page 4</ref> {{,}}<ref name=TBHR>Geoff Holmes, Bernhard Pfahringer, Richard Kirkby, [http://www.liaad.up.pt/~jgama/IWKDDS/Papers/p4.pdf Tie Breaking in Hoeffding Trees], page 2</ref>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({{Citation étrangère|lang=en|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 ({{Citation étrangère|lang=en|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é <math>1 - \delta</math>,  si on se donne <math>\delta</math> à priori.

=== Segmentation ===

==== BIRCH ====
BIRCH<ref>Tian Zhang, Raghu Ramakrishnan, Miron Livny, [http://www.cs.ubc.ca/~rap/teaching/504/2009/slides/birch.pdf BIRCH:An Efﬁcient Data Clustering Method For Very Large Databases]</ref>{{,}}<ref name=Wei>Chun Wei, [http://www.cis.uab.edu/kddm/seminar_home/Chun_ClusteringDataStreams.ppt Clustering Data Streams]</ref> ({{Citation étrangère|lang=en|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 ({{Citation étrangère|lang=en|Clustering Feature}}) composés de <math>(\Nu, \sum_{k=1}^\Nu \Chi_i^2,\sum_{k=1}^\Nu \Chi_i)</math> où chaque <math>\Chi_i</math> est un vecteur, pour résumer les micro-segments  ({{Citation étrangère|lang=en|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  ({{Citation étrangère|lang=en|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 ==
{{Traduction/Référence|en|Streaming algorithm|400384756|type=note}}

{{références}}

== 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}} [[:en:BIRCH (data clustering)|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]]

{{Palette|Exploration de données|Big data}}
{{portail|probabilités et statistiques|informatique théorique}}

[[Catégorie:Apprentissage automatique]]
[[Catégorie:Ingénierie décisionnelle]]
[[Catégorie:Algorithme d'exploration de données]]