Université Aix-Marseille III (Paul Cézanne)








télécharger 0.67 Mb.
titreUniversité Aix-Marseille III (Paul Cézanne)
page1/12
date de publication26.12.2016
taille0.67 Mb.
typeDocumentos
m.21-bal.com > droit > Documentos
  1   2   3   4   5   6   7   8   9   ...   12
ALGORITHMES DE CLASSIFICATION

Maurice ROUX

Professeur émérite

Université Aix-Marseille III (Paul Cézanne)

Cet ouvrage a été publié aux éditions Masson, Paris, en 1985. Il est maintenant épuisé et nous en mettons la présente version électronique, corrigée et améliorée, en accès libre.

Table des matières
La table des matières se trouve à la fin de l'ouvrage page 69.
Avertissement
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 « Classif.xls » associé à un mode d’emploi inclus dans le fichier « Classif.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.
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 "emboîtées", de plus en plus fines, 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}, {c, 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 recherche des classes "naturelles" dans le domaine étudié.
2.- Problèmes et méthodes de la classification automatique
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 complète de l'ensemble des végétaux, 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. Cependant, aujourd'hui encore le support mathématique de ces méthodes reste embryonnaire et ne permet pas d'élire un algorithme aux avantages 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 croît 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 heuristîques. 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 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 on oeuvre du programme correspondant et ses principales caractéristiques en vue d'une adaptation éventuelle. Par 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 est 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 classificatrices nous allons présenter 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 mortalité, 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 paraît 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 19 349 7 281 345 -369 -257 -65

WGERMANY 210 12 230 21 298 269 -245 17 149

BELGIUM 156 10 260 13 367 144 -7 95 -37

FINLAND 251 26 180 29 387 55 258 270 178

SWEDEN 194 11 151 13 384 122 54 214 58

SWITZERL 225 9 195 26 276 128 -15 212 211

ITALY 54 11 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 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 (encadrées) sont les coordonnées factorielles (multipliées par 1000) des pays sur les trois premiers axes de l’Analyse factorielle des Correspondances.


+---------+---------+---------+---------+---------+--------+

1| | |

2| | SUICIDES |

3| | |

4| | AAUTR |

5| | AINDUS |

6|-------------------+--------------------------------------|

7| |AROUTE |

8| | |

9|CIRFOIE | |

10| | |

11| | |

12| | |

13| | |

14| | |

15| | |

16| | |

17| | |

18| | |

19| | |

20| | HOMIC

+----------------------------------------------------------+
Figure 1.- Données PSYSOC, Analyse des correspondances, représentation des variables sur les axes 1 et 2. Ces deux axes expliquent respectivement 44,33 % et 34,41 % de la variance totale.
+---------+---------+---------+---------+---------+--------+

1| | HOMIC

2| | SUICIDES |

3| | |

4| | |

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, 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.

+---------+---------+---------+---------+---------+---------+---------+---+

1| | ICELAND |

2| DENMARK FINLAND |

3| | NORWAY |

4| SWITZE SWEDEN |

5| | NETHERL ENGLAND |

6| BELGIUM SCOTLAND |

7| WGERMANY | SIRELAND |

8|---------------AUSTRIA------+--------------------------------------------|

9| FRANCE | |

10| | |

11| SPAIN | |

12| | |

13|ITALY PORTUGAL | |

14| | |

15| | |

16| | |

17| | USA |

18| | |

19| | |

20| | |

21| | 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 | |

11| | NORWAY |

12| SPAIN | SCOTLAND |

13| | ICELAND |

14| | |

15| | SIRELAND |

+-------------------------------------------------------------------------+
Figure 2 bis.- Données PSYSOC, Analyse des correspondances, représentation des pays sur les axes 1 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 ...
  1   2   3   4   5   6   7   8   9   ...   12

similaire:

Université Aix-Marseille III (Paul Cézanne) iconUniversité Paul Cézanne Aix-Marseille III

Université Aix-Marseille III (Paul Cézanne) iconMaître de Conférences, iufm & Université Aix-Marseille
«La lutte contre l'échec scolaire : socio-didactique du français», 27-28 janvier 1998, Marseille, iufm

Université Aix-Marseille III (Paul Cézanne) icon1propos liminaire : une charte académique (Aix-Marseille)

Université Aix-Marseille III (Paul Cézanne) iconSujets d’annales : thales correction exercice 1 : Brevet des collèges...

Université Aix-Marseille III (Paul Cézanne) iconToulouse III paul sabatier

Université Aix-Marseille III (Paul Cézanne) iconUniversite catholique de l’afrique de l’ouest
«Très Saint Cœur de la Très Sainte Vierge Marie» (janvier 1900) et le Pape Jean Paul II, sous le titre de «Notre Dame de la Paix»...

Université Aix-Marseille III (Paul Cézanne) iconThèse Table des matières  On retiendra sur ce thème les travaux...

Université Aix-Marseille III (Paul Cézanne) iconChristian demesmaeker 26 Rue Portalis 13100 aix en Provence 06. 16. 53. 48. 35 

Université Aix-Marseille III (Paul Cézanne) iconEditions Kerygma, Aix-en-Provence, 1989, isbn 2-905464-17-8

Université Aix-Marseille III (Paul Cézanne) iconExercice 3B. 1 Marseille 2000








Tous droits réservés. Copyright © 2016
contacts
m.21-bal.com