Classification de Flux de Données par

Échantillonnages sur Fenêtres InclinéesBaptiste Csernel, Thésard 1er année

Fabrice Clérot, Superviseur FT R&D

Georges Hébrail, Superviseur ENST

Plan

Classification Automatique de Flux de Données

StreamSamp Tests Perspectives

Les Flux de Données

Définition Un flux de donnée est une séquence infinie

d’éléments générés de façon continue à un rythme rapide.

Domaines d’Applications

Logs de sites Internet Tickets de communications téléphoniques Indices Boursiers Données de capteurs

Consommation Trafic routier Géologiques

Classification Automatique de flux de Données

Réaliser une typologie des éléments du flux en les regroupant par classes.

Pouvoir réaliser ces regroupements sur n’importe quelle partie du flux.

Contraintes des Algorithmes de Traitement des Flux de Données Au plus un passage par élément Temps de traitement par élément court Ressources CPU et mémoire utilisées par

élément faibles Applicable à l’ensemble du flux ou juste une

portion de ce dernier

CluStream

Division du traitement en deux parties, une en ligne, et une hors ligne.

Partie en ligne : Création et maintenance de micro clusters. Archivage régulier de l’état de ces micro clusters

dans des clichés. Partie hors ligne :

Classification finale réalisée à partir des micro clusters.

StreamSamp

Algorithme basé sur troix principes :

L’échantillonnage du flux

Le Stockage des échantillons dans une structure de fenêtre inclinées (tilted windows)

Séparation d’une partie en ligne et hors ligne

Algorithme (1/3) (partie en ligne)

….. 1117 1116 1115

Flux de DonnéesÉchantillonnage

à taux fixe αÉchantillons de taille

T et d’ordre 0

1114 1110

1107 1001 1091 1083

1078 1069 1061 1053

Jusqu’à L échantillons d’ordre o.

Algorithme (2/3) (partie en ligne)

1110

1107 1001 1091 1083

1078 1069 1061 1053

1048 1036 1031 1022

L = 3

1004 983 962 944

918 802 786 764

1078 1061 1036 1022

Échantillons de taille T et d’ordre o.

Échantillons de taille T et d’ordre o + 1.

Tirage aléatoire de T/2 éléments de chaque échantillon père

Algorithme (3/3) (partie hors ligne) Les échantillons portant sur la partie du flux à

analyser son fusionnés.

Chaque éléments d’un fichier d’ordre i reçoit une pondération de 2^(o)

Une méthode de classification traditionnelle (ici nuées dynamique) est appliquée à cet échantillon représentatif du flux.

Tests expérimentaux

Jeu de données KDD cup 1999 500 000 éléments 34 variables quantitatives Moyennes des scores sur six essais Scores calculés pour 5 clusters utilisateurs Score = Somme de l’inertie intra cluster

Scores

CluStream StreamSamp

Tout le Flux 1747 1412

1er moitié du Flux

1506 1389

2nd moitié du

Flux

1680 1155

Avantages et Défauts

Avantages Vitesse d’exécution

rapide et indépendante de la dimension.

Faible nombre de paramètres. (T, L, α)

Concentration de données adaptée au débit.

Défauts Poids très élevés sur les

échantillons représentants des portions du flux trop anciennes.

Perd les outliers.

Perspectives

Tester l’efficacité de StreamSamp pour d’autres traitements comme l’estimation de moments.

Adapter StreamSamp de façon à l’appliquer à une sélection effectuée au préalable sur le flux.

Bibliographie

L. Golab, M.T. Özsu, Data Stream Management Issue – A Survey (2003).

S. Muthukrishnan, Data Streams Algorithm and Applications (2003).

C.C. Aggarwal et al, A Framework for Clustering Evolving Data Streams (2003).

R. Motwani et al, Models and Issues In Data Stream (2002).

Algorithme (1/3) (partie en ligne) Echantillonnage du flux à taux fixe α dans un

fichier de taille fixe T auquel est assigné l’ordre 0.

Quand le fichier est plein un nouveau fichier est entammé.

Algorithme (2/3) (partie en ligne) Quand le nombre de fichiers d’un même

ordre o atteint une limite L, les deux plus fichiers d’ordre i sont fusionnés en un fichier d’ordre o+1.

Le nouveau fichier est formé par tirage aléatoire de T/2 éléments de chacun des fichiers pères.