La classificationBENAMEUR Sabrinabenameur_s@yahoo.fr Dpartement dinformatique Universit Mohamed Khider Biskra

Plan du CoursClassificationClassification/ SegmentationLalgorithme des k-moyennesExemples (rsultats de classification par K-means)

*

ClassificationLes techniques de classification sont anciennes. C'est une tape d'abstraction et de synthse ncessaire dans toute les sciences. Avec l'avnement de l'informatique dans les annes 1960, ces mthodes ont connu de nouveaux dveloppements mthodologiques qui ont donn lieu des algorithmes de classification automatique.*

ClassificationIl s'agit d'organiser les lments analyss en classes telles que les lments d'une mme classe se ressemblent, et se ressemblent plus que 2 lments de 2 classes diffrentes. Les mthodes de classifications sont une composante des mthodes d'analyse des donnes. Elles sont aussi une premire tape de certaines mthodes de reconnaissance de formes.*

Classification/segmentation

Dans le cadre de la segmentation : attribuer une tiquette (classe) aux pixels sur la base de leur similarit.Cette tiquetage se fait en utilisant des attributs dont le premier est lintensit.Mthode utilisant seulement lintensit sera qualifie de mthode monodimensionnelle, les mthodes utilisant plusieurs attributs sont multidimensionnelles.*

Classification/segmentationNotez que les problmes de segmentation et classification sont trs lies et peuvent tre utiliser pour signifier la mme chose :Un classifieur implicitement segmente une image : l'ensemble des pixels ayant la mme classe forme une rgion de l'imageune segmentation implique une classification (les rgions sont tiquetes selon leurs appartenances)

*

Lalgorithme des k-moyennes k-means Algorithme des centres mobiles : mthode de classification automatique qui a pour objectif de partitionner lespace des attributs en k classes (k-connus)A partir dune partition initiale on amliore itrativement la partition de lespace en minimisant la variance intraclasse et en maximisant lcartement entre les classes*

Algorithme des k-moyennesDans un premier temps les objets sont regroupes autour de K centres arbitraire c1, , cK de la manire suivante : la classe Ci associe au centre ci est constitue de lensemble des points les plus proches de ci que tout autre centre. Les centres de gravit g1,, gK sont ensuite calculs partir des classes dtre formes.On recommence lopration en prenant comme centre de classe les centres de gravit trouvs et ainsi de suite jusqu' ce que les objets ne change plus de classe.*

Algorithme des k-moyennesRemarques :Le nombre de classes K fix au dbut peut diminuer au cours des itrations : en effet ; si une classe nattire aucun objet, elle sera vide et donc limine.Le principal inconvnient des centres mobiles est que la partition finale dpend du choix de la partition initiale. *

Algorithme des k-moyennesUne solution : utiliser lalgorithmes plusieurs fois avec des initialisations diffrentes et choisir la partition qui revient le plus souvent*

Algorithme des k-moyennesDe nombreuses variantes peuvent tre rencontres, par exemple au lieu de calculer le centre des classes aprs avoir affect tous les objets, le centre peut tre recalcul aprs chaque affectation ;La mthode de centres mobiles a t gnralise sous lappellation de la mthode des nues dynamiques. Au lieu de dfinir une classe par un seul point, son centre de gravit, on la dfinit par un groupe dobjets formant un noyau *

Algorithme des k-moyennesExemple:Appliquer la mthode K-means au cas o on recherche deux classes dans l'ensemble de points dfinis dans R2 par (2,1) (-1,2) (0,-2) (0,-1) (0,1) (0,2) (0,3) (1,-1), avec les centres de dpart (-2,-1) et (2,3).*

Algorithme des k-moyennes*

Algorithme des k-moyennes*

Algorithme des k-moyennescas de la segmentation dimageChoix de K centres Pour chaque pixel de limage :Calculer la distance entre ce pixel et tous les centresAffecter le pixel courant la classe du centre ci dont la distance est minimaleCalculer les nouveaux centres, et revenir (2) jusqu que les classes deviennent presque stable.

*

Algorithme des k-moyennesAvantages:Trs facile comprendre et mettre en uvreNe ncessite aucune information sur les donnes. Simple du point de vu conceptuelle.Rapide et nest pas couteux en taille mmoire.La mthode est applicable tout type de donnes *

Algorithme des k-moyennesInconvnientsLa partition finale dpend de la partition initialeLe nombre de classes est un paramtre de lalgorithme.Un mauvais choix du nombre de classes k produit de mauvais rsultats.Sensible au bruit.

*

Exemples (Rsultats de K-means) Test 1: image (270x270), k= 25, Taux=0.1

Nombres des rgions finales : 22 / 24 / 22*

Exemples (Rsultats de K-means)Test 2: image (270x270) , K=8 , Taux=0.1

Nombres des rgions finales : 8/ 8 / 8*

Exemples (Rsultats de K-means)Test 2: image (270x270) , K=2 , Taux=0.1

Nombres des rgions finales : 2/ 2/ 2*

*