Université de Neuchâtel Faculté de Droit et des Sciences économiques Analyse critique des méthodes classiques et nouvelle approche par la programmation mathématique en classification automatique Thèse présentée à la Faculté de Droit et des Sciences économiques pour obtenir le grade de docteur es sciences économiques par Thierry Gafner Imprimerie de l'Evole, Neuchâtel Monsieur Thierry GAFNER est autorisé à imprimer sa thèse de doctorat es sciences économiques intitulée "Analyse critique des méthodes classiques et nouvelle approche par la programmation mathématique en classification automatique". Il assume seul la responsabilité des opinions énoncées, Neuchâtel, le 18 décembre 1991 Le Doyen de la Faculté de droit et des sciences économiques Henri-Robert Schüpbach Table des matières Chapitre 1 : Introduction 1.1 Définition du problème, son origine, son évolution, buts et articulation du travail 1.2 Domaines d'application Chapitre 2 : Les méthodes classiques de classification 2.1 La notion de distance dans les méthodes classiques et les problèmes posés par les données 7 2.1.1 Mesures de la dissimilante entre entités 8 2.1.2 Mesure de la ressemblance 11 2.1.3 La problématique de la nature des données 11 2.1-4 Le problème de l'unité de mesure 12 2.2 Typologie des méthodes de classification automatique classique et leur fondements mathématiques 12 2.2.1 Les méthodes de classification hiérarchique 12 2.2.1.1 Les méthodes hiérarchiques ascendantes 13 2.2.1.2 Les méthodes hiérarchiques descendantes 13 2.2.2 Les méthodes de partitìonnement-optimisation 13 2.2.3 Les méthodes par recherche de densité de points 14 2.2.4 Les méthodes de "dumping" 14 2.2.5 Autres méthodes 14 2.2.6 Avenir des méthodes classiques 14 2.3 Exposé des méthodes retenues 15 2.3.1 La méthode du chaînage simple 15 2.3.2 La méthode du chaînage complet 17 2.3.3 La méthode de la moyenne des distances dans les groupes 19 I 2.3.4 La méthode de la moyenne des distances entre les groupes (ou méthodes des centroïdes] 21 2.3.5 La méthode de Ward 23 2.3.6 La méthode du K-mean 24 2.3.7 La méthode du partitionnement autour des médioïdes 27 2.3.8 La méthode de partitionnement par les médianes 28 Chapitre 3 : Problèmes posés par les méthodes classiques 30 3.1 Complexité des algorithmes 30 3.1.1 La complexitÊ de la méthode du chaînage simple 30 3.1.2 La complexité des autres méthodes hiérarchiques 31 3.1.3 La complexité des méthodes de partitionnement 31 3.2 Propagation d'erreurs par les distances {Tied distances) 33 3.3 Pourquoi un optimum n'est pas atteint par ces méthodes ? 33 Chapitre 4 : Approches par la programmation mathématique 36 4.1 Classification et programmation entière 36 4.1.1 Détermination de la médiane d'un groupe minimisant la somme totale des distances à la médiane de l'échantillon 37 4.1.1.1 Résolution par la programmation entière pure 38 4.1.1.2 Réduction par la méthode de Lagrange 41 4.1.2 Minimisation de la somme des carrés dans les groupes 42 4.1.3 Critique 43 4.2 L'approche par la programmation dynamique 44 4.2.1 Algorithme 44 4.2.2 Critique 45 4.3 Approche par la programmation linéaire 45 4.3.1 Algorithme 46 4.3.2 Critique 48 II 4.4 Approche Branch and Bound 49 4.4.1 Algorithme 49 4.4.2 Critique 52 4.5 Application d'une norme Lp â Ia classification 53 Chapitre 5 : Realisation informatique 54 5.1 Analyse et structure d'un logiciel basés sur les méthodes de programmation mathématique 54 5.2 Mode d'emploi du programme 55 5.3 Quelques considérations sur des produits disponibles â l'Université de Neuchâtel 57 5.3.1 Réalisations internes 58 5.3.2 Les packages commerciaux 58 5.4 Autres logiciels 59 5.5 Domaine d'application comparé 60 Chapitre 6 : Comparaison analytique des méthodes de classification 61 6.1 L'analyse des correspondances 61 6.2 L'analyse factorlelle en composantes principales 62 6.3 La classification automatique 63 Chapitre 7 : Comparaison des méthodes par la simulation 69 m 7.1 Evaluation par l'analyse de la variance du choix d'une nonne, d'une méthode 69 7.2 Résultats obtenus sur des problèmes connus 78 7.3 Examen d'erreurs-type 88 Chapitre 8 : Conclusion et recommandations 8.1 Etude des possibilités offertes par la programmation entière 91 8.2 Possibilités offertes par la programmation dynamique 93 8.3 Résultats des nouveaux concepts 101 8.4 Recommandations 103 Annexe 1 : Mode d'emploi des programmes PC 105 Annexe 2 : Exemple économique de Ia banque d'Iran 108 Bibliographie 112 IV Remerciements Cet ouvrage représente l'aboutissement d'une étude réalisée aux Groupes d'Informatique et de Statistique de l'Université de Neuchfltel [Suisse]. J'adresse mes sincères remerciements au Professeur Yadolah Dodge, premier rapporteur, pour ses conseils en mauere de statistique, et au Professeur Paul Schönsleben, co-rapporteur, pour son soutien apporté dans la résolution des problèmes informatiques. Mes remerciements vont aussi aux chercheurs et Professeurs associés au Postgrade en Statistique, qui ont eu l'amabilité d'examiner ce travail et de me faire part de leurs conseils et remarques; plus particulièrement le Professeur Rousseeuw de Bruxelles pour la mise à disposition de son programme PAM, pour le temps consacré a la relecture du manuscript et pour les remarques qui ont permis son amélioration, ainsi que le Professeur Diday et M. Lechevallier de i'INRIA. A Carole, pour son soutien moral et la motivation qu'elle a su m'apporter dans les périodes de doute. Résumé Au cours de cette étude, nous avons cherché à montrer par Ia simulation que seules les méthodes de la programmation mathématique permettent d'obtenir une solution optimale en classification automatique et que les méthodes classiques ne fournissent qu'une approximation. Forts de ce résultat, nous avons tenté de réduire la complexité d'une des premières méthodes afin d'obtenir des temps de calcul raisonnables, sans pour autant perdre en efficacité. Pour obtenir cette réduction, nous avons combiné les points forts de trois méthodes, de telle sorte que les calculs ne se fessent qu'en des points représentatiis de la fonction-objectif. Abstract With this study we showed in a first phase using intensive simulations, that only the mathematical programing methods could find an optimal solution to a classification problem; and that the classical methods only could find an approximation. In a second phase, we reduced the complexity of the dynamic programing algorithm by the combination of the forces taken in three methods. 2 Chapitre 1 Introduction 1.1 Définition du problème, son origine, son évolution, buts et articulation du travail Nous allons examiner des méthodes résolvant le problème suivant : SoIt un ensemble N=(l,2,...,n) d'entités ou objets dont nous connaissons jusqu'à k caractéristiques. L'objectif est de regrouper les entités étudiées dans m groupes homogènes. Afin de permettre ce regroupement, nous considérons que les entités se distinguent par une distance. Ce problème fut abordé très tôt par de nombreux scientifiques de toutes branches, comme le montre la perspective historique ci-dessous, Lc développe- ment des méthodes de résolution fut plus pragmatique que mathématique jusqu'au début des années soixante. Aristote et les philosophes antiques furent parmi ces précurseurs qui cherchèrent à classer formellement plantes et animaux. Leurs idées étaient fort simples. Il existait, par exemple, quatre états de la matière : l'eau, l'air, la terre, le feu. Par un choix approprié de caractéristiques, Us développèrent des typologies où l'on retrouvait des dominances semblables des quatre états de base. Galen (129-1991 définit l'une des plus connues qui permettait grâce a neuf types de tempéraments de trouver la vulnérabilité d'un individu â diverses maladies ou d'expliquer les différences de comportement en société. Le système moderne, dans les sciences naturelles, est dû aux travaux de Linnée (1753). Après la zoologie et la botanique, la classification fut appliquée à bien d'autres domaines : psychologie, médecine, psychiatrie, archéologie, anthropologie, marketing, sciences économiques, sociologie, éducation, criminologie,... Longtemps ces techniques demeurèrent limitées à la définition de typologies fixées par des critères observables visuellement. L'application des mathématiques connut un développement important au cours du 19e siècle. Les méthodes de regroupement en profitèrent également. Le développement des méthodes de classification resta longtemps l'oeuvre des scientifiques qui en avaient besoin. Par exemple, le professeur Robert Tryon, professeur de psychologie à l'Université de Berkeley, consacra l'essentiel de sa carrière â développer des techniques applicables â la psychologie individuelle et collective, et les utilisa dans ses études. Les méthodes proposées par ces scientifiques sont sujettes à la même critique: aucune ne garantit une classification mathématiquement correcte. Elles sont trop rudimentaires, â l'image des moyens de calcul disponibles. Le développement d'une méthode de classification exige des connaissances 3 Chapitre 1 poussées dans divers domaines. Brian Evolti 11974) écrit en conclusion à un ouvrage consacré à ces méthodes : "The number of clustering techniques available is large, as the number of problems in applying them. The greater part of the mushrooming literature on classification is concerned with new techniques which in general suffer from many of the problems of those methods already in use. Perhaps the problem is that mentionned by Johnson ( Rainbows' End : the quest for an optimal taxonomy, Proc. linn. Soc. N.S.W. 93, 8-45, 1968). namely that anyone who is prepared to learn quite a deal of matrix algebra, some classical mathematical statistics, some advanced geometry, a little set theory, perhaps a little information theory and graph theory and some computer techniques and who has access to a good computer and enjoys mathematics (as he must if he gets this far) will probably find the development of new taximctric methods much more rewarding, more up-to-date, more 'general', and hence more prestigious than merely classifying plants and animals.". Dès les années 60, des statisticiens confirmés commencèrent â s'intéresser à cette problématique. De nombreux ouvrages parurent, cherchant â formaliser les développements antérieurs, à établir de nouvelles méthodes plus fiables, en apparence du moins, et à tirer toujours plus de profits des ordinateurs. Mais eiles souffrent toujours du même défaut que les précédentes. Aucune de ces méthodes ne converge. Pour corriger ce défaut, quelques mathématiciens ou statisticiens ont étudié les possibilités d'appliquer diverses formulations issues de la programmation mathématique & la résolution d'un problème de classification automatique. Ces quelques études n'ont rencontré que peu d'échos en raison des problèmes de complexité des algorithmes et des coûts de leur mise en oeuvre. Pourquoi un nouveau travail dans ce domaine qui semble si bien couvert théoriquement ? Et pourquoi chercher â remettre au goût du Jour des techniques jugées trop coûteuses ? - Premièrement, nous avons pu nous rendre compte lors d'un congrès en 1987 à Aix-La-Chappelle, qu'aucune solution n'a été trouvée pour supprimer les défauta des méthodes classiques. Dans ce travail nous appelons méthodes classiques toutes celles qui ne font pas appel A un algorithme de programmation mathématique. Ces dernières semblent être ignorées. Aucun exposé ne leur était consacré dans cette conférence et nous n'avons trouvé aucun logiciel les appliquant. - Deuxièmement, nos recherches bibliographiques nous ont prouvé que personne n'avait réalisé une étude comparative approfondie des diverses méthodes disponibles. Seuls, & notre connaissance, Everitt, Cooper et Milligan, ont montré les problèmes posés principalement par les méthodes hiérarchiques. - Troisièmement, nous sommes convaincus que seules les méthodes issues de la recherche opérationnelle, permettent d'obtenir une solution correcte mathématiquement. Nous pensons qu'il est nécessaire d'examiner ces techniques sous un autre oeil que simplement celui de la performance. Afin d'atteindre ces objectifs, nous effectuons une étude comparative en plusieurs volets : - Premièrement, nous exposons les éléments conceptuels des algorithmes. Cette phase montrera quels sont les critères de classification utilises et l'existence ou non d'une fonction-objectif globale à minimiser (ou maximiser). Chaque exposé est illustré par un exemple. 4 - Deuxièmement, nous cherchons â montrer la complexité des méthodes et les problèmes qu'elles posent mathématiquement. Troisièmement, nous présentons les problèmes rencontres lors d'une Implantation informatique. Nous chercherons également a juger le confort d'utilisation selon des critères d'ergonomie. Quatrièmement, nous exposons deux méthodes n'utilisant pas Ia notion de distance et en comparons les concepts avec ceux de La classification automatique. Cinquièmement, nous présentons les résultats obtenus sur des jeux de données conçus de telle sorte que la classification optimale est connue. Finalement nous examinons les possibilités de développement à partir des meilleures méthodes et tirons les enseignements de cette étude. Domaines d'application L'étendue des domaines d'application, et des dénominations, se compare aisément â la variété des solutions proposées. 0 existe de très nombreuses méthodes de classification, qui s'utilisent en zoologie, en botanique, en médecine, en économie, en sociologie, en psychologie... Tryon et Bailey (1965) donnent de nombreux exemples pratiques, issus de leurs propres recherches. Dans Hartigan (1975], Everitt (1978), Späth (1983), nous trouvons de nombreuses références â des études où la classification automatique a été utilisée. La médecine, la biologie et les sciences sociales semblent être les domaines de prédilection pour ce genre d'étude. A Aix-La-Chappelle de nombreuses sessions étaient consacrées aux applications dans ces branches. Pourquoi cette technique statistique est-elle si répandue ? Pour tenter de répondre à cette question, nous allons examiner les raisons de regrouper des données : - Le scientifique qui procède â une analyse statistique peut se trouver confronté a des problèmes techniques capacité insuffisante de l'ordinateur, limites des logiciels, temps nécessaire pour opérer les calculs, saisir les données et exploiter les résultats... La classification peut servir à réduire le nombre des données â analyser, en n'étudiant que des cas types. - Un autre aspect consiste à classer les traitements pour voir s'ils suivent une loi statistique ou s'adaptent â un modèle déjà connu. - Dans le domaine des sciences sociales, on s'intéresse â l'établissement de catégories des individus observés. Par exemple, dans un sondage d'opinion, on essaie de savoir si les partisans d'un leader politique ont des caractéristiques sociales communes. - Enfin, à partir des données réunies et classîfîées lors d'une première étude, on peut chercher à prévoir le comportement d'un individu en 5 Chapitre 1 fonction des ses caractéristiques; c'est-à-dire trouver a quel groupe de la précédente étude, il appartient. Pour résumer, nous pouvons dire à l'exemple de Bail (1971], cité par Everitt [1974], que la classification doit permettre d'atteindre un des objectife suivants : - Trouver une vraie typologie. - Ajustement à un modèle. - Prédiction basée sur les groupes. - Tests d'hypothèses. - Exploration des données. - Génération d'hypothèses. - Réduction des données. 6 Chapitre 2 Les méthodes classiques de classification Les techniques de classification automatique utilisent pour la plupart une distance pour mesurer les dissimilarités entre les objets Û classer. Certaines peuvent également utiliser une mesure de similarité. Ces deux notions font l'objet de la première section de ce chapitre. Ensuite, nous exposons les fondements mathématiques des méthodes classiques et les différentes typologies qui permettent de les distinguer. Notre exposé sera illustré par un exemple. Nous empruntons notre exemple à la gestion du personnel. D s'agit d'un extrait supposé des feuilles de qualification des employés d'une entreprise. Ces qualifications sont données sous forme de notes de 1 [excellent) â 6 (très insuffisant). Nom / qualification Ponctualité Précision Contact Qualité Responsabilité Dupont 2.5 3 4 5 2 Müller 6 5 4 5 5 Meyer 2 3 3 4 4 Durand 5 6 5 5 5 Scott 2 3 3 2 1 Henry 5 5 5 4 6 Tableau 2.1 : Notes de qualification 2.1 La notion de distance dans les méthodes classiques et les problèmes posés par les données Nous abordons les problèmes liés aux données : la mesure de leur differences ou de leur ressemblance, leur unité de mesure, les divers types de données qui peuvent se présenter dans une analyse statistique. Ces problèmes sont exposés, afin de montrer que les défauts des méthodes de classification sont dûs & leurs concepts, et non pas â des influences extérieures. 7 Chapitre 2 2.1.1 Mesures de la dissimilarité entre entités Les entités peuvent Être distinguées les unes des autres par le calcul d'une distance mathématique. Avant de calculer une distance, il peut être nécessaire de procéder préalablement à une transformation des données, afin de corriger par exemple un effet de taille dû a des unités de mesures différentes, ou de codifier un ensemble de données de natures diverses. Ces divers problèmes et leurs solutions sont expliqués en détail dans les sections suivantes. De plus, une standardisation des données permet de supprimer les effets négatifs de certaines distances. Une distance mathématique, entre une paire d'objets doit avoir les propriétés suivantes : 1] Elle doit être positive : d(X±,Xj) i 0 2) Elle doit être commutative : ClCX1, Xj) = Cl(Xj1X1) 3) Elle est nulle en un point i donné : Cl(X1,Xj) =0, si i = j 4) L'inégalité triangulaire doit être vérifiée pour obtenir une distance "métrique" : d{Xi(Xj) s. Cl(X1,Xk) + d - j tel que d(Ji(Jj) = min { d(Xp,Xq), XpE J±, Xq e Jj (2.9) J Identifie une classe ou groupe. Cette classe peut être formée d'un seul élément. 2. Mémoriser l'indice de l'itération. 3. Agréger Jj et Jj, en formant un nouveau groupe Jk = Ji u Jj 4. Définir la nouvelle partition 5. Calculer les nouvelles distances par la formule propre â la méthode : d (J]C^J1) »min {Jk, J1) k <> i (2.10) 6. Ajuster le nombre de groupes Fin du tant que 15 Chapitre 2 Le altère de fin est atteint quand Q ne reste qu'un groupe formé de toutes les entités, ou quand un nombre de groupes fixés par l'utilisateur sont déterminés. Pour notre exemple, de la page 7, nous obtenons les résultats partiels suivants. Nous avons calculé la matrice des distances par la méthode de Manhattan. Nous avons attribué le numéro d'entité suivant aux six employés supposés. Dupont 1 Müller : 2 Meyer 3 Durand 4 Scott : 5 Henry ; 6 Au départ, nous considérons six groupes, formés chacun de une entité : m,f2},(3},l4),{5).{6> Les distances entre ces six groupes sont : {1} {2} {3} {4} {5} {6} {1} 0.0 8.5 4.5 9.5 5.5 10.5 {2} 0.0 9.0 3.0 14.0 4.0 {3} 0.0 10.0 5.0 9.0 {4} 0.0 15.0 3.0 {5} 0.0 14.0 {6} 0.0 La classification débute en déterminant les deux entités les plus proches. L'examen de toutes les possibilités nous montre que {2} et (4},avec une distance de 3.0 remplissent cette condition. La paire (4) et (6) est également une alternative possible. Cependant, la règle est de sélectionner la première trouvée dans la matrice. Cette distance est mémorisée afin de fournir l'indice d'agrégation pour le dendogramme. Les entités sélectionnées sont fusionnées pour former le premier groupe, nous avons : (U,(2.4J,(3},(5),{6) Nous recalculons les distances par la formule de Lance et William, n suffit de considérer les anciennes distances par paire. La distance d( 1,(2,4)] sera le minimum sur d[l,2J et d(l,4) c'est-a-dire d(l,2)=8.5. En procédant de même pour tous les groupes, nous obtenons la nouvelle matrice ci-dessous : {1} {2,4} (3) {5} {6} 0.0 8.5 4.5 5.5 10.5 0.0 9.0 14.0 3.0 0.0 5.0 9.0 0.0 14.0 0.0 Nous devons déterminer la prochaine paire d'objets a fusionner. La distance 16 Les méthodes classiques de classification la plus petite est celle entre (2,4} et {6), avec une valeur de 3. Nous formons une nouvelle classe, et recalculons la matrice des distances. Nous considérons les distances de {2,4), et (6) avec respectivement (1), (3) et {5}. Nous obtenons ainsi : (D {2,4,6} {3} {5} 0.0 8.5 4.5 5.5 0.0 9.0 14.0 0.0 5.0 0.0 Nous déterminons que (1) et {3) peuvent Être fusionnes puisque leur distance est la plus petite, 4.5. Puts nous calculons la nouvelle matrice de distance : {1,3} {2,4,6} {5} 0.0 8.5 5.5 0.0 14.0 0.0 L'examen des distances nous montre que {5} peut être fusionné avec {1,3) à une distance de 5.5. {1,3,5} {2,4,6} 0.0 8-5 0-0 n reste deux groupes, que nous fusionnons à une distance, pour le dendogramme de 8.5. Les calculs sont représentés par le dendogramme suivant : 8.5 5.5 4.5 3.0 1 3 5 2 4 6 Figure 2.2 : dendogramme obtenu par chaînage simple 2.3.2 La méthode du chaînage complet Pour cette seconde méthode hiérarchique, la distance entre deux groupes est la distance entre leurs deux objets les plus éloignés. Elle tend â former des groupes artificiels, mais très compacts. Son algorithme est le même que pour la précédente, seul le critère de l'étape (5) est diftërent ; 17 Chapftre 2 1. Trouver! <> j tel que d(JifJj) = min {a i (2.11) 6. Ajuster le nombre de groupe. Illustrons une classification, pour notre exemple. Au départ, nous avons six groupes, formés chacun de une entité comme précédemment. {1} {2} {3} {4} {5} {6} {1} 0.0 8.5 4.5 9.5 5.5 10.5 {2} 0.0 9.0 3.0 14.0 4.0 {3} 0.0 10.0 5.0 9.0 {4} 0.0 15.0 3.0 {5} 0.0 14.0 {6} 0.0 Nous déterminons que (2) et (4), à une distance de 3.0 forment la première classe. Nous obtenons cinq groupes : (11,(2,41,(3),(51,(6) Nous devons recalculer les distances du nouveau groupe avec les anciens. La distance d(l,(2,4}] sera le maximum sur d(l,2) et d[l,4) c'est-ô-dire d[l,2]=9.5. {1} {2,4) {3} {5) {6) 0.0 9.5 4.5 5.5 10.5 0.0 10.0 15.0 4.0 0.0 5.0 9.0 0.0 14.0 0.0 Nous déterminons la prochaine paire d'objets à fusionner, parmi les cinq que nous avons obtenu après agrégation de (2,4). La distance la plus petite est celle entre (2,4) et (6), avec une valeur de 4. Nous obtenons la classification partielle et la nouvelle matrice des distances : {1} {2,4,6) {3} {5} 0.0 10.5 4.5 5.5 0.0 10.0 15.0 0.0 5.0 0.0 les entités (1) et (3) sont fusionnées puisque leur distance est la plus petite, 4.5. Puis nous calculons la nouvelle matrice de distances : IS Les méthodes classiques de classification {1,3} {2,4,6} {5} 0.0 10.5 5.5 0.0 15.0 0.0 L'examen de la matrice des distances nous montre que (5) peut être fusionné avec (1,3) & une distance de 5.5. {1,3,5} {2,4,6} 0.0 10.5 0.0 Les calculs peuvent être représentes par le dendogramme suivant : 10.5 5.5 4.5 4.0 3.0 1 3 5 2 4 6 Figure 2.4 : dendogramme obtenu par chaînage complet 2.3.3 La méthode de la moyenne des distances dans les groupes La démarche de l'algorithme est en tout point semblable à celle des deux précédents, seul le critère de l'étape 5 change : nkni a = 1I11It nk (X1-Xj1) ' (X±-Xk) (2.14) Avec X1 et Xj, défini comme ci-dessus La distance entre les entités doit se calculer a l'aide de la norme L^. H est possible d'utiliser efficacement la notion de poids dans cette méthode. Au départ, nous considérons toujours que nous avons six groupes ,à une entité. (11,(2),(3),(4),(5),(6) Les distances entre ces six groupes sont : {1} {2} {3} {4} {5} {6} {1} 0.0 8.5 4.5 9.5 5.5 10.5 {2> 0.0 9.0 3.0 14.0 4.0 {3} 0.0 10.0 5.0 9.0 {4} 0.0 15.0 3.0 {5} 0.0 14.0 {6} O.O Pour débuter nous fusionnons à nouveau (2) et (4) â une distance de 3.0. Nous obtenons cinq groupes et calculons la nouvelle matrice des distances : 23 Chapitre 2 {11 {2,4} {3} {5} {6} 0.0 10.5 4.5 5.5 10.5 0.0 10.6 17.3 3.6 0.0 5.0 9.0 0.0 14.0 0.0 obten ons en fusionnant (2,4) et {6( : (1) {2,4,6} {3} {5} 0.0 12.0 4.5 5.5 0.0 12.5 19.3 0.0 5.0 0.0 Nous déterminons que (IJ et (3} peuvent être fusionnés puisque leur distance est la plus petite, 4.5. Puis nous calculons la nouvelle matrice de distance : {1,3} {2,4,6} {5> 0.0 18.8 6.5 0 19.3 0.0 Enfin, (5) est fusionné avec (1,3) â une distance de 6.5. {1,3,5} {2,4,6} 0.0 22.5 0.0 22.5 6.5 4.5 3.6 3.0 Figure 2.7 : dendogramme obtenu par la méthode de Ward 2.3.6 La méthode du K-mean C'est une des méthodes de classification par partitìonnernent, qui opèrent en trois étapes : initialisation des groupes, première allocation des entités aux groupes initialises, si nécessaire réallocation, avec comme objectif la 24 Les méthodes classiques de classification minimisation d'un critère donné. Le nombre de groupes à obtenir est à fixer comme donnée de départ. La méthode du K-MEAN n'utilise pas la première étape décrite ci-dessus. EUe débute par la première allocation des entités, puis effectue la réallocation, n est nécessaire de fournir comme donnée en entrée, une estimation des m groupes â obtenir, contenant chacun un traitement. L'algorithme du K-MEAN doit être combiné avec une méthode permettant de trouver cette estimation. Ensuite des conditions de transfert déterminent comment les entités sont â reclasser pour améliorer le regroupement. La première de ces conditions examine si un transfert est possible. La seconde effectue le transfert nécessaire. L'algorithme s'arrête si aucun transfert n'a eu lieu, ou si un nombre maximum d'itérations a été effectué. L'algorithme du K-mean est basé sur les notions suivantes : - L'échelle des observations est telle que l'utilisation de la distance euclidienne est appropriée pour calculer les dissimilarités - La partition P(N1M) est composée des m groupes [J],J2.....^m' - Chacune des n entités n'appartient qu'à un seul groupe - B(J1L) dénote le leader théorique L dans le groupe J, c'est-à-dire l'entité moyenne du groupe. Le nombre d'entités classées dans J est donné par nj et A(I1L) l'observation I de la variable L, D(I1Lj) est la distance euclidienne entre l'entité I et le leader du groupe auquel elle appartient. La distance entre l'entité I et le groupe L est donnée par : D(I,Lj) = St(A(I,L)-B(J1L)2]* (2.15) J=I L'erreur dans la partition est : n e[P(N,M>] = £ D(I,L1)2 (2.16) i = 1 Etape 1 : Soit une partition initiale donnée, déterminer les leaders et l'erreur initiale (2.16) dans la partition. Etape 2 : Tant qu'une entité est transférée faire : Pouri=l.....n faire Déterminer l'accroissement de l'erreur en transférant l'entité I du groupe auquel elle appartient (J^) â chacun des autres groupes par la formule : HJjD(I, Lj)2 FiJ1O(IfLj1)2 T = —±-------------------------------------------------- (2.17) njj + 1 nji -1 Opérer le transfert, si l'accroissement pour un groupe j est négatif, déterminer les nouveaux leaders et la valeur de l'erreur pour la partition 25 Chapitre 2 fin du pour fin du tant que Nous illustrons le développement de cette méthode par notre exemple de référence. Nous supposons que la partition initiale est donnée par les deux groupes suivants : U ,2,3] et {4,5,6} Pour chaque groupe, nous calculons la valeur moyenne de chacune des caractéristiques. (1,2,31 3.5 3.66 3.66 4.66 3.66 {4,5,61 4 4.66 4.33 3.66 4 L'erreur totale dans cette partition initiale est donnée par : e[p(6,2)]= {2.5-3.5)2 + (3-3.66)2 + ... + (4-3.66)2 + (6-4)2 = 68.47 Soit la somme des écarts de chacune des caractéristiques de l'échantillon à la valeur moyenne du groupe dans lequel l'entité est classée. Par le calcul de la distance euclidienne de l'entité 1 à la moyenne de chacun des groupes, nous obtenons les deux distances suivantes : (3(1,Lj1) = ((2.5-3. 5)2+(3-3.66)2+(4-3. 66)2+(5-4.66)2 +(2-3.66)2] = 2.10 d(1,LJ2)) = 3.30 Nous calculons ensuite le coût de transfert de {1} du groupe J] au groupe Jg. 3*10.01 3*4.42 T(1r2) =------------------------------= 1.55 3+1 3-1 T > 0, nous ne pouvons pas transférer (1) dans Jg. Nous effectuons les mêmes calculs pour (2), nous obtenons que : 0(2,Lj1) = 3.17 d<2,LJ2) = 5.065 T<1,2) = 3+25.66/4 - 3*10.47/2 » 4.13 Nous ne pouvons pas transférer (2) dans le groupe Jg. Nous renonçons à présenter les calculs pour les entités (3),{4) et 16}. Pour l'entité {5), nous obtenons : (3(5,Lj1) = 4.15 d{5,LJ2) = 4.50 T(2,1J = 3*17.27/4 - 3*20.28/2 = -17.46 (5) doit être transféré de Jg vers J1 26 Les méthodes classiques de classification La nouvelle erreur dans la partition est : e(P) = 68.47 - 17.46 » 51.01 Nous calculons les nouvelles moyennes des caractéristiques suite â ce transfert : (1.2,3,5} 3.12 3.45 3.45 3.99 2.99 (4,6| 5 5.5 5 4.5 5.5 Nous trouvons en procédant selon le même schéma que (2) doit être transféré de J1 vers Û2- Nous obtenons ainsi les deux groupes finaux : (1,3,5} et (2,4,61 2.3.7 La méthode du partitionnement autour des médioïdes Cette méthode est basée sur la recherche d'objets représentatifs des m groupes A obtenir. Ensuite, les entités restantes sont assignées au groupe dont le leader est le plus proche. Les objets représentatifs sont déterminés de façon à être les médioïdes des groupes. Us représentent la structure des données à analyser. Un médioïde est l'objet pour lequel la dissimilarité moyenne par rapport aux autres entités du même groupe est la plus petite. Cette méthode est due aux travaux du professeur Rousseeuw. Elle permet d'utiliser, soit la distance euclidienne, soit la distance de Manhattan, pour calculer les dissimilarités. L'objectif recherché est de minimiser la somme des dlssimuarités dans les groupes. L'algorithme sera illustré directement par notre exemple, n se compose de deux phases distinctes, l'une est appelée "BUILD", la seconde "SWAP". Ces deux étapes sont itératives. La phase "BUILD™ permet de trouver les objets représentatifs ou médioïdes initiaux, puis de former la classification Initiale- Par "SWAP", la solution est réexaminée, et si nécessaire de nouveaux médioïdes sont déterminés, une nouvelle classification est dans ce cas formée. Sl aucun nouvel objet représentatif n'est déterminé, l'algorithme s'arrête. Nous utilisons a nouveau la matrice des distances calculées avec L1. L'étape "BUILD" est caractérisée par deux phases : le premier objet représentatif est fixé, comme étant celui dont la distance A tous les autres est la plus petite. Trouver i | 2dij ° min S^ij i.j = 1,...,n (2.18) Pour notre exemple, nous avons pour chaque entité, les sommes des distances suivantes : 27 Chapitre 2 d{1) = 38.5, d{2} = 38.5, d{3} = 37.5 d{4} = 40.5, d{5) = 53.5, d{6} = 40.5 Le premier médioïde est (3). Ensuite pour chacun des objets non sélectionnés, la deuxième phase itérative de "BUILD" calcule la somme des différences entre les distances à tous tes médioïdes actuels et les objets â classer, l'entité pour laquelle le calcul est effectué faisant office de leader potentiel. L'objet pour lequel cette somme est maximale devient le prochain médioïde. Nous ne montrons dans le détail que les calculs nécessaires pour l'entité (2). Pour les autres, seul le résultat final est donné. Nous calculons tout d'abord la différence liée à l'entité U), soitC^i. max { [di ^d12], 0) = max {[4.5-8.5], 0) = 0 8.5 1J 1^ 0 8.5 C2 = X c2i = 17 i = 1'••-/n-médioïdes i Pour les autres entités, nous obtenons les C,- suivants : C1 = 1, C4 = 6.5, C6 = 12, C5 = 3 Ainsi (2} est le deuxième et dernier médioïde cherché, puisque nous voulons obtenir 2 groupes. La phase de "SWAP" permet, par une série de permutations, de déterminer le meilleur ensemble de médioïdes. Pour opérer ces permutations, U convient de considérer les objets par paire, un des médioïdes et une entité non-sélectionnée. Si la permutation permet de réduire la somme des dissimilarités, alors elle devient effective. Ainsi dans notre cas, avec |2} comme médioïde ta somme des dissimilati tés dans le deuxième groupe est 3 + 4 = 7. Si (4) est retenu comme objet représentatif, cette somme devient 3 + 3 = 6. Il est avantageux de procéder à cette substitution. A chaque substitution effectuée, la classification est â nouveau déterminée, chaque objet étant affecté au groupe du médioïde dont il est le plus proche comme pour "BUILD". La méthode PAM se propose de minimiser la somme des dissimilarités aux objets médians, comme certaines méthodes basées sur la programmation entière. Cette technique utilise cependant une heuristique, qui ne minimise le critère que localement. 2.3.8 La méthode de partitionnement par les médianes Cette méthode cherche également à minimiser par une heuristique la somme des distances aux objets médians, comme celle de 2.3.7.. Elle utilise toutefois une heuristique différente, assez proche de celle de K-mean. Tout d'abord il convient de déterminer par une technique quelconque une classification initiale. 28 c21 - S24 : C25 - c26 - Les méthodes classiques de classification Ensuite, pour ce regroupement, nous déterminons les objets médians, soit ceux pour lesquels la somme des distances aux autres contenus dans le même groupe est minimale. Puis, nous cherchons a réallouer toute entité a la médiane la plus proche. Les permutations concernent les entités autres que les leaders. Après chaque permutation, de nouvelles médianes sont calculées. Pour notre exemple, nous obtenons comme pour K-mean, la classification initiale suivante : (1,2,3) et {4,5,6) Pour ces deux groupes les médianes initiales sont calculées : Cl1 = 13, d2 = 17.5, d3 = 13.5 La médiane du groupe 1 est (1). d4 = 18.0, d5 = 29.0, d6 =¦ 17.0 (6} est la médiane du deuxième groupe. Chaque entité non-médiane est affectée au groupe dont la médiane est la plus proche. Ainsi, nous déterminons que (2) est plus proche de (6| que de 11). Nous procédons â l'échange et obtenons les groupes : {1,3) et (2,4,5,6). Nous déterminons les médianes pour cette classification : (1) et (2J. Nous examinons à nouveau dans quel groupe doivent être classées les autres entités, (5) étant plus proche de (1) que de (2), nous procédons à l'échange. Nous avons les groupes (1,3,5) et {2,4,6}. Les médianes sont cette fois {5) et {4). Plus aucun transfert n'est nécessaire. Les calculs s'arrêtent. Cette heuristique est moins efficace que celle de 2.3.7, comme nous le verrons plus loin, car elle dépend beaucoup de la classification initiale, qu'elle ne peut guère modifier. 29 Chapitre 3 Problèmes posés par les méthodes classiques C3.1 Complexité des algorithmes Pour déterminer et comparer la complexité des divers algorithmes examinés, nous n'avons jamais tenu compte des opérations de lecture des données, de calcul des matrices de dissimilarités et d'impression des résultats, puisque toutes ces opérations sont communes à toutes les méthodes. Les composants de la complexité sont décrits dans le chapitre 6. Le calcul de la distance a une complexité de 0(n2p), ce qui n'est pas négligeable. Nous avons voulu ne tenu- compte que de la part de la complexité due aux étapes propres des méthodes. Nous parlerons de complexité moyenne lorsque nous donnerons une valeur probable. Nous avons constaté que certaines méthodes voient en pratique leur complexité varier entre un minimum et un maximum que nous avons pu déterminer. Les techniques de classification hiérarchique ne diffèrent que par le critère utilisé lors du calcul de la nouvelle matrice des distances. Cette seule difference ne modifie pas leur complexité. Aussi pour l'illustrer, nous examinons dans le détail la technique du chaînage simple. Pour les autres méthodes, nous ne montrons que les différences dues à la variante de la formule de Lance et Williams. 3.1.1 La complexité de la méthode du chaînage simple Pour déterminer la complexité de cette méthode, nous relevons toutes les opérations nécessaires pour classer les six employés de notre exemple. Nous cherchons également à établir la nature de l'opération : s'agit-t-41 d'une affectation de résultat, d'un calcul simple, complexe, ou d'une comparaison ? Une telle enumeration est nécessaire pour évaluer la performance informatique de l'algorithme. Nous donnons dans le chapitre six une table de pondération de chaque opération en son temps relatif d'exécution par un ordinateur. A partir de la classification initiale formée par les six entités, nous devons pour déterminer la première paire â fusionner : - effectuer 6*(6-l) comparaisons de distances, â partir d'un tableau; - enregistrer la distance à laquelle la fusion a lieu, soit une opération d'af- fectation simple; - former et mémoriser la classe résultant de la fusion : deux affectations dans un tableau; 30 Problèmes des méthodes classiques - définir Ia nouvelle partition, soit mémoriser les objets non touches par la fusion dans un tableau : 5 affectations. - Calculer la nouvelle matrice des distances, il faut effectuer dans notre cas 2*4 accès à Ia matrice des distances et comparer par paire, puis mémoriser les nouvelles distances, soit 4 affectations dans un tableau. Pour que cette matrice des distances soit complète, nous devons encore récupérer les (6- 2)(6-2)/2 autres dissimilarités. - ajuster le nombre de groupes, soit une opération de calcul simple, soustraction ou addition. Pour la première paire fusionnée, nous effectuons 6(6-1) + 2 (6-2) +[6-2)2/2 opérations. Pour fusionner la seconde paire, les opérations sont : - (6-l]*(6-2) comparaisons pour trouver la paire; - 1" [6-3) comparaisons pour déterminer les nouvelles distances pour la paire fusionnée; - (6-3)2/2 affectations des anciennes distances, non touchées par la fusion; Nous effectuons pour trouver cette deuxième paire au total 3/2*62 -2'6 -3/2 opérations. A chaque itération, nous avons au minimum une complexité de 3/2 • 62- 6 k, où k représente Ie numéro de l'itération. Pour classer les six employés nous avons besoin de six itérations. Dans le cas général, nous en aurions n. La complexité moyenne de la méthode du chaînage simple est de n(3/2n2-n], soit de l'ordre de n3. 3.1.2 La complexité des autres méthodes hiérarchiques La complexité des autres méthodes hiérarchiques est identique. Elles utilisent une formule de calcul pour ces nouvelles distances, au lieu d'une série de comparaison. Ces formules ne sont formées que d'opérations simples : addition, multiplication. Elles ont besoin d'autant d'accès aux tableaux de données, mais en changent la nature. Nous aurons toujours autant d'opérations. Nous pouvons conclure que les méthodes de classification hiérarchique ont une complexité moyenne de l'ordre de n3. 3.1.3 La complexité des méthodes de partitionnement Selon Hartigan, elle est de l'ordre de n2 pour K-mean. Pour Rousseeuw, la méthode PAM demande au moins n[n-l)/2 accès a la matrice des distances. Sa complexité serait d'au moins n2/2. Nous examinons tout d'abord la méthode K-mean. Pour obtenir la classification Initiale, il nous faut n opérations d'affectation dans des tableaux, plus un calcul pour déterminer le nombre d'objets pour chacun des deux 31 ChapHre 3 groupes. Cette phase nécessite au moins n+1 opérations. Lc calcul des moyennes demande k*n accès â la matrice des données originales, k est ici le nombre de caractéristiques par entité observée, et k*n additions. Pour calculer la somme des erreurs, nous avons besoins de k*n accès à la matrice des données et de 2k*n calculs, soustraction et calcul du carré, puis nous avons k*n additions et un calcul de racine. Pour chaque entité, nous avons 2mk calculs et accès â des données pour déterminer sa distance aux moyennes de chacun des m groupes. Puis le calcul du coût de transfert nécessite 2m opérations simples. Si nécessaire, nous devons effectuer le transfert d'une entité vers un groupe, soit une opération. Si un transfert a eu lieu, nous devons recommencer tous ces calculs, et ainsi de suite jusqu'à ce que la procédure s'arrête. La complexité minimale de K-mean est de n+1 +5kn+2mk+2m, soit n(5k+l)+2m(k+l)+l. Dans le pire des cas, nous pouvons avoir â transférer les n entités. La complexité maximale est n[n(5k+l)+2m(k+l)+l], soit supérieure â n2. Raisonnablement, nous pouvons penser qu'elle est de l'ordre de n2 en moyenne, comme l'a énoncé Harügan. Pour la méthode PAM, par la procédure de "BUILD", nous avons n(n-l) additions pour trouver la somme des distances de toutes les entités. Ensuite, il nous faut n(n-l) comparaisons pour déterminer le premier médioïde. Ainsi la complexité est de 2n(n-l) pour cette première partie. La seconde phase de "BUILD", nécessite m-1 itérations, à (n-kp (k =nombre de médioïdes courants) opérations pour déterminer le reste des objets représentatifs. Cette deuxième phase a une complexité de (m-l)(n-k)2. Au minimum, nous devons effectuer une itération dans "SWAP". Ce passage coûte au moins m(n-m] opérations. Nous pouvons penser raisonnablement que le nombre d'itérations est en tout cas inférieur au nombre d'entités. Une valeur moyenne de n-m est sans doute correcte. La complexité de PAM est au moins de l'ordre de (m+2)n2+m^. La méthode de partitlonncment par les médianes demande n+1 opérations pour former la classification initiale. Ensuite, il faut n[n-l) calculs pour déterminer les distances pour chacune des entités, puis n[n-l] comparaisons pour déterminer les médianes. Pour les n-m objets non-médians, il fout effectuer m calculs pour prouver la médiane la plus proche. A ce stade-là, nous avons une complexité minimale de la méthode de 2n(n-l) + m(n-m), soit 2n2 - nfi - 2n + run, Au pire, U faudra réallouer les n entités soit, effectuer n itérations qui coûtent chacune m(n-m) calculs, la complexité maximale est : - 2n(n-l)+nm(n-m], soit (m+2]n2-m2-2n. Nous pouvons nous attendre à ce que la complexité moyenne soit de l'ordre de mn2/2. 32 Problèmes des méthodes classiques 3.2 Propagation d'erreurs par les distances (Tied distances) Une erreur type des algorithmes hiérarchiques est de mal sélectionner les paires d'objets. Nous verrons un tel cas, au chapitre sept. Dans notre exemple, nous avons toujours choisi de fusionner en premier la paire (2,4), avec une distance de 3. Mais la paire (4,6) a également la même distance et est tout autant correcte par rapport au critère de sélection. En cas d'égalité de distance entre deux paires, en général, nous choisissons arbitrairement la première trouvée. Ce choix peut s'avérer être faux. Cette erreur initiale sera propagée â toutes les étapes au travers de la formule de récurrence (Lance et Williams). Concrètement cela signifie que tous les calculs des distances sont "contaminés" par cette erreur. Comme les distances sont utilisées, a chaque sélection de paire d'objets à fusionner, toutes les agrégations sont touchées. La classification peut être complètement incorrecte dès le début. Les méthodes de partiüonnement souffrent plus ou moins d'un problème semblable. Elles ne considèrent que des critères d'échange locaux. Si l'état actuel de la solution est très éloigné de l'optimum, il est â craindre que les heuristiques utilisées ne convergent pas, bien que ces techniques visent a minimiser une fonction- objectif globale. Nous avons relevé le fait que ces méthodes voient leur critère d'arrêt, pas de transfert effectué par la dernière itération, renforcé par une condition draconienne : un nombre d'itérations maximum. Ainsi, une entité peut très bien ne pas changer de groupe, simplement parce que ce critère a été atteint. Sans cette restriction, le programme pourrait boucler sur un échange identique. Leur plus grande source d'erreur vient de la détermination des objets "centraux", n n'est pas garanti, â cause des critères d'arrêt, que les échanges suffisent a corriger une erreur â cette étape. Seule la méthode du Professeur Rousseuw nous semble donner de bons résultats quant à cette détermination. 3.3 Pourquoi un optimum n'est pas atteint par ces méthodes ? Nous allons mettre en évidence les raisons pour lesquelles les méthodes classiques ne peuvent pas atteindre un optimum global. Hartigan (1975, p. 11) précise : "All clustering algorithms are procedures for searching through the set of all possible clusterings to find one that fits the data well. Frequently, there is a numerical measure of fit which the algorithm attempts to optimize, but many useful algorithms do not explicitly optimize a criterion...". Nous pouvons souligner les deux éléments essentiels de cette citation : l'optimisation est vue sous l'angle d'un critère numérique. Et de nombreux algorithmes ne cherchent même pas â optimiser un tel critère. Nous préciserons que l'optimisation d'un critère numérique revient a rechercher un maximum ou un minimum a une fonction dite objectif. Nous aurons l'optimum global, si le point de la fonction trouvé est le minimum des 33 Chapitre 3 minimums existants, et inversement en cas de maximisation. Nous admettons le postulat qu'il existe une classification qui représente un de ces points minimums. Nous pouvons relever plusieurs raisons pour lesquelles les méthodes de classification, tant classiques que basées sur les techniques de programmation mathématique, n'atteignent pas un optimum : - Aucun critère n'est optimisé; - Un critère local est utilisé; - Un critère global est utilisé, mais l'heuristique de calcul le réduit en critère local; - Un critère global est utilisé, mais la méthode envisagée ne converge pas quand elle est appliquée â la classification automatique; Les méthodes hiérarchiques ne permettent pas d'atteindre un optimum global pour les raisons suivantes : - Lors de la recherche des paires â fusionner, elles recherchent un minimum sur les distances actuellement disponibles. Il s'agit au plus d'un critère local. - La nouvelle matrice des distances est calculée, à chaque itération à partir de la fusion décrite ci-dessus, par un critère local. Ce critère ne peut que renforcer l'erreur, ou plutôt l'éloignement de l'optimum théorique. Les autres méthodes utilisent un critère de calcul, qui tient également compte et propage l'erreur commise par la fusion. - Si les groupes ne sont pas distincts, les résultats obtenus tiennent compte des points intermédiaires â l'intérieur de l'un ou l'autre des groupes et propagent des erreurs supplémentaires. Les résultats sont difficiles a interpréter, l'utilisateur doit examiner une hiérarchie de classifications et déterminer arbitrairement a quel niveau (nombre de groupes) il s'intéresse. Il n'a aucune indication fournie par la méthode pour l'aider dans son choix. Même un test statistique tel que le test F ne lui apporterait aucune aide, car U est bien probable que la classification proposée à tout niveau ne donne pas de groupes homogènes. L'interprétation du dendogramme est avant tout une affaire visuelle et subjective. Elle ne peut pas conduire à une vision optimale, sous le sens où nous l'entendons, des résultats. L'interprétation d'un dendogramme avec plusieurs centaines de données est un exercice très difficile. Pour notre exemple avec six données, c'est chose aisée. Mais imaginons un tel graphe couvrant plusieurs pages !!I Pour pailler â ce problème, les méthodes hiérarchiques sont complétées par une technique qui permet de déterminer la classification obtenue pour un nombre de groupes fixé. Ce nombre ne peut être déterminé que subjectivement. Une distorsion supplémentaire de la réalité est introduite. Mais en revanche, les résultats sont "quantifiables", c'est-à-dire que nous obtenons la liste des groupes avec les entités qu'ils contiennent. Les méthodes de partitionnement tendent & minimiser un critère global. Cependant, comme elles travaillent avec une heuristique de calcul, elles ne trouvent qu'un optimum local. 0 y a deux raisons principales. Nous allons les illustrer par rapport â la méthode PAM. Ces remarques peuvent être facilement 34 Problèmes des méthodes classiques généralisées aux autres techniques de cette famille. Nous avons vu que "PAM" se déroule en deux phases. Dans ces deux étapes de calcul, nous trouvons deux heuristiques. Seule la détermination du premier médioïde dans "BUILD" utilise un critère global. Ce premier objet est défini comme étant celui pour lequel la somme des distances est minimale sur l'ensemble. Par la suite, cette procédure cherche les m-1 autres objets représentatifs, en utilisant â chaque fois un critère local. Seul l'objet testé, en ce moment des calculs, est considéré. Les tests se font de plus sur des localisations précises, les médioïdes déjà connus. Par la procédure de "SWAP", nous ne considérons que des paires d'objets, un médioïde et un autre, pour trouver quelles permutations sont favorables, nous localisons en deux points sur les n, le test d'optimalité. Nous pouvons résumer pour toutes les méthodes de partitionnement. Elles nécessitent un point de départ pour la classification, n s'agit souvent d'un élément représentatif pour chacun des groupes. Ce choix peut être faux et même si par la suite Ia méthode cherche â réallouer les entités en fonction du critère â optimiser, il n'y a aucune garantie d'atteindre l'optimum global. Les méthodes de partitionnement ont au moins l'avantage d'être de pures techniques de calcul, et ne donnent qu'un résultat final : les m groupes demandés, avec les entités contenues. Elles sont souvent complétées par des résultats statistiques complémentaires, tels que variance â l'intérieur des groupes, dissimilarité moyenne ou totale pour l'ensemble des groupes ou/et chacun des groupes... Ainsi l'analyste dispose d'éléments de décision, qui doivent l'aider, par exemple â fixer le nombre de groupes â retenir. Dans toutes les méthodes étudiées, le nombre de groupes n'est jamais déterminé de manière optimale, n est très souvent laissé & l'appréciation de l'utilisateur. Diverses méthodes permettant de le trouver ont été proposées. Aucune ne s'est révélée satisfaisante. Les méthodes hiérarchiques ont l'avantage d'être très rapides et faciles à comprendre conceptuellement pour des non-mathématiciens. Leur concept de regroupement par paire semble très "naturel" et explique certainement leur large diffusion. 35 Chapitre 4 Approches par la programmation mathématique Nous allons aborder quatre approches du problème de classification automatique par la programmation mathématique. Nous exposons le principe de ces méthodes, et en raison de leur complexité, nous ne présentons qu'une partie de la résolution de notre exemple. Nous déterminons Immédiatement la complexité et la performance de chaque méthode envisagée. Nous terminons ce chapitre en examinant de plus près la définition des normes Lp. Nous essayons de trouver un algorithme qui détermine quand et avec quelle méthode, pour quelles données, utiliser une norme plutôt qu'une autre. La programmation mathématique vise â optimiser une fonction-objectif, soit un critère numérique, sous un ensemble de contraintes décrivant le problême. L'optimisation consiste à trouver le maximum, respectivement le minimum global de la fonction considérée. Nous devons tenir compte de la rêalisabilitê de la solution par rapport au domaine "réel", où le problème a un sens. Pour un problême économique par exemple, nous ne pouvons que déterminer des solutions strictement positives ou nulles. Le problème de classification automatique peut être vu généralement comme étant : - L'optimisation d'un critère d'homogénéité des groupes; - Sous les contraintes qu'une entité ne doit appartenir qu'à un et un seul groupe et que toutes doivent être classées; Pour représenter un problème de classification sous une forme résoluble par une technique de programmation mathématique, U est nécessaire que le nombre de groupes soit fixé. 4.1 Classification et programmation entière Plusieurs auteurs ont démontré que le problème de classification automatique pouvait être modélisé comme un problème de programmation entière. Cette technique d'optimisation consiste â n'utiliser comme variables que des 0 et des 1. 11 existe de nombreuses variantes du problème de classification automatique sous cette forme. Nous nous proposons d'en aborder deux. Elles diffèrent par la fonction-objectif à minimiser : l'une cherche â optimiser la somme totale des distances aux médianes, l'autre la somme totale des carrés dans les groupes. Pour ces deux approches, nous utiliserons les notations suivantes : 36 Approches par la programmation mathématique N = (1,2,...,1)} : l'ensemble des n éléments à classer m nombre d'objets classés dans le jème groupe m nombre de groupes â obtenir X matrice des données entières où : 1 si l'élément i e au groupe j 0 sinon djj matrice des distances 4.1.1 Détermination de Ia médiane d'un groupe minimisant Ia somme totale des distances à la médiane de l'échantillon Nous allons examiner deux variantes de cette méthode : celle en programmation entière pure proposée par Rao (1971) et celle réduite par un lagranglen reprise par Arthanari et Dodge (1981). Nous cherchons à classer les n entités dans m groupes en introduisant la contrainte qu'un élément donné i ne peut appartenir qu'à un seul groupe j. Nous pouvons considérer que m peut être égal â n, tout en sachant que (n-m) groupes peuvent rester vide. Nous identifions les m groupes non-vides par leur médiane. La matrice des coûts C est donnée par les dissimilarités entre les entités. Nous avons à résoudre le problème suivant : n n minimiser £ Z xij^ij (4.1.1) i=i j=r et Xj^ comme défini ci-dessus sous contraintes : n 2 X1^ - 1 i=1,...,n (4.1.2) J-I J qui signifie qu'une entité ne peut appartenir qu'à un seul groupe. n Z Xj1 = m (4.1.3) Cette contrainte exprime le (ait que seuls m groupes sont non-vides. 37 Chapitre 4 Xjj i X1J i,j=1,...,n (4.1.4) assure que le groupe j n'est formé que quand l'entité correspondante est une médiane, donc Xjj=l. ni > 0. Remarque : Le problème sous sa forme actuelle est très complexe. Il contient notamment vr contraintes du type (4.1.4). Nous voyons ainsi que la complexité croît exponentiellement par rapport au nombre d'entités à classer. 4.1.1.1 Résolution par la programmation entière pure Pour Être sûrs que la résolution du problème sous forme entière pure nous conduise bien â l'optimum, il convient de considérer la condition requise émise par Rao {1971} : - "Dans une solution optimale, chaque groupe consiste en au moins un élément, qui par convention est appelé le leader du groupe; de telle sorte que la distance entre ce leader et tout élément qui n'appartient pas au groupe n'est pas moindre que celle entre cette entité donnée et tout autre élément de son groupe". Cette condition de chaînage entre le leader (médiane) et les entités classées dans son groupe n'est pas une condition nécessaire, mais elle est suffisante. Reprenons la formulation de notre problème sous forme matricielle : Min CX se AX = b Xi s 0 ou 1 pour tout i, sauf le dernier où A est une matrice (n+1)x(n(n-1)+2) X est un vecteur-colonne n(n-1)+2 b est un vecteur colonne n+1 donné par (1,1____m) C est un vecteur-ligne n(n-1)+2 Chaque élément du vecteur X représente une classification potentielle. Ainsi le ieme élément, vaut 1 ou 0, selon que ce groupe particulier est utilisé ou non dans une solution optimale. Cj représente revaluation de la fonction-objectif pour chaque groupe potentiel. Chaque colonne de A représente les coefficients pour un groupe particulier et chacune de ses lignes, a l'exception de la dernière, correspond â une entité. Une colonne de A à un 1 dans une ligne, si l'entité correspondante appartient a un groupe donné. Soit les entités I1, Ì2-..4n et j telles que : djj = o < d3i1 < dji2 ... < djin Nous pouvons obtenir les classifications suivantes, par la condition de chaînage avec l'entité j comme médiane : U,ii),(Mi.y- La classification H^q) est exclue puisque di^ > diQ. Pour une médiane donnée, nous avons n-1 possibilités de former un groupe. Comme les n entités sont des leaders potentiels, nous avons n(n-l]+l groupes possibles, y compris celui composé de 38 Approches par la programmation mathématique toutes les entités. La dernière colonne de A doit ne contenir que des zéros de façon fi limiter ces possibilités à m. De plus, il convient de ne considérer les groupes identiques qu'une seule fois, avec le meilleur leader. Le problème ainsi défini se résout par l'algorithme du "set parüoning" par enumeration décrit par Garfinkel et Nemhauser (1972). Nous utilisons les notations complémentaires suivantes : Soit S une solution partielle telle que S+ = { i I X1 * 1, i £ S } et z ¦ Xies + Ci Soit Q[S) l'ensemble des contraintes satisfaites par S. Algorithme 1. Générer le problème de programmation entière â partir des n entités et de la matrice des distances. 2. Chercher la solution optimale par l'algorithme de partitionnement en six étapes : Etape 1 : Soit S = 0 et zbar = ™ Etape 2 : (choix de la prochaine liste) Soit i* = min Ei I 1 e Q[S)J Initialiser un indicateur en haut de la liste i* (élément avec le coût inférieur) Faire l'étape 3. Etape 3 : (test pour une variable supplémentaire) Commencer fi la position indiquée dans la liste i* et examiner les colonnes de la liste dans l'ordre. Si une colonne j est trouvée telle que : Q(S) n pj = 0 et z(S} + Cj < zbar, faire l'étape 4. Si z(s) + Cj i zbar ou si Ia liste i* est épuisée ou vide, faire l'étape 5. Etape 4 : (test pour la solution) Soit S+=S+ u {j>. Si toutes les contraintes sont satisfaites, une meilleure solution a été trouvée, posons zbar=z(S) et faisons l'étape S. Sinon faire l'étape 2. 39 Chapitre 4 Etape 5 : (backtracking) Si S+=0 faire l'étape 6 sinon soit (k) le dernier élément introduit dans S+. Posons que S+=S+-(k) et i* la liste dans laquelle (kj a été trouvé, et plaçons un indicateur directement â côté de Pt) dans la liste i*. Faire l'étape 3. Etape 6 : (test de fin) Si zbar = », il n'existe pas de solution de partitionnement, sinon la solution qui a généré zbar est optimale. Pour notre exemple, nous pouvons montrer que la création des listes se passe de la manière suivante : - Soit l'entité (1) chofsie comme première médiane, nous pouvons former le premier groupe dont elle est l'unique objet. - La condition de chaînage nous indique dans quel ordre les solutions utilisant l'entité (1) sont générées. Ainsi la deuxième nous permet de créer un groupe de deux entités, en y classant (1) et (3). La distance est alors de 4.5. La troisième solution pour (1) est un groupe composé de (1),(3) et (5). La somme des distances est alors de 10.0, Et finalement la sixième solution, avec {1} comme médiane est, les entités sont énumérées dans leur ordre d'entrée, (1,3.5,2,4,¾. Finalement nous obtenons ainsi 32 solutions potentielles, pour six entités. Comme nous voulons obtenir deux groupes, ces 32 solutions sont à considérer sous forme de deux listes, l'une contenant toutes les solutions où {1} apparaît. Nous pouvons représenter partiellement ces solutions, sous forme de tableau de zéros et de uns. .. 32 0 1 0 0 0 1 somme des 04.5 38.5 7.0 4.0 distances Nous allons pointer successivement sur chacune des solutions, dans les deux listes. Au départ dans la liste 1, nous pointons sur la solution 1. Dans la liste 2, nous prenons la solution 7. Comme les six entités ne sont à ce moment pas classées, nous devons prendre la solution suivante dans la liste 2. Une fois une solution trouvée dans la liste 2 telle que combinée avec la solution 1 toutes les entités sont classées, nous calculons la somme des distances totale et enregistrons la position courante des deux pointeurs. Puis nous continuons â parcourir la liste 2. A la prochaine solution complète, nous calculons â nouveau la somme des distances et comparons ce résultat avec le précédent. Si le dernier est meilleur, nous le mémorisons. Une fois que nous avons atteint la solution 32, nous déplaçons le pointeur solution/ 12.. 6. . ..10 entité 1 1 1 0 2 0 0 1 3 0 1 0 4 0 0 1 5 0 0 0 6 0 0 1 40 Approches par la programmation mathématique dans la liste 1 sur la solution 2. Et nous reprenons le parcours de la liste 2 à la solution 7. L'algorithme s'arrête quand pour la solution 6 de la liste 1, nous avons atteint la solution 32. A ce moment, les pointeurs mémorisés nous permettent de récupérer les solutions contenant les groupes tels que la somme des distances est minimale. Dans notre cas, nous obtenons {1,3,5) et (2,4,6(. Nous pouvons très facilement esquisser les problèmes soulevés par cet algorithme. Nous générons 32 solutions potentielles pour classer seulement six entités dans deux groupes. Nous remarquons que les besoins de stockage de données sont gigantesques, n faut au moins 2m(n-l)n3 itérations pour parvenir a la solution. Chacune des itérations ne se composent que de six opérations au plus. La phase de préparation des données se compose den(n-l) opérations. 4.1.1.2 Réduction par la méthode de Lagrange Nous avons vu que le principal problème venait de !'enumeration complète des solutions. En modélisant notre problème sous forme d'un lagrangien, nous pouvons éviter cette enumeration. Nous allons parcourir partiellement la région réalisable en faisant converger vers l'optimum une fonction sous-gradiente à partir d'une solution réalisable initiale. A chaque itération, nous déterminerons l'ensemble des médianes optimisant localement [et provisoirement] la fonction- objectif. Cette réduction ne se fait pas sans risques, car nous n'avons par cette approche : - Aucune certitude que la fonction sous-gradiente converge monotonement vers l'optimum de la fonction-objectif originale, - Aucune garantie que les valeurs trouvées pour Xj forment une solution réalisable pour le problème original. L'algorithme est le suivant : 1. Trouver la solution réalisable initiale et calculer la valeur de la fonction- objectif pour cette solution (LBARRE). 2. Tant que [LBARRE-LU)AU > EPSI parcourir l'espace réalisable par le lagrangien LU : fonction-objectif pour le lagrangien EPSI : valeur de l'erreur admissible entre LBARRE et LU. 2,a Calculer les nouveaux multiplicateurs Ui i=l.....n Un(I,..n)=Un-1(1,..,n) + TP Vk(n-1)(1,..,n) Ui représente l'ensemble des multiplicateurs actuellement utilisés dans la fonction sous-gradiente et Vk[I) vaut 1 si l'entité I n'appartient pas à la solution locale actuellement atteinte. Le facteur TP représente l'accroissement relatif de la valeur de la fonction-objectif au point actuellement atteint par rapport à la norme du vecteur Vk élevée au carré. 41 Chapitre 4 2.b Calculer CBARRE tel que dii-Ui, si d^-Ui < O CBARRE1J = { O sinon pour tout i * J 2.c Calculer CBARj = Xi CBARREij 2.d Déterminer les m médianes en fonction de CBARj 2.e Assigner les Xy au groupe du leader j si CBARREij < 0 2.f Calculer ia valeur de LU Le détail et la démonstration des diverses étapes de l'algorithme sont donnés dans Dodge et Arthanari [1981). Sa complexité est de 5kn2, où k est le nombre d'itérations nécessaire pour obtenir la convergence entre LBARRE et LU. Les besoins en mémoire sont également moindres, mais restent toutefois importants. Nous supposons que la solution initiale est donnée par la partition {1,2,3) et (4,5,6), déterminée arbitrairement. Les médianes initiales sont déterminées en prenant la somme des distances minimale à l'intérieur de chacun des groupes. Nous avons ainsi (1) et (6). Nous pouvons calculer la somme totale des distances de cette solution initiale que nous avons appelée LBARRE. Elle vaut 30.0. Nous commençons les calculs au gradient zéro avec Uq = (0,0,0,0). Ainsi CBARRE = 0, pour tout ij et CBARj est également nul pour tout J. Nous pouvons choisir n'importe quelle entité comme médiane. Nous utilisons toutefois celles déterminées lors de l'initialisation de la solution. Le vecteur VK vaut ainsi (0,1,1,1,1,0), puisque seuls (1| et (6| font partie de la solution courante. Nous pouvons maintenant calculer les nouveaux multiplicateurs Uj = Uq +2 * (0,1,1,1,1,0) = (0,2,2,2,2,0). TP a été fixé à 2. Nous pouvons déterminer que CBARRE est nul en tout point, puisque pour tout ij la différence entre le multiplicateur et la distance est plus grande que zéro. Le processus se répète jusqu'à ce que le critère d'arrêt ait été atteint. Nous avons pu nous rendre compte que cette méthode ne converge pas. Ainsi, nous avons dans notre réalisation informatique renforcé ce critère d'arrêt, afin d'éviter que notre programme ne boucle. 4.1.2 Minimisation de la somme des carrés dans les groupes Nous considérons une variante de la fonction-objectif à minimiser. Il ne s'agit plus de la distance â la médiane, mais de la somme totale des carrés entre les groupes. Le problème principal réside dans le (ait que la fonction-objectif considérée est non-linéaire. La contribution de la j*me colonne de la matrice X & l'accroissement de la fonction-objectif sera donnée par : 42 Approches par la programmation mottiémaîique k k-1 Cikj = <*ikj - JId111, >2/k+1 + (Zdiij)2 / k (4.1.7) où k=1,2,...,n-1 Nous utilisons sans changement notable la condition de chaînage et l'algorithme de partitlonnement vus ci-dessus. Il suffît de changer le calcul du "coût économique" d'une solution partielle générée. La complexité de cette formulation n'est en rien modifiée par ces changements, car !'enumeration complète des solutions partielles reste nécessaire. Nous renonçons â illustrer par un exemple cette variante due uniquement & l'Implantation d'une fonction- objectif differente. 4.1.3 Critique Nous avons déterminé ci-dessus la complexité de ces deux algorithmes. Nous avons vu que pour l'algorithme de partiüonnement par enumeration, elle est particulièrement pénalisante au point de vue performance. Cependant la réalisation de cet algorithme donne un programme court, avec des instructions très simples (quelques additions ou soustractions â partir de données élémentaires ou de données structurées â un niveau, quelques tests sur ces mêmes données, et la gestion de deux "pointeurs"). Le problème principal consiste d stocker la matrice constituant le système d'équations. Puisque cette méthode ne recourt qu'à des opérations élémentaires et qu'elle procède par enumeration complète, elle limite les risques de propagation d'erreur, La méthode basée sur l'utilisation d'une fonction sous-gradiente de multiplicateurs de Lagrange est bien moins complexe. Certes, il n'est pas possible de déterminer précisément la valeur du facteur k. Cet algorithme utilise également des opérations simples avant tout. H n'y a pas de garantie que la fonction choisie converge vers la solution optimale. Nous avons pu le vérifier par simulation. Le problème est la détermination de l'ensemble des multiplicateurs d'une Itération â l'autre. L'accroissement n'est plus suffisant après quelques itérations pour que toutes les entités soient affectées â un groupe. Chacune des méthodes nécessite de la part de l'utilisateur quii fixe le nombre de groupes à obtenir. Ainsi, l'une des réserves émises quant & la qualité de la solution fournie par les méthodes classiques se retrouve pour une formulation en programmation entière. 43 Chapitre 4 4.2 L'approche par la programmation dynamique 4.2.1 Algorithme Cette méthode examine un système qui évolue d'un état vers un autre en fonction d'actions accomplies â chaque étape d'une prise de décision. Sur la base de la décision prise, nous avons un résultat "économique", qui peut être un bénéfice, une perte, le coût de l'action, etc.... L'action optimale, c'est-à-dire celle qui permettra d'optimiser le résultat économique, est l'objectif à rechercher. - Le concept d'action est le classement d'une ou plusieurs entités, dans un groupe donné â une étape connue du processus. Ainsi, les actions de la première étape consistent â classer un certain nombre d'entités dans le premier groupe. A la deuxième, nous traitons les entités du deuxième groupe, en tenant compte des premières actions, et ainsi de suite jusqu'à ce que les n entités aient trouvé leur place dans l'un des m groupes. Notons que le processus commence â une étape 0, pour laquelle nous définissons un état fictif. A cette étape, aucune entité n'est classée. A chacune des étapes du regroupement, nous ne pouvons classer au maximum qu'un nombre d'entités donné par les formes de distribution. Entre deux étapes successives, les états sont connectés par des arcs. Pour qu'un arc soit réalisable, il faut absolument qu'une entité contenue dans un état donné de l'étape K-I, le soit aussi dans l'état connecté de l'étape K, pour HKIMq-I. Pour K=O, un arc existe, connectant cet état particulier â tous ceux de l'étape K=I. L'algorithme utilisé exploite le réseau des actions réalisables par "parcours arrière" (backward value iteration algorithm), n calcule à chaque itération le résultat de la formule récurrente suivante : 0 pour k = Mq Wk*Cz)={ (4.2.1) minz [T(y-zï+Hv+1*(y)] pour k=MQ,...,0 où M = nombre de sous-ensembles non-vides et disjoints dans lesquels les n éléments sont classés. Mq = M Si N i 2M, et N - M Si N < 2M K = index de Ia variable d'étape. z = variable d'état représentant un ensemble donné d'entités â l'étape K. y = variable d'état représentant un ensemble donné d'entités â l'étape K+I. y-z = sous-ensemble de toutes les entités contenues dans y, mais qui ne le sont pas dans z. 44 Approches par ta programmation mathématique T[y-z) = le coût de transition de l'étape K + 1 à l'Étape K. L'homogênîêtê d'une partition sera mesurée par le critère : w = 2 T(Yk) avec T « <1/nk> 2 2 (4-2.2) k=1 i,j e ykJ L'objectif de cette formulation est de minimiser la somme des carrés à l'intérieur des groupes et de maximiser la somme des carrés entre les groupes. c'est-a-dire d'obtenir les groupes les plus homogènes et le plus disjoints possibles. 4.2.2 Critique La complexité de cette méthode est une combinatoire entre le nombre d'entités et le nombre de groupes. Pour classer 9 traitements dans 3 groupes, il faut 3 étapes avec à l'étape 1 456 états, et a l'étape 2 encore 174. Q faut examiner par la procédure de "parcours arrière" 174 possibilités de classification entre les étapes 3 et 2, et entre les étapes 1 et 0. Entre les étapes 2 et 1, il faut examiner de nombreux arcs, pour chacun des 174 états. En comparaison, l'algorithme de programmation entière, basé sur le parüüonnement par enumeration, génère 74 classifications potentielles, grâce à la condition de chaînage des entités. Et on n'examine les possibilités que pour les groupes de la liste 1, soit dans notre cas 8. H est également possible d'exploiter le réseau par un algorithme de parcours avant ["Forward Value Iteration"), c'est-à-dire de partir depuis l'étape 0 [aucune entité classée). Cette version n'est pas favorable, puisque la complexité est ainsi augmentée. En effet, nous aurions 456 "chemins" différents au départ, au lieu des 174 exploités en procédure de parcours arrière. Le problême de la stabilité ne semble pas se poser. Comme nous traitons des variables discrètes, nous ne faisons aucune approximation. Selon Bellman et Dreyfuss (1965, p.343-349), Q se pose dans les cas, où les variables discrètes servent & représenter une fonction d'une variable continue. Hs ont d'ailleurs démontré que la programmation dynamique fournit de bons résultats, comparé aux méthodes d'optimisation classiques [calcul de variations, calcul différentiel, ...). Nous pouvons nous attendre à ce que la solution proposée par l'algorithme décrit ci-dessus, soit la solution opümaledu problême. 4.3 Approche par la programmation linéaire L'algorithme vu ci-dessus permet de résoudre notamment le problème de la "route la plus courte" ou de l'allocation minimale de ressources. Ce genre de problème se résout également par la programmation linéaire. 45 Chapitre 4 4.3.1 Algorithme Pour résoudre le problème ainsi posé, nous utilisons la propriété de complémentarité entre le problème primai d'un modèle linéaire et son dual. Nous nous servons d'une méthode similaire a celle utilisée pour résoudre un problème de transport. Le primai s'exprime sous la forme : Minimiser Cf se Af= b fiO Alors que le dual est : Maximiser b*w se A-W £ C" w sans restriction dans le signe Avec : f = EfQ].....fj •), le vecteur des arcs liant les états dans une solution réali- sable C : le coût de transition d'un état a l'autre A : la matrice linéaire représentant le réseau b'= (1,0,0.....-U w = (wq.....w.) le vecteur des variables duales Posons sous une forme partiellement étendue le problême dual : Maximiser wq - w* se w0 - w1 * c0,1 w0 - w2 i C0#2 W0 - W3 S C0i3 w1 - w6 i C1,6 W1 - w* s C1,* w sans restriction dans le signe De la même manière que nous le ferions dans un problème de transport, nous pouvons déterminer simplement la valeur de wq, puis résoudre séquentiellement le système d-dcssus. La valeur pour wq est donnée par : wg " min 0OM (0,: • ,Jc) £ A 46 Approches par ta programmation mathématique La résolution du système dual pennet de déterminer les arcs & éliminer du réseau, si la différence Cj i-(wpWj] est plus grande que zéro. Ce procédé de calcul est répété jusqu'à ce qu'une "route" soit trouvée entre le node O et le node *, au travers du réseau restreint formé ainsi. L'algorithme complet, pour représenter le problème de classification automatique en modèle de programmation linéaire est : 1. Trouver les formes de distribution des m objets en k groupes 2. Générer le réseau des états. 3. Déterminer le coût de transition le long de chacun des arcs réalisables. 4. Appliquer la méthode priroale-duale jusqu'à ce que la route soit trouvée entre le node O et le node •. Nous avons le réseau d'états partiel suivant pour notre problème de référence. {1,2,3,4,5} / \ / \ / \ / \ 0 — {1,2,3,4} ------- {1,2,3,4,5,6} \ / \ / \ / \ / {1,2,3} Sur chacun des arcs générés, nous pouvons calculer le coût de transition d'un état à l'autre, n s'agit du coût en distance par l'ajout des entités supplémentaires pour arriver a la solution sur laquelle l'arc pointe. Ainsi le coût de transition pour l'arc, qui relie la solution initiale, aucune entité classée, à la solution (1,2,31 est égale û (8.S2 +4.52 + 9.O2), soit 173.5. Pour calculer le coût le long de l'arc entre {1,2,3} et {1,2,3,4,5,6), nous considérons que nous formons pour ce passage le groupe (4,5,6}. Ce coût de transition est la somme des carrés dans le groupe ainsi déterminé, a est égal a (152 + 32+ 142). soit 430. Nous représentons rapidement quelques coûts de notre réseau. {1,2,3,4,5} /849 \ / \ 0 / \ / 372 196 \ 0 — {1,2,3,4} ------- {1,2,3,4,5,6} \ . / \ / \ 173 /430 \ / {1,2,3} U coût le long de l'arc reliant (1,2,3,4,5) â {1,2,3,4,5,6) est nul, car le groupe 47 Chapitre 4 formé ne contient que l'entité 16). Nous pouvons poser le programme dual partiel suivant : max Wq - w* SC Wq-W-j ! 849 Wq - W2 i 372 Wq - W-j i 173 w-i - w* S. 0 «2 - w* 4 196 Wj - W* i 430 w sans restriction dans le signe Nous déterminons la valeur de w0, soft le minimum sur [849,372,173) =173. Puis nous résolvons séquentiellement toutes les équations. Ici, la résolution n'a pas grand sens, vu que nous avons négligé les 9096 du réseau au moins. Une fois toutes les valeurs pour W1 connues, nous pouvons par le calcul Cji - Iw1 -wj, éliminer tous les arcs pour lesquels cette difference est plus grande que zéro. Finalement, nous trouvons la solution habituelle, soit les groupes (1,3,5} et (2,4,6]. 4.3.2 Critique Les problèmes de complexité soulevés par le modèle de programmation dynamique ne sont pas résolus par l'application de cette méthode. En effet, il s'agit dans une première étape de déterminer également le réseau complet et de calculer le coût de transition le long de tous les arcs réalisables, en exploitation avant du réseau. Nous avons vu précédemment que cette solution n'était pas recommandable, qu'il valait mieux exploiter par la procédure de retour arrière. Ensuite seulement, nous commençons â résoudre le problème proprement dit. La résolution du dual conduit â considérer un système d'équations très nombreuses, une par arc réalisable. Le réseau est parcouru en entier au minimum deux fois au cours de la procédure complète. 4.4 Approche Branch and Bound 4.4.1 Algorithme Envisageons la façon suivante de classer les n entités en m groupes : Choisissons n=9 et m=3 pour limiter notre problème. Prenons tout d'abord les m groupes vides, choisissons ensuite de classer le premier élément de N et classons-le dans le groupe J ]. Examinons maintenant les possibilités de classer le deuxième élément. Nous pouvons soit le classer dans Jj soit dans J2 ¦¦¦ Ce qui nous donne deux solutions partielles. Cherchons ensuite fi classer le troisième élément de la liste. Il peut s'ajouter dans la première solution Issue du classement du deuxième : soit dans Jj, soit dans J2- 48 Approches por lo programmation mathématique Mais 11 est également possible de reprendre â partir de la 2e solution ( de classification pour l'élément 2), Auquel cas, notre troisième élément peut prendre place soit dans Jj, soit dans Jji 80^t dans J3. En poursuivant ce raisonnement, nous pouvons construire l'arbre des solutions partielles suivant [seule une partie de l'arbre est représentée) : J1=(U J21 =0 J3=O J1=(I,2} J2=O J7 = O J1=(I,3) J2={2> J-J=O J1=(D J2={2,3} Ji=O J1=(I,2,3} J2=O J^=O Figure 4.4.1 Arbre des solutions de classification Le Branch and Bound est une méthode permettant de construire un "arbre" en élaguant les branches inutiles, et déterminant finalement la solution optimale au problême. Considérons le problème de partitionner N en m groupes tels que la fonction- objectif suivante soit minimisée : C(J) = Z T(J1) i=l (4.4.1) où J={J-| ,J2, ... ,J1n) le sous-ensemble des m groupes et r le critère d'homogénéité des groupes L'algorithme de "Branch and Bound" se caractérise par le calcul de bornes sur les solutions partielles et par des règles de construction de ces dernières. Ces bornes correspondent a la variation que subit le coût total d'une solution partielle lors de l'ajout d'un élément supplémentaire. Pour notre problème de classification, nous considérerons les deux bornes suivantes : - La première borne est le coût de non-classification des n-q objets, n s'agit d'un coût d'opportunité, car par rapport à l'objectif fixé, nous dépensons une certaine somme & ne pas avoir tous les objets classés et notre fonction-objectif minimisée. - Pour chaque solution partielle, nous pouvons déterminer de manière 49 Chapitre 4 précise quel est l'accroissement de la fonction-objectif, lorsqu'un des objets non-encore classés vient prendre place dans l'un ou l'autre des groupes. Ce coût sera nul, si nous générons le descendant d'ordre (q+l,s+l) par notre première règle de branchement. Nous pouvons connaître a tout moment la valeur de la fonction-objectif pour toute solution partielle. La borne totale d'une solution partielle sera la somme de la fonction-objectif partielle et du maximum entre le coût d'opportunité et l'accroissement de la fonction-objectif décrits ci-dessus. Lc coût d'opportunité est donné par la formule : _ m-r m Ô(N ) = étape précédente). Puis, pour le passage entre la seconde et la première, nous en évaluons 27*9, 243. Entre la première et l'état initial, nous n'examinerons que celles qui sont les meilleures. Le nombre de routes partielles restantes, respectivement les états sélectionnés comme noeuds, est au minimum de une par forme de distribution. Nous parcourrons au minimum 9 arcs. Le maximum est en tout cas inférieur aux 36 états de cette première étape. Raisonnablement au moins la moitié des arcs sera éliminée, nous aurions vraiment dans le pire des cas 18*9, 162 arcs, à examiner. Au total, nous évaluons entre 432 arcs, le maximum, et 279 au minimum. Nous sommes là toujours très loin du nombre d'arcs qui composent le réseau généré avec la formulation de Jensen. Dans cette dernière, rien que le passage entre l'étape finale et la seconde requière déjà l'examen de 174 arcs. Nous savons ensuite que chacun de ces 174 arcs doit être connecté avec les états de la première étape. Cette opération n'est pas très aisée. D'une part, nous devons examiner tous les arcs existants pour une forme de distribution afin de savoir si la connection est possible. D'autre part, nous devons déterminer les éléments de transition (ceux qui sont classés par ce lien] et le coût de cette action. Nous retrouvons ce second problème dans notre 96 Conclusion et recommandation première formulation, mais à une plus petite échelle. Par simplification, nous supposerons que le nombre d'arcs possibles entré ces deux étapes par forme de distribution est le carré du nombre d'objets, dans notre cas 81. Nous devons évaluer 14094 arcs entre la seconde et la première étape de l'algorithme avec la formulation d'origine. A partir des 456 états de la première étape, là aussi nous supposons que la moitié est éliminée, il ne reste que 228 arcs à examiner. Au total, sous la condition que notre restriction ci-dessus soit correcte, nous parcourons un réseau de 14496. La seconde définition de notre nouvelle formulation nous oblige à examiner au départ 36 liens. Puis, nous pouvons nous restreindre pour chacune des formes à n'en examiner que 8 par état de la deuxième étape. Nous savons que seuls ceux pour lesquels le leader est different sont connectables. Nous devons toutefois examiner si l'intersection des deux sous-ensembles est bien vide. Nous évaluons au maximum pour cette action (passage de la seconde étape a la première] 288 états. Puis dans le dernier passage, nous pouvons en compter au pire 18, si seule la moitié des liens est éliminée. Au total, nous ne parcourons plus que 342 arcs. Un autre avantage de cette méthode est à relever : nous pouvons déterminer dès la génération du réseau tous les coûts de transition, car nous accédons d'office à la matrice des distances. Ceci n'est pas possible avec la première formulation, puisqu'elle se base sur le nombre total d'entités classées a une étape, et non pas sur celles qui sont effectivement assignées à un nouveau groupe. ' A titre de comparaison, nous reprenons les éléments dégagés ci-dessus pour la méthode de programmation entière. La formulation d'origine modifiée examine pour chacune des 8 solutions formant la liste 1 85t8-1* solutions, soit 86^-1' recherches de liens, soit en clair 1*835.008 "arcs"; La formulation réduite par la recherche des objets représentatifs 83 examens, 512 en clair. L'algorithme de PAM comporte quant à lui au maximum 2*2*82 + 2'8^8"3' boucles, soit en clair 336 boucles d'opérations simples. Pour les méthodes de programmation mathématique, nous n'avons pas relevé le nombre d'opérations d'examen de liens, mais elles se composent de doubles boucles à maximum n passages. En règle générale, nous avons remarqué dans toutes les méthodes que chacune des ces boucles de calcul se composait en moyenne d'une dizaine d'instructions simples. Aussi, toujours sans compter, les opérations nécessaires de traitement des données entrantes et de communication du résultat final, nous estimons que nos méthodes exécutent au total le nombre d'opérations suivantes : - programmation dynamique - programmation dynamique, réduite 1 - programmation dynamique, réduite 2 - programmation entière, complète - programmation entière, réduite - méthode de PAM 11741760 349920 277020 1.49* IO9 414720 30240 La formulation semble dans ce cas suffisamment prometteuse pour que nous tentions une dernière réduction. En utilisant le concept de chaînage des entités à un leader, nous avons pour le moment considéré que toute entité en est un. Nous avons conservé la définition d'origine développée par Rao. Mais nous pouvons très bien considérer que seuls m objets représentatifs sont intéressants, comme nous l'avons fait ci-dessus pour la programmation entière. 97 Chopftre 8 Le nouvel algorithme s'exprime par les étapes suivantes, nous ne les détaillons pas Ici avec les équations : 1. Déterminer les objets représentatifs (médioïdes) par "bswap", la méthode développée par Rousseeuw. 2. Déterminer les formes de distribution pour la méthode de programmation dynamique. 3. Générer l'ensemble des états (solutions potentielles) en appliquant la règle de chaînage sur chacune. 4. Optimiser par l'algorithme de programmation dynamique en parcours arrière. Nous réduisons de la sorte très fortement le nombre des états générés pour chacune des formes de distribution. Toutefois nous devons prendre en considération deux cas limites qui peuvent se présenter : - Une entité est plus proche de deux médianes qu'une autre; - Une entité est equidistante de deux leaders; Ces deux cas sont traités lors de la création du réseau, de telle sorte qu'une entité donnée ne peut appartenir qu'au groupe de sa meilleure médiane. Nous allons illustrer chacun des problèmes avec un exemple. Nous traiterons tout d'abord du problème de !'equidistance. Soit le fichier de données suivant : 1 . 1 . 1 . 1 . 1 . 2. 2. 2. 2. 2. 3. 3. 3. 3. 3. 4. 4. 4. 4. 4. 9. 9. 9. 9. 9. Nous voulons obtenir trois groupes à partir de ces données. Nous avons deux cas d'équidistance : d'une part l'entité (2| par rapport à EU et (3} et d'autre part {31 avec (4) et (2). Supposons que (2J, {4} et {9J sont les objets représentatifs pour cet échantillon. L'entité (1) ne peut faire partie que du groupe dont (2) est le médioïde. Par contre, l'objet (3) peut appartenir à la fois au groupe de (2) et à celui de {4), ce qui n'est pas envisageable en classification automatique. Nous avons dû trouver une règle qui élimine ce genre de problème : - Si un objet est equidistant de deux médioïdes, dont l'un est justement celui pour lequel nous construisons la solution; alors, à moins qu'A ne soit le dernier élément manquant au groupe et à la fols le dernier des objets que nous puissions classer, il n'entre pas dans la solution en cours. Le deuxième cas est assez rapidement Ulustré, soit les quatre entités suivantes et leur distances : A 0. B 9. 0. ' C 13. 11. 0. D 15. 19. 12. 0. A et C sont les objets représentatifs de l'échantillon. 98 Conclusion et recommandation Nous constatons que [B) est l'élément le plus proche des deux médioïdes. Nous risquons, lors de la construction du réseau des états de générer les solutions (A1B) (C1B). pour la même forme de distribution. Le résultat étant que l'algorithme ne trouve pas de solution optimale au problème. Pour résoudre ce cas limite, nous avons dû introduire deux règles : - Une entité ne peut pas appartenir à deux solutions de la m6me forme de distribution, sauf si nous créons les états de l'étape 1, ou s'il s'agit de la dernière pour obtenir le nombre d'éléments d'un groupe potentiel. - Une entité a classer ne peut appartenir qu'au groupe de ta médiane dont elle est le plus proche. Ënfln, nous avons encore explicitement exprimé dans notre Implantation la règle que : - Une médiane ne peut appartenir au groupe d'une autre médiane. Nous avons alors procédé à une nouvelle série de simulations qui nous a montré que les qualités de calcul de l'algorithme original étaient préservées, mais que les temps de calcul étaient en revanche très réduits. Cette nouvelle formulation ne nous a pas entièrement satisfaits, car sa complexité mémoire est encore trop importante. Pour traiter de grands problèmes, nous serions contraints de stocker une partie des données en mémoire auxiliaire (=disque). L'examen détaillé de l'algorithme d'optimisation original nous a montré que nous réalisions pratiquement un parcours d'arbre en largeur [breath search) pour examiner les états & lier, ce qui oblige à mémoriser tous les résultats intermédiaires. Nous avons donc décidé d'utiliser la technique de la recherche en profondeur (depth search]. De cette manière, nous n'avons plus besoin de mémoriser en permanence tout le réseau des états et réduisons la complexité mémoire. Nous exposons en détail cet algorithme : 99 Soit d une mesure de la distance entre les objets 1. Déterminer les objets représentatifs (médioïdes) Le premier médioïde est déterminé par : Trouver i | X^ij = min ^ij i'i = 1 »•¦•»!! (8.1) Les médioïdes suivants sont déterminés par la formule itérative : Trouver i | Ci = max(Cj) j=1,..,n (8.2) avec Cj = X maxtdpq- dpj,0) (8.3) q=1,...,n(-médioïdes) p | p e {médioïdes) L'ensemble des médioïdes est amélioré par une série de permutations par la procédure itérative Tant que l'on effectue une permutation : Trouver i | C1 > 0 (8.4) avec Ci = !(dog- dai) (8.5) q *^ M q=1,.,n(-médioïdes,!) tel que q est plus proche de p que des autres médioïdes P= 1 médioïde donné i= 1 objet non médioïde 2. Déterminer les formes de distribution des n objets en m groupes de telle sorte que : nj i n2 *.. .2. T^n (8.6) 3. Générer les états forme par forme et étape par étape en calculant la formule récurrente, et en utilisant les règles de construction énoncées ci -dessus : Pour f variant de 1 au nombre de forme faire : Pour x variant de 1 à m : 0 pour k+1= Mq Wk+1*(z)={ (8.7) minz [T(z-y)+Wk (y)] pour k=1,..Mq-I OÙ M = nombre de sous-ensembles non-vides et disjoints dans lesquels les n éléments sont classés. Mq = M si N Ä 2M, et N - M si N < 2M f = index de la forme de distribution x = index de l'objet représentatif 100 Conclusion et recommandation k = index de la variable d'étape. z = variable d'état représentant un ensemble donné d'entités à l'étape k+1, ordonnées en fonction de leur distance par rapport au médioïde de l'étape k+1. y a variable d'état représentant un ensemble donné d'entités à l'étape k. Le nombre d'entités dans z et y est donné par la forme de distribution. z-y = sous-ensemble de toutes les entités contenues dans z, mais qui ne le sont pas dans y. T(z-y) = le coût de transition de l'étape k à l'étape k+1. L'homogéniété d'une partition est mesurée par le critère, soit la somme des carrés dans les groupes : W = E TCyk) avec T(yk) = (1/nk) I (^1-;)2 (8.8) k=l i,j £ yV ou la somme des distances aux médianes W=S T(yk) avec T(yk) = £ (dj,} (8.9) k=1 i,j e yV i = médiane Si Wk < W, alc>rs W'= Wk et mémoriser la solution qui a généré Wk . A la fin des itérations, la solution mémorisée est la solution optimale. Par rapport aux méthodes de partitionnement et hiérarchiques, nous cherchons à minimiser par la formule récurrente sur l'ensemble des objets contenus dans une solution et en examinant tous les branchements possibles à partir d'une étape. Une fois, les objets représentatifs déterminés, nous n'effectuons pas une simple affectation, mais un véritable calcul d'optimisation par rapport à PAM. Par rapport à la programmation dynamique, nous éliminons toutes les équations redondantes, en introduisant les concepts d'objets représentatifs et de chaînage des autres. Nous supprimons également la redondance des formes de distribution par la règle 8.6. Nous utilisons un parcours en profondeur et ne générons les solutions que lorsque nous avons besoin. 8.3 Résultats des nouveaux concepts Nous avons réalisé une nouvelle phase de simulation restreinte, par rapport & celle du chapitre 7, avec les deux modèles de générateurs. Enfin, nous avons soumis les nouvelles méthodes de programmation dynamique a des tests sur des 101 Chapitre 8 cas limites, puisqu'elles sont plus rapides que la nouvelle mouture de l'algorithme de partitionnement. Nous avons cette fois travaillé sur un AT-286, équipé d'un co-processeur mathématique. Nous avons repris la méthode de PAM, comme exemple de méthode classique, â laquelle nous avons confronté les deux nouvelles versions de la programmation entière décrites dans la section 1, et les deux algorithmes dynamiques décrits ci- dessus. Le premier tableau présente les résultats des simulations, le second donne les temps de calculs obtenus avec divers échantillons. méthode Normal Monte-Carlo PAM 62 65 Rao (listes modifiées) 98 98 Pamrao {Rao + Rousseeuw 98 98 Dynamique (+Rao ) 100 100 Dynamique (Rao + Rous-) 100 100 Modèle Pam Rao Pamrao Dynarao Newdyn 6/2 1" 1" 1" 1" 0"57 10/2 1" 1" 1" 1" 1" 20/2 2" 15" 3" 1" 1" 6/3 1" 1" 1" 1" 0"81 9/3 1"55 3" 1" 1"60 0"90 12/3 1"79 12" 2" 2"37 0"90 18/3 2"76 118" 4" 11 "03 2"35 30/3 5"60 2800" 50" 25" 5"87 Les temps de calculs sont pour ces petits jeux de données acceptables, même si nous pouvons déjà remarquer une explosion pour la méthode de programmation entière et la méthode de programmation dynamique originales. Cette explosion se reproduit également pour "pamrao" et "newdyna", dès que le nombre de données dépasse 20 et/ou le nombre de groupes dépasse 3. Mais pour cette dernière méthode le gain est excellent par rapport â la méthode originale de programmation dynamique. Pour classer 62 entités dans 3 groupes, les calculs durent environ 36 heures, alors qu'avec la méthode réduite, il ne faut que 23 minutes. Finalement nous avons, pour compléter notre évaluation, repris les données de Hartigan dont nous nous étions servis au chapitre 7, soit les crimes dans les 102 Conclusion et recommandation villes et la valeur nutritive des aliments, sans standardiser les données. Nous obtenons avec nos trois nouvelles définitions les résultats ci-dessous : Crimes [2 groupes) : Groupe 1 : Hartford, Atlanta. Boston, Chicago Groupe 2 : Dallas, Denver, Detroit, Honolulu Crimes (3 groupes) : Groupe 1 : Denver, Dallas, Detroit, Honolulu Groupe 2 : Chicago, Boston Groupe 3 : Atlanta, Hartford Enfin, les trois groupes pour !es aliments sont : Groupe 1 : steak de boeuf, boeuf braisé, roast beef Groupe 2 : hamburger, rôti de boeuf, poulet frit Groupe 3 : coeur de boeuf, poulet rôti Comme nous nous y attendions les résultats sont les mêmes. En standardisant les données des "crimes", nous obtenons également la solution proposée au chapitre 7. 8.4 Recommandations tes méthodes dites classiques se sont révélées très inférieures aux méthodes de programmation mathématique lors de tous nos tests. L'écart entre les différentes méthodes classiques est même très important. Nous pourrions recommander l'abandon des méthodes hiérarchiques et de partitionnement en raison de ces mauvais résultats. Nous sommes d'avis que les ajouts de critères, ou une nouvelle formule de récurrence ne changeront rien. Nous avons pu montrer que la faible convergence de ces méthodes provient en réalité de la réduction des calculs â des paires, soit d'entités ou de sous-classcs. Cette réduction conduit souvent à ignorer une solution correcte au point de vue optimaUté. Sous certaines conditions, la méthode développée par le professeur Rousseeuw donne des résultats satisfaisants. Cette recommandation est toutefois une utopie, car chaque recherche a son but et les sommes d'efforts Investis dans ces méthodes rendent leur abandon impossible. Toutes les méthodes issues de la programmation mathématique ne donnent pas satisfaction. Ainsi, nous avons constaté, que les méthodes de Branch and Bound et la réduction par un lagrangien de la formulation en programmation entière ne donnent pas entière satisfaction quant â leur convergence. La deuxième est d'ailleurs de loin la plus mauvaise des méthodes que nous avons examinées. Nous recommandons l'abandon de la recherche sur ces deux méthodes. Les formulation de programmation entière et de programmation dynamique 103 Chapitre 8 obtiennent de loin les meilleurs résultats. Leur convergence est de 10096. Malgré les faibles performances obtenues, nous pensons que la voie de la programmation mathématique est la solution d'avenir de la classification automatique. Elle ne résout pas le problème du nombre de groupes optimum pour le Jeu de données. Même si la méthode de calcul est bonne, nous n'avons pas cependant résolu tous les problèmes de "mauvaise" utilisation. Pour le moment, nous ne sommes pas encore capable de déterminer avec certitude le nombre des groupes à chercher, nous ne savons pas quelle est la meilleure fonction-objectif à minimiser, et dans quel cas faut-il standardiser les données. La réduction de la complexité de l'algorithme de programmation dynamique a donné de bonnes performances au point de vue temps de calcul par rapport à l'original, mais nous sommes loin de la vitesse des méthodes classiques. Dès que le nombre de groupes recherché dépasse 2, et que le nombre d'objets fi classer dépasse 30 nous avons déjà trop de solutions â calculer. En revanche, le gain par rapport â l'algorithme original est très important : 11 faut environ 23 minutes avec la nouvelle définition pour former trois groupes â partir des 62 entités d'un de nos jeux de test. Avec l'original, il nous a fallu patienter 36 heures. Nous avons eu l'occasion de tester brièvement une machine équipée d'un processeur i486 (nouvelle génération), les performances sont dix à quinze fois meilleures, que ce que nous avons obtenu jusqu'à présent. L'amélioration de la vitesse de calcul des PC de pointe va permettre de compenser la lenteur relative de ces algorithmes. Nous n'avons pas cherché â utiliser ce nouvel algorithme sur des machines encore plus performantes [mini ou mainframes). 104 Annexe 1 : Mode d'emploi des programmes PC Sur demande, nous fournissons certains des programmes développés dans le cadre de cette étude : RAOMEDIA : programme selon l'algorithme de programmation entière complet PAMRAO : programme selon l'algorithme de programmation entière réduit DYNARAO : programme selon l'algorithme de programmation dynamique incluant la réduction par Ia règle de chaînage NEWDYNA : réduction de l'algorithme de programmation dynamique par la règle de chaînage et la détermination des objets représentatifs Tous ces programmes ont été développés sous DOS 3.30, en utilisant les librairies d'émulation et le modèle large de mémoire. L'usage de l'émulation nous permet d' exploiter un co-processeur mathématique, s'il est présent, La configuration matérielle requise pour les utiliser est : - 640 Kbytes de mémoire vive; [dont 500 libres] - un disque dur; - un écran monochrome; - en option un co-processeur mathématique; Le co-processeur réduit, selon nos tests faits avec un AT-286 à 12Mhz, les temps de calcul au tiers de ceux obtenus en configuration simple. Par contre, nous n'avons pas vu de difference de précision des calculs. Les programmes ne sont pas protégés, ils peuvent être copiés sur un disque dur, ou une disquette de sauvegarde, par la commande COPY de DOS, ou toute commande équivalente d'un gestionnaire de fichier {PC-Tools,Norton-Commander, etc]. Voici le mode d'emploi des programmes de programmation entière, dont le dialogue est en français : - Saisie des données par clavier ou fichier; Dans les 2 cas, Ie programme va demander, respectivement lire dans le fichier les données dans l'ordre suivant : - nombre d'objets à classer; - nombre de groupes à former; - norme à utiliser pour le calcul de la distance; - nombre de caractéristiques des objets; 105 Annexe 1 - les éléments de la matrice des données, chaque ligne contenant les observations pour un objet; - Choix de l'unité de sortie, fichier ou écran; En cas de travail avec des fichiers, U faut Impérativement donner le nom complet du fichier, selon les règles de DOS, s'il ne se trouve pas dans le répertoire des programmes. Pour les personnes en ayant l'habitude, la commande PATH, pour donner le chemin d'accès aux programmes, peut être utilisée sans restriction. Ces deux programmes permettent de lire une matrice de distances, dans ce cas, elle doit être préparée sous forme du triangle inférieur, avec les zéros. Les limites des programmes sont données à l'écran et des tests sont faits pour vérifier qu'elles sont respectées. En cas de saisie interactive, les données peuvent être corrigées. Lors d'une lecture sur un fichier, l'erreur est signalée et le programme s'arrête. Pour les deux autres programmes, si les données sont entrées par un fichier, Ü faut que ce fichier soit rentré comme une matrice ; X11 X12 X1n X21 X22 X2n Xm1 Xm2 Xmn Ensuite le dialogue suivant guide l'utilisateur dans le choix des options : 1, Give the number of objects : Give the number of variables : do you want to read your data from the keyboard Y/N Y = entree des données sous forme de dialogue N = lecture des données depuis le fichier dont le nom est donné plus tard Do you want your output on screen, printer, or in a file Please give the name of the device (con, pm, filename) : con = sortie a l'écran pro = sortie sur l'imprimante lpt1 filename = écriture dans un fichier, donner le nom selon les règles de DOS 2. Give the number of clusters : 106 Mod© d'emploi Choose between Ll or L2 : 1 :=L1 2:=L2 Do you want to standardize your data : Y = yes N = No Which objective function do you wish to use Total distance to the medians = 1 Within clusters sum of squares = 2 Average distance to the medians = 3 3. Après la sortie du résultat : Do you want another run ? Y = yes = continuer de travailler avec le programme N = no = fin du travail Do you want to use the same dataset ? Y = yes : continuer avec les mêmes données, dans ce cas le dialogue reprend au point 2. N = no : travailler avec de nouvelles données, reprise avec le point 1. Pour toute remarque, ou pour disposer des informations liées aux développements prévus après cette étude, vous pouvez nous contacter aux adresses suivantes : Prof. Y Dodge Groupe de Statistique Division économique de l'Université Pierre-à-Mazel 7 2000 Neuchâtel Thierry Gather Sous le Chêne 2 2043 Boudevilliers 107 Annexe 2 : Exemple économique de la banque d'Iran Nous présentons ci-dessous la classification obtenue pour des données économiques publiées par la banque dlran. Il s'agit de 55 indicateurs relevés pour chacune des 23 régions iraniennes. Nous avons effectué les calculs avec notre nouvel algorithme de programmation dynamique, en appliquant d'office les deux règles présentées au chapitre 8. Nous avons cherché ô classer les données dans 2 à 6 groupes, en utilisant la distance de Manhattan et la distance totale aux médianes. Tous les calculs ont été effectués sur un AT-286 avec un coprocesseur. Nous pouvons remarquer que l'effet de la classification est S chaque fois de sortir une ou plusieurs données du groupe 1, dont l'entité f2) est la médiane, seul le passage entre 5 et 6 groupes produit un effet différent. Nous voyons que entre le formation du 3e groupe et du 5e, nous n'avons formé que des groupes à une enuté (singleton cluster), qui est la médiane nouvellement déterminée. 108 Exempte économique ******************************************************* * * * Dynamic Programing Cluster Analysis Algorithm * * reduced with the procedure BSWAP developped by * * Prof. P. Rousseauw and L. Kaufmann Brussels and * * the medians'rule developped by Rao for * * the Integer Programing Algorithm * * author : T. Gafner Univesity of Neuchâtel * * * * * * Program's Limits are : * * Objects : 100 * * Clusters : 10 * * Variables : 60 * * Distances : LI or L2 * * * ******************************************************* Summary of options : Objects : 23 Variables : 55 Clusters : 2 Distance : Manhattan Standardisation of variables Total distance to the medians Begin of computations at : 17:23:31 Cluster 1 Objects 2 410 9 71115 20 121913181716 22 3 14 6 21 23 8 5 Cluster 2 Objects 1 Total distance to the medians 1163.389000 End of computations at : 17:24: 9 Summary of options : Objects : 23 variables : 55 Clusters : 3 Distance : Manhattan Standardisation of variables Total distance to the medians Begin of computations at : 17:27: 8 Cluster 1 Objects 2 4 10 7 11 18 22 3 6 8 5 Cluster 2 Objects 17 14 9 16 21 13 20 15 12 23 19 109 Annexe 2 Cluster 3 Objects 1 Total distance to the medians 995.439000 End of computations at : 17:29:54 Summary of options : Objects : 23 Variables : 55 Clusters : 4 Distance : Manhattan Standardisation of variables Total distance to the medians Begin of computations at : 17:30:13 Cluster 1 Objects 2 41071118 22 3 6 8 Cluster 2 Objects 17 14 9 16 21 13 20 15 12 23 19 Cluster 3 Objects 5 Cluster 4 Objects 1 Total distance to the medians 911.936200 End of computations at : 17:39:44 Summary of options : Objects : 23 Variables : 55 Clusters : 5 Distance : Manhattan Standardisation of variables Total distance to the medians Begin of computations at : 18: 2:41 Cluster 1 Objects 2 410 71118 22 3 6 9 Cluster 2 Objects 17 14 16 21 13 20 15 12 23 19 Cluster 3 Objects 8 Cluster 4 Objects S Cluster 5 Objects 1 Total distance to the medians 110 Exemple économique 835.466500 End of computations at : 16:22: 9 Summary of options : Objects : 23 Variables : 55 Clusters : 6 Distance : Manhattan Standardisation of variables Total distance to the medians Begin of computations at : 18:22:56 Cluster 1 Objects 2 410 71118 22 3 6 Cluster 2 Objects 1714 91613 20 1519 Cluster 3 Objects 21 23 12 Cluster 4 Objects 8 Cluster 5 Objects 5 Cluster 6 Objects 1 Total distance to the medians 767.606800 End of computations at : 18:47:17 111 Bibliographie ARTHANARI T.S., DODGE Y., (1981). Mathematical Programming in Statistics,Wiley, New York. BELLMAN R.E., DREYFUS S.E. {1965). La programmation dynamique et ses applications, Dunod, Paris. Classification Society of America, Journal of Classification, Springer International, vol 4 no 1, 1987. COOPER M.C.,MILLIGAN G. W. (1985). An Examination of Procedures Determining the Number of Clusters in a Data Set, Psychometrica,50, 159-179. EVERITT B. (1974). Cluster Analysis, Social Science Research Council, London. GARFINKEL R. S., NEMHAUSER G.L. (1972). Integer Programming, Wiley,New York. GRAF-JACOTTET M. (1979). Classification automatique aspects mathématiques, Cahier de Méthodes Quantitatives, Université de Neuchâtel. HARTIGAN J.A. (1975). Clustering Algorithms, Wiley, New York. HASTINGS N.A.J. (1973). Dynamic Programming with Management Applications, Butterworths, London. International Federation of Classification Society, Actes du congrès international de juillet 1987 à Aix-La-Chapelle. JENSEN R.E. (1969). A Dynamic Programming Algorithm for Cluster Analysis, Operation Research 17, 1034. METZGER-VOIDE A-C. (1983). Clasfac-Apl un package interactif d'analyse statistique multivariable. Thèse de docorat Université de Neuchâtel. RAO M.R. (1971). Cluster Analysis and Mathematical Programming, Journal of the American Statiscal Association 66, 622. ROUSSEEUW P. (1987). Cluster Analysis, Wiley, New York. SPÄTH H. (1980). Cluster Analysis Algorithms, Ellis Horwocd, London. SPÄTH H. (1986). Anti-clustering : Maximising the variance criterion, Control and Cybenetics No. 2/3. TRICOT M., DONEGANI M. (1987). Optimisation en classification automatique : sur une famille d'indices de proximité en classification hiérarchique ascendante, EPFL-DMA rapport 8702. TRYON R.C, BAILEY D.E. (1967). Cluster Analysis, Wiley, New York. VINOD H.D. (1969). Integer Programming and the Theory of Grouping, Journal of the American Statiscal Association 64, 506. 112 Table d'index ANAFAC 58 Aristote 3 Backtracking 40, 51, 52, 89 Backward 44 Bellman 45, 69, 94, 112 Box 69 BUILD 27, 28, 32, 35, 92 Camberra 10 Carrés 23, 36, 42, 45, 47, 51, 91, 94, 95, 101 Centroïdes 21,23,59,77 Chaînage 13, 15, 17, 19, 30, 31, 38, 40, 43, 45, 59, 91, 92, 93, 95, 97, 98, 101, 105 Chi-carré 9,61 CLAS 58 Classiques 2, 4, 7, 14, 15, 30, 33, 34, 43, 45, 54, 57, 59, 73, 75, 76, 77, 76, 92, 103, 104 Clumping 14 Complexité 2, 4, 5, 30, 31, 32, 36, 38, 42, 43, 45,48, 52, 54, 65, 66, 68, 92, 99, 104 Convergence 42, 69, 70, 73, 89, 93, 94, 103, 104 Cooper 4, 77, 112 CORRES 58 Densité 14 Dodge 1,37,42, 107, 112 Dual 46, 47, 48 Echantillon 26, 37, 69, 89, 92, 93, 98 Enumeration 30, 39, 41, 43, 45, 91, 93 Erreurs-type 88, 89 Euclidienne 8,9,25,26,27,62 Everitt 4, 5, 6, 11, 12,77, 112 Exploration 6, 63, 65, 94, 96 Explosion 91, 102 Fonction-objectif 2, 4, 14, 36, 38, 41, 42, 43, 49, 50, 51, 52, 53, 65, 88, 91, 95, 96, 104 Forward 45 Fuzzy 15 Garfinkel 39,91, 112 Gower 11 Hartigan 5, 31, 32, 33, 78, 80, 83, 84, 87, 89, 102, 112 Heuristique 28, 29, 34, 89 Homogénéité 36, 49 Hypothèses 6, 63, 65 IMSL 59 Infini 10 Jensen 94,96,112 Lance 14, 16,30,33 Iinnée 3 Mahanalobis 10 Manhattan 9, 16, 27, 53, 108, 109, 110, 111 Maximum 18, 25, 30, 33, 36, 44, 50. 52, 70, 93, 96, 97 Müligan 4,77, 112 Minimum 16,30,31,32,33,34,36.48, 70, 88, 93, 96 Minkovski 9 Modèle 5, 6, 46, 47, 48, 55, 57, 63, 65, 70, 72, 75, 76, 102, 105 Muller 69 Multiplicateur 42 Normalisation 12 Optimal 2, 4 Optimisation 13, 14, 15, 33, 36, 45, 52, 64,65,99, 101, 112 Pondérée 8 Prédiction 6,63,65 Primal 46 Propagation 33, 43 PSTAT 60 Qualitatives 11, 64 Quantitatives 11,12,112 Rao 37,38,92,93,97,102,109,112 Récurrence 14, 33, 89, 103 Réduction 2, 6, 41, 63, 65, 92, 93, 94, 97, 103, 104, 105 Segment 8 SPSS/PC 59, 60 Standardisation 8, 12,60, 70, 109, UO, 111 SWAP 27, 28, 32, 35, 92 Tied 33 Tryon 3, 5, 112 Typologie 6, 12, 63, 65 Variance 9, 12, 35, 69, 112 Williams 14, 30, 33 113