ALGORITHMES DE CLASSIFICATION

Wilhelm .

Sujets

• Hiérarchie numérique synchrone
• Résultats électoraux de l'extrême gauche en France
• Formule brute
• Polynôme de Hurwitz
• Axe de polarité
• Niveau (jeu vidéo)

Informations

• Publié par: Octi
• Nombre de lectures: 169
• Langue: Français

Extrait

ALGO RITHM ES DE CLAS SIFICA TION Maurice ROUX Professeur émérite Université Paul C ézanne Marseille, France. Av ertissement Cet ouvrage a été publ ié aux éd itions M asson, Par is, en 1985. Il est mainten ant épuisé et nous mettons e n a ccè s libre la pr ésente version él ectronique, c orrigée e t am éliorée. La premiè re version de cet ouvrage comportait, à la fin de chaque chapitre des programmes en lan ga ge Basi c-Appl eso ft qui sont maintenan t obsol ètes. Ces progra mmes ont été convertis en « Visu al Basi c fo r Appli cations » utilisabl es avec le tabl eur EXCEL (Mi crosoft) . Ils sont réunis dans le class eur « AnaDon. xls » as soci é à un mode d’emploi inclus dan s le fi chi er « AnaD on.do c » lisibl e avec le trait ement de textes WO RD (M icrosoft ). A la fin de chaque chapitre d e l’ouvr age figurent le s noms de s p rocé du res de ce class eur tra itées dans l e c hapitre. Ma rseille, Juin 2006.ALG ORIT HM ES D E CLASSIF ICATIO N Table des matières CHAP ITRE 1. - Introduction à la classifi cation 1. But de la classifi cation2. Probl èmes et m éthodes de la classifi cation a utoma tique 3. Objectif s e t pl an d e l'ouvrag e4. Domaines d 'appli cation e t points d e vo cabul ai re CHAP ITRE 2. - Exemples de donné es 1. Psycholog ie e t so ci été (Ps ysoc)2. Phytosociolo gie (Ph ytos) CHAP ITRE 3. - Préparation d es donn ées. Calc ul de s di stan ces 1. Généra lités 1.1. Donn ées qua ntitativ es ; exemple des caus es de décès (Psysoc) 1.2. Pré -tr aitement par l' analyse factorielle 1.3. V ar iabl es qu alit ativ es et m ixtes 2. Appli cation aux exemples 2.1. Caus es de d éc ès (Ps ysoc)2.2. Ph ytosociolo gie (Ph ytos) 3. Les p rocé du res de cal cul d e dist anc es CHAP ITRE 4. - La classifi cation a sc end ant e hiérarchique 1. Généra lités 1.1. Prin cipe généra l des constructions as cend ant es 1.2. Propr iétés des fo rmules élémentaires de recal cul 1.3. Co mpar aison d es agrégations pa r le saut m inimum et par l e diamè tre 2. Appli cation aux exemples 2.1. Caus es de d éc ès (Ps ysoc) 2.2. Ph ytosociolo gie (Ph ytos) 3. Les p rocé du res de constructions a sc endant es de hiéra rchi es CHAP ITRE 5. - Agrég ation aut our de c entres m obi les 1. Prin cipes et pr obl èmes 1.1. L'al gorithme des centres mobiles 1.2. Moment d'ordr e d eux d'une partition 1.3. Av ant ages et in convé nients d e la méthode 2. Appli cation à l'exemple Psysoc 2.1. Pa rtition e n t rois cl asses 2.2. Pa rtition e n qua tre class es 3. Les p rogra mmes de calcul d e c entres mobil esCHAP ITRE 6. - Hiérar chie du mo ment d'ord re d eux 1. Prin cipe e t probl èmes2. L'al gorithme des voisins r éci proques 3. Appli cation à l'exemple Psysoc4. Proc édu re de cal cul CHAP ITRE 7. - Classifi cation d escendant e hiérar chiqu e 1. I ntroduction2. Mé thodes bas ées su r une var iabl e particuli ère 2.1. Utilis ation d e l'une d es va riables des donn ées 2.2. Utilis ation d es variabl es pr incipa les, ou axes f actoriels 3. Mé thodes bas ées su r des indiv idus p ar ticuli ers 3.1. Sélection d 'un poin t pé riph érique3.2. Sélection d e d eux point s périph érique s3.3. Sélection d e d eux point s-noyaux 4. Le probl ème des inv ersions5. Appli cation aux exemples 5.1. Donn ées PSYSOC5.2. Donn ées PHY TOS 6. Conclusion7. Proc édu re de cal cul CHAP ITRE 8. - Aides a l'interprétation 1. Var iabl es qu antit ativ es 1.1. Interprétation d 'une par tition 1.2. Interprétation d 'une hiérarchie 2. Var iabl e qu alit at ives 2.1. I nterprétation d 'une par tition 2.2. I nterprétation d 'une hiérarchie 3. Appli cation aux exemples 3.1. Donn ées Ps ysoc (quantit ativ es)3.2. Donn ées Phytos (qualitativ es) 4. Les p rocé du res d'aide à l'interprétation CHAP ITRE 9. - Pratiqu e d e la clas sifi cat ion 1. Choix d'un a lgorithm e 1.1. Dimensions des donn ées 1.2. N ature d es donné es 1.3. Qu alité des ré sulta ts 1.4. Temps de c alcul 2. Stratégies 2.1. Hiérar chi e puis ce ntres mobiles2.2. Centres mobil es suivi s d'une hiérar chie2.3. Donn ées hé térogènes, emploi d e l'an al yse factorielle préal abl e 3. I nterprétation d es résultats 4. Un pr ogr amme supplément ai re ut ile : tronc atu re d'une pa rtitionCHAP ITRE 10. - Conclusion 1. Taxino mie de qu alit é 1.1. Pré para tion d es donn ées 1.2. Tra itement 1.3. Interprétation d es résultats 2. Classifi cation e n t ant que pré-tr aite ment 2.1. Prépara tion d es donn ées2.2. T ra itement2.3. I nterprétation ANNEXE 1. - Les ind ices de ditan ces 1. Généra lités2. Cas des donn ées bin ai res 2.1. I ndic es où l a p rése nce d es at tributs jou e un r ôle pr épondé ra nt2.2. I ndic es où l es p résences et absences d'att ribu ts jou ent des rôles éq uival ents 3. Cas des donn ees qua ntitativ es 3.1. Coeffici ents de corrélation3.2. Mesures de dist an ces 4. Conclusion ANNEXE 2. - Hiéra rchi es et ul tramétriqu es 1. Généra lités 1.1. Hi érar chi e e t o rdonna nc e 1.2. Hi érar chi e indicée e t ult ram étrique 2. Une ult ram étrique pa rticuli ère la sous -dominante 2.1. Relation d' ordr e su r les m étriques2.2. Ultra métrique “ sous -dominante ” d'une mé trique donn ée BIBLIOGR APH IE IN DEXCh apitre 1 In troduction à la classification 1. But de la classification Comme les au tres méthodes de l'An al yse des donn ées, don t elle fait partie, la Classifi cation a pour but d'obt eni r une représenta tion schématiqu e simple d'un ta bleau rect angulai re de donn ées dont les col onnes , suiva nt l'usag e, sont de s descr ipteurs de l'ensemble de s obse rvati ons, pl acées e n l ignes. L'ob jectif le plus simple d'un e classif ication est de répa rtir l'éc hantillon en groupes d'obse rvations homogè nes, ch aque groupe étan t bien différencié des aut res. Le plus souvent, cepend ant, cet obj ectif est plus ra ffin é ; on veut, en général, obt enir des sect ions à l'intérieur des gr oupes princip aux, puis des subdi visions plus petites de ces sections, et ainsi de suite. En bref, on désire avoir une hi érar chie, c'est à dire une suite de pa rtitions "emboît ées", de plus en plus fi nes, sur l'ensemble d'obse rvations initi al. Une telle hi érar chi e peut ava ntageus ement être résumée par un arb re hi érarchiqu e (figure 1) dont les nœuds (m, n, p, q) symbo lisent les div erses subdivi sions de l'échantillon ; les éléments de ces subdi visions étant les obj ets (a, b, c, d, e) , placés à l'extrémité inf érieure des branches qui leur sont reliées. Figure 1 . E xemple d'arbr e h iérarchique por tant sur c inq obj ets a, b, c , d, e. Les points m , n, p, q sont les nœuds d e l’a rbre. Le trait ho rizontal mi xte indiqu e un ni veau d e tron cature d éfinissant une partition e n trois c lasses. Le niveau des nœud s, qui est le plus souvent chif fré, est sensé indiqu er un degr é de ressem blance ent re les obj ets correspond ants. A insi, sur not re fi gure 1, les obj ets a et d se ressemblent plus que les obj ets c et e. Rema rquons, en pass ant, que si on coupe cet ar bre à un niveau inte rmédia ire entre n et p, on obti ent une partition en trois cl asses de l'ensemble étudi é, savoi r les parties {a, d}, {b}, {c, e}. En fa isant va rier ce nive au de tronc atu re on obti ent les div erses pa rtitions con stitua nt la hiérarchi e.On voit qu'il ne faut pa s confond re cl assifi cation et class ement. Dans un cla sse ment on affecte les obj ets à des groupes préétablis ; c'est le but de l'an al yse discriminante que de fixer des règl es pour déterminer la classe de s obj ets. La cla ssifi cation e st don c, en qu elqu e sorte, l e tra va il p réliminaire au cl as seme nt, savoi r l a recherche des classes "naturelles" dans le domaine étudi é. 2.- Probl èmes et m éthodes de la cl assification automatique Dans cet ouvrag e il sera beauc oup question d'al gorithmes . Rapp elons qu'un algorithme est la descr iption minutieus e de toutes les opérati ons à effect uer pour ob tenir la solution concr ète d'un prob lème . Ainsi on peut parler de l'al gorithm e permett ant de trouver la racin e carrée d'un nombre, ou bien pour ob tenir le plus gr an d com mun diviseu r de deux nombre s entiers, etc ...Il ne faut pas conf ondr e algorithme et prog ramme info rmatique : il peut y avoi r plusieurs faç ons de programmer un mê me algorithme. L'un des plus gr an ds class ifi cat eurs a, sa ns aucun dout e, été le savant suédois Linné qui, au 18-ème siècle, a établi une classif ication du monde viva nt en général et du règne végétal en particulier, cl as sificat ion enco re en vigu eur au jourd'hui chez les spécia listes des sci ences naturelle s. La prem ière moitié du 20 -ème siècl e a vu un certa in nombre de tentatives pour rati onali ser le pr oc essus me ntal utilisé par Linné. M ais ce n'est qu'à partir des années 1960, av ec la diffusion de l'informatiqu e en milieu univ ersitai re, que sont appar us un grand nombre d'algo rithm es automa tisant complèt ement la construct ion des cl as sificat ions (Willia ms an d Lambe rt, 1959, Sokal and Snea th, 1963 ). Cependa nt, aujourd 'hui enco re le support math éma tique de ces méthodes reste embr yonna ire et ne permet p as d'élire un a lg orithme aux av antages i ndisc utabl es. Supposons que l'on veui lle, pa r exemple, construire une hiéra rchi e. L'une des ma nières de "bien pose r" le probl ème pourrait être de choisir un critère évaluant la fidélité de la représentation hi érar chi que au tabl eau initial des donn ées, et de trouver ensuite un algo rithme construisa nt la hi érar chie la me illeure, au sens de ce critère. M alh eureusement on ne sait pas fai re cela sauf pour des éc hantillons très peti ts, ou pour des cr itères sans intérêt. La solution qui consiste à examiner l'ensemble de toutes les hi éra rchi es possibl