Article - La Revue MODULAD
Contents
1. ce qui correspond au profil 0 0 0 0 gt gt ou 0 0 0 LOS2. F 069 1984 P MICHAUD Agr gation la majorit Hommage Condorcet Etude IBM n F 051 1982 LB a Annexe 1 Formule de calcul du CCC Cubic Clustering Criterion a Calcul de R pour une population uniform ment distribu e dans un hypercube de b dimension p Soit s la longueur du c t de l hypercube dans la j me dimension Nous supposerons que les sj sont class s par ordre de valeur d croissante Le volume de l hypercube est p v I Sj j 1 Pour q classes choisies dans cette population de distribution uniforme on peut supposer celles ci contenues dans q hyper cubes inclus dans l hyper cube initial dont la longueur moyenne c du c t sur chaque dimension sera telle que c 2yue q Le rapport Uj Sj c inf rieur l unit repr sente le nombre d hypercubes contenus le long de la j me dimension de l hypereube initial La variance totale de la population dans la direction j est proportionnelle sj tandis que la variance intra classe est proportionnelle C p e j 1 D o R 1 2 p 24 x Prise en compte d une dimension inter classes inf rieure p Cette dimension inter classes soit p sera obtenue comme le plus grand entier plus petit que q nombre de classes tel que uj S C soit plus petit que 1 On supposera alors que les classes sont des hypercubes de c t gal C sur les p premi res dimensions et de c t gal sj sur les dimensions restantes rang sup rie
3. mettre en oeuvre pour ex cuter les essais successifs requis ou les encha nements de proc dures Les logiciels d analyse de donn es se doivent aujourd hui d offrir une telle souplesse d utilisation La seconde partie veut ouvrir une voie concurrente la trop classique utilisation du crit re de la variance en montrant que dans le cas qualitatif il est possible aussi d optimiser avec le crit re de De La Vega un crit re de choix du nombre optimal de classes Seulement utilis e titre exp rimental cette seconde m thode aujourd hui d impl mentation informatique plus lourde pourrait avec les progr s des moyens de calcul faire valoir ses qualit s de robustesse et de r f rence un crit re beaucoup plus intrins que Dans les deux cas notre philosophie reste fond e sur l optimisation d un crit re pour le probl me de classification et l utilisation conjointe cette fin pour les populations de grande taille d une m thode non hi rarchique et d une m thode hi rarchique 63 R f rences a 2 31 4 15 6 7 8 9 10 11 12 13 14 C PERRUCHET Une Analyse Bibliographique des preuves de classifiabilit en Analyse des Donn es Statistique et Analyse des Donn es 1983 Vol 8 n 2 pp 18 41 Association des Statisticiens Universitaires J L MOLLIERE The best mode of use for the CCC SEUGI85 Proceedings of the third annual Conference in COLOG
4. 9 1 1 2 T 1 E 10 3 2 R 1 1 2 O 11 i 2 12 1 13 1 1 14 1 1 15 od dada dt i A a o a N 1 3 5 7 9 11 13 15 17 19 21 23 NOMBRE DE CLASSES Figure 10 GRAPHE DU CRITERE EN FONCTION DU NOMBRE DE CLASSES Trade Le CCC redevient n gatif ce qui n emp che pas cependant vu la forme de la courbe de prendre en compte les deux indications fournies confirmation d une partition significative en 6 classes et mise en vidence d un autre niveau significatif 8 classes qui sera finalement retenu Un compromis est donc trouver entre des courbes significatives du CCC dont les valeurs ne soient pas trop n gatives et une sous population d effecfif suffisant pour ne pas trop perdre en finesse de description 5 Un param tre suppl mentaire le nombre de facteurs La condition d utilisation du CCC tant la non corr lation des variables voir I on fera donc pr c der la classification d une analyse en composantes principales ou d une analyse des correspondances suivant la nature des variables initiales quantitatives ou qualitatives Un probl me important est donc celui du choix du nombre de facteurs retenir pour la classification Nous conseillons de retenir un nombre de facteurs l g rement sup rieur au nombre de ceux qui sont bien interpr t s dans l analyse factorielle La population choisie pour illustrer l emploi de la proc dure MCLAS dans le paragraphe 111 3 figure 8 r
5. en g n ral voisines donnera un nombre plus ou moins lev de formes fortes Celles ci r unissent des observations qui se sont toujours trouv es dans la m me classe au cours des diverses exp riences La raison th orique voir th or me 3 dans 8 nonc dans le chapitre B pour pr f rer les formes fortes une partition quelconque est qu elles doivent normalement conduire dans la phase 2 agr gation hi rarchique de meilleures valeurs du crit re de classification aux diff rents niveaux ce qui sera v rifi en pratique On obtient ainsi la proc dure que nous nommons MCLAS un peu plus co teuse en temps calcul que la proc dure MCLASI mais fournissant de meilleures partitions et parfois seule capable de donner une indication s re du nombre de classes le plus significatif 3 Obtention des classes finales Les proc dures MCLAS1 et MCLAS doivent permettre l utilisateur de d terminer le nombre de classes jug le plus significatif correspondant un niveau de la classification hi rar hique obtenue dans la phase finale de chacune de ces deux proc dures T est conseill l utilisateur d optimiser du point de vue du crit re de la variance la partition correspondante en encha nant un algorithme du type K Means ou un algorithme d change susceptible de donner encore une meilleure valeur du crit re 38 III Mode d emploi des proc dures MCLAS1 et MCLAS en fonction de la nature des do
6. m me lev et continuant une croissance positive r v lent une population classifiable 40 PROCEDURE MCLAS GRAPHE DU CRITERE EN FONCTION DU NOMBRE DE CLASSES RONA OEMRRAUGTN Ne van 27 se a s z A E E E ne E w 33 333 333 233 2222 122222 31 1111 1 39 A RA ES A A 4 s 12 37 21 239 29 393 37 NOMBRE DE CLASSES Figure 4 EO FRA IO ON RAT Ne 3 4 PROCEDURE MCLAS GRAPHE DU CRITERE EN FONCTION DU NOMBRE DE CLASSES emmmmemmmm tmmmmetmmmtmmsmtmmmmemmeme O mmms eme ae qu O E A SS 1109 9 213 217 31 25 29 33 3 NOMBRE DE CLASSES Figure 5 Dans ce cas on doit r p ter des essais pour essayer de mettre en vidence soit un maximum local stable du CCC tel qu on le voit appara tre dans 4 essais diff rents sur la figure 6 un accroissement tr s significatif et stable de la valeur du CCC pour un certain nombre de classes tel qu il appara t pour 5 classes dans les 4 essais de la figure 7 Un tel accroissement significatif peut souvent donner lieu un palier sur la courbe d volution du CCC On note ici compte tenu du caract re plus subjectif de l indication l importance de la validation par une observation r p t e sur des essais diff rents Si on ne peut pas mettre en vidence une telle indication on passera alors l utilisation de la proc dure MCLAS d crite dans le paragraphe suivant Cette utilisation peut rester souhaitable m me si une i
7. population en un nombre lev de formes fortes Savoir o s arr ter dans l accroissement du nombre de formes fortes par la r p tition des exp riences n est pas une question simple un crit re reste peut tre d finir mais d s pr sent il est possible de suivre l volution des effectifs des formes fortes au fil des exp riences et de noter quand une certaine stabilit est atteinte au moins concernant les formes fortes les plus importantes SRE wonm tuwn CUNA Nun 7 gt 5 gt r gt 2 3 b S s y y nu gt se e ps q and o one see Sue eee con dames gt a b paeroun Conseils pratiques Nous recommandons de faire diff rentes ex cutions de MCLAS pour diff rentes valeurs du nombre de classes par exemple entre 6 et 10 classes Dans chaque cas 5 exp riences valeur standard peuvent suffire si la stabilit des formes fortes importantes para t tablie population bien classifiable On comparera alors les courbes d volution du CCC en portant attention pour les diff rents niveaux significatifs aux plus fortes valeurs obtenues pour ce crit re Un maximum absolu entre toutes les courbes observ pour un certain nombre de classes peut tre un indice tr s significatif Une illustration de cette m thode est donn e par les graphiques de la figure 8 10 exp riences pour 6 7 8 9 classes La conclusion du choix d une partition en 7 classes provient la
8. deux premi res fonctions d agr gation essay es formules donn es en 1 et 2 du paragraphe A III furent abandonn es au profit de la fonction correspondant la m thode de Ward dans le cas non m trique qui conduisit des classes bien meilleures du point de vue de l quilibre de leurs effectifs en haut de l arbre La courbe d volution de l accroissement du crit re de LERMAN aux diff rents niveaux de la hi rarchie montre une partition significative en 11 classe figure 11 Phase d allocation des individus restants et d optimisation La m thode des nu es dynamiques est utilis e la fois pour allouer en une it ration les individus restants autour de noyaux correspondant aux 11 classes trouv es pr c demment puis pour optimiser cette partition en 11 classes de la population totale Une analyse des correspondances montre tr s peu de changement du point de vue de la signification des classes entre celles obtenues sur la sous population classifiable et celles obtenues apr s r allocation des individus restants ce qui confirme la pertinence de la sous population s lectionn e du point de vue du probl me de classification pos 69 3 Comparaison des classifications obtenues par les deux approches m trique et non m trique Six classes sont identifi es de la m me fa on par les deux m thodes Les diff rences proviennent la fois des individus extr mes et des individus moyens qui paraissent moins bien
9. effectifs Ensuite nous montrerons comment l algorithme des nu es dynamiques de m me qu une m thode de classification hi rarchique adapt e peuvent contribuer optimiser ce crit re et gr ce son caract re intrins que d terminer un nombre de classes optimal L int r t de l ensemble de la proc dure sera galement ici d utiliser la classification hi rarchique sur un nombre pas trop lev de classes initiales qui seront en l occurence les formes fortes obtenues par les nu es dynamiques La m thode est limit e des tailles de population pour lesquelles la matrice des similarit s peut tre stock e en m moire elle a t appliqu e un jeu de donn es de mille individus d une enqu te pr c demment classifi s suivant la proc dure du chapitre A partir d une repr sentation m trique des donn es par une description des individus sur les premiers facteurs d une analyse des correspondances La comparaison des approches m trique et non m trique s est r v l e tout fait int ressante pouvant plaider en faveur de cette derni re m me au prix d une impl mentation informatique plus lourde temps calcul et place m moire Cette m thodologie originale a t pr sent e en 9 I Crit re de De La V ga 1 D finition initiale 10 Il s agit d un crit re d ad quation entre une partition 11 D d un ensemble D d objets classifier et une structure de proximit P D sur ces objets 2169 5 C
10. n 26 a 15 12 A e A A sons duo lues Se 33 3333 3 22233 222 u au 1 7 A AS 19 21 55 29 33 37 NOMBRE DE CLASSES c v a 1 e L v 2 e a 1 G e R I L z R 1 o x a 24 en CA z e N gt 27 21 1 15 3 6 GRAPHE DU CRITERE EN FONCTION DU NOMBRE DE CLASSES RS E EEE EEE REA E A AA 1 9 13 17 21 25 29 33 9 NOMBRE DE CLASSES GRAPHE DU CRITERE EN FONCTION DU NOMBRE DE CLASSES 33 3333 222222 22 32 n ma Gs 23 A A A A E DS 1 5 3 13 17 21 25 29 33 3 NOMBRE DE CLASSES EXECUTIONS PROCEDURE MCLASI Figure 7 ui 3 Utilisation de la proc dure MCLAS ulation classifiable a G n ralit s La proc dure MCLAS d pend de deux param tres le nombre d exp riences correspondant diff rentes initialisations de l algorithme de classification non hi rarchique dont la valeur par d faut est gale 5 le nombre de classes fix pour ces exp riences De ces deux param tres d pend le nombre de formes fortes intersection des diff rentes partitions qui seront soumises la classification hi rarchique L int r t des formes fortes par rapport aux classes d une partition a priori en un nombre lev de classes proc dure MCLAS1 est qu elles sont de taille tr s in gale en raison de la strat gie d agr gation de Palgorithme hi rarchique utilis m thode de WARD l
11. rectangle de dimension p p tant le nombre de variables On peut trouver une formule d approximation de E R d pendant de n nombre d unit s classifier q nombre de classes p nombre de variables Le CCC est alors calcul par la formule 1 ER CCC Ln 1 R a est un coefficient empirique pour stabiliser la variance du CCC lorsque varient les param tres n p 1Xa etq La formule exacte de calcul du CCC est donn e en Annexe 1 Suivant les valeurs positives ou n gatives du CCC on concluera au rejet ou l acceptation de l hypoth se nulle d absence de classes Une partition sera jug e d autant plus significative que la valeur positive du CCC est lev e Pe La v ritable hypoth se alternative est pour la population tudi e d tre issue d un m lange de distributions multi normales de m mes matrices de variance covariance avec des probabilit s gales d chantillonnage pour les diff rents composants Il s agit l des conditions d utilisation optimales du R2 dans les probl mes de classification 5 ce crit re comme le CCC n tant donc pas adapt la reconnaissance de classes de forme allong e ou irr guli re Deux remarques importantes peuvent tre faites Remarque 1 Le calcul de E R servant de base au calcul du CCC est effectu partir des p variables de classification en supposant que celles ci sont non corr l es Pour interpr ter les vale
12. rence entre le nombre de paires d objets de D avant une similarit inf rieure s i j et le nombre de paires d objets ayant une similarit sup rieure s i j Cette d finition reste vraie m me s il y a des paires ex aequo dans l ordre sur les valeurs des similarit s s i j En l absence d ex aequo la quantit W j la propri t remarquable suivante Y Wi 0 12 a 0 Le formalisme des comparaisons par paires 13 permet done de donner au probl me de la recherche de la partition maximisant le crit re de De la Vega une formulation tr s simple quivalente la r gle de la majorit du crit re de Condorcet 14 on d cidera de r unir dans une m me classe deux objets i et j Y j 1 si le nombre de couples d objets moins ressemblants que i et j l emporte sur le nombre de couples d objets plus ressemblants quei etj Interpr tation statistique du crit re Si l on d finit Z p q Y p Y a p q F et se rappelant la d finition de O p q voir paragraphe 3 alors S CHAH a montr 12 que maximiser le crit re de De la Vega parmi toutes les partitions de l ensemble D quivaut rechercher Z O tant donn qui maximise Cov Z 0 La covariance est donc caleul e sur l ensemble F X F de tous les couples p q de paires d objets Se rappelant par ailleurs la valeur calcul e par LERMAN de la variance du crit re de De la Vega on peut ramener la maximisation du crit re de De la Vega
13. 4 15 6 A7 18 14 2 21 22 2 NOMBRE DE CLASSES Figure 9 LAS 0 Cette m thode a t mise en oeuvre sur la population dont le caract re tr s peu classifiable a t mis en vidence sur la figure 9 Soumettant cette population d environ mille individus 20 exp riences 4 ex cutions encha n es de la proc dure MCLAS de classification non hi rarchique en 8 classes nous avons obtenu 571 formes fortes 467 d entre elles tant form es d un seul individu Les quatre graphiques de la figure 5 repr sentent le r sultat de l application de MCLAS1 trois sous populations diff rentes la premi re obtenue en supprimant les formes fortes de un et deux individus deux essais diff rents population r duite 435 individus la seconde excluant les formes fortes de trois individus et moins 387 individus la derni re celles de quatre individus et moins 352 individus Cette derni re sous population r sultant de l limination la plus s v re des individus atypiques donne des valeurs plus lev es du crit re figure 6 c Les quatre graphiques concluent nettement une partition en 6 classes Enfin un essai par la proc dure MCLAS figure 10 a t r alis sur une population un peu plus nombreuse n excluant que les seules formes fortes d un individu o 1 1 1 1 1 Os1 1 1 29 1 t t C 3 1 v 1 7 B 1 1 I 4 e 1 1 cC 5 L 1 u 1 S 6 2 T 1 E 1 3 R 7 I 1 N 1 G 8 5 2 Le 1 R
14. D EP Or le crit re de De La Vega sous son expression 3 peut encore s crire k S YGDxWGD D gt wo j 1 i 1 DEP puisque Y vaut 1 ou 0 suivant que les objets j et l appartiennent ou non la m me classe L algorithme des nu es dynamiques peut donc optimiser le crit re de De la Vega si l on choisit comme indice de similarit entre objets la quantit W d finie en 1 3 56 Cette utilisation de la m thode des nu es dynamiques avec des noyaux de taille variable n est pas classique Bien que v rifi e en pratique la convergence reste prouver th oriquement En r alit l optimisation du crit re de De la Vega nombre de classes fix comporte l inconv nient de favoriser des classes d effectif in gal Nous montrons l Annexe 2 que pour un nombre de classes fix la variance du crit re de De La Vega cro t lorsqu on augmente jusqu un certain point le d s quilibre des effectifs des classes Nous v rifierons galement ce point lorsque nous chercherons au chapitre suivant HI un algorithme hi rarchique optimisant le crit re de De La Vega Nous serons amen s pour ne pas obtenir des classes d effectifs trop d s quilibr s chercher un quivalent du crit re de la variance dans le cas non m trique Cela quivaut ici pour l algorithme des nu es dynamiques pr f rer des noyaux form s seulement de quelques objets repr sentatifs On se rapproche ainsi de la notion de centre co
15. La revue de Modulad STRATEGIE DE CLASSIFICATION POUR DE GRANDS ENSEMBLES DE DONNEES J L MOLLIERE E D F Direction des Etudes et Recherches Service IMA 1 avenue du G n ral de Gaulle 92141 CLAMART T l 47 65 43 21 R sum L objectif principal est ici le choix du nombre optimal de classes comme pr alable la solution du probl me de classification sur une population de taille importante Des r ponses satisfaisantes exp riment es en pratique sont ici apport es s appuyant sur l utilisation de crit res ad quats et la mise en oeuvre des algorithmes classiques de classification hi rarchique et non hi rarchique pour leur optimisation Mots cl s Classification automatique classifiabilit nombre de classes crit re de la variance crit re de De La Vega nu es dynamiques K means m thode de Ward formes fortes ANA Introduction En d pit de la difficult d finir des crit res de choix d un nombre de classes optimal dans une population classifier fond s sur des tests rigoureux se r f rant des hypoth ses nulles de non classificabilit ou des hypoth ses alternatives d existence d une structure de classification 1 les utilisateurs sont bien amen s dans la pratique s appuyer sur des crit res remplissant pour le moins la fonction d indicateurs Le plus courant d entre deux pour des attributs num riques est le crit re R de variance expliqu e par une partition L int r t
16. NE SAS Software Limited Warren S SARLE Cubic Clustering Criterion SAS Technical Report A 108 SAS Institute Inc Box 8000 CARY NC 27 511 8000 USA MILLIGAN G W et COOPER M C 1985 An examination of procedures for determining the number of clusters in a data set PSYCHOMETRIKA 50 159 179 G CELEUX Classification et mod les Revue Statistique Appliqu e 1988 XXXVI 4 43 58 J L MOLLIERE B GERARDIN Macro for determining the optimal clusters in large data sets SEUGI 84 Proceedings AMSTERDAM April 4 6 1984 Edwin DIDAY Optimisation en Classification Automatique et Reconnaissance des Formes Revue Fran aise d Automatique Informatique Recherche Op rationnelle RA LR O 6 me ann e Novembre 1972 Vol 3 pp 61 96 DUNOD Paris Edwin DIDAY Optimization in non hierarchical clustering Pattern Recognition 1974 Vol 6 pp 17 33 PERGAMON Press Jean Luc MOLLIERE What s the real number of clusters Classification as a tool of research W GAUL and M SCHADER Editors NORTH HOLLAND 1986 BENZECRI et Collaborateurs L Analyse des Donn es 1 la Taxinomie DUNOD 1973 LC LERMAN Classification et analyse ordinale des donn es DUNOD 1981 S CHAH Calcul des partitions optimales d un crit re d ad quation une pr ordonnance Data Analysis and Informatics HI North Holland 1984 F MARCOTORCHINO Utilisation des comparaisons par paires en statistique des Contingences Etude IBM n
17. S DA NONNNANNN BURN Aaa PROCEDURE MCLAS GRAPHE DU CRITERE EN FONCTION DU NOMBRE DE CLASSES H H ma LJ M s i 3 2 3 4 i 1 L 1 1 1 5 1 6 i 1 1 s s H 1 Ly t 1 H i 1 n 1 3 a 4 H i 2 4 A A E E EE PE E EES E EA EEES s 4 ve sy y kad 1 v 2 at 22 23 2 a 3 NOMBRE DE CLASSES Figure 8d EXPERIENCES AVEC 9 CLASSES 4 Utilisation de MCLAS pour des populations non classifiables M thodologie Une population non classifiable se reconnait aux valeurs tr s n gatives du CCC sur la courbe d volution de ce crit re en fonction du nombre de classes apr s utilisation de la proc dure MCLAS1 L utilisation de la proc dure MCLAS fournira des valeurs moins n gatives du crit re mais la courbe demeurera nettement en dessous de z ro Un exemple d une telle courbe obtenue par MCLAS sur ce type de population est donn e sur la figure 9 En face de cette situation nous proposons de d finir une sous population plus classifiable Celle ci sera obtenue en liminant de la population initiale des objets ou groupes d objets ayant montr une grande instabilit pour se rattacher une classe caract ristique de la population initiale La mise en vidence de ces classes caract ristiques formes fortes comme celle des l ments instables se fera en augmentant le nombre d exp riences dans la proc du
18. ant un tr s grand nombre d unit s classer on observe alors dans les derniers niveaux des valeurs tr s m diocres du crit re de classification ainsi qu une volution tr s monotone de celui ci rendant difficile la d tection de niveaux plus significatifs Les pointes de significavit sont amorties par le bruit important r sultant de la somme des erreurs commises dans la suite des tr s nombreux regroupements Un tel type de courbe est donn pour le crit re du CCC sur la figure 2 pour une population de 1000 individus class e par la m thode hi rarchique de Ward crit re de la variance Ce graphique devra tre compar ceux obtenus en suivant la m thodologie que nous proposons Remarque Cette solution combinant classifications non hi rarchique et hi rarchique nous a paru l exp rience 6 pr f rable une m thode consistant comparer les valeurs du crit re pour diff rents nombres de classes obtenues par un algorithme de classification non hi rarchique La raison en est la variabilit des valeurs du crit re pour un nombre de classes donn pour diff rentes initialisations rendant d licate et co teuse en temps calcul la mise en vidence d un nombre de classes optimal 362 27 24 21 18 15 12 6 LOMVMIMMN OA MIDA AN vw gone tmimee pommes mme e mr venue A o toner 9 13 17 21 25 29 33 37 41 to un NOMBRE DE CLASSES Figure 2 2 Miseenoeuvre La m thodolo
19. ase de cette m thodologie 1 L int r t des m thodes de classification hi rarchique pour juger des niveaux de partition les plus significatifs La courbe d volution du crit re de classification aux diff rents niveaux de regroupement de l arbre hi rarchique peut donner une r ponse globale au probl me du choix du nombre de classes On pr f rera ici videmment le CCC comme crit re au classique R2 en se rappelant toutefois que l volution du CCC sous l hypoth se nulle n est pas absolument ind pendante du nombre de classes 1 Remarque 2 E 2 L inconv nient d utiliser une m thode hi rarchique sur un nombre trop important d unit s statistiques classer Au del de quelques centaines d observations il devient impossible de faire clairement appara tre une structure en classes plus significative dans les derniers niveaux d agr gation de l arbre qui sont justement ceux auxquels on s int resse en pratique Cela r sulte du fait que les derniers niveaux de regroupement cumulent les erreurs d cart Poptimum des partitions obtenues tous les niveaux pr c dents Il est connu en effet qu un niveau donn la partition n est jamais optimale pour le crit re de classification consid r mais est d une certaine mani re d pendant de l algorithme d agr gation seulement localement optimale par rapport au niveau de partition pr c dent Sur les courbes d volution du crit re pour des arbres agr ge
20. asses on a donc ni Jin di entier Si n cessaire on multiplie tous les effectifs par un facteur entier tel que J soit le plus petit entier tel que k Y 3 K3 i l On notera RL et S e les valeurs de R et S correspondant une partition en K classes d effectifs gaux J n de la population d effectif total N Pour la partition consid r e on a alors IR Sle A et S Sle A K D J K as Tix a 2 k et 2 J KJ iT Appelons E la quantit suivante E R X S Rlo x So E A X ISl IRle Al 2467 amp Variation de E en fonction des effectifs des classes a est toujours positif ou nul et d autant plus grand que les effectifs sont d s quilibr s Le signe de E d pend donc du signe de la quantit S e R A qui s exprime K KK gt 32 KJ ISle IRle A a 8 b Etude du signe de 3 La quantit 3 peut s crire K2J2n 1 13 KJ 2 1 a iej 2 res En posant J L _ KJ Ci l expression 3 devient en se rappelant que KJn N 2 Es S xa S x 1 2 NR ANA Le EN Sans le terme 1 l expression ci dessus entre crochets serait toujours positive ou nulle K Hors mis le cas de deux classes o l expression 3 sera n gative d s qu on s loignera un tant soit peu du cas de classes quilibr es si N est grand cette expression ne deviendra n gative que dans un domaine de valeurs de X _proches de 0 ou de 1 et d autant plus res
21. avec le crit re de De La Vega suivi les tapes suivantes a Calcul des similarit s entre individus Nous avons choisi pour mesurer la similarit entre deux individus la quantit tr s simple gale au nombre de modalit s de toutes les variables consid r es poss d es en commun par les deux individus Les rangs de ces similarit s devront ensuite tre calcul s par un algorithme de tri sur toutes les similarit s pour calculer l indice W n cessaire au crit re de la Vega pour toute paire Gj d individus lt 6l b c d e Obtention des formes fortes par les nu es dynamiques 15 exp riences des nu es dynamiques donnant des partitions en 8 classes ont t r alis es chacune optimisant donc localement un crit re proche du crit re de de La Vega normalis R sultant de l intersection des 10 meilleures exp riences du point de vue du crit re environ cinq cent formes fortes ont t obtenues sur une polulation initiale d environ mille individus ce nombre lev est un crit re du caract re peu classifiable de la population S lection d une sous population plus classifiable Suivant la m thode pr sent e au chapitre A H 4 nous liminons les formes fortes form es d un seul individu ou montrant une faible coh sion voir plus haut la d finition de la coh sion interne Nous conservons ainsi 97 formes fortes compos es de 438 individus sur les 1012 initiaux Classification hi rarchique Les
22. c les fonctions pr c dentes r sultent de la tendance naturelle du crit re de De la Vega d j signal e plus haut II 2 favoriser des classes d effectifs in gaux Nous pouvons le comprendre d une autre mani re en examinant la forme que prendrait le crit re sur des dissimilarit s correspondant de vraies distances Maximiser le crit re de De la Vega quivaudrait alors en terme de variance minimiser la quantit k y n Var Var Var variance de P i 1 Var variance totale n effectif de Pi ce qui est encore quivalent maximiser k gt n Var Var i 1 On constate que le coefficient nj favorisera des classes d effectif important m me si leurs variances sont plus grandes que celles de classes plus petites Par contre le crit re de Ward connu pour donner des classes plus quilibr es maximise la quantit k gt n Var Var i 1 io Partant de la forme du crit re de Ward et exprimant les distances en terme de dissimilarit s nous en d duisons la fonction d agr gation correspondante dans le cas non m trique D wo Y wap RAB 2 Y y Wie n ny E EE aCA hEB DA Mz L utilisation de cette fonction ne donnera pas d aussi bonnes valeurs du crit re de De la Vega que les deux fonctions d finies en 1 et 2 mais satisfaira la contrainte de classes d effectifs quilibr es C est cette fonction que nous retiendrons En r alit cette derni re fonct
23. chercher parmi toutes les partitions celle qui maximise le crit re d ad quation exprim en 1 R sultats de LERMAN 11 LERMAN a montr que maximiser l expression 1 quivaut maximiser Igr o N R X SI 3 KR X S Igr o N R X S 4 IRIX ISI 2 Susan A partir de cette expression LERMAN a prouv le r sultat suivant sur la distribution de toutes les partitions d un type donn c est dire en K classes d effectifs n1 no nx la moyenne statistique de l expression 2 du crit re de De la Vega est nulle sa variance est gale IRI X ISI X IRI ISi 1 12 et sa distributrion asymptotique est Gaussienne L importance de ce r sultat est de permettre par la normalisation du crit re de lui donner un caract re intrins que en liminant l influence de la taille de la population du nombre de classes et de leurs effectifs respectifs sur sa valeur absolue Lin arisation du crit re de De la Vega Said CHAH 12 a donn une nouvelle formulation tr s simple du probl me de maximisation de l expression 2 On d finit les fonctions Y p et O p q p et q tant des paires d objets donc l ments de F 1sipeR per Yp Osipes 1 sis p gt s q per Opa e sinon Alors le crit re de De la Vega peut s crire gt ve gt Opa 0 ap per CES ou encore en revenant aux objets i j de l ensemble D classifier YGD x WEP ijeD 8 irj WG j tant gal la diff
24. des m thodes de classification hi rarchique est alors d offrir globalement l volution des valeurs d un tel crit re aux diff rents niveaux Nous voulons dans cet article d une part montrer l int r t pratique de combiner classification non hi rarchique sp cialement par la m thode des nu es dynamiques et classification hi rarchique d s que les populations classifier d passent quelques centaines d individus d autre part montrer que d autres crit res ayant de meilleures propri t s que le crit re R sont d s pr sent utilisables pour appr cier le caract re classifiable d une population et d terminer le nombre de classes le plus significatif Une exp rience de plusieurs ann es d utilisation du Cubic Clustering Criterion CC dans le cadre du logiciel SAS 2 pour des variables quantitatives nous am nera proposer une strat gie de classification bas e sur l utilisation de ce crit re Par ailleurs nous montrerons que cette strat gie g n rale combinant classification non hi rarchique et classification hi rarchique peut galement s appliquer sur des donn es non m triques indices de similarit A Donn es num riques Utilisation du crit re du CCC Les m thodes m triques de classification automatique fond es sur le calcul de distances dans un espace appropri mesurent la qualit d une partition par le crit re R de variance expliqu e rapport de la variance inter classes entre les cen
25. e par l emploi de la proc dure MCLAS1 D une part cette proc dure est peu co teuse en temps calcul d autre part son utilisation est simple car ne d pendant que d un seul param tre le nombre de classes de la partition initiale standard gal 100 Nous sugg rons dans un premier temps de garder ce standard et de r p ter plusieurs fois l ex cution de MCLASI avec des initialisations diff rentes videmment Deux r sultats sont attendus de ces premiers essais lire sur la courbe d volution du CCC en fonction du nombre de classes le caract re classifiable ou non de la population et si oui l indication du nombre de classes retenir 39 Une courbe du type de la figure 3 correspond une population non classifiable Le CCC reste tr s n gatif dans toute la zone d volution du nombre de classes repr sent e sur le graphique et particuli rement entre 5 et 10 classes Pour traiter ce type de population il faut se reporter au paragraphe 4 PROCEDURE MCLASI GRAPHE DU CRITERE EN FONCTION DU NOMBRE DE CLASSES 3253 2 9 7 3 18 9 manemane a os a A aTa 6 e e G A mee O ma h a m aee maae ee ma ea aeae e 0 1 2 7 tt 1 1 LEA at 23 t Li ar 31 37 NOMBRE DE CLASSES Figure 3 Des courbes du type de la figure 4 valeurs positives lev es du CCC ou du type de la figure 5 g n ralement rencontr CCC prenant des valeurs positives seulement partir d un certain nombre de classes
26. elle ci est d finie par une pr ordonnance sur D c est dire un pr ordre total sur l ensemble de tous les couples d objets de D o le rang d une paire d objets est une fonction strictement monotone de la ressemblance de ces deux objets Plus pr cis ment cette ressemblance est mesur e par l indice de similarit s d fini sur toutes les paires d objets Pour la d finition du crit re de De La V ga on d finit F ensemble de toutes les paires d objets de D l ordre total tel que pour deux paires p et q de F p lt qe s p gt s q et le graphe correspondant dans FXF gr w p q F X F p lt q pour o Toute partition n peut aussi tre repr sent e dans F X F par le produit cart sien R X S o Rest l ensemble des paires r unies par la partition S est l ensemble des paires s par es par la partition Le cardinal de l intersection dans F X F de ces deux sous ensembles repr sentant l un la structure de proximit l autre la partition sera la base du crit re soit card gr w N R x S Le crit re lui m me dans sa d finition initiale est gal au cardinal du compl mentaire dans F xX F de la diff rence sym trique entre les ensembles gr w et R X S D notant le cardinal de A par Al et la diff rence sym trique entre les ensembles A et B par AA B le crit re de De La V ga s crit IF XF gr o A R X S a Le probl me de classification se r sume donc avec cette d finition re
27. entatifs pour retrouver la notion de centre m thode ascendante hi rarchique quivalente la m thode de WARD H s agit l seulement de moyens d optimiser le crit re de De la Vega sous la contrainte de classes quilibr es ou d une autre fa on de prendre en compte sa normalisation le crit re normalis appel crit re de LERMAN ne pouvant tre maximis directement mais restant le crit re final utilis Dans sa nature le crit re de De la Vega reste fondamentalement diff rent du crit re de la variance comme les r sultats ci apr s le montreront un int r t de son caract re non m trique tant ses propri t s intrins ques gr ce sa facilit de normalisation pour comparer entre elles des partitions diff rentes Mise en oeuvre pratique de la strat gie de classification Le jeu de donn es utilis correspondait une population de mille individus d crits par des r ponses 33 questions qualitatives modalit s exclusives d une enqu te d opinion population d j analys e par une m thode de classification sur variables quantitatives utilisant les cinq premiers facteurs d une analyse factorielle des correspondances pr alable et ayant montr son caract re difficilement classifiable C est sur cette population que fut appliqu e avec succ s la m thodologie d crite au chapitre AU 4 qui consuisit une classification en 8 classes figure 10 Nous avons ici pour une approche non m trique
28. es plus grosses d entre elles correspondant des regroupements tr s coh rents ne s agr geront qu en haut de l arbre ce qui se traduira n cessairement par une chute de la valeur du crit re de classification On est donc assur par cette m thode de mettre en vidence un maximum du crit re ou au moins une indication significative dans la zone du haut de l arbre o nous recherchons le nombre de classes optimal Moins les formes fortes seront nombreuses plus elles seront pour certaines d entre elles d effectif important do un maximum plus accentu de la courbe du CCC Cependant il est craindre si le nombre de classes et le nombre d exp riences ne sont pas assez lev s que l indication trouv e soit d pendante du nombre de classes choisi comme param tre En effet les formes fortes importantes correspondront alors aux classes des exp riences et on risque de retrouver ce nombre de classes ou plus souvent ce nombre major de 1 comme niveau significatif de l arbre Il est done souhaitable d obtenir un nombre de formes fortes assez lev et nous pr f rons pour ce faire r p ter un nombre plus grand nombre d exp riences en majorant le standard gal 5 ou en enchainant plusieurs ex cutions de la proc dure MCLAS ce qui est possible et permet defaire cro tre le nombre d exp riences de 5 en 5 plut t que d augmenter trop le nombe de classes initial on risque en effet de fragmenter de mani re artificielle a
29. fois des figures 8 c et 8 d saut significatif 7 classes pour deux partititons diff rentes des formes fortes mais aussi de la figure 8 a le maximum 8 est sans doute d au nombre initial de classes gal 7 mais le saut 7 est plus significatif et correspond surtout la plus forte valeur observ e du CCC de l ordre de 20 et dans une moindre mesure de la figure 8 b le maximum observ 7 d pendant pour une part du nombre initial de 6 classes ce qui sera d autant moins vrai cependant que le nombre d exp riences sera lev Une partition en 5 classes para t galement assez significative au vu des 4 graphiques pr c dents PROC DURE MCLAS GRAPHE DU CRITERE EN FONCTION DU NOMBRE DE CLASSES Le QD me me meme un nee A o pu G at mens 2 3 s s 6 7 s kid ma REUB SV v 49 39 29 22 23 azan NOMBRE DE CLASSES Figure 8a EXPERIENCES AVEC 7 CLASSES PAL EE Zommmin MN CENsmihcra Nica LC 12 12 mirra tos A tune mme mue dm MONA Arman As ee 2 vs 15 6 52 5 1 s 2 5 5 0 Toece enua oenue tamatea pane buna tene teun mme pm gun PROCEDURE MCLAS GRAPHE DU CRITERE EN FONCTION D NOMBRE DE CLASSES A AA A il y A kad 17 kad 49 20 239 23 23 n NOMBRE DE CLASSES Figure 8b EXPERIENCES AVEC 6 CLASSES PROCEDURE MULAS GRAPHE DU CRITERE EN FONCTION DU NOMBRE DE CLASSES mme 5 8 3 Ho n R U NBN 4 1 1 Y 2 29 22 2 2 NOMBRE DE CLASSES Figure 8c EXPERIENCES AVEC 8 CIASSE
30. gie propos e proc de en deux phases obtention partir de la population initiale classer d une partition en un nombre lev de classes par exemple de l ordre de la centaine application d une m thode de classification hi rarchique ascendante suivant la m thode de WARD sur les classes pr c dentes et analyse de la courbe d volution du crit re de classification CCC aux diff rents niveaux La premi re phase a pour but de r duire le nombre d observations soumises la classification hi rarchique 9 Pour cette premi re phase on peut soit proc der une classification non hi rarchique en un nombre fix assez lev de classes standard gal 100 Toutes nos classifications non hi rarchiques sont ffectu es avec une m thode de type K Means ou centres mobiles On obtient alors avec la phase 2 la proc dure que nous nommons MCL AS1 r aliser une partition en formes fortes 7 de la population initiale Cette partition s obtient en r alisant diff rentes classifications non hi rarchiques en un nombre de classes fix ce nombre compris en g n ral entre 5 et 10 classes peut d pendre de l ordre de grandeur du nombre de classes souhait pour la partition finale En standard on r alisera 5 exp riences avec des initialisations diff rentes conduisant 5 classifications correspondant chacune un optimum local du crit re de la variance L intersection de ces partitions
31. ion n optimise plus le crit re de De La Vega ayant la forme suivante S wid SY win E GD EP k GD EP n acus COS maisle crit re Er 4 i l n i 1 n 1 1 Ce crit re prenant en compte une contrainte de normalisation sur les effectifs des classes se rapproche d une certaine fa on du crit re de De la Vega normalis Or c est ce dernier que nous avons appel crit re de LERMAN qui demeure notre crit re de choix du nombre de classes a quantit j E La quantit WG D n sera appel e coh sion interne de la classe Pi et l expression 4 constituera ce que nous nommerons la coh sion globale de la partition Cette quantit qui peut tre n gative car S Ww j 0 xj sera un indicateur tr s commode pour analyser la qualit d une partition IV Application des donn es r elles 1 R sum sur le crit re optimis Si nous r sumons ce niveau les r sultats pr c dents le crit re de De la Vega peut tre optimis par la m thode des nu es dynamiques gr ce sa forme suivante k D YED WED gt S wD j 1 i 1 GDE W D tant un indice construit partir des similarit s initiales s j 1 260 2 Le besoin de normaliser ce crit re conduira aussi bien pour les nu es dynamiques que pour la phase de classification hi rarchique se rapprocher des conditions d utilisation optimales de ces m thodes pour le cas m trique noyaux r duits quelques objets repr s
32. it entre deux ensembles d objets A et B partir de l indice de proximit ou de similarit s entre les objets par la formule suivante R A B Y R aB gt gt sab atA atA bEB A l it ration de num ro j de la proc dure globale nous avons un ensemble NJ de noyaux soit Njj Nid pour les k classes et un ensemble PJ de classes soit Pi Py La convergence de la proc dure alternative de d finition des classes et des noyaux partir d une initialisation al atoire des classes ou des noyaux pour un nombre de classes fix peut tre prouv e sous un certain nombre de conditions g n rales A la convergence la solution finale NP est associ e un maximum local dans le cas d un indice de similarit du crit re suivant k RON P gt RON P i i Application au crit re de De la Vega Dans le cas particulier d un indice de dissimilarit correspondant une vraie distance dans un espace m trique et condition de repr senter chaque classe par son centre de gravit le crit re optimis par les nu es dynamiques est la somme pond r e des variances intra classes c est dire le classique crit re R voir chapitre A A l oppos et c est l un int r t de la notion de noyau si l on impose que chaque classe soit repr sent e par un nombre d objets gal l effectif de la classe alors il est facile de voir qu la convergence le crit re optimis sera de la forme k S D stp i 1 G
33. llons chercher dans un premier temps une m thode d agr gation permettant lors des regroupement ascendants d optimiser localement le crit re de De la Vega dont nous rappelons l expression ci dessous 5 YG X Waj Y Gj 1siietjsont r unisdans la m me classe ixj Y ij 0 sinon l indice W ij d fini partir des similarit s s ij voir 1 3 a la propri t remarquable d tre de somme nulle sur tous les couples ij condition qu il n y ait pas d ex aequo parmi les similarit s gt wap 0 ixj 58 L aigorithme de classificatoin hi rarchique est d fini par la fonction d agr gation R A B de deux classes A et B un niveau donn Souhaitant optimiser le crit re de De La Vega nous avons essay les fonctions suivantes 1 RAB Y Web acA bEB Il s agit d agr ger les deux classes qui apr s fusion maximisent le crit re En haut de l arbre on obtient quelques tr s grosses classes et de nombreuses classes d effectif tr s faible 2 R A B gt gt Wa b average linkage method NAB atA bEB Les classes en haut de l arbre sont un peu plus quilibr es mais encore de tailles tr s diff rentes Les valeurs du crit re de De la Vega dans les derniers niveaux sont comparables celles obtenues avec la fonction d agr gation pr c dente 3 Optimisation locale d un crit re diff rent du crit re de De la Vega Les inconv nients observ s du point de vue de l quilibre des classes ave
34. ndication a t trouv e par la proc dure MCLASI pour confirmation et en raison de la meilleure qualit des partitions fournies par la proc dure MCLAS SXT amp MOA ERARIO OMAN GRN Nava 1 3 Inu nr mm 9 A SS 1 s 9 13 17 21 25 29 93 37 NOMBRE DE CLASSES Figure 6a GRAPHE DU CRITERE EN FONCIION DU NOMBRE DE CLASSES CON CARRIER NADAN 1 1 1 9 z 323 t 33 1 33 t 2233 1 2222 a y 2 un 1 t 3 y t 1 1 1 1 t 1 1 1 1 sn i 4 i t 1 y t t s 1 4 1 4 1 4 t 1 2 3 e med 1 s 9 13 17 21 25 29 33 37 NOMBRE DE CLASSES Figure 6c OLI ACUARIOS Nan 2 bgi AAA O E A 3333 3 222 A o ca i 9 13 17 21 25 29 33 3 NOMBRE DE CLASSES Figure 6b GRAPHE DU CRITERE EN FONCTION DU NOMBRE DE CLASSES CI e w emmm o mmm o mem O olmi i O an an oo O m m a D Me eia O a m ma ms mme ee ee dm LOLA OMAR MON A E E mettent 3 0911917 21 23 29 33 3 NOMBRE DE CLASSES Figure 6d EXECUTIONS PROCEDURE MCLAS 42 GRAPHE DU CRITERE EN FONCIIUN DU NOMBRE DE CLASSES OMR OR SMAMETNO Nuwe 24 a 18 12 3 TONPOLINO OIC Mara a ron rr cremoso 1 A A did de 333333 222 2222 222 11 11 1 31111 m 9 13 17 21 25 29 3 37 NOMBRE DE CLASSES ROA ORAR ON Maa GRAPHE DU CRITERE EN FONCIION DU NOMBRE DE CLASSES
35. nduisant dans le cas m trique des classes quilibr es 5 Dans la pratique utilis e de cette fa on la m thode des nu es dynamiques a permis d am liorer substantiellement les valeurs du crit re de De la Vega sous la contrainte de classes d effectifs non d s quilibr s C est l une mani re de prendre en compte la normalisation n cessaire de ce crit re Pourquoi s int resser aux formes fortes Celles ci r sultent de l intersection de plusieurs partitions en un m me nombre K de classes partitions obtenues partir d initialisations diff rentes de la m thode des nu es dynamiques et correspondant diff rents optimums locaux du crit re optimis par cette m thode Dans notre strat gie expos e dans le chapitre A combinant classification non hi rarchique puis classification ascendante hi rarchique la premi re phase a pour but quand la population est de taille importante d obtenir une partition en un nombre assez lev de classes mais bien inf rieur au nombre initial d objets classifier qui seront agr g es dans la seconde phase par l algorithme hi rarchique D autre part l ensemble de la proc dure vise l optimisation d un crit re de classification crit re de la variance dans le cas m trique crit re de De la Vega normalis dans le cas non m trique 57 La raison de pr f rer les formes fortes une partition diff rente en un m me nombre de classes qui pourrait tre obten
36. nn es classifier 1 V rification de la stabilit des r sultats Le r sultat recherch par la mise en oeuvre de ces deux proc dures est l indication d un nombre de classes jug le plus significatif Or dans chacune de ces proc dures la m thode suivie pour arriver au r sultat d pend dans sa premi re phase partitionnement de la population en un nombre de classes lev de l initialisation fournie l algorithme de classification non hi rarchique Celui ci est utilis une fois dans la proc dure MCLAS1 et cinq fois successives pour le standard de 5 exp riences dans la proc dure MCLAS Il est donc important de v rifier tous les autres param tres de la m thode tant fix s que l indication finale obtenue pour le nombre de classes est stable vis vis d un changement d initialisation de l algorithme de classification Dans l algorithme de K Means utilis pour nos essais l initialisation ne pouvait tre modifi e que par un changement de l ordre de rangement des observations sur le fichier initial Une proc dure de tirage al atoire de cet ordre param tr e soit par l heure de l horloge et donc non reproductible soit par une valeur enti re et donc reproductible figurant en param tre de l algorithme nous a permis tr s ais ment de r p ter l ex cution de l algorithme consid r pour diff rentes conditions initiales Premi re analyse par la proc dure MCLAS1 Nous conseillons de commencer l analys
37. normalis parmi toutes les partitions celle du coefficient de corr lation entre Z et O igro NR X S 1 IRI X ISI M An ADS Max Cor O e Max RIS X OR F ISF 1 Nous retiendrons finalement ce crit re normalis d LERMAN que nous appelerons pour simplifier crit re de LERMAN comme crit re de choix d une partition H L utilisation de la m thode des Nu es Dynamiques Deux points seront soulign s l ad quation de la m thode gr ce sa notion de noyau constitu de plusieurs l ments l optimisation du crit re de De la V ga et l int r t de la notion de formes fortes pour une classification hi rarchique ult rieure en r f rence l optimisation de ce m me crit re 1 Crit re optimis par les nu es dynamiques 7 Utilis dans la premier phase de notre strat gie globale de classification cet algorithme non hi rarchique est du type centres mobiles ou allocation r allocation Il proc de alternativement par la d finition de classes puis de repr sentants pour chacune de ces classes Ces repr sentants pour une classe peuvent tre soit un ensemble appel noyau d un nombre fix d objets les plus repr sentatifs de la classe soit dans le cas m trique le centre de gravit de la classe les nu es dynamiques se ramenant dans ce cas une m thode de K Means 55 La construction des classes et des noyaux n cessite seulement une fonction R A B d finissant la proxim
38. pondant pas une interpr tation claire introduit un bruit de fond qui emp che de voir des indications significatives Cet effet a t v rifi clairement sur d autres donn es en faisant cro tre le nombre de facteurs de 6 15 Pour un nombre trop lev de facteurs la courbe du CCC montre une volution tr s monotone sans aucune irr gularit pouvant tre l indice d une indication Le choix du nombre de facteurs doit se faire d s le d but de l analyse en essayant diff rentes valeurs au moyen de la proc dure MCLAS1 et compte tenu des r sultats de l analyse factorielle Organigramme d utilisation des diff rentes proc dures Analyse factorielle o Choix nombre facteurs S lection formes fortes Optimisation des classes Optimisation des classes Sous population plus classifiable St B Indices de similarit crit re de La V ga Nous allons montrer que la strat gie d utilisation conjointe d une m thode non hi rarchique m thode des nu es dynamiques et d une m thode hi rarchique est galement applicable en respectant la nature initiale des donn es si celles ci sont qualitatives indices de similarit ou de dissimilarit En premi re tape nous d finirons un crit re nous permettant comme dans le cas quantitatif de comparer entre elles des partitions de mani re intrins que c est dire en faisant abstraction du nombre de classes ou de leurs
39. re MCLAS Pratiquement on enchainera diff rentes ex cutions de cette proc dure et on analysera l volution des formes fortes obtenues apr s chaque nouvelle s rie de 5 exp riences ET NR LOMMMANLO HE Pmancer rO ONICO On s arr tera quand les formes fortes ies plus importantes appara tront stables Le nombre total de celles ci sera videmment tr s important un grand nombre d entre elles ne contenant qu un seul l ment Sur ce type de population il peut tre n cessaire d aller jusqu 20 exp riences pour voir appara tre des formes fortes stables Pour obtenir partir de la population initiale des sous populations de plus en plus structur es on liminera les formes fortes d un seul l ment puis celles de deux l ments ete jusqu obtenir pour les sous populations s lectionn es des valeurs positives du crit re CCC lors de l application de la proc dure MCLAS1 par exemple On arrivera ainsi sur une sous population mettre en vidence un nombre significatif de classes L utilisation finale de l algorithme non hi rarchique pour optimiser la partition servira galement ici pour allouer les individus restants limin s dans la premi re phase aux classes caract ristiques et fournir la partition finale de l ensemble de la population PROCEDURE MCLAS GRAPHE DU CRITERE EN FONCTION DU NOMBRE DE CLASSES A or e A AAA A A A A qe A A e ce a g e t 1 2 3 a s 7 s 30 u 12 49 1
40. reconnus par la m thode adoptant le crit re de la variance en particulier cette m thode ne d couvre pas une importante classe centrale et pourtant de forte coh sion rassemblant des individus d opinion moyenne sur la plupart des questions D autre part la m thode non m trique distingue plusieurs classes atypiques de tr s faibles effectifs qui sont d un faible int r t pratique Au total la m thode m trique r v le quelques d fauts inh rents au crit re de la variance qui tend refuser de constituer une classe centrale et d autre part tend agr ger plus facilement des individus assez diff rents d s lors qu ils sont loign s du profil moyen Sur ce jeu de donn es la m thode non m trique a apport une information pr cieuse par la mise en vidence d une importante classe non typ e 18 de la population CONCLUSION Nous avons voulu montrer dans cet article qu il est possible de r soudre de mani re satisfaisante le probl me jug difficile en th orie du choix du nombre de classes dans une population de taille importante En pr sentant dans le cas quantitatif une m thode efficace fond e sur l utilisation du crit re du CCC introduit pour la premi re fois dans le logiciel SAS notre intention est de promouvoir l utilisation de ce crit re dont nous donnons l expression explicite en annexe La m thode propos e utilis e couramment dans le cadre de ce logiciel suppose de disposer de proc dures faciles
41. sultait du choix des cinq premiers facteurs d une analyse factorielle des correspondances Le choix s tait arr t sur 7 classes Une autre approche pour noter l volution du CCC diff rents niveaux de partition consiste r aliser des essais directement au moyen de l algorithme de classification non hi rarchique Nous avons signal en remarque au paragraphe 111 les difficult s de cette approche N anmoins on peut tirer une information tr s significative de la comparaison de deux s ries de valeurs du CCC obtenues par l algorithme de classification non hi rarchique pour diff rents nombres de classes correspondant respectivement au choix des cinq puis des six premiers facteurs de l analyse des correspondances 5 facteurs Aoma si classes EEN E 22 39 23 07 22 67 23 37 6 facteurs 2048 2106 2208 ES 50 Nombre de classes 6 Malgr la difficult conclure avec cette approche en particulier pour 5 facteurs cause de la variabilit des r sultats 6 il semble tabli par contre que l importante variation du CCC entre 7 et 8 classes pour 6 facteurs est l indication d un niveau significatif 8 classes Le simple ajout d un facteur suppl mentaire fait appara tre une structure beaucoup plus nette Simple ajout d un facteur suppl mentaire fait apparaitre une Structure beaucoup plus nette dans les donn es A contrario le choix d un nombre trop lev de facteurs ne corres
42. treint que le nombre de classes K est lev On mesurera l cart la situation de classe quilibr es x1 x2 xx 1 par l angle O du k vecteur x1 X2 xx dont l extr mit est dans le plan d quation K DAS i 1 avec le vecteur E e A x X X p normal ce plan es La distance au carr de l origine ce plan tant gale 1 ona K 1 1 K 2 1 x avec y X i i 5 Coste K i l t d o la nouvelle forme de l expression 3 gale N jal 1 1 2 N K cose c L cart E est le produit de A positif et croissant avec 8 et de Vexpression 3 initialement positive et ne changeant de signe qu partir d une certaine valeur 6 de 8 Calculant la d riv e de E par rapport 8 on trouve dE N sin8l DK Cos 8 2 de 2 H existe donc un domaine de valeurs de Xi HN plus grand que K est lev o la valeur de la variance cro t quand on s carte du cas de classes quilibr es Pr cis ment cette croissance est assur e jusqu une valeur o de telle que 2 1 Coste os K 1 l N Ensuite la variance d cro t et redevient inf rieure la valeur du cas quilibr pour 81tel que 1 Co 8 os 8 Ki d Exemples Pour K 3 la variance cro t jusqu 8o tel que 2 Cos 80 V 3 ce qui correspond au profil AE E O 22 663 Pour K 6 la variance cro t jusqu o tel que 1 Cos 80 V 3
43. tres pond r s des classes la variance totale Ce crit re classique compris entre 0 et 1 a videmment une tendance naturelle cro tre avec le nombre de classes ce qui rend d licat son utilisation pour comparer deux partitions en des nombres de classes diff rents di Le crit re du CCC d Warren S Sarle 3 et popularis par le logiciel SAS vise mesurer le caract re plus ou moins significatif d une partition en r f rence une hypoth se nulle d absence de classes une seule distribution statistique uniforme de l ensemble des unit s classifier De cette fa on on peut comparer de mani re plus objective diff rents niveaux de partition de la population classifier D autre part ce crit re pr sente l avantage de mettre en vidence des populations priori peu classifiables On montrera dans ce cas l int r t de la notion des formes fortes attach e la m thode des nu es dynamiques pour extraire une sous population mieux structur e La validit du CCC compar d autres crit res du point de vue de sa capacit retrouver une structure en classes connue l avance a t prouv e par MILLIGAN et COOPER 4 L Le crit re du CCC Le CCC est obtenu en comparant la valeur du R de la partition sur les donn es r elles ce que serait la valeur attendue du R2 soit E R2 pour le m me nombre de classes si la population tait issue d une distribution uniforme sur un parall lipip de
44. ue directement par un algorithme non hi rarchique comme dans la proc dure MCLAS1 du chap tre A est que la partition des formes fortes fournira de meilleurs valeurs du crit re quand on recherchera un regroupement de ces classes initiales par la classification hi rarchique ou d ailleurs par une autre m thode pour trouver la partition optimale maximisant globalement le crit re Ce r sultat a t v rifi dans la pratique par comparaison des proc dures MCLAS1 et MCLAS d crites dans le chapitre A et r sulte du th or me suivant montr par E DIDAY 8 Th or me Si les formes fortes ne varient plus quand on augmente le nombre de partitions diff rentes en K classes dont elles r sultent partir d un nombre n de partitions strictement sup rieur q n tant strictement inf rieur au nombre maximum N d optimums locaux du crit re alors la partition des formes fortes r sultant des q premi res partitions est plus fine que la partition correspondant l otimum global en K classes Cela revient dire que la partition globalement optimale en K classes pourra tre obtenue comme r sultat d une agr gation des formes fortes Dans le cas des donn es non m triques examin dans ce paragraphe notre strat gie d velopp e sur un exemple s est appuy e uniquement sur les formes fortes pour r aliser la classification hi rarchique de la seconde phase II Phase de classification ascendante hi rarchique Nous a
45. ur p On en d duit alors p 2 p 2 LE R 1 j p p AS u j j 1 65 e Correction pour les chantillons de taille n faible Bas e sur des simulations cette correction conduit la formule suivante pour la valeur moyenne T TA n u i p n u m q 4 BR 1 i RO A id 2 AE ETE p n n u E j j 1 d Formule finale du CCC ap 1 ER Va CCC In piaia 1 R 0001 ER Cette formule r pond au besoin de stabiliser la variance du CCC pour diff rentes valeurs du nombre d observations de variables et de classes Elle a t obtenue empiriquement 66 Annexe 2 Etude de la variance du crit re de De La Vega en fonction des effectifs des classes LERMAN a trouv pour cette variance l expression suivante IR X IS x GR x IS D 12 1 IR nombre de paires d objets r unis par la partition IS nombre de paires d objets s par s par la partition Rappelons que la distribution consid r e pour le calcul de la variance est la distribution de toutes les partitions d un type donn c est dire des partitions en K classes d effectifs fix s n sur laquelle la moyenne du crit re est nulle Dans l expression 1 la quantit entre parenth se tant constante gale au nombre total de couples d objets plus un il reste tudier la variation avec les effectifs des classes de la quantit R x S On appelle n le P G C D des effectifs des diff rentes cl
46. urs du CCC il faudra donc en g n ral effectuer pr alablement une A C P analyse en composantes principales ou une A F C analyse factorielle des correspondances partir des variables initiales et utiliser les facteurs non corr l s obtenus comme variables de classification Remarque 2 Une simulation de Monte Carlo assez compl te 3 a permis d tudier le comportement du CCC pour la distribution uniforme de r f rence Les valeurs le plus souvent n gatives observ es pour le CCC montrent le caract re g n ralement conservatif du test trop s v re dans sa d cision de rejet de l hypoth se nulle Il est int ressant pour des conditions voisines de celles dans lesquelles nous utiliserons le CCC c est dire en particulier pour un nombre d individus important de noter pour la distribution uniforme de r f rence l volution des valeurs n gatives du CCC en fonction du nombre de classes On doit noter sur la figure 1 que pour la distribution uniforme la valeur du CCC de r f rence cro t avec le nombre de classes She DISTRIBUTION UNE ORME N 64 P LES INTERVALLES DE VARIATION SUR LES 4 DIMENSIONS SONT DANS LES RAPPORTS 4 2 2 1 ut IT 0 3 6 83 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 NB CLASSES Figure H Une m thodologie pour classer les populations de grande taille 1 Principes Deux id es forces tay es par des arguments d ordre pratique et th orique sont la b
Download Pdf Manuals
Related Search