Пошук зв'язків у соціальних мережах

Привіт, Хабр! У цьому пості ми хочемо поділитися нашим рішенням задачі з передрікання прихованих зв'язків у корпоративній соціальній мережі «Вулик» компанії Білайн. Це завдання ми вирішували в рамках віртуального хакатона Microsoft. Треба сказати, що до цього хакатона у нашої команди вже був успішний досвід вирішення таких завдань на хакатоне від Однокласників і нам дуже хотілося випробувати наші напрацювання на нових даних. У статті ми розповімо про основні підходи, які застосовуються при вирішенні подібних завдань і поділимося деталями нашого рішення.

Постановка завдання і вихідні дані
Розробка якісного алгоритму рекомендацій друзів є однією з найбільш пріоритетних завдань практично для будь-якої соціальної мережі т. к. подібний функціонал є сильним інструментом для залучення і утримання користувачів.

В англомовній літературі існує досить багато публікацій по цій темі, а сама задача навіть має спеціальну абревіатуру PYMK (People You May Know).

Компанія Білайн в рамках віртуального хакатона від Microsoft надала граф корпоративної соціальної мережі «Вулик». 5% ребер у графі була штучно прихована. Завдання полягало в пошуку прихованих ребер вихідного графа.



Крім наявності зв'язку між користувачами соціальної мережі, для кожної пари також була надана інформація про компаніях в яких працюють користувачі, інформація про кількість відправлених та отриманих повідомлень, тривалості дзвінків і числі відправлених і прийнятих документів.

Завдання пошуку ребер сформульована як задача бінарної класифікації, як приймальною метрики була запропонована міра F1. У деяких подібних завданнях метрику якості вважають окремо для кожного користувача і оцінюють середня. В даній задачі якість оцінювалося глобально для всіх ребер.

Навчання та тест
В загальному випадку для пошуку прихованих ребер у графі необхідно перебрати всі можливі пари вершин і для кожної пари отримати оцінку ймовірності наявності зв'язку.

Для великих графів такий підхід потребує багато обчислювальних ресурсів. Тому на практиці безліч кандидатів у соціальних графах обмежують тільки парами, які мають хоча б одного спільного друга. Як правило, таке обмеження дозволяє помітно скоротити обсяг обчислень і прискорити роботу алгоритму без істотної втрати якості.

Кожна пара кандидатів описується вектором ознак і бінарним відповіддю: «1» якщо ребро є або «0» у разі відсутності ребра. На отриманому множині {вектор ознак, відповідь} навчається модель, пророча ймовірність наявності ребра для пари кандидатів.

Оскільки граф в даній задачі ненаправлений, то вектор ознак не повинен залежати від перестановки кандидатів у парі. Це властивість дозволяє при навчанні враховувати кілька кандидатів тільки один раз і скоротити обсяг навчальної вибірки вдвічі.

Щоб відповісти на питання, які саме ребра приховані у вихідному графі, оцінку ймовірності на виході моделі необхідно перетворити в бінарний відповідь, підібравши відповідне значення порога.

Для оцінки якості та підбору параметрів моделі ми видалили з наданого графа 5% випадково вибраних ребер. Решту граф використовували для пошуку кандидатів, генерації ознак і навчання моделі. Приховані ребра використовували для підбору порогу і фінальної оцінки якості.

Нижче описані основні підходи для генерації ознак у задачі PYMK.

Лічильники
Для кожного користувача вважаємо статистики: розподіл друзів з географії, спільнотам, віку чи статі. За цим статистикам отримуємо оцінку схожості кандидатів один на одного, наприклад з допомогою скалярного твори.

Схожість множин і спільні друзі

Коефіцієнт Жаккарда — дозволяє оцінити схожість двох множин. В якості множин можуть бути як друзі, так, наприклад, і спільноти кандидатів.


Коефіцієнт Адамик/Адара — по суті це зважена сума загальних друзів двох кандидатів.

Вага цієї суми залежить від кількості друзів спільного друга. Чим менше друзів у спільного друга, тим більший внесок він дає в результуючу суму. До речі, саме цю ідею ми активно використовували у своєму рішенні.

Латентні фактори

Ці ознаки виходять в результаті матричних розкладань. Причому, розкладання можна застосовувати як до матриці зв'язків між користувачами, так і до матрицям спільнота — користувач, або географія — користувач і їм подібним. Отримані в результаті розкладання вектора з латентними ознаками можна використовувати для оцінки схожості об'єктів один на одного, наприклад за допомогою косинусної заходи відстані.

Мабуть найбільш поширеним алгоритмом матричного розкладання є SVD. Також можна використовувати популярний в рекомендаційних системах алгоритм ALS та алгоритм пошуку спільнот у графах BigCLAM.

Ознаки на графах

Ця група ознак обчислюється з урахуванням структури графа. Як правило, для економії часу при розрахунках використовується не весь граф, а якась його частина, наприклад, підграф спільних друзів глибини 2.

Одним з популярних ознак є Hitting Time — середнє число кроків, необхідне для проходження маршруту від одного кандидата до іншого з урахуванням ваг ребер. Шлях прокладається таким чином, що чергова вершина вибирається випадково з імовірністю, яка залежить від значень атрибутів ребер, що виходять з поточного вузла.

Рішення
У вирішенні даної задачі ми активно використовували ідею, закладену в коефіцієнті Адамик/Адара про те, що не всі друзі однаково корисні. Ми експериментували з дисконтирующей функцією — пробували дробові ступені замість логарифма, а також експериментували зі зважуванням спільних друзів по різних атрибутах корисності.

Т. к. над завданням ми працювали паралельно, то у нас вийшло два незалежних рішення, які надалі були об'єднані для фінального сабміта.

Перше рішення засноване на ідеї Адамик/Адар, і являє собою емпіричну формулу, яка враховує як число друзів загального одного, так і потік повідомлень між кандидатами через спільних друзів.

n — кількість спільних друзів;
xi — кількість друзів у спільного друга;
yi — сума вхідних і вихідних повідомлень між кандидатами через їх спільного друга

У другому рішенні ми згенерували 32 ознаки і навчили на них модель лог. регресії і random forest.

Моделі першого і другого рішення об'єднували з допомогою ще однієї логістичної регресії.

У таблиці описані основні ознаки, які використовувалися у другому рішенні.
ознака опис
weighted_commom Аналог коефіцієнта Адамик/Адара, але замість логарифма використовували корінь третього ступеня
conductivity_common Зважуємо спільних друзів з урахуванням провідності повідомлень. Чим менше співвідношення вихідних і вхідних повідомлень/дзвінків/документів загального одного, тим вище його вага при підсумовуванні
flow_common Оцінюємо прохідність повідомлень/дзвінків/документів між кандидатами через спільного друга. Чим вище прохідність, тим більше вага при підсумовуванні
friends_jaccard Коефіцієнт Жаккарда для друзів кандидатів
friend_company Подібність на основі частки друзів користувача з компанії кандидата
company_jaccard Оцінюємо дружність компаній кандидатів з допомогою коефіцієнта Жаккарда (дорівнює одиниці, якщо кандидати з однієї компанії)

Нижче в таблиці приведені оцінки якості як окремо, так і результуючих моделей
Модель F1 Точність Повнота
Емпірична формула 0.064 0.059 0.069
Лог регресія 0.060 0.057 0.065
Random forest 0.065 0.070 0.062
Лог регресія + Random Forest 0.066 0.070 0.063
Лог регресія + Random Forest + Емпірична формула 0.067 0.063 0.071
Підбір порогу
Отже, модель навчена. Наступний крок — це підбір порогу для оптимізації приймальною метрики.

В цій задачі ми оптимізували метрику F1.

Ця метрика однаково чутлива як до точності, так і до повноти і являє собою гармонійне середня цих величин.

Т. к. залежність метрики F1 від порога є опуклою функцією, то пошук максимуму не становить великої праці.

В даній задачі для підбору оптимального значення порогу ми скористалися алгоритм бінарного пошуку.

Технології
Вихідний граф був заданий у вигляді списку ребер з зазначенням ідентифікаторів користувачів і відповідними атрибутами. Всього в навчальній вибірці було представлено 5.5 мільйонів зв'язків. Вихідні дані надані у вигляді текстового файлу формату csv і займають на жорсткому диску 163Мб.

В рамках хакатона нам були надані ресурси хмарного сервісу Microsoft за програмою Microsoft BizSpark, в якому ми створили віртуальну машину для наших розрахунків. Ціна сервера в годину становила $0.2 і не залежала від інтенсивності розрахунків. Виділеного організаторами бюджету виявилося достатньо для вирішення даної задачі.

Алгоритм пошуку спільних друзів ми реалізували на Spark, результати проміжних обчислень кешировали на диск у форматі parquet, що дозволило помітно скоротити час читання даних. Час роботи алгоритму пошуку спільних друзів на віртуальній машині склало 8 годин. Кандидати зі списком спільних друзів у форматі parquet займають 2.1 Гб.

Алгоритм навчання та підбору параметрів моделі реалізовано на python з використанням пакету scikit-learn. Процеси генерації ознак, навчання моделі та підбору порогу на віртуальному сервері сумарно зайняли приблизно 3 години.

У висновку хочеться подякувати Брагіна Івана за активну участь у вирішенні задачі і креативність у виборі емпіричної формули.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.