[Из песочницы] SciPy, алгоритмы на графах
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)
Рассмотрим применение пакета scipy.csgraph на примере детской игры «Лесенки слов». Эта игра была придумана Льюисом Кэрроллом в Рождество 1877 года. В этой игре нужно найти путь между словами, проводя замену по одной букве за раз. Например, можно проследить путь от обезьяны до человека, связав слова «ape» и «man» следующим образом:
$$display$$\rm ape \to apt \to ait \to bit \to big \to bag \to mag \to man$$display$$
Обратите внимание, что каждый шаг включает в себя изменение только одной буквы слова. Это всего лишь один возможный путь от обезьяны до человека, но является ли этот путь самым коротким? Таким образом, необходимо найти кратчайший путь (лестницу) между двумя заданными словами. Эту задачу можно решить с помощью пакета 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('
Теперь у нас есть массив, в котором каждая запись содержит три символа Юникод. Мы хотели бы найти все пары, у которых отличается ровно один символ. Начнем с преобразования каждого слова в трехмерный вектор:
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)
Вспоминаем, что расстоянием Хэмминга называется количество отличающихся символов в двух векторах одинаковой длины. С помощью расстояния Хэмминга определим длину ребер, связывающие пары слов. В лестницу слов соединяются каждые два слова с расстоянием, равным $inline$\frac{1}{N} $inline$, где $inline$ N = 3 $inline$ — количество букв в слове:
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')]
Мы увидели все две пары слов, которые максимально отделены друг от друга. Это «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 будет интересно почитать в следующей статье.
