INSTITUT DE LA FRANCOPHONIE POUR L’INFORMATIQUE RAPPORT DU STAGE REDUCTION DE BASE DE DONNEES PAR LA CLASSIFICATION AUTOMATIQUE Sous la direction de Pr. Georges HEBRAIL, ENST Paris Réalisé par LE Anh Tuan, IFI Hanoi Décembre 2004 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Remerciements Je tiens à remercier mon encadrant du stage, Monsieur Georges Hébrail, le professeur du département Informatique et Réseaux (INFRES), ENST Paris, pour sa disponibilité, son soutient et son aide précieuse pendant toute la durée du stage. Je voudrais également remercier chaleureusement Madame Sophie Bizart, le secrétaire du département INFRES de m’avoir accueilli et son aide pendant le stage. Un grand merci à l’IFI d’avoir bien préparé mon stage.
J’ai le plaisir de remercier tous les stagiaires au département INFRES, ENST qui m’ont porté leur amitié. J’exprime mon entière reconnaissance à ma famille et mes amis pour leurs soutiens, leurs aides et leurs encouragements. 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Table de matières Résumé. Etat de l’art.
Classification de données. Types de données et les mesures. 8 1) Classification basée sur la taille de domaine :. 8 2) Classification basée sur l’échelle de mesure :.
Méthodes de classification .13 2) Méthodes de partitionnement (partitional clustering):.15 3) Méthodes basées sur la densité.20 4) Méthodes basées sur la grille.22 5) Algorithmes pour des données de haute dimension. Réduction de dimensionnalité. Classification dans sous-espaces .25 6) Algorithmes pour les données qualitatives (catégorie). Classification sur le flux de données.
Classification sur le flux de données. Algorithmes BIRCH et CLUSTREAM. Arbre des CFs. Cluster Feature et la distance dans BIRCH.
Maintenance en ligne des micros classes. Création des macros classes. Analyse d’évolution des classes. Implémentation et expérimentation.
Implémentation du BIRCH. Expérimentation du BIRCH. Conclusion et perspectives. Sommaire des algorithmes de classification .53 2 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Liste des figures.56 3 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Résumé Aujourd’hui, il y a plus en plus des applications dont la base de données est très grosse et les données apparaissent sous la forme d’un flux de données infini comme des enregistrements de coup de téléphone, la surveillance de réseaux. Pour ce type de données, les systèmes de gestion de base de données (SGBDs) traditionnels semblent ne pas convenables parce que ils ne traitent que des données à taille limitée. Pour exploiter efficacement des données massives en utilisant un espace de stockage limité, il faut trouver un traitement spécial qui réduit les données afin d’obtenir des informations nécessaires appelées des résumés à partir de ces données. Il y a certaines méthodes pour ce fait : échantillonnage, compression et classification.
Parmi eux, la classification est la solution la plus convenable. 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. Après avoir découvert plusieurs algorithmes de classification, nous avons trouvé que l’algorithme BIRCH est une solution de réduction de données très bonnes et le modèle CLUSTREAM permet de traiter efficacement les données sur un flux de données. Nous avons également implémenté l’algorithme BIRCH pour tester sa performance.
Abstract Today, there is more and more applications whose database is very large and the data appear in the form of an infinite data stream like records of telephone call, the monitoring of networks. For this type of data, the traditional database management systems (DBMS) seem not suitable because they treat only data with limited size. To exploit effectively massive data by using a space of limited storage, it is necessary to find a special processing which reduces the data in order to obtain necessary information called the summaries from these data. There are certain methods for this: sampling, compression and clustering.
Among them, clustering is the most suitable solution. In this report, we talk about the general clustering algorithms and particularly about those which are for the data flow. After having studied several clustering algorithms, we found that BIRCH algorithm is a very good data reduction solution and the CLUSTREAM is a model which allows to effectively treating the data stream. We also implemented algorithm BIRCH to test its performance.
4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Introduction Aujourd’hui, il y a plusieurs applications qui ont besoin d’un autre modèle de stockage des données que le modèle des SGBD (Système de Gestion de Base de Données) traditionnel. Un modèle de SGBD traditionnel stocke des jeux de données finis et persistants, donc il n’est approprié qu’aux applications dont le volume de données n’est pas gigantesque, dont des parties significatives de données sont souvent requises et dont les mises à jour sont relativement peu fréquentes. On peut trouver de telles nouvelles applications dans les télécommunications, la surveillance des réseaux, les affaires, les marchés financiers, les flux de clics sur les pages web…Dans ces applications, les données arrivent sous la forme d’un flux de données, i.
un gros volume de données qui arrive continuellement. Les données ne sont accessibles que par ordre d’arrivée, les accès aléatoires ne sont pas permis. La mémoire réservée aux données est relativement plus petite que le volume total du flux de données, donc il n’y a qu’une petite quantité de données qui peut être gardée. Dans les télécommunications, par exemple, les enregistrements d’appel sont continuellement générés.
Typiquement, la plupart de traitements sont faits en examinant un enregistrement une seule fois. Après, il ne sera plus examiné. Il existe des méthodes pour réaliser un compromis entre un gros volume de données qui arrivent et un espace de stockage et petit. On peut échantillonner les données qui arrivent et utiliser les échantillons obtenus dans les opérations de l’application.
Cette méthode perd beaucoup d’informations concernant le jeu entier de données. Une autre méthode est de compresser les données et d’utiliser les données compressées au lieu des données originales. Dans ce cas, les données compressées ne peuvent pas être efficacement interprétées et directement utilisées sans être décompressées. La classification automatique est aussi une technique de compression (réduction) de données mais les données sont bien compressées en sens que le jeu de données peut être bien interprété en n’utilisant que les données compressées.
La classification automatique des données consiste à diviser un jeu de données en sous-ensembles de données appelés classes pour que tous les individus dans même une classe soient similaires et les individus de classes distinctes soient dissimilaires. Typiquement, chaque classe est représentée par un individu qui s’appelle le centre de la classe ou par certaines informations dérivées de tous les individus de la classe qui sont suffisantes de décrire la classe. Il y a plusieurs algorithmes de classification des données. Ils diffèrent par la nature de données qu’ils traitent (données numériques ou données de catégorie, petit jeu de données ou gros jeu de données, données de dimension élevée ou moins élevée, sur un flux de données ou pas…), par les méthodes de distribution des données en classes, par la représentation des classes… Ce stage de fin d’étude a eu lieu à l’Ecole Nationale Supérieure des Télécommunications de Paris, France.
J’ai travaillé sous la direction du professeur Georges HEBRAIL. Mon travail dans ce stage est de découvrir tout d’abord le domaine de classification de données en général. Ce travail consiste à faire 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com connaissance le concept de classification des données, les problèmes concernant du domaine, une classification des algorithmes de classification différents afin de trouver que l’algorithme BIRCH et le modèle CLUSTREAM est une bonne solution pour le problème de classification sur le flux de données. Nous avons également implémenté l’algorithme BIRCH et fait des expérimentations pour évaluer sa performance.
Une simulation simple de classification sur un flux de données est également réalisée en se basant sur cet algorithme. Ce rapport est organisé comme suivant : Le chapitre 2 décrit le problème de classification de données en général et de différents algorithmes de classification. Le chapitre 3 parle de l’algorithme BIRCH et CLUSTREAM. Le chapitre 4 décrit notre implémentation et expérimentation de l’algorithme BIRCH.
Le chapitre 5 est une conclusion avec quelques perspectives. 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Etat de l’art 1. Classification de données La classification est une méthode qui a pour but de grouper les individus d’une population en des classes disjointes telles que dans une même classe, les membres sont similaires et dans les classes différentes, les individus sont dissimilaires.
Il faut distinguer la classification (la classification non supervisée) avec le classement (la classification supervisée) [1][3] : - Classification supervisée: Etant donné un ensemble des classes déjà identifiées et un individu, il s’agit de trouver la meilleure classe à laquelle cet individu appartient. - Classification non supervisée : Etant donné un ensemble des individus, il s’agit de structurer des classes pas encore identifiées qui groupent ces individus. Nous nous intéressons à la classification non supervisée dans la fouille de données dans laquelle les exigences principales sont la capacité de traitement d’un gros jeu de données et la capacité de traitement des différents types de données. Le processus de classification comprend les étapes suivantes [2] [3] : (1) représentation des individus, (2) définition d’une mesure de similarité appropriée aux données, (3) classification, (4) abstraction des données, (5) validation du résultat.
La représentation des individus (patterns) a pour but de déterminer les informations concernant les données : le nombre de classes désiré, le nombre d’individus disponibles, le nombre, le type et l’échelle des attributs de données. Ces informations sont utilisées dans l’algorithme de classification. La proximité des individus est souvent mesurée par une fonction de distance entre chaque pair d’individus. De nombreuses mesures de proximité sont proposées, se basant sur la nature de données.
La classification est une phase de groupement des individus dans les classes. Plusieurs algorithmes de classification sont proposés. La différence entre eux est la manière dont ils groupent les individus telles que la méthode hiérarchique, la méthode de partition…, le type de données qu’ils traitent comme des données numériques, de catégorie, le flux de données…, la mesure de proximité des individus et des classes qu’ils utilisent, telles que la distance euclidienne, la distance de Minkowski, le lien simple ou le lien complet…ou le critère selon lequel on construit des classes. L’abstraction des données est un processus d’extraction d’une représentation simple et compacte pour un jeu de données.
Typiquement, une abstraction des données est une description compacte de chaque classe, souvent en terme de prototypes des classes ou d’individus représentatifs des classes comme le centre des classes. La validation du résultat vise à déterminer si les classes fournies sont significatives en utilisant un critère spécifique d’optimalité. Cependant, un tel critère est souvent subjectif, donc il y a peu de manières standard pour valider la classification sauf dans certains domaines bien décrits à priori. 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com La classification est utile dans une variété de domaines comme : reconnaissance des formes, apprentissage, fouille de données, recherche de documents, segmentation d’images… 2.
Types de données et les mesures Dans la classification, le type d’objets traités est divers (des personnes, des avis, des entités…). Ces objets doivent être soigneusement présentés en termes de leurs caractéristiques. Ces caractéristiques sont les variables principales du problème et leur choix influence considérablement sur les résultats d'un algorithme de classification. Nous présentons une classification basée sur deux caractéristiques : la taille de domaine et l’échelle de mesure [1][24].
1) Classification basée sur la taille de domaine : Cette classification distingue des objets sur une variable en se basant sur la taille de leur domaine, i. le nombre de valeurs distinctes de la variable. - Un attribut est continu si son domaine n’est pas compté et infini, i. ses éléments ne peuvent pas être mis dans une bijection avec l'ensemble de nombres entiers positifs.
Cela signifie qu’entre deux valeurs quelconques de l'attribut, il existe un nombre infini de valeurs. - Un attribut est discret si son domaine est un ensemble fini, i.