Graph Analytics - это будущее
Специалисты по данным вполне комфортно работают с Pandas, SQL или любой другой реляционной базой данных. Мы привыкли видеть наших пользователей в строках, а их атрибуты - в виде столбцов. Но действительно ли реальный мир так себя ведет?
В связанном мире пользователей нельзя рассматривать как независимые сущности, поскольку у них есть определенные отношения друг с другом. Иногда мы хотели бы включить такие отношения при построении наших моделей машинного обучения.
В то время как в реляционной базе данных мы не можем использовать такие отношения между разными строками (пользователями), в графической базе данных это сделать довольно тривиально.
Здесь я собираюсь поговорить о некоторых из наиболее важных алгоритмов графов, которые вам следует знать, и о том, как их реализовать с помощью Python.
1. Подключенные компоненты
С точки зрения непрофессионала вы можете рассматривать подключенные компоненты как своего рода алгоритм жесткой кластеризации, который находит кластеры в связанных / связанных данных.
В качестве конкретного примера: Предположим, у вас есть данные о дорогах, соединяющих любые два города мира. Вам нужно узнать все континенты мира и города, в которых они находятся.
Как вы этого добьетесь? Давай, подумай над этим.
Алгоритм связных компонентов основан на частном случае BFS / DFS. Я не буду здесь много говорить о том, как это работает, но мы увидим, как запустить и запустить код с помощью Networkx.
Приложения
Предположим, у нас много клиентов, использующих множество учетных записей. Один из способов использования алгоритма связанных компонентов - это обнаружение различных семейств в нашем наборе данных.
Мы можем предположить границы (дороги) между идентификаторами клиентов на основе использования одной и той же кредитной карты, одного адреса и т. Д. После того, как у нас будут эти соединения, мы можем запустить алгоритм связанного компонента на том же самом, чтобы создать отдельные кластеры, которым мы затем можем назначить семейный идентификатор.
Затем мы можем использовать эти семейные идентификаторы, чтобы предоставлять персональные рекомендации, основанные на семейных потребностях. Мы можем использовать этот идентификатор семейства, чтобы подпитывать наши алгоритмы классификации, создавая сгруппированные объекты на основе семейства.
Другое приложение может быть из финансовой точки зрения, где мы можем фиксировать мошенничество, используя эти семейные идентификаторы.
Код
Мы будем использовать модуль Networkx в Python для создания и анализа наших графиков. Начнем с создания списка ребер вместе с расстояниями, которые мы добавим как вес ребра:
Давайте создадим график, используя Networkx:
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'}
2. Кратчайший путь
Продолжая приведенный выше пример, нам дается график с городами Германии и соответствующими расстояниями между ними.
Алгоритм, который мы используем для решения этой задачи, называется Дейкстры. Алгоритм Дейкстры (в терминах непрофессионала) можно объяснить как: - алгоритм для поиска кратчайших путей между узлами в графе, которые могут представлять, например, дорожные сети.
Приложения
- Варианты алгоритма Дейкстры широко используются в Google Maps для поиска кратчайших маршрутов.
- Вы видели, как LinkedIn выявляет связи 1-й степени и связи 2-й степени. Что происходит за кадром?
Код
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 x in nx.all_pairs_dijkstra_path(g,weight='weight'):
print(x)
3. Минимальное связующее дерево
У нас другая проблема. Предположим, мы работаем в компании по прокладке водопроводных труб или в компании, занимающейся оптоволоконным Интернетом. Мы хотим соединить все города на графике с использованием минимального количества проводов / труб. Как мы это делаем?
Приложения
- Минимальные остовные деревья имеют прямое применение при проектировании сетей, включая компьютерные сети, транспортные сети, сети водоснабжения и электрические сети (для которых они были впервые изобретены).
- MST используется для аппроксимации задачи коммивояжера.
- Сегментация изображений: - она использовалась для сегментации изображений, когда мы сначала строим MST на графике, где пиксели являются узлами, а расстояния между пикселями основаны на некоторой мере сходства (цвет, интенсивность и т. Д.).
Код
# nx.minimum_spanning_tree(g) returns a instance of type graph nx.draw_networkx(nx.minimum_spanning_tree(g))
Это нарисует или создаст MST для нашего графика.
4. Меры центральности
Существует множество критериев централизации, которые вы можете использовать в качестве функций своих моделей машинного обучения. Я расскажу о двух из них.
Централизованность посредничества: важны не только пользователи, у которых больше всего друзей, важны также пользователи, связывающие одну географию с другой, поскольку это позволяет пользователям видеть контент из разных географических регионов. Центральность по промежуточности количественно определяет, сколько раз конкретный узел проходит по кратчайшему выбранному пути между двумя другими узлами.
Степень центральности - это просто количество подключений для узла.
Приложения
Меры центральности можно использовать как функцию в любой модели машинного обучения.
Код
Вот код для определения центральности между подграфом.
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')
Здесь вы можете увидеть размеры узлов по их промежуточным значениям центральности. Их можно рассматривать как распространителей информации.
Вывод
В этом посте я рассказал о некоторых из наиболее влиятельных алгоритмов графов, которые изменили наш образ жизни.
С появлением такого большого количества социальных данных сетевой анализ может очень помочь в улучшении наших моделей и создании ценности.
Существует множество графических алгоритмов, но они мне нравятся больше всего. В этом посте я просто хотел получить необходимую ширину в этой области.
Спасибо за прочтение.
