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

О сети гиперссылок

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

Данные

Данные загружаются из Социальная сеть SNAP: сеть гиперссылок Reddit.

Количество необходимых файлов = 3

  1. Сеть гиперссылок subreddit-to-subreddit, извлеченных из гиперссылок в теле сообщения. Скачайте здесь.
  2. Сеть гиперссылок subreddit-to-subreddit, извлеченных из гиперссылок в заголовке сообщения. Скачайте здесь.
  3. Встраивание векторов субреддитов (сообществ на Reddit). Скачайте здесь. Этот файл генерирует один числовой вектор в низкоразмерном пространстве (также известный как вложения) для каждого субреддита. Каждое вложение имеет 300 размеров. Два вложения субреддита похожи, если пользователи, которые публикуют в них, похожи.

Зависимости

  1. NetworkX
  2. NetworKit

Контур

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

Файлы * .csv, загруженные выше, должны храниться в ./input/ каталога вашего проекта.

Давайте быстро проверим каждый фрейм данных.

Выход:

Здесь мы можем видеть, что для каждого субреддита (в столбце = 0) нам предоставляется вложение длиной 300. Векторы генерируются из сети сообщений от пользователя к субреддиту с использованием целевой функции в стиле word2vec.

Мы хотели бы изменить имя столбца фрейма данных subreddits для нашего удобства.

Выход

Теперь о фрейме данных body.

Выход:

  • SOURCE_SUBREDDIT: субреддит, откуда берет начало ссылка.
  • TARGET_SUBREDDIT: субреддит, в котором заканчивается ссылка.
  • POST_ID: сообщение в исходном субреддите, с которого начинается ссылка.
  • TIMESTAMP: время публикации.
  • LINK_SENTIMENT: метка, указывающая, является ли исходное сообщение явно отрицательным по отношению к целевому сообщению. Значение -1, если источник отрицательный по отношению к цели, и 1, если он нейтральный или положительный.
  • POST_PROPERTIES: вектор, представляющий текстовые свойства исходного сообщения, перечисленный в виде списка чисел, разделенных запятыми. Все объекты подробно перечислены здесь.

Выход:

Столбцы и их значение такие же, как в теле для фрейма данных заголовок.

Сохранение словаря нормализованных вложений субреддита

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

Выход:

/usr/local/lib/python3.6/dist-packages/ipykernel_launcher.py:1: RuntimeWarning: invalid value encountered in true_divide   """Entry point for launching an IPython kernel.

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

Выход:

array([50601, 50662, 50739, 50779, 50842, 50961, 51020, 51035, 51106])

Давайте проверим эти индексы во фрейме данных subreddits.

Выход:

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

Удаление этих индексов также из temp_normalised_embeddings.

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

Сохранение словаря embeddings как ‘embeddings.pickle’

Создание текстового файла графика

Объединение фреймов данных title и body. Мы также удаляем столбцы POST_ID, TIMESTAMP, LINK_SENTIMENT, PROPERTIES из объединенного фрейм данных.

Выход:

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

Замена каждого значения в «SOURCE_SUBREDDIT» и «TARGET_SUBREDDIT» другим значением, полученным из mapper.

Давайте снова проверим комбинированные.

Выход:

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

Давайте проверим длину комбинированного фрейма данных.

Выход:

768835

Мы будем создавать наборы для обучения и тестирования и графики из комбинированного фрейма данных. Если для этой цели мы будем использовать полный комбинированный фрейм данных, то создание этих наборов будет очень затратным с точки зрения вычислений. По этой причине мы возьмем только 30% объединенного фрейма данных и создадим необходимые наборы из этих 30% данных.

Мы сохраним информацию в объединенном в файле graph.txt.

2. Создание графиков проверки, теста и обучения, а также тестирования и обучающих наборов .

Чтение данных графика

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

Создание графика проверки

Из этого графика проверки мы извлечем графики test и train. Это будет сделано через NetworKit.

test_it - это подграф valid_it, содержащий случайные 90% ребер valid_it. train_it - это подграф test_it, содержащий случайные 70% ребер test_it.

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

Создание ярлыков для тестирования и обучающего набора.

Объединение этикеток с образцами

Выход:

В столбцах узлов каждая строка состоит из кортежа. первый элемент кортежа - это исходный субреддит, а второй элемент - целевой субреддит. Теперь разделим столбец узлы на два столбца: src и tar.

Наконец, просто переставляем столбцы в train и test

Наконец, давайте сбросим эти объекты на диск, чтобы потом их можно было использовать.

3. Создание функций на основе графических изображений и вложений субреддита.

Давайте посмотрим на фреймы данных train и test.

Давайте посмотрим на распределение классов в столбце label как в test, так и в train.

Сначала тест

Выход:

0    1772223 
1        578 
Name: label, dtype: int64

Затем на поезд

Выход:

0    1347041 
1       1908 
Name: label, dtype: int64

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

Несбалансированность классов может быть серьезным осложняющим фактором в проблемах классификации. Мы рассмотрим эту проблему в следующем разделе.

А пока создадим train_dict и test_dict как словарный эквивалент train и test соответственно.

РАЗРАБОТКА ФУНКЦИЙ

Функция 1: Косинусное сходство между вложениями субреддита.

Каждое вложение - это вектор размером 300 d с действительным знаком, который генерируется из сети отправки сообщений от пользователя к субреддиту с использованием целевой функции в стиле word2vec.

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

Сначала тест

Затем для поезда

Следующий набор функций основан на работе, проделанной Дарио Гарсия-Гасулла и Улисес Кортес. [1]

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

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

Учитывая элемент x, мы называем элементы, которые обобщают x предков элемента x, , т. е. A (x), а элементы, которые специализируются на x, являются потомками от x, то есть D (x).

A (x): набор узлов, которые являются конечными точками ребер, происходящих из x
D (x): набор узлов, которые являются исходными ребрами, которые оканчивается на x.

Терминология на секунду может показаться запутанной! Но давайте примем это за чистую монету и создадим из них метрики. Эти метрики в конечном итоге дадут нам функции.

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

Формула для расчета метрики DED:

Метрика дает нам вероятность ребра x → y. Это процесс нисходящий для оценки вероятности возникновения края.

Метрика 2: Индуктивная метрика (IND)
Она следует индуктивному рассуждению и поддерживается специализациями узла: Если большинство публикаций автора сложны, то весьма вероятно, что сам автор - искушенный человек.

Формула для вычисления показателя IND:

Метрика дает нам вероятность ребра x → y. Это процесс снизу вверх для оценки вероятности возникновения края.

Согласно двум критериям, определенным выше (DED и IND), вероятность преимущества определяется пропорцией удовлетворительных доказательств (сколько из всех моих обобщений / специализации имеют это преимущество).

Однако пропорция может быть не лучшим показателем значимости в определенных областях. Абсолютное количество доказательств может быть решающим фактором надежности. Рассмотрим следующий пример:

Оранжевая направленная линия - это край, который следует классифицировать как метку 0/1.
На следующем рисунке A (x) ₁ является единственным предком узла x, а также подключен к узлу y. Это дает нам показатель DED, равный 1.

Здесь множество A (x) состоит из 100 узлов, из которых 99 (исключая A (x) ₄₇) подключены к узлу x. Это даст показатель DED, равный 0,99.

Во многих доменах ребро z → y кажется более надежным, чем ребро x → y из-за абсолютного количества свидетельств (100 против 1 ), хотя у него менее пропорциональные доказательства (99% против 100%). Учитывая модификацию DED и IND, в которой учитывается количество удовлетворяющих требованиям предков и потомков, а не только их соотношение.

Показатель 3: DED_LOG

Показатель 4: IND_LOG

Теперь, исходя из этих 4 показателей, мы будем определять характеристики следующим образом.

Функция 2: рейтинг INF

Объедините DED и IND в одну оценку. Это объединяет свидетельства, предоставленные как предками, так и потомками вершины, чтобы определить вероятность существования ребер, происходящих из этой вершины.

Функция 3: Оценка INF_2D

Авторы [1] заметили, что оценка DED обычно достигает более высокой точности, чем IND. Комбинация DED и IND превосходит только DED. Они изменили INF на INF_2D, где оценка DED дается в два раза больше, чем оценка IND.

Характеристика 4: Оценка INF_2I

Мы также создаем INF_2I, где оценка IND дается в два раза больше, чем оценка DED.

Функция 5: INF_LOG Score

Модификация INF, в которой учитывается количество удовлетворяющих предков и потомков, а не только их соотношение.

Функция 6: Оценка INF_LOG_2D

Объединение INF_LOG и INF_2D для создания INF_LOG_2D, которое решает проблемы 1) пропорции удовлетворительных предков / потомков 2) низкая точность в нормальном балле INF.

Функция 7: Оценка INF_LOG_2I

Мы также создаем INF_LOG_2I, где баллу IND_LOG присваивается удвоенный вес балла DED _LOG.

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

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

Между двумя узлами A и B узел с большим числом входящих ребер (скажем, A) считается более конкретным, чем другой узел. (B); в то время как B считается более абстрактным, чем A.

Авторы [1] предложили иерархическую версию тройки алгоритмов предсказания неориентированных ссылок CN, AA и RA. Они рассматривают только отношения, идущие от данной вершины к тем, которые более абстрактны, чем она сама. То есть найти обычное сходство для ребра x → y тогда и только тогда, когда узел x более конкретен, чем узел y . Если условие не выполняется, установите схожесть для края на 0.

Я расширил список алгоритмов неориентированного предсказания ссылок. Я нашел их в обзоре [2].

Прежде всего, мы конвертируем оба направленных графика (train_graph и test_graph) в их неориентированный эквивалент.

Функция 8: Общие соседи
Сходство между двумя узлами определяется как количество общих соседей между обоими узлами.

Функция 9: индекс распределения ресурсов
На основе процесса распределения ресурсов, который имеет место в сложных сетях.

Функция 10: Коэффициент Жаккара
Он измеряет соотношение общих соседей в полном наборе соседей для двух узлов. Эта функция подобия определяется как

Функция 11: Индекс Адама Адара

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

Функция 12: предпочтительное прикрепление
Основано на наблюдении, что вероятность образования связи между двумя узлами увеличивается с степенью этих узлов. делает

Функция 13: Распределение ресурсов на основе взаимодействий общих соседей (RA-CNI)
На основе процесса выделения ресурсов, когда каждый узел отправляет единицу ресурса своим соседям.

Функция 14: индекс Солтона
Индекс Солтона дает значение, примерно в два раза превышающее индекс Жаккара.

Функция 15: Индекс Соренсена (SO)
Несмотря на сходство с индексом Жаккара, он менее чувствителен к выбросам.

Функция 16. Индекс продвигаемого концентратора (HPI)
Основная цель этого показателя сходства - избежать образования связи между узлами концентратора и способствовать формированию связи между узлами низкого уровня и концентраторами.

Характеристика 17: Индекс пониженного содержания концентратора (HDI)
Индекс пониженного значения концентратора способствует формированию связи между концентраторами и между низко- узлы степени, но не между концентраторами и узлами низкого уровня.

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