Основы рекомендаций — сводка по совместной фильтрации

1 Обзор

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

2. Алгоритмы

2.1 Окрестность CF

2.1 Принцип

Алгоритм совместной фильтрации на основе соседства является одним из наиболее распространенных алгоритмов для рекомендаций. Преимущества: низкая стоимость реализации, не так легко ошибиться, быстрая скорость расчета, хороший эффект и возможность рекомендовать элементы с длинным хвостом. Недостатком является то, что пользователи и элементы с небольшим числом кликов хвоста склонны к плохой регистрации. «Метод ближайшего соседа» включает в себя «совместную фильтрацию на основе элементов» и «совместную фильтрацию на основе пользователей». «Совместная фильтрация на основе элементов» — на основе элементов относится к поиску других элементов, похожих на элемент а. другие похожие элементы для пользователей. «Совместная фильтрация на основе пользователей» — на основе пользователей относится к поиску других пользователей B, C, D, которые похожи на пользователя A. Если пользователь A и пользователь B имеют схожие предпочтения просмотра, потому что пользователь A и пользователь B имеют схожие зрительские предпочтения Очень похожи, тогда считается, что другие элементы b, которые видел пользователь B, также, вероятно, понравятся пользователю A. Взяв диаграмму Корена в качестве примера для иллюстрации пользовательского метода, Джо нравятся три фильма a, b , c слева, и рекомендует его Джо При поиске фильма найдите похожих на него пользователей A, B и C. Все трое смотрели Фильм 1, Спасти рядового Райана. первый рекомендованный фильм.

2.2 Метод расчета

Возьмем метод базового элемента в качестве примера, чтобы проиллюстрировать, как вычислить сходство между элементами. Предположим, что пользователь А просмотрел или щелкнул элемент a, b (далее в совокупности именуемый кликом), аналогичным образом пользователь B щелкнул элемент b, элемент d, пользователь C щелкнул элемент a, элемент b, элемент c.

	item a	item b	item c	item d
user A	1	1
user B		1		1
user C	1	1	1

Разверните последовательность кликов, чтобы получить матрицу

Найдите элемент-элемент или сходство пользователя и пользователя по косинусному сходству матрицы. В этом примере сходство между элементом a и элементом b является косинусным сходством между вектором (1,1,0,0) и вектором (0,1,0,1). Такой метод прост, быстр и подходит для параллельной обработки на искре.

2.3 Заключение

Будут некоторые «непользовательские клики», то есть поисковые роботы и т. д., которые характеризуются чрезмерными кликами и должны быть удалены.
Среди элементов, хотя мы хотим, чтобы каждый элемент был передан пользователю хотя бы один раз, что хорошо работает для длинного хвоста, в некоторых случаях качество по умолчанию не высокое для тех, у кого особенно мало кликов, и его также можно удалить. .
При вычислении не расширяйтесь в вектор, а отдельно вычисляйте количество вхождений элемента a, количество вхождений элемента b и количество совместных вхождений элемента a и элемента b. Поэтому этот метод подходит для распараллеливания.
Совместная фильтрация по элементам и пользователям выбирается по разным сценариям. Например, на торговой площадке Amazon количество пользователей значительно превышает количество товаров, и предпочтения пользователей сильно меняются, вещи, купленные в разные периоды, неодинаковы, сходство непостоянно, количество элементы относительно малы по сравнению с пользователями, и сходство между элементами более стабильно, поэтому чаще используется элемент на основе.

2. OCF (заказ-ср)

2.1 Принцип

Item-CF предназначен для расчета сходства между элементом и элементом после получения полного объема информации и одинаковой обработки всех элементов, на которые нажали, без учета порядка щелчков. OCF учитывает порядок последовательности кликов. Например, в новостном сценарии статья B, на которую нажали после того, как нажали на статью A, более релевантна статье A, чем статья C, на которую нажали до статьи A.

2.2 Метод расчета

s(i,j)=\frac{\sum_N{order(i,j)}}{click(i)·click(j)}

символ	значение
i,j	item
order(i,j)	В определенной транзакции j клик после i записывается как 1, в противном случае он записывается как 0
click(i)	Общее количество кликов по мне
N	Общее количество транзакций

2.3 Улучшение ОСФ

В приведенном выше методе по умолчанию все клики после статьи A одинаково важны. Однако интересы пользователей часто меняются с течением времени. Например, после нажатия для просмотра статьи а статья б, на которую нажимают сразу, может быть более похожей, чем статья в, на которую нажимают после 10 статей. Потому что с увеличением статей интерес пользователя может постоянно передаваться. На основе приведенных выше предположений предлагается oicf, основанный на гипотезе местоположения, и формула выглядит следующим образом:

s(i,j)=\frac{\sum_{N,p}\alpha_p·{order(i,j)}}{click(i)·click(j)}

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

3. SCF

3.1 Принцип

Этот метод взят из статьи Али «Инженерная реализация алгоритма рекомендаций в реальном времени SWING на основе структуры графа». Предположим, как показано на рисунке ниже

Пользовательский набор — [a, b, c, d, e], а набор элементов — [s, r, p, q, w, z, t, x], и должны быть рассчитаны элементы, подобные s. пользователя и предмет можно рассматривать как двудольный граф В этом двудольном графе нет треугольников, но есть много угловых структур в форме качелей, таких как (a, r, b), образующих качели, (a, p ,c) также представляет собой свинг. Эта свинговая структура дает больше информации, чем реберная структура (e,w). Например, когда несколько пользователей нажимают на r, они нажимают только на p, тогда r и p должны быть сильно связаны. Если формируется свинг между двумя парами пользователей и множеством элементов, то меньший вес присваивается каждому узлу на этих элементах.

3.2 Расчет

s(i,j)=\sum_{u{\in}U_i{\bigcap}U_j}\sum_{v{\in}U_i{\bigcap}U_j}\frac{1}{\alpha+|I_u{\bigcap}I_v|}

символ	значение
i,j	item
u,v	user
$\alpha$	параметр
	Коллекция пользователей, которые нажали на i
	Совокупность пользователей, которые нажали на j

SCF больше использует коллективный разум пользователя

3.3 Заключение

Из формулы видно, что если больше людей нажмут i и j одновременно, s(i,j) больше. Многие пользователи переходят на пошлые статьи, и их легко вывести на передний план, поэтому SCF легко стать популярным и пошлым. Его можно контролировать и решать другими средствами. Элемент, на который нажимает пользователь, составляет не более нескольких сотен в день, при подсчете это не является большой проблемой. Однако на элемент будут нажимать миллионы или даже десятки миллионов пользователей, и эти пользователи составят пару для расчета, поэтому это займет много времени. Здесь нужна некоторая оптимизация. Ключом к оптимизации является комбинация (u1, u2).

Карта трансляции (элемент, список пользователей) и Карта (пользователь, список элементов);
Поместите RDD (u1, i1) -> RDD (u1, itemList) -> RDD ((i1, i2), u) -> RDD ((i1, i2), (u1, u2)) -> вычислите каждую пару ( i1 , i2) оценка -> сумма по ключу (i1, i2)
Другое улучшение заключается в том, что вы можете вычислять только (userA, userB), потому что score(A,B)=score(B,A) , писать (userA, userB, score) и (userB, userA, score) при сохранении.

4. Матричное разложение ФМ

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

4.1 Основное преобразование матрицы

Суть матричного преобразования — это функция, в отличие от обычных функций, матричное преобразование получает вектор и выдает вектор. То есть вектор перемещается в другой вектор, а исходный единичный вектор перемещается в новую позицию. Например, есть вектор $\vec v$ До преобразования $\vec v =\left[ \begin{matrix} -1\\ 2 \end{matrix} \right]= -1 \vec i+ 2\vec j$ после преобразования $Transformed \vec v = -1 Transformed\vec i + 2Transformed\vec j$ Предположение $Transformed \vec i = \left[ \begin{matrix} 3\\ 1 \end{matrix} \right]$ , $Transformed \vec j = \left[ \begin{matrix} 1\\ 2 \end{matrix} \right]$ , получить $Transformed\vec v=-1\left[ \begin{matrix} 3\\ 1 \end{matrix} \right]+2\left[ \begin{matrix} 1\\ 2 \end{matrix} \right] = \left[ \begin{matrix} -1\\ 3 \end{matrix} \right]$ То есть, если преобразовать $\vec i$ и $\vec j$ Определяется положение , т. е. новая система отсчета координат, и может быть получен любой вектор в этом пространстве. $\vec v$ позиция. Запись этих двух векторов вместе является матричным умножением

M * \vec v = \left[ \begin{matrix} 3 & 1\\ 1 & 2 \end{matrix} \right] * \left[ \begin{matrix} -1\\ 2 \end{matrix} \right]

Он представлен графически как:

Обратите внимание на изменение здесь $Transformed\vec i$ и $Tranformed\vec j$ не только в оригинале $\vec i$ и $\vec j$ Ориентация растянута, и есть вращение. если матрица $M=\left[ \begin{matrix} 2 & 0\\ 0 & 4 \end{matrix} \right]$ , $M * \vec v = \left[ \begin{matrix} 4 & 1\\ 2 & 3 \end{matrix} \right] * \left[ \begin{matrix} -1\\ 2 \end{matrix} \right] = \left[ \begin{matrix} -2\\ 4 \end{matrix} \right]$ , что эквивалентно простому растяжению вектора $\vec v$ .

И наоборот, для некоторой матрицы большая часть векторов будет смещена, но есть некоторые векторы, которые будут только растягиваться, а не смещаться.Такие векторы называются собственными векторами матрицы, а величина растяжения называется собственные значения, соответствующие этому вектору. Процесс нахождения собственных векторов и собственных значений называется разложением матрицы, то есть разложением матрицы на $A=Q\Sigma Q^{-1}$ , где каждый столбец Q является собственным вектором матрицы A, указывающим, какие векторы только растянуты матрицей; $\Sigma$ представляет собой диагональную матрицу.Элементы на диагонали соответствуют собственным значениям, соответствующим собственным векторам, указывая, как растягиваются соответствующие собственные векторы. Предположим, что вектор v является собственным вектором квадратной матрицы A, тогда $A\vec v=\lambda\vec v$ , $\lambda$ вектор признаков $\vec v$ Соответствующие собственные значения, набор собственных векторов матрицы представляет собой набор ортогональных векторов. Решая это уравнение, можно получить $\vec v$ и $\lambda$ . Когда мы хотим описать преобразование, мы хотим описать только его основное направление преобразования, то есть направление, в котором оно изменяется больше всего. Для матричной декомпозиции вектор-столбец, соответствующий Q, является основным направлением изменения, когда $\Sigma$ При расположении в порядке убывания чем больше собственное значение соответствует большему изменению, соответствующему собственному вектору. Когда матрица многомерна, мы находим top-k собственных значений матрицы, которые соответствуют k наиболее важным преобразованиям матрицы, то есть наиболее важному признаку матрицы, и можем использовать эти k признаков аппроксимировать эту матрицу. Однако разложение по собственным значениям применимо только к квадратным матрицам, но многие из них не являются квадратными матрицами в практических приложениях, поэтому предлагается разложение по сингулярным значениям (SVD). Разложение по сингулярным числам подходит для обычных матриц, которые можно выразить алгебраически как $A=U\Sigma V^T$ , U становится левой сингулярной матрицей, правая называется правой сингулярной матрицей, а середина является сингулярным значением. Графически это

. k, для получения приближенного решения этого уравнения существует алгоритм ALS.

4.2 Базовая модель

Основная модель матричной факторизации: $\hat{r}_ {ui}=q^T_ip_u$ ,в $\hat r_{ui}$ — рейтинг элемента i пользователем u, q^T_i - вектор элемента, p_u вектор для пользователя u. Цель оптимизации:

min_{p^*, q^*}\Sigma_{(u,i)\in k}(r_{ui}-q^T_ip_u)^2+\lambda (||q_i||^2+||p_u||^2)

известен $r_{ui}$ Набор (u,i) . Поскольку ни q, ни p не известны, это уравнение не является выпуклой функцией, а метод его решения — ALS (чередование наименьших квадратов).Один из них фиксируется в момент времени, например, p, тогда эта задача оптимизации эквивалентна квадратичной Задача оптимизации. Используйте SGD, чтобы найти оптимальное решение относительно p, затем исправьте p и решите задачу оптимизации относительно q и т. д.

4.3 Учет предвзятости

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

Цель оптимизации:

min_{p^*, q^*,b^*}\Sigma_{(u,i)\in k}(r_{ui}-\mu-b_u-b_i-q^T_ip_u)^2+\lambda (||q_i||^2+||p_u||^2+b^2_u+b^2_i)

$\mu$ является средним значением всех предметов. Например, чтобы спрогнозировать рейтинг Джо для «Титаника», средний балл для всех фильмов составляет 3,7, «Титаник» — хороший фильм, и он на 0,7 выше, чем средний фильм. пользователей, поэтому итоговая оценка составила 3,9 (3,7+0,5-0,3).

4.4 Сценарии неявной обратной связи

Наиболее распространенным вариантом использования приведенной выше матричной факторизации является явная обратная связь, и то, что нам нужно сделать сейчас, — это неявная обратная связь. Отображение обратной связи означает, что пользователи четко знают свое отношение, например, оценку фильма и т. д. Неявная обратная связь не отражает напрямую отношение пользователя, например, данные о кликах, данные просмотра, и клик пользователя не означает, что ему нравится элемент или новость. Неявная обратная связь очень отличается от явной обратной связи: неявная обратная связь более плотная и стабильная, а явная обратная связь более разреженная. Неявная обратная связь более реалистична, и данные легче получить; явная обратная связь лучше отражает отношение пользователей. Неявные данные обрабатываются иначе, чем явные данные. В настоящее время существует два метода для этих двух типов данных: точечный (предсказание предпочтения для точки) и парный (упорядочивание двух элементов). Для неявных данных метод оптимизации становится (в соответствии с исходным текстом, p, q заменяются на x, y соответственно):

min_{x^*, y^*}\Sigma_{(u,i)\in k}c_{ui}(p_{ui}-x^T_uy_i)^2+\lambda (||x_u||^2+||y_i||^2)

p_{ui}= \begin{cases} 1 \ \ r_{ui}>0 \\ 0 \ \ r_{ui}=0, c_{ui}=1+\alpha r_{ui} \end{cases}

использованная литература:

Matrix factorization techniques for recommender systems

Collaborative Filtering for Implicit Feedback Datasets