Algorithme de fouille de flots de données

En sciences de l'informatique, les algorithmes de fouille de flots de données reçoivent en entrée un flot continue d'items qui doivent être examinés en peu de passes (en général, ils le sont en une seule passe). Ces algorithmes ont 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.

Algorithmes

Recherche de fréquences

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

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

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 : et où est le taux d'erreur et s le seuil de support souhaités par l'analyste. Si N est le nombre d'items (itmesets) venant d'arriver, l'algorithme utilise des fenêtres de longueur 1/. 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 à ) sont dans la liste de sortie, aucun item (itemset) dont la fréquence réelle est inférieure à 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 à .

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 à . Il utilise trois paramètres - le taux d'erreur - s le seuil de support, et δ la probabilité d’échec souhaités par l'analyste. Si , 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ément dont la fréquence .

DSM-FI

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

VFDT

« 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

« 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

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 − δ, si on se donne δ à priori.

Segmentation

BIRCH

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 où chaque Χ_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.

Voir aussi

Notes

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

Liens internes

Liens externes

• BIRCH sur Wiki anglophone

Références

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

• Portail de l’informatique
• Portail des probabilités et des statistiques