Поиск похожих проектов на GitHub

    Привет, Друзья!

    Гитхаб — прекрасный сайт. Но представьте, что вы нашли проект А, и хотите узнать какие еще существуют похожие проекты. Как быть?

    Именно с таким вдохновением уселся я разбирать 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:

    image

    В облако
    Результат работы пауков я загрузил на S3. Все современные браузеры распознают CORS, потому обычным ajax запросом можно достать необходимый js файл с рекомендациями. Если вычисленных рекомендаций для проекта не существует в облаке, сайт перейдет в режим онлайн-постройки рекомендаций. Аутентифицируйтесь на гитхабе, чтобы получить большую квоту. Промежуточные данные сохраняются в локальный IndexedDB, потому можно возобновить индексацию даже после закрытия страницы.

    Код
    Если вы, дорогой хабрачитатель, знаете как можно улучшить рекомендации — я с огромным удовольствием! Код сайта доступен здесь: anvaka/gazer.

    Ставьте звездочки проектам, которые вам нравятся — это делает приятно не только авторам репозиториев, но и может помочь другим разработчикам найти нужные проекты :).

    Спасибо огромное, что дочитали до конца :)!
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 33

      +2
      Плохо, я невольно следую толпе — у меня ник на букву 's'. :(
        +1
        Интересно, почему большинство «обзывают» себя с маленькой буквы? Комментирующие этот топик, кстати, тоже исповедуют этот принцип.
          +1
          Поведаю своё мнение по данному вопросу.

          Username@mail.com выглядит не так аккуратно и удобочитаемо, как username@mail.com. Иначе говоря, в местах, где суффикса к нику нет — использую написание с прописной буквы.

          Почему безсуффиксные ники пишутся со строчной — для меня тоже загадка.
            0
            Да, как правильно заметили, это из email приплыло + думаю банальная лень, постоянно строчную букву в нике пробивать.
            • UFO just landed and posted this here
                0
                Интересно, почему большинство «обзывают» себя с маленькой буквы?

                Я лично так назвался потому как в UNIX-подобных системах логин, начинающийся с большой буквы выглядел бы довольно странно.
              +1
              Данные можно выложить, чтобы другие могли поиграться и не терзали гитхаб?
                0
                Вам какие данные? У меня есть несколько баз leveldb.

                — База фолловеров популярных проектов
                — База пользовтелей и их «полайканных» репозиториев
                — База описаний репозиториев, которым поставили звездочку
                — Финальная база с рекомендациями

                Сумарный объем баз больше гигабайта, если помню правильно. Куда вам было бы удобно залить?
                  0
                  Было бы интересно все базы получить, в последнее время возникали задумки других data mining исследований с ними.

                  Мне кажется лучше всего в торренты поместить, если вы можете себе позволить держать включенный компьютер с раздающей программой.
                +2
                очень круто, нашёл много полезного по своим запросам)
                  0
                  Интересно выглядит запрос на само приложение :) www.yasiv.com/github/#/costars?q=anvaka%2Fgazer
                    0
                    Там еще совсем маленькое число звездочек, плюс хабраэффект :). Пока что очень маленькая выборка для анализа
                    +4
                    По поводу машинного обучения. Чтобы избежать влияния общего количества звёзд для проектов метрики нужно нормализовать, т.е. каким-то образром делить количество общих звёзд на общее количество звёзд. Один из самых распространённых способов искать рекоммендации с использованием нормализации — косинусное расстояние.

                    Каждый репозиторий можно представить в виде большого вектора, в котором элементы обозначают пользователей и равны либо 1 (пользователь X поставил звезду текущему репозиторию A), либо 0 (в противном случае). Разумеется, вектора получатся сильно разряжённымм, о чём следует помнить при выборе структуры данных для представления вектора.

                    Если взять два таких вектора для интересующих репозиториев, то косинус угла между ними покажет, насколько они похожи. Например, возьмём 3 репозитория и 2-х пользователей (2 оси координат для вектора), репозиторий A понравился только первому пользователю, репозиторий B — только второму, а репозиторий C — обоим:

                    A — (1, 0)
                    B — (0, 1)
                    C — (1, 1)

                    Вектора для A и B, вообще говоря, будут ортогональны друг другу. Косинус угла между ними будет равен нулю. А вот между A и C угол будет равен 45 градусов, а косинус, соответсвенно, ~0.7. Если добавить ещё один репозиторий D — (1, 0), то угол между A и D будет равен 0, а косинус — 1 (максимальное значение). Обратите внимание: все значения лежат в интервале [0..1] (или [-1..1], если вы используется отрицательные значения, что-то вроде «антизвезды»).

                    Реализовать такой метод также достаточно просто (при условии правильного представления разряжённых векторов, опять же):

                    cos(x, y) = (x[1] * y[1] + x[2] * y[2] + ... + x[n] + y[n]) / ( len(x) * len(y) )
                    


                    где в числителе — выражение для вычисления скалярного произведения двух векторов, а в знаменателе — произведение длин векторов. Чем больше общих звёзд у репозиториев, тем больше скалярное произведение, но чем больше звёзд в каждом из векторов вообще, тем больше их длина, и тем большее пенальти накладывается на результат.

                    А проекту звёздочка, да :)
                      0
                      Здорово! Спасибо огромное за наводку. Непременно попробую!
                        0
                        Получается, если у вас есть два проекта, представленные векторами

                        image

                        где



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

                        Попробовал посчитать для d3, у которой больше 16к звезд — увы, наибольший угол получился с бутстрапом, который ничего общего кроме популярности с библиотекой не имеет. Популярный шум остался, даже после использования случайной выборки из 1000 звезд.
                          0
                          Наверное, не наибольший угол, а наименьший (и, соответсвенно, наибольший косинус)?

                          Это вполне возможно, но проблема тут не в большой популярности репозиториев, а скорее в репрезентативности признаков. Ваше изначальное предположение в том, что если человеку понравилась одна библиотека, выполняющая функцию X, то ему должна понравиться (он должен поставить звезду) и другая, выполняющая ту же функцию. Но возьмите для примера языки программирования, скажем, C# и Java или Python и Ruby: если человек рубист, и поставил звёзды нескольким Ruby-проектам, то он скорее всего будет искать для своей работы (и ставить звёзды) библиотекам на JavaScript, чем на гораздо более близком Python. С D3, должно быть, та же история: люди, активно использующие D3, вряд ли будут ставить звёзды другим похожим проектам (зачем? нужный функционал у них уже есть в D3), зато будут искать другие связанные с их работой библиотеки, например, Bootstrap, позволяющий обрамить красивые графики D3 в не менее элегантные стили.

                          А чему, кстати, оказался равен косинус между бутстрапом и d3? Сдаётся мне, он не слишком большой, просто со всеми остальными проектами он ещё меньше.
                            0
                            Правильно заметили про угол, спасибо. Получился наибольшийи косинус. Значение формулы равно 0.2203. На втором месте идет bartaz/impress.js со значением 0.2173, и замыкает тройку лидеров backbone — 0.2131.
                              0
                              0.2 — это немного, могу предположить, что действительно тесно связанные репозитории будут иметь коэффициент хотя бы в 0.4-0.6. Впрочем, это тоже нужно проверять.
                        +1
                        gitfm.com делает что-то похожее (в плане результата, но не способа), спасибо за статью, было интересно.
                          0
                            +2
                            Не стесняйтесь, поясните свою ссылку.
                              0
                              За упоминание того, что это уже есть на Java часто заплёвывают.
                              Mahout — движок рекоммендаций из экосистемы Hadoop, в котором уже заимплеменчены все возможные алгоритмы и подходы Machine Learning'а и структуры данных для них.
                                0
                                Оу, давайте по порядку. Mahout — это библиотека для large-scale машинного обучения. Именно для машинного обучения в целом, а не конкретно рекоммендательных движков, которые составляют лишь небольшую часть функционала библиотеки. Лично меня гораздо больше радуют кластеризация и распределённое сингулярное разложение. И именно large-scale, т.е. когда база состоит из хотя бы пары терабайт, а алгоритм требует одновременной загрузки слишком большого количества данных, которые просто не помещаются в памяти одной машины (например, перемножение очень больших матриц). Для остальных задач вполне достаточно обычных библиотек (в одной только Java есть как минимум Weka и RapidMiner).

                                Mahout реализует несколько популярных рекоммендательных движков, но далеко не все из них. Алгоритмов для рекоммендации уйма — основанные на содержании рекоммендуемых объектов, на оценках пользователей, на похожести самих пользователей, на социальных графах и т.д. Mahout основывает свои recommenders на определённой модели, и не все алгоритмы в принципе ложатся на эту модель. Да и не нужен Hadoop для большинства алгоритмов и реальных ситуаций — чаще всего даже если вся база не влазит в память, её можно считывать последовательно и/или по частям.
                                  0
                                  Заметьте, я говорю экосистема Hadoop, потому что часто части это экосистемы можно использовать по отдельности и не обязательно в BigData.
                                    0
                                    Я не совсем понял, что вы имеете ввиду под «экосистемой Hadoop», и какие её части имеет смысл использовать без больших данных.
                                    0
                                    А за Wekа и RapidMiner, спасибо. Гляну на досуге. В информационном шуме сложно найти небольшие проекты не тратя на это неделю.
                              +2
                              Судя по описанию, это просто «пользователи также смотрели», а не похожие проекты (под схожими я имею ввиду только конкурентов). Ввёл MarcWeber/vim-addon-manager, получил Vundle на 54‐й позиции, а vim-snippets на первой. Проектом со схожими целями является именно Vundle, а vim-snippets — просто некоторое дополнение к дополнению Vim (последнее, кстати, идёт вторым).

                              Что странно*, на 4‐й позиции таки схожий проект: Vimana. Следующий на очереди — pathogen — только 25‐й. Потом 54‐й; я про него говорил первым из‐за его популярности. На 94‐й откопался пакетный менеджер для NixOS. VAM, конечно, тоже небольшой пакетный менеджер, но кого‐то из больших братьев я увидеть не ожидал. Больше ничего схожего нет. 4, 25, 54, 94 — удивительная последовательность: по одному схожему проекту на каждую четверть сотни.

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

                              Ваш проект хорош для нахождения полезных дополнений к другому проекту: я, к примеру, нашёл все известные мне варианты powerline для разных программ одним запросом. Если бы новый powerline не поддерживал бы все эти программы в одиночку, то результат поиска бы меня весьма порадовал. Но здесь надо быть точным: когда я вижу заголовок «поиск похожих проектов» я ожидаю увидеть именно поиск конкуретов: тех, кто ходил некоторым путём до меня и у кого можно чему‐нибудь научиться. На вашем сайте есть правильная надпись: «related projects», связанные проекты, не «похожие».
                                0
                                Спасибо! Действительно, корректнее было бы говорить «связанные». Правда, проект все же находит как связанные так и похожие проекты. Например, для моей библиотеки графов он безупречно нашел первые четыре позиции. Как вы говорите, для addon-manager'a он смог найти vundle, хоть и на слишком далекой позиции. Наверное, метрику похожести можно улучшить расмотрев описание проекта… Интересно будет посмотреть на результаты косинусного расстояния, предложенного ffriend

                                Оффтопик: недавно мой бывший коллега Bailey Ling зарелизил свой плагин для вима, заменяющий powerline: vim-airline — когда я индексировал гитхаб проекта еще не существовало, за несколько дней после релиза его проект получил 660+ звезд. Вдруг будет интересно посмотреть тоже :).
                                  +2
                                  Тут вопрос не в алгоритме, тут скорее вопрос в признаках, используемых для поиска похожих проектов. Косинусное расстояние — это просто чуть болшее структурированный и чуть более стандартный способ делать то же самое, что делали вы. Вероятнее всего, он даст небольшой прирост точности, но однозначно не решит основную проблему.

                                  А основная проблема в том, чтобы найти признаки, по которым можно было бы судить о похожести проектов. Вы упомянули описание проектов — годный вариант. Можно выдирать ключевые слова/фразы, и по ним считать схожесть (считать хотя бы тем же косинусным расстоянием или, что более популярно в NLP, метрикой tf-idf). Вопрос только в том, что делать с проектами, в которых описания нет, или оно очень краткое. Вместо ключевых слов можно использовать используемые технологии и/или библиотеки: если проекты A и B оба используют библиотеку my-http, то можно сделать вывод, что как минимум они оба работают с сетью, а это уже кое-что. Если вернуться к пользователям, то вместо звёздочек можно использовать форки — форкают обычно то, с чем действительно работают (а таких технологий обычно для одного человека не так много), а не то, что просто понравилось.

                                  Скорее всего хороший результат в случае с GitHub даст анализ графа взаимодействий — кто кого фоловит, кто какой репозиторий форкнул, какие репозитории зависят от каких других и т.д. Скорее всего в графе обнаружатся кластеры (плотно связанные узлы, как, например, группа школьных друзей вконтакте, которые почти все друг с другом связаны), причём как кластеры репозиториев, так и кластеры людей, а это уже целая куча информации. BFS, алгоритм Дейкстры, связные компоненты, ассоциативные правила — всё это может быть использовано для построения рекоммендаций. Но, если уж использовать графы, то сначала надо хорошо понять природу таких графов на GitHub, а это уже совсем другая история :)

                                  В любом случае, нужно брать и пробовать. Пока ещё ни одна система машинного обучения не заработала нормально на основе одних только спекулятивных размышлений и без огладки на реальные данные.
                                    0
                                    Согласен :). Тут еще эксперементировать и экспереметировать.

                                    Любопытно было бы посмотреть/разработать коэффициент похожести абстрактных синтаскических деревьев кода…

                                    Кстати, примитивный анализ похожести описаний (тот же индекс Соренсена-Дайса) дает интересные результаты. Тестировал на своей библиотеке графов, ее описание — 'Graph drawing library for JavaScript'. Первая тройка наиболее близких проектов:

                                    1. 'an open-source lightweight JavaScript graph drawing library'
                                    2. 'JavaScript library for mobile-friendly interactive maps'
                                    3. 'Graphs and Charts for Canvas in JavaScript.'
                                      0
                                      Любопытно было бы посмотреть/разработать коэффициент похожести абстрактных синтаскических деревьев кода…

                                      А есть и такие. Не помню, правда, ищется ли там похожесть или просто совпадение кусков графа, но то, что некоторые наработки уже есть, это я точно помню. Другое дело, что AST описывает конкретную программу, т.е. конкретный способ реализовать функционал, поэтому использовать поиск похожих подграфов имеет смысл для выявления плагиата или чего-то такого, но не для поиска похожих проектов.
                                  +1
                                  Кстати, я тоже исследовал тему нахождения похожести и пришёл к тому, что похожесть находится с помощью поисковых алгоритмов, а не алгоритмов рекоммендаций, которые реализовал автор. Подмена понятий, т.к. рекомендации выполняют эту функцию для объектов у которых критерий сравнения сложно найти или он имеет мало смысла. Например фильмов, музыки.
                                  0
                                  Можно решать эту задачу в стиле Latent semantic indexing:

                                  1. сформировать матрицу пользователей — проектов, с 1 в ячейках соответсвующим звездочкам, и 0 в других
                                  2. применить фильтры типа TF-IDF или Log-Entropy (см. предыдущую ссылку)
                                  3. (необязательный, но полезный шаг) уменьшить размерность с помощью SVD
                                  4. считать косинусное растояние между интересующими проектами или пользователями


                                  Но, если ваша матрица будет большой (условно больше 10000х10000), на расчет SVD понадобится большое время. Можно использовать алгоритмы усеченного SVD или вместо него/ перед ним использовать Random Projection

                                  Однако, так как 0 в нашем случае гораздо чаще значит «пользователь не видел проект», а не «пользователь видел проект, и специально не поставил ему звездочку», то скорее всего лучшие результаты покажет подход, лежащий в основе победителя конкурса Netflix. Его на хабре хорошо описали детали ребята из surfingbirds — SVD, часть I, SVD и базовые предикторы, SVD на Perl

                                  Only users with full accounts can post comments. Log in, please.