Рекомендательные системы: You can (not) advise

Более полугода назад в поисках что посмотреть, я листал топ произведений. Это занятие повторялось уже много раз и успело надоесть — постоянно приходилось пропускать то, что я смотреть не хочу. Имхонетами раньше не пользовался, да и не доверял им из-за специфики искомых произведений. На сайте, где я производил поиски, была возможность создать свой список просмотренных произведений и выставить оценку, также были доступны оценки других пользователей. Тут мне в голову пришла гениальная идея, как оказалось позднее банальная, — используя оценки других пользователей делать рекомендации. Данная деятельность называется коллаборативной фильтрацией, а программа её реализующая — Рекомендательной системой(РС). Оглядываясь назад я понимаю, что совершил множество ошибок из-за недостатка информации и её труднодоступности в данной тематике, а что самое главное — сильно переоценил РС. В данном посте я сделаю обзор основных типов и алгоритмов РС, а также постараюсь передать часть своих знаний и опыта.

Рекомендательная система — это программа, которая на основе данных о пользователе(User) и предмете(Item) дает рекомендации.
Такая система включает в себя весь процесс — от получения информации до её представления пользователю.
Важен каждый этап. От информации, которую вы будете собирать зависит, какие алгоритмы вы сможете применить. Хорошие алгоритмы дают хорошие, полезные рекомендации. Критерии оценки результата позволяют выбрать наиболее подходящие алгоритмы. И это ничего не работает, если правильно не представить и не объяснить совет пользователю. Я расскажу про алгоритмы, но не забывайте и про остальные части системы.

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

Тестовые данные

На сайте, где я брал данные, десяти бальная система оценивания, около миллиона пользователей и 30к предметов.
Можно конечно начинать как я, просто брать алгоритм и делать, но скоро вы поймете, что это плохая идея. После реализации нескольких видов систем возникают вопросы — какой вид выбрать, чего мы добились и можно ли сделать лучше? Для ответа на эти вопросы необходимо проводить оценку результатов по каким-нибудь критериям.
Нужно создать равные условия для всех алгоритмов — зафиксировать некоторые данные при помощи которых алгоритмы будут делать свои предсказания и найти какой-то эталонный результат с которым можно сравнивать полученные предсказания.

Помните, что придется тестировать множество алгоритмов с различными опциями и желательно этот процесс максимально ускорить. Когда мы уже выбрали алгоритм мы можем использовать все данные, но до этого для ускорения опытов нужно взять только их часть. Это тоже наука, называется sampling.
В моем случае все было просто — я уже имел множество оценок пользователей и как показали результаты, при использовании 100%, 25% и 10% данных результаты практически не изменялись, поэтому все свои опыты я проводил на 10%. Из 200к пользователей(30кк оценок) с количеством оценок больше пяти я случайным образом выбрал 30к пользователей(3кк оценок). Оценки каждого пользователя разделил на два набора по следующему алгоритму — если оценок больше десяти, то первые шесть оценок(сделанных раньше по времени) я переносил в обучающую выборку, а последние шесть убирал в тестовую выборку(эталонную), если меньше десяти, то в тестовую выборку попадало меньше оценок.

Производительность

Для проведения исследования порой приходится перезапускать алгоритм сотни раз изменяя параметры, и что же будет если один расчет занимает несколько часов? Правильно — очень сильный персонаж в Террарии, но это не было главной моей цель.
Первоначально все алгоритмы писались на Питоне, так как я знаю этот язык лучше всего, но потом многое пришлось переписать на Java, которая работала до двадцати раз быстрее и потребляла значительно меньше ОП(в основном благодаря примитивным типам и массивам). Java была выбрана лишь потому, что по изученности она стоит у меня на втором месте. Возможно мое решение проблемы не самое лучшее( в numpy и scipy многое реализовано нативно, есть множество специализированных фреймворков и языков), но мне было интереснее все сделать самому.
Еще были проблемы с хранением данных — сериализация не подходила, так как иногда нужно было данные из питона перебросить в джаву и наоборот, SQL был не удобен, а потом я встретил MongoDB. Она мне идеально подошла. Опять таки велика вероятность, что это не самое лучшее решение и возможно нужно использовать какой-нибудь Hadoop.
Расчет SVD на Java на полном объеме данных в итоге занимает примерно десять минут и потребляет 2Гб памяти. А вот для SVD++ уже нужно подождать около часа.

Критерии оценки РС

Прежде чем рассматривать типы РС необходимо поговорить о критериях оценки результата.
Существует множество различных критериев по которым можно оценивать рекомендательную систему — такие как точность, новизна, возможность удивлять, устойчивость к атакам, зависимость от холодного старта, убедительность и так далее, но одним из наиболее важных все-таки является — точность. Она показывает на сколько наши предсказания близки к эталонному результату. Для измерения точности есть множество методов, рекомендую подойти к выбору аккуратно, так как от этого многое зависит. Я взял один из самых популярных методов — расчет среднеквадратичной ошибки (RMSE). После того как на основе тестовых данных алгоритм производит предсказания, ошибку можно вычислить по следующей формуле:

u — пользователь
i — предмет
r — оценка
p — предсказанная оценка
T — общее количество тестовых оценок
чем меньше тем лучше

В дальнейшем я буду указывать точность для алгоритмов в rmse.
Как показала практика меньше rmse не всегда значит лучше алгоритм. Лучших результатов rmse мне удалось добиться с алгоритмом timeSVD++ — 1.29, для рекомендательной системы основанной на знаниях 1.41(где пользователи саму указывали зависимости). Вторая система субъективно дала мне несколько очень хороших советов, которых первая система не нашла.

Более подробно про критерии можно почитать в Recommendation System Handbook, которую я указал в разделе литература.

Отправной точкой своего исследования я взял результат который получается если предсказанную оценку взять как среднюю оценку предмета — тогда rmse будет равно 1.53. Сделано так потому, что для получения этой оценки практически ничего не нужно делать и очень часто она у нас уже есть. Посмотрим на сколько мы сможем превзойти этот результат.

Типы РС

Существует четыре основных типа рекомендательных систем:

• Основанные на контенте(Content base)
• Коллаборативные(Collaboration)
• Основанные на знаниях(Knowlege base)
• Гибридные

РС основанные на контенте

Основные шаги в данной системе: проанализировать контент предметов и составить набор его критериев(жанры, тэги, слова), узнать какие критерии нравится пользователю, сопоставить эти данные и получить рекомендации. Критерии объединяют пользователей и предметы в единой системе координат, а тут уже все просто — если точка пользователя и предмета рядом, то вероятно предмет понравится пользователю.
Одним из самых простых видов этой системы является жанровая система, здесь наши критерии — жанры.
Моя жанровая РС показала результат 1.48, что немного лучше чем если просто брать среднюю оценку. Но не все так плохо — жанровая система, объединенная со средней оценкой в гибридную систему показала результат 1.40. Такую систему очень просто сделать.

Еще один вид этой РС использует слова описывающие предмет. На сайте где я брал информацию, есть раздел с описаниями предмета. Я взял эти данные и прогнал через алгоритм tf-idf(который позволяет определить схожесть двух текстов) в результате получилось 1.46.

Как видно данный вид РС при использовании базовых алгоритмов не дает большой точности, но зато у него есть другие плюсы: высокая производительность, более теплый «холодный старт», для получения рекомендации нужны только данные о пользователе и предметах.
Очень часто эти системы используют до коллаборативной фильтрации, когда оценок пользователей еще не достаточно.
Про данный вид РС также рекомендую почитать в Recommendation System Handbook или на хабре .

Коллаборативные РС

Это системы в которых рекомендации пользователю рассчитывается на основе оценок других пользователей. Здесь существует множество алгоритмов, но наиболее популярные — User/User(ищем соседей по оценкам), Item/Item(ищем схожесть предметов по оценкам пользователей) и SVD(самообучающийся алгоритм). Все они описаны на хабре — User/User&Item/Item, SVD и в Recommendation System Handbook. Если вы решили создавать коллаборативную РС рекомендую присмотреться к алгоритму SVD, у него наилучшая точность, высокая производительность и низкое потребления памяти.

При выборе User/User или Item/Item необходимо учитывать кого больше — пользователей или предметов. Если больше пользователей, то предпочтительнее Item/Item, если наоборот то User/User.
Суть этих алгоритмов — нахождение ближайших соседей. Близость двух пользователей или предметов определяется метриками схожести(similarity metrics)
Чаще всего используют косинусную метрику или корреляцию пирсона. На моих данных оба метода давали близкие результаты.

До того как я познакомился с ними я придумал свою метрику сходства:
sim = cross_count / euclid
sim — результат
cross_count — количество пересечений
euclid — евклидово расстояние

На моих тестовых данных она показала себя лучше чем пирсон и косинусная. Это наглядно показывает важность количества пересечений. Предупреждаю! Перед использованием обязательно провести тестирование с использованием других метрик, так как не известно что за скайнет у вас может получится. В дальнейшем я буду указывать результаты без учета этой метрики.

Для User/User лучший результат, который мне удалось добиться был при использовании корреляции пирсона и был равен 1.49. Это даже хуже чем у контентной системы. В основном из-за того, что User/User алгоритм плохо учитывает количество пересечений у пользователя и выдает рекомендации на основе всего нескольких оценок, с этим можно бороться вводя ограничения на минимальное количество пересечений.

Для Item/Item лучший результат также был с Пирсоном — 1.35, что значительно лучше чем User/User. Причина в том, что предметов значительно меньше и при расчете схожести двух предметов у них множество пересечений оценок.

Первый раз когда я реализовал SVD я был в восторге от его работы и с восхищением смотрел как уменьшается ошибка при обучении модели. Всем рекомендую для ознакомления реализовать его.
Я попробовал 3 вида SVD: SVD, SVD++ и timeSVD++. Результаты у меня были следующие:
SVD — 1.30
SVD++ — 1.29
timeSVD++ — 1.29

Как видно данные алгоритмы позволяют добиться наибольшей точности. Из этих трех рекомендую использовать простой SVD, так как он самый производительный. Другие алгоритмы значительно больше требуют времени на выполнение, а точность повышают не значительно.

РС основанная на знаниях

В основном это системы в которых для получения рекомендаций используются полученные каким-либо образом знания, чаще всего эти знания добавляются вручную.
На сайте, где я брал информацию пользователи могли указать предмету другие схожие предметы. На основе этих данных я сделал рекомендации как в Item/Item. В результате получилось — 1.41. Как я уже указывал ранее многие понравившиеся рекомендации этой системы, не смогли найти коллаборативные алгоритмы.

Подробнее об этих РС написано в Recommendation System Handbook.

Гибридные РС

Эти системы объединяют несколько выше представленных алгоритмов в один. Их есть несколько видов, но я сильно не углублялся и использовал простую формулу с весами:
res = w1 * a + w2 * b
w1 — вес для алгоритма a
w2 — вес для алгоритма b
Здесь веса всегда постоянные, но желательно чтобы они были в виде w = f(x), то есть зависящими от каких-то параметров.
Вот небольшой пример для средней оценки и жанрового алгоритма:
w1 w2 — rmse
0.2 0.8 — 1.4330
0.3 0.7 — 1.4173
0.4 0.6 — 1.4092
0.45 0.55 — 1.4083
0.5 0.5 — 1.4095
0.6 0.4 — 1.4180
0.7 0.3 — 1.4347

Как видно два алгоритма с точностью 1.5 позволили получить точности 1.40

Лучшего результата мне удалось с гибридной системой w1*(Item/Item) + w2*(SVD), где w1 = 0.5 и w2 = 0.5. RMSE уменьшилась на 0.01. Данный результат не противоречит тому что получили победители конкурса NetFlix — BellKor. Для победы они использовал гибрид из 27 алгоритмов. Это позволило им достичь точности 0.86, а использование одного SVD — 0.88. В их случае это было необходимо, в моем совершенно не оправдано, так как падает производительность, возрастает сложность, а улучшение результата не значительно.
Можно использовать лучший гибрид, что не сильно усложнит систему, зато немного повысит точность.

Про гибридные системы также подробно описано в Recommender Systems Handbook.

Литература и ссылки

Есть три книги о РС:
Programming Collective Intelligence
Уже устарела, так как была написана до Netflix Prize. Есть примеры на Питоне.

Recommender Systems An Introduction
Средний уровень сложности, больше об РС в целом. Некоторые вещи написаны более подробно чем в следующей книге. Есть описания алгоритмов. Примеров кода нет.

Recommender Systems Handbook
Лучшая книга об РС, здесь есть все. Алгоритмы описаны хорошо, но без примеров реализации — их придется искать на стороне.

Информация в интернете:
На хабре есть блог Surfingbird, они часто пишут об РС

Настоятельно рекомендую материалы об коллаборативной фильтрации BellKor:
BellKor — часть данной информации опубликована в Recommender Systems Handbook

еще есть opensource библиотека для коллаборативной фильтрации, C#:
MyMediaLite Recommender System Library

Вывод

Немного почитав про РС вначале я подумал «как мы жили без этого раньше?», но в последствии оказалось, что даже самые передовые методы дают слабые результаты и нет возможности полностью доверить им выбор. Проведя широкое исследование мне не удалось создать систему, которой бы часто пользовались, а главное — которой бы доверяли, так что я буду продолжать свои исследования.

Этой области еще нет и двадцати лет, она активно развивается и здесь полно задач, где можно проявить себя.
Это очень интересная проблема, после которой я заинтересовался Data Mining'ом и записался на несколько курсов по машинному обучению, посмотрим что из этого получится.

Автор: overmes

Источник