ALGORITHMES DE CLASSIFICATION
Contents
1. NETHER NGLAN El Figure 1 Donn es PSYSOC hi rarchie du Moment d ordre deux calcul e d apr s les coordonn es factorielles 3 facteurs A F C Certains pays par exemple AUSTRI et WGERMA semblent ne pas tre connect s l arbre ceci est du au fait que les niveaux de la hi rarchie sont tr s proches les uns des autres dans les faibles valeurs et il n est pas possible de les repr senter sans distordre l chelle globale de l arbre Il faut remarquer que dans l affichage des r sultats les niveaux d agr gation des n uds ne vont pas toujours en croissant Cela r sulte du principe m me de l algorithme dans lequel ceux ci sont form s d s que l on d couvre des voisins r ciproques sans tenir compte de leur distance mutuelle Les niveaux les plus hauts pr sentent entre eux de grands carts par rapport aux niveaux inf rieurs ce qui semble indiquer que les groupes sont bien individualis s et homog nes Cet aspect tr s tranch de l arbre hi rarchique est trompeur En effet les niveaux ici ne s interpr tent pas comme des distances mais comme des dispersions ou plus exactement des accroissements de dispersion voir ci dessus paragraphe 1 L exp rience montre aussi et pour la m me raison que cette m thode tend cr er des groupes d effectifs quilibr s 4 Proc dure de calcul Le classeur AnaDon xls comporte la proc dure CAHmom2 qui r alise la construction hi rarchique2. ICELAN SWEDEN 4 BELGIU 4 H NORWAY 4 SCOTLA 4 ENGLAN NETHER Fig 2 Donn es PSYSOC H rarchie obtenue par l algorithme CDH LM de construction descendante selon le lien moyen Les donn es de base sont les distances entre les pays calcul es d apr s les coordonn es factorielles issues de l A F C 3 premiers facteurs 5 2 Exemple PHYTOS L algorithme CDH LM a t appliqu aux donn es phytosociologiques en partant de la distance de Jaccard entre relev s Les r sultats voir figure 2 ne concordent pas avec ceux que fournissent les algorithmes l mentaires de construction ascendante voir chapitre 4 paragraphe 2 2 Seul le groupement 3 4 14 16 Pacnl Festucetum halleri subass nardetosum faci s normal apparait clairement Les autres relev s sont m lang s et l on n y reconnait aucun des groupements identifi s R38 R31 R30 R27 R10 R24 R23 R54 R15 R13 R55 R36 R4 R3 R16 R14 Fig 3 Donn es PHYTOS Hi rarchie obtenue par l algorithme CDH LM de construction descendante partir de la matrice des distances de Jaccard 6 Conclusion Les constructions hi rarchiques par divisions successives ont un aspect s duis
3. N Auteur Formule Etendue Moyenne Note 1 Russel amp Rao 1940 c n 0 1 pg n 1 2 Jaccard 1908 EME 8 6 0 1 pq n p q pa 3 3 Dice 1945 2c p q 0 1 2pq n p q 2 3 4 Sokal amp Sneath 2 1963 c 2 p q 3c 0 1 pq 2n p q 3pq 3 5 Kulczinski 1 1927 c p q 2c 0 Infini pq n p q 2pq 3 6 Kulczinski 2 1927 c p c q 2 0 1 p q 2n 2 7 Ochiai 1957 c Rac p q 0 1 Rac pq n 2 8 Simpson 1960 c Min p q 0 1 Max p q n 4 9 Kochen amp Wong 1962 nc pq 0 n T 5 Tableau 1 Indices o la pr sence des attributs joue un r le pr pond rant p nombre d attributs du l er objet q nombre d attributs du 2 eme objet c nombre d attributs communs aux 2 objets n nombre total d attributs possibles Rac racine carr e Min minimum Max maximum Note 1 Dans l indice de Russel et Rao num ro 1 si p q alors s i i p n s 1 1 q n et i ne ressemble pas lui m me avec la m me intensit que ne le fait i envers lui m me Note 2 Les indices de Dice num ro 3 Kulczinski 2 num ro 6 et Ochiai num ro 7 ne sont autres que c divis par la moyenne arithm tique de p et q leur moyenne harmonique et leur moyenne g om trique respectivement On peut donc s attendre ce que les valeurs de ces indices soient voisines s cartant le plus les unes des autres lorsque p et q sont les plus diff rents Cf Roux G et Roux M 1967 Note 3 Les i
4. R14 R16 Figure 5 Donn es PHYTOS Hi rarchie du lien moyen bas e sur la distance de Jaccard R36 R27 R38 R31 R30 R23 R13 R15 R24 R10 R55 R54 R4 R3 R14 R16 Figure 6 Donn es PHYTOS Hi rarchie du diam tre bas e sur la distance de Jaccard 3 Les proc dures de construction ascendantes de hi rarchies Les proc dures Excel suivantes sont disponibles dans le classeur AnaDon xls CAHLM calcule la CAH du lien moyen CAHdiam calcule la CAH du diam tre ou lien complet CAHsmin calcule la CAH du saut minimum ou lien simple DessArb dessine l arbre hi rarchique obtenu par les m thodes pr c dentes Chapitre 5 Agr gation autour de centres mobiles 1 Principes et probl mes 1 1 L algorithme des centres mobiles L algorithme que nous allons d crire a pour but de construire une seule partition de l ensemble tudi Il en existe de nombreuses variantes mais nous ne parlerons que de la plus simple d entre elles Au d but de l algorithme il faut se fixer un nombre k de classes et choisir une partition initiale Cette partition peut tre inspir e par une connaissance a priori des objets classer ou bien elle peut tre obtenue par r partition au hasard des objets en k cat gories On ex cute alors les op ra
5. ex e 1 m 8 4 o m est l effectif total des objets On appelle e l effectif de la modalit k tandis que ei est l effectif de la classe I 2 1 Interpr tation d une partition Dans le cas d une partition on demande l ordinateur de dresser un tableau variables classes partition o l on trouve l intersection de la ligne j et de la colonne k la valeur CTR j k de la contribution de la variable j la classe k de la partition Pour cela il suffit d effectuer dans la double somme ci dessus 8 4 la partie relative aux classes de la variable consid r e CTR j k Bierg ek ek e1 m ex ea m o l indice parcourt l ensemble L J des modalit s de la variable j Il est clair que la somme de ces nombres obtenue en faisant varier k sur l ensemble des classes de la partition est gale au Khi 2 Pour plus de commodit ces nombres sont divis s par leur somme et sont exprim s en milli mes de facon d terminer facilement les classes les mieux caract ris es par la variable j tudi e Il faut noter que dans le cas d une variable j deux modalit s comme la pr sence ou l absence d une esp ce une classe peut tre caract ris e aussi bien par la pr sence que par l absence de l esp ce en question Le tableau est compl t par la valeur du Khi deux et par le nombre de degr s de libert prendre en compte dans une ventuelle proc dure de test statistique 2 2 Interpr tation d un
6. SPAIN 680 NORWAY 152 762 STRELA 280 761 327 NETHER 2 45 702 3153 392 ENGLAN 198 717 224 344 128 USA 687 800 791 809 694 656 Tableau 1 Donn es PSYSOC distances du Khi 2 sur donn es brutes multipli es par 1000 AUST FRAN PORT WGER BELG FINL SWED SWIT ITAL NIRE DENM ICEL SCOT SPAI FRANCE 218 PORTUG 339 303 WGERMA 54 263 370 BELGIU 277 237 506 312 FINLAN 557 614 855 564 384 SWEDEN 355 381 645 369 164 244 SWITZE 317 433 649 308 274 282 167 ITALY 433 395 121 455 614 966 750 748 NIRELA 1170 1173 1184 1207 1079 1077 1128 1180 1283 DENMAR 422 564 761 398 419 321 296 146 852 1265 ICELAN 712 623 900 743 435 425 412 572 1004 1091 674 SCOTLA 546 449 703 586 277 416 324 484 811 982 613 211 SPAIN 379 263 144 413 494 869 641 670 171 1253 789 857 672 NORWAY 594 516 796 625 319 355 298 462 901 1085 572 119 145 759 SIRELA 680 536 775 724 423 583 490 653 873 1021 784 244 179 720 NETHER 422 375 642 454 151 304 166 323 752 1030 455 296 161 626 ENGLAN 478 437 695 509 214 281 205 357 807 991 480 260 142 683 USA 652 710 700 682 644 717 703 711 805 553 797 853 684 794 NORW SIRE NETH ENGL SIRELA 253 NETHER 183 332 ENGLAN 159 320 67 USA 789 793 656 644 Tableau 2 Distances euclidiennes usuelles sur les 3 premiers facteurs de l Analyse factorielle des correspondances multipli es par 10
7. galement r solu c est la distance euclidienne usuelle qui s impose En effet si l on a opt pour l ACP elle redonne approximativement la distance euclidienne usuelle que l on aurait pu calculer sur les donn es brutes si l on a opt pour l AFC la distance euclidienne usuelle sur les facteurs est peu pr s gale la m trique du Khi deux sur les donn es brutes Dans les deux cas le degr d approximation est d autant meilleur qu on travaille sur un plus grand nombre de facteurs Bien entendu il ne s agit pas d une m thode miracle Le choix de la distance se trouve remplac par le choix du codage pr alable des donn es en vue de l analyse factorielle Mais les diff rents codages possibles sont maintenant bien connus et prouv s Cf Benz cri 1980 Roux et Guittonneau 1977 3 L Analyse factorielle des correspondances surmonte l gamment le probl me de l effet de taille et permet de traiter des donn es tr s h t rog nes par d coupages en classes de valeurs des variables quantitatives et mise sous forme disjonctive compl te de l ensemble des variables 4 On y gagne galement sur le plan informatique Comme on ne conserve rarement plus de cinq dix facteurs le tableau des donn es est d une taille raisonnable et peut en g n ral tenir dans la m moire centrale de l ordinateur D ou un gain de temps et une plus grande facilit de programmation Mais surtout on n a qu un seul programme de distance programmer
8. 1 entre les objets est gale la hauteur du n ud le plus bas qui assure la liaison entre ces deux objets On v rifie facilement que les valeurs ainsi tablies satisfont aux axiomes math matiques des distances voir annexe 1 et en particulier l in galit du triangle Elles satisfont en outre l in galit ultram trique qui est plus contraignante que celle du triangle d r Ar S Max d r rf d x r C est pourquoi on appelle distance ultram trique ou en abr g ultram trique une distance satisfaisant cette in galit On montre Cf annexe 2 qu toute hi rarchie indic e correspond une distance ultram trique et une seule Supposons maintenant que l on ait deux distances d et d sur le m me ensemble I d objets On dit que d est inf rieure d si et seulement si pour tout couple d objets i et 1 on a d i i lt d i i Il est clair que par construction l ultram trique d associ e la hi rarchie du saut minimum est inf rieure la distance d donn e Mais elle poss de en outre l importante propri t suivante parmi toutes les ultram triques inf rieures la distance d d est sup rieure toutes les autres Autrement dit d s approche de d par le bas le mieux possible cf annexe 2 1 3 Comparaison des agr gations par le saut minimum et par le diam tre Examinons la figure 2 form e de quatre points x y z t align s et s par s par des distances voisi
9. 4 PORTUG 4 ITALY 4 FINLAN BELGIU 4 H SWEDEN 4 SWITZE 4 DENMAR 4 SIRELA ICELAN 4 NORWAY SCOTLA 4 H NETHER ENGLAN Figure 4 Donn es PSYSOC Hi rarchie du lien moyen construite partir de la distance euclidienne usuelle calcul e sur les coordonn es factorielles A F C 3 facteurs 2 2 Phytosociologie PHYTOS La comparaison des deux arbres hi rarchiques obtenus l un en agr geant par la distance moyenne l autre par le diam tre lien maximum fait apparaitre les m mes groupes principaux au nombre de quatre qui coincident assez bien avec les groupes tablis lors de l tude ant rieure Voir Chapitre 2 paragraphe 1 2 Sur les deux figures 5 et 6 apparaissent les rassemblements suivants 3 4 14 16 PAcnl 10 54 55 PAcn2 13 15 23 PAn 27 30 31 36 38 PAc Le relev num ro 24 est isol l extr mit d une longue branche dont le rattachement change selon le mode d agr gation employ Il s agit clairement d un relev interm diaire d affectation d licate R36 R27 R38 R31 R30 R23 R13 R15 R10 R55 R54 R24 R4 R3
10. celui de la distance euclidienne 5 Les facteurs de l analyse factorielle sont tr s stables c est dire que de petites erreurs de mesures ou bien la suppression d observations douteuses ne modifient quasiment pas les coordonn es sur les axes ni par cons quent les classifications calcul es d apr s ces coordonn es Or c est pr cis ment un d faut fr quent de ces m thodes que d tre sensibles de petites fluctuations des donn es Dans l analyse factorielle celles ci modifient surtout les derniers facteurs c est dire ceux que l on ne prend pas en compte dans notre strat gie 6 L analyse factorielle permet une autre approche des donn es et facilite l interpr tation des classifications obtenues La seule difficult de cette m thode r side dans le choix du nombre d axes factoriels prendre en consid ration Toutefois l utilisateur sera guid dans ce choix par l examen des d croissances successives des pourcentages d inertie des axes factoriels Il faut arr ter lorsque celles ci deviennent n gligeables D autre part un autre crit re important est de ne conserver que les facteurs que l on arrive interpr ter 1 3 Variables qualitatives et mixtes Lorsque les variables sont qualitatives la strat gie ci dessus s applique encore avec cette restriction que seule l analyse des correspondances est justifi e sur le plan math matique Il convient pour cela de mettre les donn es sous forme disjonctive compl te C
11. entre deux r gions denses 2 Application l exemple PSYSOC Dans cette application plut t que le moment intraclasse nous utilisons comme crit re de qualit de la partition obtenue le rapport R du moment interclasse au moment total Ce rapport que nous appellerons rapport d inerties de la partition est toujours compris entre z ro et 1 puisque le moment total s crit comme la somme des moments interclasse et intraclasse Une bonne partition sera donc caract ris e par une valeur de R proche de 1 Le premier choix d licat de l algorithme des centres mobiles est celui du nombre de classes de la partition La construction ascendante hi rarchique nous a permis de d celer chapitre 4 paragraphe 2 l existence de trois groupes que l on a d nomm s M diterran e Europe Nord et Atlantique par commodit Nous avons donc fait une premi re s rie de calculs en fixant le nombre de classes trois puis une autre s rie avec quatre classes pour examiner le comportement du programme dans une situation embarrassante Dans tous les cas les donn es sont constitu es des trois premiers facteurs de l Analyse des correspondances 2 1 Partition en trois classes En introduisant comme partition initiale les trois groupes d termin s par la construction hi rarchique le programme ne fait qu une seule tape qui montre que cette partition initiale ne peut pas tre am lior e Nous avons alors tir au hasard quatre partitions initiales
12. quantitatives ou mixtes Dans le cas purement qualitatif ou purement quantitatif diverses formules sont disponibles voir chapitre 3 et annexe 1 On veillera viter les redondances introduire deux variables mesurant le m me ph nom ne ou une variable dont la valeur s obtient partir des valeurs de deux autres variables Mais le m lange de variables qualitatives et quantitatives pose quelques difficult s On est dans ce cas oblig de cr er de nouvelles variables qualitatives correspondant aux classes de valeurs que l on aura eu soin de faire pour chacune des variables quantitatives Dans tous les cas une analyse factorielle pr alable fournit g n ralement une base de d part solide pour la classification 1 2 Traitement Les nombreuses variantes de la construction ascendante hi rarchique ne doivent pas impressionner l utilisateur Dans la plupart des cas l agr gation par la distance moyenne ou bien celle du moment d ordre deux lui fourniront de bons r sultats chapitres 4 et 6 1 3 Interpr tation des r sultats Toutes les variables jouent un r le quivalent dans la d termination des groupes d objets et il est rare qu un groupe puisse tre caract ris par une plage de variation d termin e d une seule variable Cependant les aides l interpr tation chapitre 8 peuvent mettre en avant quelques unes des variables avec des valeurs typiques pour certains groupes On se souviendra aussi que l ordre horizontal
13. s en commun par i et i ce qui peut s crire Go 24 xx k TL 2 e n On remarque que ces quantit s suffisent exprimer le nombre d de caract res absents simultan ment d ntc p q E 1 xx 1 x amp k 1 2 n En r sum on a la table suivante i i 1 0 1 el p 0 q c d n c p aq o chaque case d signe le nombre d attributs qui sont dans l tat indiqu en t te de la ligne et de la colonne correspondantes Nous allons maintenant num rer ci dessous les diff rentes formules connues comme indices de ressemblance en appelant chacune d elles du nom du premier auteur l ayant employ e notre connaissance Elles seront expos es suivant un ordre analogue celui qui est adopt par Sokal et Sneath 1963 c est dire en pr sentant d abord les formules o la ressemblance n est prise en compte que par les pr sences communes d attributs puis celles o la ressemblance est compt e la fois par les pr sences communes et les absences communes Faire un choix entre ces formules en vue d une application pr cise est une t che assez d licate c est pourquoi nous compl terons cet expos de divers renseignements intervalle de variation absolu v a c est dire en supposant que tous les caract res puissent prendre chacune des deux valeurs 0 ou 1 puis variation relative v r en supposant que les nombres d attributs p et q sont fix s Enfin nous nous int ressero
14. s est encore accentu e par le fait que les niveaux de liaison ne sont pas des distances mais plut t des carr s des distances 4 Un programme suppl mentaires utile troncature d une partition La strat gie d crite ci dessus au paragraphe 2 1 n cessite la troncature d une hi rarchie pour obtenir une partition de d part introduire dans la proc dure CenMob d agr gations autour de centres mobiles D s qu on d passe quelques dizaines d objets effectuer cela la main est fastidieux et source d erreurs C est pourquoi nous avons mis au point la proc dure Troncat pour faire cette op ration Elle cr e une partition de n objets en k classes k tant fix par l utilisateur partir d une hi rarchie d crite par ain s et benjamins voir chapitre 4 paragraphe 3 1 La partition obtenue est constitu e par une suite de n valeurs comprises entre 1 et k La i me valeur donne le num ro de la classe de l individu 1 Chapitre 10 Conclusion Etant donn es la faiblesse des connaissances math matiques en mati re de classification et l impossibilit o l on se trouve d examiner toutes les solutions possibles les conseils que l on peut donner en conclusion ne sont bas s que sur des appr ciations exp rimentales Rappelons que comme tout processus d Analyse des donn es l obtention d une classification se fait en trois phases principales au cours desquelles l utilisateur est amen faire des choix cruciaux pr p
15. sociale c est dire le nombre de d c s pour 100 000 habitants dus des causes sociales La somme des termes d une colonne est proportionnelle la moyenne des taux de mortalit pour une cause fix e sur l ensemble des pays consid r s Dans ces conditions la distance du Khi deux utilis e par l analyse factorielle des correspondances est tout fait adapt e pour tudier les ressemblances entre les r partitions des d c s d un pays l autre Nous avons donc deux solutions pour le calcul des distances La premi re consiste calculer la distance du Khi deux directement sur le tableau des donn es brutes Cf tableau 1 la seconde est de calculer la distance euclidienne usuelle sur les premiers axes issus de l analyse des correspondances tableau 2 Dans cette derni re strat gie se pose le probl me du nombre d axes retenir Si l on conserve tous les facteurs possibles nombre de variables moins un alors les r sultats sont rigoureusement identiques ceux de la premi re m thode Pour appr cier l effet de filtrage de l analyse factorielle nous pr f rons ne retenir que trois axes qui repr sentent 93 7 de l inertie totale le quatri me axe tombant 4 4 de l inertie totale Les r sultats de ces deux s ries de calculs figurent dans les tableaux 1 et 2 Etant donn e l approximation adopt e dans la deuxi me m thode ces deux tableaux ne sont pas facilement comparables si ce n est en observant l ordre dans lequel s
16. 1 0000000000 601011 1 qo T9 611010 0 ds Or l D ld 62 1 T L 1 0 0 0 L0 T I 630101000100000 64 1000111000001 65 1 10101000101 67 1 1 000 111 681000011010000 69 1 0 01000001 700000000 0000 710000000001001 2 Spe pop 111000 75001000000 0 0 770000000 L 100 d 190 T 101 110000 82 0001011100000 84 0000000000110 86 1100000000000 87 0000000110000 900000000000000 95000101010 000 98000000000 0 0 LOO 1 0 01 050000000 0000 09 0 000100 0 12 000000 00000 131 1 01 0 0 14 1 0 1 1 16 0000000000 17 1 0000 120 00000 0 0 qo sed sr Sed 1 ICT eL 126 0 0 0 1000000 1290001010100000 130 1 0 0000000000 13100100000000 00 14400001000011 1 450000100010110 156000000000100 1570000000000010 580101010100000 1591001010100000 160 0101000000001 63 I Tod 0 IL O ds OF 1 1 0 1 1 1660000101010010 1680000000000110 Tableau 2 Donn es PHYTOS OOOOH o000000o0rProo0oroooootr w DECO ODO OOD ARA O R OH O O H CO QOOOorLnoococcoomrmrococococoocococco t O H o O H Hs Y Ooo0ooort Oot COO OoOOOoornooocdoccot oo o OoOorooooor OOH OOOH Ooo0roo0oo0oo0ooootr Antennaria dioica L Cerastium arvense var 1 Plantago alpina L Poa alpina L L Polygonum viviparum L Achillea millefolium Agrostis alpina Scop Alchemilla glaberrima Schm Alchemilla hybrida L Androsace carnea L Gaertn Anthoxanthum odoratum L Aster alpinus L Astragalus campestris L Ten A
17. Figure 1 Ph nom ne d inversion La distance entre l l ment c et le groupe a b est plus faible que la distance entre a et b Quelle que soit la formule adopt e il faut donc s assurer que les distances recalcul es soient sup rieures au niveau du n ud que l on vient de former d iUi k IV diy 44 Cela est vident pour les formules 1 et 2 puisqu au moment de la fusion d i 1 est la plus petite de toutes les distances On v rifie ais ment que c est encore vrai de la formule 3 pour la m me raison Lorsqu on utilise la formule 1 on dit qu on proc de l agr gation par le saut minimum ou du lien simple en anglais single link parce que la fusion de deux groupes est bas e sur la plus petite des distances inter groupes La hi rarchie bas e sur la formule 2 est appel e hi rarchie du diam tre ou du lien complet en anglais complete link car elle est bas e sur la plus grande distance interne au groupe r sultant ce qui est la d finition m me du diam tre de ce groupe Enfin la classification fond e sur la formule 3 s appelle hi rarchie de la distance moyenne average link en anglais Deux remarques s imposent propos de cette construction hi rarchique les nombreuses recherches et modifications sur les distances obligent g rer celles ci en m moire centrale de l ordinateur ce qui limite s rieusement la taille de l chantillon en revanche ce type d al
18. Numerical Taxonomy 359p Freeman and co San Francisco London Shepard R N 1962 The analysis of proximities scaling with an unknown distance function I Psychometrica vol 27 no 2 Spearman C 1904 The proof and measurement of association between two things American J Psychology 15 88 Todd E 1979 Le fou et le prol taire Le Livre de Poche Robert Laffont Paris Volle M 1978 Analyse des donn es 265p Economica Paris Ward J H 1963 Hierarchical grouping to optimize an objective function J Amer Stat Assoc 58 236 244 Williams W T and Lambert J M 1959 Multivariate methods in plant ecology I Association analysis in plant communities J Ecology 47 83 101 INDEX N B Les r f rences indiquent successivement le num ro du chapitre et du paragraphe concern s Ainsi c3 1 2 d signe le paragraphe 1 2 du chapitre 3 Quand il n y a pas de num ro de paragraphe cela signifie que tout le chapitre est consacr la notion que l on recherche Les r f rences al ou a2 d signent respectivement les annexes 1 et 2 enfin la lettre b renvoie la bibliographie Agglom ration Voir agr gation Agr gation s Autour de centres mobiles Par le diam tre ou Lien complet Par la distance moyenne Par le lien simple ou Saut minimum Par le moment d ordre deux Successives Analyse factorielle Des correspondances En composantes principales Pr traitement par Benz cri J P Bourbaki N CAHLM CAH
19. P 1964 Analyse factorielle des proximit s Publication de l Institut de Statistique de l Universit de Paris Paris Benz cri J P 1966 Le ons sur l analyse factorielle et la reconnaissance des formes Cours du 3 me cycle ISUP Paris Benz cri J P et coll 1973 L Analyse des donn es Tome 1 La Taxinomie 615p Dunod Paris Benz cri J P 1982 Histoire et pr histoire de l Analyse des donn es 159 p Dunod Paris Benz cn J P et F Benz cri 1980 Pratique de l Analyse des donn es Analyse des correspondances expos l mentaire 424p Dunod Paris Bertier P et Bouroche J M 1975 Analyse des donn es multidimensionnelles 270p PUF Paris Boley D 1998 Principal directions divisive partitioning Data mining and knowledge discovery 2 325 344 Bourbaki N 1958 Livre III chap 9 Utilisation des r els en topologie 2 Ex 4 Hermann Paris Bouroche J M et Saporta G 1980 L Analyse des donn es 125p Collection Que sais je PUF Paris Caillez P et Pag s J P 1976 Introduction l analyse des donn es 616p Ed SMASH 9 rue Duban 75016 Paris Paris Chandon J L et Pinson S 1981 Analyse typologique 254p Masson Paris Chavent M Guinot C Lechevallier Y Tenenhaus M 1999 M thodes divisives de classification et segmentation non supervis e recherche d une typologie de la peau humaine saine Rev Stat Appl XLVII 4 87 99 Clark P J 1952 An extension of the co
20. axes factoriels 2 2 Traitement Le choix de l une ou l autre des deux m thodes possibles tiendra compte surtout de leur fonctionnement car les contraintes li es la taille des donn es sont peu pr s les m mes pour les deux m thodes Celle du moment d ordre deux d une partition fournit une hi rarchie qui devra donc tre tronqu e si l on veut une partition des objets L agr gation autour de centres mobiles fournit directement une partition mais elle n cessite le choix d une partition initiale qui peut tre tir e au hasard dont d pend le r sultat final 2 3 Interpr tation Lorsqu on utilise la classification comme une tape pr liminaire d autres traitements on ne cherche pas d interpr tation aux r sultats Cependant les aides l interpr tation sont parfois utiles pour critiquer les donn es avant d aller plus avant dans leur analyse En r sum on ne devra pas s effrayer devant la vari t des algorithmes possibles car le choix se limite de fait deux ou trois d entre eux pour leur qualit ou pour leur efficacit sur de grands tableaux D ailleurs lorsqu on peut les comparer on constate g n ralement un bon accord entre les r sultats des diff rentes m thodes Pour des applications r p titives dans un domaine pr cis l utilisateur devra vraisemblablement faire des essais comparatifs et choisir l algorithme qui lui parait le mieux adapt son probl me Cependant nous d conseillons l adjonc
21. c est dire des effectifs des classes Le r le des variables peut tre facilement appr ci dans leur contribution cette dispersion Comme au chapitre 5 on suppose que la distance utilis e est la distance euclidienne usuelle 1 1 Interpr tation d une partition Reprenant les notations du chapitre 5 on appelle Q la partition form e des classes q q d effectifs m My dont les centres de gravit sont g gq Le moment d ordre deux de la partition Q est M Q m Za Mg d Sar g o g sans indice d signe le centre de gravit de l ensemble de tous les objets Le carr de la distance euclidienne entre g et g s crit d Jar g Mia 94 3 s g 39 o J repr sente l ensemble des variables g J est la j me coordonn e du point g En intervertissant l ordre de sommation on a donc M Q Lies DA Mg Ja 3 g 3 8 1 On appellera contribution de la variable j la classe q la quantit CTR q j m gq j g j Remarquons que cette quantit est toujours positive cependant il peut tre utile de connaitre le signe de la diff rence entre parenth ses pour savoir si la variable j est inf rieure ou sup rieure la moyenne g n rale g j dans la classe consid r e Dans la pr sentation des r sultats on publiera deux tableaux Le premier s appelle contributions des variables aux classes et donne les quantit s ci dessus munies du signe convenable exprim es en pourcentage re
22. certain nombre fix par l utilisateur de tirages al atoires de partitions initiales qui sont toutes soumises l algorithme des centres mobiles Seule la meilleure partition finale est conserv e et affich e Dans les deux versions le r sultat rend compte de la qualit de la partition obtenue en donnant le rapport d inerties Il indique galement la contribution de chaque classe au moment inter classe Chapitre 6 Construction ascendante hi rarchique du moment d ordre deux 1 Principe et probl mes La construction hi rarchique du moment d ordre deux est une m thode agr gative analogue celles qui sont d crites au chapitre 4 Elle est connue dans le monde anglo saxon sous le nom de m thode de Ward Ward 1963 Son originalit provient de ce que le crit re permettant de d cider de la fusion de deux classes n est pas bas sur une quelconque notion de distance entre classes mais sur l augmentation de la dispersion intra classe Pour comprendre cela il nous faut reprendre le th or me de Huyghens examin au chapitre pr c dent paragraphe 1 2 et l appliquer au cas particulier d une partition en deux classes q et q Dans ce cas la formule 5 3 du chapitre 5 devient M qUq M q M q m d g Ja mg g Jar o l on d signe par qUq la r union des deux classes q et q On montre par ailleurs facilement cf Benz cri 1975 Jambu 1978 que le moment intra classe repr sent par les deux derniers termes de
23. des formes fortes permet galement de s affranchir d un autre inconv nient de la m thode qui est de n cessiter le choix a priori du nombre de classes En effet le nombre de formes fortes peut tre tr s variable et ne d pend pas directement du nombre de classes choisi Un autre probl me est celui du choix d une partition initiale Il est vident que si l on a des informations sur les regroupements possibles il vaut mieux en tenir compte pour d marrer avec une bonne partition Notons ce propos qu il n est pas n cessaire d affecter tous les objets une classe On peut laisser certains objets sans affectation A la premi re tape de l algorithme les centres de gravit seront calcul s sur les seuls objets appartenant une classe d clar e Puis l ensemble des objets sera affect ou r affect en fonction de ces centres de gravit Signalons enfin une variante possible de cet algorithme Pour chaque classe trouv e au cours d une tape on peut prendre un certain nombre fix l avance de repr sentants de cette classe au lieu du centre de gravit On r affecte ensuite l ensemble des objets en fonction de la moyenne de leurs distances ces repr sentants Les repr sentants sont des points centraux choisis suivant le m me crit re de la moyenne des distances Cette variante a l avantage d viter de fabriquer des classes creuses le centre de gravit peut en effet tomber dans une zone de faible densit interm diaire
24. deux noeuds concern s p et q sont fusionn s et leur niveau est calcul selon la distance moyenne entre les trois groupes n c et d Nous proposons une troisi me strat gie dans laquelle apr s la construction descendante on contr le les niveaux des partitions successives Dans le cas o l on d couvre une inversion on recalcule la distance moyenne entre les trois groupes concern s et cette distance moyenne est prise comme niveau commun aux deux noeuds en inversion 5 Applications aux exemples 5 1 Exemple PSYSOC Nous avons trait le tableau des distances relatif aux donn es PSYSOC par l algorithme que l on vient de d crire CDH LM paragraphe 3 3 Les distances sont calcul es par la formule euclidienne usuelle sur les 3 premiers axes de l A F C Les r sultats voir figure 1 sont comparables ceux que procure la hi rarchie ascendante de la distance moyenne quoique les deux pays excentriques Irlande du Nord NIRELA et USA tout en tant isol s des autres ne soient pas mis dans un m me groupe Mais on y retrouve bien le groupe M diterran en SPAIN ITALY et PORTUG reli au groupe Europe moyenne FRANCE WGERMA et AUSTRIA Les autres pays sont ceux du groupe Europe Nord dans lequel il est difficile de discerner des sous groupes NIRELA PORTUG 4 FRANCE WGERMA AUSTRI DENMAR SWITZE FINLAN SIRELA
25. diff rentes trois d entre elles ont converg vers la m me partition finale d j trouv e Une seule d entre elles a donn une partition diff rente voir tableau 1 mais avec un rapport moment interclasse moment total de 0 51 beaucoup plus faible que celui de 0 70 qui correspond la partition pr c dente Ce rapport R nous permet de trancher en faveur de la partition trouv e l aide de la CAH 2 2 Partition en quatre classes Nous avons voulu voir quels r sultats on obtient lorsque l on choisit un nombre de classes en d saccord avec les donn es Ce qui peut arriver en pratique si l on n a fait aucune analyse pr alable On a effectu quatre tirages au hasard en quatre classes Les partitions P1 P2 P3 P4 issues de ces tirages ainsi que les r sultats P1 P2 P3 P4 de l algorithme des centres mobiles sont consign s dans le tableau 2 Les rapports d inertie obtenus sont respectivement 0 80 0 49 0 75 et 0 81 La partition P4 est donc la meilleure mais elle est suivie de pr s par P1 et P3 La partition P2 est franchement mauvaise PB P P1 P3 AUSTRI 1 4 AUSTRI 4 1 FRANCE 3 1 FRANCE 1 4 PORTUG 3 1 PORTUG 1 4 WGERMA 1 1 WGERMA 4 1 BELGIU 1 3 BELGIU 3 1 FINLAN 3 3 FINLAN 3 4 SWEDEN 3 3 SWEDEN 4 4 SWITZE 3 3 SWITZE 3
26. entier est d abord scind en deux puis chacune de ses parties est son tour subdivis e et ainsi de suite Dans le troisi me groupe de m thodes on peut rassembler toutes celles qui se limitent l laboration d une partition Par des algorithmes tr s divers ces m thodes ont pour objectif de d tecter les zones forte densit dans l espace des observations Etant donn la faiblesse des bases th oriques de tous ces algorithmes usuels il serait imprudent de se fier totalement aux r sultats ainsi obtenus C est pourquoi nous recommandons vivement l utilisateur de toujours confronter ses r sultats ceux d une analyse factorielle Benz cri et coll 1973 b Bertier et Bouroche 1975 De Lagarde 1983 F nelon 1981 Foucart 1982 Bouroche et Saporta 1980 3 Objectifs et plan de l ouvrage Dans les pages qui suivent on se propose de donner les bases math matiques les algorithmes et les programmes de calcul pour les principales m thodes de classification Comme notre intention est de fournir aux praticiens les moyens de comprendre et d utiliser ces m thodes nous avons bas l expos sur deux exemples typiques d crits au chapitre 2 qui sont trait s par tous les algorithmes possibles Chaque chapitre comporte l expos d un algorithme et son application l un ou l autre des exemples On explique ensuite la mise en uvre du programme correspondant et ses principales caract ristiques en vue d une adaptation ventuelle Par
27. entre tous les objets deux deux ont t calcul es suivant l une des formules du chapitre pr c dent On proc de alors par tapes successives chacune d elles consistant r unir les deux objets les plus proches A la fin de chaque tape on recalcule les distances entre le groupe nouvellement cr et le reste des objets Cela permet de r it rer le processus jusqu ce que tous les objets aient t r unis dans un seul groupe Lorsque cela est achev on dresse un arbre hi rarchique dont les noeuds repr sentent les fusions successives la hauteur de ces noeuds tant gale la valeur de la distance entre les deux objets ou groupes fusionn s Le niveau des noeuds a donc ainsi une signification concr te on dit dans ce cas qu on obtient une hi rarhie indic e La seule difficult de ce processus reside dans le choix d une formule pour le recalcul des distances apr s fusion Curieusement les consid rations math matiques ne sont pas d un grand secours pour faire ce choix voir cependant ci dessous paragraphe 1 2 et annexe 2 Dans les m thodes usuelles il est plut t le fruit du bon sens et de l exp rience Nous allons examiner les trois formules les plus courantes On d signe par 1 et i les deux objets ou groupes d objets que l on veut fusionner et par k un autre point de 1 ensemble d iUi k Min d i k d i kp 1 d iUi k Max d i k d i k 2 d iUi k p i d i k p i d i k p
28. est dire qu chaque tat de variable ou modalit on fait correspondre une colonne du tableau final En regard d une observation occupant une ligne du tableau on met un 1 dans les colonnes indiquant ses qualit s et des z ros partout ailleurs cf Benz cri 1980 Foucart 1982 Toutefois pour certaines donn es o les variables sont deux modalit s pr sence ou absence d un attribut il arrive que l absence n ait pas la m me valeur significative que la pr sence Il est alors pr f rable de coder chaque attribut sur une seule colonne au lieu de deux avec un 1 si l attribut est pr sent et un z ro s il est absent C est le cas en phytosociologie cf exemple 2 au chapitre pr c dent o la pr sence d une plante est une indication plus importante que son absence relativement la nature du sol au climat etc De nombreux chercheurs ont d ailleurs mis au point des formules de distances prenant en compte cette remarque Ainsi l indice de Jaccard fournit g n ralement un bon point de d part pour une classification Cet indice est bas sur le nombre c d attributs communs c est le nombre d esp ces pr sentes simultan ment dans deux relev s de plantes et sur les nombres p et q d attributs poss d s par chacune des deux observations consid r es d 1 c p q c 2 Le d nominateur de la fraction repr sente le nombre d attributs existant soit dans l une soit dans l autre soit dans les deux observatio
29. est de 132 les pays de l autre sous classe 2 ayant naturellement des taux inf rieurs la moyenne sauf BELGIU 3 2 Donn es PHYTOS qualitatives Pour cette application nous reprenons la partition en 4 classes mise en avant au chapitre 2 paragraphe 1 2 et retrouv e dans les applications pr c dentes le relev 24 d affectation incertaine a t attribu au groupement Pacnl comme cela a t propos au chapitre 2 CL 1 Groupement Pan relev s 13 15 23 Nardetum alpigenum CL 2 Groupement Pacnl relev s 3 4 14 16 24 Festucetum halleri subass Nardetosum faci s normal CL 3 Groupement Pacn2 relev s 10 54 55 Idem mais faci s Elyna et Salix CL 4 Groupement Pac relev s 27 30 31 36 38 Festucetun halleri sensu stricto Le tableau 4 donne pour toutes les esp ces en lignes leur contribution aux quatre classes de cette partition vedette L avant derni re colonne repr sente la somme de ces contributions c est dire le degr de liaison globale entre l esp ce et la partition gale au Khi deux de contingence Les contributions sont exprim es on milli mes Comme les esp ces sont toujours des variables deux modalit s pr sence ou absence tous ces nombres sont comparables d une ligne l autre Cependant on doit se souvenir que l absence d une esp ce joue autant que la pr sence dans la valeur du Khi deux ce qui conduit caract riser les classes plus souvent par l absence que par la pr sence Il conv
30. i p i 3 La formule 1 indique que la nouvelle distance entre le groupe i 1 d sign par 1U1 et le point k sera gale la plus petite des deux distances de 1 k et de i k La formule 2 stipule au contraire que la nouvelle distance doit tre gale la plus grande des deux anciennes Enfin la formule 3 dit que la nouvelle distance vaudra la moyenne des distances ant rieures Dans cette formule p 1 et p i d signent le nombre d objets appartenant au groupe i et au groupe 1 Au d but de l algorithme ces groupes sont r duits un seul point mais il n en est pas de m me au bout de quelques tapes Ces pond rations assurent qu tout moment la distance calcul e entre deux groupes est gale la moyenne des distances initiales entre les points de l un et les points de l autre distances inter groupes D ailleurs si l on n utilisait pas ces pond rations on s exposerait des d sagr ments En effet chaque tape de l algorithme on prend la valeur de la distance entre les deux points fusionn s pour niveau du n ud de l arbre hi rarchique Les distances recalcul es par l une ou l autre des formules ci dessus sont donc des valeurs possibles pour le niveau des noeuds suivants de la hi rarchie Mais pour que celle ci puisse tre construite il faut que ces niveaux ult rieurs soient sup rieurs celui que l on vient de cr er On aurait autrement un ph nom ne d inversion voir figure 1 a b c
31. la somme ci dessus s crit aussi Ma d g Ja Ma d g g My Mar Mg m4 d Jar Jaq 6 1 Si les deux classes q et q sont les l ments d une partition cette expression repr sente l augmentation du moment intra classe qui arriverait si l on fusionnait les deux classes q et q en effet lorsque q et q sont s par es leur contribution au moment intra classe vaut M q M q C est pr cis ment cette quantit 6 1 que l on prend comme crit re d agr gation dans la hi rarchie du moment d ordre deux A chaque pas de l algorithme on fusionne les deux classes qui provoquent la plus faible augmentation du moment intra classe Cette augmentation du moment intra classe joue donc maintenant le r le de la distance dans l algorithme l mentaire du chapitre 4 nous l appellerons pseudo distance Au d but de l algorithme supposant que chaque objet est muni d une masse unit la matrice des pseudo distances vaut pour la case i 1 1 2 od i i Au premier pas de l algorithme on agr ge la paire pour laquelle cette quantit est la plus petite qui en l occurence co ncide avec celle de la plus petite distance Pour pouvoir proc der l agr gation suivante il faut alors calculer l augmentation du moment intra classe avec chacun des autres objets La formule 6 1 fait intervenir les centres de gravit des classes et ne permet donc pas facilement le recalcul des nouvelles pseudo distances partir des a
32. le premier cas les donn es ne sont pas classifiables tandis qu elles le sont dans le deuxi me cas L exp rience confirme cette appr ciation mais elle doit tre modul e en fonction de l algorithme utilis pour la construction hi rarchique En effet certains algorithmes ont une propension donner un arbre du type 1 d autres donner des groupes tr s visibles comme dans le cas 2 Ainsi dans l agr gation par le saut minimum ou lien simple l effet de chaine caract ristique de cette m thode voir chapitre 4 paragraphe 1 2 se traduit par un arbre du type 1 mais m me en l absence de r elle disposition en chaine cette m thode tend r tr cir les intervalles de variation des distances donc rapprocher les niveaux d agr gation On n en conclura donc pas la non validit des groupes observ s La hi rarchie du diam tre ou lien complet pr sente la particularit inverse c est dire qu elle montre des groupes bien marqu s l o parfois on n a qu une seule suite de points faible distance les uns des autres En bref elle casse les chaines d objets Bien entendu l agr gation par la distance moyenne r alise un compromis int ressant entre les deux m thodes pr c dentes Enfin la hi rarchie du moment d ordre deux pr sente le m me d faut que celle du diam tre en plus pouss Non seulement elle a tendance fabriquer des boules de diam tres comparables mais l impression de nettet des groupes form
33. on peut faire correspondre une hi rarchie indic e unique H dont s 1 d soit l indice associ En effet la relation s i 1 gt x ou d i 1 1 x est une relation d quivalence sur I dont les classes d finissent une partition P x unique pour chaque x H est alors d termin e par les parties h telles qu il existe x e 0 1 dont la partition P x contient h comme l une de ses composantes L indice x h est alors le plus grand x tel que h e P x Ces d finitions et propri t s appellent quelques remarques Remarque 1 La relation 1 entra ne l in galit triangulaire de sorte que toute application d de I x I dans R v rifiant 1 et les conditions 2 d i j 0 gt i 3 V i Lhe I i d i i d i 1 est une distance ultram trique Remarque 2 Si d est une ultram trique on peut d montrer que d i k d j k entra ne d i j Max d i k dg k de sorte que tout triangle est isoc le avec la base inf rieure aux cot s gaux En effet on n enl ve pas de g n ralit supposer que d i k lt dj k donc di j x dG k d apr s 1 Toujours d apr s 1 on a d j k x Max d 1 j dG k comme d i k lt dG k par hypoth se on a n cessairement d j k lt dG j donc d i j dG kK La correspondance entre hi rarchie indic e et ultram trique nous permet de poser le probl me de la classification en termes plus pr cis que ceux de notre introduction chapitre 1 paragr
34. p variables Ce moment d ordre 2 est encore appel Moment d inertie car il est correspond exactement cette notion de m canique Th or me de Huyghens Examinons maintenant le cas du moment d ordre deux par rapport un point a diff rent du centre de gravit M I a m d 1 a m d 2 a m d n a Le i me terme m d i a de cette somme est lui m me une somme pond r e de carr s d carts aux coordonn es x a j de a l indice j parcourant l ensemble 1 2 p des variables m qd i a m x i 1 x a 1 m x i 2 x a 2 m x i p x a PIN Le j me terme de cette expression peut son tour se d composer en faisant intervenir la j me coordonn e du centre de gravit m x i j x a 3 m x i 3 x g 3 x g 3 x a j m x i j x a j mIx i Jj x g 3 2m x i j x g j x g 3 x a 3 m x g 3 x a j Pour obtenir le moment d ordre deux il faudra donc faire une double somme d expressions analogues l une sur les variables indice j l autre sur les individus indice 1 Commengons par la somme sur les individus et examinons le terme interm diaire 2m x i j x g 3 lix g 3 x a 3 1 Comme le deuxi me crochet ne d pend pas des individus on pourra le mettre en facteur dans la somme des termes interm diaires qui devient 2 x g 3 x a 3 m x 1 3 x g j m x 2 3 x g 5 zu doma
35. plus n n 1 2 partitions au lieu des 20 1 _ 1 bipartitions possibles Le calcul du crit re est lui m me d ordre n enfin le nombre total de scissions effectuer est gal n 1 On a donc un algorithme de complexit polynomiale de degr 4 C est un ordre lev mais qui reste r alisable avec les ordinateurs actuels En accord avec le crit re de scission il est naturel de fixer les niveaux de la hi rarchie gaux la distance moyenne entre les groupes qu ils d finissent C est pourquoi nous avons appel CDH LM le programme r alisant cet algorithme 4 Le probl me des inversions La proc dure ci dessus pr sente un grave inconv nient elle ne garantit pas contre l apparition d inversions dans la hi rarchie laquelle est alors impossible construire et jette quelques doutes sur sa validit Ce ph nom ne bien que peu fr quent environ 10 des cas selon nos essais demande un am nagement de la m thode Pour cela plusieurs strat gies sont possibles La premi re strat gie consisterait simplement signaler par un message l utilisateur qu une inversion s est produite La seconde strat gie possible est celle adopt e par Kaufman et Rousseeuw 1990 les niveaux d agr gations sont les diam tres des classes correspondantes Comme les sous classes sont n cessairement d un diam tre inf rieur ou gal la classe qui les englobe il ne peut y avoir d inversion a b c d a b c d Fig 1 En cas d inversion les
36. plusieurs centaines d objets voire plusieurs milliers il arrive que la seule m thode possible soit celle des agr gations autour de centres mobiles En une telle circonstance il n est gu re possible d essayer plusieurs partitions initiales tir es au hasard car chaque tirage le temps de calcul n cessaire au d roulement de l algorithme peut tre assez long et l on est donc contraint de se limiter quelques essais voire un seul La partition ainsi obtenue peut tre de qualit m diocre et ne donne pas d assurances sur la validit du nombre de classes choisi Plut t que de chercher directement le regroupement des objets en un nombre restreint de classes nous proposons dans une tape pr liminaire d obtenir une partition en un grand nombre de classes Puis de prendre les centres de gravit ou points moyens de ces classes comme objets pour une classification hi rarchique Supposons que l on ait par exemple 5000 observations classer On pourra demander aux centres mobiles de cr er disons 100 classes Chacune d entre elles contiendra en moyenne 50 observations qui seront repr sent es par les valeurs moyennes de leurs variables Ces points moyens seront alors agr g s en un temps raisonnable par une construction ascendante hi rarchique 2 3 Donn es h t rog nes emploi de l analyse factorielle pr alable On a d j eu l occasion d examiner les avantages du pr traitement par l analyse factorielle cf chapit
37. seconde Il est vident que toute m trique d sur I induit une ordonnance en d clarant 1 j lt k 1 si et seulement si d i j d k 1 voir annexe 1 D autre part une hi rarchie H sur un ensemble fini I induit une relation d ordre non total en g n ral sur les paires d l ments de I de la fa on suivante on dira que 1 j k D s il existe une partie h de H contenant i et j telle que l on ait soit lehet ke h soit L het ke sh Si une telle partie h n existe pas c est que la situation est la suivante toute partie h qui contient i et j soit contient aussi k et 1 soit ne contient ni l un ni l autre Deux ventualit s se pr sentent alors ou bien il existe h e H contenant k et 1 mais ne contenant pas i et j auquel cas i j et k 1 ne sont pas comparables ou bien une telle partie h n existe pas et alors i j lt k 1 En notation arborescente ces deux cas donnent les arbres suivants A B j i l k j i l k Figure 2 Comparaison de paires d objets A Existence de h B h n existe pas Enfin si toute partie de H qui contient i et j contient aussi k et 1 nous dirons que i J k 1 1 2 Hi rarchie indic e et ultram trique D finition 1 Benz cri 1966 Une hi rarchie H sur un ensemble I fini est dite indic e s il existe une application x H gt 0 1 telle que 1 si h H est r duite un l ment alors x h 1 2 si h cC h eH alors x h gt x h On
38. souci de clart les d veloppements th oriques importants sont renvoy s en annexe Comme la plupart des m thodes commencent par le calcul de distances on tudiera d abord les modalit s de ce calcul chapitre 3 On pourra alors d crire les algorithmes usuels de construction ascendante de hi rarchie chapitre 4 puis un algorithme devenu classique de construction d une partition chapitre 5 On envisage ensuite des m thodes moins courantes la construction ascendante selon la variance des distances chapitre 6 et une construction descendante hi rarchique chapitre 7 On termine par des calculs compl mentaires facilitant l interpr tation des r sultats chapitre 8 et par un chapitre num ro 9 indiquant quelques r gles l mentaires suivre pour le traitement ces donn es En conclusion chapitre 10 nous r sumerons les caract ristiques de chacune des techniques d crites en indiquant nos pr f rences 4 Domaines d application et points de vocabulaire La classification a un r le jouer dans toutes les sciences et techniques qui font appel la statistique multidimensionnelle Citons tout d abord les sciences biologiques botanique zoologie cologie Ces sciences utilisent galement le terme de taxinomie pour d signer l art de la classification De m me les sciences de la terre et des eaux g ologie p dologie g ographie tude des pollutions font grand usage de classifications La classification es
39. stocker en m moire le tableau des donn es mais de le relire chaque fois qu on en a besoin les individus tant balay s s quentiellement dans les deux cas o cela se produit Cependant un allongement consid rable du temps de calcul serait pr voir du la lenteur des acc s disques 1 2 Nature des donn es Lorsque les donn es sont quantitatives chacun des programmes peut tre utilis Cependant il convient de refl chir si l on doit effectuer une normalisation pr alable des variables En revanche avec les donn es qualitatives il est obligatoire de choisir une formule de distances adapt e voir chapitre 3 Dans ce cas il faut utiliser l un des programmes DisJac ou DisKi2 ou tout autre programme destin au cas de variables qualitatives puis appliquer CAH ou CDH aux distances ainsi calcul es 1 3 Qualit des r sultats En dehors des contraintes voqu es ci dessus les quatre principaux algorithmes tudi s ne donnent pas des r sultats d gale qualit On a d j critiqu chacun d eux en son temps mais il est bon de rappeler que dans le cas o ils sont tous applicables l exp rience permet d tablir entre eux la hi rarchie suivante en allant du m diocre au tr s bon CenMob gt CDH gt CAHmom2 gt CAHLM Bien entendu ce rangement correspond aux cas les plus fr quents il peut arriver que pour un exemple particulier CDH ou CAHmom2 donne une hi rarchie meilleure que CAHLM c est di
40. suivant 1 Pour chaque objet 1 rechercher son plus proche voisin que nous appellerons PPV 1 2 Agr ger toutes les paires de voisins r ciproques c est dire les couples i i tels que PPV i 1 et PPV i i 3 Retourner en 1 tant que le nombre de groupes restants est sup rieur ou gal deux Il faut noter que les r sultats sont rigoureusement identiques ceux que l on obtient par l algorithme maintenant traditionnel des agr gations successives tel qu il a t d crit au chapitre 4 3 Application l exemple PSYSOC Les coordonn es des pays sur les trois premiers facteurs de l AFC ont encore une fois servi de donn es pour l algorithme des voisins r ciproques celui ci a t programm voir ci dessous paragraphe 4 pour valuer les distances selon la m trique euclidienne usuelle tandis que les agr gations sont faites selon le crit re du moment d ordre deux Les r sultats sont tr s largement concordants avec les m thodes employ es jusqu ici figure 1 On retrouve les trois groupes principaux d j d termin s Seules changent les subdivisions du grand groupe baptis Europe Nord FRANCE AUSTRI WGERMA SPAIN PORTUG ITALY NIRELA 4 USA 4 FINLAN SWITZE DI Lr NMAR SIRELA ICELAN NORWAY Bi Lr GIU SWEDEN SCOTLA
41. 0 0 33 Q Jp 36 0 7 0 21 53 0 100 0 0 0 0 100 0 25 0 56 100 8 3 5 55 0 0 0 0 0 0 100 0 0 0 100 100 14 3 2 57 0 0 0 0 100 0 O 33 0 17 20 100 8 17 0 60 0 100 0 0 0 100 0 100 25 6 Zi 20 8 44 5 61 0 100 0 0 0 0 0 100 25 6 2 0 45 0 21 62 0 100 100 100 25 100 0 11 25 38 0 25 0 44 0 63 100 0 0 25 0 0 0 100 100 6 22 0 7 0 21 64 100 0 0 25 0 0 100 100 100 38 0 0 7 38 10 65 0 0 0 0 0 100 100 0 100 100 22 25 31 3 0 67 0 0 100 100 25 0 0 11 0 38 20 100 1 17 1 68 100 0 100 25 25 0 0 33 0 17 36 0 0 0 15 69 0 0 0 0 0 0 100 0 0 100 9 0 66 38 16 70 0 0 0 100 0 0 0 0 0 100 9 0 6 0 6 71 0 0 0 0 0 0 0 0 0 0 0 100 0 44 5 72 0 0 0 0 0 0 100 0 0 0 0 0 0 38 73 75 0 100 0 0 0 0 0 0 225 0 56 0 8 100 5 77 0 0 0 100 0 100 0 0 100 100 22 25 0 44 5 T9 100 0 0 25 100 0 0 11 100 6 22 0 0 0 35 82 0 0 100 0 25 0 o 11 0 6 9 0 66 0 15 84 0 0 0 0 0 0 0 0 0 0 0 0 0 100 51 86 0 0 0 0 100 0 0 33 0 L7 v20 0 8 0 6 87 0 0 0 100 0 0 0 0 0 100 9 0 6 0 6 90 0 0 0 0 0 0 0 0 100 0 56 0 8 0 6 95 0 100 0 0 0 0 100 0 25 0 24 0 66 38 3 98 0 0 0 0 0 100 100 0 0 0 0 25 0 3 51 100 0 0 0 0 0 100 100 0 0 0 0 25 0 3 DL LOS 0 0 0 100 0 0 0 0 0 100 9 0 6 0 6 109 0 0 100 0 25 0 100 33 100 7 0 0 14 38 24 12 0 0 0 100 100 0 0 11 0 6 9 0 6 0 6 113 0 0 0 0 0 0 0 0 100 0 24 0 4 100 30 14 0 0 0 0 0 0 0 0 100 0 24 0 4 0 3 116 0 0 0 0 100 0 0 33 O TI 36 0 3T 0 21 117 0 0 0 0 0 0 0 0 0 0 0 0 0 0 100 120 0 0 100 0 25 0 0 33 0 7 20 0 8 0 58 125 0 0 0 0 0 0 0 0 0 0 0 100 Q IT d5 126 0 0 100
42. 00 2 2 Phytosociologie PHYTOS Pour l exemple des donn es phytosociologiques on prend l indice de distance de Jaccard On aurait pu galement calculer les distances au sens du Khi deux Mais l exp rience montre que les disparit s de poids entre esp ces provoquent des fluctuations disproportionn es dans les distances et les classifications ult rieures s en trouvent souvent difficiles interpr ter Cf chapitre 4 paragraphe 2 Les r sultats sont consign s dans le tableau 3 o les valeurs sont multipli es par mille R3 RA R10 R13 R14 R15 R16 R23 R24 R27 R30 R31 R36 R38 R54 RA 550 R10 632 629 R13 590 622 784 R14 486 514 563 600 R15 500 675 763 276 543 R16 474 579 629 658 424 528 R23 727 732 821 469 718 455 667 R24 675 744 697 757 531 667 469 531 R27 721 756 676 800 711 810 725 833 789 R30 750 789 750 735 625 784 686 811 758 697 R31 756 763 794 811 636 850 730 902 765 625 500 R36 537 600 718 675 541 690 634 826 756 528 667 676 R38 825 868 844 919 861 923 838 975 914 621 654 615 784 R54 651 579 629 543 595 528 683 632 744 725 789 763 634 868 R55 585 579 545 692 556 707 615 732 676 622 757 763 564 806 412 Tableau 3 Donn es PHYTOS indices de distance de Jaccard entre relev s multipli s par 1000 3 Les proc dures de calcul de distances Trois proc dures s par es sont propos es dans le classeur Excel la proc dure DisEuc pour le calcul des distances euclidiennes usuelles la proc dure DisKi2 pour le calc
43. 100 25 0 0 33 0 7 20 0 15 0 15 129 0 100 0 0 0 0 0 0 25 0 24 0 66 0 15 130 0 0 0 0 100 0 0 11 100 6 2 0 8 0 6 131 0 0 0 0 0 0 0 0 0 0 100 0 14 0 10 144 0 0 100 0 25 0 0 0 6 9 0 4 0 76 45 0 0 100 0 25 0 0 11 0 38 20 100 8 44 5 156 0 0 0 0 0 0 0 0 0 0 0 0 0 100 31 157 0 0 0 0 0 100 0 0 0 0 0 25 0 44 31 158 0 100 0 0 0 0 0 100 25 6 2 0 45 0 21 159 0 0 0 0 100 0 o 11 0 6 9 0 66 0 15 L60 100 0 0 25 0 0 100 100 0 6 9 0 6 38 0 163 0 100 0 0 0 100 0 0 25 0 24 25 66 44 0 166 0 0 0 0 100 100 0 33 0 17 36 25 14 17 1 168 0 0 0 0 0 0 0 0 0 0 0 100 0 44 31 Tableau 5 Donn es PHYTOS contributions des variables esp ces aux n uds de la hi rarchie du lien moyen Voyons maintenant l application des calculs de contributions la hi rarchie ascendante de la distance moyenne calcul e sur l indice de distance de Jaccard Comme dans le cas quantitatif seuls les niveaux sup rieurs de l arbre sont int ressants Cf figure 2 construite d apr s les r sultats du chapitre 4 PAcnl 26 27 29 31 PAcn2 25 PAn 20 PAC 30 Figure 2 Partie sup rieure de la hi rarchie de la distance moyenne Donn es PHYTOS distance de Jaccard Dans le tableau 5 la disposition est que les lignes repr sentent les variables esp ces tandis que les colonnes sont les noeuds successifs de la hi rarchie Pour le noeud 31 derni re colonne se d tachent les esp ces suivantes la contribution au n ud est entre parenth ses 117
44. 13 Paris Paris Foucart T 1982 Analyse factorielle Programmation sur micro ordinateur Masson Paris Gondran M 1975 Valeurs propres et vecteurs propres en classification hi rarchique Communication aux journ es d Etude sur les Probl mes d Analyse et d Ajustement de tableaux statistiques INSEE Nantes 23 25 Avril 1975 Goodall D W 1966 A new similarity index based on probability Biometrics 882 907 Guinochet M 1955 Logique et dynamique du peuplement v g tal 144p Masson Paris Guinochet M 1973 Phytosociologie 227p Masson Paris Hubert L 1973 Monotone invariant clustering procedures Psychometrika 30 1 Jaccard P 1908 Nouvelles recherches sur la distribution florale Bull Soc Vaud Sci Nat 44 223 270 Jambu M et Lebeaux M 0 1978 Classification automatique pour l Analyse des donn es Tome 1 M thodes et Algorithmes 312p Tome 2 Logiciels 400p Dunod Paris Jardine N and Sibson R 1971 Mathematical Taxonomy 286p Wiley and sons New York London Jardine C J Jardine N Sibson R 1967 The structure and construction of taxonomic hierarchies Mathematical Bioscience 175 195 Kendall M G 1938 A new measure of rank correlation Biometrika 30 1 2 81 93 Kochen M et Wong E 1962 Concerning the possibility of a cooperative information exchange IBM journal of Research and Development 6 270 271 Kulczinski S 1927 Die Pflanzenassoziationen der Pieninen En p
45. 159 1000 7 2479 3 7 82 380 488 50 1000 3 5879 3 10 688 85 85 142 1000 5 0286 3 11 218 131 634 17 1000 10 4145 3 T2 311 240 187 263 1000 1319 3 20 188 313 313 188 1000 1 3714 3 21 142 85 85 688 1000 5 0286 3 24 2 241 241 516 1000 7 4667 S 26 276 165 460 99 1000 6 0444 3 29 169 94 344 393 1000 6 7894 3 41 467 261 54 219 1000 2 4550 3 42 607 12 12 367 1000 1 7778 S 45 17 710 256 17 1000 9 9111 3 48 688 85 85 142 1000 5 0286 3 50 263 187 240 311 1000 1 3115 3 53 276 460 165 99 1000 6 0444 3 55 218 634 131 17 1000 10 4145 3 57 516 241 241 2 1000 2 8718 3 60 38 63 563 338 1000 1 7778 3 61 32 1 719 248 1000 9 1733 3 62 188 313 313 188 1000 0 0711 3 63 49 289 289 374 1000 6 0703 3 64 219 261 54 467 1000 2 4550 3 65 53 26 452 6 1000 5 1640 3 67 3317 562 62 37 1000 1 7778 3 68 540 165 18 276 1000 6 0444 3 69 187 313 313 187 1000 9 6000 3 70 99 165 460 276 1000 2 5905 3 71 142 85 85 687 1000 8 1231 3 72 142 85 85 688 1000 11 7333 3 75 276 460 165 99 1000 6 0444 3 TI 467 261 54 219 1000 2 4550 S T9 364 18 87 530 1000 7 3312 3 82 6 85 767 142 1000 11 7333 3 84 142 85 85 687 1000 8 1231 3 86 688 85 85 142 1000 5 0286 3 87 99 165 460 276 1000 2 5905 3 90 72 812 43 72 1000 9 9048 3 95 248 1 719 32 1000 9 1733 3 98 142 85 85 687 1000 8 1231 3 100 142 85 85 687 1000 8 1231 3 105 99 165 460 276 1000 2 5905 3 109 6 26 452 2517 1000 5 1640 3 112 99 165 460 276 1000 2 5905 S 113 276 18 165 540 1000 6 0444 3 114 72 813 43 72 1000 4 6222 3 116 17 634 1
46. 2n c d O 1 14 Sokal Sneath 3 1963 c d p q 2c 0 Infini 15 Sokal amp Sneath 4 1963 S1 c p c q D S2 d n p d n q S S1 S2 A 16 Sokal amp Sneath 5 1963 cd Rac pq n p n q 0 17 Roux 1 1985 D1 Min p a 0 D2 Min n p n q S c d D1 D2 18 Roux 2 1985 n cd pq n p n q 0 n 19 Hamann 1961 c d p c q c n 1 1 20 Yule 1911 N cd p c q c 1 1 D cd p c q c s N D 21 Phi de Pearson N cd p c q oc shy 1 D Rac pq n p n q S N D Tableau 2 Indices o les pr sences et les absences communes d attributs jouent des r les equivalents p nombre d attributs du 1 er objet q nombre d attributs du 2 me objet c nombre d attributs communs aux 2 objets d nombre d attributs absents simultan ment dans les 2 objets n nombre total d attributs possibles X xx k 1 2 n Rac racine carr e Min minimum Max maximum Remarque le coefficient Phi no 21 est gal au Khi 2 de contingence au coefficient 1 n pr s Note 10 L indice de Yule num ro 20 poss de l int ressante propri t d avoir un intervalle de variation s tendant de 1 1 m me lorsque p et q sont fix s cf remarque 4 paragraphe 2 1 Note 11 Les indices suivants ont des valeurs moyennes ind pendantes de p et q cf remarque 5 paragraphe 2 1 l indice num ro 15 a pour valeur moyenne 1 2 num rol
47. 31 218 1000 10 4145 3 117 142 85 85 688 1000 16 0000 3 120 3 210 210 578 1000 11 1238 3 125 142 85 85 687 1000 2 3467 3 126 99 165 460 276 1000 6 0444 3 129 134 9 723 134 1000 12 4444 3 130 99 460 165 276 1000 2 5905 3 dd 72 813 43 72 1000 16 0000 3 144 52 143 143 662 1000 12 5867 3 145 188 313 313 188 1000 3 2000 3 156 142 85 85 688 1000 5 0286 3 157 142 85 85 688 1000 5 0286 3 158 32 1 719 248 1000 9 1733 3 159 6 85 767 142 1000 11 7333 3 160 Dy GLE 313 5 1000 1 1214 S 163 338 3 622 2 1000 8 0356 3 166 613 188 188 13 1000 5 3333 3 168 142 85 85 688 1000 5 0286 3 Tableau 4 Donn es PHYTOS contribution des variables esp ces aux classes d une partition N17 N18 N19 N20 N21 N22 N23 N24 N25 N26 N27 N28 N29 N30 N31 1 0 100 0 0 100 0 0 11 25 6 2 0 8 100 5 2 0 0 100 0 25 0 0 33 100 17 y 0 21 0 35 5 100 100 0 25 0 0 0 O 25 0 24 0 29 0 10 7 0 0 0 100 100 0 100 11 0 6 9 100 29 3 2 10 0 0 100 0 25 0 o 11 0 38 20 0 8 0 6 TI 0 0 0 0 0 100 100 0 0 0 0 25 100 3 2 12 0 100 0 0 0 100 100 0 25 0 56 25 8 3 17 20 0 0 0 0 0 0 100 100 0 6 9 0 4 38 2 21 0 0 0 0 0 0 0 0 0 0 0 0 0 100 31 24 0 0 0 0 100 100 0 33 0 17 20 295 8 I4 35 26 100 0 0 25 0 0 0 0 0 0 0 100 59 44 5 29 0 100 0 0 0 0 100 0 25 100 22 0 14 38 24 41 0 100 0 100 0 100 100 0 25 100 22 25 0 3 5 42 0 0 100 100 295 0 100 33 100 17 7 0 2 38 6 45 0 0 0 0 0 0 100 100 100 6 22 0 14 38 1 48 0 0 100 0 25 0 0 33 0 17 20 0 8 0 6 50 100 0 100 25 25
48. 4 ITALY 1 1 ITALY 4 2 NIRELA 2 2 NIRELA 4 3 DENMAR 2 3 DENMAR 1 2 ICELAN 1 2 ICELAN 4 1 SCOTLA 1 2 SCOTLA 4 1 SPAIN oa SPAN 4 1 NORWAY 2 2 NORWAY 3 3 SIRELA 3 2 SIRELA 2 4 NETHER 2 3 NETHER 2 3 ENGLAN 2 2 ENGLAN 4 3 USA 1 2 USA 2 1 Tableau 1 gauche et tableau 2 droite Tableau 1 Partitions initiale P et finale P en trois classes R 0 51 P2 P2 1 2 2 3 4 1 1 2 4 3 3 4 4 3 2 2 1 1 1 1 4 2 1 4 4 4 3 1 4 4 4 4 2 4 3 4 4 1 Tableau 2 Partitions initiales P1 P2 P3 et P4 et finales P1 P2 P3 et P4 en quatre classes RI 0 8 R2 0 49 R3 0 75 R4 0 81 La partie encadr e en gras correspond aux trois meilleures partitions finales sur lesquelles sont bas es les formes fortes num r es dans le tableau 3 ci dessous L examen attentif des trois meilleures partitions montre que celles ci ressemblent beaucoup la bonne partition en trois classes obtenue pr c demment Elles s obtiennent par scission de l une des trois classes Ainsi P1 coupe en deux le groupe Europe Nord tandis que P3 subdivise le groupe M diterran e enfin P4 scinde encore le groupe Europe Nord mais d une mani re diff rente de PI Il est facile de d terminer la main les groupements stables ou formes fortes en rep rant les pays ayant la m me succession de num ros de classe travers les trois partitions retenues voir tableau 3 Ceci nou
49. 7 182 32 314 37 242 100 379 NETHERLA 89 7 169 10 218 47 133 142 68 ENGLANDW 79 10 130 14 203 36 200 141 65 USA 121 102 220 26 273 158 253 447 195 Tableau 1 Donn es PSYSOC avec les r sultats de l Analyse factorielle des Correspondances Les six premi res colonnes contiennent les taux de mortalit de diff rentes causes violentes de d c s dans 19 pays occidentaux en nombre de d c s pour 100 000 habitants Les trois derni res colonnes F1 F2 et F3 sont les coordonn es factorielles multipli es par 1000 des pays sur les trois premiers axes de l Analyse factorielle des Correspondances Tl 2 SUICIDES 3 4 AAUTR Bil AINDUS 6 4 7 AROUTE 8 9 CIRFOIE 10 11 12 T3 14 15 16 17 18 19 20 Figure 1 Donn es PSYSOC Analyse des correspondances repr sentation des variables sur les axes l et 2 Ces deux axes expliquent respectivement 44 33 et 34 41 de la variance totale 3 5 CIRFOIE 6 AROUTE 7 AINDUS 8 AAUTR Figure 1 bis Donn es PSYSOC Analyse des correspondances repr sentation des variables sur les axes 1 et 3 Ces deux axes expliquent respectivement 44 33 et 14 96 de la variance totale Sur le graphique des variables figure 1 l axe 1 oppose les homicides aux d c s par cirrhose du foie
50. 8 pum ro20 OQ num ro2 0 3 Cas des donn es quantitatives 3 1 Coefficients de corr lation La plupart des coefficients de corr lation ont t cr s avec l intention de mesurer la ressemblance entre caract res Pour valuer la similitude entre individus ils devraient tre employ s avec circonspection Dans ce qui suit x 1 j d signe la valeur de la j me variable pour l objet i Les formules donnent selon l usage la corr lation entre variables il faudrait intervertir les r les des indices 1 et j pour obtenir la corr lation entre observations Coefficient de Bravais Pearson usuel s j j Xi Ix i 3 m 3 Ix i j 7m 3 1 s 3 s 3 m j et m j d signent les moyennes des variables j et j s j et s j d signent les carts types des variables j et j s2 j Ej Ix i j m 5 1 n Coefficient de rangs de Spearman 1904 En supposant que pour chaque variable j les valeurs ont t rang es par ordre croissant on d signe par RG j le rang de l observation 1 pour la variable j Sip 35 9 165 Rx DER 3519 ee Q3 Coefficient de rangs de Kendall 1938 Dans ce coefficient il faut pour chaque variable j comparer deux deux toutes les observations On pose R i 45 1 si x3 gt x i j R i i 0 si x i j x i j R i i 1 si x i j lt x i j Str j 2 Ba RAG i Ry i i na n 1 Remarque L avantage des coefficients de rangs est qu ils
51. ALGORITHMES DE CLASSIFICATION Maurice ROUX Professeur m rite Universit Paul C zanne Marseille France Avertissement Cet ouvrage a t publi aux ditions Masson Paris en 1985 Il est maintenant puis et nous mettons en acc s libre la pr sente version lectronique corrig e et am lior e La premi re version de cet ouvrage comportait la fin de chaque chapitre des programmes en langage Basic Applesoft qui sont maintenant obsol tes Ces programmes ont t convertis en Visual Basic for Applications utilisables avec le tableur EXCEL Microsoft Ils sont r unis dans le classeur AnaDon xls associ un mode d emploi inclus dans le fichier AnaDon doc lisible avec le traitement de textes WORD Microsoft A la fin de chaque chapitre de l ouvrage figurent les noms des proc dures de ce classeur trait es dans le chapitre Marseille Juin 2006 ALGORITHMES DE CLASSIFICATION Table des mati res CHAPITRE 1 Introduction la classification 1 But de la classification 2 Probl mes et m thodes de la classification automatique 3 Objectifs et plan de l ouvrage 4 Domaines d application et points de vocabulaire CHAPITRE 2 Exemples de donn es 1 Psychologie et soci t Psysoc 2 Phytosociologie Phytos CHAPITRE 3 Pr paration des donn es Calcul des distances 1 G n ralit s 1 1 Donn es quantitatives exemple des causes de d c s Psysoc 1 2 Pr traitement par l
52. Potentilla aurea L 100 144 Sempervivum arachnoideum 76 72 Geum montanum 73 On a d j vu en effet que l esp ce 117 est absente du groupe PAc n ud 30 alors qu elle est pr sente partout ailleurs nceud 29 A l inverse l esp ce 144 est quasi exclusive du groupe PAc tandis que l esp ce 72 en est presque totalement absente Sautant le noeud 30 qui subdivise le groupe PAc on peut analyser de la m me fa on le n ud num ro 29 pour lequel ressortent les esp ces 11 Antemnaria divica 100 69 Gentiana nivalis 66 82 Homogyna alpina L Cass 66 95 Luzula sysicata L DC 66 129 Sapina glabra Willd Fewyl 66 159 Trifolium pratense L 66 165 Veronica alionci Vill 66 L esp ce 11 est totalement absente du groupe PAn n ud 20 alors qu elle est dans tous les relev s des groupes PAcnl et PAcn2 qui forment le noeud 27 Les esp ces 82 95 129 159 caract risent le groupe PAn bien qu elles n en soient pas exclusives L esp ce 165 est absente de ce groupe et pr sente dans la plupart des relev s du noeud 27 Enfin pour le n ud 27 qui s pare les deux groupes PAcnl n ud 26 et PAcn2 n ud 25 on rel ve les esp ces 55 Elyna sp 100 151 Salix herbacea 100 4 Proc dures de calculs Pour les contributions aux noeuds d une hi rarchie les proc dures CTRHqual et CTRHquan sont disponibles la premi re s applique des variables qualitatives et la seconde aux variables quantitatives Pour les contri
53. ages indiscutables Supposons que l on veuille par exemple construire une hi rarchie L une des mani res de bien poser le probl me pourrait tre de choisir un crit re valuant la fid lit de la repr sentation hi rarchique au tableau initial des donn es et de trouver ensuite un algorithme construisant la hi rarchie la meilleure au sens de ce crit re Malheureusement on ne sait pas faire cela sauf pour des chantillons tr s petits ou pour des crit res sans int r t La solution qui consiste examiner l ensemble de toutes les hi rarchies possibles pour en retenir la meilleure se heurte au mur de la complexit combinatoire Le nombre de hi rarchies croit en effet si vite avec le nombre d objets que m me avec de puissants ordinateurs il n est pas r aliste de vouloir les envisager toutes C est pourquoi l on a recours des heuristiques c est dire des algorithmes dont on consid re qu ils sont suffisamment raisonnables vous donner des r sultats satisfaisants Grossi rement on peut distinguer trois grands types parmi ces heuristiques Il y a d abord les algorithmes construisant une hi rarchie par agr gations successives d objets puis de groupes en fonction des distances entre objets ou groupes On les appelle Constructions ascendantes de hi rarchies en abr g CAH A l inverse les Constructions descendantes de hi rarchies en abr g CDH proc dent par dichotomies successives Dans celles ci l ensemble tout
54. analyse factorielle 1 3 Variables qualitatives et mixtes 2 Application aux exemples 2 1 Causes de d c s Psysoc 2 2 Phytosociologie Phytos 3 Les proc dures de calcul de distances CHAPITRE 4 La classification ascendante hi rarchique 1 G n ralit s Lbs 1 2 1 3 Comparaison des agr gations par le saut minimum et par le diam tre 2 Application aux exemples 2 1 Causes de d c s Psysoc 2 2 Phytosociologie Phytos Principe g n ral des constructions ascendantes Propri t s des formules l mentaires de recalcul 3 Les proc dures de constructions ascendantes de hi rarchies CHAPITRE 5 Agr gation autour de centres mobiles 1 Principes et probl mes 1 1 L algorithme des centres mobiles 1 2 Moment d ordre deux d une partition 1 3 Avantages et inconv nients de la m thode 2 Application l exemple Psysoc 2 1 Partition en trois classes 2 2 Partition en quatre classes 3 Les programmes de calcul de centres mobiles CHAPITRE 6 Hi rarchie du moment d ordre deux 1 Principe et probl mes 2 L algorithme des voisins r ciproques 3 Application l exemple Psysoc 4 Proc dure de calcul CHAPITRE 7 Classification descendante hi rarchique 1 Introduction 2 M thodes bas es sur une variable particuli re 2 1 Utilisation de l une des variables des donn es 2 2 Utilisation des variables principales ou axes factoriels 3 M thodes bas es sur des individus particuliers 3 1 S lec
55. ant elles commencent par le haut de l arbre c est dire par la partie sur laquelle repose essentiellement l interpr tation Malheureusement les simplifications drastiques qu elles exigent pour maintenir des temps de calcul raisonnables font que les r sultats obtenus sont souvent d cevants Cependant les dichotomies bas es sur des variables bien choisies ont l avantage d tre rapides et de fournir des interpr tations ais es Elles permettent donc de traiter facilement de tr s grands jeux de donn es avec peu de variables 7 Proc dure de calcul La proc dure CDHLM dans le classeur AnaDon xls r alise la construction descendante d crite au paragraphe 3 3 Chapitre 8 Aides pour l interpr tation des classifications Lorsque par l une des m thodes des chapitres pr c dents on a obtenu une classification des objets on souhaite en g n ral savoir quelles sont les variables responsables de tel ou tel regroupement C est ce probl me que l on va tudier dans le pr sent chapitre en s parant comme il se doit le cas de variables quantitatives de celui des variables qualitatives 1 Variables quantitatives On a vu au chapitre 5 quation 5 3 que le moment d ordre deux d un solide peut se d composer en moment intra classe et moment inter classe Ce dernier qui est ce qu on appelle le moment d ordre deux d une partition repr sente la dispersion des centres de gravit dans laquelle on tient compte des masses
56. aphe 2 Ce probl me peut en effet tre consid r comme la recherche de l ultram trique la plus proche de la m trique donn e Par proche nous entendons ressemblante au sens d un certain crit re donn l avance Malheureusement l ensemble des m triques n a pas la structure d un espace vectoriel et le sous ensemble des ultram triques ne peut donc pas avoir de propri t remarquable comme par exemple celle d tre un sous espace ou un convexe sous ensembles sur lesquels on sait abaisser une perpendiculaire Cependant nous verrons au paragraphe 2 que pour un crit re assez fruste Relation d ordre et pour une classe particuli re d ultram triques Ultram triques inf rieures il existe une solution optimale 2 Une ultram trique particuli re la sous dominante N B Dans ce paragraphe l abr viation J J S renvoie l article de Jardine C J Jardine N et Sibson R 1967 2 1 Relation d ordre sur les m triques D finition 1 J J S Soit un ensemble fini I muni de deux m triques d et d On dira que d est inf rieure d si pour tout couple de points i j I on a d 1 j lt d 1 j On v rifie facilement que c est une relation d ordre sur l ensemble des m triques sur I Remarque 1 Une m trique peut tre inf rieure une autre et avoir la m me ordonnance mais ce n est pas toujours le cas on peut avoir une m trique inf rieure une autre mais n ayant pas la m me ordonnance et l on peut avoi
57. aration des donn es traitement interpr tation des r sultats De plus il arrive souvent que l interpr tation fasse apparaitre des redondances de variables ou l h t rog n it de l chantillon ce qui am ne modifier le tableau initial et r it rer le processus complet Bien que chacune de ces phases que nous allons r examiner plus loin pose ses probl mes propres elles ne peuvent tre totalement dissoci es les unes des autres et elles doivent tenir compte de l objectif global Celui ci peut selon nous tre de deux sortes Ou bien le but est d obtenir une taxinomie de qualit ou bien la classification n est qu une tape pr liminaire destin e r duire la taille des donn es ou trouver des sous chantillons homog nes en vue de l application d une autre m thode statistique analyse factorielle r gression multiple Rappelons les principaux probl mes qui se posent et comment on peut les r soudre en fonction de ces objectifs globaux 1 Taxinomie de qualit Si l on recherche avant tout la qualit des r sultats on s orientera plut t vers la classification ascendante hi rarchique qu on pourra ventuellement am liorer apr s troncature par une agr gation autour de centres mobiles cf chapitre 9 1 1 Pr paration des donn es La pr paration consistera essentiellement calculer une distance entre les objets classer La formule retenir d pendra de la nature des donn es qualitatives
58. artitions de q en 2 classes ou bipartitions on dit qu une bipartition est induite par 1 et i tous deux l ments de q si elle est form e de la fa on suivante C 1 est le sous ensemble de q dont tous les l ments sont plus proches de i que de 1 et de fa on analogue C i a tous ses l ments plus proches de 1 que de 1 Le crit re pour d cider qu une classe q sera scind e en deux est bas sur la distance moyenne inter classe M qjui np E k CG kt e CG d kk Dans cette formule n et n d signent les effectifs des deux groupes C i et C 1 respectivement L algorithme se d roule comme suit a Mise l tat initial Au d but tous les objets appartiennent la m me classe b A chaque tape on a une partition Q de l ensemble des objets Pour toutes les classes q de Q d effectif sup rieur ou gal 2 on calcule le crit re Crit q Maxi q M q 1 1 c On subdivise la classe q qui maximise ce crit re Crit q Max q e Q Crit q d S il reste des classes 2 l ments ou plus on retourne en b sinon on arr te Dans une version pr c dente de ce travail Roux 1985 nous avions envisag un crit re de scission bas sur la variance des distances inter groupe comme Edwards and Cavalli Sforza 1965 ou Fages 1978 mais les r sultats obtenus taient de qualit moyenne et nous avons abandonn ce crit re A chaque scission cette facon de proc der conduit examiner au
59. butions aux classes d une partition on a de la m me fa on les proc dures CTRPqual et CTRPquan Chapitre 9 Pratique de la classification Sans chercher tre exhaustifs nous avons jusqu pr sent examin les m thodes typologiques les plus courantes En tudiant leurs principes et leurs propri t s on a not au passage que chacune d elles poss de souvent plusieurs variantes L utilisateur novice est donc confront un choix difficile qui doit tre subordonn la nature des donn es et l objectif qu il poursuit C est ce qu on examinera au paragraphe 1 En outre il est possible d utiliser successivement deux algorithmes l un affinant les r sultats de l autre De telles strat gies seront envisag es au paragraphe 2 Enfin quelques r gles l mentaires d interpr tation des r sultats seront tablies au paragraphe 3 et deux algorithmes auxiliaires seront d crits au paragraphe 4 1 Choix d un algorithme Le choix est faire entre quatre grandes m thodes hi rarchiques ascendantes trois agr gations l mentaires et l agr gation suivant le moment d ordre deux une m thode hi rarchique descendante et une m thode non hi rarchique dite agr gation autour de centres mobiles Dans la suite on d signera ces algorithmes par leur nom g n rique CAH pour les constructions ascendantes CDH pour la construction descendante et CENMOB pour la partition par agr gation autour de centres mobiles 1 1 Dimensions
60. che des classes naturelles dans le domaine tudi 2 Probl mes et m thodes de la classification automatique Dans cet ouvrage il sera beaucoup question d algorithmes Rappelons qu un algorithme est la description minutieuse de toutes les op rations effectuer pour obtenir la solution concr te d un probl me Ainsi on peut parler de l algorithme permettant de trouver la racine carr e d un nombre ou bien pour obtenir le plus grand commun diviseur de deux nombres entiers etc Il ne faut pas confondre algorithme et programme informatique il peut y avoir plusieurs fa ons de programmer un m me algorithme L un des plus grands classificateurs a sans aucun doute t le savant su dois Linn qui au 18 me si cle a tabli une classification du monde vivant en g n ral et du r gne v g tal en particulier classification encore en vigueur aujourd hui chez les sp cialistes des sciences naturelles La premi re moiti du 20 me si cle a vu un certain nombre de tentatives pour rationaliser le processus mental utilis par Linn Mais ce n est qu partir des ann es 1960 avec la diffusion de l informatique en milieu universitaire que sont apparus un grand nombre d algorithmes automatisant compl tement la construction des classifications Williams and Lambert 1959 Sokal and Sneath 1963 Cependant aujourd hui encore le support math matique de ces m thodes reste embryonnaire et ne permet pas d lire un algorithme aux avant
61. d ne sont pas ind pendants voir d but paragraphe 2 il ne s agit donc que d une sym trie d criture La plupart de ces indices d crits dans le tableau 2 s obtiennent partir de leur homologue colonne H du tableau pr c dent o d est introduit de facon naturelle Compte tenu que la valeur moyenne de d est gale n p n q n on en d duit facilement les valeurs moyennes de ces indices Nous signalerons dans la Note num ro 10 les valeurs remarquables de ces moyennes Voici quelques commentaires sur ces indices Note 6 Les trois premiers indices du tableau num ros 11 12 et 13 donnent la m me ordonnance car ils sont tous trois fonctions d croissantes de n c d Note 7 Nous avons construit les indices num ro 17 et 18 par analogie avec les formules num ro 8 et 9 du tableau 1 Note 8 La valeur maximum n de l indice num ro 18 est atteinte pour c d p q n 1 on suppose en effet que tout objet poss de au moins un attribut et au plus n 1 Note 9 Si s est l indice de Sokal et Michener num ro 11 et si s d signe le coefficient num ro 19 alors on a s 2s 1 Les propri t s de s se d duisent donc facilement de celles de s outre que ces deux coefficients ont m me ordonnance No Auteurs Formule Etendue TI Sokal amp Michener 1958 c d n 0 1 12 Sokal amp Sneath 1 1963 2 c dou d 0 13 Rogers amp Tanimoto 1960 c d
62. d sur I x I induit une ordonnance de la facon suivante i i j j si et seulement si d i i d j j Un tel pr ordre qui est alors total claire la remarque 3 deux paires d objets peuvent pr senter le m me niveau de dissemblance sans pour cela tre identiques Nous insistons sur cette notion d ordonnance car nous avons constat empiriquement et R N Shepard 1962 a montr que sa seule connaissance suffit g n ralement pour reconstruire le nuage donn une homoth tie pr s avec une approximation d autant meilleure que la dimension r elle du ph nom ne tudi est petite relativement au nombre d observations Autrement dit deux nuages de points ayant des ordonnances voisines auront des structures analogues m me si les valeurs respectives des distances sont assez diff rentes 2 Cas des donn es binaires Soient 1 et i deux objets quelconques de I ils sont repr sent s par deux vecteurs bool ens n composantes si n est le nombre total d attributs possibles i Xip X2 y hay Xa Lite Qt Xle aaar R a Pour tout k xx respectivement x ne peut valoir que 0 ou 1 suivant que le caract re k est pr sent ou absent chez l individu i respectivement 1 Dans la suite nous utiliserons les nombres suivants p EE x k 1 2 n q 2 xs Ke i 2 42 p respectivement q est donc le nombre d attributs poss d s par 1 respectivement 1 Nous appellerons c le nombre d attributs poss d
63. dans lequel on place les objets en bas d un arbre hi rarchique est assez arbitraire puisqu on peut faire pivoter un groupe sur lui m me autour de son noeud Autrement dit la proximit horizontale ne veut rien dire seuls les niveaux de liaison sont prendre en compte et ceux ci indiquent g n ralement des distances moyennes entre les groupes non entre les individus sauf aux niveaux inf rieurs 2 Classification en tant que pr traitement Le traitement de grands ensembles de donn es dans le but de r duire leur taille pose plut t moins de probl mes Il exclut toutes les m thodes n cessitant la gestion de la matrice des distances en m moire centrale Il ne reste donc que la classification ascendante hi rarchique du moment d ordre deux programm e selon la m thode des voisins r ciproques chapitre 6 ou bien l agr gation autour de centres mobiles chapitre 5 Toutefois un arbre hi rarchique portant sur des milliers d individus est difficile examiner et interpr ter La m thode de choix est donc l agr gation autour de centres mobiles 2 1 Pr paration des donn es Les deux m thodes envisageables traitent exclusivement des donn es quantitatives Si l on a des donn es qualitatives on devra donc obligatoirement passer par l nterm diaire de l Analyse factorielle des correspondances sur le tableau des donn es transform es en 0 1 cette analyse r alise en effet une sorte de quantification des donn es sur les
64. des donn es Le lecteur aura d j remarqu que certains algorithmes n cessitent une taille de m moire centrale plus importante que d autres contrainte qui est primordiale lorsqu on travaille sur un micro ordinateur Deux cat gories d algorithmes se distinguent ais ment ce sujet d une part ceux qui manipulent des distances les trois CAH l mentaires et CDH d autre part ceux qui travaillent directement sur les donn es brutes la CAH du moment d ordre 2 et CENMOB Les premiers g rent la matrice des distances en m moire centrale tandis que les seconds travaillent sur le tableau des donn es brutes L avantage va en g n ral aux seconds En effet supposons que l on ait un tableau de donn es ayant 200 individus et 15 variables ce qui est une disposition assez commune Le tableau des donn es occupera donc 200 15 3000 cases tandis que le tableau des distances n cessiterait 200 199 2 19900 cases En revanche si le nombre des variables est lev alors les algorithmes travaillant sur les distances sont sup rieurs Dans la version actuelle des proc dures Excel Juin 2006 la programmation est faite de mani re pouvoir occuper toute la m moire vive disponible Toutefois il est bon de savoir qu il y a des limites la dimension des tableaux que l on peut traiter En fait les programmes du type centres mobiles pourraient accepter des dimensions encore plus grandes avec des modifications mineures Il suffirait de ne pas
65. deux groupes De m me si deux points appartiennent au m me groupe s ou leur distance est inchang e Si i s et si i s leur distance avant agr gation est la m me que la distance d s s entre les deux groupes et elle est encore inchang e apr s agr gation Examinons le cas d un point u n appartenant ni s ni s et sa distance d u i un point i des Soit i un troisi me point appartenant s d tant ultram trique deux cas sont alors possibles triangles isoc les remarque 2 ci dessus Cas 1 d u i d u i gt di 1 Par hypoth se de r currence on a d u i lt d u i et d u i lt d u i donc d u i lt Min d amp a u i d amp a u i d u i Cas 2 d u i d i i gt d u i et le cas analogue d u i d i i gt du i Par hypoth se de r currence on a d i i d 1 1 et dia 1 1 d s s Or si on fusionne s et s c est parce que la distance entre ces deux groupes est la plus petite des distances intergroupes donc d s s lt d s s daa u i d o d u i d i i Min d amp a u i da amp a u i d amp u i Ainsi la propri t d lt d est vraie Mais comme d est la plus grande des ultram tr ques inf rieures 6 dk lt d ce qui entra ne dk d BIBLIOGRAPHIE Anderberg M R 1973 Cluster analysis for applications 359p Academic Press New York London Benz cri J
66. du Moment d ordre 2 Chapitre 7 Construction descendante d une hi rarchie 1 Introduction Les algorithmes de construction hi rarchique par agglom rations successives ou Constructions ascendantes hi rarchiques CAH sont juste titre les plus couramment utilis s Ils sont en effet rapides et l exp rience montre qu ils fournissent des r sultats coh rents Cependant leur mode de fonctionnement par agr gations successives partir des objets simples sugg re que les n uds les plus lev s de la hi rarchie sont probablement peu repr sentatifs Malheureusement c est g n ralement sur eux que repose l interpr tation des r sultats en effet l utilisateur interpr te habituellement la hi rarchie obtenue en examinant l arbre r duit ses seules branches principales Les m thodes bas es sur des dichotomies successives ou Constructions descendantes hi rarchiques CDH seraient plus satisfaisantes cet gard Ces m thodes partent de l ensemble entier de tous les objets celui ci est scind en deux parties qui sont leur tour scind es en deux etc jusqu ce que tous les sous ensembles obtenus soient r duits un objet unique Cependant ce type d algorithmes a eu peu de succ s jusqu pr sent cause des inconv nients majeurs qu il pr sente En effet pour obtenir de bons r sultats il faudrait examiner chaque tape toutes les dichotomies possibles pour n en retenir qu une celle qui optimise un crit re f
67. e ci constitue un ensemble de majorants d i i ie I i e 1 La famille des ultram triques inf rieures 5 est donc une famille born e Cette famille a donc une enveloppe sup rieure qui sera appel e ultram trique sous dominante de 6 ou plus bri vement la sous dominante de Proposition La construction ascendante hi rarchique du saut minimum fournit la sous dominante Nous reprenons ici la d monstration de Benz cri 1973 On appelle encore la distance initiale et d sa sous dominante On d signe par di dr dx les tats successifs de la distance d en cours de construction n tant le nombre d l ments de l ensemble I classer au d but ona d 6 Au pas h de l algorithme on suppose qu on forme le groupe a par fusion des deux groupes s et s A chaque pas de la construction le recalcul des distances fait que les nouvelles distances sont soit gales soit inf rieures aux distances de l tape pr c dente Par cons quent l ultram trique finale d est inf rieure la distance initiale L ultram trique construite est donc bien inf rieure 0 On va montrer maintenant par r currence que l ultram trique inf rieure maxima d est inf rieure l ultram trique construite par le saut minimum Au d but de l algorithme d lt d 8 On va donc montrer que si d lt ds1 alors d lt dy Si deux points n appartiennent ni s ni s alors leur distance n est pas modifi e par la fusion de ces
68. e classification usuelles D autre part certains auteurs pr f rent parler en termes de ressemblance et utilisent cette fin un indice de similitude s similarity index qui devra satisfaire des conditions analogues celles de d 1 Vier SE digas 2p M EL BST wed qc mute Smax est la valeur maximum que peut prendre s Smax Sup s i i ie i T elle d pend de la formule retenue vaut g n ralement 1 mais peut tre parfois infiniment grande Supposons s d fini sur I x I Si pour tout i et tout 1 de Ion pose de es eis a3 alors d sera un indice de distance Dans ce cas se donner l un ou l autre des types de mesure est quivalent puisqu on passe facilement de l un l autre Remarque 1 Certains auteurs n imposent pas la condition 1 c est dire que l on peut avoir s i 1 lt Smax ainsi que s i i s j j si i j D finition Sera reprise l annexe 2 Une ordonnance sur I est une relation de pr ordre sur Ix que l on notera lt On aura donc 1 r flexivit V i 1 l i i lt i i 2 transitivit i i j j et j j lt k k gt i i lt k k Remarque 2 Ce pr ordre peut tre non total c est dire que certaines paires peuvent ne pas tre comparables certaines autres Remarque 3 S agissant d un pr ordre on n a pas n cessairement i i 5 j et 3 j s 1 1 gt 3 3 1 1 Remarque 4 Un indice de distance
69. e hi rarchie Pour aider au d pouillement d une hi rarchie on dresse un tableau variables n uds donnant les contributions CTR j n de la variable j l cart entre les deux classes formant le n ud n La formule 8 4 fournit encore les valeurs cherch es mais l indice k n y peut prendre que deux valeurs correspondant aux deux classes en question L indice repr sente comme pr c demment les classes de la variable consid r e Et les effectifs ne prennent en compte que les objets appartenant au n ud n CTR j n Xe an bn Miei Cr ex ea m e ea m Dans cette formule an bn d signe l ensemble deux l ments form de l a n et du benjamin du n ud n Il faut aussi prendre garde que l effectif m est ici le nombre d objets impliqu s dans le nceud n et non l effectif total de tous les objets tudi s 3 Application aux exemples 3 1 Donn es PSYSOC quantitatives On a effectu les calculs de contributions en utilisant d abord la partition en trois classes que nous connaissons bien Classe 1 AUSTRI FRANCE WGERMA ITALY SPAIN PORTUG Classe 2 BELGIU SWEDEN SCOTLA NETHER ENGLAN ICELAN NORWAY SIRELA F INLAN SWITZE DENMAR lasse 3 NIRELA USA Il faut noter en passant que la fa on dont cette partition a t obtenue importe peu on recherche simplement quelles sont les variables initiales le
70. e pr sentent les distances Ainsi en commen ant par les plus petites d entre elles on a dans le premier cas distance du Khi deux sur donn es brutes d WGERMA AUSTR lt d NETHER ENGLAND lt d NORW SCOTL d ICELAN NORW 117 128 152 159 Dans le deuxi me cas distance euclidienne sur trois facteurs d WGERMA AUSTR lt d NETHER ENGLAND lt d ICELAN NORW lt d NORW SCOTL 54 67 119 145 L ordre des distances est approximativement le m me AUST FRAN PORT WGER BELG FINL SWED SWIT ITAL NIRE DENM ICEL FRANCE 361 PORTUG 388 440 WGERMA T17 322 412 BELGIU 322 347 510 338 FINLAN 570 638 882 565 417 SWEDEN 430 384 702 395 268 274 SWITZE 319 501 670 315 304 295 265 ITALY 438 453 222 456 630 968 770 749 NIRELA 1179 1184 1196 1208 1084 1079 1134 1184 1287 DENMAR 444 604 769 406 422 341 342 176 858 1267 ICELAN 717 664 909 745 443 435 451 574 1006 1094 675 SCOTLA 565 472 730 588 308 418 339 495 815 982 620 227 SPAIN 420 302 329 428 548 872 652 689 212 1260 812 874 NORWAY 610 538 829 627 363 356 318 474 904 1088 586 159 SIRELA 684 646 804 745 473 613 581 663 884 1044 808 288 NETHER 464 51 3 643 498 179 387 349 370 779 1048 476 332 ENGLAN 486 520 702 521 229 315 313 364 813 999 486 266 USA 658 731 730 683 663 717 720 TES 806 560 805 857 SCOT SPAI NORW SIRE NETH ENGL
71. e voisins r ciproques au lieu de la seule paire qui pr sente la plus petite distance On r duit ainsi le nombre d tapes accomplir et surtout on diminue consid rablement le nombre des distances recalculer Pour montrer la l gitimit de cet algorithme il suffit de montrer que dans l algorithme usuel les agglom rations successives de niveau inf rieur la distance qui s pare deux voisins r ciproques ne modifient pas la propri t de ces deux points d tre l un pour l autre le plus proche voisin Soient k et k une paire de voisins r ciproques et i et i la paire fusionner l tape consid r e Il n est pas possible d avoir agr ger i et k par exemple car d i k gt d k k donc d i k n est pas la plus petite des distances En supposant que la formule de recalcul satisfait la condition 6 3 on a apr s fusion d iUi k Min d i k d i k mais comme k et k sont voisins r ciproques on a il en r sulte que d k k d iUi k on montrerait de m me que diy kt y Qm deny Autrement dit la cr ation du groupe iUi ne change pas le fait que d k k est la plus petite des longueurs des segments issus de k ou de k Ainsi au fur et mesure que se d roule l algorithme l mentaire les niveaux d agr gation augmentent jusqu ce que d k k soit son tour la plus petite des distances En r sum la hi rarchie du moment d ordre deux peut se calculer en suivant l algorithme
72. efficient of divergence for use with multiple characters Copeia 2 61 64 Cramer P J 1946 Mathematical methods of statistics 575p Princeton University press Princeton Czekanowski J 1932 Coefficient of racial likeness und durchschnittliche differens Anthrop Anz 9 227 249 De Lagarde J 1983 Initiation l analyse des donn es 158p Dunod Paris De Rham C 1980 La classification hi rarchique selon la m thode des voisins r ciproques Cah Ana des donn es vol V no 2 135 144 Dice L R 1945 Measures of the amount of ecologic association between species Ecology 26 297 302 Diday E Lemaire J Pouget J Testu F 1982 El ments d analyse des donn es 462 p Dunod Paris Diday E 1971 La m thode des nu es dynamiques Rev Stat appliqu e vol XIX no 2 19 34 Edwards A W F and Cavalli Sforza L L 1965 A method for cluster analysis Biometrics 21 362 375 Escofier B et J Pag s 1990 Analyses factorielles simples et multiples 2 me dition Dunod Paris 266 p Estabrook G F 1967 An information theory model for character analysis Taxon 16 86 97 Everitt B 1974 Cluster analysis 122 p Heinemann Educational Books London Fages R 1978 La notion de dispersion en classification automatique Communication aux Journ es de Statistique Nice 22 26 Mai 1978 F nelon J P 1981 Qu est ce que l analyse des donn es 311 p Ed Lefonen 26 rue des Cordeli res 750
73. entres mobiles Examinons ce que devient le moment intra classe W au cours du d roulement de l algorithme Dans la phase de r affectation des objets appelons q la classe reconstitu e autour du centre de gravit g de l ancienne classe q W geo Die q mi d i Ja Appelons S la valeur de W apr s r affectation des points i au centre de gravit le plus proche S sqeo sie gt mi Q i gg Soit 1 un l ment de la classe q Si 1 n a pas chang de classe sa contribution au moment intra classe reste la m me Mais s il provient d une autre classe q alors c est qu il est plus proche de g que de gy donc d i g lt d i gy et sa contribution S est inf rieure celle qu il avait dans W Il en r sulte que S W Remarquons que S n est plus la somme des moments centr s puisque les g ne sont plus les centres de gravit des classes q Consid rons alors la valeur W du moment intra classe de la nouvelle partition W Ygeo0 Die aq mi A i ge Cette fois on prend en compte les moments centr s qui sont d apr s le th or me de Huyghens inf rieurs aux moments non centr s Donc W S Il en r sulte qu la fin de cette tape le moment intra classe W est inf rieur ce qu il tait la fin de l tape pr c dente et la nouvelle partition est donc meilleure que la partition pr c dente Cela ne veut pas dire pour autant que la partition finale de l algorithme des centres mobiles soit la meilleure partition possib
74. es sur l ensemble d observations initial Une telle hi rarchie peut avantageusement tre r sum e par un arbre hi rarchique figure 1 dont les n uds m n p q symbolisent les diverses subdivisions de l chantillon les l ments de ces subdivisions tant les objets a b c d e plac s l extr mit inf rieure des branches qui leur sont reli es Figure 1 Exemple d arbre hi rarchique portant sur cinq objets a b c d e Les points m n p q sont les n uds de l arbre Le trait horizontal mixte indique un niveau de troncature d finissant une partition en trois classes Le niveau des n uds qui est le plus souvent chiffr est sens indiquer un degr de ressemblance entre les objets correspondants Ainsi sur notre figure 1 les objets a et d se ressemblent plus que les objets c et e Remarquons en passant que si on coupe cet arbre un niveau interm diaire entre n et p on obtient une partition en trois classes de l ensemble tudi savoir les parties a d b fc e En faisant varier ce niveau de troncature on obtient les diverses partitions constituant la hi rarchie On voit qu il ne faut pas confondre classification et classement Dans un classement on affecte les objets des groupes pr tablis c est le but de l analyse discriminante que de fixer des r gles pour d terminer la classe des objets La classification est donc en quelque sorte le travail pr liminaire au classement savoir la recher
75. es o la pr sence des attributs joue un r le pr pond rant 2 2 Indices o les pr sences et absences d attributs jouent des r les quivalents 3 Cas des donnees quantitatives 3 1 Coefficients de corr lation 3 2 Mesures de distances 4 Conclusion ANNEXE 2 Hi rarchies et ultram triques 1 G n ralit s 1 1 Hi rarchie et ordonnance 1 2 Hi rarchie indic e et ultram trique 2 Une ultram trique particuli re la sous dominante 2 1 Relation d ordre sur les m triques 2 2 Ultram trique sous dominante d une m trique donn e BIBLIOGRAPHIE INDEX Chapitre 1 Introduction la classification 1 But de la classification Comme les autres m thodes de l Analyse des donn es dont elle fait partie la Classification a pour but d obtenir une repr sentation sch matique simple d un tableau rectangulaire de donn es dont les colonnes suivant l usage sont des descripteurs de l ensemble des observations plac es en lignes L objectif le plus simple d une classification est de r partir l chantillon en groupes d observations homog nes chaque groupe tant bien diff renci des autres Le plus souvent cependant cet objectif est plus raffin on veut en g n ral obtenir des sections l int rieur des groupes principaux puis des subdivisions plus petites de ces sections et ainsi de suite En bref on d sire avoir une hi rarchie c est dire une suite de partitions emboit es de plus en plus fin
76. es voisins r ciproques est bas sur la propri t suivante Soient i et i les deux objets ou groupes fusionn s une tape quelconque de l algorithme usuel et k un troisi me objet ou groupe d iUi k 2 Min d i k d i k 6 3 Cette criture revient dire que la formule de recalcul des distances est telle que toute distance recalcul e est plus grande que la plus petite de celles qu elle remplace Cette propri t est v rifi e par les trois formules l mentaires examin es au chapitre 4 Montrons que cela est encore vrai pour la formule 6 2 ci dessus En effet on remarque tout d abord que puisque i et i sont agr g s ona d i i d i k et d i i lt d i k Donc en rempla ant d i 1 par d i k ou par d i k on diminue la valeur de l expression de droite de 6 2 Supposons maintenant que d 1 k soit inf rieur ou gal d i k alors en rempla ant d i k par d 1 k le terme de droite dans 6 2 est rendu encore plus petit que sa vraie valeur mais ces deux remplacements rendent ce terme gal d i k qui est donc inf rieur ou gal d 1Ui k Il en serait de m me si d i k tait inf rieur d i k On montre que dans ce cas deux objets qui sont voisins r ciproques constituent n cessairement un n ud de la hi rarchie quelle que soit la distance qui les s pare On profite alors de cette observation pour agr ger chaque tape de l algoritnme toutes les paires d
77. ette strat gie apporte en outre un avantage suppl mentaire Elle transforme un grand nombre de variables qualitatives en un petit nombre d axes factoriels qui peuvent tre consid r s comme des variables quantitatives et par suite les quatre grands types d algorithmes sont applicables 3 Interpr tation des r sultats On a vu au chapitre 8 qu un certain nombre de calculs suppl mentaires facilitent l interpr tation des r sultats mais nous voulons parler ici d un autre probl me Il s agit du fait que quelles que soient les donn es les algorithmes de classification fournissent toujours une typologie On congoit pourtant que certains chantillons tr s homog nes pouvant tre consid r s comme issus d une population unique ne devraient pas donner lieu une taxinomie Dans le cas d une classification hi rarchique quelques r gles permettent a posteriori d estimer la classifiabilit des donn es Figures la et 1b Les deux formes d arbres extr mes en classification hi rarchique Deux formes d arbres extr mes peuvent se pr senter qui sont sch matis es dans les figures 1a et 1b ans le premier cas les deux objets les plus proches constituent le noyau auquel viennent se raccrocher progressivement tous les autres objets Dans le second cas au contraire se distinguent clairement des groupes bien individualis s reli s des niveaux lev s par rapport aux distances intra groupes L intuition sugg re que dans
78. gorithme est peu exigeant sur les propri t s de la distance initiale qui peut tre obtenue par des formules sp ciales cf annexe 1 ne satisfaisant pas forc ment aux axiomes usuels des distances 1 2 Propri t s des formules l mentaires de recalcul Propri t 1 Transformation monotone des distances initiales Soit d i 1 la distance initiale entre les objets i et i Une transformation monotone de ces distances est une modification de d que nous appellerons d qui conserve l ordre entre les distances C est dire que d r YS Og Se OE aay ESO n o En particulier toute fonction croissante de d a cette propri t Si l on applique une telle transformation aux distances initiales il est clair que l arbre hi rarchique va tre modifi Cependant dans le cas de l agr gation par le diam tre ou par le saut minimum les noeuds successifs vont regrouper les m mes objets tout au long de l algorithme Autrement dit les niveaux de regroupement changent mais la structure de l arbre hi rarchique est invariante Ceci relativise la question du choix de l indice de distance cf annexe 1 Cette propri t n est pas vraie pour l agr gation par la distance moyenne Propri t 2 Extr malit de la hi rarchie du saut minimum Lorsqu on a construit une hi rarchie par l un des trois proc d s ci dessus on peut en d duire une nouvelle valuation d de la distance entre deux objets i et i On d cide pour cela que la distance d i
79. hi deux ou Khi carr Lambert J M Lance G N Lerman I C Linn M trique distance voir ce mot Moment d ordre deux Moment inter classe Moment intra classe Niveau d agr gation Noeud C3 1 c3 3 a1 3 a1 c4 1 c4 1 3 c7 3 3 b c3 1 c5 1 3 c5 2 2 c1 c3 1 2 b c2 2 b c3 1 2 c2 1 c1 2 c4 c7 c4 3 a2 1 c8 2 C9 2 1 c9 4 c10 1 c 3 2 b c5 1 2 b a1 a1 c1 2 c3 1 2 C8 c10 1 C4 1 c7 4 C3 1 3 a1 2 b c4 1 c6 1 b a2 2 b C3 1 c3 2 c7 2 1 c8 3 c9 2 3 a1 3 2 C7 c8 2 a1 3 2 b ai 4 b c1 2 c5 1 c6 c8 1 c5 1 2 c6 c8 1 c5 1 2 c6 c8 1 c1 c4 c6 2 c9 2 1 c1 c4 c6 3 c7 22 Nu es dynamiques Voir Agr gations autour de Centres mobiles Ordonnance Ordre sur les distances Partition Choix d une partition initiale Interpr tation Obtenue par troncature Recherche d une partition Phi PHYTOS exemple de donn es Phytosociologie Pond ration des distances Psychologie PSYSOC exemple de donn es Recalcul des distances Roux G a1 1 a2 1 1 a2 2 1 c5 1 c5 2 1 C8 1 1 c8 2 1 C9 2 1 c10 1 c5 1 a1 2 c2 2 c3 2 2 c4 2 2 c7 5 2 c8 3 2 c2 2 c3 1 3 c3 2 2 b c4 1 1 c1 4 c2 1 C2 1 c3 1 1 c3 2 1 c4 2 1 c5 2 c6 3 c7 5 1 c8 3 1 C4 1 1 c4 1 2 c6 1 c6 2 c7 4 a2 2 2 c2 2 a1 2 1 b Roux M C3 1 2 c7 3 3 a1 2 2 a1 2 2 a2 1 2 b Segmentation c1 4 b s lection d objets c7 3 de va
80. ient d examiner d abord la colonne Khi deux pour d terminer les esp ces les plus importantes On remarque les esp ces suivantes valeur du Khi deux entre parenth ses 117 Potentilla aurea 16 131 Salix herbacea 16 144 Sempervivum arachnoideum 12 5867 129 Sagina glabra Wild 12 4444 72 Geum montanum 11 7333 82 Homogyne alpina 11 7333 159 Trifolium pratense L 11 7333 Un retour sur le tableau des donn es chapitre 2 nous permet de constater que l esp ce 117 est absente de la classe 4 et pr sente partout ailleurs Au contraire l esp ce 131 n est pr sente que dans la classe 2 Ceci confirme que le crit re bas sur le Khi deux attribue autant d importance l absence qu la pr sence d une esp ce L esp ce 144 est une caract ristique de la classe 4 quoiqu elle apparaisse une fois ailleurs De m me pour l esp ce 129 caract ristique du groupe 3 mais qui apparait une fois dans un autre relev le num ro 54 L esp ce 72 se distingue parce qu elle est pr sente partout sauf dans la classe 4 encore que l un des relev s de cette classe la poss de On pourrait continuer ainsi l examen des esp ces par ordre des coefficients de liaison d croissants On voit que ces calculs auxiliaires font clairement apparaitre les variables discriminant les diff rents groupes CL 1 CL 2 CL 3 CL 4 TOTAL KHI 2 D D L 1 38 63 563 338 1000 1 7778 3 2 64 16 458 462 1000 8 4148 3 5 159 58 624
81. ix l avance Mais la scission en deux d un groupe n objets demande l examen de anl bipartitions ce qui requiert des calculs prohibitifs comme l avaient d j remarqu Edwards et Cavalli Sforza d s 1965 sans fournir de solution M me si l examen d un aussi grand nombre de bipartitions tait techniquement r alisable la hi rarchie obtenue n optimiserait pas pour autant un crit re global d ajustement aux donn es mais les dichotomies ainsi obtenues pourraient sans doute tre plus facilement interpr tables Pour viter l examen exhaustif de toutes ces dichotomies les auteurs de tels algorithmes ont eu recours des simplifications que nous regroupons en trois grandes cat gories m thodes bas es sur le choix ou la construction d une variable particuli re m thodes bas es sur un ou plusieurs individus formant les embryons des sous ensembles m thodes bas es sur la th orie des graphes Bien que les m thodes utilisant la th orie des graphes soient tr s en vogue actuellement Juin 2006 elles n cessitent quelques d veloppements qui d passent le cadre de cet ouvrage Nous nous limiterons ici aux deux premi res cat gories de m thodes Un autre probl me ennuyeux r side dans le calcul des niveaux de jonction entre les branches de la hi rarchie selon la formule utilis e ces niveaux peuvent pr senter des inversions rendant impossible la repr sentation de l arbre hi rarchique associ la classificati
82. l pour cette variable en dessous de ce seuil les objets seraient rang s dans l une des sous classes au dessus de ce seuil les objets seraient affect s l autre sous classe Toutefois une telle proc dure pr senterait les m mes avantages et les m mes inconv nients que celle de Williams et Lambert 2 2 Utilisation des directions principales ou axes factoriels Plusieurs auteurs ont propos des m thodes de ce type citons par exemple Reinert 1983 Boley 1998 et Chavent et al 1999 Le principe g n ral consiste calculer pour les seuls objets de la classe C scinder la premi re direction principale de ce sous ensemble Cette direction est la premi re composante principale s il s agit de variables quantitatives continues ou bien le premier axe factoriel de l Analyse des Correspondances si les variables initiales sont qualitatives ou si elles repr sentent des comptages homog nes En g n ral les coordonn es des objets sur les directions principales sont centr es de sorte que l origine constitue le seuil naturel comme point de scission les objets de coordonn es n gatives sont mis dans l une des sous classes ceux de coordonn es positives sont affect s l autre sous classe Il est possible cependant d adopter une autre valeur seuil pour optimiser par exemple la variance inter classe Les r sultats obtenus par de telles m thodes sont videmment meilleurs que ceux de l algorithme de Williams et Lambert puis
83. lativement la dispersion de la classe c est dire la somme de ces quantit s pour toutes les variables la classe tant fix e Le second tableau d nomm contributions des classes aux variables fournit en pourcentages galement le rapport de la contribution la dispersion de chaque variable c est dire la somme des contributions pour toutes les classes et pour une variable fix e Si l on s int resse l interpr tation des classes c est donc le premier tableau qu il faudra examiner Au contraire si une ou plusieurs variables ont un r le important il vaudra mieux tudier le second tableau 1 2 Interpr tation d une hi rarchie Lorsqu on a tabli une hi rarchie sur un ensemble I d objets on d sire en g n ral savoir quelles sont les variables de l ensemble J d terminantes pour la formation de chaque n ud de l arbre Dans le cas de variables quantitatives comme pr c demment on examine le r le jou par chaque variable dans le carr de la distance d g g entre les centres de gravit des deux classes q et q constitutives de chaque n ud d Jar Ja X35 Gg 3 Jar 4 8 2 C est donc la quantit g j g j qu on appelle contribution de la variable j au n ud consid r Et le programme de calcul fournira un tableau dont les lignes sont les noeuds successifs de la hi rarchie et dont les colonnes repr sentent les variables Dans ce tableau les contributions seront rapport es le
84. le relativement aux classes Ainsi on peut dire que les Cirrhoses sont des taux tr s voisins les uns des autres pour les pays de la classe 1 alors que ces taux sont plus dispers s pour la classe 2 Autrement dit les taux lev s de Cirrhose sont beaucoup plus caract ristiques de la classe 1 que ne le sont les taux faibles pour la classe 2 Nous allons examiner maintenant la hi rarchie ascendante de la distance moyenne obtenue on prenant pour distance initiale la distance du Khi deux sur les donn es brutes Les contributions des variables aux noeuds de la hi rarchie sont d crites au tableau 3 dont les lignes repr sentent les n uds de la hi rarchie et dont les colonnes sont les variables SUI HOM ARO AIN AAU CIR 20 5 0 53 3 22 17 21 5 0 76 1 11 6 22 40 7 24 1 1 21 23 7 0 19 6 56 12 24 2 1 26 0 31 41 25 10 0 23 0 47 20 26 1 0 43 0 1 55 27 36 2 9 3 0 49 28 4 0 75 0 7 14 29 57 0 10 2 30 0 30 1 1 1 0 93 4 31 7 0 5 1 70 16 32 9 0 6 1 82 2 33 46 0 2 0 52 0 34 88 0 0 0 0 12 35 28 5 0 0 10 93 36 0 0 9 0 0 90 37 18 63 2 0 2 15 Tableau 3 Contribution des variables aux n uds de la Hi rarchie ascendante du lien moyen La difficult pour interpr ter ce tableau provient de ce qu il est n cessaire d identifier les noeuds Pour cela il faut se reporter la description de la hi rarchie telle qu elle figure au chapitre 4 En fait seuls les nceuds les plus hauts de la hi rarchie sont r ellement utiles c est pourquoi nous
85. le en k classes En effet la partition finale d pend de la partition initiale Une autre partition initiale peut donc donner une partition finale pour laquelle le crit re du moment d ordre deux soit encore meilleur On r sume cela en disant qu on obtient un optimum local du crit re et non un optimum absolu 1 3 Avantages et inconv nients de la m thode L algorithme des centres mobiles contrairement de nombreuses m thodes classificatoires a l avantage d optimiser un crit re simple de dispersion savoir le moment d ordre deux d une partition Cependant comme on vient de le voir on n a pas la certitude d obtenir un optimum absolu c est dire la meilleure solution L un des moyens g n ralement pr conis s cf Diday 1971 pour obtenir des r sultats valables est d ex cuter plusieurs fois l algorithme complet avec des partitions initiales diff rentes On peut alors retenir la partition finale associ e au moment intra classe le plus petit qui n est pas pour autant le minimum absolu ce que l on ne sait pas d terminer Cependant une autre strat gie est de proc der l examen des formes fortes Celles ci sont constitu es des sous ensembles d objets qui ont toujours t r unis dans la m me classe finale au cours des diff rents essais de partitions initiales Ces formes fortes repr sentent donc des groupes homog nes et mettent en relief les objets d attribution ind cise qui n appartiennent aucune forme forte L tude
86. le pour laquelle la somme de ses Khi deux est maximum La m thode de Williams et Lambert est bien adapt e au traitement de tableaux pr sentant un grand nombre d observations et peu de variables qualitatives ou questions La table des Khi deux de contingence entre variables est alors rapide obtenir par comparaison au temps qu il faudrait pour calculer par exemple la matrice de Jaccard relative aux individus En outre chaque noeud de la hi rarchie est attach par construction le nom d une variable ce qui facilite l interpr tation tous les individus associ s une m me branche r pondent de la m me fagon toutes les questions variables qui ont abouti la cr ation de cette branche Malheureusement les r sultats sont en g n ral grossiers Cela tient au fait que les groupes d individus se d finissent rarement par leurs r ponses strictement identiques une s rie de questions mais bien plutot par un pourcentage lev de r ponses semblables sur l ensemble des questions Notons encore que les niveaux des n uds de la hi rarchie ne sont plus d finis que par l ordre dans lequel ils apparaissent et il n est pas naturel de leur associer un indice montrant la coh sion du groupe d objets associ s ce n ud On pourrait imaginer un programme semblable travaillant sur des variables quantitatives Il y faudrait ajouter une tape suppl mentaire une fois choisie la variable de scission il faudrait choisir une valeur seui
87. les diff rents types d accidents tant en position interm diaire On peut donc interpr ter cet axe comme celui de l agressivit de la soci t Le second axe est d interpr tation plus difficile Outre qu il temoigne d un l ger effet Guttman disposition en forme de croissant cf Benz cri 1980 Volle 1978 il isole principalement les homicides ceux ci tant massivement le fait de deux pays seulement l Irlande du Nord et les USA figure 2 Enfin le 3 me axe figure 1 bis tablit une distinction entre la mort donn e volontairement suicides et homicides du cot positif de l axe et les d c s accidentels ICELAND DENMARK FINLAND NORWAY NETHERL ENGLAND 1 2 3 4 5 6 BELGIU SCOTLAND 7 WGERMANY SIRELAND 8 AUSTRIA 9 FRANCE 10 11 SPAIN 12 13 ITALY PORTUGAL 14 15 16 17 USA 18 19 20 2 NIREL Figure 2 Donn es PSYSOC Analyse des correspondances repr sentation des pays sur les axes 1 et 2 Ces deux axes expliquent respectivement 44 33 et 34 41 de la variance totale 1 DENMARK 2 3 4 SWITZER USA FINLAND 5 WGERMANY 6 AUSTRIA 7 SWEDEN NIREL 8 9 PORTUGAL BELGIUM NETHERLANDS 10 ITALY FRANCE Tj NORWAY 12 SPAIN SCOTLAND 13 ICELAND 14 35 SIRELAND Figure 2 bis Donn es PSYSOC Analyse des correspondances repr sentation des pays sur les axe
88. lit s 1 1 Hi rarchie et ordonnance D finition 1 Benz cri 1966 Soit I un ensemble fini et H un ensemble de parties de J Nous dirons que H est une hi rarchie sur I si 1 IEH 2 Pour tout ie I ona i eH 3 Quels que soient h et h l ments de H si h N h alors on a soit h Ee ht sort bY EA Un couple LH form d un ensemble fini I et d une telle hi rarchie H peut tre repr sent comme un arbre dont les noeuds traits horizontaux symbolisent les diverses parties appartenant H ainsi l arbre ci dessous correspond la hi rarchie H form e des parties suivantes hl 1 7 h2 27 ASS 43 r7 h4 2 4 AS 15 h6 2 5 h7 4 3 K8 2 3 4 St oF NOH ql 2 Se Ay S E 1 2 3 4 5 Figure 1 Exemple simple de hi rarchie D finition 2 Benz cri 1966 Un ensemble I est dit muni d une ordonnance s il existe une relation d ordre total sur les paires d l ments de I C est dire que quels que soient les l ments 1 j k 1 de I l une ou l autre des expressions suivantes est vraie i j lt k 1 k 1 lt i j i j k 1 Nous pr f rons distinguer l galit du cas o une paire est effectivement diff rente de l autre tant entendu que la derni re des relations ci dessus signifie non pas que les deux paires sont constitu es des m mes l ments mais que les l ments qui les constituent se ressemblent autant dans la premi re paire que dans la
89. mom2 CDH CENMOB Centre de gravit Centres mobiles Voir agr gation Chi deux Voir Khi deux Construction ascendante hi rarchique Construction descendante hi rarchique Contributions Corr lation De Bravais Pearson De rangs Spearman De rangs Kendall Cram r CTRHqual CTRHquan CTRPqual CTRPquan De Rham C DessArb Diam tre Dichotomies successives Diday E DisEuc DisKi2 DisJac Disjonctif tableau voir forme disjonctive Dispersion Distance s De Jaccard Du Khi deux c5 c10 C4 1 c9 3 C4 1 c9 3 C4 1 c9 3 c6 c9 3 ci c4 c2 c3 1 2 c3 1 2 c3 1 2 C2 1 c2 2 c3 2 c6 a2 1 b a2 1 b c4 3 c9 1 c6 4 c9 1 c7 c9 1 c5 3 c9 1 c5 c6 1 c9 2 c9 3 c4 c9 c10 c7 c8 2 a1 3 a1 3 1 b a1 3 1 b c8 2 b c8 4 c8 4 c8 4 c8 4 c6 2 c9 1 4 b c4 3 c4 1 c1 c7 c5 1 3 b c3 3 c3 3 c9 1 2 c3 3 c9 1 2 c5 1 c6 1 c3 2 2 c3 2 2 a1 3 Euclidienne Indices de distances Recalcul des distances Ultram trique Voir ultram trique Effet de chaine Fages R Forme disjonctive compl te donn es sous Formes fortes Foucart T Guinochet M Guittonneau G G Guttman L effet Heuristique Hi rarchie Construction ascendante Construction descendante Dessin Indic e Interpr tation Troncature Hubert L Huyghens C Indices de distances Indices de similitude Informatique Interpr tation aides Inversion dans une hi rarchie Jaccard P Jambu M Jardine N K
90. mparis Hautes Alpes France Les num ros des relev s sont crits en colonnes sur les deux premieres lignes On porte l intersection de la ligne 1 et de la colonne j un 1 si l esp ce 1 est pr sente dans le relev j et un z ro dans le cas contraire On note parfois un coefficient d abondance au lieu de la simple pr sence absence toutefois dans notre exemple nous ne prenons en compte que cette derni re Le tableau 2 recense 66 esp ces dans un ensemble de 16 relev s Ces donn es sont extraites d un ensemble plus vaste de 55 relev s effectu s sur le plateau d Emparis 2200 m d altitude Hautes Alpes par G Roux et d j analys par ailleurs Cf chapitres Alpes I et II dans Benz cri et coll 1973 a Pour r duire la taille du tableau on a en outre limin une trentaine d esp ces qui n taient pr sentes qu une seule fois et dont le r le est donc minime L objectif de cette tude est de v rifier le bien fond de la classification des pelouses nard du nom de l esp ce dominante que nous avions obtenue pr c demment sans les dissocier des autres relev s Celle ci s tablissait ainsi Sigles des groupements Relev s Noms des groupements Pan L5 l5 Nardetum alpigenum Pacnl 3 4 L4 16 24 Festucetum halleri Sunass Nardetosum Pacn2 105 54 55 Festucetum halleri Subass Nardetosum Faci s Elyna et Salix Pac Zi 305 Sly 36 39 Festucetum halleri Se
91. n avons reconstruit que la partie sup rieure de l arbre avec les num ros des noeuds figure 1 Classe 1 36 37 Classe 2 34 Classe 2 Classe 3 35 Figure 1 Partie sup rieure de l arbre hi rarchique de la distance moyenne Donn es PSYSOC distance du Khi 2 sur donn es brutes Dans cette figure on a dissoci la classe 2 en ses deux sous classes Classe 2 FINLAN SWEDEN SWITZE DENMAR Classe 2 BELGIU NETHER ENGLAN ICELAN SCOTLA NORWAY SIRELA Examinons d abord le dernier noeud 37 qui relie la classe 3 NIRELA et USA aux deux autres La derni re ligne du tableau 3 montre clairement que ce sont les Homicides qui d partagent ces deux groupes de pays Le nceud 36 relie la classe 1 et la classe 2 Il est caract ris par la variable Cirrhose du foie qui explique 90 de la dispersion interclasse Ces renseignements ne font que confirmer ceux que nous avions d j recueillis par l observation des contributions aux classes de la partition Mais on peut continuer avec l examen des n uds suivants En particulier le n ud 34 attire notre attention sur les deux sous classes 2 et 2 d crites ci dessus On voit que ce sont les Suicides qui cette fois ci permnettent de distinguer ces deux sous classes Un coup d oeil au tableau des donn es montre qu en effet les pays de la sous classe 2 ont des taux de suicides nettement plus lev s que la moyenne qui
92. nciennes Il existe heureusement une formule un peu plus compliqu e qui permet de faire cette mise jour donc de suivre de tr s pr s l algorithme l mentaire d crit au chapitre 4 d iUi k 1 m m mx d i k m m d i k m d i i 6 2 m est mis pour la somme m m mx des effectifs des trois groupes en pr sence L criture d iUi k d signe maintenant la pseudo distance c est dire l accroissement du moment intra classe qui r sulterait de la fusion ventuelle du groupe iUi que l on vient de former avec le groupe k Voir Benz cri 1973 pour une d monstration Cependant nous n utiliserons pas cette formule Nous pr f rons tudier ici un autre algorithme fournissant les m mes r sultats mais travaillant directement sur le tableau des donn es brutes supposer que celles ci soient quantitatives Ou mieux encore sur le tableau des coordonn es issues d une analyse factorielle ainsi qu on l a recommand au chapitre 5 Cet algorithme consiste tenir en m moire centrale le tableau rectangulaire des donn es puis au fur et mesure des agr gations remplacer les lignes des objets agr g s par une ligne contenant les coordonn es de leur centre de gravit L avantage de cette m thode est qu elle permet de traiter des ensembles d objets beaucoup plus importants que l algorithme l mentaire En effet lorsque les objets sont nombreux le nombre des variables est g n ralement
93. ndices de Jaccard num ro 2 Dice num ro 3 Sokal et Sneath 2 num ro 4 et Kulczinski 1 num ro 5 donnent la m me ordonnance Cf d finition de ce terme au paragraphe pr c dent Cela tient ce qu ils sont tous quatre fonctions d croissantes de p q c L indice de Jaccard par exemple peut s crire sous la forme s 1 p q c 1 on v rifiera que les trois autres indices cit s se mettent sous des formes analogues Rappelons que la structure de l arbre dans certaines classifications hi rarchiques ne d pend que de l ordonnance elles donnent donc les m mes r sultats avec ces quatre indices voir chapitre 4 paragraphe 1 2 Note 4 Dans l indice de Simpson num ro 8 comme dans tous les autres c a pour valeur minimum soit z ro si p q lt n soit p q n Min p q Dans le premier cas qui est fr quent dans de nombreuses disciplines comme l cologie v g tale ou animale l arch ologie etc l intervalle de variation lorsque p et q sont fix s est 0 1 Il est donc ind pendant de p et q ce qui n est pas le cas pour les autres indices en g n ral Note 5 Pour l indice de Kochen et Wong num ro 9 l esp rance math matique dans les conditions d crites au d but de ce paragraphe est constante mais les objets de faible poids sont avantag s 2 2 Indices o les pr sences et absences d attributs jouent des r les quivalents Le titre de ce paragraphe est un peu abusif car on sait que c et
94. nes d x y 1 d x z 2 1 d x t 3 3 d y z 1 1 d y t 2 3 d z t 1 2 x y Z t X y Z t Figure 2 Pour les m mes donn es o les points sont dispos s en cha ne gauche les CAH du saut minimum au centre et du diam tre droite donnent des r sultats radicalement diff rents Le premier groupe form est toujours xUy la distance 1 Dans l agr gation par le saut minimum ona d xUy z 1 1 d xUy t 2 3 tandis qu avec l agr gation par le diam tre d xUy z 2 1 d xUy t 3 3 Dans le premier cas on agr ge z xUy tandis que dans le second on agr ge z et t distants seulement de 1 2 La derni re tape consiste r unir tous les objets d o les graphiques ci dessus On remarque que l agr gation par le saut minimum a tendance craser les niveaux de liaison tandis que la m thode du diam tre les distend Avec le saut minimum on congoit que l on arrive rapprocher des points extr mement diff rents c est ce qu on appelle l effet de chaine 2 Application aux exemples 2 1 Causes de d c s PSYSOC On a appliqu la construction ascendante sur les deux matrices de distances entre pays calcul es au chapitre pr c dent La premi re tait obtenue en calculant la distance du Khi deux sur les donn es brutes tandis que la seconde provenait de la formule euclidienne usuelle appliqu e aux r sultats de l AFC Les deux r sultats voir figures 3 et 4 son
95. ns la valeur moyenne de chacun des indices consid r s Plus pr cis ment on supposera que tous les caract res retenus pour la composition du tableau de donn es sont quiprobables que p et q sont fix s et que l on tire toute paire d attributs ind pendamment l un de l autre Dans ces conditions il y a p n chances pour que 1 poss de l attribut k de m me il y a q n chances pour que i poss de k les deux tirages tant ind pendants il y a pq n chances pour que i et i poss dent k ensemble l esp rance math matique e m de c nombre d attributs en commun est donc pq n Voici donc ces formules assorties le cas ch ant de remarques ou de critiques elles sont toutes pr sent es sous forme d indices de similitude 2 1 Indices o la pr sence des attributs joue un role pr pond rant Le souci majeur des auteurs de ces formules a t comme on le voit sur le tableau 1 de pond rer le nombre c d attributs communs par les poids des deux objets consid r s c est dire les nombres totaux d attributs poss d s par l un et par l autre Les num ros figurant dans la colonne Note de ce tableau 1 renvoient aux remarques ci dessous La colonne Moyenne est calcul e comme l esp rance math matique dans les conditions suivantes les nombres p et q d attributs des deux objets sont fix s tous les attributs ont m me probabilit d apparition et ils sont ind pendants
96. ns Cet indice vaut z ro lorsque les deux observations sont tout fait identiques et un lorsqu elles n ont aucun attribut en commun Primitivement cet indice a t cr comme une mesure de ressemblance s C p q c 3 La ressemblance vaut z ro quand les deux observations n ont pas de caract res communs et un lorsqu elles sont identiques Mais nous pr f rons l expression sous forme de distance qui permet de n avoir qu un seul programme de classification pour travailler sur des donn es qualitatives ou quantitatives De nombreuses formules analogues sont donn es en Annexe 1 avec les remarques qu elles n cessitent Enfin dans le cas o les donn es contiennent un m lange de variables qualitatives et quantitatives il est encore possible de combiner des formules pour obtenir une expression de la distance entre observations voir annexe 1 Mais cette mani re de faire comporte tellement d arbitraire qu il vaut mieux dans ce cas d couper les variables quantitatives en classes de valeurs que l on consid re ensuite comme des modalit s On applique alors l AFC puis la classification sur les coordonn es factorielles 2 Application aux exemples 2 1 Causes de d c s PSYSOC Les donn es sur les causes des d c s d j examin es ci dessus paragraphe 1 1 sont constitu es de valeurs additives la somme des nombres d une ligne du tableau repr sente en effet pour un pays ce que E Todd appelle le taux de mortalit
97. nsu stricto Tableau 3 Donn es PHYTOS partition des 16 relev s en 4 classes appel es groupements Les noms des groupements sont tablis en fonction des esp ces caract ristiques Par exemple le dernier groupement est appel Festucetum halleri parce que son esp ce caract ristique est Festuca halleri Mais si chaque esp ce prise individuellement s accommode de terrains plus ou moins vari s les associations v g tales sont en g n ral caract ristiques de conditions d environnement tr s pr cises Cf Guinochet 1955 1973 R55 R54 R4 R10 R36 R27 R3 R13 R15 R14 O00 0 100145 NH 11 R16 12 R38 13 R23 16 R24 R30R31 Figure 3 Donn es Phytos Analyse des correspondances repr sentation des relev s sur les axes 1 horizontal et 2 vertical Ces deux axes expliquent repectivement 21 32 6 et14 53 6 de la variance totale Apr s Analyse factorielle des correspondances en examinant conjointement les deux plans factoriels form s des axes 1 2 et 1 3 figures 3 et 4 on reconnait l existence des groupements Pan 13 15 23 et Pac 27 30 31 36 38 aux deux extr mit s de l axe 1 La r alit des deux autres groupements est plus contestable La classification automatique confirmera t elle ou infirmera t elle cette partition R13 R38 R23 R15 R54 R27 R30 R36 R31 LU 30014 0N EA 10 R3 R55 11 R4 13 R16 R14 14 R10 16 R24 Figu
98. olonais r sum en allemand Bull Intern Acad Pol Sci Lett Cl Sci Math Nat B Sci Nat Suppl 2 57 203 Lance G N and W T Williams 1966 Computer programs for hierarchical polythetic classification Comput J 9 60 64 Lebart L Morineau A F nelon J P 1982 Traitement des donn es statistiques 518p Dunod Paris Lefebvre J 1983 Introduction aux analyses statistiques multidimensionnelles 275p Masson Paris Lerman I C 1970 Les bases de la classification automatique 117p Gauthier Villars Paris Lerman I C 1981 Classification et analyse ordinale des donn es 740p Dunod Paris Reinert M 1983 Une m thode de classification descendante hi rarchique Cahiers analyse des donn esd VIII 2 187 198 Roux G et Roux M 1967 A propos de quelques m thodes de classification en phytosociologie Rev Stat Appl vol XIV no 2 50 72 Roux M et Guittonneau G G 1977 Sur la taxinomie du genre Erodium Cah Ana des donn es vol IL no 1 97 113 Roux M 1985 Algorithmes de classification 151 p Masson Paris Roux M 1995 About divisive methods in hierarchical clustering In Data Science and Its Applications Y Escoufier C Hayashi B Fichet N Ohsumi E Diday Y Baba L Lebart Eds Acad Press Tokyo pp 101 106 Saporta G 1990 Probabilit s analyse des donn es et statistique Editions Technip Paris 493 p Sokal R R et Sneath P H A 1963 Principles of
99. on du coefficient de Dice pour les donn es binaires sous forme de distance Coefficient de divergence Clark 1952 qd i i 1 p X D j x i j x i j Ce coefficient varie entre 0 observations identiques et 1 Distance du Khi 2 Variables qualitatives ou effectifs Ici on change la d finition de D j D j x i j x i x i j x i x i somme des termes de la ligne i X j somme des termes de la colonne j w 3 ceu E X w j D j Particuli rement adapt e au cas des tableaux homog nes d effectifs ou de grandeurs additives voir exemple PSYSOC chapitre 2 la distance du Khi 2 impose une double pond ration sur les lignes et sur les colonnes du tableau des donn es 4 Conclusion Les formules de distances comme de similitudes sont tr s nombreuses mais il est d conseill de choisir une formule inusit e sans raison valable En ce qui concerne les donn es binaires qualitatives deux familles d indices se distinguent l int rieur desquelles le choix d une formule influe peu sur le r sultat de la classification D autres formules ont t propos es ailleurs qui font intervenir la notion de probabilit voir Goodall 1966 Lerman 1981 ou la th orie de l information voir Estabrook 1967 mais leur complication et le faible avantage qu elles apportent nous ont conduit les carter de cet inventaire ANNEXE 2 Hi rarchies et ultram triques 1 G n ra
100. on obtenue 2 M thodes bas es sur une variable particuli re Ces m thodes reposent sur le choix ou sur la construction d une variable que nous appellerons variable crit re Cette variable qui change chaque tape sert ensuite effectuer la dichotomie Supposons que l on veuille scinder la classe C en deux sous classes C et C Cette dichotomie se fera en mettant dans C tous les objets pr sentant pour la variable crit re une valeur inf rieure ou gale un certain seuil et de ranger dans C le reste des objets c est dire ceux dont la valeur est sup rieure au seuil choisi 2 1 Utilisation de l une des variables des donn es Le prototype de ce type d algorithme est la m thode de Williams et Lambert 1959 que nous d crivons maintenant Cette m thode est particuli rement rudimentaire N op rant que sur des variables qualitatives elle s lectionne l une des variables pour servir de crit re d affectation tous les objets pr sentant pour cette variable la m me modalit sont rang s dans la m me classe si les variables sont plus de deux modalit s le noeud correspondant aura plus de deux branches La variable retenue est celle qui dans la classe C scinder est la plus corr l e toutes les autres Comme il s agit de variables qualitatives la corr lation est mesur e par le Khi deux de contingence On calcule donc les Khi deux de contingence de toutes les variables prises deux deux et l on retient cel
101. ortalit calcul s pour 100 000 habitants Afin de juger du bien fond des classifications nous donnons ici les r sultats de l Analyse factorielle des correspondances de ce tableau Tableau 1 colonnes F1 F2 et F3 Les variables tant quantitatives on aurait pu appliquer galement l Analyse en composantes principales Toutefois l tude des profils des pays r alis e par la premi re nous parait mieux adapt e au sujet trait c est dire les taux de mortalit comme indicateurs de maladies sociales voir chapitre 3 pour un compl ment de justification Au demeurant les poids des lignes tant relativement comparables les r sultats des deux types d analyse factorielle sont assez voisins SUICI HOMIC AROUT AINDU AAUTR CIRFO F1 F2 F3 AUSTRIA 241 16 330 43 363 325 220 6 108 FRANCE 156 9 225 10 535 328 210 3 110 PORTUGAL 85 Lg 349 y 281 345 309 729 65 WGERMANY 210 12 230 21 298 269 245 17 149 BELGIU 156 10 260 13 367 144 95 cS FINLAND 251 26 180 29 387 55 258 270 178 SWEDEN 194 11 TSL 13 384 122 54 214 58 SWITZERL 225 9 195 26 276 128 15 Z2 211 ITALY 54 Ti 219 19 224 319 484 287 90 NIRELAND 40 136 215 18 320 43 727 691 48 DENMARK 241 6 168 11 230 107 21 289 334 ICELAND 101 5 179 23 380 9 328 283 241 SCOTLAND 82 15 155 18 342 59 215 109 203 SPAIN 40 4 136 17 237 225 392 178 183 NORWAY 104 6 138 22 346 41 234 250 176 SIRELAND 38
102. ous les mi De la sorte on peut se repr senter les observations comme un nuage mat riel I form des masses ponctuelles mi Son centre de gravit g a pour j me coordonn e x Gy 3 xy wx ARA e XI 7 M oum m m2 m est la masse totale du nuage Remarquons en passant que x g j n est autre que la moyenne de la variable j Le moment centr d ordre deux ou moment par rapport au centre de gravit est la quantit M I g m d 1 g m d 2 g m n 9 5 1 o d i g d signe le carr de la distance de i g Dans le cas de la distance euclidienne usuelle di g xls D x g 1 x 3 2 Kg 2 t 2 Rip eG pr Autrement dit le moment centr d ordre deux du nuage I s obtient comme la somme pour toutes les variables et tous les objets des carr s des carts la moyenne somme pond r e par les masses des objets C est une mesure de la dispersion des points du nuage En effet si les points sont tr s concentr s autour de leur centre de gravit le moment d ordre deux est faible il est grand dans le cas contraire D ailleurs la variance d une variable j qui est la mesure usuelle de la dispersion en statistique s crit var j m x 1 3 x g J m x n 3 x g 3 m C est la moyenne pond r e de la somme des carr s des carts pour la variable consid r e Au coefficient 1 m pr s le moment d ordre deux est donc une variance g n ralis e au cas de
103. que les axes factoriels synth tisent g n ralement plusieurs variables Elles sont efficaces pour le traitement du m me format de tableau nombreux individus mais peu de variables En effet si les variables sont nombreuses alors le temps de calcul n cessaire l extraction du premier axe s allonge rapidement Par ailleurs ces m thodes ne permettent pas d associer une variable chaque noeud de la hi rarchie puisque ceux ci sont d finis par une combinaison lin aire des variables initiales 3 M thodes bas es sur des individus particuliers 3 1 S lection d un point p riph rique m thode de McNaughton Smith et al 1964 Pour initier une dichotomie ces auteurs examinent la somme des distances de chaque objets tous les objets de sa propre classe Celui dont la somme des distances est maximum est supprim de sa classe et est pris comme embryon ou noyau d une nouvelle classe Appelons encore C la classe qui perd cet l ment et C la nouvelle classe La suite de l algorithme consiste transf rer un un certains l ments de C vers C de fagon optimiser un crit re local L article de McNaughton Smith et al ne donne aucune pr cision sur ce crit re mais on peut penser maximiser la variance interclasse pour les deux classes C et C ou bien la distance moyenne inter classe La proc dure de transfert est arr t e lorsque le crit re cesse de s am liorer 3 2 S lection de deux points p riph riques m thode de H
104. r aussi deux m triques de m me ordonnance sans qu elles soient comparables D finition 2 Soit un ensemble I fini muni d une famille dm m e M de m triques index e par M fini ou non Nous dirons que cette famille est born e si pour tous 1 1 e I il existe b i 1 tel que pour tout m e M d i i x bG 1 Il en r sulte imm diatement comme I est fini et que l ensemble des paires i 1 est fini aussi qu il existe b majorant de tous les d i 1 savoir le Max b i i 1 1 I D finition 3 Soit un ensemble fini I muni d une famille born e de m triques d m e Mj Nous appellerons enveloppe sup rieure de la famille l application de I x I dans R d finie pour tout i i Ix I par Ly 2 a gt sup dd iy a Lime M Proposition L enveloppe sup rieure d une famille born e d ultram triques sur un ensemble fini I est une ultram trique sur I 1 Les dm tant des m triques si i i on a pour tout m M dm i i 0 donc Sup d i i m eM 0 R ciproquement si l on a Sup d 1 1 m e Mj 0 comme les dm sont des applications positives cel entra ne que pour tout m e M d i 1 0 donc i i 2 On a pour tout m e M d i i dA 1 1 ce qui entraine Sup du i i m M Sup d i i me M 3 D montrons maintenant la relation ultram trique 1 du paragraphe 1 2 pour l enveloppe sup rieure La conclusion s crit Sup dn i i m M l
105. r gation autour de centres mobiles pour obtenir un ensemble de classes dont les centres de gravit sont alors utilis s comme donn es pour une classification hi rarchique D autre part une strat gie mixte employant conjointement analyse factorielle et classification donne souvent d excellents r sultats 2 1 Construction hi rarchique suivie des centres mobiles L objectif d une telle strat gie est d obtenir une partition de bonne qualit On a vu chapitre 5 que quelle que soit la partition de d part l algorithme des centres mobiles ne peut qu am liorer la valeur du moment inter classe Il est donc tentant de fournir cet algorithme une partition initiale labor e au lieu de la tirer au hasard Cela peut tre fait par l application pr alable d une CAH ou d une CDH En effet en coupant l arbre obtenu un endroit o la succession des niveaux d agr gation pr sente un saut important on obtient g n ralement une partition coh rente On peut m me si cela semble justifi modifier manuellement cette partition avant de l introduire dans un programme d agr gations autour de centres mobiles L examen soigneux de l arbre hi rarchique est n cessaire on pourra ventuellement essayer plusieurs variations autour de la partition obtenue par troncature 2 2 Centres mobiles suivis d une construction hi rarchique On a remarqu ci dessus paragraphe 1 que lorsque les dimensions du tableau des donn es sont importantes
106. ravit g de cette classe On peut donc appliquer le th or me de Huyghens pour le sous ensemble q M Ifg 24 M q gak med ga 9 que l on peut encore crire M I g X M q 94 M Q g 5 3 En effet la deuxi me somme issue du crochet n est autre que le moment centr d ordre deux du solide form par les centres de gravit g chacun d eux tant muni de la masse m car ce solide a son centre de gravit confondu avec le centre de gravit g de I L quation 5 3 repr sente la d composition de la dispersion totale en dispersion l int rieur des classes appel e intra classe et dispersion entre les classes ou inter classe On dit que le moment d ordre deux total est gal la somme des moments centr s de chacune des classes augment e du moment inter classe Cette quation est analogue celle de l Analyse de la variance dans le cas d une seule variable Il est vident qu une bonne classification doit rendre la dispersion intra classe aussi petite que possible pour fournir des classes homog nes La dispersion totale tant fix e par les donn es elles m mes il est quivalent de chercher une partition minimisant la dispersion intra classe ou rendant maximum la dispersion inter classe L une ou l autre de ces quantit s constitue le crit re du moment d ordre deux d une partition On en verra une application la construction ascendante hi rarchique dans le chapitre 6 Application l algorithme des c
107. re plus conforme ce qu un examen attentif de la matrice des distances permet d esp rer Mais dans le cas g n ral on sera presque toujours satisfait de la hi rarchie obtenue par agr gation suivant la distance moyenne La hi rarchie fournie par CAHmom2 est presque toujours tr s voisine dans sa structure de celle que donne CAHLM bien que les niveaux d agr gations soient fort diff rents L ordre de pr f rence ci dessus n implique pas qu il faille liminer la m thode d agr gation autour de centres mobiles On a vu en effet paragraphe 1 1 que pour certaines tailles de donn es c est la seule applicable D autre part en essayant un nombre suffisant de partitions initiales diff rentes on parvient des solutions satisfaisantes indiqu es par une valeur lev e du moment inter classe 1 4 Temps de calcul Du point de vue du temps de calcul la palme revient sans conteste au programme CAHMOM Ceci est du l emploi de l algorithme sp cial dit des voisins r ciproques Bien entendu cette m thode particuli re pourrait tre galement utilis e pour construire les hi rarchies l mentaires mais sa programmation serait un peu plus complexe cf De Rahm 1980 2 Strat gies Suivant la nature des donn es et l objectif atteindre on peut utiliser une des strat gies suivantes Classification hi rarchique tronqu e pour donner une partition servant de point de d part une agr gation autour de centres mobiles Ag
108. re 3 paragraphe 1 2 mais il nous parait souhaitable de rappeler ici l un d eux on relation avec la nature des donn es En effet lorsque celles ci comprennent un m lange de variables quantitatives et qualitatives le plus simple est de rendre qualitatives celles qui ne le sont pas par l tablissement de classes de valeurs On consid re ensuite chaque classe de valeur ou chaque cat gorie pour les variables qualitatives comme une variable en 0 ou 1 suivant que les objets tombent dans cette cat gorie ou non Cela s appelle mettre les variables sous forme disjonctive compl te Ceci fait on peut alors calculer un indice de distance adapt ce type de donn es Distance du Khi2 ou indice de Jaccard par exemple cependant ces indices eux m mes existent en grand nombre et un nouveau choix d licat est donc n cessaire Dans l ignorance d une bonne formule la distance du Khi deux donnera g n ralement des r sultats satisfaisants Mais compte tenu des avantages de la m thode et de l int r t des r sultats interm diaires qu elle fournit l emploi pr alable de l Analyse factorielle des correspondances nous parait s imposer en de telles circonstances On calculera ensuite la distance euclidienne usuelle sur les premiers axes retenus du point de vue des r sultats cette strat gie est quasi quivalente comme on l a vu avec l exemple PSYSOC effectuer la classification apr s calcul de la distance du Khi deux sur les donn es brutes C
109. re 4 Donn es Phytos Analyse des correspondances repr sentation des relev s sur les axes 1 horizontal et 3 vertical Ces deux axes expliquent respectivement 21 32 et 10 64 de la variance totale Chapitre 3 Pr paration des donn es calcul des distances La plupart des algorithmes de classification ont pour point de d part une mesure des distances ou dissemblances entre les objets Or il existe une infinit de facons pour valuer ces dissemblances et la formule retenue aura une influence d cisive sur les r sultats C est pourquoi nous croyons que l utilisateur doit r fl chir consciencieusement sur cette question en fonction de chaque probl me pratique Nous donnons ci dessous quelques id es g n rales elles sont compl t es par des consid rations math matiques plus pr cises dans l annexe 1 1 G n ralit s 1 1 Donn es quantitatives exemple des causes de d c s Psysoc Dans nos donn es sur les causes sociales des d c s il nous faut commencer par calculer les distances entre les pays La formule la plus utilis e est celle de la distance euclidienne usuelle a i i Ej xij xi 3 o xij d signe le nombre de d c s de cause j dans le pays i Par exemple pour l Autriche et la France on aura d2 AUST FRAN 241 156 16 9 325 328 7225 49 11025 1089 29584 9 48981 d AUST FRAN 221 3 Un premier probl me appara t imm diatement les nombre
110. remarque imm diatement qu une telle application permet de d finir sur I un indice de similarit s c est dire une mesure de la ressemblance cf Benz cri 1966 et Roux 1967 entre les l ments de I de la mani re suivante Pour toute paire i i I s i i est le plus grand nombre x h tel que i i Che Het x h s i i De plus on v rifie ais ment que d i 1 1 s 1 1 constitue une distance sur I Une telle hi rarchie d finit donc une v ritable ordonnance et non plus un ordre partiel sur les paires d l ments de I D finition 2 Bourbaki 1958 Une distance d sur un ensemble E est dite ultram trique si elle v rifie pour tout triplet de points i j k de I la condition d i k lt Max d i j d j k 1 Il est clair que la distance d d finie ci dessus pour les indices de similarit est ultram trique en effet pour tout triplet de points de I il ne peut y avoir que deux situations ou bien toute partie de H qui contient deux des points soient i et j contient aussi le troisi me soit k ou bien il existe h H telle que i j e h et k h Dans le premier cas d apr s la d finition et la relation 1 est bien v rifi e triangle quilat ral dans le second cas ona d i j lt d i k d i j lt d j k et d i k d j k d apr s la d finition de d o l on voit que 1 est encore v rifi e R ciproquement toute distance ultram trique d sur un ensemble fini I
111. restreint Supposons par exemple qu on ait 200 objets rep r s par 10 variables quantitatives alors la matrice des donn es n occuppe que 200x10 2000 cases tandis que la matrice des distances utilise 200 x 199 2 19900 cases en ne conservant que la demi matrice inf rieure ou sup rieure Dans le cas o le nombre de variables est lui aussi lev alors il devient indispensable d effectuer une analyse factorielle pr alable dont on ne retient que les cinq ou dix premiers axes factoriels En contre partie le nombre de calculs effectuer sera nettement plus lev puisqu apr s chaque agr gation il faudra recalculer les pseudo distances non seulement entre la paire fusionn e et les autres objets mais aussi entre tous les objets puisqu on ne garde pas en m moire cette matrice des pseudo distances En fait on va voir que gr ce la consid ration des voisins r ciproques on peut r duire substantiellement cette quantit de calculs et obtenir un algorithme particuli rement efficace 2 L algorithme des voisins r ciproques De Rham 1980 Le plus proche voisin i d un objet i est celui pour lequel la distance di 1 est la plus petite des distances entre 1 et tout autre objet On limine le cas peu courant o par suite de distances gales un objet i aurait plusieurs plus proches voisins On appelle voisins r ciproques deux objets dont l un est le plus proche voisin de l autre et vice versa L algorithme d
112. riables c 2 1 Sibson R a2 2 b Sneath P H A c1 2 a1 2 a1 2 1 a1 2 2 b Sokal R R c1 2 a1 2 a1 2 1 a1 2 2 b Taxinomie c1 4 c9 3 c10 1 b Todd E c2 1 c3 2 1 b Transposition d un tableau c3 3 TRONCAT c9 4 Troncature C1 1 c9 2 1 c9 4 c10 1 Typologie c1 4 c9 3 b Ultram trique a2 Variables R le des variables c8 Pond rations des variables a1 3 2 Voisins r ciproques c6 2 c10 2 b Volle M C2 1 c3 1 2 b Ward J H c6 1 M thode de Ward voir agr gation par le moment d ordre 2 Williams W T c7 2 1 a1 3 2 b
113. s conduit six groupements qui ne sont pas en contradiction avec les hi rarchies d j obtenues Aucun pays ne reste isol Il est malheureusement impossible de dire si une partition en six classes est meilleure qu une autre en trois classes car le rapport d inerties qui nous sert de crit re d pend du nombre de classes comme le font d autres crit res non bas s sur l inertie G1 1 1 1 AUSTRI FRANCE WGERMA G2 1 2 1 PORTUG ITALY SPAIN G3 3 4 2 BELGIU FINLAN SWEDEN SUISS DENMAR G4 2 3 3 NIRELA USA G5 4 4 4 ICELAN SCOTLA SIRELA NORWAY G6 3 4 4 NETHER ENGLAN Tableau 3 Groupements stables formes fortes apr s tirages de partitions al atoires en 4 classes Les pays rassembl s dans un m me groupe se sont toujours trouv s ensemble dans les trois partitions finales retenues l issue des diff rents tirages initiaux ces groupes sont symbolis s par leurs num ros figurant entre parenth ses Voir Tableau 2 ci dessus 3 Les programmes de calculs de Centres mobiles Nous proposons dans notre biblioth que de proc dures Classeur AnaDon xls deux versions de l agr gation autour de centres mobiles d nomm es respectivement CenMobl et CenMob2 Dans CenMobl l utilisateur doit fournir une partition initiale qui est alors am lior e par le programme tandis que dans CenMob2 l utilisateur fournit seulement le nombre de classes d sir Le programme effectue alors un
114. s l et 3 Ces deux axes expliquent respectivement 44 33 et 14 96 de la variance totale L examen du plan 1 2 pour les pays figure 2 confirme la th se de Mr Todd sur la similitude entre l Allemagne et la France du point de vue des tensions internes de la soci t alors que l Angleterre se trouve tre plus proche des pays nordiques On remarque galement le regroupement des pays m diterran ens ESP PORT ITAL dans la zone domin e par la cirrhose du foie 2 Phytosociologie PHYTOS L tude des affinit s de terrain entre esp ces v g tales porte le nom de phytosociologie Elle a pour point de d part des enqu tes sur des r gions plus ou moins tendues au cours desquelles on effectue des relev s Un relev consiste en la liste des esp ces v g tales poussant dans un lieu particulier Le r sultat d une enqu te de terrain se met sous la forme d un tableau rectangulaire o l usage est de mettre les relev s en colonnes et les esp ces en lignes T5153 3k 10 2 2 72 53 13 53 34034563470 6 1100000000100 1 20100001001111 500000101000 0 0 71001010000001 100000001010000 Ju dS EI 01011010 12 1 T0 1 1 0 0 1 20 0 00000000001 210000000001001 24 00 1 1 1 l Q I 0 0 260001000 00110 29 L0 L101000 41 L 0 1 100001 42 001 1 0 0 0 0 I 4 45010000000000 48 0 0010000000 50 000011 1000 53 0 0 000000 0 0 55 0 0 000000100 5
115. s plus caract ristiques de chaque classe C est pourquoi le moment d ordre deux total et le moment inter classe figurant au tableau ci dessous calcul s sur ces variables ne coincident pas avec les quantit s homologues que l on a pu obtenir avec l algorithme des centres mobiles appliqu aux coordonn es factorielles des pays MOMENT TOTAL 556228 MOMENT INTERCLASSE 261834 R 0 47 el CONTRIBUTIONS VAR CLASSES SUI HOM ARO AIN AAU CIR 1 O O 8 O 0 91 2 1 2 EP O O 85 3 18 63 2 O 2 dS Tableau 1 Donn es PSYSOC contributions des variables aux classes CONTRIBUTIONS CLASSES VAR SUI HOM ARO AIN AAU CIR 1 O 3 58 O 38 68 2 17 8 39 13 2 30 3 83 89 2 87 60 2 Tableau 2 Donn es PSYSOC contributions des classes aux variables Il ressort nettement du tableau 1 que la classe 3 se caract rise principalement par un taux lev d Homicides alors que les Suicides et les Cirrhoses du foie y sont un niveau inf rieur la moyenne signes n gatifs Ce qui caract rise de facon quasi exclusive les classes 1 et 2 ce sont les Cirrhoses du foie en quantit importante dans la classe 1 excessivement peu nombreuses signe n gatif dans la classe 2 Dans une moindre mesure ces deux classes se diff rencient galement par les Accidents de la route nombreux dans la classe 1 plus rares dans la classe 2 Le tableau 2 fournit des renseignements int ressants sur la dispersion de chaque variab
116. s qui mesurent les homicides deuxi me terme dans la somme ci dessus sont beaucoup plus petits que les autres Leur contribution la distance ici 49 sera donc en g n ral beaucoup plus faible que celle des autres colonnes du tableau Pour r quilibrer les r les des variables l usage est d op rer leur r duction c est dire de diviser les valeurs par l cart type de la variable consid r e Le second probl me provient des diff rences globales dans les taux de mortalit Il peut en effet arriver que deux pays aient une r partition des d c s analogue mais que pour l un des deux les quantit s soient toujours plus faibles que pour l autre Seules sont conserv es les proportions entre les cat gories de d c s On peut alors consid rer que ces deux pays souffrent des m mes malaises sociaux l un un degr moindre que l autre Cependant comme la distance euclidienne repose sur les carts absolus ces deux pays seront vraisemblablement loign s et donc class s dans des cat gories distinctes On dit qu il y alors un effet de taille On peut pallier cette difficult en calculant la somme des d c s par pays puis en rempla ant chaque valeur par son rapport cette somme Mais cette transformation ne r sout pas tous les probl mes En effet si plusieurs variables sont li es au m me ph nom ne sous jacent elles seront corr l es entre elles et apporteront plusieurs fois la m me information Pour viter cet incon
117. s weno yog 202 Mais la deuxi me expression entre crochets est nulle de par la d finition du centre de gravit La somme des carts la moyenne est gale z ro Revenons alors la double somme constituant le moment d ordre deux Les deux types de termes restants fournissent l un le moment centr d ordre deux l autre une quantit qui s crit m d g a M I a M I g m g a 5 2 C est le th or me de Huyghens qui s nonce ainsi le moment d inertie d un solide par rapport un point quelconque a est gal au moment du solide par rapport son centre de gravit augment du moment du point g affect de la masse totale m du solide par rapport au point a Application une partition Supposons d finie une partition Q de l ensemble I c est dire que tout l ment q de Q est un sous ensemble de I et tout l ment de I appartient un et un seul des l ments de Q On appelle m la masse du sous ensemble des points de q Reprenons dans une criture condens e l expression 5 1 du moment centr le signe 2 signifie qu il faut faire la somme de tous les termes analogues obtenus en faisant varier l indice 1 M 1 9 21 mi d i g et d composons cette somme en faisant des sommes partielles sur les sous ensembles q de Q Mig A ea lem d du o5 La somme entre crochets repr sente le moment de la classe q par rapport au point g centre de gravit g n ral qui est diff rent du centre de g
118. sont ind pendants de l origine et de l chelle des variables 3 2 Mesures de distances Les formules ci dessous expriment la distance entre deux observations 1 et i Ces formules utilisent la quantit o x i j est la valeur l intersection de la ligne i et de la colonne j du tableau rectangulaire des donn es les observations sont suppos es plac es en lignes D j est la valeur absolue de la diff rence des valeurs de la variable j pour les deux observations i et i On l appelle parfois l cart entre les deux observations i et 1 pour le caract re j Ecart moyen Czekanovski 1932 d i i 23D 3 p p d signe le nombre de variables Ecart maximum d i i Max D Distance euclidienne usuelle Do A By DG Cette distance est particuli rement sensible l chelle choisie pour chacune des variables c est pourquoi on lui pr f re souvent une formule introduisant des coefficients de pond ration w Distance euclidienne pond r e d i i 2 w 3 D 3 w j pond ration affect e la variable j L usage est de prendre pour pond ration l inverse de la variance de j w j 1 s 3 mais tout autre syst me de pond rations est possible condition que celles ci soient positives Distance de Manhattan M trique Ll Distance de Chebychev M trique L infini d i i Max D j Coefficient de Lance et Williams 1966 d i i j D j 24 x i 3 x i 3 C est une g n ralisati
119. t Max Sup dn i i me M Sup dn i i m Mj ou encore Sup da i i m M Sup Max di i i dti 27 1 m M avec pour hypoth se Ym eM Vi i im el dolus why c Max dites 347 cie oy S Sup dn 1 1 m e M existe car pour tout i i I d n 1 1 est born Cela signifie que pour tout e gt 0 il existe m tel que S lt ds 1 1 Mais par hypoth se d m 1 1 lt Max d m 1 1 d ms 1 1 et par passage la borne sup rieure dm i i lt Sup Max da i i da G i m M ce qui entra ne car e est quelconque que S lt Sup Max Dd da i i m MJ Remarque 2 On aurait pu d finir d une fa on analogue l enveloppe inf rieure d une famille de m triques mais on n aurait pu d montrer de proposition analogue la pr c dente comme le prouve le contre exemple suivant di 3 k 4 d j 1 di k 1 ER 4 d jy k PE 35 dz j 35 d k 1 2 on a alors Inf di j k d j k 3 Inf di j d2 5 1 1 Inf di k 1 d2 k 1 2 d o Max Inf di j 1 d j 1 Inf di k 1 dk 1 2 qui n est pas sup rieur Inf di j kK d j k comme l exige la relation 1 du paragraphe 1 2 ci dessus 2 2 Ultram trique sous dominante d une m trique donn e D finition J J S Etant donn e une m trique 6 quelconque sur un ensemble fini I pour l ensemble des ultram triques inf rieures 6 cell
120. t fort utile galement dans les sciences de l homme psychologie sociologie linguistique arch ologie histoire etc et dans les techniques d riv es comme les enqu tes d opinion le marketing etc Ces derni res emploient parfois les mots de typologie et segmentation pour d signer la classification ou l une de ses innombrables variantes Citons encore la m decine l conomie l agronomie et nous en oublions certainement Dans toutes ces disciplines la classification peut tre employ e comme une fin en soi mais elle l est souvent juste titre comme une m thode compl mentaire d autres m thodes statistiques Elle peut en effet aider efficacement l interpr tation des graphiques d analyse factorielle ou bien d terminer des groupes d objets homog nes pr alablement une r gression lin aire multiple Chapitre 2 Exemples de donn es Avant d aborder les m thodes classificatoires nous pr sentons deux exemples qui nous serviront tout au long de ce livre 1 Psychologie et soci t PSYSOC Notre premier exemple est tir du livre de E Todd Le fou et le prol taire 1979 annexe 2 p 283 Il s agit de statistiques concernant pour diff rents pays occidentaux les causes de d c s qui selon Mr Todd sont caract ristiques de l tat de sant mentale de la soci t voir tableau 1 six premi res colonnes Notre objectif sera d tablir une classification des pays en fonction de ces taux de m
121. t tr s semblables et font apparaitre trois groupes principaux NIRELA USA FRANCE AUSTRI 4 WGERMA 4 PORTUG ITALY SPAIN FINLAN SWEDEN SWITZE 4 L DENMAR 4 BELGIU NETHER 4 SIRELA ICELAN 4 SCOTLA 4 NORWAY 4 Figure 3 Donn es PSYSOC Hi rarchie du lien moyen construite partir de la distance du Khi 2 calcul e sur les donn es brutes groupe Europe Ouest AUSTRI WGERMA FRANCE SPAIN ITALY PORTUG groupe Europe Nord ICELAN NORWAY NETHER ENGLAN SCOTLA SIRELA BELGIU SWEDEN SWITZE DENMAR FINLAN groupe Atlantique USA et NIRELA Les deux premiers groupes sont subdivis s en deux sous groupes que l on distingue ais ment par l importance de l cart entre les niveaux de jonction Il est int ressant de constater que dans les deux calculs la FRANCE ne se rattache pas ses soeurs latines que sont l ITALY et SPAIN mais AUSTRI et WGERMA Ce qui confirme la th se de Mr E Todd qui soutient contrairement aux id es re ues que France et Allemagne se ressemblent beaucoup quant aux comportements sociaux NIRELA SSE USA FRANCE AUSTRI WGERMA SPAIN
122. tion d un point p riph rique 3 2 S lection de deux points p riph riques 3 3 S lection de deux points noyaux 4 Le probl me des inversions 5 Application aux exemples 5 1 Donn es PSYSOC 5 2 Donn es PHYTOS 6 Conclusion 7 Proc dure de calcul CHAPITRE 8 Aides a l interpr tation 1 Variables quantitatives 1 1 Interpr tation d une partition 1 2 Interpr tation d une hi rarchie 2 Variable qualitatives 2 1 Interpr tation d une partition 2 2 Interpr tation d une hi rarchie 3 Application aux exemples 3 1 Donn es Psysoc quantitatives 3 2 Donn es Phytos qualitatives 4 Les proc dures d aide l interpr tation CHAPITRE 9 Pratique de la classification 1 Choix d un algorithme l l Dimensions des donn es 1 2 Nature des donn es 1 3 Qualit des r sultats 1 4 Temps de calcul 2 Strat gies 2 1 Hi rarchie puis centres mobiles 2 2 Centres mobiles suivis d une hi rarchie 2 3 Donn es h t rog nes emploi de l analyse factorielle pr alable 3 Interpr tation des r sultats 4 Un programme suppl mentaire utile troncature d une partition CHAPITRE 10 Conclusion 1 Taxinomie de qualit 1 1 Pr paration des donn es 1 2 Traitement 1 3 Interpr tation des r sultats 2 Classification en tant que pr traitement 2 1 Pr paration des donn es 2 2 Traitement 2 3 Interpr tation ANNEXE 1 Les indices de ditances 1 G n ralit s 2 Cas des donn es binaires 2 1 Indic
123. tion de variantes personnelles qui ont trop souvent pour but de fournir des r sultats en accord avec l hypoth se que l on veut d montrer La multiplicit des algorithmes de classification ne doit pas faire oublier la multiplicit encore plus grande des traitements pr liminaires des donn es souvent indispensables voir chapitre 2 et qui sont g n ralement d cisifs pour la qualit des r sultats cf Benz cri J P 1973 Benz cri J P et F 1980 ANNEXE 1 Les indices de distances N B Dans ce qui suit on utilise les signes math matiques classiques suivants V pour tout ou quel que soit appartenant gt implique k xx somme de tous les termes analogues Xi Xz etc en faisant varier l indice k Cette somme s crit aussi X xx K 1 2 n 1 G n ralit s Intuitivement un indice de distance d est une formule qui permet de mesurer de combien diff rent deux des objets que l on tudie C est une valuation de leur dissemblance math matiquement si I est l ensemble de ces objets d est une application fonction de I x I dans l ensemble R des nombres r els positifs ou nuls dont on exige 1 V ie d i i 0 2y Va Sp ir eI d i i d i i Si de plus on a in galit triangulaire 3 V i i i e I d i i lt dqd i i d i i alors d est une v ritable distance mais cette derni re condition n est pas indispensable pour la bonne marche des proc dures d
124. tions suivantes 1 Pour chaque classe q d terminer le centre de gravit g 2 R affecter chaque objet 1 la classe C 1 dont le centre de gravit est le plus proche C 1 q si et seulement si d 1 g min d i gr r e Qj 3 Retourner en 1 tant que surviennent des modifications dans la composition des classes Cet algorithme tr s simple repose sur d int ressantes propri t s math matiques que l on va examiner maintenant Ses avantages et inconv nients seront discut s au paragraphe 1 3 Les d veloppements math matiques inhabituels du paragraphe 1 2 sont n cessaires car ils seront utilis s galement au chapitre suivant qui expose une construction ascendante hi rarchique importante par la qualit des r sultats qu elle fournit 1 2 Moment d ordre deux d une partition Par souci de simplification on suppose que toutes les variables au nombre de p sont quantitatives et que la dissemblance entre les objets est correctement mesur e par la distance euclidienne d usuelle On appelle x i j la valeur de la j me variable pour la i me observation On suppose en outre que ces observations au nombre de n sont pond r es par des masses not es mi proportionnelles au r le que l on veut leur faire jouer Par exemple si l observation i repr sente l individu moyen d une sous population on peut d cider que mi est l effectif de la sous population S il n y a pas lieu de pond rer les observations on affectera la valeur 1 t
125. ubert 1973 La m thode de Hubert diff re de la pr c dente en ce que les scissions successives sonr initi es par les deux points les plus loign s de la classe scinder Hubert a propos diverses variantes de sa m thode qui ne diff rent entre elles que par le mode d affectation qui est toujours bas sur les distances aux deux points les plus loign s de la classe scinder Ainsi dans la variante la plus l mentaire si un objet est plus proche du premier que du second de ces points il est mis dans la premi re classe Sinon il est affect l autre classe Les autres variantes consistent examiner les distances rang es par ordre croissant On n affecte alors un objet une sous classe que s il est suffisammnent proche de l un ou de tous les objets d j affect s cette sous classe Les r sultats obtenus par l un ou l autre des algorithmes de Hubert ne donnent pas non plus satisfaction Nous pensons que l affectation bas e sur les distances aux points les plus loign s est discutable En effet ces points sont souvent des observations accidentelles voire aberrantes et en tous cas non repr sentatives des grandes masses de la classe consid r e De sorte que la dichotomie qui en r sulte ne repr sente pas correctement la r partition des objets de la classe 3 3 S lection de deux points noyaux m thode de Roux 1995 Soit q un sous ensemble de l ensemble I des objets classer On examine un certain nombre de p
126. ul des distances du Khi 2 et la proc dure DisJac pour le calcul des indices de distance de Jaccard La proc dure DisEuc calcule les distances sur les donn es telles qu elles sont pr sent es dans la feuille active du classeur Excel il appartient l utilisateur d effectuer une standardisation pr alable des donn es si cette op ration est n cessaire En g n ral dans les trois proc dures les distances sont calcul es entre les lignes du tableau Pour effectuer le calcul entre les colonnes il faut donc recopier les donn es avec transposition dans une nouvelle feuille Cependant la proc dure DisJac peut calculer les distances de Jaccard sur les lignes ou sur les colonnes En effet cette proc dure est destin e traiter des donn es phytosociologiques dans lesquelles il y a souvent un tr s grand nombre d esp ces Or si ce nombre d passe 255 le tableau ne peut pas tre dispos avec les esp ces en colonnes Dans cette ventualit on peut mettre les esp ces en lignes et les relev s en colonnes selon l usage et travailler tout de m me sur les relev s Pour la commodit de la lecture et par souci d homog n it les r sultats se pr sentent sous la forme d un tableau carr sym trique par rapport la premi re diagonale qui elle ne comporte que des Z ros Chapitre 4 La construction ascendante hi rarchique 1 G n ralit s 1 1 Principe g n ral des constructions ascendantes On suppose que les distances
127. ur somme pour toutes les variables et exprim es en pourcentage de cette somme 2 Variables qualitatives Dans le cas de variables qualitatives le calcul du centre de gravit n aurait pas de sens On ne peut donc pas utiliser les formules du paragraphe pr c dent En revanche on dispose d un crit re bien adapt notre probl me la formule du Khi deux de contingence entre deux variables On peut en effet consid rer une partition en k classes comme une variable qualitative k modalit s ou tats Le Khi deux de contingence entre une variable et les classes d une partition indique le degr de liaison de cette variable avec la partition Dans le cas d une hi rarchie on consid rera le r le des variables noeud par n ud un n ud tant consid r comme une variable qualitative deux cat gories en effet tout objet de la classe associ e au noeud appartient l une ou l autre des sous classes associ es aux deux branches r unies Rappelons la formule du Khi deux cette quantit est gale la somme des carr s des carts entre effectifs observ s et effectifs th oriques pond r s par les effectifs th oriques Khi 2 X effectifs observ s effectifs th oriques effectifs th oriques Dans le cas d un tableau de contingence o les effectifs e se r partissent dans un tableau dont les lignes sont indic es par la lettre k et les colonnes par la lettre 1 cette formule devient Khi 2 22 Xi ex l Cay m
128. v nient on peut utiliser une formule de distance particuli re appel e m trique du khi deux qui fait intervenir la fois les poids xj des lignes et xj des colonnes Ces poids ne sont autres que les sommes des termes de la ligne i ou de la colonne j da i i Ej 1 x j xij xi xi j xi 1 Les termes de chaque ligne i sont rapport s leur somme xi Une variable j contribue la distance en raison inverse de son poids x j Une autre solution int ressante s offre nous que nous allons examiner en d tail ci dessous 1 2 Pr traitement par l Analyse factorielle Cette op ration consiste effectuer avant la classification soit une Analyse en composantes principales ACP soit une Analyse factorielle des correspondances AFC selon ce qui parait le mieux adapt aux donn es et aux objectifs poursuivis On prend alors comme nouvelles donn es pour la classification les coordonn es des objets sur les premiers axes factoriels obtenus c est dire ceux qui apportent le plus d information cf Benz cri 1980 Foucart 1982 Volle 1978 etc Bien qu il implique beaucoup de calculs ce d tour vaut la peine d tre fait car il pr sente de nombreux avantages I Le plus important d entre eux est que l Analyse factorielle fournit des nouvelles variables non correl es entre elles et limine donc la derni re difficult examin e ci dessus 2 Le d licat probl me du choix de la distance initiale se trouve
129. vena versicolor Vill Botrychium lunaria L Sw Campanula scheuchzeri Vill Carex sempervirens Vill Strict Cirsium acaule L Webb Crepis aurea L Deschampsia flexuosa L Trin Draba aizoides L Elyna myosuroides All Erygeron sp Euphrasia minima L Festuca halleri Festuca macrophylla Degld Festuca violacea Galium pumilum Lmk Gentiana alpina Vill Gentiana campestris L Gentiana kochiana Per Gentiana nivalis L Gentiana punctata L Gentiana verna L Ry Song 1 Geum montanum L L Gregoria vittaliana D Hieracium glaciale Reyn Hieracium pilosella L Homogyne alpina L Cass Juncus trifidus L Leontodon helveticus Leontodon pyrenaicus Gouan Lotus corniculatus Luzula spicata L Minuarta rupestris Nardus stricta L Pedicularia rostratospicata Phyteuma hemisphericum L Phyteuma orbiculare L Duby Lach DC Scop Sch Potentilla aurea L Potentilla grandiflora L Pulsatilla vernalis L Ranunculus pyrenaicus L Sagina glabra Willd Fenzl Sagina linnaei Presl Salix herbacea L Sempervivum arachnoideum L Sempervivum montanum Jacq Thymus serpillum L Lyka Trifolium alpinum L Trifolium badium Schreb Trifolium pratense ssp nival Trifolium thallii Vill Veronica allionii Vill Veronica bellidioides L Veronica serpyllifolia L y pr sence 1 ou absence 0 de 66 esp ces v g tales dans 16 relev s du Plateau d E
Download Pdf Manuals
Related Search