Carte à une dimension du monde?

59

C'est une question étrange mais j'espère que vous pourrez poser cette question ici.

Quelqu'un a-t-il entendu parler d'une projection «unidimensionnelle» de la carte du monde, qui consiste à cartographier tous les points du globe sur une seule ligne?

Je pensais faire une chose pareille: essayer de garder les villes «proches» du globe «proches» du danger.

Avant de faire cela, je me demandais quel était l'état de la technique dans ce domaine?

utunga
la source
Bonne idée, mais je voudrais dire que cette ligne est une caractéristique «bidimensionnelle».
Vent Lam
16
Les lignes sont unidimensionnelles car il suffit d'une seule coordonnée pour localiser un point le long de celle-ci. Les points sont à 0 dimension et les polygones à 2 dimensions.
blah238
5
la projection Apple Peel: t1.thpservices.com/fotos/thum4/013/881/sfd-362035.jpg , bien que je n’aie rencontré aucun algorithme prêt à l’utiliser ... ;-)
matt wilkie
2
@ Matt C'est un mignon. De façon approximative, cette projection cartographie les points proches de (lat, lon) = (f, l) à (Int ((90-f) / e), l) où e est le nombre de "spirales" dans la peau. Le problème est que, à mesure que e s'agrandit, les points de discontinuité se densifient, ce qui implique qu'il a exactement le contraire du comportement souhaité: presque toutes les paires de points ceux qui sont proches sur la terre sont cartographiés loin les uns des autres.
whuber

Réponses:

49

Une technique générale permettant de mapper une collection de points (pour lesquels des distances sont données) dans un espace euclidien (tel qu'un espace de trois, un plan ou même une ligne) avec une distorsion minimale des distances est appelée mise à l'échelle multidimensionnelle (MDS). Il y a plusieurs algorithmes. Les solutions sont disponibles gratuitement dans R et sont souvent fournies avec des progiciels de statistiques commerciales.

Les 20 plus grandes villes des États-Unis sont mappées ici avec les paramètres MDS par défaut de Stata 11. Les graduations indiquent des intervalles de 100 km.

US unidimensionnel

whuber
la source
génial - oui, c’était exactement ce que je comptais faire - même si j’espérais utiliser l’algorithme MDS appelé "Stochastic Neighbor Embedding", mais oui, dans l’ensemble. Je vois que vous l'avez déjà fait, cependant. La chose principale que je pense, c'est que ça a l'air plutôt logique / bon pour moi! Je veux dire intéressant, c'est sa propre façon. Merci!
Utunga
La mise à l'échelle multidimensionnelle est un outil 2D!
huckfinn
@huckfinn Cela peut être fait dans n'importe quel nombre de dimensions; 2 est simplement une application commune. Voir, entre autres , Buja et al. qui ne fournissent aucune limite à la dimension k et dont le tout premier exemple (figure 1, à gauche) fonctionne clairement dans une dimension. Ou regardez simplement ma solution 1D MDS!
whuber
Oui, c’est vrai, mais au-dessous de l’OMI 2D, cela n’a aucun sens, les MDS seront dégradés en mesures de distance normales et en re-projection vers le faisceau numérique. L'ordination se transforme en tri, je ne suis pas sûr?
Huckfinn
Êtes-vous vraiment en train de dire que la carte que je présente dans cette réponse "n'a pas de sens"? Cela nécessitera des explications considérables de votre part, car tout le monde peut constater que (1) cela donne des informations géographiques utiles et (2) que cela ne se réduit pas à "une mesure de distance normale".
whuber
17

Merci beaucoup à @whuber pour la réponse initiale. pensais que je devrais télécharger les résultats de moi faisant à peu près la même chose ...

La forme particulière de MDS que j’ai utilisée est ce qu’on appelle t-SNE (alias «t-Distributed Stochastic Neihbor Embedding» ) pour obtenir les images suivantes.

Voici une photo de toutes les villes dans l’ordre - sur l’axe de gauche, vous trouverez l’emplacement réel à 1 jour de cette ville et les villes rangées dans l’ordre, de haut en bas, de gauche à droite sur cet axe. Color = country villes dans l'ordre

Voici une autre photo où j’ai pris la ligne de villes mais l’ai tracée sur la carte du monde .. Je suppose que ce problème se résume en quelque chose d'assez proche du problème des vendeurs itinérants - mais à la différence qu'il ne s'agit pas seulement d'une commande de villes une cartographie des villes sur une ligne 1-d ...

chemin à travers la carte du monde

Si quelqu'un souhaite connaître l'intégralité des données de sortie ou la méthodologie utilisée ici, veuillez m'envoyer un message.

-

MODIFIER:

En réponse au commentaire de @ whuber ..

Oui, vous avez raison lorsque vous mettez l’accent sur la distance locale (c’est-à-dire que les distances locales des voisins immédiats doivent être aussi proches que possible des distances réelles sur la carte du monde), le problème de la MDS se réduit au problème du vendeur voyageur. Toutefois, si vous mettez l'accent sur l'optimisation (ou l'adaptation) des distances sur une plage plus large / plus modérée, vous pouvez obtenir des résultats différents. Par exemple, voici ce que l'algorithme t-sne donne lorsque vous utilisez une valeur plus élevée pour 'perplexity':entrez la description de l'image ici

utunga
la source
Merci d'avoir partagé. Cela ressemble plus à un voyageur de commerce: ce n'est pas MDS. Une solution MDS aurait beaucoup plus de distorsion mais une relation plus régulière et prévisible entre le monde et la carte. En tant que tel, votre réponse constitue une solution supplémentaire au problème initial.
whuber
mis à jour ma réponse pour donner une autre variante, soyez intéressé par votre point de vue.
Utunga
La seconde est une solution curieuse et intéressante, en effet. Il semble que votre algorithme "t-sne" tente de visiter chaque point exactement . C’est une sorte d’analogie, dans le cas 2D, de créer une projection locale extrêmement précise autour de chaque point et de permettre ensuite à la projection de s’interrompre entre les points, déformant gravement leurs distances et leurs orientations tout en maintenant une fidélité locale presque parfaite. Je suppose que cela pourrait avoir une utilisation spécialisée, mais dans la pratique, on permet généralement une petite erreur de projection car cela laisse assez de marge pour améliorer considérablement la solution globale.
whuber
12

Ce que vous pouvez faire est de couvrir votre espace 2D avec une courbe de remplissage d'espace 1D, telle qu'une courbe de Peano ou une courbe de Hilbert. Ensuite, vous mappez vos points sur le point le plus proche de la courbe. Déballer la courbe et vous devriez dans une certaine mesure obtenir une ligne avec les villes les plus proches dans l'espace le plus proche de la ligne.

Ce n'est pas parfait (je pense que rien ne peut l'être), mais je l'ai déjà utilisé comme base pour un algorithme de représentant de commerce itinérant. la meilleure solution.

Spacedman
la source
4
Cela fonctionne, mais soyez prudent: les villes les plus proches la ligne sera proche dans l'espace, mais les villes proches dans l'espace ne seront généralement pas proches les unes des autres sur la ligne (les courbes carte-> ℝ² en continu, par ne avoir un inverse continu).
gauche vers
2
cette réponse bénéficierait d'un exemple graphique de ce à quoi ressemble une courbe de Peano / Hilbert (et / ou des liens vers les définitions)
matt wilkie
1
ou vous pourriez aller sur wikipedia vous-même ... tout y est, je ne vois pas vraiment l'intérêt de répéter ici trop de wikipedia ...
Spacedman
1
Eh bien, je pense que vous pouvez le répéter un peu! Que diriez-vous d'un lien ou deux et d'une image?
Blah238
À titre d’illustration, on peut consulter la carte Internet XKCD de Randall Munroe , qui utilise précisément cette technique (bien qu’en sens inverse, c’est-à-dire mappant une ligne sur un avion)
waldyrious
9

Les questions étranges sont souvent les plus intéressantes!

Si vous recherchez un état de l'art dans la manière dont les dimensions sont utilisées en cartographie, vous pouvez commencer par la sémiologie graphique de Bertin . Selon Bertin, un morceau de papier (ou une surface ipad) a 3 dimensions: les deux dimensions planes, plus la valeur / texture. La sémiologie graphique fournit des règles permettant de mapper les dimensions d'informations sur ces dimensions de représentation. Lorsque les deux dimensions planaires sont les dimensions spatiales, le graphique est une carte et la troisième dimension est utilisée pour les informations à représenter.

Si vous souhaitez créer une carte à une dimension, cela signifie que vous choisissez de ne pas utiliser l'une des dimensions du papier pour représenter les informations souhaitées (la proximité entre les villes). Est-il vraiment nécessaire d'imposer une telle contrainte et de ne pas faire une carte normale?

Si cela est vraiment nécessaire, comme indiqué dans d'autres réponses, cela ne peut être fait! La relation de proximité entre les villes ne peut être représentée dans une seule dimension. Pour cela, vous pourriez:

  • Utilisez une "approche centrée sur l'utilisateur": si l'audience de la carte est située quelque part ou s'il existe un endroit spécifique sur lequel se concentrer, cet endroit peut être pris pour origine et toutes les autres villes peuvent être triées en fonction de leur distance par rapport à cette origine.
  • Triez les villes non seulement en fonction de leur distance relative, mais en fonction d'autres critères de similarité (population, continent, nombre de voitures par habitant, etc.). Ensuite, certains traitements statistiques tels que l’ analyse en composantes principales pourraient donner une seule ligne de dimension sur laquelle les villes pourraient être classées.
Julien
la source
Jusqu'à présent, toutes les réponses sont très intéressantes et éclairantes. La première balle dans celle-ci, choisir un point d'origine et tous les autres sont "distance de l'origine", semble être la plus immédiatement possible.
Matt Wilkie
La projection en deux dimensions "ne peut pas être faite", soit, comme on le sait! BTW, il existe de nombreuses applications pour les projections 1D, telles que les cartes en bandes pour la planification des trajets.
whuber
7
trying to keep cities that are 'close' on the globe 'close' on the line

Imaginez trois villes situées à la même distance l'une de l'autre, par exemple aux sommets d'un triangle équilatéral. Comment représenteriez-vous cela sur une ligne? Certaines informations seront perdues.

Soit vous ignorez complètement une dimension, par exemple en projetant toutes les villes sur un parallèle ou sur un méridien (ce dernier serait intéressant car nous ne sommes pas habitués à comparer la position relative nord / sud des villes entre différents pays), ou vous en sélectionnez un spécifique. mesure dimensionnelle, p.ex. "distance de New York".

La courbe Peano suggérée par Spacedman est très intéressante et constituerait une carte originale, mais les villes proches pourraient aboutir très loin sur cette courbe.

UncleZeiv
la source
5
... gardez vos villes proches et vos globes plus proches ...
Thomas
1
+1 Bonnes remarques. Cependant, ce n'est pas une proposition ni-ni: vous n'avez pas à projeter sur une ligne ou à la réduire à la distance d'un point de base. Des solutions non linéaires sont disponibles, tout comme elles sont utilisées pour les projections 2D (habituelles). L'objectif est de minimiser une certaine mesure des différences entre les distances projetées et les distances réelles. À cet égard, la courbe de Peano sera particulièrement pauvre, mais des variantes de celle-ci (adaptées pour passer par tous les points souhaités aux premiers stades de sa construction) pourraient fonctionner - en quelque sorte.
whuber
3

Je ne l'ai jamais utilisé, mais je pense qu'un GeoHash pourrait fonctionner pour cela.

Les Geohashes offrent des propriétés telles que la précision arbitraire et la possibilité de supprimer progressivement les caractères de la fin du code afin de réduire sa taille (et de perdre progressivement la précision).

Conséquence de la dégradation progressive de la précision, les lieux proches présentent souvent (mais pas toujours) des préfixes similaires. Inversement, plus un préfixe partagé est long, plus les deux emplacements sont proches.

Kirk Kuykendall
la source
Ces hachages ont tendance à fonctionner en codant en mots des subdivisions raffinées de la surface de la sphère, et sont donc intrinsèquement bidimensionnels. On ne sait pas comment on pourrait en extraire une coordonnée unidimensionnelle (de manière significative).
whuber
@whuber Donc, si j'avais une liste de villes et leur générais des hachages en passant leur lat / long à geohash.org, puis en triant les villes en fonction du hachage, l'ordre des villes ne représenterait-il pas une cartographie unidimensionnelle ( quelle que soit sa précision)?
Kirk Kuykendall
1
Cela dépend entièrement du hash. Une simple commande n'est pas unidimensionnelle, c'est juste une commande. De plus, vous avez besoin d'une coordonnée numérique significative. Si cela sort également du hash, alors vous avez une projection 1D, mais elle a probablement des propriétés terribles. Le but des projections est d’ignorer les distorsions qui n’importent pas pour la visualisation ou l’analyse et de minimiser celles qui le sont. Il est hautement improbable qu'un hash soit utile comme projection dans la plupart des cas.
whuber