Click here to load reader

RECONNAISSANCE DE FORMES IAR-6002. Techniques daggrégation (clustering) u Introduction u Aggrégation hiérarchique –Méthode UPGMA –Méthode de Ward u Algorithme

  • View
    109

  • Download
    3

Embed Size (px)

Text of RECONNAISSANCE DE FORMES IAR-6002. Techniques daggrégation (clustering) u Introduction u...

  • Page 1
  • RECONNAISSANCE DE FORMES IAR-6002
  • Page 2
  • Techniques daggrgation (clustering) u Introduction u Aggrgation hirarchique Mthode UPGMA Mthode de Ward u Algorithme de Forgy u Algorithme k-means u Algorithme Isodata
  • Page 3
  • Introduction u Lorsque nous ne pouvons dfinir priori le nombre de classes u Nous devons avant le design du classificateur, extraire un ensemble dobservations tires dune population quelconque pour ainsi dduire les sous- ensembles distincts u Laggrgation (clustering) consiste regrouper des observations de telle faon que les observations sont semblables dans chaque groupe (agrgats)
  • Page 4
  • Introduction u Le but des techniques daggrgation est de crer un ensemble daggrgats (cluster) regroupant des obser- vations de mmes caractristiques u Ces techniques cherchent alors regrouper les ob- servations semblables u Le regroupement dobservations est base entre autre sur la notion de distance par rapport des centrodes (centre de masse de chaque classe) u Ces techniques sont non supervises
  • Page 5
  • Aggrgation hirarchique u Laggrgation hirarchique consiste regrouper des observations dans de gros regroupements contenant de plus petits groupements hirarchiquement ratta- ch au groupement plus gros u Cette technique daggrgation peut tre reprsent par un arbre. Le plus petit regroupement se trouve au bas de larbre, chaque observation est en elle- mme un aggrgat
  • Page 6
  • Aggrgation hirarchique u Si un niveau L de larbre donn, un aggrgat contient un ensemble dobservations donn, cet ensemble se retrouveras dans les niveaux suprieurs de larbre u Ces techniques daggrgations sont soient agglom- rante si larbre est construit du bas vers le haut et divisible si construit du haut vers le bas
  • Page 7
  • Aggrgation hirarchique (Techniques agglomrantes) u Algorithmes dagglomration 1- Commencer avec n (observations) aggrgats 2- Rpter ltape 3, n-1 fois (n: nombre daggrgats du niveau L courant) 3- Trouver la paire daggrgats la plus semblable C i et C j et regrouper C i et C j dans le mme aggrgat. Si il y a galit, regrouper la premire paire trouve
  • Page 8
  • Aggrgation hirarchique (Mthode UPGMA) u La technique de liaison-moyenne (UPGMA) est base sur lutilisation dune distance entre deux aggrgats dcoulant de la distance moyenne entre un point dans un aggrgat et un point dans lautre aggrgat. Si C i est un aggrgat avec n i lments et C j un aggrgat avec n j lments, la distance entre C i et C j est donne par
  • Page 9
  • Aggrgation hirarchique (Mthode UPGMA, Exemple)
  • Page 10
  • Aggrgation hirarchique (Mthode de Ward) u La mthode de Ward consiste regrouper la paire daggrgats produisant la plus petite erreur quadratique de lensemble des aggrgats rsultants u Si un aggrgat contient m observations x 1, x 2,...., x m ou x i est le vecteur de caractristiques (x i1,...,x id ), lerreur quadratique de lobservation x i (distance Euclidienne par rapport la moyenne) est
  • Page 11
  • Aggrgation hirarchique (Mthode de Ward) u Lerreur quadratique pour tout un aggrgat est = ( 1,...., d ) 2 =( 2 1,....., 2 d ) Centrodes
  • Page 12
  • Aggrgation hirarchique (Mthode de Ward, Exemple)
  • Page 13
  • Algorithme de Forgy u Cet algorithme daggrgation prend en entre: Les observations Le nombre de classes k Les valeurs initiales des k centrodes u Les valeurs initiales des centrodes peuvent tre choisies de faon alatoire mais la connaissance priori de la structure des classes peut guider leur choix
  • Page 14
  • Algorithme de Forgy Initialisation des centrodes avec les valeurs initiales FIN = FAUX TANT QUE NON FIN FAIRE POUR chaque observation FAIRE Trouver le centrode le plus proche Placer lobservation dans laggrgat le plus proche FIN POUR SI aucun changement dagggat FAIRE FIN = VRAI SINON Calculer les nouveaux centrodes FIN SI FIN TANT QUE
  • Page 15
  • Algorithme de Forgy u Trouver le centro de le plus proche
  • Page 16
  • Algorithme de Forgy u Calculer les nouveaux centro des
  • Page 17
  • Algorithme de Forgy u Lalgorithme de Forgy converge trs lentement puisque le critre de stabilit des aggrgats est trs contraignant u Plus le nombre dobservations est grand plus le temps de convergence est grand u Certaine versions de cet algorithme permettent de restreindre le nombre ditrations
  • Page 18
  • Algorithme k-means u Lalgorithme k-means est semblable lalgorithme de Forgy u Cependant, le critre darrt de lalgorihme k- mean est bas sur la stabilit des moyennes u Son taux de convergence est plus rapide
  • Page 19
  • Algorithme k-means Initialisation des centrodes avec les valeurs initiales FIN = FAUX TANT QUE NON FIN FAIRE POUR chaque observation FAIRE Trouver le centrode le plus proche Placer lobservation dans laggrgat le plus proche FIN POUR SI aucun changement des valeurs des centrodes FAIRE FIN = VRAI SINON Calculer les nouveaux centrodes FIN SI FIN TANT QUE
  • Page 20
  • Algorithme k-means (illustration de la convergence)
  • Page 21
  • Page 22
  • Algorithme Isodata u Comme les 2 autres algorithmes, Isodata permet de mini- miser lerreur quadratique en associant chaque observa- tion au centro de le plus proche u Isodata permet de traiter un nombre daggrgats variables pouvant aller au del du nombre introduit par lusager u Isodata limine les aggrgats avec trop peu dlments u Isodata peut regrouper des aggrgats si le nombre daggr- gats est trop grand ou certains aggrgats sont trop proches u Un aggrgat peut tre divis si le nombre daggrgats est trop petit ou si laggrgat contient des lments dissem- blables
  • Page 23
  • Algorithme Isodata u Paramtres dentres Nombre daggrgats Nombre minimum dlments par aggrgat Distance minimale entre chaque aggrgat Paramtre de contrle des subdivisions daggrgat Nombre ditrations dans la premire phase de lalgorithme Nombre maximum de regroupements par itration Nombre ditrations maximun dans le corps de lalgorith- me
  • Page 24
  • Algorithme Isodata Initialisation des centrodes finISO = FAUX nbiterISO = 0 TANT QUE NON finISO ET nbiterISO < iter_body FAIRE finF = FAUX nbiterF = 0 TANT QUE NON finF ET nbiterF < iter_start FAIRE POUR chaque observation FAIRE Trouver le plus proche aggrgat Insrer lobservation dans laggrgat le plus proche FIN POUR Calculer les nouveaux centrodes SI aucune observation change daggrgat ALORS finF = VRAI FINSI nbiterF = nbiterF + 1 FIN TANT QUE
  • Page 25
  • Algorithme Isodata liminer les aggrgats avec pas assez dlments et aussi les lments eux-mmes SI nb aggrgat >= 2 * no_cluster OU nbiterISO est paire ALORS nbmerge = 0 TANT QUE nbmerge < max_merge FAIRE SI la distance entre 2 centrodes < min_dist ALORS /* AGGRGATION */ Regrouper ces 2 aggrgats Mise jour des centrodes FIN SI nbmerge = nbmerge + 1 FIN TANT QUE SINON SI nb aggrgat split_size * x ALORS /* SUBDIVISION */ Calculer la moyenne de x de laggrgat Subdiviser laggrgat en 2 par rapport la moyenne de x Calculer les 2 centrodes
  • Page 26
  • Algorithme Isodata SINON SI nb aggrgat split_size * x ALORS /* SUBDIVISION */ Calculer la moyenne de x de laggrgat Subdiviser laggrgat en 2 par rapport la moyenne de x Calculer les 2 centrodes SI distance entre les 2 centrodes >= 1.1 * min_dist ALORS Remplacer laggrgat par 2 aggrgats SINON Garder laggrgat inchang FIN SI SINON SI aucun changement daggrgatdans la dernire itration globale ALORS finISO = VRAI FIN SI nbiterISO = nbiterISO + 1 FIN SI FIN TANT QUE
  • Page 27
  • Algorithme Isodata (exemple) u Image digitalise dun X avec comme vecteur de caract- ristiques (4, 10, 10, 4, 10, 9, 11, 9)
  • Page 28
  • Algorithme Isodata (exemple) u Lalgorithme Isodata est appliqu 45 images (15 par lettres) avec comme paramtres: no_clusters = 4 min_elements = 8 min_dist = 2.5 split_size = 0.5 iter_start = 5 max_merge = 1 iter_body = 3
  • Page 29
  • Algorithme Isodata (exemple) u A la fin, lalgorithme Isodata donne comme rsultat de classification Classe # dans aggrgat 1 # dans aggrgat 2 # dans aggrgat 3 # dans aggrgat 4 8OX8OX 0 11 0 000000 13 2 0 14
  • Page 30
  • Algorithme Isodata (exemple) u Diagrammes de dispersion