- Classification de données. - Types de données et les mesures. - Classification sur le flux de données...29. - Classification sur le flux de données ...29. - Dans ce rapport, nous parlons des algorithmes de classification en général et particulièrement de ceux qui sont pour le flux de données. - un gros volume de données qui arrive continuellement. - Cette méthode perd beaucoup d’informations concernant le jeu entier de données. - Une simulation simple de classification sur un flux de données est également réalisée en se basant sur cet algorithme.. - De nombreuses mesures de proximité sont proposées, se basant sur la nature de données. - L’abstraction des données est un processus d’extraction d’une représentation simple et compacte pour un jeu de données. - z k ) sont des objets dans un jeu de données D en k dimensions, x i , y i , z i sont des attributs, i = 1. - Les calculs de proximité sont des mesures de la ressemblance ou de l’association entre les paires d'objets de données. - Nous présentons une description brève de mesures pour chaque type d’attribut de données. - Il est une approche hybride : utiliser tous les points de données et ainsi un un centroid pour former les classes. - CURE est conçu pour traiter de gros jeux de données. - Dans la première, l’algorithme utilise des échantillonnages aléatoires qui sont retirés du jeu de données et classifié pour former des partitions partielles. - En conséquence, CLARA peut traiter un plus gros jeu de données que PAM. - Au début, les points de données sont partitionnés dans k classes : Un point appartient à une classe si le point de référence de cette classe est le plus proche. - Si le jeu de données est gros et l’échantillon est représentatif du jeu de données, alors l’algorithme peut converger plus vite qu’un algorithme qui doit examiner séquentiellement tous les points.. - Il vise à augmenter l’extensibilité de k-means pour de gros jeux de données. - Notons que DS et CS stocke les statistiques de données.. - Chaque classe a un jeu de données supprimées représenté par le triplet ci- dessus pour représenter tous les points appartenant à cette classe. - La densité est représentée par le nombre d’objets de données dans le voisinage. - Elles ne travaillent que dans un espace métrique, donc elles sont utilisées dans la classification de données spatiales. - L’idée de ces méthodes est qu’on divise l’espace de données en cellules. - En fait, elle est un produit cartésien de sous intervalles d’attributs de données. - Au contraire, les parties de basse fréquence du signal correspondent aux régions de l’espace de données où les objets sont concentrés. - CLIQUE est une solution pour la classification de données en haute dimension. - Cette approche cible à la situation de haute dimension, de gros jeu de données et beaucoup de classes.. - Par conséquent, on néglige la distribution de données au long de chaque dimension. - MAFIA utilise une taille d’intervalle adaptative pour diviser chaque dimension dépendant de la distribution de données dans la dimension. - La complexité de MAFIA est O (c k + kn) tels que c est un constant, n est le nombre de points de données est k est le nombre maximum de dimension des sous- espaces. - Donc la classification de données de catégorie est vraiment compliquée que celle de données numériques. - Il prend un échantillon aléatoire d’un jeu de données pour faire la classification. - ROCK peut être utilisé pour faire la classification de gros jeux de données et bien extensible à la taille de la base de données.. - La complexité de ROCK est O (n 2 +nm m m a +n 2 logn) tels que m m est le nombre maximum de voisins et m a est le nombre moyen de voisins d’un objet de données, n est la taille de l’échantillon de données qu’il traite.. - Figure 4: Une base de données et sa représentation de graphe. - Le support d’un pair de valeurs d’attribut est le nombre d’uplets (objets) dans le jeu de données alors que ces deux valeurs apparaissent à la fois. - Le support d’une région d’intervalle est le nombre de uplets dans le jeu de données qui appartiennent à cette région. - CACTUS est un algorithme extensible (scalable algorithm) puisqu'il exige seulement un passage du jeu de données. - Classification sur le flux de données. - Les flux de données diffèrent d’autres modèles de stockage des données sur les caractéristiques suivantes [54]:. - Les éléments de données sur un flux de données arrivent en ligne.. - Les flux de données sont potentiellement illimités en taille.. - Une fois qu’un élément de données sur le flux est traité, il est soit archivé soit écarté.. - Par conséquent, le calcul sur un flux de données doit être simple à cause de ces restrictions. - Un flux de données est une séquence ordonnée de points de données qui ne peuvent être accédés que séquentiellement et une seule fois (balayage linéaire). - Plusieurs algorithmes de classification sur un flux de données ont été proposés. - Avant tout, nous présentons deux algorithmes de classification développés pour faire de la classification sur le flux de données STREAM-LOCALSEARCH et GenIc. - L’idée principale de l’algorithme est qu’on fait tout d’abord la classification sur chaque morceau de données en utilisant une procédure qui s’appelle LOCALSEARCH. - GenIc (Generalized Incremental) est un algorithme de fenêtrage pour la classification d’un flux de données. - Chaque morceau de n points de données comme une génération. - Et on continue à traiter le flux de données. - GenIc est indépendant de l’ordre d’arrivée des points de données en prenant tous les lots de points d’une façon indépendante de n points précédents. - Premièrement, c’est la mauvaise qualité pour les flux de données évolués, car ils ne gardent que k centres, pas des classes. - Deuxièmement, c’est leur capacité limitée pour découvrir et exploiter les classes sur différentes parties du flux de données pendant le temps. - BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) est un algorithme qui travaille efficacement sur de gros jeux de données. - C’est pourquoi il peut traiter un grand volume de données en utilisant une mémoire limitée. - il a besoin d’un seul balayage du jeu de données. - La communauté du domaine de classification trouve que BIRCH est l’un des meilleurs algorithmes qui peuvent traiter de gros jeux de données.. - Pour faciliter l’insertion au niveau algorithmique, on considère un point de données comme une sous-classe qui dispose d’un seul membre. - Au début, on choisira sans doute un seuil à zéro afin de garder tous les points de données comme une sous-classe aux feuilles de l’arbre. - De plus, quand on traite un jeu de données très large, cette tâche a lieu souvent. - Une ancienne entrée de feuille est considérée comme un aberrant potentiel si elle a peu de points de données. - Quand l’espace pour un arbre de CF dépasse sa capacité, c’est peut-être qu’il y a encore des points de données qui peuvent être insérés ou absorbés dans l’arbre de CF courant sans changer le seuil. - On peut sauvegarder de tels points de données sur le disque d’une façon similaire à celle du traitement des aberrants. - L’avantage de ce mécanisme est que, en général, plus de points de données peuvent être insérés dans l’arbre avant qu’on doive reconstruire l’arbre.. - Le Cluster Feature est une structure de données représentant une sous-classe.. - Pour un jeu de données complètement numérique en d dimensions, un CF est défini comme suivant. - Etant donné N points de données (en d dimensions) dans une classe. - L’algorithme BIRCH est appliqué sur ces types de données de la même manière dont on l’applique sur les données purement numériques, sauf que la compacité d’une classe dans 2 cas n’est pas pareille. - La plupart des algorithmes de classification sur flux de données peuvent traiter de gros jeux de données et traiter de nouveaux points de données qui arrivent. - CLUSTREAM est un algorithme de classification sur les flux de données évoluées. - La composante hors ligne est utilisée pour fournir une compréhension rapide des classes du flux de données. - Les micros classes sont stockées à des moments particuliers du flux de données comme des snapshots. - On suppose que le flux de données se compose d’un jeu des enregistrements multidimensionnels X 1 , X 2. - Une micro classe d’un ensemble de données de points en d dimensions. - CF 2 est un vecteur de d valeurs (d entrées), chaque valeur stocke la somme x des valeurs carrées de données. - CF1 est un vecteur de d valeurs (d entrées), chaque valeur stocke la somme x des valeurs de données. - n est le nombre de points de données dans la micro classe.. - Quand un nouveau point de données. - Un point de données peut être considéré comme une entrée libre. - C’est le nombre maximum de points de données d’une entrée feuille afin de décider si une entrée feuille est considérée comme une sous classe ou un aberrant. - Pour insérer un point de données dans l’arbre, tout d’abord, ce point est représenté comme une entrée. - La classification sur le flux de données est très importante dans divers domaines d’application dont les données arrivent sous forme d’un flux. - BIRCH est incrémental et il utilise des résumés compacts de données au lieu des données initiales. - C’est pourquoi il est très efficace dans le traitement des gros jeux de données avec un espace limité. - Caractéristiqu es de données. - Sphérique Petits jeux de données. - Sphérique Jeux de données relativement gros. - Arbitraire Jeux de données relativement gros. - Traite les aberrants Complexité : O (n 2 log n) Utiliser le résumé de données. - Sphérique Gros jeux de données. - Traite les aberrants Complexité : O (n) Utiliser le résumé de données. - Trois versions pour données numériques, mélangées et flux de données. - Arbitraire Gros jeux de données. - Arbitraire Gros jeux de données de haute dimension. - Arbitraire Gros jeux de données de haute de dimension. - Petits jeux de données avec bruit. - Gros jeux de données avec bruit