Рекомендательные системы — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 72: Строка 72:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''SVD''' (''Single Value Decomposition'') {{---}} у любой матрицы <tex> A </tex> размера <tex> n \times m </tex> существует разложение трех матриц: <tex> U, \Sigma, V^T </tex>:
+
'''SVD''' (''Single Value Decomposition'') {{---}} у любой матрицы <tex> A </tex> размера <tex> n \times m </tex> существует разложение трех матриц: <tex> U, \Sigma, V^T </tex>. Матрицы <tex> U, V </tex> ортогональные, а <tex> \Sigma </tex> - диагональная.
  
 
<tex> A_{n \times m} = U_{n \times n} \times \Sigma_{n \times m} \times V^T_{m \times m} </tex>
 
<tex> A_{n \times m} = U_{n \times n} \times \Sigma_{n \times m} \times V^T_{m \times m} </tex>
  
 
}}
 
}}
 +
 +
<tex> UU^T = I_n</tex>,  <tex>VV^T = I_m</tex>
 +
 +
<tex> \Sigma = diag(\lambda_1, ..., \lambda_{min(n, m)})</tex>, <tex>\lambda_1 \geq ... \geq \lambda_{min(n, m)} \geq 0 </tex>
 +
 +
Обратить внимание же стоит на усеченное разложение, когда из лямбд, остаются только первые <tex> d </tex> чисел, а остальные полагаем, что равны нулю.
 +
 +
<tex> \lambda_{d+1}, ..., \lambda_{min(n,m)} := 0 </tex>
 +
 +
Значит у матриц <tex> U </tex> и <tex> V </tex> остаются только первые <tex> d </tex> столбцов, а матрица <tex> \Sigma </tex> становится квадратной размером <tex> d \times d </tex>.
 +
 +
<tex> A'_{n \times m} = U'_{n \times d} \times \Sigma'_{d \times d} \times V'^T_{d \times m} </tex>
 +
 +
Получаем наилучшее низкоранговое приближение с точки зрения средне-квадратичного отклонения.
 +
 +
Чтобы предсказать оценку пользователя <tex> U </tex> для объекта <tex> I </tex>, берём некотрый вектор <tex> p_u </tex> для данного пользователя и вектор данного объекта <tex> q_i </tex>. Получаем необходимое предсказание: <tex> \hat{r_{ui}} = \langle p_u,q_i \rangle </tex>.
 +
 +
Помимо предсказания оценок, алгоритм позволяет выявлять скрытые признаки объектов и интересы пользователей.
 +
 +
Одна есть и свои проблемы:
 +
 +
*<tex> R </tex> матрица оценок полностью не известна, поэтому просто взять SVD разложение не получится.
 +
*SVD разложение не единственное, поэтому даже если какое-то разложение будет найдено, нет гарантии, что первая координата в нем будет соответствовать некоторым выбранным характеристикам пользователя.
 +
 +
==Решение проблемы матрицы оценок==

Версия 14:03, 25 марта 2020

Рекомендательные системы - программы, которые пытаются предсказать, какие объекты будут интересны пользователю, имея определенную информацию о его профиле.

Обзор и постановка задачи

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

  • Предмет рекомендации.
  • Цель рекомендации.
  • Контекст рекомендации.
  • Источник рекомендации.
  • Степень персонализации.
  • Прозрачность.
  • Формат рекомендации.
  • Алгоритмы.

В центре таких систем лежит матрица предпочтений. В этой матрице одна из осей отвечает за пользователей, вторая за обхекты рекомендации. Заполнена же эта матрица значениями по заданной шкале (например от 1 до 5). Каждый клиент с малой долей вероятностью оценивал все объекты рекомендации, поэтому задача системы - это обобщение информации и предсказание, какое отношение к рекомендуемому обхекту будет у пользователя.

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

  • явно (explicit ratings)
  • неявно (implicit ratings)

Очевидно, что явное оценивание лучше, так как сам пользователь определяет насколько ему интересен тот или иной объект, однако из-за непостоянства в получении явных оценок от пользователей, на практике используется оба подхода.

Формализуем задачу. Имеется множество пользователей [math] u \in U [/math], множество объектов [math] i \in I [/math] и множество событий [math] (r_{ui}, u, i, ...) \in D [/math] (действия, которые совершают пользователи с объектами). Каждое событие задается пользователем [math] u [/math], объектом [math] i [/math], своим результатом [math] r_{ui} [/math] и, возможно, но не обяхательно, другими харакетристиками. По итогу требуется:

  • предсказать предпочтение: [math] \hat{r_{ui}} = Predict(u, i, ...) \approx r_{ui} [/math]
  • персональные рекомендации: [math] u \mapsto (i_1, ..., i_k) = Recommend_k(u, ...) [/math]
  • похожие объекты: [math] u \mapsto (i_1, ..., i_M) = Similar_M(i) [/math]

Кластеризация пользователей

Определение:
Коллаборативная фильтрация (англ. collaborative filtering) — это один из методов построения прогнозов (рекомендаций) в рекомендательных системах, использующий известные предпочтения (оценки) группы пользователей для прогнозирования неизвестных предпочтений другого пользователя.


Основная идея метода - похожим пользователям нравятся похожие объекты.

Алгоритм можно разбить на следующие шаги:

  • Выберем условную меру схожести пользователей по истории их оценок [math] sim(u, v) [/math]
  • Объеденим пользователей в группы так, чтобы похожие пользователи оказывались в одном кластере [math] u \mapsto F(u) [/math]
  • Оценку пользователя предскажем как среднюю оценку кластера этому объекту [math] \hat{r_{ui}} = \frac{1}{|F(u)|}\sum_{u \in F(u)}{}{r_{ui}} [/math]

Проблемы алгоритма:

  • Нечего рекомендовать новым пользователям, их невозможно определить к какому-нибудь кластеру,а значит и рекомендовать им нечего.
  • Не учитывается контекст и специфика пользователя.
  • Если в кластере нет оценки объекта, то предсказание невозможно.

User-based и item-based алгоритмы

Заменим жесткую кластеризацию на предположение, что фильм понравится пользователю, если он понравился его друзьям.

[math] \hat{r_{ui}} = \bar{r_u} + \frac{\sum_{v \in U_i}{}{sim(u, v)(r_{vi} - \bar{r_v})}}{\sum_{v \in {U_i}}{}{sim(u, v)}} [/math]

Однако у этого алгоритма есть недостатки:

  • Холодный старт.
  • Нечего рекомендовать новым/нетипичным пользователям.

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

[math] \hat{r_{ui}} = \bar{r_i} + \frac{\sum_{j \in I_u}{}{sim(i, j)(r_{uj} - \bar{r_j})}}{\sum_{j \in {I_u}}{}{sim(i, j)}} [/math]

У такого подхода остается недостаток в виде холодного старта и при этом рекомендации становятся тривиальными.

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

Алгоритм SVD

Определение:
SVD (Single Value Decomposition) — у любой матрицы [math] A [/math] размера [math] n \times m [/math] существует разложение трех матриц: [math] U, \Sigma, V^T [/math]. Матрицы [math] U, V [/math] ортогональные, а [math] \Sigma [/math] - диагональная. [math] A_{n \times m} = U_{n \times n} \times \Sigma_{n \times m} \times V^T_{m \times m} [/math]


[math] UU^T = I_n[/math], [math]VV^T = I_m[/math]

[math] \Sigma = diag(\lambda_1, ..., \lambda_{min(n, m)})[/math], [math]\lambda_1 \geq ... \geq \lambda_{min(n, m)} \geq 0 [/math]

Обратить внимание же стоит на усеченное разложение, когда из лямбд, остаются только первые [math] d [/math] чисел, а остальные полагаем, что равны нулю.

[math] \lambda_{d+1}, ..., \lambda_{min(n,m)} := 0 [/math]

Значит у матриц [math] U [/math] и [math] V [/math] остаются только первые [math] d [/math] столбцов, а матрица [math] \Sigma [/math] становится квадратной размером [math] d \times d [/math].

[math] A'_{n \times m} = U'_{n \times d} \times \Sigma'_{d \times d} \times V'^T_{d \times m} [/math]

Получаем наилучшее низкоранговое приближение с точки зрения средне-квадратичного отклонения.

Чтобы предсказать оценку пользователя [math] U [/math] для объекта [math] I [/math], берём некотрый вектор [math] p_u [/math] для данного пользователя и вектор данного объекта [math] q_i [/math]. Получаем необходимое предсказание: [math] \hat{r_{ui}} = \langle p_u,q_i \rangle [/math].

Помимо предсказания оценок, алгоритм позволяет выявлять скрытые признаки объектов и интересы пользователей.

Одна есть и свои проблемы:

  • [math] R [/math] матрица оценок полностью не известна, поэтому просто взять SVD разложение не получится.
  • SVD разложение не единственное, поэтому даже если какое-то разложение будет найдено, нет гарантии, что первая координата в нем будет соответствовать некоторым выбранным характеристикам пользователя.

Решение проблемы матрицы оценок