Одномерная карта мира?

59

Немного странный вопрос, но надеюсь, что здесь можно задать вопрос.

Кто-нибудь слышал о «одномерной» проекции карты мира, которая отображает все точки земного шара в одну линию?

Я думал о том, чтобы сделать такую ​​вещь - попытаться удержать города, «близкие» на планете, «близкие» на линии.

Прежде чем я это сделаю, я подумал, каков уровень техники в этой области?

Утунги
источник
Хорошая идея, но я хотел бы сказать, что линия является «двухмерной» функцией.
Vent Lam
16
Линии являются одномерными, потому что требуется только одна координата, чтобы найти любую точку вдоль нее. Точки являются 0-мерными, а полигоны 2-мерными.
blah238
5
проекция Apple Peel: t1.thpservices.com/fotos/thum4/013/881/sfd-362035.jpg , хотя я не встречал никаких готовых алгоритмов для этого ... ;-)
matt wilkie
2
@Matt Это мило. В хорошем приближении эта проекция отображает точки вблизи (широта, долгота) = (f, l) с (Int ((90-f) / e), l), где e - число «спиралей» в кожуре. (Я немного обманываю, но в этом суть.) Проблема в том , что с ростом e точки разрыва становятся плотными, подразумевая, что это имеет в точности противоположность желаемому поведению: почти все пары точек которые находятся близко к земле, отображаются далеко друг от друга.
whuber

Ответы:

49

Общий метод отображения набора точек (для которых даны расстояния) в евклидово пространство (например, трехмерное пространство, плоскость или даже линию) с минимальным искажением расстояний называется многомерным масштабированием (MDS). Есть несколько алгоритмов. Решения свободно доступны в R и часто поставляются с пакетами коммерческой статистики.

Здесь отображаются 20 крупнейших городов США со стандартными настройками MDS Stata 11. Клещи обозначают интервалы в 100 км.

Одномерные США

Whuber
источник
блестяще - да, это было именно то, что я планировал сделать - хотя я надеялся использовать алгоритм MDS под названием «Стохастическое вложение соседей», но да, по сути, тот же. Я вижу, что вы уже сделали это, однако. Главное, я думаю, это выглядит довольно логично / хорошо для меня! Я имею в виду, интересно, это по-своему. Спасибо!
Утунга
Многомерное масштабирование - это 2D!
huckfinn
@huckfinn Это может быть сделано в любом количестве измерений; 2 является просто распространенным приложением. См., В частности , Buja et al. которые не дают ограничений на размерность k и чей самый первый пример (рисунок 1, слева) явно работает в одном измерении. Или просто посмотрите на мое 1D решение MDS!
whuber
Да, это правда, но ниже 2D IMO это не имеет смысла, MDS будет ухудшен до нормального измерения расстояния и перепроецируется на числовой луч. Обряд превращается в сортировку Я не уверен?
huckfinn
Вы действительно утверждаете, что карта, которую я представляю в этом ответе, "не имеет смысла"? Это потребует значительного объяснения с вашей стороны, поскольку любой может ясно видеть, что (1) он действительно передает полезную географическую информацию и (2) он не сводится к «обычному измерению расстояния».
whuber
17

Большое спасибо @whuber за первоначальный ответ. Я думал, что я должен загрузить результаты, которые я делаю примерно так же ...

Для чего стоит конкретная форма MDS, которую я использовал, это то, что называется t-SNE (он же «t-распределенное стохастическое вложение Нейбора» ) для получения следующих изображений.

Вот изображение всех городов по порядку - на левой оси - фактическое 1-е местоположение для этого города, а города расположены в порядке сверху вниз, слева направо по этой оси. Color = country города в порядке

Вот еще одна картина, где я взял линию городов, но нанес ее на карту мира. Думаю, суть в том, что эта проблема сводится к чему-то довольно близкому к проблеме коммивояжера, но с той разницей, что это не просто упорядочение городов, но отображение городов на 1-ую линию ...

путь по карте мира

Если кому-то нужны полные выходные данные или методология, используемые здесь, пожалуйста, напишите мне.

-

РЕДАКТИРОВАТЬ:

В ответ на комментарий @ whuber ..

Да, вы правы, когда подчеркиваете локальное расстояние (то есть локальные расстояния ближайших соседей должны быть как можно ближе к фактическим расстояниям на карте мира), проблема MDS сводится к проблеме коммивояжера. Однако, если вы подчеркиваете оптимизацию (или сопоставление) расстояний в более широком / более умеренном диапазоне, вы можете получить разные результаты. Например, вот что дает алгоритм t-sne, когда вы используете более высокое значение для «недоумения»:введите описание изображения здесь

Утунги
источник
Спасибо, что поделился. Это действительно больше похоже на коммивояжера: это не MDS. Решение MDS будет иметь гораздо больше искажений, но гораздо больше регулярных, предсказуемых отношений между миром и картой. Таким образом, ваш ответ представляет собой еще одно решение исходной проблемы.
whuber
обновил мой ответ, чтобы дать еще один вариант, интересоваться вашими взглядами.
Утунга
Второе - действительно любопытное и интересное решение. Похоже, ваш алгоритм t-sne пытается точно посетить каждую точку . Это в некотором роде аналогично, в 2D-случае, созданию высокоточной локальной проекции вокруг каждой точки, а затем позволяющей проекции разбиваться между точками, серьезно искажая их расстояния и ориентации, сохраняя при этом почти идеальную локальную точность. Я полагаю, что это может иметь какое-то специальное использование, но на практике обычно допускается небольшая ошибка проекции, потому что она позволяет достаточно ослабить, чтобы значительно улучшить глобальное решение.
whuber
12

Что вы можете сделать, так это покрыть свое 2-мерное пространство 1-мерной кривой заполнения пространства, такой как кривая Пеано или кривая Гильберта. Затем вы отображаете свои точки на ближайшую точку на кривой. Разверните кривую, и вы должны в определенной степени получить линию с ближайшими городами в пространстве, ближайшем к линии.

Он не идеален (я не думаю, что что-то может быть), но я видел, что он использовался в качестве основы для алгоритма путешествующего продавца - идея заключается в том, что, если вы совершаете поездку по продавцу, это будет хорошим приближением к лучшее решение

Spacedman
источник
4
Это работает, но будьте осторожны: ближайшие города на одной линии будут находиться рядом в космосе, но ближайшие города в космосе, как правило, не будут находиться близко друг к другу на линии (карта кривых continuously-> ℝ² непрерывно, не иметь непрерывный обратный).
оставил около
2
этот ответ будет полезен из графического примера того, как выглядит кривая Пеано / Гильберта (и / или ссылки на определения)
Matt Wilkie
1
или вы могли бы пойти в википедию самостоятельно ... все там, я действительно не вижу смысла повторять здесь слишком много википедии ...
Spacedman
1
Ну, я думаю, вы можете повторить это немного! Как насчет ссылки или двух и изображения?
blah238
В качестве иллюстрации можно взглянуть на карту интернета XKCD Рэндалла Манро , которая использует именно эту технику (хотя и в обратном порядке, то есть отображение линии на плоскости)
странный
9

Странные вопросы часто самые интересные!

Если вы ищете современный способ использования измерений в картографии, вы можете начать с графической семиологии Бертина . Согласно Бертину, лист бумаги (или поверхность ipad) имеет 3 измерения: два плоских измерения плюс значение / текстура. Графическая семиология предоставляет правила для сопоставления информационных измерений с этими измерениями представления. Когда два плоских измерения являются пространственными измерениями, графика представляет собой карту, а третье измерение используется для представления информации.

Если вы хотите создать одномерную карту, это означает, что вы решили не использовать одно из измерений бумаги для представления нужной вам информации (близость между городами). Действительно ли необходимо навязывать такое ограничение, а не составлять карту нормалей?

Если это действительно необходимо, как сказано в других ответах, это невозможно сделать! Отношение близости между городами не может быть представлено в одном измерении. Для этого вы можете:

  • Используйте «ориентированный на пользователя подход»: если аудитория карты находится где-то или есть определенное место, на котором можно сфокусироваться, это место может быть принято за источник, а все другие города могут быть отсортированы в соответствии с их расстоянием до этого источника.
  • Сортируйте города не только по их относительному расстоянию, но и по другим критериям сходства (население, континент, количество автомобилей на одного жителя и т. Д.). Затем некоторые статистические обработки, такие как анализ главных компонентов, могут дать единую размерную линию, по которой можно ранжировать города.
жюльен
источник
Все ответы здесь очень интересны и интересны. Первая пуля в этом, выбрать точку происхождения, а все остальные «расстояние от начала», кажется наиболее практичной.
Мэтт Уилки
Как известно, проекция в два измерения «не может быть осуществлена»! Кстати, есть множество приложений для одномерных проекций, таких как стрип-карты для планирования поездок.
whuber
7
trying to keep cities that are 'close' on the globe 'close' on the line

Представьте себе три города на одинаковом расстоянии друг от друга, например, в вершинах равностороннего треугольника. Как бы вы представили это на линии? Некоторая информация будет потеряна.

Либо вы полностью отбрасываете одно измерение, например, проецируете все города на параллельном или меридиане (последнее было бы интересно, поскольку мы не привыкли сравнивать относительное положение городов север / юг среди разных стран), либо вы выбираете конкретный размерная мера, например, «расстояние от Нью-Йорка».

Кривая Пеано, предложенная Spacedman, очень интересна и создаст оригинальную карту, но близлежащие города могут оказаться очень далеко на этой кривой.

UncleZeiv
источник
5
... держи свои города ближе, а свои глобусы ближе ...
Томас,
1
+1 Хорошие замечания. Тем не менее, это не то или иное предложение: вам не нужно проецировать на линию или уменьшать ее до расстояния от базовой точки. Нелинейные решения доступны так же, как они используются для (обычных) 2D проекций. Цель состоит в том, чтобы минимизировать некоторую меру различий между проецируемыми расстояниями и фактическими расстояниями. В этом отношении кривая Пеано будет особенно плохой, но ее варианты (адаптированные для прохождения всех желаемых точек на ранних этапах ее построения) могут работать - своего рода.
whuber
3

Я никогда не использовал его, но я думаю, что GeoHash может сработать для этого.

Геохэш предлагает свойства, такие как произвольная точность и возможность постепенного удаления символов из конца кода, чтобы уменьшить его размер (и постепенно потерять точность).

Как следствие постепенного снижения точности, близлежащие места часто (но не всегда) представляют аналогичные префиксы. И наоборот, чем длиннее общий префикс, тем ближе эти два места.

Кирк Куйкендалл
источник
Эти хэши имеют тенденцию работать, кодируя усовершенствованные подразделения поверхности сферы в слова, и, таким образом, по сути своей двумерны. Непонятно, как можно извлечь из них одномерную координату (любым значимым способом).
whuber
@whuber Итак, если бы у меня был список городов и сгенерировал для них хэши, передав их lat / long на geohash.org, а затем отсортировал города на основе хэша, разве порядок городов не представлял бы одномерное отображение ( независимо от того, насколько это точно)?
Кирк Куйкендалл
1
Это полностью зависит от хеша. Простой заказ не одномерный, это просто заказ. Кроме того, вам нужна значимая числовая координата. Если это также исходит из хеша, то у вас действительно есть 1D-проекция, но она, вероятно, обладает ужасными свойствами. Весь смысл проекций состоит в том, чтобы игнорировать искажения, которые не имеют значения для визуализации или анализа, и минимизировать те, которые имеют значение. Маловероятно, что какой-либо хеш будет полезен в качестве проекции для большинства целей.
whuber