cours-classif-4

Description

Introduction Mesures d’´eloignement La CAH Introduction Mesures d’´eloignement La CAHCadre du probl`emeLes donn´ees:G´en´eralit´es:◮ tableau X de n individus avec p variables (quantitatives, qualitatives, ou◮ Impossibilit´e d’une recherche exhaustive;mixte ;◮ Proc´edure it´erative tendant vers un optimum local d’un crit`ere fix´e;◮ un tableau de distances D entre les n individus.Objectif d’une classification: Choix laiss´es `a l’utilisateur:◮ d´efinition d’une mesure d’´eloignement (entre des classes);◮ partition des individus en des classes homog`enes et bien diff´erenci´ees entre◮elles; crit`ere d’homog´en´e¨ıt´e des classes ;◮ cr´eation d’une typologie, d’une segmentation des individus ◮ m´ethode: CAH ou r´eallocation dynamique ;◮ nombre de classes (question difficile) ;Difficult´es: ◮ outils d’interpr´etation des classes obtenues.◮ Le nombre de classes `a construire est g´en´eralement inconnu a priori ;◮ Apprentissage non-supervis´e - clustering ;◮ Diff´erent d’un probl`eme de discrimination - classification (faux ami!): :Introduction Mesures d’´eloignement La CAH Introduction Mesures d’´eloignement La CAHM´ethode de classification 1 M´ethode de classification 2R´eallocation dynamique :Synonymes: nu´ee, centres-mobiles◮CAH - classification ascendante hi´erarchique Nombre de classes K fix´e a priori;◮ Tirage des K centres de classes au hasard parmi les n individus;◮ Construction d’un dendogramme (arbre) par regroupement successifs des`◮ A chaque ´etape, on ...

Informations

• Publié par: Nusur
• Nombre de lectures: 36
• Langue: Français

Extrait

Cadreduprobl`eme

:

:

Onit`erecesdeux´etapesjusqu’a`laconvergencedel’algorithme. ◮

La CAH

Me´thodedeclassification2

Choixlaisse´sa`l’utilisateur: de´finitiond’unemesured’´eloignement(entredesclasses); ◮ crit`ered’homog´en´e¨ıt´edesclasses; ◮ ◮ me´thode:CAHour´eallocationdynamique; nombre de classes (question difficile) ; ◮ outilsd’interpr´etationdesclassesobtenues. ◮

G´en´eralite´s: ◮ Impossibilit´ed’unerechercheexhaustive; ◮ Proc´edureit´erativetendantversunoptimumlocald’uncrite`refix´e;

CAHclassificationascendantehi´erarchique ◮ Construction d’undendogramme(arbre) par regroupement successifs des individus, des groupes d’individus; ◮ ` Ad´efinir,distanceentre2groupesd’individusa`partirdutableaude distanceDentre les individus; ◮ Dendogrammecoup´eselonleshauteurs de sautsselr,¸condefateni`aob classes finales.

Re´allocationdynamique: Synonymes:euqimanydee´un,centresmobiles Nombre de classesK´xfirpaeiroi; ◮ ◮ Tirage desKcentres de classes au hasard parmi lesnindividus; ◮ ` Achaquee´tape,ondisposedeKcentresc 1 , . . . ,c K . Onles actualise en deux´etapes: 1.Regroupement des individusndeiquha:c`e´tceffatseudiviequiauncentr est le plus proche (souvent la distance euclidienne); On obtient ainsiKclasses. 2.Actualisation des centres mobiles: c j =barycentre de la classej.

partition des individus en des classeseseng`mohoeterteffn´bdiiener´ecienes ◮ elles; cre´ationd’unetypologie, d’unesegmentation des individus ◮

: Introduction

Mesuresd’e´loignement

La CAH

Introduction

Difficulte´s: ◮ Lenombredeclasses`aconstruireestge´ne´ralementinconnua priori ; ◮ Apprentissagenonsupervis´eclustering; ◮ Diffe´rentd’unproble`medediscriminationclassification(faux ami!)

: Introduction

Mesuresd’´eloignement

Mesuresd’e´loignement

Lesdonne´es: tableauXdenindividus avecpvariables (quantitatives, qualitatives, ou ◮ mixte ; ◮ untableau de distancesDentre lesnindividus.

La CAH

Mesuresd’´eloignement

Introduction

La CAH

Objectif d’une classification:

Me´thodedeclassification1

M´ethodedeclassification3

Mesuresd’e´loignement

Introduction

:

Mesuresd’´eloignement

Variables continues pvariables quantitatives; ◮ 1 p ◮ un individuirulrveceeterp´pa´erem i = (X, . . . ,X). i i 2 2 ◮ Soit les variances des variables:D=diag(σ 1 , . . . , σ p ) Distanceeuclidienner´eduite: T−1 d(i,k) =km i −m k k D −1 = (m i −m k )D(m i −m k )

◮ Distance de Mahalanobis: Danslaformulepr´ec´edente,onremplaceDpar 1p Σ =Cov(X, . . . ,X). Remarque:Deladu´ednaleiagoseedtstictnoΣ.

Mesuresd’´eloignement

: Introduction

: Introduction

Mesuresd’´eloignement

:

Variables binaires,ilaresimit´eecdsnIidusuels 1 1.Concordance :(a ik +b ik ) 2 a ik 2.Jaccard : a ik +b ik +c ik 2a ik 3.Dice : 2a ik +b ik +c ik =⇒sdceisedmisier.itl´aidni

Dissimilarit´eentrelesindividus2

La CAH

Dissimilarite´entrelesindividus2 Variables binaires caspvariables binaires ; ◮ Comparaison entre deux individusi,k ◮ m i = (1,0,1,0,0,1, . . . ,0,1,0,1), m k = (1,1,0,0,0,1, . . . ,0,0,1,1). Soit  „ «„ «ff „ «„ «ff j j X1X1 i i a ik =cardj: j =,b ik =cardj: j =, X 1 X 0 k k  „ «„ «ff „ «„ «ff j j X0X0 i i c ik =cardj: j =,d ik =cardj: j =. X 1 X 0 k k on a a ik +b ik +c ik +d ik =p.

La CAH

Dissimilarite´entrelesindividus1

La CAH

La CAH

Introduction

Classification mixte: CAH: ◮ 1.ourafficiedpnelpttera`emicelngrand (temps de calcul trop long); 2.avantage: pas deKe´pairroi.xfi Unestrat´egiemixtepossible: ◮ ′ 1.CAH sur un tableau partiel avecn≪nnerermiinasudividte´dednfiK, le nombre de classes a priori ; 2.Une RD ensuite avec ceK.

CAH 1. Actualisationdu tableauDir´timalsiisddees ◮ ` Achaquefoisqu’uneagre´gationestproduite(individus,groupes d’individus),unnouveaugroupeestcr´ee´; Letableaudesdissimilarit´esesta`actualiserpourcenouveaugroupe. ◮

Dissimilarit´eentredeuxgroupesd’individus: ◮ groupesA,Bde poids respectifsw A ,w B (ex. leurtaille); soitd(i,k)isduursenldaimve;itsipee´hlciiroausesimxiueoddird ◮ ◮ diff´erentschoixcasd’unedissimilarite´ d(A,B) = min{d(i,k);i∈A,k∈B}saut minimumsingle linkage d(A,B) = max{d(i,k);i∈A,k∈B}saut maximumcomplete linkage X 1 d(A,B) =d(i,k),saut moyengroup average linkage |A||B| i∈A,k∈B

Dissimilarit´eentredeuxgroupesd’individus: ◮ Casdesvariablescontinuesm´etriqueeuclidienne d(A,B) =kg A −g B kdistance centroides w a w B d(A,B) =kg A −g B ksaut de Wardrd´eurpavale;edaftuSAS w A +w B

:

Dissimilarite´entrelesindividus4

La CAH

: Introduction

Donne´esmixtes:m´elangedevariablescontinuesetcat´egorielles: Deux alternatives: ◮ Discr´etiserlesvariablescontinuesetutilisercequipr´ece`de; ◮ ` A l’inverse,rendre toutes les variables continues !!

Mesuresd’´eloignement

Mesuresd’e´loignement

Mesuresd’e´loignement

Transformationdesvariablescate´gorielles¿continues: 1p1p1p 1 2 ◮ SupposonsX, . . . ,X=Y, . . . ,Y,Z, . . . ,Z | {z }| {z } continues cate´gorielles 1p 2 ◮ AFCMsurlapartiecate´gorielle(Z, . . . ,Z); ensuite choisirkirotcafsdnetesleirel´eduxeaeskcomposantes 1k canoniques:C, . . . ,C 1p1k 1 ◮ Classificationsurlesdonn´eestransforme´es:Y, . . . ,Y,C, . . . ,C avecp 1 +k“variables” continues. j ◮ Important:comme les composantes canoniquesCormaontnees,lis´lis j convient dereuide´rles variablesYalableaupr´e

La CAH

La CAH

Introduction

Mesuresd’e´loignement

: Introduction

Dissimilarit´eentrelesindividus3 Variablescat´egoriellesg´en´erales: j ◮ cas depscle´eatrigoleelsavirbaX`ac j smladoe´ti{a j1 , . . . ,a jc j }, respectivement ; Tableau disjonctif complet: ◮ 1p X= [X∙ ∙ ∙X]

La CAH

Comparaison entre deux individusi,k: ◮ 2 distancedeHamingpond´er´ee(χentre les profils lignes): c p j X X 2 n jℓ 1 χ(i,k) =δ ik j p n j=1 ℓ=1 ℓ o`u j ◮ n=effectif dea jℓ ce´’tnahollindslan ℓ jℓ j ◮ δ= 1siietkneettnnudesiocdrpr´ese´rlsuceanitalodama jℓ deX ik

CAH

Introduction

: