Привет, Друзья!
Гитхаб — прекрасный сайт. Но представьте, что вы нашли проект А, и хотите узнать какие еще существуют похожие проекты. Как быть?
Именно с таким вдохновением уселся я разбирать API GitHub'a. Спустя пару недель свободного времени вот что получилось:
Для большинства проектов находится пара действительно интересных предложений. Вот несколько примеров: angular.js, front end bookmarks, three.js
Основная идея для построения рекомендаций — «Разработчики которые поставили звездочку этому проекту, также поставили звездочку...». А детали идеи, ее недостатки и ссылка на код — ниже.
Пожалуй, мне стоит признаться что я никакой не эксперт в области машинного обучения или построения рекомендационых систем. Все что описано ниже — результат экспериментального тыка и огромного любопытства.
Идея для старта
Давай проанализируем всех фолловеров проекта А, посмотрим какие другие проекты они фолловят, и выберем наиболее часто повторяющиеся проекты? Увы, этот подход провалился с треском: среди результатов поиска рекомендаций на первые места зачастую выходят самые популярные проекты, но не обязательно имеющие отношение к текущему. Весь GitHub влюблен в Bootstrap — самый популярный проект на сегодня.
Сколько весит общая звезда?
Например:
Проект A — всего 100 звезд
Проект B — всего 200 звезд
Проект C — всего 1000 звезд
Допустим сто одних и тех же разработчиков поставили звездочку проекту А и B, и сто одних и тех же разработчиков поставили звездочку проекту А и С. Какой проект B или С будет более близким проекту А? Очевидно — B. Половина его фолловеров следят за проектом А. Лишь 10% последователей C заметили проект A.
Как же можно обобщить три переменные в одну формулу похожести? Думал я медленно и идея рассмотреть процент общих звездочек от суммарного числа звезд обоих проектов пришла не сразу:
similarity = 2 * shared_stars_count / (project_a_stars + project_b_stars)
Формула дает очень неплохие рекомендации. Как я узнал позже от Камерона Девидсона, эта формула была выведена в 1946-м году, двумя ботаниками (это не попытка оскорбить кого-либо, они действительно были специалистами в ботанике): Соренсеном и Дайсом.
Проблемы API
К сожалению у GitHub'a отсутствует bulk API, позволяющий одним запросом достать информацию обо всех фолловерах проекта. Ко всем неудобствам ограничение в 5 000 запросов в час делает анализ проектов невыносимо долгим. Адди Османи предложил ограничиться анализом лишь нескольких сотен последователей. Экспериментально, если выбрать случайных 500 последователей проекта — результат рекомендаций не ухудшится.
Метрику сходства проектов для случайных N последователей проекта A я переписал так:
alpha = N/project_a_stars
similarity = 2 * N / (alpha * (N + project_b_stars))
Такая формулировка делает проекты с примерно одинаковым числом звезд более близкими друг другу и неплохо отсеивает шум от популярных проектов.
К сожалению даже при N = 500 время постройки анализа одного проекта занимает около семи минут.
А что если вычислить все похожие проекты заранее?
Рекомендация работает неплохо для проектов с 200+ звездами. Но сколько таких проектов на GitHub'e? Как оказалось, чуть больше семи тысяч (на момент написания кода было около 7 300).
Написав паука для поиска ников всех фолловеров популярных репозиториев, я обнаружил около 457 115 уникальных пользователей :). Теперь для каждого пользователя нужно достать его любимые проекты. Но сколько это может занять времени? Даже при очень пессимистичной оценке в 300 звездочек на фолловера, учитывая ограничение на 5 000 запросов в час, пришлось бы «копать» гитхаб 11 суток без остановки.
11 суток не так и много для хобби, да? Задача хорошо распределяется, потому если у вас есть добрый друг, готовый поделиться своим токеном на гитхабе, то можно справится за неделю! В тот же вечер появился паук для сбора любимых проектов фолловеров.
Весело шурша сеткой, время от времени часто спотыкаясь о баги, два паука насобирали необходимые данные за… 4 дня. Как оказалось, в среднем один пользователь гитхаба дает 22 звездочки. Лишь 0.02% пользователей дали больше 600 звезд. Потому при безупречной работе пауков можно было бы построить всю необходимую базу за пару суток.
Бесполезный факт
На GtHub'e больше всего ников начинается на букву 's'. За ними идут пользователи на 'm' и на 'a'. Ники на заглавную 'Q' встречаются реже, чем ники на цифру 2:
В облако
Результат работы пауков я загрузил на S3. Все современные браузеры распознают CORS, потому обычным ajax запросом можно достать необходимый js файл с рекомендациями. Если вычисленных рекомендаций для проекта не существует в облаке, сайт перейдет в режим онлайн-постройки рекомендаций. Аутентифицируйтесь на гитхабе, чтобы получить большую квоту. Промежуточные данные сохраняются в локальный IndexedDB, потому можно возобновить индексацию даже после закрытия страницы.
Код
Если вы, дорогой хабрачитатель, знаете как можно улучшить рекомендации — я с огромным удовольствием! Код сайта доступен здесь: anvaka/gazer.
Ставьте звездочки проектам, которые вам нравятся — это делает приятно не только авторам репозиториев, но и может помочь другим разработчикам найти нужные проекты :).
Спасибо огромное, что дочитали до конца :)!
Автор: anvaka
