Обзор

  • Введение в прогнозирование ссылок, как это работает и где вы можете использовать его в реальном мире.
  • Узнайте о важности прогнозирования ссылок в социальных сетях
  • Создайте свою первую модель прогнозирования ссылок для сценария использования Facebook с помощью Python

Введение

Вы когда-нибудь задумывались, кто будет вашим следующим участником Facebook? Любопытно, от кого может исходить следующий запрос?

Что, если бы я сказал вам, что есть способ это предсказать?

Мне нравится проводить мозговой штурм и придумывать эти постановки задач, когда я просматриваю свою учетную запись Facebook. Это одно из преимуществ мышления специалиста по данным!

Большинство платформ социальных сетей, включая Facebook, можно структурировать в виде графиков. Зарегистрированные пользователи связаны между собой во вселенной сетей. И для работы с этими сетями и графами нам нужен другой набор подходов, инструментов и алгоритмов (вместо традиционных методов машинного обучения).

Итак, в этой статье мы решим проблему социальной сети с помощью графиков и машинного обучения. Сначала мы разберемся с основными концепциями и компонентами прогнозирования ссылок, прежде чем приступить к тематическому исследованию Facebook и реализовать его на Python!

Я рекомендую просмотреть следующие статьи, чтобы понять, что такое графики и как они работают:

Оглавление

  1. Обзор аналитики социальных сетей
  2. Учебник по прогнозированию ссылок
  3. Стратегия решения проблемы прогнозирования ссылок
  4. Пример использования: прогнозирование будущих соединений между страницами Facebook
    - понимание данных
    - построение модели подготовки набора данных
    - извлечение функций
    - построение модели: модель прогнозирования ссылок

Обзор аналитики социальных сетей

Давайте сначала определим социальную сеть, прежде чем мы углубимся в концепцию прогнозирования ссылок.

Социальная сеть - это, по сути, представление отношений между социальными объектами, такими как люди, организации, правительства, политические партии и т. Д.

Взаимодействие между этими сущностями генерирует невообразимые объемы данных в виде сообщений, сообщений чата, твитов, лайков, комментариев, репостов и т. Д. Это открывает окно возможностей и вариантов использования, над которыми мы можем работать.

Это подводит нас к Аналитике социальных сетей (SNA). Мы можем определить это как комбинацию нескольких действий, которые выполняются в социальных сетях. Эти действия включают сбор данных с сайтов социальных сетей в Интернете и использование этих данных для принятия деловых решений.

Преимущества аналитики социальных сетей могут быть очень полезными. Вот несколько ключевых преимуществ:

  • Помогает лучше понять свою аудиторию
  • Используется для сегментации клиентов
  • Используется для разработки систем рекомендаций
  • Среди прочего обнаруживать фейковые новости

Учебник по прогнозированию ссылок

Предсказание ссылок - одна из важнейших тем исследований в области графов и сетей. Цель прогнозирования ссылок - выявить пары узлов, которые либо будут формировать ссылку, либо нет в будущем.

Прогнозирование ссылок широко используется в реальных приложениях. Вот некоторые из важных случаев использования предсказания ссылок:

  • Предскажите, какие клиенты, вероятно, купят какие товары на онлайн-рынках, таких как Amazon. Это может помочь в составлении лучших рекомендаций по продукту
  • Предложите взаимодействие или сотрудничество между сотрудниками в организации
  • Извлекайте важную информацию из террористических сетей

В этой статье мы рассмотрим несколько иной вариант использования предсказания ссылок - предсказание ссылок в социальной сети!

Стратегия решения проблемы прогнозирования ссылок

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

Давайте возьмем фиктивный график, чтобы понять эту идею. Ниже приведен 7-узловой граф, а несвязанные пары узлов - это AF, BD, BE, BG и EG:

Теперь предположим, что мы проанализировали данные и получили график ниже. Сформировано несколько новых подключений (ссылки выделены красным):

Нам нужен набор переменных-предикторов и целевая переменная для построения любой модели машинного обучения, верно? Так где же эти переменные? Что ж, мы можем получить это из самого графика! Посмотрим, как это делается.

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

  1. A-F
  2. B-D
  3. B-E
  4. B-G
  5. E-G

Обратите внимание, что для удобства я рассмотрел только те узлы, которые находятся на расстоянии пары ссылок.

Следующим шагом для нас является создание функций для каждой пары узлов. Хорошая новость заключается в том, что существует несколько методов извлечения функций из узлов сети. Допустим, мы используем один из этих методов и создаем функции для каждой из этих пар. Однако мы до сих пор не знаем, что такое целевая переменная. Не о чем беспокоиться - мы легко можем получить и это.

Посмотрите на график в момент времени t + n. Мы видим, что в сети появилось три новых звена для пар A-F, B-D и BE соответственно. Следовательно, мы присвоим каждому из них значение 1. Пары узлов B-G и E-G будут присвоены 0, потому что все еще нет связей между узлами.

Следовательно, данные будут выглядеть так:

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

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

Извлечение данных из графика для построения вашей модели

В приведенном выше разделе мы смогли получить метки для целевой переменной, потому что у нас был доступ к графику в момент времени t + n. Однако в реальных сценариях у нас будет только один набор графических данных. Вот и все!

Допустим, у нас есть приведенный ниже график социальной сети, где узлами являются пользователи, а ребра представляют собой какие-то отношения:

Пары узлов-кандидатов, которые могут сформировать ссылку в будущем: (1 и 2), (2 и 4), (5 и 6) , (8 и 10) и так далее. Мы должны построить модель, которая предсказывает, будет ли связь между этими парами узлов или нет. Вот в чем суть предсказания ссылок!

Однако для построения модели прогнозирования ссылок нам необходимо подготовить обучающий набор данных из этого графика. Сделать это можно с помощью несложной уловки.

Представьте себе это - как бы этот график выглядел в какой-то момент в прошлом? Между узлами будет меньше ребер, потому что со временем связи в социальной сети налаживаются постепенно.

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

Удалите ссылки из графика

При удалении ссылок или ребер мы должны избегать удаления любого ребра, которое может создать изолированный узел (узел без ребра) или изолированную сеть. Давайте уберем некоторые ребра из нашей сети:

Как видите, ребра в парах узлов (1 и 4), (7 и 9) и (3 и 8) были удалены.

Добавить ярлыки к извлеченным данным

Затем нам нужно будет создать функции для всех неподключенных пар узлов, включая те, для которых мы пропустили края. Удаленные ребра будут помечены как «1», а неподключенные пары узлов - как «0».

Целевая переменная в этом наборе данных будет сильно несбалансированной. Это то, с чем вы также столкнетесь в реальных графиках. Количество неподключенных пар узлов будет огромным.

Давайте рассмотрим пример и решим проблему предсказания ссылок с помощью Python.

Пример использования: прогнозирование будущих подключений между страницами Facebook

Здесь мы применим все вышеперечисленное в потрясающем реальном сценарии.

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

Вы можете скачать набор данных здесь.

Цель: создать модель прогнозирования ссылок для прогнозирования будущих связей (взаимных лайков) между неподключенными узлами (страницами Facebook).

Давайте запустим наш Jupyter Notebook (или Colab)!

Понимание данных

Сначала мы импортируем все необходимые библиотеки и модули:

Давайте загрузим страницы Facebook как узлы и взаимные лайки между страницами как края:

Вывод: (620, 2102)

У нас 620 узлов и 2102 ссылки. Теперь давайте создадим фрейм данных всех узлов. Каждая строка этого фрейма данных представляет собой ссылку, образованную узлами в столбцах «node_1» и «node_2» соответственно:

fb_df.head()

Узлы «276», «58», «132», «603» и «398» образуют связи с узлом «0». Мы можем легко представить это расположение страниц Facebook в виде графика:

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

Подготовка набора данных для построения модели

Нам нужно подготовить набор данных из неориентированного графа. Этот набор данных будет иметь особенности пар узлов, а целевая переменная будет двоичной по своей природе, что указывает на наличие ссылок (или отсутствие).

Получение пар неподключенных узлов - отрицательные образцы

Мы уже поняли, что для решения задачи прогнозирования ссылок мы должны подготовить набор данных из заданного графа. Основная часть этого набора данных - это отрицательные выборки или пары неподключенных узлов. В этом разделе я покажу вам, как мы можем извлечь несвязанные пары узлов из графа.

Сначала мы создадим матрицу смежности, чтобы определить, какие пары узлов не связаны.

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

Ссылки обозначаются значениями в матрице. 1 означает, что существует связь между парой узлов, а 0 означает, что существует связь между парой узлов. Например, узлы 1 и 3 имеют 0 на их перекрестке в матрице, и эти узлы также не имеют ребер на графе выше.

Мы будем использовать это свойство матрицы смежности, чтобы найти все несвязанные пары узлов из исходного графа G:

Давайте посмотрим на форму матрицы смежности:

adj_G.shape

Вывод: (620, 620)

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

Мы можем искать значения выше диагонали (зеленая часть) или значения ниже (красная часть). Давайте найдем по диагонали ноль:

Вот сколько пар неподключенных узлов у нас в наборе данных:

len(all_unconnected_pairs)

Вывод: 19018

У нас 19 018 неподключенных пар. Эти пары узлов будут действовать как отрицательные образцы во время обучения модели прогнозирования ссылок. Давайте сохраним эти пары во фрейме данных:

Удаление ссылок из пар подключенных узлов - положительные образцы

Как мы обсуждали выше, мы случайным образом отбросим некоторые ребра из графа. Однако случайное удаление ребер может привести к отсечению слабо связанных узлов и фрагментов графа. Это то, о чем мы должны позаботиться. Мы должны убедиться, что в процессе отбрасывания ребер все узлы графа должны оставаться соединенными.

В блоке кода ниже мы сначала проверим, приводит ли удаление пары узлов к разделению графа (number_connected_components ›1) или уменьшению количества узлов. Если и то и другое не происходит, мы отбрасываем эту пару узлов и повторяем тот же процесс со следующей парой узлов.

В конце концов, мы получим список пар узлов, которые можно удалить с графа, и все узлы останутся нетронутыми:

len(omissible_links_index)

Вывод: 1483

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

Данные для обучения моделей

Затем мы добавим эти съемные ребра к фрейму данных неподключенных пар узлов. Поскольку эти новые ребра являются положительными выборками, они будут иметь целевое значение «1»:

Проверим распределение значений целевой переменной:

data['link'].value_counts()

0 -19018
1 -1483

Оказывается, это сильно несбалансированные данные. Соотношение ссылок и отсутствия ссылок близко к 8%. В следующем разделе мы извлечем особенности для всех этих пар узлов.

Извлечение функций

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

Затем мы установим библиотеку node2vec. Он очень похож на алгоритм DeepWalk. Однако это предполагает предвзятые случайные блуждания. Чтобы узнать больше о node2vec, вам обязательно стоит прочитать этот документ node2vec: изучение масштабируемых функций для сетей.

Пока просто имейте в виду, что node2vec используется для векторного представления узлов графа. Установим:

!pip install node2vec

Установка на локальном компьютере может занять некоторое время (это довольно быстро, если вы используете Colab).

Теперь мы обучим модель node2vec на нашем графике (G_data):

Затем мы применим обученную модель node2vec к каждой паре узлов в dataframe фрейма данных. Чтобы вычислить характеристики пары или ребра, мы сложим характеристики узлов в этой паре:

x = [(n2w_model[str(i)]+n2w_model[str(j)]) for i,j in  
      zip(data['node_1'], data['node_2'])]

Построение нашей модели прогнозирования ссылок

Чтобы проверить производительность нашей модели, мы должны разделить наши данные на две части - одну для обучения модели, а другую - для проверки производительности модели:

Давайте сначала подберем модель логистической регрессии:

Теперь сделаем прогнозы на тестовой выборке:

predictions = lr.predict_proba(xtest)

Мы будем использовать показатель AUC-ROC, чтобы проверить производительность нашей модели.

roc_auc_score(ytest, predictions[:,1])

Вывод: 0,7817

Мы получили оценку 0,78 с использованием модели логистической регрессии. Посмотрим, сможем ли мы получить лучший результат, используя более сложную модель.

Обучение остановилось после 208-й итерации, потому что мы применили критерий ранней остановки. Самое главное, модель получила впечатляющую оценку AUC 0,9273 на тестовом наборе. Я рекомендую вам взглянуть на документацию по lightGBM, чтобы узнать больше о различных параметрах.

Конечные заметки

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

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

Пожалуйста, не стесняйтесь задавать любые вопросы или оставлять отзывы в разделе комментариев ниже. Продолжайте исследовать!

Первоначально опубликовано на https://www.analyticsvidhya.com 16 января 2020 г.