Рекомендательные системы
Рекомендательные системы - программы, которые пытаются предсказать, какие объекты будут интересны пользователю, имея определенную информацию о его профиле.
Содержание
Обзор и постановка задачи
Основная задача рекомендательных систем - проинформировать пользователя о товаре или услуге, которая будет для него наиболее инетерсной и акутальной. Разнообразие таких систем можно проиллюстрировать основными характеристиками:
- Предмет рекомендации.
- Цель рекомендации.
- Контекст рекомендации.
- Источник рекомендации.
- Степень персонализации.
- Прозрачность.
- Формат рекомендации.
- Алгоритмы.
В центре таких систем лежит матрица предпочтений. В этой матрице одна из осей отвечает за пользователей, вторая за обхекты рекомендации. Заполнена же эта матрица значениями по заданной шкале (например от 1 до 5). Каждый клиент с малой долей вероятностью оценивал все объекты рекомендации, поэтому задача системы - это обобщение информации и предсказание, какое отношение к рекомендуемому обхекту будет у пользователя.
Пользовательские оценки, необходимые для составления матрицы предпочтений, можно получить двумя способами:
- явно (explicit ratings)
- неявно (implicit ratings)
Очевидно, что явное оценивание лучше, так как сам пользователь определяет насколько ему интересен тот или иной объект, однако из-за непостоянства в получении явных оценок от пользователей, на практике используется оба подхода.
Формализуем задачу. Имеется множество пользователей
, множество объектов и множество событий (действия, которые совершают пользователи с объектами). Каждое событие задается пользователем , объектом , своим результатом и, возможно, но не обяхательно, другими харакетристиками. По итогу требуется:- предсказать предпочтение:
- персональные рекомендации:
- похожие объекты:
Кластеризация пользователей
Определение: |
Коллаборативная фильтрация (англ. collaborative filtering) — это один из методов построения прогнозов (рекомендаций) в рекомендательных системах, использующий известные предпочтения (оценки) группы пользователей для прогнозирования неизвестных предпочтений другого пользователя. |
Основная идея метода - похожим пользователям нравятся похожие объекты.
Алгоритм можно разбить на следующие шаги:
- Выберем условную меру схожести пользователей по истории их оценок
- Объеденим пользователей в группы так, чтобы похожие пользователи оказывались в одном кластере
- Оценку пользователя предскажем как среднюю оценку кластера этому объекту
Проблемы алгоритма:
- Нечего рекомендовать новым пользователям, их невозможно определить к какому-нибудь кластеру,а значит и рекомендовать им нечего.
- Не учитывается контекст и специфика пользователя.
- Если в кластере нет оценки объекта, то предсказание невозможно.
Холодный старт
Определение: |
Холодный старт — ситуация, когда ещё не накоплено достаточное количество данных для корректной работы рекомендательной системы. |
Данная проблема актуальна для новых объектов или объектов, которые редко покупают. Если средний рейтинг посчитан по оценкам всего трёх пользователей, такая оценка явно не будет достоверной, и пользователи это понимают. Часто в таких ситуациях рейтинги искусственно корректируют.
Первый способ – показывать не среднее значение, а сглаженное среднее (Damped Mean). Смысл таков: при малом количестве оценок отображаемый рейтинг больше тяготеет к некому безопасному «среднему» показателю, а как только набирается достаточное количество новых оценок, «усредняющая» корректировка перестает действовать.
Другой подход – рассчитывать по каждому рейтингу интервалы достоверности (Confidence Intervals). Математически, чем больше оценок, тем меньше вариация среднего и, значит, больше уверенность в его корректности. А в качестве рейтинга можно выводить, например, нижнюю границу интервала (Low CI Bound). При этом понятно, что такая система будет достаточно консервативной, с тенденцией к занижению оценок по новым товарам.
User-based и item-based алгоритмы
Заменим жесткую кластеризацию на предположение, что фильм понравится пользователю, если он понравился его друзьям.
Однако у этого алгоритма есть недостатки:
- Холодный старт.
- Нечего рекомендовать новым/нетипичным пользователям.
Так же имеется абсолютно симметричный алгоритм. Теперь будем считать, что фильм понравится пользователю, если ему понравились похожие фильмы.
У такого подхода остается недостаток в виде холодного старта и при этом рекомендации становятся тривиальными.
Так же стоит отметить ресурсоемкость вычислений такими методами. Для предсказаний необходимо держать в памяти все оценки всех пользователей.
Алгоритм SVD
Определение: |
SVD (Single Value Decomposition) — у любой матрицы | размера существует разложение трех матриц: . Матрицы ортогональные, а - диагональная.
,
,
Обратить внимание же стоит на усеченное разложение, когда из лямбд, остаются только первые
чисел, а остальные полагаем, что равны нулю.
Значит у матриц
и остаются только первые столбцов, а матрица становится квадратной размером .
Получаем наилучшее низкоранговое приближение с точки зрения средне-квадратичного отклонения.
Чтобы предсказать оценку пользователя
для объекта , берём некотрый вектор для данного пользователя и вектор данного объекта . Получаем необходимое предсказание: .Помимо предсказания оценок, алгоритм позволяет выявлять скрытые признаки объектов и интересы пользователей.
Одна есть и свои проблемы:
- матрица оценок полностью не известна, поэтому просто взять SVD разложение не получится.
- SVD разложение не единственное, поэтому даже если какое-то разложение будет найдено, нет гарантии, что первая координата в нем будет соответствовать некоторым выбранным характеристикам пользователя.
Решение проблемы матрицы оценок
Модель будет зависить от ногих параметров - вектора пользователей и вектора объектов. Для заданных парметров, возьмем вектор пользователя, вектор объекта и получим их скалярное произведение, чтобы предсказать оценку:
,
Но вектора пока не известны, их нужно получить. Имеются оценки пользователей, при помощи которых можно можно найти оптимальные параметры, при которых модель предскажет оценки наилучших образом:
То есть, нужно найти такие параметры
, чтобы квадрат ошибки был наименьшим. Однако ситуация следующая: оптимизация приведет к наименьшим ошибкам в будущем, но как именно оценки будут спрашивать - неизвестно. Следовательно, это нельзя оптимизировать. Однако, так как оценки уже проставленные пользователями известны, постараемся минимизировать ошибку на тех данных, что у нас уже есть. Так же добавим регуляризатор.
Определение: |
Регуляризация (англ. regularization) в статистике, машинном обучении, теории обратных задач — метод добавления некоторых дополнительных ограничений к условию с целью решить некорректно поставленную задачу или предотвратить переобучение. Чаще всего эта информация имеет вид штрафа за сложность модели. |
Регуляризация заключается в том, что минимизируется не только ошибка, но и некоторая функция параметров (например, норма вектора параметров). Это позволяет ограничить размер параметров в решении, уменьшает степень свободы модели.
Численная оптимизация
Необходимо оптимизировать данный функционал. Множество параметров: для каждого объекта и пользователя есть свой вектор, который нужно оптимизировать. Дабы найти минимум функции воспользуемся градиентом - вектор из частных производных по каждомц параметру.
Можно воспользоваться градиентным бустингом:
Проблема же заключается в том, что алгоритм работает медленно, а минимумы которые он находит - локальные, а не глобальные.
Измерение качества рекомендаций
Было предложено измерять качество рекомендаций при помощи RMSE:
Однако она также обладает недостатками, хоть и является стандартом измерения качества:
- Пользователи с большим разбросом оценок будут влиять на значение метрики больше, чем остальные.
- Ошибка в предсказании высокой оценки имеет такой же вес, что и ошибка в предсказании низкой оценки.
- Есть риск плохого ранжирования при почти идельаной RMSE и наоборот.
Существуют при этом и другие метрики - метрики ранжирования, на основе полноты и точности. Однако они не так популярны и используются значительно реже.