Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 33
Плохо, я невольно следую толпе — у меня ник на букву 's'. :(
Интересно, почему большинство «обзывают» себя с маленькой буквы? Комментирующие этот топик, кстати, тоже исповедуют этот принцип.
Поведаю своё мнение по данному вопросу.
Username@mail.com выглядит не так аккуратно и удобочитаемо, как username@mail.com. Иначе говоря, в местах, где суффикса к нику нет — использую написание с прописной буквы.
Почему безсуффиксные ники пишутся со строчной — для меня тоже загадка.
Username@mail.com выглядит не так аккуратно и удобочитаемо, как username@mail.com. Иначе говоря, в местах, где суффикса к нику нет — использую написание с прописной буквы.
Почему безсуффиксные ники пишутся со строчной — для меня тоже загадка.
Да, как правильно заметили, это из email приплыло + думаю банальная лень, постоянно строчную букву в нике пробивать.
Интересно, почему большинство «обзывают» себя с маленькой буквы?
Я лично так назвался потому как в UNIX-подобных системах логин, начинающийся с большой буквы выглядел бы довольно странно.
Данные можно выложить, чтобы другие могли поиграться и не терзали гитхаб?
Вам какие данные? У меня есть несколько баз leveldb.
— База фолловеров популярных проектов
— База пользовтелей и их «полайканных» репозиториев
— База описаний репозиториев, которым поставили звездочку
— Финальная база с рекомендациями
Сумарный объем баз больше гигабайта, если помню правильно. Куда вам было бы удобно залить?
— База фолловеров популярных проектов
— База пользовтелей и их «полайканных» репозиториев
— База описаний репозиториев, которым поставили звездочку
— Финальная база с рекомендациями
Сумарный объем баз больше гигабайта, если помню правильно. Куда вам было бы удобно залить?
очень круто, нашёл много полезного по своим запросам)
Интересно выглядит запрос на само приложение :) www.yasiv.com/github/#/costars?q=anvaka%2Fgazer
По поводу машинного обучения. Чтобы избежать влияния общего количества звёзд для проектов метрики нужно нормализовать, т.е. каким-то образром делить количество общих звёзд на общее количество звёзд. Один из самых распространённых способов искать рекоммендации с использованием нормализации — косинусное расстояние.
Каждый репозиторий можно представить в виде большого вектора, в котором элементы обозначают пользователей и равны либо 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], если вы используется отрицательные значения, что-то вроде «антизвезды»).
Реализовать такой метод также достаточно просто (при условии правильного представления разряжённых векторов, опять же):
где в числителе — выражение для вычисления скалярного произведения двух векторов, а в знаменателе — произведение длин векторов. Чем больше общих звёзд у репозиториев, тем больше скалярное произведение, но чем больше звёзд в каждом из векторов вообще, тем больше их длина, и тем большее пенальти накладывается на результат.
А проекту звёздочка, да :)
Каждый репозиторий можно представить в виде большого вектора, в котором элементы обозначают пользователей и равны либо 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) )
где в числителе — выражение для вычисления скалярного произведения двух векторов, а в знаменателе — произведение длин векторов. Чем больше общих звёзд у репозиториев, тем больше скалярное произведение, но чем больше звёзд в каждом из векторов вообще, тем больше их длина, и тем большее пенальти накладывается на результат.
А проекту звёздочка, да :)
Здорово! Спасибо огромное за наводку. Непременно попробую!
Получается, если у вас есть два проекта, представленные векторами
где
тогда числитель будет равен количеству пользователей, поставивших звездочку обоим проектам, а знаменатель — корню произведения числа звезд обоих проектов.
Попробовал посчитать для d3, у которой больше 16к звезд — увы, наибольший угол получился с бутстрапом, который ничего общего кроме популярности с библиотекой не имеет. Популярный шум остался, даже после использования случайной выборки из 1000 звезд.
где
тогда числитель будет равен количеству пользователей, поставивших звездочку обоим проектам, а знаменатель — корню произведения числа звезд обоих проектов.
Попробовал посчитать для d3, у которой больше 16к звезд — увы, наибольший угол получился с бутстрапом, который ничего общего кроме популярности с библиотекой не имеет. Популярный шум остался, даже после использования случайной выборки из 1000 звезд.
Наверное, не наибольший угол, а наименьший (и, соответсвенно, наибольший косинус)?
Это вполне возможно, но проблема тут не в большой популярности репозиториев, а скорее в репрезентативности признаков. Ваше изначальное предположение в том, что если человеку понравилась одна библиотека, выполняющая функцию X, то ему должна понравиться (он должен поставить звезду) и другая, выполняющая ту же функцию. Но возьмите для примера языки программирования, скажем, C# и Java или Python и Ruby: если человек рубист, и поставил звёзды нескольким Ruby-проектам, то он скорее всего будет искать для своей работы (и ставить звёзды) библиотекам на JavaScript, чем на гораздо более близком Python. С D3, должно быть, та же история: люди, активно использующие D3, вряд ли будут ставить звёзды другим похожим проектам (зачем? нужный функционал у них уже есть в D3), зато будут искать другие связанные с их работой библиотеки, например, Bootstrap, позволяющий обрамить красивые графики D3 в не менее элегантные стили.
А чему, кстати, оказался равен косинус между бутстрапом и d3? Сдаётся мне, он не слишком большой, просто со всеми остальными проектами он ещё меньше.
Это вполне возможно, но проблема тут не в большой популярности репозиториев, а скорее в репрезентативности признаков. Ваше изначальное предположение в том, что если человеку понравилась одна библиотека, выполняющая функцию X, то ему должна понравиться (он должен поставить звезду) и другая, выполняющая ту же функцию. Но возьмите для примера языки программирования, скажем, C# и Java или Python и Ruby: если человек рубист, и поставил звёзды нескольким Ruby-проектам, то он скорее всего будет искать для своей работы (и ставить звёзды) библиотекам на JavaScript, чем на гораздо более близком Python. С D3, должно быть, та же история: люди, активно использующие D3, вряд ли будут ставить звёзды другим похожим проектам (зачем? нужный функционал у них уже есть в D3), зато будут искать другие связанные с их работой библиотеки, например, Bootstrap, позволяющий обрамить красивые графики D3 в не менее элегантные стили.
А чему, кстати, оказался равен косинус между бутстрапом и d3? Сдаётся мне, он не слишком большой, просто со всеми остальными проектами он ещё меньше.
gitfm.com делает что-то похожее (в плане результата, но не способа), спасибо за статью, было интересно.
Не стесняйтесь, поясните свою ссылку.
За упоминание того, что это уже есть на Java часто заплёвывают.
Mahout — движок рекоммендаций из экосистемы Hadoop, в котором уже заимплеменчены все возможные алгоритмы и подходы Machine Learning'а и структуры данных для них.
Mahout — движок рекоммендаций из экосистемы Hadoop, в котором уже заимплеменчены все возможные алгоритмы и подходы Machine Learning'а и структуры данных для них.
Оу, давайте по порядку. Mahout — это библиотека для large-scale машинного обучения. Именно для машинного обучения в целом, а не конкретно рекоммендательных движков, которые составляют лишь небольшую часть функционала библиотеки. Лично меня гораздо больше радуют кластеризация и распределённое сингулярное разложение. И именно large-scale, т.е. когда база состоит из хотя бы пары терабайт, а алгоритм требует одновременной загрузки слишком большого количества данных, которые просто не помещаются в памяти одной машины (например, перемножение очень больших матриц). Для остальных задач вполне достаточно обычных библиотек (в одной только Java есть как минимум Weka и RapidMiner).
Mahout реализует несколько популярных рекоммендательных движков, но далеко не все из них. Алгоритмов для рекоммендации уйма — основанные на содержании рекоммендуемых объектов, на оценках пользователей, на похожести самих пользователей, на социальных графах и т.д. Mahout основывает свои recommenders на определённой модели, и не все алгоритмы в принципе ложатся на эту модель. Да и не нужен Hadoop для большинства алгоритмов и реальных ситуаций — чаще всего даже если вся база не влазит в память, её можно считывать последовательно и/или по частям.
Mahout реализует несколько популярных рекоммендательных движков, но далеко не все из них. Алгоритмов для рекоммендации уйма — основанные на содержании рекоммендуемых объектов, на оценках пользователей, на похожести самих пользователей, на социальных графах и т.д. Mahout основывает свои recommenders на определённой модели, и не все алгоритмы в принципе ложатся на эту модель. Да и не нужен Hadoop для большинства алгоритмов и реальных ситуаций — чаще всего даже если вся база не влазит в память, её можно считывать последовательно и/или по частям.
Судя по описанию, это просто «пользователи также смотрели», а не похожие проекты (под схожими я имею ввиду только конкурентов). Ввёл 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», связанные проекты, не «похожие».
Что странно*, на 4‐й позиции таки схожий проект: Vimana. Следующий на очереди — pathogen — только 25‐й. Потом 54‐й; я про него говорил первым из‐за его популярности. На 94‐й откопался пакетный менеджер для NixOS. VAM, конечно, тоже небольшой пакетный менеджер, но кого‐то из больших братьев я увидеть не ожидал. Больше ничего схожего нет. 4, 25, 54, 94 — удивительная последовательность: по одному схожему проекту на каждую четверть сотни.
* Странно, потому что пользователям не нужно больше одного проекта со схожей функциональностью.
Ваш проект хорош для нахождения полезных дополнений к другому проекту: я, к примеру, нашёл все известные мне варианты powerline для разных программ одним запросом. Если бы новый powerline не поддерживал бы все эти программы в одиночку, то результат поиска бы меня весьма порадовал. Но здесь надо быть точным: когда я вижу заголовок «поиск похожих проектов» я ожидаю увидеть именно поиск конкуретов: тех, кто ходил некоторым путём до меня и у кого можно чему‐нибудь научиться. На вашем сайте есть правильная надпись: «related projects», связанные проекты, не «похожие».
Спасибо! Действительно, корректнее было бы говорить «связанные». Правда, проект все же находит как связанные так и похожие проекты. Например, для моей библиотеки графов он безупречно нашел первые четыре позиции. Как вы говорите, для addon-manager'a он смог найти vundle, хоть и на слишком далекой позиции. Наверное, метрику похожести можно улучшить расмотрев описание проекта… Интересно будет посмотреть на результаты косинусного расстояния, предложенного ffriend
Оффтопик: недавно мой бывший коллега Bailey Ling зарелизил свой плагин для вима, заменяющий powerline: vim-airline — когда я индексировал гитхаб проекта еще не существовало, за несколько дней после релиза его проект получил 660+ звезд. Вдруг будет интересно посмотреть тоже :).
Оффтопик: недавно мой бывший коллега Bailey Ling зарелизил свой плагин для вима, заменяющий powerline: vim-airline — когда я индексировал гитхаб проекта еще не существовало, за несколько дней после релиза его проект получил 660+ звезд. Вдруг будет интересно посмотреть тоже :).
Тут вопрос не в алгоритме, тут скорее вопрос в признаках, используемых для поиска похожих проектов. Косинусное расстояние — это просто чуть болшее структурированный и чуть более стандартный способ делать то же самое, что делали вы. Вероятнее всего, он даст небольшой прирост точности, но однозначно не решит основную проблему.
А основная проблема в том, чтобы найти признаки, по которым можно было бы судить о похожести проектов. Вы упомянули описание проектов — годный вариант. Можно выдирать ключевые слова/фразы, и по ним считать схожесть (считать хотя бы тем же косинусным расстоянием или, что более популярно в NLP, метрикой tf-idf). Вопрос только в том, что делать с проектами, в которых описания нет, или оно очень краткое. Вместо ключевых слов можно использовать используемые технологии и/или библиотеки: если проекты A и B оба используют библиотеку my-http, то можно сделать вывод, что как минимум они оба работают с сетью, а это уже кое-что. Если вернуться к пользователям, то вместо звёздочек можно использовать форки — форкают обычно то, с чем действительно работают (а таких технологий обычно для одного человека не так много), а не то, что просто понравилось.
Скорее всего хороший результат в случае с GitHub даст анализ графа взаимодействий — кто кого фоловит, кто какой репозиторий форкнул, какие репозитории зависят от каких других и т.д. Скорее всего в графе обнаружатся кластеры (плотно связанные узлы, как, например, группа школьных друзей вконтакте, которые почти все друг с другом связаны), причём как кластеры репозиториев, так и кластеры людей, а это уже целая куча информации. BFS, алгоритм Дейкстры, связные компоненты, ассоциативные правила — всё это может быть использовано для построения рекоммендаций. Но, если уж использовать графы, то сначала надо хорошо понять природу таких графов на GitHub, а это уже совсем другая история :)
В любом случае, нужно брать и пробовать. Пока ещё ни одна система машинного обучения не заработала нормально на основе одних только спекулятивных размышлений и без огладки на реальные данные.
А основная проблема в том, чтобы найти признаки, по которым можно было бы судить о похожести проектов. Вы упомянули описание проектов — годный вариант. Можно выдирать ключевые слова/фразы, и по ним считать схожесть (считать хотя бы тем же косинусным расстоянием или, что более популярно в NLP, метрикой tf-idf). Вопрос только в том, что делать с проектами, в которых описания нет, или оно очень краткое. Вместо ключевых слов можно использовать используемые технологии и/или библиотеки: если проекты A и B оба используют библиотеку my-http, то можно сделать вывод, что как минимум они оба работают с сетью, а это уже кое-что. Если вернуться к пользователям, то вместо звёздочек можно использовать форки — форкают обычно то, с чем действительно работают (а таких технологий обычно для одного человека не так много), а не то, что просто понравилось.
Скорее всего хороший результат в случае с GitHub даст анализ графа взаимодействий — кто кого фоловит, кто какой репозиторий форкнул, какие репозитории зависят от каких других и т.д. Скорее всего в графе обнаружатся кластеры (плотно связанные узлы, как, например, группа школьных друзей вконтакте, которые почти все друг с другом связаны), причём как кластеры репозиториев, так и кластеры людей, а это уже целая куча информации. BFS, алгоритм Дейкстры, связные компоненты, ассоциативные правила — всё это может быть использовано для построения рекоммендаций. Но, если уж использовать графы, то сначала надо хорошо понять природу таких графов на GitHub, а это уже совсем другая история :)
В любом случае, нужно брать и пробовать. Пока ещё ни одна система машинного обучения не заработала нормально на основе одних только спекулятивных размышлений и без огладки на реальные данные.
Согласен :). Тут еще эксперементировать и экспереметировать.
Любопытно было бы посмотреть/разработать коэффициент похожести абстрактных синтаскических деревьев кода…
Кстати, примитивный анализ похожести описаний (тот же индекс Соренсена-Дайса) дает интересные результаты. Тестировал на своей библиотеке графов, ее описание — '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.'
Любопытно было бы посмотреть/разработать коэффициент похожести абстрактных синтаскических деревьев кода…
Кстати, примитивный анализ похожести описаний (тот же индекс Соренсена-Дайса) дает интересные результаты. Тестировал на своей библиотеке графов, ее описание — '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.'
Любопытно было бы посмотреть/разработать коэффициент похожести абстрактных синтаскических деревьев кода…
А есть и такие. Не помню, правда, ищется ли там похожесть или просто совпадение кусков графа, но то, что некоторые наработки уже есть, это я точно помню. Другое дело, что AST описывает конкретную программу, т.е. конкретный способ реализовать функционал, поэтому использовать поиск похожих подграфов имеет смысл для выявления плагиата или чего-то такого, но не для поиска похожих проектов.
Кстати, я тоже исследовал тему нахождения похожести и пришёл к тому, что похожесть находится с помощью поисковых алгоритмов, а не алгоритмов рекоммендаций, которые реализовал автор. Подмена понятий, т.к. рекомендации выполняют эту функцию для объектов у которых критерий сравнения сложно найти или он имеет мало смысла. Например фильмов, музыки.
Можно решать эту задачу в стиле Latent semantic indexing:
Но, если ваша матрица будет большой (условно больше 10000х10000), на расчет SVD понадобится большое время. Можно использовать алгоритмы усеченного SVD или вместо него/ перед ним использовать Random Projection
Однако, так как 0 в нашем случае гораздо чаще значит «пользователь не видел проект», а не «пользователь видел проект, и специально не поставил ему звездочку», то скорее всего лучшие результаты покажет подход, лежащий в основе победителя конкурса Netflix. Его на хабре хорошо описали детали ребята из surfingbirds — SVD, часть I, SVD и базовые предикторы, SVD на Perl
- сформировать матрицу пользователей — проектов, с 1 в ячейках соответсвующим звездочкам, и 0 в других
- применить фильтры типа TF-IDF или Log-Entropy (см. предыдущую ссылку)
- (необязательный, но полезный шаг) уменьшить размерность с помощью SVD
- считать косинусное растояние между интересующими проектами или пользователями
Но, если ваша матрица будет большой (условно больше 10000х10000), на расчет SVD понадобится большое время. Можно использовать алгоритмы усеченного SVD или вместо него/ перед ним использовать Random Projection
Однако, так как 0 в нашем случае гораздо чаще значит «пользователь не видел проект», а не «пользователь видел проект, и специально не поставил ему звездочку», то скорее всего лучшие результаты покажет подход, лежащий в основе победителя конкурса Netflix. Его на хабре хорошо описали детали ребята из surfingbirds — SVD, часть I, SVD и базовые предикторы, SVD на Perl
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Поиск похожих проектов на GitHub