Как я сделал простую рекомендательную систему на Ruby и Redis

и узнал много нового аниме

Коллаборативная фильтрация — это весело. Именно по такому принципу работают рекомендательные системы на многих сайтах и приложениях

Вкратце её можно описать так:

Если Пете нравятся “A”, “B” и “C”, а Васе нравятся “A”, “B”, “C” и “D” то, вероятно, Пете тоже понравится “D”

В качестве предмета для рекомендаций я решил выбрать мангу и аниме, благо, недавно я нашел весьма подходящий источник пользовательских оценок

Shikimori — это сайт-энциклопедия аниме и манги, с плюшками вроде оценок и отслеживания просмотренных эпизодов

Походив по сайту, поотмечав просмотренные тайтлы, я решил получить рекомендаций, и тут меня ждал облом:

Собираем данные

Поразмыслив и решив, что с моей скоростью просмотра/чтения нужный объем я наберу где-то через пару месяцев, я подумал: а почему бы и да?

Весьма быстро на сайте нашлось подходящее открытое API, а после общения с администратором, оно еще и разжилось парой нужных параметров, позволяющих получать оценки для конкретных тайтлов, а не только для конкретных пользователей

Для начала, я написал простой парсер на Ruby и Faraday, который делает следующее:

1. Парсит все мои оценки
2. Получает иды всех всех пользователей, попадающих под критерии
3. Получает оценки этих пользователей
4. Сохраняет все это в текстовики в формате user_id:type:item_id:score

Я выбрал несколько критериев для парсинга оценок:

• Пользователь смотрел то же, что и я
• Пользователь оценил просмотренное (score > 0)
• Тайтл не находится в отложенных (status != planned)
• Пользователь отметил, что прочитал/просмотрел хотя бы один эпизод/главу/часть (episodes > 0 || volumes > 0 || chapters > 0)
• Пользователь был онлайн за последние 30 дней

Изначально я хотел прогнозировать оценки, которые пользователь даст тем или иным непросмотренным тайтлам, и даже переписал реализацию такой системы от RedisLabs, использующую Redis, с Go на Ruby. Но когда я увидел результаты, до меня плавно дошло, что конкретно та реализация не очень хорошо дружит с моими данными, так что я решил воспользоваться более простым подходом:

Поделить оценки на “лайки” и “дизлайки” в зависимости от рейтинга. Благо, сходу нашелся весьма простой алгоритм для таких данных

Поскольку shikimori лимитирует число запросов к API и ждать, пока спарсятся 21000 человек я не отважился, я собрал оценки примерно 1500 пользователей, смотревших то же, что и я, а так же слегка разбавил их оценками еще около 350 случайных пользователей из числа активных.

Собрав оценки, я решил поделить их следующим образом и запихать в Redis:

Всё, что оценено на 6 и выше — лайки, всё, что оценено на 5 и ниже — дизлайки

Всего, с примерно 1934 пользователей, у меня получилось более 300000 оценок на 11910 тайтлах

Алгоритм

DISCLAIMER: Я — удивительно безграмотный как в математике, так и в рекомендательных системах человек, так что прошу не бить ногами за очевидные ошибки и неточности

Но буду безумно рад, если вы меня поправите в комментах и предложите свои оптимизации/улучшения/эвристики

Алгоритм основан на магии множеств и несколько модифицированном коэффициенте сходства Жаккара, вот так выглядит его исходный вариант:

Wikipedia: Коэффициент сходства

В нашем случае, A и B — множества того, что оценили пользователи A и B соответственно.

Переводя с математики на русский: мы делим количество схожих оцененных предметов у пользователей на количество оцененных предметов этих двух пользователей.

Поскольку, у нас не только лайки, но и дизлайки, формула превращается в такую:

Тут добавляется деление на лайки (L) и дизлайки (D)

По сути, отличается она тем, что сходство зависит от взаимных лайков, дизлайков, а так же, коэффициент понижается, если мнения в чем-то не сошлись

Подробнее обо всех метаморфозах этой формулы можно прочитать вот здесь: https://davidcel.is/posts/collaborative-filtering-with-likes-and-dislikes/ (именно там я её нашел)

При помощи этой формулы, мы определяем степень сходства двух пользователей. Формула принимает значения от 1.0, если другому пользователю понравилось всё то же самое что и нам до -1.0, если мнения совершенно разошлись

Для полного счастья нам не хватает еще одной формулы, она будет вычислять вероятность, с которой пользователю понравится или не понравится предложенный предмет:

Обозначения:

nL — количество пользователей, оценивших предмет положительно

nD — количество пользователей, оценивших предмет отрицательно

Что здесь происходит?

1. У нас есть пользователь (user) и предмет, который нам вероятно понравится (thing)
2. Сначала мы берем всех других пользователь, кому понравился предмет, и суммируем сходство с ними (сходство user с пользователем 1 + сходство user с пользователем 2 + …)
3. Проделываем то же самое для тех, кому не понравился этот предмет
4. Отнимаем второе от первого
5. Делим полученное число на количество оценивших

Звучит весьма просто, не так ли?

В дело вступает Redis

Как вы могли заметить, наш алгоритм активно использует множества, так что, почему бы нам не взять и не запихать всё это дело в Redis?

У Redis’а весьма богатый функционал для работы с множествами, поэтому, весьма логично будет запихать всё это дело туда

Бегло окинем взглядом наши формулы и составим список того, что нам нужно хранить:

1. Лайки пользователя
2. Дизлайки пользователя
3. Все оцененные пользователем предметы (лайки + дизлайки)
4. Кто лайкал предметы
5. Кто дизлайкал предметы
6. Все оценки предмета

Кроме этого, в самом ключе я решил указывать некий префикс-категорию, чтобы разделить оценки для аниме и манги (мы же помним, что наша цель — получить рекомендации именно по ним?)

Бонусом, хоть это и не требуется для реализации, я храню следующее:

1. Все итемы
2. Все пользователи
3. Все категории

Как оно всё выглядит в коде

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

Начнем с двух методов, которые добавляют наши оценки в редис:

Смотрим на нашу функцию, считающую коэффицент и реализуем её по кускам

Сперва, количество итемов, оцененных двумя пользователями (пересечение множеств и количество итемов в результате)

Затем, отдельные для лайки-лайки, дизлайки-дизлайки, лайки-дизлайки

Теперь можно реализовать и метод, считающий коэффициент:

Далее, несколько хелперов для предиктора:

Метод, возвращающий сумму коэффицентов для данного массива пользователей:

И, наконец, сам предиктор:

И так, теперь у нас есть метод, предсказывающий, понравится нам определенный итем или нет. Осталось собрать похожих пользователей, узнать, что они смотрели, посчитать, насколько эти итемы нам понравятся

Для начала найдем похожих пользователей:

Здесь мы просто ищем тех, кто лайкал то же, что и мы и считаем коэффициент похожести

Затем, узнаем что же эти пользователи лайкают:

Ну и всё вместе:

Немного поигравшись с рекомендациями, я сделал несколько вещей:

1. Спарсил еще 3000 рандомных и 2500 смотревших-то-же-что-и-я пользователей
2. Подвинул порог лайка с 7 до 6
3. Добавил кеширование для similarity

Методом “на глаз” было выяснено, что даже с таким небольшим количеством оценок как у меня, оно выдает вполне себе релевантные вещи

Конечно, это далеко не самый идеальный и уж точно не самый быстрый способ построения рекомендаций, но точно один из самых простых в реализации

Буду неимоверно рад, если вы предложите свои замечания и улучшения представленному здесь безобразию :)

GitHub с кодом / Контакты / Накормить меня кофе