Какую технологию хранения/обработки данных использовать для реализация алгоритма схожести предметов (рекомендаций)?
Привет!
Столкнулся с проблемой производительности при реализации алгоритма рекомендаций.
Входные данные:
Есть порядка 60000 записей с оценками пользователей, вида {user_name, item, score} в виде CSV файла на диске, а так же в MongoDB.
Задача:
Для каждой пары предметов рассчитать их схожесть на основе оценок пользователей.
Проблема: Производительность. Пробовал работать с базой данных и вытаскивать оценки для каждой пары, но т.к. всех возможных пар n(n-1)/2, получается слишком долго; много обращений к базе данных. Потом подумал загрузить всё в память и там обсчитывать, но не понятно как маштабировать с увеличением количества оценок (что если все данные не поместятся в память?). Пишу на Node.js, если это важно.
Может, есть специальные технологии для подобной задачи? Подскажите, в каком направлении смотреть:
- более эффективные реализации алгоритма, с малым количеством обращений к базе данных?
- написать какой-то хитрый MapReduce / Aggregate?
- посмотреть базы данных на основе графов?
- что-то другое?
Для каждой пары предметов (item1, item2), я выбираю пользователей, которые оценивали оба эти предмета. Затем считаю разницу между оценками (это грубо и есть расстояние). Например, если item1 и item2 оценили 100 пользователей и все поставили одинаковую оценку - считаем расстояние между предметами 0 (одно и тоже). Если загнать все данные в память и отсортировать по item, затем по user_name.. то по идее можно всё рассчитать за N*(logN + Const). Вообще конечная цель, это дать рекомендации пользователю на основе его оценок. Я думал это сделать таким образом: отобрать предметы, которые пользователь оценил высоко и затем предложить ему ближайшие (на основе проведённых рассчётов).
Непонятный немного рейтинг - получается что и плохими отзывами можно достичь одинаковости мнений и более того, потом предложить такой товар тому, кто может быть единственный его оценил хорошо.
Я то сначала думал, что Вы пытаетесь найти схожих с текущим покупателей по схожести их оценок одинаковым товарам (пусть называются "со сходными взглядами на жизнь"), а затем посмотреть, какие другие товары такие покупатели со сходными взглядами тоже оценили хорошо, а текущий покупатель еще не видел ...
Про рейтинг - вы правы, возможно это изьян. Тут два момента: 1) есть определённая специфика товара (это алкоголь) 2) я думал считать похожесть только, если товар оценили 10+ человек.
Думал об этом, но почему-то решил считать именно похожесть товаров, а не пользователей. Вообще надо подумать, что лучше (непонятен пока критерий), а ещё проще попробовать оба варианта, как только смогу реализовать.
В плане теории я бы предложил метод "k-Nearest Neighbours" между покупателями. При этом величину k держать где-то в диапазоне 20-50, и предлагать взвешенно пропорционально степени близости те продукты, которые тоже были положительно оценены k соседями.
В плане практики я создал бы вспомогательную таблицу, где для каждого покупателя хранятся его k соседей (поэтому и предлагаю ограничить k около 30) и нормированное расстояние до них. Этой таблицы будет достаточно для того чтобы с высоким быстродействием предлагать рекомендации.
А саму таблицу пересчитывать отдельным потоком в малонагруженное время раз в неделю или раз в месяц (в зависимости от Вашего товарооборота). Пусть это будет занимать час-два. По факту готовности - переливать в боевую таблицу соседей.
Если интересует мое мнение о формуле расстояния между покупателями или алгоритме средневзвешенного предложения - спрашивайте ...
@kunya В этой статье и комментариях алгоритм kNN обсуждается как исключительно "классификатор". В то же время ничто не мешает не разбивая пользователей на четкие группы, пользоваться весами kNN для взвешивания влияния "j-ого по схожести" соседа на изучаемого пользователя.
В этом плане я даже больше бы Вам посоветовал видеолекции Яндекса по Machine Learning, анонсированные зимой на Хабре. Там в одной из лекций это было довольно подробно рассказано (номер не помню, извините).
А что такое схожесть? Линейное соотношение одного score к другому?
Вы можете сделать MapReduce для начального расчета и обновления оценок, запихать оценку в item и искать по вхождению в некий диапазон.
Главное - полный пересчет каждый раз не делать.
@AMar4enko Скорее разница по модолю между двумя оценками предметов (потом ещё и делённая на количество оценок). Т.е. непонятно как это вычислить, если в MapReduce, values я могу считать только от одной записи в базе данных, когда мне нужно брать разницу между парами.
{Вася, Балтика 7, 4}
{Вася, Балтика 3, 3}
{Петя, Балтика 7, 5}
{Петя, Балтика 3, 4}
Тут расстояние между Балтика 7 и Балтика 3 (обратное от похожести) будет ((4-3) + (5-4))/2 = 1.
Вы просто формулу замороченную написали и она вас в заблуждение ввела.
Вам всего лишь надо сделать (5 + 4)/2 - (4 + 3)/2, смысл тот же. Получается, что первое это усредненная оценка для первого продукта, второе - для второго.
Т.е. вам для решения вашей задачи надо написать MapReduce, который запишет в каждый продукт усредненную оценку и все, потом делайте по этим оценкам любые выборки.
Средний
Средний
Простой
