Méthode de la Classification Ascendante Approximative (CAA)

Télécharger le fichier pdf d’un mémoire de fin d’études

Visualisation de Classifications

Nous allons tout d’abord voir les techniques existantes de visualisation de résumés qui permettent de visualiser les principales caractéristiques d’une classe. Puis nous verrons, les différents types de visualisation de classifications sous forme de tableau. Nous finirons par les algorithmes d’optimisation de l’ordre des variables et des classes qui permettent une lecture aisée des visualisations (aussi bien pour les résumés ou que pour les tableaux).

Visualisation de classes sous forme de résumés

La visualisation des résumés (ou des classes) s’apparente à la visualisation d’informations synthétiques concernant un groupe d’individus. Il existe de nombreux outils graphiques en statistique permettant de faire cela. Les plus simples permettent de visualiser les informations pour une seule variable d’un ensemble d’individus. Nous verrons ensuite les outils plus évolués permettant de visualiser simultanément les informations pour plusieurs variables.

Visualisation des caractéristiques d’une seule variable.

Ces graphiques sont très communs en statistiques. Nous allons étudier les points forts et les points faibles des graphiques les plus intéressants :

L’histogramme des fréquences

C’est l’un des graphiques les plus utilisés pour décrire une « variable » pour un ensemble d’individus. C’est un graphique constitué par des rectangles de même base placés les uns à côté des autres, et dont la hauteur est proportionnelle à la fréquence d’apparition de différentes classes de valeurs. Dans l’exemple suivant, on observe la fréquence (nombre de zones IRIS de Paris et sa petite couronne) des classes de taux d’ouvriers pour différents intervalles de valeurs.

Boite à moustaches (box-and-whisker plot)

La « boite à moustaches » a été définie par J. Tukey [Tuke77] et elle permet de donner sous forme d’un graphique horizontal ou vertical les informations les plus importantes de la distribution :

La valeur médiane (50% des valeurs sont plus faibles et 50 % sont plus fortes)

La valeur minimale et la valeur maximale.

Le premier quartile (25% des valeurs sont plus faibles et 75 % sont plus fortes)

Le troisième quartile (75% des valeurs sont plus faibles et 25 % sont plus fortes)

En outre, les moustaches séparent les valeurs ordinaires des valeurs exceptionnelles. La moustache « gauche » est située à plus de 1,5 fois l’écart interquartile au dessous du 1er quartile et la moustache « droite » au dessus du 3ème quartile. En effet, si la distribution de la variable suit une distribution normale (gaussienne), plus de 99% des individus sont situés entre les moustaches.

Dans l’exemple suivant, on observe la distribution du taux d’ouvriers dans les IRIS (zones) de Paris et sa petite couronne.

Visualisation en coordonnées parallèles

Le graphique en coordonnées parallèles [ID90, Siir00] est constitué d’axes verticaux représentant chacun une variable. Ces axes sont placés en parallèle et les coordonnées de chaque individu sont représentées sur ces axes. Une ligne reliant les coordonnées de proche en proche constitue la représentation de l’individu dans le graphique. L’exemple ci-dessous montre le profil des zones de Paris et de sa Petite Couronne en fonction du revenu moyen et des taux de cadres, d’intermédiaires, d’employés et d’ouvriers. L’individu moyen est représenté par la ligne bleue. Un exemple d’individu réel est surligné par une ligne noire.

L’inconvénient de ce type de graphique est son aspect « embrouillé » lorsque le nombre d’individus devient important comme c’est le cas dans l’exemple précédent.

On peut signaler une amélioration [YMR03] permettant de visualiser les différentes classes d’une hiérarchie dans un seul graphique.

Diagramme en étoile

Il s’agit d’une variante de la visualisation en coordonnées parallèles. Les axes sont simplement organisés suivant les rayons d’un cercle. Il n’est intéressant que pour des variables périodiques ayant donc un « ordre circulaire » telles que les jours de la semaine ou les mois.

L’exemple suivant montre l’évolution du nombre de mariage suivant les mois (ils constituent les variables) pour quatre années (elles constituent les individus).

Tri des individus selon la moyenne de leur valeurs

Cette méthode n’a de sens que pour trier les individus, et elle ne s’applique donc pas au tri des variables [ESSB98].
On calcule donc pour chaque individu la moyenne de ses valeurs. Ainsi, il est nécessaire que les variables soient toutes de même nature ou bien standardisées (centrées-réduites par exemple). Ensuite, les individus sont réordonnés selon leur moyenne.
Cette méthode très simple n’est efficace que lorsque toutes les variables sont corrélées positivement. Dans notre exemple, on voit que les Régions sont bien triées pour certaines variables (Artisan, Ouvrier, …) mais pas pour d’autres (Intermédiaire, SansActivite, Retraite,…). Cette méthode n’est donc pas idéale.

Réorganisation via l’Analyse en Composantes Principales (ACP)

L’analyse en composante principale (ACP) permet de créer des variables synthétiques qui s’expriment en fonction des variables naturelles. De plus, ces variables synthétiques peuvent être ordonnées en fonction de leur facteur d’explication. Ainsi, pour résumer les variables naturelles par une unique variable synthétique, il suffit de prendre la variable synthétique ayant le plus grand facteur d’explication, aussi appelé axe principal. Brièvement, le principe de l’ACP est le suivant : les variables synthétiques sont calculées à partir de la matrice des corrélations des variables. D’un point de vue technique, cela consiste à trouver les valeurs propres de la matrice et les vecteurs associés. Le vecteur ayant la plus grande valeur propre est la variable synthétique ayant la plus grande explication.
L’exemple suivant donne les coefficients de la variable synthétique ayant la plus grande explication, il s’agit du « axe_1 ».

Recherche de l’ordre optimal dans une classification existante

Une autre façon d’aborder le problème est de le définir de la façon suivante : parmi tous les ordres possibles, l’ordre optimal est celui qui minimise la somme des distances entre les individus consécutifs. Ce problème d’ordonnancement est connu sous le nom de Sequential Ordering Problem (SOP) ou Linear Ordering Problem (LOP). C’est une variation du problème du voyageur de commerce, Traveling Salesman Problem (TSP), qui à la différence que le chemin (l’ordre des individus) n’est pas une boucle (on ne prend pas en compte la distance entre le dernier individu et le premier individu qui ferme la boucle). Soit P une permutation de 1,…,n, l’ordre correspondant des individus est OPoP1 ,…,oP net son coût est CP∑n1 doP i ,oP i1 avec d la distance entre deux individus. L’ordre optimal est OOpt 1 correspondant à COpt min CP. Le coût peut être décrit comme la longueur du Ppermutation « chemin » correspondant à l’ordre

En reprenant l’exemple précédent et en calculant son coût en prenant la distance euclidienne au carré, on s’aperçoit que la hiérarchie de droite est bien meilleure. Pour la hiérarchie ABC, nous avons : CABC  dA,B dB,C 1121 (1)21 021 02  22 221212 8 2.

Sectorisation

Nous étudierons en premier les techniques existantes permettant de réaliser une sectorisation équilibrée. Comme cette problématique est équivalente à la problématique du partitionnement de graphe (sujet largement exploré en théorie des graphes), nous nous focaliserons donc sur les méthodes les plus intéressantes, c’est-à-dire les méthodes récursives et multi-échelles car elles offrent de très bons résultats.
Nous verrons ensuite les méthodes de rééquilibrage qui permettent d’optimiser une sectorisation existante. En effet, il est parfois plus intéressant d’améliorer une sectorisation existante que d’en calculer une nouvelle. Nous verrons en détails les techniques de rééquilibrage qui se décomposent en deux étapes : le calcul de tous les transferts à effectuer entre les secteurs, puis la mise en œuvre des transferts.

Sectorisation équilibrée

La sectorisation équilibrée consiste en la création de secteurs de « taille » égale. La taille est dans ce cas une quantité à partager : surface, population, clients, … De plus, la localisation des secteurs n’est pas définie à l’avance. La sectorisation équilibrée est toutefois un problème largement étudié en théorie des graphes sous le nom de partitionnement de graphe (Graph Partitioning).
Il existe de nombreuses méthodes de partitionnement de graphe pour réaliser une sectorisation équilibrée [SKK03]. Nous ne les présenterons pas ici, car nous allons seulement présenter l’une des méthodes les plus efficaces, ainsi que ses évolutions. Il s’agit de la bipartition récursive. Cette méthode découpe itérativement le territoire en morceaux de plus en plus petits. Par exemple, pour une partition en 5 secteurs d’un territoire de taille 100, l’algorithme procède d’abord à un partage entre un grand secteur A de taille 40 et un autre secteur B de taille 60. Puis le secteur A est découpé à nouveau en deux secteurs A1 et A2 de tailles 20. On procède de même pour le secteur B. Le schéma suivant montre les ce partitionnement récursive.

Rééquilibrage des secteurs

Lorsque nous disposons d’une sectorisation existante, il est parfois plus intéressant d’améliorer cette sectorisation plutôt que d’en calculer une nouvelle. Le rééquilibrage des secteurs vise donc à « améliorer » les quantités de chaque secteur en transférant des objets géographiques entre les secteurs. Ceci dans le but que la quantité de chaque secteur se rapproche de la quantité idéale. Ce problème peut être modélisé de différentes façons [SKK97]. On peut classer les méthodes entre les méthodes de diffusion non dirigées (locales) et celles dirigées (globales). Les méthodes non dirigées réalisent directement les transferts entre secteurs voisins et tente ainsi itérativement d’atteindre l’équilibre. Au contraire, les méthodes dirigées calculent d’abord les transferts à réaliser avant de les mettre en œuvre. Cette dernière méthode est la plus intéressante car elle permet de minimiser les quantités transférées et évite donc de trop modifier la forme des secteurs. C’est ce dernier type de méthode que nous allons étudier.

Calcul des quantités à transférer

Ce problème peut être modélisé de différentes façons : les calculs les plus utilisées sont d’une part, le calcul de la solution minimisant la somme des quantités transférées [OR94] et d’autre part, le calcul de la solution minimisant la somme des carrés des quantités transférées [HB95]. Cette dernière méthode a notre préférence car elle est plus simple à mettre en œuvre. En effet, il s’agit de résoudre un système d’équations linéaires dont la solution unique est facilement trouvée par un solveur d’équations. De plus, les transferts à effectuer sont de plus faible quantité (mais plus nombreux).

Nous définissons dans un premier temps les contraintes liées aux transferts. D’abord, nous établissons pour chaque secteur, les secteurs immédiatement voisins, car pour des raisons de contiguïté, un transfert ne peut être effectué qu’entre secteurs voisins. Nous notons Tij la quantité à transférer entre le secteur Si et le secteur S j . Les contraintes sur les transferts sont les suivantes :

La somme des transferts arrivant vers un secteur Si doit permettre d’atteindre la quantité désirée pour ce secteur : ∑Tji Di S jVoisinage ( Si )

Avec Di la différence entre la quantité actuelle et la quantité souhaitée du Secteur Si Les transferts entre deux secteurs sont opposés : TijTji

Nous allons maintenant voir la méthode la plus intéressante qui permet de minimiser la somme des carrés des quantités transférées, c’est-à-dire qui vérifie que∑Tji2 est minimum. La modélisation est la suivante. Chaque transfert Tij est considéré comme la différence entre deux variables xi et xj dépendant respectivement du secteur Si et du secteur S j , et on pose Tij xi xj . Ainsi, le système de contraintes devient le système linéaire à n inconnues xi et à n équations : ∑ xi x j Di n xi∑ x j Di S jVoisinage ( Si )S jVoisinage ( Si n Ces équations sont liées car la somme des n équations est nulle car∑Dj  0 . Nous i1 supprimons donc la première équation et nous fixons x1 0 afin d’obtenir un système linéaires de n-1 équations indépendantes avec n-1 inconnues. Ce système linéaire admet une solution unique que nous trouvons informatiquement à l’aide d’un solveur d’équations. Nous déduisons alors tous les transferts à partir des valeurs des xi .

L’exemple suivant montre le calcul des transferts entre les secteurs A, B, C et D. Les relations de voisinages sont symbolisées par des liens. De plus, l’excédent (ou le déficit) de chaque secteur est indiqué sous son nom.

Mise en œuvre des transferts

Une fois les quantités à transférer établies, il faut alors mettre ces transferts en œuvre. Nous allons voir les méthodes existantes.

Dans la littérature, les méthodes mettant en œuvre le rééquilibrage sont nombreuses [AK95]. Ces méthodes sont pour la plupart itératives, transférant les objets géographiques un par un entre les secteurs. Ces méthodes peuvent donc fonctionner indifféremment dans le cadre d’une diffusion dirigée ou non dirigées. Dans le cadre, d’une diffusion dirigée, il s’agit de réaliser les transferts calculés tandis que dans le cadre d’une diffusion non dirigée, il s’agit d’atteindre l’équilibre pour les secteurs. Bien évidemment, les résultats sont meilleurs et trouvés plus rapidement dans le cadre de la diffusion dirigée. Les méthodes diffèrent par la façon dont elles choisissent l’objet qui doit migrer entre deux secteurs. Les plus utilisées pour mettre en œuvre la diffusion sont les suivantes :

L’algorithme Fiduccia-Mattheyses [FM82] trie les objets situés à la frontière en fonction de leur « gain ». L’objet ayant le meilleur gain migre. L’intérêt de cette méthode est qu’elle permet au secteur de garder une forme compacte. Cependant, son principal défaut est que si l’objet ayant le meilleur gain ne peut pas migrer (si sa quantité est trop grande) alors, on est obligé d’arrêter l’algorithme. En effet, si l’on décide de migrer un autre objet, on risque alors de créer un trou dans le secteur d’arrivé, ce trou étant formé justement par l’objet que l’on avait pas pu faire migrer.

L’algorithme de Krishnamurthy [Kris84] reprend le précédent algorithme en essayant de déterminer plus efficacement les objets à migrer. Pour cela, il calcule un gain sur plusieurs coups à l’avance, c’est-à-dire que le gain est calculé pour une série d’objets à faire migrer. La taille de la série permet de faire varier « l’intelligence » de l’algorithme.

Pour une longueur de 1, il est identique à l’algorithme de Fiduccia-Mattheyses. Cette stratégie permet de limiter l’arrêt prématuré.

On peut noter qu’il est possible d’utiliser la stratégie multi-niveaux en complément des algorithmes précédents afin de rééquilibrer rapidement des sectorisations comprenant un très grand nombre d’objets. C’est ce que réalise notamment JOSTLE [WC00].

Nous verrons ultérieurement la mise en œuvre de ces algorithmes en répondant aux questions suivantes : Quel ordre pour les transferts ? Faut-il réaliser les transferts en totalité ou pas à pas ? Comment rééquilibrer les secteurs ayant un centre ?

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela chatpfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Introduction
1. État de l’art
Introduction
1 Classification de Données
1.1 Méthodes de classification sur les grands volumes de données
1.2 Similarités, dissimilarités et distances
2 Visualisation de Classifications
2.1 Visualisation de classes sous forme de résumés
2.2 Visualisation de classes sous forme de tableau
2.3 Optimisation de l’ordre des variables et des individus
3 Lissage spatial
3.1 Méthodes de lissage
3.2 Fonctions d’interaction spatiale
3.3 Fonctions de lissage spatial
4 Sectorisation
4.1 Sectorisation équilibrée
4.2 Rééquilibrage des secteurs
Conclusions
2. Contributions
Introduction
1 Classification de Données pour de grands volumes de données mixtes
1.1 Dissimilarité utilisée
1.2 Méthode de la Classification Ascendante Approximative (CAA)
1.3 Conclusion
2 Visualisation de Classifications
2.1 Hiérarchie évoluée des profils de classes
2.2 Tableau évolué des profils de classes
2.3 Optimisation de l’ordre des variables et des classes
2.4 Conclusion
3 Détermination et Hiérarchisation de pôles
3.1 Détermination de pôles
3.2 Hiérarchisation des pôles
3.3 Conclusion
4 Sectorisation
4.1 Méthodes communes aux deux types de sectorisation
4.2 Sectorisation équilibrée
4.3 Sectorisation à partir de centres
4.4 Rééquilibrage des secteurs
4.5 Conclusion
Conclusions
3. Expérimentations et Applications
Introduction
1 Classification de Données & Visualisation de Classifications
1.1 Expérimentations et Comparaison avec les K- moyennes
1.2 Autre application : la Classification de Variables
1.3 Analyse des données socioprofessionnelles de Paris et de sa Petite Couronne
1.4 Autre application : la Classification Hiérarchique Spatiale
1.5 Conclusion
2 Lissage Spatial, Détermination et Hiérarchisation de Pôles
2.1 Analyse spatiale de la population pour la France entière
2.2 Utilisation du Lissage Spatial en prétraitement de la Classification de Données
2.3 Conclusion
3 Sectorisation
3.1 Sectorisation équilibrée de la population française en 22 secteurs
3.2 Sectorisation de la population française à partir de 9 centres
3.3 Rééquilibrage de la sectorisation précédente
3.4 Conclusion
Conclusions
Conclusion générale et Perspectives
Annexe
Introduction
1 Contributions à la méthode de l’Arbre de Décision
1.1 Rappels
1.2 Recherche du meilleur partitionnement binaire pour une variable qualitative
1.3 Facteur de correction avantageant la création de partitions pures
1.4 Conclusion
2 Contributions à l’amélioration des coefficients d’Autocorrélation Spatiale
2.1 Etat de l’art
2.2 Amélioration des coefficients
2.3 Conclusion
3 Contributions à l’amélioration de la Modélisation des Flux
3.1 Etat de l’art
3.2 Amélioration
3.3 Application pour l’analyse des migrations des entreprises à l’intérieur du département de la Loire-Atlantique
3.4 Conclusion
Bibliographie