Даже основы помогут вам начать!

Почему я должен узнать об этом прямо сейчас, а не позже?

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

  • ускорить код значительно
  • свести функции с большим количеством циклов, индексирования и т. д. к сладким однострочникам
  • сделать возможными определенные задачи, которые ранее были практически неразрешимыми

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

Основные понятия и терминология

Граф состоит из набора узлов {a1, a2,… и}, а также набора ребер, , которые соединяют некоторые или все узлы друг с другом (Рис. 1). Например, пусть есть набор аэропортов {ap1, ap2, ap3}. Если есть рейсы между всеми аэропортами, кроме ap2, который предлагает рейсы только до ap3, края будут {(ap1, ap3), (ap3, ap1), (ap2, ap3), (ap3, ap2)}. Обычно термин «граф» относится к тем графам, в которых все ребра также существуют в их перевернутой форме (ap1, ap3) - ›(ap3, ap1). В противном случае он называется направленным графиком, который не является частью этого руководства.

Каждый граф может быть представлен в числовой форме его матрицей смежности. В данном случае это:

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

Это вся теория, необходимая для начала работы. Давайте решим некоторые реальные проблемы. Вы можете найти весь код в этом репозитории на github.

Подготовка данных

Набор данных

В качестве реального приложения я выбрал набор полетных данных. Общедоступный, этот набор данных включает все рейсы, которые вылетают или начинаются в 2500 участвующих аэропортах. Загрузите набор данных с отпечатком пальца md5: 0df632f65e1d7b7dd6f89294e81861e0, чтобы повторить мой анализ.

Уборка

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

Анализ

Чтобы проиллюстрировать полезность подхода теории графов, мы зададим несколько основных вопросов, которые могут возникнуть у специалиста по данным относительно набора полетных данных. Затем мы сравним простоту и эффективность типичного подхода pandas с подходом графа.

Предварительный анализ: создание матрицы смежности

Метод графа основан на манипулировании матрицей смежности. Таким образом, нам нужно сначала создать его. Рассматривайте время, потраченное на вычисление матрицы смежности, как вложение. Это будет того стоить.

Во-первых, нам нужно получить список всех уникальных аэропортов в наборе данных. Это очень легко сделать с помощью pandas и numpy (не забудьте их импортировать).

airports = np.unique(np.append(df[“origin”], df[“destination”]))

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

mapping_dict = {k:i for i,k in enumerate(airports)}
df_mapped = df.applymap(lambda x: mapping_dict[x])

Теперь матрица смежности находится всего в одном шаге. Мы собираемся создать нулевую матрицу размером nxn, где n - количество уникальных аэропортов. Затем мы просматриваем каждую строку фрейма данных только один раз и смотрим, нужно ли изменить значение 0 на 1.

# Create null-matrix
A = np.zeros((len(airports), len(airports)), dtype = int)
# Enter 1 into the null-matrix where there is an edge
for date, flight in df_mapped.iterrows():
    i, j = flight["origin"], flight["destination"]
    if A[i,j] == 0:
        A[i,j], A[j,i] = 1,1

Хорошо, мы сделали это! Вот наша матрица смежности:

Вопрос 1: Можете ли вы лететь из пункта А в пункт Б напрямую?

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

def exists_direct_path(df, node1, node2):
    
    # Loop through each row
    for i, row in df.iterrows():
        
        # Check whether (node1, node2) or (node2, node1) is in the dataset
        if {row["origin"], row["destination"]} == {node1,node2}:
            return True
        
    return False

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

A[node1, node2] == 1

Но ждать? Разве это не ложное сравнение? Не делает ли функция «exists_direct_path» то же самое, что мы делали в предварительном анализе? В самом деле, метод графа имеет здесь только преимущество, потому что мы предварительно вычислили то, что сейчас делает общий метод. Однако в том-то и дело! Мы перебрали каждую строку один раз и теперь можем проверять каждый путь, просто индексируя. Используя «exists_direct_path», каждый отдельный вызов функции будет выполнять один и тот же цикл. Это явно неэффективно.

Фактически, выполнение 200 таких сравнений заняло у моего ноутбука 18 секунд. Графический метод занял 0,0006 секунды. Мы уже видим:

Есть проблемы, которые прекрасно решаются стандартными методами Python и Pandas, но ужасно неэффективно по сравнению с методом на основе графов.

Вопрос 2: Со сколькими аэропортами напрямую связана А?

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

Решение этой проблемы обычными методами означало бы перебрать все строки и отслеживать все возможные места назначения, найденные в чем-то вроде списка. Вот как это могло бы выглядеть:

def degree(df, node): # degree is the technical term
    
    # Setup empty list
    flights = []
    
    # Loop through every row
    for i, row in df.iterrows():
        
        # If the node is either an origin or a destination, there must be a direct path
        if row["origin"] == node:
            flights.append(row["destination"])
        elif row["destination"] == node:
            flights.append(row["origin"])
    
    # Remove duplicates
    flights = list(set(flights))
    
    return len(flights)

Используя матрицу смежности, это снова намного проще:

A[node].sum()

Как и раньше, эффективность работы впечатляет. Получение степени 200 узлов заняло у моего ноутбука 19,5 секунды, в то время как метод на основе графов занял 0,02 секунды.

Вопрос 3: Сколько раз мне придется пересаживаться из пункта А в пункт Б?

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

Мы можем использовать еще одно удобное свойство матрицы смежности. Помните, что ранее я определил матрицу смежности как указание количества путей длиной 1 между каждой парой узлов. Оказывается, если возвести матрицу смежности в степень 2, получится количество путей длиной 2 и так далее. Другими словами: если рейс между аэропортами ap1 и ap2 требует как минимум трех изменений, вы обнаружите, что: (A ** 3) [ap1, ap2] ›0. Следовательно, чтобы найти кратчайший путь между двумя аэропортами, нам нужно умножить A на себя, пока не найдем значение ›0.

Этот трюк позволяет нам эффективно находить кратчайший путь, возводя A в возрастающую степень до тех пор, пока путь не будет найден. Как только он будет найден, последнее число A будет увеличиваться до минимальной длины пути. Нам также нужно указать компьютеру, когда прекратить поиск, иначе он будет искать вечно, пока не найдет путь. В этом случае я установил эту максимальную длину равной 10. Если совпадения для A¹⁰ не найдено, программа просто вернет 10.

def shortest_path(A, x, y, iterations = 10, mapping_dict = mapping_dict):
    
    # Create copy of Matrix to work on
    M = A.copy()
    
    # Get numerical representations of airports
    i, j = mapping_dict[x], mapping_dict[y]
    
    # Define the maximum power to which A is to be raised
    iterations = 10
    # A = A*A until a path is found or the max iterations are reached
    for k in range(iterations):
        if M[i,j] == 0:
            M = np.matmul(M,A)
        else:
            return (x,y,k)

Возвращаясь к проблеме, ваш клиент хотел бы вылететь в «LFPO» и имеет в виду пункты назначения «YWHA», «LTAC», «LIRF», «EVRA» и «KRFI».

home_airport = "LFPO"
vacation_destinations = ["YWHA", "LTAC", "LIRF", "EVRA", "KRFI"]
max_changes = 2

Используя функцию «shorttest_path», мы можем легко сказать ему, какие пункты назначения могут быть достигнуты с максимум двумя изменениями.

n_changes = [shortest_path(A, home_airport, destination) for destination in vacation_destinations]
acceptable = [destination for location, destination, changes in n_changes if changes <= 2]
acceptable

Выход:

['LIRF', 'EVRA']

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

Если вы когда-либо работали с алгоритмами с экспоненциальной сложностью, вы, вероятно, уже понимаете, насколько плох этот метод. Он может нормально работать с 5 или 10 аэропортами. Но возьмите 1000 аэропортов, и ваши внуки уйдут на пенсию до того, как закончится ваш анализ. В отличие от этой экспоненциальной сложности, метод на основе графов имеет сложность O (n³), поскольку все, что он делает, - это умножение матриц.

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

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

Заключение

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

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

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

Большое спасибо за чтение!