Алгоритмы поиска на графах с Python
В этой статье я расскажу вам о реализации алгоритмов поиска на графах с помощью Python. Как специалист по данным, вы должны уметь находить отношения между людьми, используя сеть, которую они создают друг в друге. Итак, здесь я познакомлю вас с алгоритмами поиска на графах, которые вы должны знать в науке о данных с использованием Python.
Что такое алгоритмы поиска на графах?
Как люди, практикующие машинное обучение, мы довольно хорошо освоили Pandas, SQL или любую реляционную базу данных. Мы привыкли видеть наших пользователей в строках, а их атрибуты – в столбцах. Но так ли себя ведет реальный мир?
В связанном мире пользователей нельзя рассматривать как независимые сущности. У них есть определенные отношения друг с другом, и иногда мы хотим включить такие отношения при построении наших моделей машинного обучения.
Теперь, когда в реляционной базе данных мы не можем использовать такие отношения между разными пользователями, в графовой базе данных это сделать довольно просто. В этой статье я расскажу о некоторых из самых важных графовых алгоритмов, о которых вы должны знать, и о том, как их реализовать с помощью Python.
Алгоритмы поиска на графах: связанные компоненты
Вы можете думать о связанных компонентах в очень простых терминах как о своего рода алгоритме жесткой кластеризации, который находит кластеры в связанных данных.
В качестве конкретного примера, допустим, у вас есть данные о дорогах, соединяющих два города мира. И вам предстоит узнать все континенты мира и какой город на них расположен.
Алгоритм связанных компонентов, который мы используем для этого, основан на частном случае BFS/DFS. Я не буду здесь много говорить о том, как он работает, но мы увидим, как заставить код работать с Networkx.
Я буду использовать модуль Networkx в Python для построения и анализа наших графовых алгоритмов. Начнем с примера диаграммы, который мы используем для наших целей. Он содержит информацию о городах и расстоянии между ними.
Я начну с создания списка ребер с расстояниями, которые я добавлю в качестве веса ребер:
edgelist = [['Mannheim', 'Frankfurt', 85], ['Mannheim', 'Karlsruhe', 80], ['Erfurt', 'Wurzburg', 186], ['Munchen', 'Numberg', 167], ['Munchen', 'Augsburg', 84], ['Munchen', 'Kassel', 502], ['Numberg', 'Stuttgart', 183], ['Numberg', 'Wurzburg', 103], ['Numberg', 'Munchen', 167], ['Stuttgart', 'Numberg', 183], ['Augsburg', 'Munchen', 84], ['Augsburg', 'Karlsruhe', 250], ['Kassel', 'Munchen', 502], ['Kassel', 'Frankfurt', 173], ['Frankfurt', 'Mannheim', 85], ['Frankfurt', 'Wurzburg', 217], ['Frankfurt', 'Kassel', 173], ['Wurzburg', 'Numberg', 103], ['Wurzburg', 'Erfurt', 186], ['Wurzburg', 'Frankfurt', 217], ['Karlsruhe', 'Mannheim', 80], ['Karlsruhe', 'Augsburg', 250],["Mumbai", "Delhi",400], ["Delhi", "Kolkata",500],["Kolkata", "Bangalore",600],["TX", "NY",1200],["ALB", "NY",800]]
Теперь создам график:
g = nx.Graph()
for edge in edgelist:
g.add_edge(edge[0],edge[1], weight = edge[2])
Теперь мы хотим открыть для себя различные континенты и расположенные на них города с этого рисунка. Теперь мы можем сделать это, используя алгоритм связанных компонентов, например:
for i, x in enumerate(nx.connected_components(g)):
print("cc"+str(i)+":",x)
Результат:
cc0: {'Frankfurt', 'Kassel', 'Munchen', 'Numberg', 'Erfurt', 'Stuttgart', 'Karlsruhe', 'Wurzburg', 'Mannheim', 'Augsburg'}
cc1: {'Kolkata', 'Bangalore', 'Mumbai', 'Delhi'}
cc2: {'ALB', 'NY', 'TX'}
Таким образом, мы можем найти отдельные сетевые компоненты в наших данных, используя ребра и вершины. Этот алгоритм поиска на графе можно использовать для разных наборов данных, чтобы удовлетворить любой вариант использования, как указано выше.
Алгоритмы поиска на графе: кратчайший путь
Продолжая приведенный выше пример, нам дан график с городами Германии и соответствующими расстояниями между ними. Вы хотите знать, как добраться из Франкфурта (начальный пункт) в Мюнхен, преодолев кратчайшее расстояние.
Применение кратчайшего маршрута в графовых алгоритмах используется в Google Maps для поиска кратчайшего маршрута. Допустим, вы находитесь в магазине Walmart. У вас разные пути и расстояние между ними. Вы хотите предложить клиенту кратчайший маршрут между пунктом A и пунктом D.
print(nx.shortest_path(g, 'Stuttgart','Frankfurt',weight='weight')) print(nx.shortest_path_length(g, 'Stuttgart','Frankfurt',weight='weight'))
Результат:
['Stuttgart', 'Numberg', 'Wurzburg', 'Frankfurt']
503
Чтобы найти кратчайший путь между всеми парами, мы можем просто использовать цикл for:
for x in nx.all_pairs_dijkstra_path(g,weight='weight'):
print(x)
Результат:
('Mannheim', {'Mannheim': ['Mannheim'], 'Frankfurt': ['Mannheim', 'Frankfurt'], 'Karlsruhe': ['Mannheim', 'Karlsruhe'], 'Augsburg': ['Mannheim', 'Karlsruhe', 'Augsburg'], 'Kassel': ['Mannheim', 'Frankfurt', 'Kassel'], 'Wurzburg': ['Mannheim', 'Frankfurt', 'Wurzburg'], 'Munchen': ['Mannheim', 'Karlsruhe', 'Augsburg', 'Munchen'], 'Erfurt': ['Mannheim', 'Frankfurt', 'Wurzburg', 'Erfurt'], 'Numberg': ['Mannheim', 'Frankfurt', 'Wurzburg', 'Numberg'], 'Stuttgart': ['Mannheim', 'Frankfurt', 'Wurzburg', 'Numberg', 'Stuttgart']})
('Frankfurt', {'Frankfurt': ['Frankfurt'], 'Mannheim': ['Frankfurt', 'Mannheim'], 'Kassel': ['Frankfurt', 'Kassel'], 'Wurzburg': ['Frankfurt', 'Wurzburg'], 'Karlsruhe': ['Frankfurt', 'Mannheim', 'Karlsruhe'], 'Augsburg': ['Frankfurt', 'Mannheim', 'Karlsruhe', 'Augsburg'], 'Munchen': ['Frankfurt', 'Wurzburg', 'Numberg', 'Munchen'], 'Erfurt': ['Frankfurt', 'Wurzburg', 'Erfurt'], 'Numberg': ['Frankfurt', 'Wurzburg', 'Numberg'], 'Stuttgart': ['Frankfurt', 'Wurzburg', 'Numberg', 'Stuttgart']})
Графические алгоритмы: рейтинг страницы
Это – алгоритм сортировки страниц, который долгое время использовался в Google. Он присваивает баллы страницам в зависимости от количества и качества входящих и исходящих ссылок.
Pagerank можно использовать везде, где мы хотим оценить важность узлов в любой сети. Здесь я собираюсь использовать данные Facebook. У нас есть файл edge/link между пользователями Facebook. Давайте сначала создадим график FB, используя:
fb = nx.read_edgelist('facebook-combined.txt', create_using = nx.Graph(), nodetype = int)
Теперь давайте создадим график:
pos = nx.spring_layout(fb)
import warnings
warnings.filterwarnings('ignore')
plt.style.use('fivethirtyeight')
plt.rcParams['figure.figsize'] = (20, 15)
plt.axis('off')
nx.draw_networkx(fb, pos, with_labels = False, node_size = 35)
plt.show()
Алгоритмы поиска по графу: меры центральности
Существует множество показателей центральности, которые вы можете использовать в качестве функциональных возможностей для своих моделей машинного обучения. Я расскажу о двух из них:
- Центральное место между ними: важны не только пользователи, у которых больше всего друзей, важны также пользователи, которые связывают одну географию с другой, потому что это позволяет пользователям видеть контент из разных географических регионов. Центральность промежуточного звена определяет количество раз, когда конкретный узел находится на кратчайшем пути, выбранном между двумя другими узлами.
- Степень центральности: это просто количество подключений для узла.
Меры центральности можно использовать как функцию в моделях машинного обучения
pos = nx.spring_layout(subgraph_3437)
betweennessCentrality = nx.betweenness_centrality(subgraph_3437,normalized=True, endpoints=True)
node_size = [v * 10000 for v in betweennessCentrality.values()]
plt.figure(figsize=(20,20))
nx.draw_networkx(subgraph_3437, pos=pos, with_labels=False,
node_size=node_size )
plt.axis('off')
Здесь вы можете увидеть размеры узлов в зависимости от их центральных значений. Их можно рассматривать как информационных брокеров. Нарушение одного из узлов с высокой центральностью между ними разделит граф на несколько частей.
Надеюсь, вам понравилась эта статья о реализации графовых алгоритмов с помощью Python, которые вам нужно знать в машинном обучении.
