BI Consult
  • Перейти на QlikSense
  • Перейти на QlikView
  • Перейти на Tableau
  • Перейти на Power BI
  • российские bi dwh dl
  • Главная
  • Продукты Business-Qlik
    • Дистрибуция
    • Розничная торговля
    • Производство
    • Операторы связи
    • Страхование
    • Банки
    • Лизинг
    • Логистика
    • Нефтегазовый сектор
    • Медицина
    • Сеть ресторанов
    • Энергетика
    • Фрод-менеджмент
    • E-Commerce
    • Фармацевтика
    • Построение хранилища данных
    • Создание Data Lake
    • Цифровая трансформация
    • Управление по KPI
    • Финансы
    • Продажи
    • Склад
    • HR
    • Маркетинг
    • Внутренний аудит
    • Категорийный менеджмент
    • S&OP и прогнозная аналитика
    • Геоаналитика
    • Цепочки поставок (SCM)
    • Process Mining
    • Сквозная аналитика
  • Платформы
    • Qlik Sense
    • QlikView
    • Tableau
    • Microsoft Power BI
    • Геоаналитика Qlik GeoAnalytics
    • Qlik NPrinting - рассылка отчетности QlikView/Qlik Sense
    • KliqPlanning Suite - бюджетирование в QlikView
    • ATK BiView-1C Коннектор (для Qlik/Tableau/PowerBI)
    • QlikView/Qlik Sense SAP Коннектор
    • QlikView R-Коннектор
    • Qlik Web Connectors - коннектор Google, Facebook, Twitter
    • Vizlib Qlik Sense extentions (библиотека экстеншнов)
    • Библиотека extention для Qlik
    • Qlik Alerting
    • Qlik Data Integration Platform - создание Data Lake
    • Qlik Data Catalog решение для Data Governance
    • ATK BiView документация
  • Услуги
    • Консалтинг
    • Пилотный проект
    • План обучения и сертификации
    • Подготовка специалистов по Qlik
    • Бесплатное обучение Qlik
    • Сертификация Qlik
    • Поддержка
    • Технические задания
    • Сбор требований для проекта внедрения BI-системы
    • Аудит приложений Qlik и Tableau
    • Разработка BI Стратегии
    • Styleguide для BI-системы
    • Как выбрать BI-систему
  • Курсы
    • Учебный курс по Qlik Sense
    • Учебный курс по Tableau
    • Учебный курс по Microsoft Power BI
    • Учебный курс Информационная грамотность (Data Literacy)
    • Учебный курс Современная архитектура хранилища данных
    • Учебный курс для бизнес-аналитиков
    • Учебный курс по NPrinting
    • Учебный курс по BigQuery
    • Учебный курс по Azure Databricks
    • Учебный курс по DWH
    • Учебный курс по Data Governance
    • Учебный курс по Data Science (ML, AI)
    • Учебный курс администратора Qlik Sense
  • Компания
    • Руководство
    • Новости
    • Клиенты
    • Карьера
    • Скачать
    • Контакты

QlikView / Qlik Sense

  • Qlik Sense
    • Возможности Qlik Sense
    • Qlik Sense Enterprise
    • Qlik Sense Desktop
    • Qlik Sense Saas облачная инфраструктура для компаний
    • Источники данных и хранение данных
    • Безопасность и разграничение прав доступа
    • Масштабируемость
    • Политика лицензирования Qlik Sense
    • Qlik Sense November 2021: новые возможности
    • Географические карты в Qlik Sense
    • Qlik Sense Cloud / Qlik Sense в облаке
    • Учебное пособие по Qlik Sense
  • QlikView
    • Архитектура
    • Отличия QlikView от традиционных BI-систем
    • Политика лицензирования QlikView
    • Системные требования и сайзинг
    • Отличие от OLAP-систем
    • QlikView on Mobile
    • Qlik и Big Data
    • Демонстрационные примеры
    • QlikView в "облаке" (Amazon) / QlikView in the cloud
    • Интеграция QlikView с Microsoft SharePoint
    • Учебное пособие по QlikView
    • Что такое QlikView Publisher
    • QlikView Extranet Server и дистрибуция отчетности внешним пользователям
  • Qlik Data Catalog
  • Qlik Alerting
  • Qlik Data Integration Platform
  • Add-ons для QlikView
    • Vizlib Qlik Sense extentions (библиотека экстеншнов)
    • QlikView/Qlik Sense ATK BiView-1C Коннектор
    • Документация ATK BiView
    • Qlik NPrinting
    • Геоаналитика Qlik GeoAnalytics
    • GeoQlik
    • KliqPlanning Suite
    • QlikView/Qlik Sense SAP Коннектор
    • QlikView R-Коннектор
    • Qlik Web Connectors
    • QlikView Cognos TM1 Коннектор
    • Визуализация графов в Qlik Sense с помощью Ogma / Linkurious
  • Учебный курс по Qlik Sense

Tableau

  • Tableau
    • Tableau Desktop
    • Tableau Server
    • Tableau Prep
    • Технологии
    • Источники данных Tableau
    • Безопасность в Tableau
    • Политика лицензирования
    • Tableau 2021: новые возможности
    • Сравнение продуктов Tableau (Desktop, Server, Online, Public)
    • Демонстрационные примеры
    • Учебный портал Tableau
    • Коробочное решение "Мониторинг Tableau Server"
    • Чем отличаются Tableau Reader и Viewer?
  • Учебный курс по Tableau

Другое

  • Microsoft Power BI
    • Power BI Desktop
    • Power BI Report Server
    • Отраслевые решения Microsoft Power BI
    • Политика лицензирования Microsoft Power BI
    • Power BI Mobile
    • Учебные курсы Microsoft Power BI
    • Архитектура Power BI
    • Обработка данных в Power BI
    • Аудит системы Power BI
  • Учебный курс по Microsoft Power BI
  • Alteryx
    • Alteryx Designer
    • Инструменты Alteryx Designer
    • Alteryx Server
    • Alteryx Analytics Gallery
    • Alteryx. Создание приложения, workflow, ETL
  • Data Engeneering
    • Создание Data Lake
    • Создание Data Warehouse
    • Учебный курс "Современная архитектура хранилища данных"
Главная » Курсы » Учебный курс по Data Science (ML, AI)

Алгоритмы поиска на графах с 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, которые вам нужно знать в машинном обучении.

 

Узнать стоимость решенияЗапросить видео презентацию

Запросить видео презентацию Запросить доступ к демо стенду online Узнать стоимость лицензий

Задать вопрос

loading...

Решения

Анализировать ФинансыУвеличивайте ПродажиОптимальный Склад и ЛогистикаМаркетинговые Метрики

Клиенты

  • Решение в области планирования, бюджетирования, план-фактного анализа продаж. Хранилище данных QlikSense;

  • ЮЕ-Интернейшнл

    Анализ активности клиентов; реализация корпоративной отчетности; сегментация клиентской базы; моделирование маркетинговых акций; план-фактный анализ.

  • Adriver

    Группа компаний Internest работает на рынке интернет-рекламы с 1997 года.

    Основное направление деятельности - создание технологических и бизнес-решений в области интернет-маркетинга.  

  • Concept Club
    Детализированный план-фактный анализ продаж и прибыли в разрезах магазинов/регионов/брендов/номенклатурных групп/коллекций/SKU с детализацией до дня
    Сравнительный Like-for-like анализ продаж по показателям товарооборот, прибыль, средний чек, проходимость, конверсия и т.д. в разрезах (Факт/Факт и План/Факт)
    Факторный анализ продаж, расходов, себестоимости, маржинальности
    Отчет по контролю корректности расчетов по поконтрольным значениям
    Построение трендов продаж для оценки адекватности планирования
    Отчет P&L консолидированный и по регионам/бизнес-юнитам/брендам/юр.лицам
    Прогноз P&L на текущий месяц с индикацией по контрольным значениям с возможносью создания версий и внесения корректировок 
    Отчет "Cash-Flow" консолидированный и по юр.лицам
    Отчет "Баланс" консолидированный и по юр.лицам
    Совмещенное товарное планирование ("пилы/кривулины"): реализация интерактивной модели товародвижения в разрезах, анализ жизненного цикла товаров, планирование уценок (скрытых/открытых)
    Совмещенный анализ оборачиваемости и среднего товарного запаса в разрезах.
  • Решения
    • Дистрибуция
    • Розничная торговля
    • Производство
    • Операторы связи
    • Банки
    • Страхование
    • Фармацевтика
    • Лизинг
    • Логистика
    • Медицина
    • Нефтегазовый сектор
    • Сеть ресторанов
  • Продукты
    • Qlik Sense
    • QlikView
    • Tableau
    • Microsoft Power BI
    • ATK BiView-1C Коннектор (для Qlik/Tableau/PowerBI)
    • Vizlib Qlik Sense extentions (библиотека экстеншнов)
    • NPrinting
    • Геоаналитика Qlik GeoAnalytics
    • KliqPlanning Suite
    • Qlik WebConnectors
    • QlikView R Коннектор
    • QlikView/Qlik Sense SAP Коннектор
    • Alteryx
    • Qlik Data Catalog
    • Документация ATK BiView
  • Услуги
    • Консалтинг
    • Пилотный проект
    • Поддержка
    • План обучения и сертификации Qlik
    • Бесплатное обучение
    • Учебные курсы
    • Сертификация Qlik
    • Аудит приложений
  • Курсы
    • Учебный курс по Qlik Sense
    • Учебный курс по Tableau
    • Учебный курс по Microsoft Power BI
    • Учебный курс Современная архитектура хранилища данных
    • Учебный курс Информационная грамотность
    • Учебный курс для бизнес-аналитиков
    • Учебный курс по NPrinting
    • Учебный курс по Azure Databricks
    • Учебный курс по Google BigQuery
  • Компания
    • О нас
    • Руководство
    • Новости
    • Клиенты
    • Скачать
    • Контакты
  • Функциональные решения
    • Продажи
    • Финансы
    • Склад
    • HR
    • S&OP и прогнозная аналитика
    • Внутренний аудит
    • Геоаналитика
    • Категорийный менеджмент
    • Построение хранилища данных
    • Система управления KPI и BSC
    • Управление цепочками поставок
    • Маркетинг
    • Цифровая трансформация
    • Сквозная аналитика
    • Process Mining
QlikView Partner
LinkedInYouTubeVkontakteFacebook
ООО "Би Ай Консалт",
ИНН: 7811437757,
ОГРН: 1097847154184
199178, Россия,
Санкт-Петербург,
6-ая линия В.О., Д. 63, 4 этаж
Тел: +7 (812) 334-08-01
Тел: +7 (499) 608-13-06
E-mail: info@biconsult.ru