SciPy, алгоритмы на графах

image


SciPy (произносится как сай пай) — это пакет прикладных математических процедур, основанный на расширении Numpy Python. Он значительно расширяет возможности Python, предоставляя в распоряжение пользователя команды и классы высокого уровня для управления данными и их визуализацией. С SciPy интерактивный сеанс Python превращается в такую же полноценную среду обработки данных и прототипирования сложных систем, как MATLAB, IDL, Octave, R-Lab и SciLab.


Введение


Пакет SciPy рекомендуется устанавливать в составе Anaconda. Желательно также знакомство с основами Python и иметь под рукой документацию по Numpy. Для краткости и дальнейшего удобства договоримся, что основные пакеты (numpy, scipy и matplotlib) будут импортироваться следующим образом:


import numpy as np
import matplotlib as mpl
import matplotlib.pyplot as plt

Это официальное соглашения об импорте, используемые в исходном коде NumPy, SciPy и в документации. Соблюдение этих соглашений в Вашем коде не обязательно, но настоятельно рекомендуется. Каждый из пакетов желательно импортировать отдельно следующим образом:


from scipy import linalg, optimize

SciPy и NumPy имеют полные версии документации, которые охватывают почти все их функции. Они доступны на https://docs.scipy.org/ в формате HTML и PDF. Некоторые части могут быть неполными или устаревшими, т.к. документация постоянно находится в процессе разработки. Поскольку SciPy является волонтерской организацией и зависит от сообщества, Ваше участие от предоставления обратной связи до улучшения документации и кода приветствуется и активно поощряется.


Алгоритмы на разреженных графах (scipy.csgraph)



Льюис Кэрролл, веселое Рождество 1877


Рассмотрим применение пакета scipy.csgraph на примере детской игры "Лесенки слов", придуманной Льюисом Кэрроллом в Рождество 1877 года. В этой игре нужно найти путь между словами, проводя замену по одной букве за раз. Например, можно проследить путь от обезьяны до человека, связав слова «ape» и «man» следующим образом:


$\rm ape \to apt \to ait \to bit \to big \to bag \to mag \to man$


Обратите внимание, что каждый шаг включает в себя изменение только одной буквы слова. Это всего лишь один возможный путь от обезьяны до человека, но является ли этот путь самым коротким? Таким образом, необходимо найти кратчайший путь (лестницу) между двумя заданными словами. Эту задачу можно решить с помощью пакета scipy.sparse.csgraph.


Сначала нам понадобится список допустимых слов. Многие операционные системы имеют такой встроенный список. Например, в linux список слов можно найти в одном из следующих мест:


/usr/share/dict 
/var/lib/dict 

Другим источником слов являются словари, доступные на разных сайтах в Интернете (поищите в Вашей любимой поисковой системе). Системный список слов представляет собой файл с одним словом на строку. Для использования системного списка слов необходимо прочитать его следующим образом:


word_list = open('/usr/share/dict/words').readlines()
word_list = map(str.strip, word_list)

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


word_list = [word for word in word_list if len(word) == 3]
word_list = [word for word in word_list if word[0].islower()]
word_list = [word for word in word_list if word.isalpha()]
word_list = list (map (str.lower, word_list))
len (word_list)

591

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


word_list = np.asarray(word_list)
word_list.sort()  # сортируем для быстрого поиска
word_list.dtype   # тип данных - символы Unicode в Python

dtype('<U3')

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


word_bytes = np.ndarray((word_list.size, word_list.itemsize),
                        dtype='uint8',
                        buffer=word_list.data)
# длина каждого символа юникода - 4 байта. Нам нужен только первый байт
# каждое слово состоит точно из трех символов
word_bytes = word_bytes[:, ::word_list.itemsize//3]
word_bytes.shape

(591, 3)

Вспоминаем, что расстоянием Хэмминга называется количество отличающихся символов в двух векторах одинаковой длины. С помощью расстояния Хэмминга определим длину ребер, связывающие пары слов. В лестницу слов соединяются каждые два слова с расстоянием, равным $\frac{1}{N} $, где $ N = 3 $ — количество букв в слове:


from scipy.spatial.distance import pdist, squareform
from scipy.sparse import csr_matrix
hamming_dist = pdist (word_bytes, metric = 'hamming')
graph = csr_matrix (squareform (hamming_dist < 1.5 / 3))

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


i1 = word_list.searchsorted ('ape')
i2 = word_list.searchsorted ('man')

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


from scipy.sparse.csgraph import dijkstra
distances, predecessors = dijkstra(graph, indices=i1,
                                    return_predecessors=True)
print(distances[i2])

5.0

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


path = []
i = i2
while i != i1:
    path.append(word_list[i])
    i = predecessors[i]
path.append(word_list[i1])
print(path[::-1]) 

['ape', 'apt', 'opt', 'oat', 'mat', 'man']

Длина лестницы на три ступеньки меньше, чем в начальном примере. Используя другие инструменты модуля, можно найти ответ и на другие вопросы. Например, существуют ли слова с тремя буквами, которые не связаны в лестницу слов? Это задача определения связности графа:


from scipy.sparse.csgraph import connected_components
N_components, component_list = connected_components(graph)
print(N_components)

15

В нашем примере для слов из трех букв имеется 15 связанных компонентов: то есть 15 различных наборов слов без путей между ними. Сколько слов в каждом из этих наборов? Мы можем узнать это из списка компонентов:


[np.sum(component_list == i) for i in range(N_components)]

[577, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

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


[list(word_list[np.where(component_list == i)]) for i in range(1, N_components)]

[['aha'],
 ['chi'],
 ['ebb'],
 ['gnu'],
 ['ism'],
 ['khz'],
 ['nth'],
 ['née'],
 ['ova'],
 ['qua'],
 ['ugh'],
 ['ups'],
 ['urn'],
 ['use']]

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


distances, predecessors = dijkstra(graph, return_predecessors=True)
max_distance = np.max(distances[~np.isinf(distances)])
print(max_distance)

13.0

Итак, в нашем примере существуют такие пары слов, между которыми самая короткая лестница содержит 13 ступеней! Давайте определим, что это за пары:


i1, i2 = np.where(distances == max_distance)
list(zip(word_list[i1], word_list[i2]))

[('imp', 'ohm'),
 ('imp', 'ohs'),
 ('ohm', 'imp'),
 ('ohm', 'ump'),
 ('ohs', 'imp'),
 ('ohs', 'ump'),
 ('ump', 'ohm'),
 ('ump', 'ohs')]

Мы увидели все возможные сочетания пар слов, расстояние между которыми равно 13 (максимально отделены друг от друга). Если присмотреться, с одной стороны лестницы находятся слова «imp» и «ump», которые отличаются между собой всего одной буквой. С другой стороны лестницы находятся слова «ohm» и «ohs», которые также отличаются всего одной буквой. Список ступенек между этими словами будет почти одинаковым. Его можно найти так же, как было указано выше:


path = []
i = i2[0]
while i != i1[0]:
    path.append(word_list[i])
    i = predecessors[i1[0], i]
path.append(word_list[i1[0]])
print(path[::-1])

['imp', 'amp', 'asp', 'ass', 'ads', 'ids', 'ins', 'inn', 'ion', 'won', 'woo', 'who', 'oho', 'ohm']

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

Поделиться публикацией

Комментарии 11

    +1
    Пакет SciPy рекомендуется устанавливать в составе Anaconda.
    Где рекомендуется и почему именно анаконда? А если я через pip хочу?
      0
      scipy.org/install.html — первый пункт в списке.
      Рекомендуется анаконда, потому что с ней в комплекте идет вся экосистема для научных вычислений (numpy, matplotlib и т.д.). Если все это добро Вам не нужно, ставьте на здоровье через pip.
        +1
        Пруф приведёте на «официальное руководство» где написано, что сайпай «рекомендуется устанавливать в составе Anaconda»?

        потому что с анакондой в комплекте идет вся экосистема для научных вычислений (numpy, matplotlib и т.д.)
        И ради numpy, matplotlib и scipy вы предлагаете скачать инсталлятор весом более 500Мб и затем развернуть 300+ пакетов (большинство из которых никогда не будут использованы)?
          0
          Пруф привел. От себя могу добавить, что для подготовки научных публикаций анаконда очень удобная штука, поэтому лично я ее тоже рекомендую. Матлаб вообще по 5 Гб дистрибутивы, и представьте себе, качают!
            +2
            Вы правда считаете, что вот это:
            «For many users, especially on Windows, the easiest way to begin is to download one of these Python distributions, which include all the key packages:
            — Anaconda
            — Enthought Canopy
            — Python(x,y)
            — WinPython
            — Pyzo»
            тождественно вашему:
            «Пакет SciPy рекомендуется устанавливать в составе Anaconda»?

            И если уж вы рекомендуете именно этот способ получения scipy, то какие проблемы он помогает решить в сравнении с pip install?
              0
              Анаконда помогает решить проблемы, связанные с проведением исследованием, мат моделированием и публикацией результатов. Как pip install помогает решить эти проблемы я не могу сказать.
                0

                dedyshka balezz
                Тут спор у вас вышел ни о чём по сути.
                Среди некоторой части научных работников существует что-то вроде суеверия.
                Смысл которого — пользуйся Anaconda и все пакеты у тебя встанут как нужно.
                Это от лени и нежелания ковырять в кошках системы.
                И это нормально.
                А у вас получается разговор слепого с глухим о слоне.
                И напоследок подолью масла в огонь (мне тоже нужно погреться)
                Наиболее кошерным способом установки всего из мира python сейчас становится pyenv и pipenv.
                По отдельности или вместе.
                Уж полгода как начал активно pyenv пользоваться и нарадоваться не могу.
                Что внутри будет это вторично хоть pip хоть conda всё равно.

                  0
                  Спасибо Вам, теперь все расставлено на свои места.
      0
      «Мы увидели все две пары слов, которые максимально отделены друг от друга. Это «imp» и «ump», с одной стороны, и «ohm» и «ohs», с другой.» Однако прямо перед этой фразой в выводе видно восемь пар слов, и упомянутых пар среди них нет. Такие пары можно получить, если взять первое и последнее слово в столбцах вывода. Но тогда зачем все остальные слова? Поясните, пожалуйста, этот момент.
        0
        imp и ump в лестнице слов ведут к одному и тому же слову amp с одной стороны,
        вершины ohm и ohs с другой стороны лестницы являются смежными для одной и той же вершины — oho.
        Путь между oho и amp одинаков для всех восьми вариантов (не учитывая направления, естественно).
        Статью поправил, надеюсь теперь понятно.
          0
          Да, спасибо, теперь понятно.

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

      Самое читаемое