Tài liệu Reduction de base de donnees par la classification automatique

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 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 Table de matières Résumé ..................................................................................................................... 4 Abstract..................................................................................................................... 4 Chapitre 1. Introduction............................................................................................. 5 Chapitre 2. Etat de l’art.............................................................................................. 7 1. Classification de données............................................................................... 7 2. 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 : ............................................. 8 3. Méthodes de classification ................................................................................11 1) Méthodes hiérarchiques (hierarchical clustering).......................................11 i. CURE ...................................................................................................13 2) Méthodes de partitionnement (partitional clustering):................................14 i. K-medoids ............................................................................................14 ii. K-means................................................................................................15 3) Méthodes basées sur la densité..................................................................18 i. DBSCAN..............................................................................................19 ii. DENCLUE............................................................................................20 4) Méthodes basées sur la grille.....................................................................21 i. STING ..................................................................................................21 ii. WaveCluster .........................................................................................22 iii. CLIQUE ...............................................................................................22 5) Algorithmes pour des données de haute dimension....................................23 i. Sélection d’attributs ..............................................................................23 ii. Réduction de dimensionnalité................................................................23 iii. Classification dans sous-espaces ...........................................................24 iv. Co-classification ...................................................................................25 6) Algorithmes pour les données qualitatives (catégorie) ...............................25 i. ROCK...................................................................................................26 ii. STIRR...................................................................................................26 iii. CACTUS ..............................................................................................27 Chapitre 4. Classification sur le flux de données.......................................................29 1. Classification sur le flux de données .............................................................29 i. STREAM-LOCALSEARCH.................................................................30 ii. GenIc ....................................................................................................31 2. Algorithmes BIRCH et CLUSTREAM .........................................................32 1) BIRCH......................................................................................................32 i. Arbre des CFs .......................................................................................32 ii. Algorithme............................................................................................33 iii. Cluster Feature et la distance dans BIRCH............................................38 2) CLUSTREAM ..........................................................................................42 i. Maintenance en ligne des micros classes ...............................................43 ii. Création des macros classes ..................................................................44 iii. Analyse d’évolution des classes ............................................................45 Chapitre 3. Implémentation et expérimentation.........................................................46 1. Implémentation du BIRCH ...........................................................................46 2. Expérimentation du BIRCH ..........................................................................51 Chapitre 4. Conclusion et perspectives .....................................................................52 Annexe 1. Sommaire des algorithmes de classification .............................................53 2 Annexe 2. Liste des figures.......................................................................................55 Références................................................................................................................56 3 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 Chapitre 1. 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.e. 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 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 Chapitre 2. 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 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.e. le nombre de valeurs distinctes de la variable. Un attribut est continu si son domaine n’est pas compté et infini, i.e. 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.e. un ensemble dont les éléments peuvent être mis dans une bijection avec un sous-ensemble fini des nombres entiers positifs. Un attribut est binaire s’il est un attribut dont le domaine contient exactement 2 valeurs. 2) Classification basée sur l’échelle de mesure : Cette classification distingue des attributs selon leur échelle de mesure. Supposons que x = ( x1 ,..., xk ) , y = ( y1 ,..., y k ) et z = ( z1 ,..., z k ) sont des objets dans un jeu de données D en k dimensions, xi, yi, zi sont des attributs, i = 1,…, k. Une échelle nominale distingue les catégories. Cela signifie que nous pouvons seulement dire si xi = yi ou xi ≠ yi . Les valeurs ne peuvent pas être totalement ordonnées. Elles sont simplement une généralisation des attributs binaires, avec un domaine à plus de deux valeurs discrètes. Une échelle ordinale implique des attributs d’échelle nominale utilisant un dispositif additionnel pour que leurs valeurs soient totalement mises en ordre, mais les différences entre les valeurs ne peuvent pas être quantifiées. Par conséquent, au lieu de dire xi = yi ou xi ≠ yi on peut dire xi < yi ou xi > yi . Une échelle d'intervalle mesure des valeurs dans l’échelle linéaire. Avec l’échelle d'intervalle nous pouvons dire non seulement si une valeur se trouve avant ou après une autre, mais aussi à quelle distance avant ou après. Puisque des valeurs sont mises sur une échelle linéaire, si xi > yi alors nous pouvons également indiquer que x est différent de xi − yi unités de y pour l’attribut i. Une échelle de rapport est une échelle d'intervalle avec un point nul significatif. 8 Des attributs d’échelle nominale et ordinale s’appellent des attributs qualitatifs (ou catégoriques), alors que l’échelle d'intervalle et de rapport s’appelle des attributs quantitatifs. Il est évident que des attributs quantitatifs sont mesurés en utilisant les unités spécifiques, telles que des kilogrammes et des centimètres. Les unités de mesure affectent les résultats d'analyse des classes, puisque, par exemple, les unités changeantes de mesure des kilogrammes à livres pour le poids, peuvent mener à un résultat différent. Le remède à ce problème s'appelle la standardisation. Etant donné un attribut i, 1 ≤ i ≤ k et n objets x1, x2, …, xn. Il s’agit de deux phases dans la standardisation : Trouver la déviation absolue moyenne si de i, pour tous les objets : 1 si = x1i − mi + x 2 i − mi + ... + x n i − mi , tels que xi1, xi2, …, xin sont n n valeurs de l’attribut i dans n objets, et mi est la moyenne de l’attribut i. x j i − mi j , 1≤ i ≤ n Déterminer la mesure standardisée : z i = si Une fois que les caractéristiques des données ont été déterminées, nous sommes confrontés au problème de trouver des moyens appropriés de décider à quelle distance un objet se trouve de l’autre. Les calculs de proximité sont des mesures de la ressemblance ou de l’association entre les paires d'objets de données. Un calcul de proximité peut mesurer la similarité ou la dissimilarité : plus deux objets se ressemblent, plus leur similarité est grande et plus leur dissimilarité est petite. La dissimilarité peut être mesurée de différentes manières, l’une est la distance. Quant à elle, la distance peut également être mesurée de plusieurs façons. Chaque mesure de distance est dépendante des caractéristiques des données qu’on traite. - ( ) Les métriques sont les mesures de distance les plus importantes. Une métrique doit satisfaire 4 conditions : non négative, définitive (la distance entre un objet et soimême doit être à zéro), symétrique et l’inéquation triangulaire. En conséquence, une métrique est toujours une mesure mais l’inverse n’est pas toujours vrai. Nous présentons une description brève de mesures pour chaque type d’attribut de données : Attributs d’échelle d’intervalle: Après la standardisation, la dissimilarité entre deux objets x et y peut être calculé par les métriques suivantes : 1 +  n q q Distance de Minkowski : d ( x, y ) =  ∑ xi − yi   i =1  +  n 2 Distance euclidienne : d ( x, y ) =  ∑ (xi − yi )  (Minkowski, q = 2).  i =1  + Distance de Manhattan : d ( x, y ) = ∑ xi − yi (Minkowski, q = 1). + Distance maximum: d ( x, y ) = max n i=1 xi − yi . (Minkowski, p → ∞ ). n i =1 9 En cas où les attributs sont assignés à des poids, il faut transformer les formules de distance en formules pondérées, e.g.: d ( x, y ) = k ∑ w (x i =1 i i − yi ) 2 , tel que wi est le poids pour l’attribut i, i=1,…, k. + −1 T Distance de Mahanalobis : d ( x, y ) = ( x − y )∑ ( x − y ) , tel que ∑ est une matrice de covariance d’échantillon ou une matrice de covariance connue du processus de génération d’individus. Attributs binaires : Supposons que les attributs de 2 objets x et y n’aient que les valeurs 1 et 0. α +δ + Simple Matching Coefficient : d ( x, y ) = (x et y sont symétriques) + Jaccard Coefficient : τ α (x et y sont asymétriques) d ( x, y ) = α + β +γ Tels que α est le nombre de valeurs d’attribut qui sont égales à 1 dans tous les deux objets, β est le nombre de valeurs d’attribut qui sont égales à 1 dans x mais 0 dans y, γ est le nombre de valeurs d’attribut qui sont égales à 0 dans x mais 1 dans y, δ est le nombre de valeurs d’attribut qui sont égales à 0 dans tous les deux objets, τ =α + β +γ +δ p−m Attributs d’échelle nominale : d ( x, y ) = , tels que m est le nombre p d’attributs dont la valeur est pareille dans tous les deux objets, p est le nombre total d’attributs. Attributs d’échelle ordinale : Ce type d’attributs peut être traité comme celui d’intervalle mais il a besoin d’être converti en une forme convenable. - Supposons que i est un attribut d’échelle ordinale dont le domaine contient Mi valeurs. Ces valeurs sont mises en ordre [1…Mi], donc on peut remplacer chaque valeur par son rang correspondant ri ∈ {1,..., M i } . Chaque attribut ordinal pourrait avoir une taille différente de domaine, donc il est souvent nécessaire de convertir chaque valeur en une valeur se trouvant dans l’intervalle [0.0, 1.1] en utilisant la formule j r −1 suivante : z j i = i M i −1 Après la transformation, on peut calculer la dissimilarité entre les objets par les mesures des attributs d’intervalle en appliquant ces mesures sur les zij. Attributs d’échelle de rapport : Il y a plusieurs méthodes pour calculer la dissimilarité entre ces attributs. Une solution est d’appliquer une formule logarithmique sur chaque attribut. Le résultat peut être traité comme un attribut d’intervalle. L’utilisation d’une transformation dépend de la définition des attributs et de l’application. - 10 k ∑δ Attributs mélangés : d ( x, y ) = - f =1 f xy d xy , tels que x et y sont des objets de k ∑δ f =1 f f xy k attributs mélangés, δ xy signifie le degré de dissimilarité entre x et y à l’attribut f et f f d xy est la contribution de l’attribut f à la dissimilarité entre x et y. 3. Méthodes de classification De nombreux algorithmes ont été inventés dans le domaine. Ils se diffèrent grâce aux facteurs : le type d’attributs de données qu’ils traitent (numériques, de catégorie, taxonomiques…) donc la structure de données utilisée est différente, la capacité de traiter un gros jeu de données, la capacité de traiter des données en haute dimension, la capacité de traiter des observations aberrantes, la complexité de l’algorithme (temps de calcul), la dépendance de l’ordre des données qui arrivent, la dépendance des paramètres prédéfinis par utilisateurs ou la connaissance a priori sur les données… Selon ces critères et leurs combinaisons, il y a plusieurs types d’algorithmes de classification. Traditionnellement et souvent, les méthodes de classification sont divisées en 2 catégories principales : Méthodes hiérarchiques et méthodes de partitionnement selon la manière dont on construit les classes. Tandis que les premières établissent graduellement les classes, les dernières apprennent directement les classes. C'est-à-dire qu’elles les découvrent en faisant bouger des points entre les classes. Ensuite, les algorithmes se diffèrent grâce aux autres critères comme le nombre de passes d’accès aux données, le nombre de dimensions, le type de données traitées, la forme des classes… Ces algorithmes sont soit hiérarchiques, soit de type partitionnement, soit une combinaison de ces deux types, et ils utilisent différents mécanismes d’organisation des données, de recherche, de construction des classes … Faire une classification pour tous les critères n’est pas facile, donc ici nous ne faisons qu’une distinction entre les 2 types fondamentaux et nous décrirons certaines familles d’algorithmes qui jouent un rôle important dans la communauté de classification. Ce sont [1] [2] [3] : Méthodes hiérarchiques, méthodes de partitionnement, méthodes basant sur la grille, méthodes basant sur la densité, algorithmes pour les données qualitatives (catégorie), algorithmes pour les données en haute dimension et algorithmes pour le flux de données. 1) Méthodes hiérarchiques (hierarchical clustering) Ces méthodes construisent les classes graduellement sous une forme hiérarchique, autrement dit, un arbre des classes qui est appelé un dendrogramme. Elles sont divisées en 2 sous-types : Agglomération (ascendant) et division (descendant). Agglomération : On commence en considérant chaque point comme une classe et on essaye de fusionner deux ou plusieurs classes appropriées (selon une 11 similarité) pour former une nouvelle classe. Le processus est itéré jusqu’à ce que tous les points se trouvent dans une même classe ou bien jusqu’à ce qu’on l’arrête. Division : En considérant tous les points comme une seule classe au début, on divise successivement les classes en classes plus raffinées. Le processus marche jusqu’à ce que chaque classe contienne un seul point ou bien si l’on atteint un nombre de classes désiré. Les méthodes hiérarchiques ont les avantages: La flexibilité pour le niveau de granularité (on peut atteindre une classe la plus fine ou la plus épaisse comme souhait), la capacité de traiter n’importe quelle mesure de similarité ou distance et l’application sur n’importe quel type d’attributs. A côté, elles ont les inconvénients : la critère de terminaison est souvent vague et le besoin de multi accès aux données. La plupart des méthodes hiérarchiques utilisent le lien simple (single-link), lien complet (complete-link) ou le lien moyen pour mesurer la similarité entre les classes [1] [3]: Dans le lien simple, la distance entre 2 classes est la valeur minimum des distances entre toutes les paires d’individus, l’un de la première classe, l’autre de la deuxième. Dans le lien complet, la distance entre 2 classes est la valeur maximum des distances entre toutes les paires d’individus Dans le lien moyen, la distance entre 2 classes est la valeur moyenne des distances entre toutes les paires d’individus, l’un de la première classe, l’autre de la deuxième. Figure 1: Classification de lien simple (gauche) et complet (droite) d’objets contenant 2 classes 1 et 2 avec le brut *. L'algorithme de lien complet produit des classes étroitement liées ou compactes. En revanche, l'algorithme de lien simple souffre d'un effet d'enchaînement. Il a une tendance de produire des classes qui sont prolongées (Voir la figure ci-dessus). Cependant l'algorithme de lien simple est plus souple que l'algorithme de lien complet. D’un point de vue pragmatique, on a observé que l'algorithme de lien complet produit des hiérarchies plus utiles dans beaucoup d'applications que l'algorithme de lien simple [3]. Il y a de nombreux algorithmes qui sont proposés. Les algorithmes hiérarchiques les plus connus sont CURE, COBWEB, CACTUS, BIRCH. Nous décrirons COBWEB et CACTUS dans la section algorithmes pour les données qualitatives, et BIRCH dans une section propre. 12 i. CURE CURE (Clustering Using REpresentatives) a été proposé par Guha, Rastagi et Sim [20]. Il est une approche hybride : utiliser tous les points de données et ainsi un un centroid pour former les classes) : Il représente une classe par un nombre constant de points de représentation appelés les représentants. Pour obtenir ces points, tout d’abord, on choisit les points qui s’éparpillent bien autour d’une classe. Ensuite on les fait rétrécir vers le centroid de la classe par une fraction quelconque. Ces points éparpillés après le rétrécissement seront utilisés comme les représentants de la classe. Les représentants visent à capturer la forme et l’ampleur de la classe. Le rétrécissement des points éparpillés vers le mean de la classe par un facteur a pour but de débarrasser les surfaces anormales et diminuer les effets des points aberrants. L’idée est basée sur le fait que les aberrants se trouvent normalement loin du centre de la classe. En conséquence, le rétrécissement pourrait fait déplacer les aberrants plus vers le centre tandis que les représentants sont moins déplacés. Le grand déplacement des aberrants peut réduire de mauvaises fusions des classes. La distance entre deux classes utilisée dans le processus d’agglomération n’est ni le lien simple ni lien moyen. Seuls les points de représentants sont utilisés pour la calculer. La distance est définie comme le minimum de distances entre deux représentants de deux classes. CURE est conçu pour traiter de gros jeux de données. Pour ce faire, on divise l’algorithme en 2 passes. 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. Après, ces partitions partielles sont classifiées pendant la deuxième passe pour former les classes désirées. Pour chaque classe, on stocke son mean, un ensemble de représentants pour le calcul de la distance entre elle et une autre classe et la classe la plus proche d’elle. L’algorithme commence en considérant chaque point d’entrée comme une classe et successivement fusionne chaque paire de classes les plus proches. Initialement, les représentants d’une classe sont les points dans la classe. Chaque classe est fusionnée avec sa classe la plus proche en faisant simplement une union des points de deux classes. Dans la nouvelle classe, les représentants sont calculés en tout d’abord choisissant par itérations les points bien éparpillés et après en les rétrécissant vers le centre de la classe. Dans la première itération, le point le plus loin du centre dans la classe est choisi comme le premier point éparpillé. Dans chaque itération suivante, le point le plus loin des points éparpillés précédents est choisi. Après avoir choisi les points bien éparpillés, les représentants sont obtenus par rétrécissement de ces points par une fraction vers le centre de la classe. L’algorithme utilise un arbre kd (kd-tree) où sont stockés les points représentants des classes qui sont pris pour calculer la classe la plus proche d’une classe. La complexité de temps du pire cas est O (n2log n). Si la dimension des données est petite, la complexité de temps peut être réduite à O (n2) [20]. La complexité d’espace est O (n). 13 2) Méthodes de partitionnement (partitional clustering): Ces méthodes produisent une seule partition des données au lieu d’une structure des classes. Elles créent les classes en optimisant une fonction objective qui est définie d’une façon locale (sur un sous-ensemble des données) ou globale (sur toutes les données) [3]. Le coût de construction des classes est cher, donc des heuristiques sont utilisées pour l’optimisation d’itérations sous la forme de mécanisme de réallocation qui réaffectent les points entre les classes. Ces méthodes raffinent graduellement les classes et donc peuvent donner les classes de meilleure qualité. En fait, les algorithmes ont besoin d’exécuter plusieurs fois avec différents états initiaux afin d’obtenir un meilleur résultat. Une approche est d’utiliser un point de vue conceptuel pour identifier les classes en supposant que les données viennent d’un mélange de certaines populations Une autre approche travaille avec une fonction objective définie sur chaque classe. Dépendant de la représentation d’une classe, on classifie ces types d’algorithmes en deux : k-medoids et k-means. i. K-medoids Dans ces algorithmes, une classe est représentée par un de ses points, qui s’appelle medoid. Une telle représentation nous donne deux avantages : elle s’adapte à n’importe quel type d’attributs, et le médoid est choisi comme une fraction des points prédominants dans une classe, donc il n’est pas sensible aux aberrants. Si les médoids sont choisis, les classes sont définies comme les sous-ensembles de points proches du médoid correspondant. Et la fonction objective sera définie comme la distance (ou d’autres mesures de dissimilarité) moyenne entre un point et le medoid. Les algorithmes les plus connus sont PAM, CLARA et CLARANS [1] [2] [10] [11] PAM (Partitioning around Medoids) a été développé par Kaufman and Rousseeuw [12]. PAM recherche les medoids des classes. Initialement, PAM choisit k points représentatifs à partir des données de N points (k est le nombre de classes, N est le nombre total de points). Ensuite, N-k points restants sont classifiés en se basant sur leur distance aux medoids : chaque point restant appartient à une classe si la distance entre ce point et le medoid de cette classe est la plus petite. Puis, PAM échange 2 points : l’un de l’ensemble de medoids, et l’autre de l’ensemble de nonmedoids. Le critère de la sélection est que la somme de distance de tous les points à leur medoid correspondant doit diminuer et avoir la décroissance la plus forte. PAM calcule le changement de la distance après un échange pour toutes les paires (medoid et non-medoid). Il choisira le pair dont la valeur de changement est la plus petite (cette valeur est toujours négative). S’il n’y a plus de paires dont le changement est négatif, cela signifie que la classe courante est bonne, donc que PAM s’arrête et renvoie k medoids. Les classes seront formées en calculant les distances entre les points et ces medoids. La complexité d’une seule itération (un échange) de PAM est O (k (N-k) 2). Donc le coût total de calcul est vraiment cher car il a de plus besoin de nombreuses itérations avant de terminer. 14 CLARA (Clustering LARge Applications) est aussi développé par Kaufman et Rousseeuw [12]. L’amélioration de CLARAN par rapport de PAM est qu’il ne se base pas sur l’ensemble entier de points, il travaille sur les échantillons des points. On prend une petite partie de données pour les représenter et k medoids sont déterminés en appliquant PAM sur cet échantillon. Si cet échantillon est choisi d’une manière aléatoire, alors il représente bien les données entières, donc les medoids sont similaires à ceux qui sont créés à partir des données tout entières. L’algorithme est exécuté sur plusieurs échantillons pour obtenir le meilleur résultat. En conséquence, CLARA peut traiter un plus gros jeu de données que PAM. La complexité d’une itération est O (kS2+k (n-k)) avec S est la taille d’un échantillon. Les auteurs ont indiqué, suite à leurs expérimentations, que la taille d’un échantillon de 40+2k donne un bon résultat. Un inconvénient de cet algorithme est qu’un point qui serait le meilleur medoid n’apparaît dans aucun échantillon, alors CLARA ne trouvera jamais le meilleur résultat. CLARANS (Clustering Large Applications based on RANdomized Search) est une combinaison de PAM et CLARA. Il a été développé par Raymon Ng et Jiawei Han [12]. Dans cet algorithme, les auteurs ont utilisé une abstraction de graphe pour représenter le problème de recherche des k meilleurs medoids. On construit un graphe dont chaque nœud est un ensemble de k points (intuitivement, ce sont k medoids). Deux nœuds sont dits voisinages s’ils ne diffèrent que par un seul point. En conséquence, le problème de déterminer un ensemble de k meilleurs medoids devient le problème de recherche dans ce graphe du meilleur nœud. Le critère pour estimer qu’un nœud est meilleur qu’un autre est comme dans le PAM : on minimise le changement dans la distance si un medoid est remplacé par un point non medoid en parcourant d’un nœud à un nœud voisin. Ce changement est appelé le coût différentiel de remplacement d’un medoid par un point non medoid. PAM le fait en parcourant tous les nœuds voisins d’un nœud donc c’est trop cher. CLARAN le fait en parcourant un sous graphe. En conséquence, cela ne donne pas toujours un bon résultat car il travaille sur une région localisée. CLARANS est une combinaison des deux algorithmes. C’est à dire à partir d’un nœud dans le graphe, il n’examine pas tous les voisinages. Il choisit un nombre (donné comme un paramètre de l’algorithme) de voisins aléatoires (ce n’est pas tous les voisins) pour rechercher un voisin dont le coût de remplacement de ce nœud par son voisin est minimisé. Si ce coût est négatif, i.e. le remplacement ne peut optimiser plus le résultat, le nœud trouvé est le meilleur résultat, et le processus peut s’arrêter. Théoriquement, la complexité de CLARA est O (k3+nk) pour chaque itération, tandis que celle de CLARANS est linéaire par rapport au nombre de points, donc le deuxième est théoriquement meilleur que le premier. L’expérimentation des auteurs prouve également que CLARANS est meilleur que CLARA dans tous les cas [12] ii. K-means Cet algorithme est le plus connu dans la communauté de classification des données. Dans cet algorithme, chaque classe est représentée par la moyenne (mean) ou la moyenne pondérée qui est nommée le centroid. K-means est un algorithme itératif. Il commence avec un ensemble de k points de référence (centroid) choisi par l’utilisateur. 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 15 de lui. La mise à jour des points de référence et l’affectation des points de données aux classes sont réalisées pendant les itérations successives. Il y a plusieurs versions de k-means. On peut les distinguer selon deux critères : la différence dans la mise à jour des classes et le critère pour faire cette mise à jour. Pour le premier critère, les algorithmes de ce type diffèrent dans le détail de la génération et de l’ajustement des classes. Il y a 3 algorithmes de base de ce type : Standard K-means, l’algorithme de Lloyd, et continuous K-means qui a été proposé par McQueen en 1967 [15]. L’algorithme de Lloyd : L’initialisation de l’algorithme est similaire à la description ci-dessus. Les ajustements sont réalisés en calculant le centroid pour chaque classe et en utilisant ces centroids comme les points de référence dans l’itération suivante pour tous les points de données. La mise à jour des centroids n’est faite qu’après une itération. Standard k-means: Cet algorithme est meilleur que celui de Lloyd en terme de l’utilisation plus efficace de l’information à chaque pas d’itération. C’est à dire la mise à jour des centroids est faite pendant et après une itération. Si un point appartient à une classe et que pour lui, le centroid de cette classe est le point de référence le plus proche, alors il n’y aura aucun ajustement. Mais si après avoir affecté un point x à une classe A, on trouve qu’il y a une autre classe B dont le centroid est le point de référence plus proche de x que celui de A, alors il faut réaffecter x à la classe B et recalculer les centroids de toutes les deux classes, et les points de référence de ces deux classes se déplacent aux nouveaux centroids. Continuous k-means: Cet algorithme diffère au standard k-means par le choix des points de référence initiaux et la sélection des points pour la mise à jour des classes. Dans la première différence, pas comme dans Lloyd ou standard k-means où les points de référence initiaux sont arbitrairement choisis, dans cet algorithme, ces points sont choisis comme un échantillon aléatoire de la population entière des points. Si l’échantillon est assez gros, alors la distribution des points de référence initiaux pourrait refléter celle des points de la population. La deuxième différence, contrairement au standard k-means où tous les points sont séquentiellement examinés, cet algorithme n’examine qu’un échantillon aléatoire des points. 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. Pour le deuxième, il y a deux versions de l’optimisation itérative de kmeans [1]: L’algorithme de Forgy, est similaire à l’algorithme EM et ses itérations disposent de deux pas : réaffecter tous les points à leur centroid le plus proche et recalculer les centroids des nouveaux groupes créés. Les itérations continuent jusqu’à ce qu’on atteigne un critère de terminaison (par exemple, il n’y a plus de réaffection). Les avantages sont la capacité de travailler sur toutes les normes Lp, la facilité de paralléliser, l’insensibilité à l’ordre des données. 16 L’algorithme d’optimisation itérative réaffecte les points en se basant sur une analyse plus détaillée des effets sur la fonction objective quand un point est déplacé de sa classe à une classe potentielle. Si l’effet est positif, ce point sera réaffecté et deux centroids seront recalculés. L’expérimentation prouve que la version classique est souvent meilleure que celle de Forgy [4]. K-means est populaire et beaucoup utilisé grâce à sa simplicité. En fait, il a pas mal des inconvénients : Le résultat est vraiment dépendant des centroids initiaux, l’optimum local calculé est trop différent de la valeur globale, il n’est pas facile de déterminer un bon nombre de classes utilisé pour l’algorithme, le processus est sensible aux aberrants, l’algorithme n’est pas extensible et l’algorithme ne travaille que sur les données numériques. Pour remédier à ces inconvénients, certaines améliorations et extensions sont proposées comme ISODATA qui permet de déterminer automatiquement un bon nombre de classes utilisé pour donner un bon résultat, k-modes, k-prototypes pour manipuler sur les données catégorie [5] ou l’accélération de k-means par l’inéquation triangulaire, single pass k-means pour travailler sur un gros jeu de données [6]… ISODATA : Comme on a vu, le nombre de classes K est toujours déterminé à priori pour k-means. ISODATA a été proposé pour remédier à cet inconvénient. Il intercale des phases de fusion et d’éclatement de groupes dans k-means [14] : fusionner 2 classes si la distance entre elles est faible (inférieure à un seuil) et éclater une classe en 2 classes si son inertie est trop grande (supérieure à un seuil). Initialement, on donne un nombre k assez grand comme l’entrée du nombre de classes de k-means. Après avoir appliqué k-means sur ces données, on fait la fusion et l’éclatement pour trouver un bon nombre de classes. La difficulté est que l’on a besoin déterminer deux seuils pour la phase supplémentaire. K-modes, k-prototypes sont développés par Z. Huang [5]. On sait que Kmeans ne travaille que sur les données numériques sur lesquelles on utilise la distance euclidienne pour calculer la dissimilarité entre les points ou les classes. Pour que cet algorithme puisse marcher avec les données catégoriques, Z. Huang a proposé deux extensions de k-means en définissant une mesure de dissimilarité pour comparer les objets de données. En conséquence, on utilise les modes au lieu des means et une méthode basée sur la fréquence pour mettre à jour les modes. Etant donnés 2 objets de type catégorie, la dissimilarité entre eux est définie comme le nombre d’attributs différents correspondants entre ces deux objets. n si xi = y i 0 d ( x, y ) = ∑ δ ( xi , y i ) Tel que δ ( xi , y i ) =  xi ≠ y i i =1 1 si Le mode d’une classe est l’objet qui apparaît le plus dans la classe. L’algorithme k-modes a pour but de traiter seulement les données catégorie, kprototypes vise à manipuler les données mélangées (numérique et catégorie) en additionnant la distance euclidienne pour les attributs numériques avec la distance décrite ci-dessus pour les attributs catégoriques avec un poids (la somme pondérée) : 17 d = d n + λ.d c , tels que dn est la distance numérique et dc est la distance catégorique, λ est un poids qui équilibre la domination des attributs catégorie sur les attributs numériques. Cette distance est utilisée dans l’algorithme k-means. Single pass k-means (Scalable k-means): Cet algorithme a été développé par Bradley, Fayyad et Reina [6]. Il vise à augmenter l’extensibilité de k-means pour de gros jeux de données. L’idée de cet algorithme est basée sur la notion que les solutions effectives de classification peuvent être obtenues en sélectionnant et stockant des parties importantes de données et résumant les autres. Il est capable d’identifier les régions de données qui sont compressibles, les régions qui doivent être gardées dans la mémoire et les régions qui peuvent être supprimées. Pour représenter un groupe de données (une sous-classe) sous une forme compressée, l’algorithme utilise un triplet de statistique (SUM, SQUAREDSUM, N) tels que SUM est la somme linéaire de tous les points dans le groupe, SQUAREDSUM est la somme des écarts carrés des points au centroid, et N est le nombre de points dans ce groupe. Il a besoin de 3 types de jeu de données stockés dans la mémoire : DS- jeu de données supprimées, CS- jeu de données compressées et RS- jeu de données gardées. Notons que DS et CS stocke les statistiques de données. L’algorithme comprend 2 étapes de compression : la compression primaire a pour but de déterminer les données qui sont supprimées (donc stockées dans DS). La compression secondaire vise à compresser les données qui ne sont pas supprimées dans la première phase (le résultat est stocké dans CS). Les données qui ne sont pas traitées dans ces 2 étapes de compression sont stockées dans RS. Les points qui sont supprimés dans la première étape sont ceux qui ne se déplacent quasiment jamais à une autre classe. Cette tâche est effectuée en utilisant le seuillage d’un rayon de Mahalanobis autour du centre d’une classe. Les points se trouvent dans ce rayon sont compressés. Chaque classe a un jeu de données supprimées représenté par le triplet cidessus pour représenter tous les points appartenant à cette classe. La première étape trouve les régions denses (les sous-classes) qui ne sont pas compressées par la première étape en appliquant l’algorithme k-means avec un nombre de classes k’ > k. Après avoir trouvé k’ sous-classes, on applique un critère de compacité (dense) sur ces k’ classes comme un filtre: une sous-classe dont la covariance est inférieure à un seuil est passée ce filtre. Les sous-classes filtrées sont fusionnées avec celles stockées dans CS et les autres points par une classification hiérarchique d’agglomération. Accélération de k-means : En utilisant l’inégalité triangulaire, Elkan a proposé une amélioration qui permet de diminuer le coût de calcul des distances dans k-means [13]. L’idée est basée sur le fait que la plupart des calculs de distance sont redondants. Si un point se trouve très loin d’un centre, alors ce n’est pas nécessaire de calculer la distance exacte entre lui et ce centre afin de savoir si ce point peut être affecté à ce centre. En plus, si un point est vraiment plus proche d’un centre que tous les autres centres, on n’a pas besoin de calculer les distances exactes pour décider si le point appartient à ce centre. 3) Méthodes basées sur la densité C’est des méthodes hiérarchiques dans lesquelles les classes sont considérées comme des régions en haute densité qui sont séparées par des régions en faible 18 densité. La densité est représentée par le nombre d’objets de données dans le voisinage. C’est pourquoi ces méthodes sont capables de chercher des classes de forme arbitraire. Elles ne travaillent que dans un espace métrique, donc elles sont utilisées dans la classification de données spatiales. Pour réduire le coût de calcul lors de la classification, les données sont indexées, par exemple R*-tree (cf. section Méthodes de recherche de voisinage), donc elles ne sont efficaces qu’avec les données en basse dimension. Il y a deux approches dans ce type de classification, l’une est basée sur la connectivité de densité, l’autre est basée sur la fonction de densité. Les algorithmes les plus connus de ce type sont DBSCAN (connectivité de densité) et DENCLUE (fonction de densité). i. DBSCAN DBSCAN (Density Based Spatial Clustering of Applications with Noise) est un algorithme très populaire dans ce type d’algorithme de classification [2] [18]. Pour chaque objet, il cherche le voisinage qui contient un nombre minimum d’objets. Une classe est formée par tous les objets qui sont transitivement connectés par leurs voisinages. Un voisinage de rayon Eps contenant au moins MinPts objets d’un objet est appelé le voisinage Eps-MinPts de cet objet. On utilise la notion connecté-densité pour former des classes : Un objet est dit directement accessible-densité Eps-MinPts d’un autre objet s’il se trouve dans le voisinage Eps-MinPts de cet objet. Un objet est dit accessible-densité Eps-MinPts d’un autre objet s’il y a une chaîne d’objets entre eux dont tous les 2 objets successifs sont directement accessible densité Eps-MinPts. Un objet est dit connecté-densité Eps-MinPts d’un autre objet s’il y a un objet duquel tous les deux objets sont accessibles-densité. Une classe avec Eps et MinPts prédéfinis est définie comme un ensemble non vide d’objets qui satisfait 2 conditions, l’une est la condition de connectivité, i.e. tous les objets de la classe doivent être connectés-densité, l’autre est la condition de maximum, i.e. tous les objets qui se trouvent dans le voisinage Eps-MinPts d’un objet de la classe doivent appartenir à cette classe. Le bruit est défini comme un ensemble d’objets qui n’appartiennent à aucune classe. Il y a deux objets différents qui sont pris en compte dans la classification : l’objet de noyau et non noyau. Un objet de noyau est celui qui a un voisinage EpsMinPts. Un objet non noyau est celui qui n’a pas un tel voisinage. Un objet non noyau peut être un objet de frontière ou un bruit. L’algorithme commence en prenant en compte d’un objet arbitraire et cherche tous les objets accessibles densité. S’il est objet de noyau, alors cette phase forme une classe. S’il est un objet de frontière et qu’il n’y a aucun objet qui est accessible densité depuis lui, alors c’est un bruit, l’algorithme passe à un autre objet. 19