Как стать автором
Обновить

Комментарии 17

Увидел матан на Хабре и испугался, настолько отвык :)

Введение про Васю гениальное. Сразу объясняет, о чем, собственно статья, и позволяет в ней разобраться.

> Остаётся только понять, как быстро искать ближайших соседей.

Это хорошо решается в graph базах данных, и имеет смысл, наверное, хотя бы часть данных хранить в графах и пользоваться чем-то типа Gremlin'а для поисков. Но это уже тех. детали.
Спасибо на добром слове! Вроде матана не планируется. :) Этот пост можно с большой натяжкой назвать геометрией разве что. :)

Можете ссылку кинуть о том, что вы имели в виду про graph databases? Тут же нет статического графа как такового, расстояние между элементами базы постоянно меняется, и надо уметь считать расстояние между любой парой (а от graph database на полном графе толку немного, наверное :) ). Какие-то работы гуглятся, конечно:
www.ncbi.nlm.nih.gov/pmc/articles/PMC2860326/
но про «хорошо решается» я не слышал… или я недопонял, о чём идёт речь?
Граф базы данных из популярных — это Neo4j и FlockDB.

Есть очень симпатичная библиотека для создания запросов к таким базам под названием Gremlin. Здесь описание того, что можно делать.

А так — да, по граф. базам данных практически работы нет. Есть некоторые презентации у автора Гремлина.
Спасибо! Про Gremlin не знал, попробую разобраться, зачем это всё может быть нужно в данном случае. :)
> попробую разобраться, зачем это всё может быть нужно в данном случае.

Ну, это как раз для этого:
Поэтому эту формулу обычно огрубляют до k ближайших соседей – k пользователей, максимально похожих на данного пользователя и уже оценивших этот продукт:

Остаётся только понять, как быстро искать ближайших соседей.


В простейшем случае — это все люди, до которых от нас ровно один шаг в графе, что для формулы не подойдет :)

В более сложных — можно играться с графами на основе разных критериев (вплоть до того, чтобы проводить ребро от каждой сущности к каждому пользователю). Тога посик становится если не тривиальным, то выполнимым. Например: github.com/tinkerpop/gremlin/wiki/Flow-Rank-Pattern
Вот я и не понял, что значит «один шаг в графе». Расстояние можно подсчитать между любой парой юзеров, и эти расстояния меняются после каждой новой оценки — как определить граф так, чтобы он не оказался почти полным?..

Если же говорить про настоящие графы, то, например, тот же социальный граф действительно можно использовать в рекомендациях — возможно, поговорим об этом ещё.
Ну, шагом я имел в виду ребро.

А так… Берем Map Reduce в руки — и вперед, высчитывать :)
Ну, так я и спрашиваю: как определить рёбра в графе?

MapReduce — дело хорошее, если всё параллелизуется идеально. kNN в этом смысле — не слишком удобная штука, хотя да, методы есть: www.lsdsir.org/wp-content/uploads/2010/05/lsdsir10-2.pdf
> Ну, так я и спрашиваю: как определить рёбра в графе?

Вот это пока не знаю :(
Для интересующихся темой ещё можно почитать книгу на английском Programming Collective Intelligence, там одна из глав посвящена составлению рекомендаций — Collaborative Filtering.
Она уже давно переведена на русский: habrahabr.ru/blogs/books/79151/
Мне она показалось очень поверхностной. Автор переусердствовал в избегании математики, в итоге вместо того, чтобы дать емкую и простую формулу вроде тех, что встречаются в этой статье, он словами описывает, что нужно сложить и где поделить, что очень тяжело воспринимается.

(формулы правда есть в приложении, но все равно читать эту книгу тяжеловато).
Да, избегать математики тут сложно и совершенно ни к чему, математика только способствует пониманию. Следующая инсталляция должна сделать этот тезис совсем очевидным. :)
Спасибо, очень интересно! Продолжайте, обязательно.
Спасибо на добром слове! Будем продолжать.
Очень интересно, спасибо. Параллельно писал код для проверки и у меня получилось, что для user-based корреляция с Петровичем равна -0.1890.
И, как следствие, прогнозируемая оценка будет выше — 4.1.
да, в статье ошибка с Петровичем. Так же не очень понятно — почему в формуле GroupLens algorithm в числитель идет вес со знаком и тот же самый вес в знаменатель уходит в сумму уже по модулю…
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.