Jednowymiarowa mapa świata?

59

Trochę dziwne pytanie, ale mam nadzieję, że zadaję pytanie tutaj.

Czy ktoś słyszał o „1-wymiarowej” projekcji mapy świata - która mapuje wszystkie punkty na kuli ziemskiej w jedną linię?

Myślałem o zrobieniu czegoś takiego - staraniu się, aby miasta, które są „blisko” na kuli ziemskiej, były „blisko” na linii.

Zanim to zrobiłem, zastanawiałem się, jaki może być stan techniki w tej dziedzinie?

utunga
źródło
Dobry pomysł, ale chciałbym powiedzieć, że linia jest funkcją „dwuwymiarową”.
Vent Lam
16
Linie są jednowymiarowe, ponieważ do zlokalizowania dowolnego punktu wzdłuż tej linii potrzebna jest tylko jedna współrzędna. Punkty są 0-wymiarowe, a wielokąty są 2-wymiarowe.
blah238,
5
projekcja Apple Peel: t1.thpservices.com/fotos/thum4/013/881/sfd-362035.jpg , chociaż nie spotkałem się z żadnymi gotowymi do użycia algorytmami ... ;-)
Matt Wilkie
2
@Matt To urocze. Dla dobrego przybliżenia, ta projekcja odwzorowuje punkty w pobliżu (lat, lon) = (f, l) do (Int ((90-f) / e), l), gdzie e jest liczbą „spiral” w skórce. (Trochę mi to kręci, ale to jest sedno.) Problem polega na tym, że gdy e staje się duże, punkty nieciągłości stają się gęste, co sugeruje, że ma dokładnie odwrotność pożądanego zachowania: prawie wszystkie pary punktów które są blisko Ziemi, zostaną zmapowane daleko od siebie.
whuber

Odpowiedzi:

49

Ogólna technika mapowania zbioru punktów (dla których podano odległości) na przestrzeń euklidesową (taką jak trzyprzestrzeń, płaszczyzna, a nawet linia) przy minimalnym zniekształceniu odległości nazywa się skalowaniem wielowymiarowym (MDS). Istnieje kilka algorytmów. Rozwiązania są swobodnie dostępne w języku R i często dostarczane są z pakietami statystyk handlowych.

Największe 20 miast w USA jest zmapowanych tutaj z domyślnymi ustawieniami MDS Stata 11. Kleszcze oznaczają interwały 100 km.

Jednowymiarowy USA

Whuber
źródło
genialne - tak właśnie zamierzałem zrobić - chociaż miałem nadzieję na użycie algorytmu MDS o nazwie „Stochastic Neighbor Embedding”, ale tak samo w istocie. Widzę jednak, że już to zrobiłeś. Myślę, że najważniejsze jest to, że dla mnie wygląda to całkiem logicznie / dobrze! Mam na myśli interesujące, to po swojemu. Dzięki!
utunga
Skalowanie wielowymiarowe to rzeczy 2D!
huckfinn
@huckfinn Można to zrobić w dowolnej liczbie wymiarów; 2 jest jedynie powszechnym zastosowaniem. Patrz, między innymi , Buja i in. którzy nie podają żadnych ograniczeń wymiaru k i których pierwszy przykład (ryc. 1 po lewej) wyraźnie działa w jednym wymiarze. Albo po prostu spójrz na moje rozwiązanie 1D MDS!
whuber
Tak, to prawda, ale poniżej 2D IMO nie ma sensu, MDS zostanie zdegradowany do normalnego pomiaru odległości i ponownej projekcji na wiązkę liczb. Wyświęcenie zmienia się w sortowanie Nie jestem pewien?
huckfinn
Czy naprawdę twierdzisz, że mapa, którą przedstawiam w tej odpowiedzi „nie ma sensu”? Że będzie potrzebował wyjaśnień na znaczną część, jak każdy może wyraźnie zobaczyć, że (1) nie ma przekazać użyteczne informacje geograficzne i (2) to jednak nie zredukować do „normalnego pomiar odległości.”
whuber
17

Bardzo dziękuję @whuber za wstępną odpowiedź. pomyślałem, że powinienem wgrać wyniki, które robię tak samo ...

Do tego, co jest warte szczególnej formy MDS, której użyłem, jest coś o nazwie t-SNE (aka „t-Distributed Stochastic Neihbor Embedding” ), aby uzyskać następujące obrazy.

Oto zdjęcie wszystkich miast w kolejności - na lewej osi znajduje się rzeczywista 1-d lokalizacja dla tego miasta, a miasta ułożone w kolejności od góry do dołu, od lewej do prawej w poprzek tej osi .. color = country miasta w porządku

Oto kolejne zdjęcie, na którym wziąłem linię miast, ale narysowałem ją na mapie świata. Wydaje mi się, że ten problem sprowadza się do problemu bardzo zbliżonego do problemu podróżującego sprzedawcy - z tą różnicą, że nie jest to tylko zamawianie miast, ale mapowanie miast do linii 1-d ...

ścieżka przez mapę świata

Jeśli ktoś chce użyć pełnych danych wyjściowych lub zastosowanej metodologii, proszę o wiadomość.

-

EDYTOWAĆ:

W odpowiedzi na przykazanie @ whuber.

Tak, masz rację, kiedy podkreślasz lokalną odległość (to znaczy, że lokalne odległości bezpośrednich sąsiadów powinny być jak najbardziej zbliżone do rzeczywistych odległości na mapie świata), problem MDS ogranicza się do problemu podróżującego sprzedawcy. Jeśli jednak zaakcentujesz optymalizację (lub dopasowanie) odległości w szerszym / bardziej umiarkowanym zakresie, możesz uzyskać różne wyniki. Na przykład oto, co daje algorytm t-sne, gdy używasz wyższej wartości dla „zakłopotania”:wprowadź opis zdjęcia tutaj

utunga
źródło
Dzięki za udostępnienie. To naprawdę bardziej przypomina podróżującego sprzedawcę: to nie jest MDS. Rozwiązanie MDS miałoby znacznie więcej zniekształceń, ale znacznie więcej regularnych, przewidywalnych relacji między światem a mapą. W związku z tym twoja odpowiedź stanowi kolejne rozwiązanie pierwotnego problemu.
whuber
zaktualizowałem moją odpowiedź, by podać kolejną odmianę, zainteresuj się swoimi opiniami.
utunga
Drugie jest rzeczywiście ciekawym i interesującym rozwiązaniem. Wygląda na to, że Twój algorytm „t-sne” próbuje dokładnie odwiedzić każdy punkt . Jest to w pewnym sensie analogiczne, w przypadku 2D, do stworzenia bardzo dokładnej lokalnej projekcji wokół każdego punktu, a następnie umożliwienia projekcji przełamania się między punktami, poważnie zniekształcając ich odległości i orientacje, zachowując prawie idealną lokalną wierność. Przypuszczam, że może to mieć jakieś wyspecjalizowane zastosowanie, ale w praktyce zwykle dopuszcza się niewielki błąd projekcji, ponieważ pozwala na wystarczający luz, aby znacznie poprawić globalne rozwiązanie.
whuber
12

To, co możesz zrobić, to pokryć swoją przestrzeń 2-d krzywą wypełniającą przestrzeń 1-d, taką jak krzywa Peano lub krzywa Hilberta. Następnie odwzoruj swoje punkty na najbliższy punkt na krzywej. Rozpakuj krzywą i powinieneś w pewnym stopniu uzyskać linię z najbliższymi miastami w przestrzeni najbliższej linii.

Nie jest idealny (nie wydaje mi się, żeby cokolwiek mogło być), ale widziałem, że jest on wykorzystywany jako podstawa algorytmu podróżujących sprzedawców sprzedażowych - pomysł polega na tym, że jeśli wybierasz się w podróż sprzedawcy wzdłuż linii, będzie to dobre przybliżenie do najlepszym rozwiązaniem.

Spacedman
źródło
4
Działa to, ale należy zachować ostrożność: najbliższe miasta, jedna linia będzie w pobliżu w kosmosie, ale w pobliżu miast w kosmosie na ogół nie będą blisko siebie na linii (mapa krzywych ℝ-> ℝ² w sposób ciągły, przez nie mieć ciągłe odwrotne).
leftaroundabout
2
ta odpowiedź skorzystałaby na graficznym przykładzie tego, jak wygląda Peano / Hilbert Curve (i / lub linki do definicji)
Matt Wilkie
1
lub możesz sam przejść na wikipedię ... to wszystko tam, naprawdę nie widzę sensu powtarzania tutaj zbyt wiele wikipedii ...
Spacedman,
1
Myślę, że możesz to trochę powtórzyć! A może link lub dwa i obraz?
blah238,
Dla celów ilustracyjnych można spojrzeć na mapę XKCD Randall Munroe w Internecie , która wykorzystuje dokładnie tę technikę (choć w odwrotnej kolejności, tj. Odwzorowuje linię na samolot)
waldyrious
9

Dziwne pytania są często najciekawsze!

Jeśli szukasz najnowocześniejszego sposobu wykorzystania wymiarów w kartografii, możesz zacząć od semiologii graficznej Bertina . Według Bertina kawałek papieru (lub powierzchnia iPada) ma 3 wymiary: dwa płaskie wymiary plus wartość / tekstura. Semiologia grafiki zapewnia reguły mapowania wymiarów informacji na te wymiary reprezentacji. Gdy dwa płaskie wymiary są wymiarami przestrzennymi, grafika jest mapą, a trzeci wymiar jest wykorzystywany do reprezentowania informacji.

Jeśli chcesz zrobić 1-wymiarową mapę, oznacza to, że zdecydujesz się nie używać jednego z wymiarów papieru do reprezentowania potrzebnych informacji (bliskość między miastami). Czy naprawdę trzeba narzucić takie ograniczenie i nie tworzyć normalnej mapy?

Jeśli jest to naprawdę potrzebne, jak powiedziano w innych odpowiedziach, nie można tego zrobić! Relacji bliskości między miastami nie można przedstawić w jednym wymiarze. W tym celu możesz:

  • Użyj „podejścia zorientowanego na użytkownika”: jeśli odbiorca mapy znajduje się gdzieś lub istnieje określone miejsce, na którym można się skupić, to miejsce może być traktowane jako źródło, a wszystkie inne miasta mogą być posortowane według odległości od tego źródła.
  • Sortuj miasta nie tylko według ich względnej odległości, ale według innych kryteriów podobieństwa (liczba ludności, kontynent, liczba samochodów na mieszkańca itp.). Następnie niektóre metody statystyczne, takie jak analiza głównych składników, mogłyby dać jedną linię wymiarową, według której miasta mogłyby zostać uszeregowane wzdłuż.
Julien
źródło
Wszystkie dotychczasowe odpowiedzi są bardzo interesujące i pouczające. Pierwsza kula w tym punkcie, wybierz punkt początkowy, a wszystkie pozostałe znajdują się w „odległości od początku”, wydaje się być najbardziej praktyczna natychmiast.
matt wilkie
Jak wiadomo, projekcji na dwa wymiary „nie da się zrobić”. BTW, istnieje wiele aplikacji do projekcji 1D, takich jak mapy paskowe do planowania podróży.
whuber
7
trying to keep cities that are 'close' on the globe 'close' on the line

Wyobraź sobie trzy miasta w tej samej odległości od siebie, np. W wierzchołkach trójkąta równobocznego. Jak byś to reprezentował na linii? Niektóre informacje zostaną utracone.

Albo całkowicie odrzucisz jeden wymiar, np. Rzutujesz wszystkie miasta na równoleżnik lub na południk (ten drugi byłby interesujący, ponieważ nie jesteśmy przyzwyczajeni do porównywania względnej pozycji miast na północy / południu między różnymi krajami), lub wybierasz konkretny miara wymiarowa, np. „odległość od Nowego Jorku”.

Krzywa Peano sugerowana przez Spacedmana jest bardzo interesująca i stanowiłaby oryginalną mapę, ale pobliskie miasta mogą skończyć się bardzo daleko na tej krzywej.

UncleZeiv
źródło
5
... trzymaj swoje miasta blisko, a globusy bliżej ...
Thomas,
1
+1 dobre uwagi. Nie jest to jednak ani propozycja: nie musisz rzutować na linię ani zmniejszać jej do odległości od punktu bazowego. Dostępne są rozwiązania nieliniowe, tak jak są one używane do (zwykłych) projekcji 2D. Celem jest zminimalizowanie pewnej miary różnic między rzutowanymi odległościami a rzeczywistymi odległościami. Pod tym względem krzywa Peano będzie szczególnie słaba, ale jej warianty (przystosowane do przechodzenia przez wszystkie pożądane punkty na wczesnych etapach jej budowy) mogłyby działać - w pewnym sensie.
whuber
3

Nigdy go nie użyłem, ale myślę, że GeoHash może do tego zadziałać.

Geohashy oferują właściwości takie jak dowolna precyzja i możliwość stopniowego usuwania znaków z końca kodu w celu zmniejszenia jego rozmiaru (i stopniowej utraty precyzji).

W wyniku stopniowej degradacji precyzji miejsca w pobliżu często (ale nie zawsze) mają podobne prefiksy. I odwrotnie, im dłuższy jest wspólny prefiks, tym bliżej są dwa miejsca.

Kirk Kuykendall
źródło
Te skróty działają zwykle poprzez kodowanie wyrafinowanych podziałów powierzchni kuli na słowa, a zatem są z natury dwuwymiarowe. Nie jest jasne, w jaki sposób można wyodrębnić z nich jednowymiarową współrzędną (w jakikolwiek znaczący sposób).
whuber
@whuber Więc gdybym miał listę miast i wygenerował dla nich skróty, przekazując ich lat / long do geohash.org, a następnie posortowałbym miasta na podstawie skrótu, czy uporządkowanie miast nie reprezentowałoby mapowania jednowymiarowego ( niezależnie od tego, jak dokładne jest).
Kirk Kuykendall
1
Zależy to całkowicie od skrótu. Samo zamówienie nie jest jednowymiarowe, to po prostu zamówienie. Ponadto potrzebujesz znaczącej współrzędnej numerycznej. Jeśli to również pochodzi z skrótu, to rzeczywiście masz projekcję 1D, ale prawdopodobnie ma ona straszne właściwości. Chodzi o to, aby zignorować zniekształcenia, które nie mają znaczenia dla wizualizacji lub analizy, i zminimalizować te, które to robią. Jest mało prawdopodobne, aby jakikolwiek skrót był użyteczny jako projekcja do większości celów.
whuber