Réduction de dimension : analyse factorielle d'un tableau de distances

Introduction

Dans ce TP, nous nous intéressons au problème consistant à obtenir une représentation graphique (si possible en 2 dimensions) d'un ensemble d'objets définis par la distance entre chaque paire d'objets.
Pour N objets, on dispose donc d'une matrice réelle D de taille NxN, D_i,j étant la distance entre l'objet i et l'objet j.
La méthode utilisée appartient à la famille des méthodes factorielles, et ressemble à l'ACP. C'est une méthode linéaire qui, comme l'ACP, détermine un plan, ou un esapce euclidien de petite dimension, dans lequel la projection des objets donne une image fidèle de leur répartition dans l'espace des données.
On s'en tient pour l'instant à supposer que la distance utilisée est la distance euclidienne.
La méthode a été justifiée et décrite en cours, il suffit de la mettre en &oeilig;uvre.
À l'issue de ce TP, vous m'envoyez par email un compte-rendu (format pdf) indiquant la réponse aux questions qui sont posées. Vous m'envoyez également un fichier python réalisant toutes les manipulations de ce TP : je dois pouvoir exécuter ce fichier en tapant python3 nom-de-votre-fichier.py et reproduire vos résultats. Cette exécution ne doit pas provoquer d'erreur de python. Remarque : un notebook ne convient pas.

Rappel sur l'analyse factorielle d'un tableau de distances

On dispose d'une matrice D de distances. L'AFTD se compose des étapes suivantes :

1. on centre doublement la matrice D, ce qui donne la matrice R. On a : R_i,j = -1/2 (D_i,j² + m - l_i - l_j) où :
   • m est la moyenne de tous les éléments de D²,
   • l_i est la moyenne des éléments de la ligne i de D².
2. On effectue la décomposition spectrale de R.
3. On examine les valeurs propres : le nombre de valeurs propres non nulles indique le nombre de dimensions de l'espace euclidien qui représente fidélement la répartition des objets. Idéalement, il y en a une ou deux. La détermination se fait comme dans l'ACP.
4. On détermine les coordonnées des projections des objets en utilisant les vecteurs propres associés aux valeurs propres non nulles.
   La coordonnée j de l'objet i est λ_j^1/2 V_i,j

Mise en application

Application 1

Pour la première application, on considère un ensemble de villes de France métropolitaine. On dispose de la matrice de distance calculée à partir de leurs coordonnées géographiques. Cette matrice est disponible à cette url : https://philippe-preux.codeberg.page/ensg/miashs/datasets/distances-entre-10-villes-de-France-métropolitaine.csv.
À faire :

• réaliser une AFTD. Combien de dimensions sont pertinentes ? Faites une représentation graphique dans le plan principal.
• Les villes sont (dans l'ordre correspondant à la matrice de distance) : Amiens, Angers, Bordeaux, Brest, Dijon, Grenoble, Lille, Paris, Roubaix, Toulouse. Réaliser une représentation graphique avec le nom des villes : le résultat obtenu vous satisfait-il ? Si non, pourquoi ? Pouvez-vous y remédier ?

Application 2

On considère maintenant la matrice de distances disponible à cette url : https://philippe-preux.codeberg.page/ensg/miashs/datasets/eurodist.txt. Dans ce fichier, lignes et colonnes portent le nom de la ville concernée par cette ligne et cette colonne.
Cette matrice de distances donne la distance kilométrique entre 21 villes d'Europe : ces distances sont mesurées en suivant les routes les plus courtes allant d'une ville à une autre ; elle est symétrique (même si en réalité, la distance par la route allant d'une ville à une ville B n'est pas forcément symétrique (et donc ce n'est pas une distance au sens mathématique du terme).
À faire :

• réaliser une AFTD. Combien de dimensions sont pertinentes ? Faites une représentation graphique dans le plan principal en indiquant le nom des villes.
• Le résultat obtenu vous satisfait-il ? Si non, pourquoi ? Pouvez-vous y remédier ? Pouvez-vous déterminer les villes dont la position n'est pas correctement projetée ?