Algorithme de fouille de flots de données

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique théorique, un algorithme de fouille de flots de données (ou 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]

Exemples de problèmes[modifier | modifier le code]

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

Pour la recherche d'items fréquents[2] dans un flot de données, il y a deux types d'algorithmes : les algorithmes basé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[3] 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[4] 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 \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 \ge (s- \epsilon)N.

DSM-FI[modifier | modifier le code]

Data Stream Mining for Frequent Itemset[5] 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 »[6] 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 »[7] 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[8],[9] ,[10]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[11],[12] (« 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 (\Nu, \sum_{k=1}^\Nu \Chi_i^2,\sum_{k=1}^\Nu \Chi_i) où chaque \Chi_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 calculer pour les algorithmes de streaming, notamment en utilisant les résultats de la complexité de communication.

Voir aussi[modifier | modifier le code]

Notes[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)

Liens internes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Références[modifier | modifier le code]

  1. ENST, Projet MIDAS
  2. Nishad Manerikar, Themis Palpanas, Frequent Items in Streaming Data: An Experimental Evaluation of the State-of-the-Art
  3. Gurmeet Singh Manku, Rajeev Motwani, Approximate Frequency Counts over Data Streams
  4. Hervé Bronnimann, Echantillonnage et Problèmes Géométriques en Ligne
  5. Hua-Fu Li, Suh-Yin Lee et Man-Kwan, ShanAn Efficient Algorithm for Mining Frequent Itemsets over the Entire History of Data Streams
  6. Pedro Domingos, Geoff Hulten, Mining High-Speed Data Streams
  7. Pedro Domingos, Laurie Spencer, Geoff Hulten, Mining Time-Changing Data Streams
  8. Pedro Domingos, Geoff Hulten, Mining High-Speed Data Streams
  9. Albert Bifet, Geoff Holmes, Bernhard Pfahringer, Richard Kirkby, Ricard Gavaldà, New Ensemble Methods For Evolving Data Streams, page 4
  10. Geoff Holmes, Bernhard Pfahringer, Richard Kirkby,Tie Breaking in Hoeffding Trees, page 2
  11. Tian Zhang, Raghu Ramakrishnan, Miron Livny, BIRCH:An Efficient Data Clustering Method For Very Large Databases
  12. Chun Wei, Clustering Data Streams

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