В повседневной жизни мы использовали множество приложений для социальных сетей, таких как FB, IG и т. Д., Но думаете ли вы, как эта платформа будет предоставлять уведомление о рекомендации друзей? Кроме того, оповещение для каждого пользователя является своего рода уникальным и зависит от круга его или ее друзей, круга офиса и т. Д. В этом тематическом исследовании мы подробно рассмотрим, как все это будет работать с точки зрения моделей машинного обучения. .
Оглавление:
А. Введение
Б. Состав ML
С. Бизнес-цели и ограничения
Д. Анализ набора данных
Э. Первый подход
Ф. Матрица производительности
Г. EDA
H. Featurization
Я. Моделирование
Дж. Резюме
К. Будущая работа
Л. Профиль
М. Ссылки
А. Введение:
В этом тематическом исследовании мы должны сосредоточиться на системе рекомендаций друзей для пользователей Facebook (т. Е. Рекомендовать человека, у которого есть наибольшая вероятность стать другом).
Б. Состав ML:
В этом тематическом исследовании мы можем использовать модель контролируемого обучения с двоичной классификацией, поскольку мы должны определить, является ли связь между исходным и конечным узлами хорошей или плохой.
C. Бизнес-цели и ограничения:
а) Цели:
• Основная цель - выявить возможное недостающее звено, используя предоставленные данные.
• Вероятность классификации важна, потому что с ее помощью мы можем выбрать конкретное количество вариантов рекомендации относительно вероятности.
б) Ограничения:
• Вероятность предсказания полезна, чтобы рекомендовать ссылки с наивысшей вероятностью.
• Отсутствие строгих ограничений по задержке, так как цель больше заключается в принятии правильного решения, чем в быстром решении. Было бы хорошо и приемлемо, если бы модели потребовалось несколько секунд, чтобы сделать прогноз.
D. Анализ набора данных:
Данные взяты из задачи по набору персонала facebook на Kaggle.
Данные https://www.kaggle.com/c/FacebookRecruiting содержат два столбца: источник и место назначения, каждое ребро графа.
Столбцы данных (всего 2 столбца):
- Исходный узел int64
- Целевой узел int64
Э. Первый подход:
1) Набор данных, который у нас есть, содержит узлы и ребра. Итак, сначала мы выполним EDA для набора данных, чтобы получить четкое представление о наборе данных.
2) Опубликовать EDA, мы должны сделать особенность, потому что мы не будем передавать набор данных с узлом и ребрами непосредственно в модель. Итак, чтобы избежать этого, мы создадим возможные элементы, используя узлы и ребра.
3) После того, как мы доработаем функции, мы создадим набор данных, используя эти функции, и сможем использовать его для моделирования.
4) Теперь, в разделе моделирования, мы попробуем разные модели НЛП и проверим их эффективность.
5) Наконец, мы выберем модель, которая будет обеспечивать наилучшие характеристики.
F. Матрица производительности:
1) Прогнозируемое недостающее звено должно быть правильным, поэтому нам требовалось высокое значение Напоминания.
2) Поскольку мы должны охватить максимальное количество людей, значение точности также должно быть высоким.
4) Итак, оценка матрицы эффективности F-1 очень полезна.
5) Матрица путаницы
Импорт важных библиотек:
Примечание. Мы будем использовать библиотеку networkx, поскольку она очень полезна для функций, связанных с графиками.
Теперь мы прочитаем график, где степень и степень объясняются, как показано ниже:
Пусть есть человек A, который следует за 3 людьми, и у него есть 5 последователей, тогда в этом случае
Внутренняя степень = 5 и исходящая степень = 3.
Вывод приведенного выше кода указан ниже:
Тип графика - Направленный график.
Количество узлов (исходный + целевой узел) в наборе данных - 1862220
Общее количество ребер в наборе данных - 9437519
И средняя степень, и средняя степень выхода для узлов в наборе данных равны 5,0679.
G. EDA:
В наборе данных у нас есть узлы и ребра между узлами. Узлы - это исходный узел и целевой узел. Итак, мы проанализируем данные с точки зрения подписчиков, подписчиков и подписчиков + подписок.
There is total 1862220 unique persons.
1) Последователи (в степени каждого человека):
· Во-первых, мы попытаемся построить график между количеством последователей и индексом №. Из этого мы узнали, что очень мало людей, у которых количество последователей больше 50.
· Для дальнейшего анализа мы проверим количество подписчиков для первых 1,5 миллионов человек, используя график «Число подписчиков по сравнению с индексом №». Из этого графика мы узнали, что у большинства людей нет. подписчиков менее 7.
· Мы пытались построить коробчатую диаграмму, используя внутренние градусы, но это не дает четкого понимания.
· Теперь мы построили график значения процентиля от 90 до 100 внутренней степени, и мы узнали, что значение процентиля 99 равно 40, а значение процентиля 100 552.
· Итак, теперь мы продолжим анализировать значение 100-процентиля, построив график значения процентиля между 99,1 и 100. Из этого мы узнали, что значение процентиля 99,9 равно 112, а значение 100 процентиля 552.
· Мы также построили PDF-файл для данных в градусах.
2) Следование (получение степени от каждого человека):
· Во-первых, мы попытаемся построить график между количеством подписчиков и индексом №. Из этого мы узнали, что очень мало людей, у которых число подписчиков превышает 50.
· Для дальнейшего анализа мы проверим количество подписчиков для первых 1,5 миллионов человек, используя график «Число подписчиков» и «Индекс №». Из этого графика мы узнали, что у большинства людей нет. следующих меньше чем равно 7.
· Мы попытались построить коробчатую диаграмму, используя исходящую степень, но она не дает четкого понимания.
· Теперь мы построили график значения процентиля от 90 до 100 исходящей степени и узнали, что значение 99 процентиля равно 40, а значение процентиля 100 - 1566.
· Итак, теперь мы продолжим анализировать значение 100-процентиля, построив график значения процентиля между 99,1 и 100. Из этого мы узнали, что значение процентиля 99,9 равно 112, а значение 100 процентиля 1566.
· Число людей, которые ни на кого не подписываются или у которых нет подписчиков, равно 0.
· Нет лиц, которые ни за кем не подписаны: 274512, а% - 14,741115442858524
· Число лиц, не имеющих нулевых подписчиков: 188043, а% - 10.097786512871734
3) Последователи + Подписчики (внутренняя и окончательная степень для каждого человека):
· Во-первых, мы попытаемся построить график между количеством подписчиков + подписчиков и номером индекса. Из этого мы узнали, что очень мало людей, у которых число подписчиков превышает 80.
· Для дальнейшего анализа мы проверим количество подписчиков + подписчиков для первых 1,5 млн человек, используя график «Число подписчиков + подписок против индекса №». Из этого графика мы узнали, что у большинства людей нет. подписчиков + число подписок меньше 14.
· Теперь мы построили график значения процентиля от 90 до 100 для исходящей степени + In-градуса и узнали, что значение процентиля 99 равно 79, а значение 100 процентиля 1579.
· Итак, теперь мы продолжим анализировать значение 100-процентиля, построив график значения процентиля между 99,1 и 100. Из этого мы узнали, что значение процентиля 99,9 составляет 221, а значение 100 процентиля 1579.
· Количество подписчиков + подписчиков менее 10 составляет 1320326 человек.
· Минимальное количество подписчиков + подписчиков - 1 и 334291 человек, у которых минимальное количество подписчиков + подписок
· Максимальное количество последователей + подписчиков - 1579 и 1 человек, имеющий максимальное количество подписчиков + подписчиков
· Количество слабосвязных компонентов 45558 слабосвязных компонентов с 2 узлами 32195
В настоящее время у нас есть набор данных с хорошими краями (y = 1), только поэтому набор данных в настоящее время дисбалансирован, чтобы правильно сбалансировать набор данных, мы должны добавить некоторые плохие края (y = 0). Созданы неверные ссылки из графа, которые не входят в граф и кратчайший путь которых больше 2.
Len (U1, U4) = 3 и Len (U1, U3) = 2, поэтому мы отклоним (U1, U3) и примем ссылку (U1, U4).
Общее количество плохих ссылок (missing_edges), которые мы получили, составляет 9437519, которые мы можем добавить в текущий набор данных.
Итак, теперь у нас есть сбалансированный набор данных с хорошими ссылками (y = 1) и плохими ссылками (y = 0), как указано ниже.
Теперь мы должны случайным образом разделить данные поезда и теста на комбинацию 80% и 20%, как указано ниже:
Теперь мы сделали некоторые наблюдения по поводу поездов и тестовых данных.
Как показано на раскопке, 81 000 точек присутствуют в тесте, но отсутствуют в наборе данных поезда, а 717 000 точек присутствуют в наборе данных, но не входят в набор данных теста. Итак, у нас нет информации по этому поводу, такая проблема называется проблемой частичного холодного запуска.
После анализа вывода приведенного выше кода мы узнали, что:
- Количество узлов в обучающем и тестовом наборе данных составляет 1780722 и 144623 соответственно.
- Количество ребер в наборе тестовых данных составляет 7550015 и 1887504 соответственно.
- Средняя степень в поезде тестового набора данных составляет 4,2399 и 1,6490 соответственно.
- Средний выпускной диплом в наборе тестовых данных составляет 4,2399 и 1,6490 соответственно.
- Количество узлов, общих в наборе обучающих и тестовых данных, составляет 1063125.
- Количество узлов, присутствующих в поезде, но отсутствующих в тесте, составляет 717597
- Количество узлов, присутствующих в тесте, но отсутствующих в поезде, составляет 81498
- Процент узлов, присутствующих в тесте, но не присутствующих в поезде, от общего набора тестовых данных составляет 7,12%.
H. Особенности:
В настоящее время у нас есть набор данных с исходным узлом, целевым узлом и Yi, но мы не можем передать эти данные напрямую модели, нам нужно сначала выполнить настройку данных. Пусть у нас есть функция f1, f2, f3… и т. Д., Если мы введем исходный узел и целевой узел в функцию f1, мы получим соответствующее значение для функции и добавим его в новый набор данных на основе функций.
1) Расстояние Жаккара
2) Косинусное расстояние
3) Показатели рейтинга
3.1) Рейтинг страницы
4) Возможности графика
4.1) Кратчайший путь:
4 · 2) Проверка того же сообщества
4 · 3) Индекс Адама / Адара:
4 · 4) Это человек следил за ответом
4 · 5) Центральность Каца:
4 · 6) Количество просмотров
1) Расстояние Жаккара:
Он рассчитывается по приведенной ниже формуле:
Расстояние Жаккара мы можем рассчитать как для последователя, так и для следующего. Параметр для определения сходства между пользователем. Чем выше расстояние Жаккара, тем больше вероятность того, что между пользователями есть преимущество. Пусть X = {u1, u2, u3} и Y = {u2, u3, u4}, тогда | X ∩ Y | = {u1, u4} = 2 и | X ∪ Y | = {u1, u2, u3, u4} = 4, т. е. j = 2/4 = 0,5
Фрагмент кода:
2) Косинусное расстояние:
Косинусное расстояние также является расстоянием, равным расстоянию Жаккара, только с разницей в знаменателе. Он рассчитывается по приведенной ниже формуле:
Фрагмент кода:
3) Меры ранжирования
3.1) Рейтинг страницы:
Если в наборе данных есть данные ориентированного графа, тогда популярной функцией является PageRank. Считайте каждую вершину веб-страницей, и мы можем назвать ее ориентированным графом. Если какая-либо веб-страница имеет гиперссылку CNN.com, то это условие находится в состоянии ориентированного графа. Рейтинг страницы увеличивается, если на нее направлено большое количество важных страниц.
На приведенном ниже изображении B имеет наивысший рейтинг страницы, потому что все веб-страницы направлены на него, поэтому к нему подключено большое количество веб-страниц, а некоторые из них являются важными. В то время как C имеет более высокий рейтинг страницы по сравнению с E, хотя на него направлено меньше страниц, но B направлено на C, поэтому это также важная веб-страница, поэтому она имеет более высокое значение рейтинга страницы по сравнению с E. Из этого мы узнали, что рейтинг страницы во многом зависит от качества и количества направленной на нее веб-страницы.
Он в основном используется в задачах поиска в Интернете / в Интернете. Но мы можем использовать в нашем наборе данных, так как давайте рассмотрим, что Билл Гейтс - это человек, за которым следуют Марк Зугарбарк, Уоррен Баффет (оба такие знаменитости, как Билл Гейтс, а также важные лица), так что это увеличит счет Билл Гейтса и также нравится не знаменитостям вроде нас (увеличивает количество подписчиков), поэтому мы можем рекомендовать Билла Гейтса любому случайному человеку, поскольку есть шансы, что этот человек последует за ним.
У нас уже есть функция ранжирования страниц в сети. Мы можем вычислить минимальную вероятность, максимальную вероятность и среднее значение вероятности. Значение вероятности - это вероятность того, что человек попадет на эту страницу, если он выполнит произвольный поиск. Ранее мы видели, что есть некоторые узлы, которые присутствуют в поезде, но не присутствуют в тесте, и наоборот. Для таких узлов источника и назначения мы будем использовать среднее значение рейтинга страницы (mean_pr).
Фрагмент кода:
После анализа результатов мы узнали, что:
- Минимальный рейтинг страницы - 1.6556497245737814e-07.
- Максимальный рейтинг страницы составляет 2,7098251341935827e-05
- Среднее значение рейтинга страницы 5.615699699389075e-07. Мы можем использовать среднее значение для вменения узлов, которых нет в данных поезда.
4) ОСОБЕННОСТИ ГРАФИКА:
4.1) НАИБОЛЕЕ КОРОТКИЙ ПУТЬ:
В этой характеристике мы рассчитаем кратчайший путь между двумя узлами. Если между двумя узлами нет кратчайшего пути, мы будем рассматривать его как -1. Если два узла напрямую связаны, то сначала мы удалим это прямое соединение, а затем найдем кратчайший путь между ними.
Фрагмент кода:
Кратчайший путь между исходным узлом 77697 и целевым узлом 826021 равен 10.
4.2) ПРОВЕРКА ОДНОГО СООБЩЕСТВА:
Прежде чем понять эту особенность, мы должны сосредоточиться на концепции компонента с недельной связью и компонента с сильной связью.
На приведенном ниже изображении компонент в секции S1 является Сильно связанным компонентом, потому что из 1,2,0 мы можем перейти к любому компоненту, следуя направлению, но мы не можем добраться до узла 0,1,2 из узла 3 и узла 4. Итак, компонента в сечении S2 является слабосвязной компонентой.
Если мы объединяем S1 и S2, когда мы пытаемся перейти от вершины 4 к 0, мы не получаем никакого пути для перемещения, поэтому мы не можем вызвать Подграф комбинации S1 и S2 как компонент сильной связности.
Теперь позвольте, если есть человек, у которого есть набор друзей в коллаже в одном слабо связанном подграфе, также называемом сообществом, а в другом сообществе - его другом по Office. Оба набора очень сильно отличаются друг от друга. Если есть какая-либо связь между обоими этими сообществами, то оба сообщества можно объединить.
Мы можем найти слабосвязанный компонент, используя библиотеку networkx, и мы можем проверить, являются ли входные узлы слабо связным компонентом или нет.
Фрагмент кода:
Мы проверяем, принадлежат ли исходный узел 861 и целевой узел 1659750 к одному сообществу или нет. Но на выходе мы получили 0, что означает, что он не принадлежит к тому же сообществу.
4.3) ИНДЕКС АДАМИКА / АДАРА:
Он рассчитывается по приведенной ниже формуле:
Где N (x) → Количество входящих и исходящих соединений в узле x
N (y) → Количество входящих и исходящих соединений в узле y
Мы можем рассчитать индекс Адара, как показано ниже:
1) Если нам нужно найти индекс Адара для узла x и узла y, то сначала мы должны определить общую окрестность между ними, то есть N (x) ∩ N (y)
2) Есть два типа общих окрестностей, которые мы можем попасть в узел x и узел y:
1) Узел знаменитости: он имеет большое количество соседей, и узел x и узел y являются одним из них, поэтому существует вероятность границы между узлом x и узел y очень мал. Итак, в этом случае log (N | u |) велик, поэтому значение 1 / log (N | u |) уменьшается. В результате индекс Адара уменьшается.
2) Нормальный узел: у него ограниченное количество соседей. Узел может быть узлом x и узлом y друга по колледжу и т. Д., Поэтому существует большая вероятность того, что между узлом x и узел y. Итак, в этом случае log (N | u |) мало, поэтому значение 1 / log (N | u |) увеличивается. В результате увеличивается индекс Адара.
Фрагмент кода:
Расчет индекса Адара между исходным узлом 1 и целевым узлом 189226, который равен 0.
4.4) НАЗАД:
Если есть ребро между (a, b), тогда высока вероятность, что есть край между (b, a).
Существует вероятность, что исходный узел 1 последует за целевым узлом 189226, так как на выходе будет 1.
4.5) КАРЦ-ЦЕНТРАЛЬНОСТЬ:
Центральность по Кацу узла - это мера центральности в сети. Он похож на рейтинг страницы, но это очень старый метод, поэтому он не пользуется большой популярностью. Формула центральности Каца приведена ниже:
Где, Aij → Присоединенная матрица с собственным вектором λ
Β → контролирует начальную центральность и α ‹1 / λmax
Фрагмент кода:
После анализа результатов мы узнали, что:
- Минимальная оценка центральности Каца составляет 0,0007313532484065916.
- Максимальная оценка центральности Каца составляет 0,003394554981699122.
- Среднее значение показателя центральности Каца 0,0007483800935562018. Мы можем использовать среднее значение для вменения узлов, которых нет в данных поезда.
4.6) ОЦЕНКА ПОПАДАНИЙ:
Пожалуйста, обратитесь к https://en.wikipedia.org/wiki/HITS_algorithm для получения более подробной информации.
Фрагмент кода:
После анализа результатов мы узнали, что:
- Минимальный балл HITS - 0,0.
- Максимальный балл HITS составляет 0,004868653378780953.
- Среднее значение показателя HITS 5,615699699344123e-07
4.7) СВД (разложение):
Пусть A - это матрица смежности для G, которая представляет собой размер узлов в наборе данных, то есть 1,78M * 1,78M. Это большая разреженная матрица, потому что, как показано в матрице A ниже, значение для вершины i и j равно Aij, которое равно 1, если есть ребро между ui и uj, а если нет, то 0. Таким образом, матрица выглядит как редкий.
В приведенном ниже коде при выполнении SVD мы выбрали разложение матрицы на размер 6. После применения SVD, т. Е. Разложения матрицы смежности, мы получили три значения U, S (также называемые сигмой) и VT, соответственно. формы матрицы указаны ниже. В U точка i определяется шестью возможными способами, а также в V то же самое i определяется шестью возможными способами. Итак, если у нас есть две вершины, то для каждой вершины у нас есть пара из 6 характеристик, соответствующих U и VT. Итак, для пары вершин у нас есть всего 24 объекта со значением 0 или 1.
Фрагмент кода:
Форма матрицы пост SVD декомпозиции:
4.8) ВЕСОВЫЕ ХАРАКТЕРИСТИКИ:
Чтобы определить схожесть узлов, между узлами было вычислено значение веса ребра. Вес края уменьшается по мере увеличения числа соседей. Интуитивно представьте, что один миллион человек подписан на знаменитость в социальной сети, тогда, скорее всего, большинство из них никогда не встречались друг с другом или со знаменитостью. С другой стороны, если у пользователя 30 контактов в своей социальной сети, шансы, что многие из них знают друг друга, выше.
Мы создали указанную ниже функцию как для обучения, так и для тестирования:
· Вес входящих кромок
· Вес отходящих ребер
· Вес входящих ребер + вес исходящих ребер
· Вес входящих ребер * вес исходящих ребер
· 2 * вес входящих ребер + вес исходящих ребер
· Вес входящих ребер + 2 * вес исходящих ребер
Фрагмент кода:
4.9) ТОЧКА СВД:
Точечный продукт между функциями SVD исходного узла и SVD узла назначения. как показано ниже.
Фрагмент кода:
4.10) ПРЕДПОЧТИТЕЛЬНОЕ ПРИЛОЖЕНИЕ:
Одна хорошо известная концепция в социальных сетях заключается в том, что пользователи с большим количеством друзей, как правило, устанавливают больше связей в будущем. Это связано с тем, что в некоторых социальных сетях, например в финансах, богатые становятся еще богаче. Мы оцениваем, насколько «богаты» две наши вершины, вычисляя умножение числа друзей (| Γ (x) |) или последователей каждой вершины. Можно отметить, что индекс подобия не требует никакой информации о соседях узла; следовательно, этот индекс подобия имеет наименьшую вычислительную сложность.
Фрагмент кода:
I. Моделирование:
Мы закончили настройку. Итак, теперь мы приступим к моделированию в следующих шагах:
· Настройка параметров
· Обучите модель с лучшим параметром.
· Проверка матрицы эффективности
· Важность функции
В таблице ниже представлены характеристики различных моделей:
J. Резюме:
По производительности, которую мы наблюдали в разделе моделирования, GBDT является лучшей моделью для системы рекомендаций FB с набором данных на основе графа.
К. Будущая работа:
1. В настоящее время мы пытались реализовать важный алгоритм NLP, но мы также можем проверить производительность модели с помощью метода DL, например:
1) MLP
2) LSTM
3) GRE
2. Кроме того, мы можем представить новые методы определения характеристик для улучшения набора данных, поскольку вы знаете правило машинного обучения, согласно которому чем больше данных, тем лучше производительность.
Л. Профиль:
Спасибо за чтение! ценю мою тяжелую работу, хлопая в ладоши. Если вы хотите увидеть, как я реализовал этот анализ, вот репозиторий проекта GitHub. Я всегда открыт для конструктивных отзывов - если у вас есть идеи для дальнейшего анализа, прокомментируйте их ниже или свяжитесь с нами через LinkedIn.
М. Ссылки:
1) Особая благодарность: https://www.appliedaicourse.com/?gclid=CjwKCAjwzMeFBhBwEiwAzwS8zGsy_TVp9ZwwZtXRBlFlAMxT_Iq5c6CP5-dPPYQeteoT5b9ho_VeBm
2) https://en.wikipedia.org/wiki/HITS_algorithm
3) Справка по весовым характеристикам: функции на основе графиков для прогнозирования контролируемых ссылок Уильям Цукерски, Бенджамин Хамнер, Бо Ян
4) Предпочтительное приложение ссылка: https://medium.com/@cynosuremishra01/different-featurization-techniques-for-graph-related-problems-in-machine-learning-9c9d60caae60
