Вычисление матрицы расстояний для набора сайтов по их координатам на Python

Расчет матрицы расстояний для набора веб-сайтов на Python по их координатам

Легко оценить расстояние между любой парой сайтов по их географическим координатам как ступенька к эффективному решению проблем маршрутизации

👁️ Это статья №4 из серии, охватывающей проект «Интеллектуальная система поддержки принятия решений для туризма на Python». Я призываю вас ознакомиться с ним, чтобы получить общее представление о всем проекте. Если вас интересует только создание матрицы расстояний, вам понадобится только эта статья, она самодостаточна. Если Вы также хотите применить матрицу расстояний к практическим проблемам, этот сериал будет интересен для вас.

В настоящей статье мы продолжаем наше путешествие именно там, где мы закончили третью спринт. Здесь, в четвертом спринте, мы ненадолго отклоняемся от моделирования и разрабатываем класс с геопространственной функциональностью, который будет очень полезен, когда мы попытаемся решить общие проблемы коммивояжера, то есть проблемы для произвольных сайтов, для которых у нас может и не быть готовых данных о расстоянии. Мы указали это “требование” в предыдущем спринте, и мы построим подсистему, чтобы удовлетворить его в этом спринте.

Содержание

1. Предыдущий спринт резюме

2. Чтение входных данных

3. Создание матрицы расстояний из данных о местоположении

• 3.1. Стоит ли пойти на повышение?
• 3.2. Геолокационные утилиты с помощью geopy
• 3.3. Добираемся до точек
• 3.4. От координат до матрицы расстояний

4. Обернуть в Class

• 4.1. Проектирование класса GeoAnalyzer
• 4.2. Пример использования класса

5. Заключение (или планы на следующий спринт)

1. Предыдущий спринт резюме

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

При этом наш новый базовый вход будет намного проще: просто географические координаты сайтов, которые мы хотим посетить:

• Инференциальные двигатели с улучшенным поиском и генерацией (RAG) с использованием LangChain на процессорах.
• «Индия обращается к искусственному интеллекту для преодоления языкового барьера»
• Data Engineering Руководство для начинающих вдохновленное Формулой 1

и вывод будет представлять собой фрейм данных, который мы использовали в качестве входных данных для модели TSP, матрицы расстояний для входных сайтов:

Чтобы обеспечить последовательность, мы будем использовать те же парижские сайты, которые мы рассматривали до сих пор. В следующей статье мы интегрируем эту функциональность с оптимизационной моделью задачи коммивояжера, что позволит создать более гибкий MVP.

🎯 Сохраняя конечную цель в виду

Давайте немного отойдем в сторону и кратко рассмотрим, почему мы делаем это. Оригинальная задача реальной жизни, которую мы стремимся решить, – это то, что мы можем назвать Проблемой путешествующего туриста (TTP), то есть проблема создания оптимальных планов поездок для обычного туриста, учитывая его «личные» данные (предпочтения, бюджеты и т. д.) и данные «окружающей среды» поездки (расстояния, цены, виды транспорта и т. д.).

Поскольку эта задача реальной жизни оказалась слишком сложной, мы упростили ее до сущностной версии в спринте 1, чтобы разработать решение. Эта «сущностная проблема» оказалась Задачей коммивояжера (TSP), в которой мы рассматривали посещаемые точки как «интересные места» для туриста в городе. С разработанной в этой статье функциональностью мы приближаемся к общему решению TTP, в котором TSP является ядром решения.

2. Чтение входных данных

Наши основные входные данные теперь представляют собой географические координаты мест, которые мы хотим посетить во время поездки. Мы рассматриваем «отель» как другой вид места, поскольку отель сам по себе не является «интересным местом», но это место, которое мы должны посетить, чтобы выспаться во время многодневных поездок. Наш выбор отеля может быть разным в другой поездке или в других обстоятельствах, в то время как интересные места в городе являются более или менее «постоянными» местами, в отношении которых существует согласие множества путеводителей. Полезность этого различия станет более очевидной, когда мы будем готовы исследовать более сложные приложения.

Поэтому я сохранил координаты нашего отеля в CSV-файле location_hotel.csv, а координаты для «интересных мест» в отдельном CSV-файле sites_coordinates.csv. Оба CSV-файла имеют одну и ту же структуру, поэтому мы считываем и объединяем их в один фрейм данных, содержащий все наши места:

import pandas as pdprint(f"версия pandas: {pd.__version__}")DATA_FOLDER = ("https://raw.githubusercontent.com/carlosjuribe/"               "traveling-tourist-problem/main/data")FILE_LOCATION_HOTEL = "location_hotel.csv"FILE_LOCATION_SITES = "sites_coordinates.csv"df_sites = pd.concat([    pd.read_csv(f"{DATA_FOLDER}/{FILE_LOCATION_SITES}", index_col='site'),    pd.read_csv(f"{DATA_FOLDER}/{FILE_LOCATION_HOTEL}", index_col='site')])display(df_sites)

ℹ️ Как быстро подготовить собственные данные о местоположении

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

1. Перейдите на Google Maps и поищите каждое место в вашем списке.

2. Каждое место будет отображаться как точка на карте. Нажмите кнопку правой кнопкой мыши на каждой из них. Первый элемент, который появляется, представляет собой пару чисел: широту и долготу точки, на которую вы нажали.

3. Нажмите на эти числа, они будут сохранены в буфер обмена и готовы к вставке в файл вместе с выбранным вами именем для этой точки.

4. Повторите шаги 1-3 для всех своих сайтов, и у вас будет файл, эквивалентный sites_coordinates.csv.

Этот процесс хорошо работает для небольшого набора сайтов, но если у вас есть сотни или даже десятки сайтов, это становится очень трудоемким. В [дальнейшей статье] мы создадим способ автоматизировать эту ручную работу, которую называют геолокацией.

3. Создание матрицы расстояний из данных о местоположениях

Для создания матрицы расстояний нам необходимо получить расстояние между любой парой местоположений. Звучит просто, но “расстояние” действительно зависит от контекста. Мы учитываем число, указанное в приложениях для картографирования, таких как Google Maps, которые учитывают уличную сеть, мосты, парки и т. Д.? Если да, то мы учитываем расстояние, которое проходимый пешеходом или проходимый автомобилем? Или, может быть, просто длину прямой линии, соединяющей две точки? Очевидно, что у нас есть множество возможных расстояний на выбор с разными степенями точности. Первый вопрос, на который мы должны ответить: как мы должны определить “расстояние” в конкретном контексте нашей проблемы и на этом этапе?

3.1. Стоит ли пойти на большую дистанцию, чтобы получить дополнительный ярд?

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

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

👁️ Бесплатной точности не существует

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

Итак, давайте начнем с очень простого. У нас есть координаты. Первая идея: эти координаты распределены по частям Земли, очень малым по сравнению с радиусом Земли, поэтому мы можем считать широты как координаты Y и долготы как координаты X на плоскости двух измерений, а затем просто вычислить евклидово расстояние (фантастический термин для обычной “прямой линии”).

• Плюсы: простая формула для расстояния, отсутствие новых зависимостей или данных, сохранение пространственных отношений между местоположениями.
• Минусы: широты и долготы являются безразмерными числами, поэтому числа, полученные при решении проблемы, не будут являться фактическими расстояниями. Это означает, что некоторая информация, о которой мы заботимся, например, общее пройденное расстояние, не будет доступна, даже если мы сможем получить оптимальный маршрут.

Минусы перевешивают плюсы, поэтому нам нужен более сложный подход (но все еще простой). Вторая идея: рассматривать координаты как то, что они есть, точки на Земле, но приближать Землю к сфере. Сфера не обладает знакомой евклидовой геометрией, поэтому нам понадобится нетривиальная формула, которая учитывает эту сферическую геометрию при вычислении “прямой линии” между двумя точками. Таким образом, теперь дело только за реализацией этой формулы с использованием радиуса Земли. Мы могли бы это сделать, но вместо этого мы полагаемся на известную библиотеку, которая уже делает это и даже лучше.

3.2. Утилиты геолокации с помощью geopy

Если эта серия статей особенно сосредоточена на геопространственной науке, было бы ценно потратить время на объяснение и реализацию формулы для расчета расстояния по большому кругу, хороший вариант для вычисления “прямолинейного” расстояния между точками на сфере. Однако эта серия статей посвящена созданию системы планирования туризма, основанной на оптимизации, поэтому вместо разработки собственных формул для геопространственных утилит мы полагаемся на Geopy, чтобы это сделать за нас. Таким образом, мы сохраняем фокус на быстром достижении решения.

Установите его, запустив в командной строке Anaconda (или внутри созданной нами среды conda в первой статье, если вы создали ее), следующее:

conda install -y -c conda-forge geopy=2.3.0

Теперь давайте проведем демонстрацию с geopy для только двух местоположений.

3.3. Движение к точкам

Учитывая координаты двух точек, функция geodesic модуля geopy вычисляет расстояние по геодезической, соединяющей эти две точки на поверхности Земли. В геометрии геодезической линией называется путь минимального расстояния между точками в заданном метрическом пространстве. В нашем знакомом евклидовом пространстве геодезическими линиями являются прямые линии. В сферическом пространстве это большие окружности. Модель “пространства”, рассматриваемая функцией geodesic из модуля geopy, является точной эллипсоидной моделью Земли.

👁 Большая окружность прекрасна, но эллипс еще прекраснее

Ранее я говорил, что мы будем считать Землю сферой, потому что это было самое простое рабочее приближение. На самом деле, Земля не является сферой, а эллипсоидом – твердым телом с более сложной геометрией. Теперь, когда geopy освобождает нас от кодирования собственных функций для невыпуклой геометрии, мы можем улучшить наше приближение Земли и использовать более точное расстояние, вычисленное на эллипсоиде между двумя точками, а не расстояние по большой окружности. Более точная модель Земли при том же количестве строк кода. Это действительно бесплатная точность, так зачем ее не использовать?

Вот функция, которая вычисляет эллипсоидное расстояние между точкой 1 и точкой 2, в метрах:

from geopy.distance import geodesicdef ellipsoidal_distance(p1, p2) -> float:    """ Вычисляет расстояние (в метрах) между p1 и p2, где каждая точка представлена в виде кортежа (широта, долгота) """    return geodesic(p1, p2).meters

Какое расстояние между Эйфелевой Башней и Лувром?

p1 = df_sites.loc['Tour Eiffel']p2 = df_sites.loc['Louvre']ellipsoidal_distance(p1, p2)  # результат: 3173.119635531859

3173 метра, примерно 3,2 км. Google Maps говорит, что это 3,5 км. Вычисленное расстояние на 8,6% меньше “реального” расстояния. Наши ноги, однако, обращают внимание только на абсолютные ошибки в расстоянии, которые в этом случае составляют всего лишь 330 метров дополнительного пути по сравнению с оцененным расстоянием. Кажется, что это несущественная ошибка для туриста, который ожидает бродить по большому городу целый день.

А между Эйфелевой Башней и Портом де Суффрен?

ellipsoidal_distance(    df_sites.loc['Tour Eiffel'],    df_sites.loc['Port de Suffren'])  # результат: 328.3147101635456

328 метров, на этот раз на 6% меньше (на 22 метра короче), чем 350 метров, которые указывает Google Maps. Не так плохо для применения формулы. Как и ожидалось, чем ближе точки, тем меньше шансов наличия зигзагов у улиц и поворотов, и тем меньше ошибка, вызванная эллипсоидной моделью. Для наших текущих целей это выглядит достаточно хорошо.

Теперь нам нужно применить эту функцию ко всем парам местоположений, чтобы получить матрицу расстояний, необходимую для модели TSP.

3.4. От координат до матрицы расстояний

Это простая часть, где мы просто должны перебрать все сайты дважды, вычислить и сохранить расстояние между каждой парой. Ниже приведена функция, выполняющая это. Обратите внимание, что метрика расстояния передается как необязательный аргумент, по умолчанию используется эллипсоидное расстояние, которое мы использовали ранее. Мы оставляем возможность передачи более точных метрик расстояния в будущем.

def compute_distance_matrix(df_sites, dist_metric=ellipsoidal_distance):    """ Создает матрицу расстояний размером N x N из данных о N местоположениях     с колонками широты и долготы """    df_dist_matrix = pd.DataFrame(index=df_sites.index,                                   columns=df_sites.index)    for orig, orig_loc in df_sites.iterrows():  # для каждого местоположения        for dest, dest_loc in df_sites.iterrows():  # для каждого места назначения            df_dist_matrix.at[orig, dest] = dist_metric(orig_loc, dest_loc)    return df_dist_matrixdf_distances = compute_distance_matrix(df_sites)display(df_distances)

И вот оно! Как и ожидалось, диагональ матрицы равна нулю, и матрица симметрична. Индексы и столбцы выходного dataframe содержат имена входных местоположений.

Показана функциональность. Теперь мы можем улучшить эту функцию для удобства использования. Завернем эту функциональность внутрь класса, чтобы сделать ее удобно повторно использовать, и, что более важно, для более легкой интеграции с моделью оптимизации TSP, созданной в предыдущем спринте.

4. Обернем это! (внутри класса)

4.1. Дизайн класса GeoAnalyzer

Создадим новый класс GeoAnalyzer, посвященный геопространственным утилитам, которые могут возникнуть в задачах маршрутизации. Таким образом, наша функция compute_distance_matrix естественно вписывается как метод. Основные части этого класса на данный момент будут следующими:

• Dataframe с местоположениями сайтов, атрибут _df_locations.
• Чистая функция ellipsoidal_distance.
• Метод get_distance_matrix, эквивалентный предыдущей функции compute_distance_matrix, но использующий атрибут экземпляра _df_locations для вычисления расстояний.

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

Ниже приведено определение класса GeoAnalyzer. Здесь также есть другие удобные методы и свойства, не упомянутые здесь.

from typing import Tupleimport pandas as pdfrom geopy.distance import geodesicclass GeoAnalyzer:    """ Вспомогательные функции для географической информации и обработки """      _GeoPoint = Tuple[float, float]        def __init__(self):        """ Используйте метод `add_locations` для сохранения некоторых местоположений внутри класса         и начать использование гео-утилит """        self._df_locations = pd.DataFrame(columns=['широта', 'долгота'])            #####################   расстояния   #####################    @staticmethod    def ellipsoidal_distance(point1: _GeoPoint, point2: _GeoPoint) -> float:        """ Вычисляет эллипсоидное расстояние (в метрах) между точкой 1         и точкой 2, где каждая точка представлена в виде кортежа (широта, долгота)        """        return geodesic(point1, point2).meters    #########################################################        @property    def locations(self):        return self._df_locations        @property    def num_locations(self):        return len(self._df_locations)            def add_locations(self, df_locations: pd.DataFrame):        """ Географические данные, необходимые для анализа.        Параметры        ----------        df_locations : pd.DataFrame            Dataframe географических координат с первым столбцом,             названным 'широта' и вторым столбцом, названным 'долгота'        """        df_updated = pd.concat([self._df_locations, df_locations.copy()])        # удаление дубликатов на случай, если пользователь добавляет повторяющиеся местоположения        self._df_locations = df_updated.drop_duplicates()            def get_distance_matrix(self) -> pd.DataFrame:        """ Вычисляет матрицу расстояний в виде dataframe на основе         предоставленных данных о местоположении """        df_locations = self._df_locations        dist_metric = self.ellipsoidal_distance  # доступно только одно расстояние        # инициализация dataframe для матрицы расстояний        df_dist_matrix = pd.DataFrame(index=df_locations.index,                                       columns=df_locations.index)        # для каждой пары места отправления и назначения вычисляем расстояние        for orig, orig_loc in df_locations.iterrows():            for dest, dest_loc in df_locations.iterrows():                  df_dist_matrix.at[orig, dest] = dist_metric(orig_loc,                                                            dest_loc)        # немного метаданных не повредит        df_dist_matrix.distance_metric = dist_metric.__name__        return df_dist_matrix            def __repr__(self):        """ Выводит количество рассматриваемых в данный момент местоположений """        return f"{self.__class__.__name__}(n_locs={self.num_locations})"

4.2. Пример использования класса

Давайте немного исследуем основную функциональность класса. Мы создаем экземпляр и добавляем наши интересующие нас места из Парижа:

geo_analyzer = GeoAnalyzer()geo_analyzer.add_locations(df_sites)

Мы проверяем представление нашего экземпляра на данном этапе, которое говорит нам о том, что мы предоставили 9 мест, подробности которых мы можем проверить с помощью атрибута locations:

display(geo_analyzer)display(geo_analyzer.locations)

Конечно, мы можем извлечь матрицу расстояний из объекта, которая к настоящему моменту уже довольно знакома:

df_distances = geo_analyzer.get_distance_matrix()display(df_distances)

И, наконец, если мы интересуемся, откуда взялись эти значения, мы можем проверить это из самого датафрейма:

print(f"Используемая метрика расстояния: {df_distances.distance_metric}")# [Out]: Используемая метрика расстояния: ellipsoidal_distance

Это было бы более ценным, если бы у нас было больше метрик расстояния, что мы увидим в будущих спринтах.

5. Заключение (и планирование для следующего спринта)

Итогом нашей работы стал класс GeoAnalyzer с удобными методами, которые помогут нам обобщить проблему коммивояжера на произвольные наборы мест. Точное целью нашего следующего спринта будет обобщение этой проблемы с помощью класса, похожего на оценщик, для TSP, который скрывает этапы создания модели, рассмотренные в спринте 2, и принимает в качестве входных данных географические координаты мест, которые нужно посетить. Класс GeoAnalyzer будет ключевым компонентом этого нового класса-оценщика, позволяющим полноценное использование оптимизационной модели TSP, которую мы построили. Этот новый класс-оценщик, объединяющий гибкость GeoAnalyzer и обобщенность модели TSP, станет основой нашего решения более общей проблемы путешествия туриста, которую мы стремимся решить. Продолжайте к следующему спринту для настоящего результата!

Не стесняйтесь следовать за мной, задавать мне вопросы, давать обратную связь или связаться со мной через LinkedIn. Спасибо за чтение! 📈😊