Мы уже знаем, что машинное обучение - удивительная область, и существует большое количество методов для решения проблем. К сожалению, лишь несколько подмножеств алгоритмов очень популярны и широко используются в соревнованиях Kaggle. Но, поскольку мир огромен, существует множество мощных и мало используемых алгоритмов / методов.

В этой статье мы покажем простое применение алгоритма тензорной декомпозиции (TD) к данным графа. Более подробно мы покажем, как применить TF для анализа графиков изменения времени. Цель этого анализа - извлечь скрытую информацию из графиков, чтобы найти скрытую информацию.

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

Тензорная факторизация

Начнем с простого определения тензора. В этой статье мы будем использовать различные определения, взятые из известной статьи о тензорном разложении: Kolda et. др., Тензорные декомпозиции и приложения, SIAM Review, 2009, Vol. 51 (3): стр. 455–500.

Тензор - это многомерный массив. Более формально, тензор N-го порядка или N-го порядка является элементом тензорного произведения N векторных пространств,
каждое из которых имеет свою собственную систему координат. Тензор третьего порядка имеет три индекса, как показано на рисунке 1. Тензор первого порядка - это вектор, тензор второго порядка - это матрица, а тензоры третьего порядка и выше называются тензорами более высокого порядка. (Колда и др., Тензорные разложения и приложения)

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

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

Один из наиболее важных моментов, которые следует учитывать на рисунке 2, - это ранг (R) факторизации.

Ранг тензора T, обозначаемый рангом (T), определяется как наименьшее количество тензоров ранга один, которые порождают T как свою сумму. Другими словами, это наименьшее количество компонентов в точном CP-разложении, где точное означает равенство факторизации и исходного тензора. Точное CP-разложение с компонентами R = rank (T) называется разложением ранга. (Колда и др., Тензорные разложения и приложения)

Тенторизуйте и факторизуйте графики с помощью Python

Данные, используемые в этой статье, были отобраны среди большой серии наборов сетевых данных, доступных на сайте Index of Complex Networks. Мы выбрали набор данных Золотой век Голливуда, вот его описание, взятое с веб-сайта:

Сеть, в которой участвовали 55 актеров, которые были выдающимися деятелями Золотого века Голливуда (1930–1959). Узлы - это актеры, а каждое ребро представляет актеров, вместе появляющихся в фильме. Направление Edge указывает на участника с «лучшим» статусом выставления счетов. Сотрудничество было извлечено из базы данных Internet Movie Database за период с 1909 по 2009 год. Данные доступны как в виде временной сети (последовательность графиков, каждый из которых охватывает 10 лет), так и в виде единой агрегированной сети.

При анализе использовались все графики, кроме агрегированной сети. Как вы уже знаете, граф можно представить с помощью матрицы смежности. Используя его матричное представление, мы можем затем построить тензор (3D-матрицу), в котором мы сложили всю матрицу вдоль 3-го режима, как показано на рисунке 3.

Первый шаг - загрузить все матрицы смежности в 3D-матрицу, используя следующий код Python.

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

Теперь мы можем начать использовать тензорную факторизацию. Tensorly - лучший выбор для выполнения тензорной факторизации в Python, поскольку он предлагает широкий набор функций. Еще один замечательный инструмент - Tensorlab, к сожалению, он доступен только для MATLAB и не будет использоваться в этой статье. Перед запуском алгоритма факторизации нам нужно преобразовать матрицу 3D numpy в тензор, который Tensorly может обработать, используя следующий код.

Теперь мы можем выполнить неотрицательную тензорную факторизацию. В этой статье мы решили выделить 20 компонентов.

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

Для построения сюжета мы использовали matplotlib и NetworkX. Более подробно, мы наносим на график две разные информации: 1) Векторное произведение между A и B. Эта информация показывает подграф исходного графика, описывающий подсвязи, более актуальные для этого конкретного источника. 2) Фактор C. Этот фактор описывает, какой временной период содержится в конкретном компоненте.

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

Вот сюжеты

А теперь давайте попробуем понять смысл этих сюжетов. По всей видимости, компонент №0 содержит информацию о фильмографии братьев Маркс. В самом деле, если мы сосредоточим наш анализ на графике произведения факторов A и B (Боттон на рис. 8), мы увидим, что полученный график содержит связь между 4 братьями Маркс. Более того, если мы проанализируем компонент C, то увидим отличные от нуля значения в диапазоне 1920–1959 гг. С пиком в 1930–1939 гг. Этот сюжет полностью совпадает с их фильмографией, как вы можете видеть на Рисунке 9. Из 17 фильмов 2 (11,8%) относятся к 1920–1929 гг., 9 (52,9%) относятся к 1930–1939 гг., 4 (23,5%) относятся к 1940–1990 годам. 1949 г. и 2 (11,8%) относятся к 1950–1959 гг.

Еще один интересный компонент - №4. Графики видны на следующем изображении

Этот компонент также важен, поскольку представляет собой одно из самых знаменитых и успешных совместных работ любого актера / режиссера, сотрудничество Альфреда Хичкока и Кэри Гранта, которое видно в нижней части рисунка 10. Если мы также посмотрим на верхнюю часть рисунка, мы можем увидеть то же значение в диапазоне 1940–1949 и 1950–1959 годов. Это действительно удивительный факт, так как этот дуэт снял 4 фильма: 2 в 1940–1949 годах («Подозрение» - 1941 и «Печально известный» - 1949) и 2 в 1950–1959 годах («Поймать вора» - 1941 и «Север у. Северо-Запад »- 1949).

Выводы

В этой статье мы представили простой подход к анализу продольно изменяющихся сетей с использованием неотрицательной тензорной факторизации. Мы начали с простого введения в тензоры и тензорную факторизацию. Более подробно, мы использовали особый тип тензорной факторизации, а именно неотрицательную каноническую полиадическую декомпозицию (NCPD). Декомпозиция применялась для анализа графиков изменения времени, полученных с сайта Index of Complex Networks. Анализируя различные компоненты, мы обнаружили интересную скрытую информацию, доступную в наборе данных.