Recommender system
Цель рекомендующей системы состоит в создании значимых рекомендаций пользователям относительно набора предметов или продуктов (далее будем использовать термин сервис), которые могут их заинтересовать. Это могут быть предложения книг, товаров или фильмов.

Вначале несколько примеров.
Пример 1.
Сеть магазинов Target в США с помощью этих технологий решила определить модель покупательского поведения для беременных женщин. Для этого они собрали данные обо всех покупках женщин, которые участвовали в их программе лояльности для беременных, и проанализировали их с помощью математических алгоритмов и машинного обучения. Оказалось, что на начало второго триместра беременности женщины обычно покупают лосьоны без запаха, а через несколько недель начинают покупать пищевые биодобавки и так далее. Закономерности в изменениях покупательского поведения так четко прослеживались, что по ним даже можно было определить срок беременности с точностью до недели.

Благодаря полученным данным, розничная сеть смогла составить алгоритм для определения беременности по покупкам. Со временем эта система персонального таргетирования стала настолько точной и продвинутой, что она зачастую определяла беременность женщины раньше, чем та узнавала о ней сама. Если модель покупательского поведения женщины говорила о том, что она беременна, Target начинала показывать ей определенную рекламу, предлагать скидки на товары, которые ей вскоре могут понадобиться.
Это привело к скандалу в 2012 году, когда 12 летняя девочка получила от магазина кучу рекламных материалов, посвященных беременности и товаров для малышей. Ее отец поднял скандал, в том числе, и в прессе и когда через пару недель руководители этой сети магазинов приехали с извинениями, то этот же отец был вынужден сказать, что девочка и не знала, что она беременна.
Пример 2.
Расшифрованные данные с камер слежения, позволяют довольно детально понять и проанализировать перемещение людей по большому моллу, сделать вывод о том, как правильно оптимизировать выкладку товаров, разработать специальные акции в зависимости от времени суток, дня недели и т.д., опираясь только на то, как перемещаются по магазину потребители, где каждый потребитель ходил и около какой из полок застрял, т.е. сделать тепловую карту.


Пример 3.
Ровно такие же тепловые карты сейчас используют при анализе и оптимизации расположения различных элементов на веб-странице. Только в данном случае вместо перемещения потенциальных покупателей используется движение курсора, клики мыши, концентрация внимания и др. метрики.

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

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


Общая структура рекомендующей системы.

Получение рекомендаций из надежных источников является одним из важнейших компонентов естественного процесса принятия решений. Растущее потребление, поддержанное развитием Всемирной Сети, приводит к тому, что покупателям представлен более широкий круг выбора сервисов, в то время как продавцы сталкиваются с проблемой персонализации своих рекламных кампаний.
Рекомендующие системы эволюционируют, чтобы удовлетворить потребности покупателей и продавцов за счет автоматизации рекомендаций на основе анализа данных.
Термин "коллоборативная (совместная) фильтрация" был введен в контексте первой коммерческой рекомендующей системы, которая была разработана для адресной рекомендации новостей определенному кругу пользователей. Мотивация состояла в том, чтобы пользователь не получал документы, которые ему не интересны. Совместная фильтрация анализирует данные об использовании товаров или услуг (сервисов) разными пользователями, с целью выявления хорошо подобранной пары пользователь-сервис. В соответствии с методологией фильтрации контента, которая уходит корням к информационному поиску, рекомендации не являются "совместными", в том смысле, что предложения, высказанные пользователями, явным образом не используют информацию всей пользовательской базы, а отталкиваются от атрибутов сервиса (товара, услуги).
Первые методы для рекомендующей системы были основаны на простой статистике корреляции и прогнозного моделирования.
Дальнейшие исследования были вызваны публичной доступностью данных в Интернете, и интересом, связанным с возросшей популярностью электронной коммерции. Всплеск интереса к этой проблеме вызвала компания Netflix, специализирующаяся на онлайн потоковом видео и DVD аренде, которая выложила для свободного доступа крупный набор данных, содержащий 100 млн. рейтингов, примерно на полмиллиона пользователей, и несколько тысяч названий фильмов, после чего объявила открытый конкурс на лучший алгоритм коллоборативной фильтрации.


Сообщение Netflix об окончании конкурса.

В настоящее время, рекомендующие системы остаются областью активных исследований, в которых пересекаются разделы математической статистики, машинного обучения, интеллектуального анализа данных, и пр. Приложения методов рекомендующих систем осуществляются в различных областях, начиная от веб-страниц, рекомендующих музыку, книги, фильмы и другие потребительские товары, до интерпретации политических выборов.
Общая структура рекомендующей системы представлена на следующем рисунке. Известные предпочтения пользователя представлены в виде матрицы из \(N \) пользователей и \(M \) сервисов (изделий, элементов, услуг), где каждой ячейке соответствует рейтинг данного сервиса, установленный пользователем \(User\).


Матрица рейтинов \(r_{u,i} \) , соответствующих пользователю u и объекту \(i \).

Матрица рейтингов является очень разреженной, поскольку большинство пользователей заполняет всего несколько пунктов. Особенностью является то, что под разреженностью матрицы понимается не традиционно математическое определение (большое количество коэффициентов матрицы равно нулю), а отсутствие в большей части ячеек какой-либо информации. Задачей рекомендационной системы является предсказание рейтинга пользователей, то есть заполнение пустых ячеек.
Множество подходов к рекомендующим системам можно классифицировать следующим образом:
  • Совместная или коллаборативная фильтрация (CF - Collaborative Filtering): в системах CF, пользователю рекомендуется элементы на основе прошлых коллективных рейтингов всех пользователей.
  • Content-ориентированные (CB - Content Based) рекомендации: эти подходы рекомендуют сервисы, аналогичные по содержанию сервисам, которые понравились пользователю в прошлом, или соответствуют предопределенным атрибутам предпочтений пользователя.
  • Гибридные подходы: эти методы сочетают содержание приведенных подходов.

    Совместная или коллаборативная фильтрация (CF - Collaborative Filtering).

    Совместная фильтрация (CF) системы работает путем реализации обратной связи с пользователями в виде оценки элементов данной области и использованием сходства в рейтинге поведения среди нескольких подобных пользователей. Другими словами, CF методы основаны на близости соседей и моделей.
    Рассмотрим простую модель рекомендующей системы. Близость соседей является основой методов, в случае, если группа пользователей выбирается с учетом их сходства с активным пользователем, и, взвешенное сочетание их рейтингов используется для получения прогнозов этого пользователя.
    Такого рода алгоритмы основываются на следующих шагах:
    1. Назначение веса для всех пользователей в отношении сходства с активным пользователем.
    2. Выбор \(k \) пользователей, которые имеют наибольшее сходство с активным пользователем - соседей.
    3. Вычисление прогноза от взвешенной комбинации выбранных оценок соседей.
    На шаге 1, вес \(w_{a,u} \) является мерой сходства между пользователем \(u \) и активным пользователем \(a \).Наиболее часто используемой мерой сходства является коэффициент корреляции Пирсона между рейтингами двух пользователей: \[ w_{a,u} = \frac{\sum\nolimits_{i \in I} {\left( {r_{a,i} - \bar {r}_a } \right)\left( {r_{u,i} - \bar {r}_u } \right)} }{\sqrt {\sum\nolimits_{i \in I} {\left( {r_{a,i} - \bar {r}_a } \right)^2} } \sqrt {\sum\nolimits_{i \in I} {\left( {r_{u,i} - \bar {r}_u } \right)^2} } }, \] где \(I \) - набор элементов, оцененных пользователями, \(r_{u,i} \) рейтинг данного сервиса \(i \) пользователем \(u \),и \(\bar {r}_u \)- средняя оценка рейтинга пользователя \(u\).
    Что касается второго шага, то этому вопросу мы уделили внимание, рассматривая методы кластеризации.
    На шаге 3, прогнозы, как правило, рассчитываются как средневзвешенные отклонения от соседей: \[ p_{a,i} = \bar {r}_a + \frac{\sum\nolimits_{u \in K} {\left( {r_{u,i} - \bar {r}_u } \right)\times w_{a,u} } }{\sum\nolimits_{u \in K} {w_{a,u} } }, \] где \(р_{a,i} \) предсказание для активных пользователей \(a \) по сервису \(i, w_{a,i} \) - сходство между пользователями \(a \) и \(u \),и \(K \) - соседи или окрестность, набор пользователей, наиболее близких к активному пользователю.
    Кроме того, если рассматривать рейтинги пользователей как векторы, то оценить их сходство можно основываясь на косинусе угла между ними: \[ w_{a,u} = \cos \left( {\vec {r}_a ,\vec {r}_u } \right) = \frac{\vec {r}_a \cdot \vec {r}_u }{\left\| {\vec {r}_a } \right\|_2 \left\| {\vec {r}_u } \right\|_2 } = \frac{\sum\nolimits_{i = 1}^m {r_{a,i} r_{u,i} } }{\sqrt {\sum\nolimits_{i = 1}^m {r_{a,i}^2 } } \sqrt {\sum\nolimits_{i = 1}^m {r_{u,i}^2 } } }. \] Заметим, что эмпирические исследования установили, что корреляция Пирсона обычно работает лучше. Есть и другие меры сходства, в том числе среднеквадратическая ошибка, энтропия и пр.

    Выбор элемента на основе совместной фильтрации.

    При применении к миллионам пользователей и сервисов, использование традиционных методов из-за вычислительной сложности не эффективно. В качестве альтернативы, предлагается схема совместной фильтрации элемент-к-элементу, где соответствие определяется не по подобным пользователям, а по рейтингу аналогичных элементов. На практике, этот подход приводит к более быстро реагирующей рекомендационной системе, и часто приводит к улучшению прогнозов пользовательского поведения.
    При таком подходе, сходство между парами элементов \(i \) и \(j \) вычисляется с использованием корреляции Пирсона: \[ w_{i,j} = \frac{\sum\nolimits_{u \in U} {\left( {r_{u,i} - \bar {r}_i } \right)\left( {r_{u,j} - \bar {r}_j } \right)} }{\sqrt {\sum\nolimits_{u \in U} {\left( {r_{u,i} - \bar {r}_i } \right)^2} } \sqrt {\sum\nolimits_{u \in U} {\left( {r_{u,j} - \bar {r}_j } \right)^2} } }, \] где \(U \) является множеством всех пользователей, которые оценили оба элемента \(i \) и \(j \),\(r_{u,i} \) рейтинг пользователя \(u\) по элементу \(i \),и \(\bar {r}_i \) средний рейтинг элемента \(i \) между пользователями.
    Теперь, рейтинг по элементу \(i \) пользователя a может быть предсказан с помощью взвешенной оценки: \[ p_{a,i} = \frac{\sum\nolimits_{j \in K} {r_{a,j} w_{i,j} } }{\sum\nolimits_{j \in K} {\vert w_{i,j} \vert } }, \] где \(К \) окрестность множества \(k \) элементов по оценке \(a \),наиболее близких к сервису \(i\).
    Заметим, что при измерении сходства между пользователями, элементы, которые были оценены всеми (понравилось или не нравится), не так полезны, как менее распространенные элементы. Чтобы учесть этот факт используют понятие обратной частоты пользователя, которое рассчитывается следующим образом \(f_i = \log\frac{n}{n_i} \),где \(n_i \) количество пользователей, которые оценили элемент \(i \) из общего числа \(n \) пользователей.
    Чтобы применить обратную частоту пользователя при использовании сходства на основе CF, оригинальный рейтинг \(i \) умножается на \(f_{i} \). Основанием этого подхода является то, что элементы, которые поголовно понравились, оцениваются чаще, чем другие.
    В случае использования больших массивов пользователей и сервисов, высокую эффективность проявили латентные (скрытые) модели и факторизация матричных моделей. В отличие от методов, основанных на локализации окрестности соседей, которые генерируют рекомендации на статистических понятиях сходства между пользователями или между элементами, латентные факторные модели базируются на том, что сходство между пользователями и предметами индуцируется некоторыми скрытыми структурами данных меньшей размерности. Например, рейтинг, который пользователь дает фильму, по всей вероятности, зависит от нескольких неявных факторов, таких как пользовательский вкус в жанрах кино. Матричной факторизацией называется класс удачных моделей скрытых факторов, где пользователи и сервисы представлены в виде неизвестных вектор-функций (вектор-столбцы) \(w_u ,h_i \in \Re ^k \) вдоль \(k \) скрытых размерностей. Произведение \(w_u^T h_i \) является приближением матрицы известных рейтингов \(r_{u,i} \). Для решения этой задачи традиционно используется метод наименьших квадратов \[ J(W,H) = \sum\limits_{(u,i) \in L} {\left( {r_{u,i} - w_u^T h_i } \right)^2}, \] где \(W = [w_{1} ... w_{n} ]^{T} \) матрица размера \(n\times k, \) \(H =[h_{1} ... h_{m}] \) является матрицей размера \(k\times n\), а \(L \) есть множество пар пользователь-элемент, для которых известны рейтинги. В тривиальном случае, когда все рейтинги пар пользователь - элемент известны, целевая функция будет иметь вид \[ J(W,H) = \left\| {R - WH} \right\|_{F}^2 , \] где \(R \) обозначает матрицу размером \(n\times m\) полностью известных пар пользователь-сервис и \(\left\| \bullet \right\|_{F}\)-норма Фробениуса. Решение этой задачи дается сингулярным разложением. Однако, в реальных условиях, когда большинство рейтингов пользователь-элемент неизвестно, такое глобально оптимальное решение не может быть получено в явном виде, поэтому требуется оптимизация невыпуклой целевой функции \(J(W, H) \). В этом случае целевая функция представляет собой особую форму взвешенных потерь, т.е. \[ J(W,H) = \left\| {S \otimes (R - WH)} \right\|_{F}^2 , \] где \( \otimes \) обозначает поэлементное произведение, и \(S \) является бинарной матрицей с коэффициентами, равными единице для известной пары пользователь - элемент \(L \),и нулю в противном случае. Стандартное решение предполагает использование градиентных методов или процедур, подобных итерационной модификации метода наименьших квадратов, когда \(H \) определяется при фиксированном \(W \), и, наоборот, пока не достигается критерий сходимости. Подобный подход был рассмотрен нами в разделе, посвященном методу наименьших квадратов.
    После нахождения \(W \) и \(H \),их произведение \(WH \) обеспечивает приближенное восстановления рейтинг-матрицы, откуда рекомендации могут быть считаны непосредственно.
    Различный выбор функций цели, регуляризация и дополнительные ограничения модели вызвали большой интерес к методам факторизации матриц. Можно утверждать, что для дискретных рейтингов, квадрат ошибки не самый естественный метод.
    Другой класс методов использует факторизацию матрицы при условии неотрицательности ограничений, налагаемых на \(W \) и \(H \).Рейтинг поведения каждого пользователя может рассматриваться посредством проявления различных ролей, например, присутствием в группах пользователей связанных интересами или общением, что приводит к функции цели вида \[ J(W,H) = \sum\limits_{(i,u) \in L} {r_{u,i} \log \frac{r_{u,i} }{w_u^T h_i } - r_{u,i} + w_u^T h_i .} \] В завершившемся конкурсе Netflix с призом в миллион долларов победил метод факторизации матриц. Окончательную победу принес сложный комплекс различных моделей, в состав которых входит несколько улучшений основных матричных моделей факторизации. К ним относятся:
    1. Учет дополнительных конкретных пользователей и конкретных сервисов для учета систематических погрешностей в рейтингах, например, использование того факта, что популярные фильмы в среднем получают более высокие оценки.
    2. Использование временной динамики рейтинга \[ J(W,H) = \sum\limits_{(u,i) \in L} {\left( {r_{u,i} (t) - b_u (t) - \hat {r} - w_u^T (t)h_i } \right)^2,} \] где \(t \) обозначает отсчет времени, и \(W \) включает в себя зависящую от времени размерность пространства пользователей.
    Во многих случаях, в отличие от рейтингов "нравится - не нравится", доступны только неявные предпочтения, например, записи транзакций, содержащие информацию о продукции, приобретенной клиентами, или навигации клиента на сайте продавца. Эта информация может быть использована для формирования отрицательных примеров, что позволит не предлагать клиентам услуги или товары, в которых они не нуждаются. Такого рода информацию трудно собрать и поддерживать, с учетом быстро меняющейся бизнес-среды. Метод факторизации матриц может быть использован для решения таких задач, если ввести вес \(c_{u,i} \) характеризующий степень доверия, который может принимать отрицательные значения \[ J(W,H) = \sum\limits_{(u,i) \in L} {c_{u,i} \left( {r_{u,i} - w_u^T h_i } \right)^2} . \]

    Смесь скрытых профилей.

    Пусть \(Y = \left\{ {y_m } \right\}_{m =1}^M \) набор сервисов и \(U = \left\{ {u_n } \right\}_{n = 1}^N \) множество зарегистрированных пользователей. Матрица рейтингов R имеет размерность \(N\times M\). Рейтинг установленный пользователем \(u_n \) сервису \(y_m \) обозначим \(r_{n,m} \). Наблюдаемые рейтинги хранятся в списке \(D = \left\{ {\left( {u,y,r} \right)_i } \right\}_{i = 1}^L \). Заметим, что не все элементы имеют рейтинг для того или иного пользователя. Опишем вероятностные смеси модели скрытых профилей. Идея заключается в представлении рейтинга поведения пользователей простой порождающей моделью. Рассмотрим две версии вероятностного подхода к смеси. Первая предполагает, что существуют группы пользователей, имеющих по существу тот же поведенческий рейтинг. Вторая модель позволяет каждому пользователю иметь свой собственный профиль рейтинга, но этот профиль представлен в виде смеси нескольких типичных профилей рейтингов. Заметим, что рейтинг профиля определяется распределением рейтингов на полном наборе сервисов, на основании \(P\left( {r,y\left| \theta \right.} \right) \),где \(r = \left( {r_1 ,r_2 ,...,r_M } \right)^T \) и \(y = \left( {y_1 ,y_2 ,...,y_M } \right)^T \) с значением \(y_m = 1 \) , если элемент \(m \) получил рейтинг и \(y_m = 0 \) в случае \(r_m = O \). При прогнозировании рейтинга, обычно, известно на какой элемент нужно делать прогноз, и, таким образом, достаточно определить условную вероятность рейтинга профиля \(P\left( {r\left| y \right.;\theta } \right) \), считая, что распределение параметризовано по \(\theta \).
    Вначале рассмотрим рейтинг, построенный на бинарной информации - было ли взаимодействие между пользователем \(u_n \) и элементом \(y_m \), или нет. В этом случае рейтинг профиля определяется через \(P\left( {y\left| \theta \right.} \right) \) - вероятность получения (по имеющейся информации) рейтинга для каждого элемента. В этом случае, используя распределение Бернулли, получаем \[ P\left( {y\left| \theta \right.} \right) = \prod\limits_m {\beta _m^{y_m } \left( {1 - \beta _m } \right)^{1 - y_m }} . \] Множество параметров \(\theta \equiv \left( {\beta _1 ,...,\beta _M } \right)^T\) и \(0 \le \beta _M \le 1 \) определяет вероятность того, что пользователь взаимодействовал с \(y_m \).
    Альтернативой распределению Бернулли является полиномиальное распределение. В этом случае существует дополнительное ограничение между параметрами: \(\theta \equiv \beta = \left( {\beta _1 ,...,\beta _M } \right)^T \) при условии \(\sum\nolimits_m {\beta _m = 1} \) и \(\beta _m \ge 0 \). Тогда вероятность профиля будет определяться следующим образом \[ P\left( {y\left| \theta \right.} \right) \propto Mn\left( {y\left| \beta \right.,V} \right) = V!\prod\limits_m {\beta _m^{y_m } = V!\prod\limits_{y_m = 1} {\beta _m } } , \] где \(V = \sum\limits_m {y_m } \)- число элементов, имеющих рейтинг.
    Интересно, что, для полиномиального распределения, элементы, не имеющие рейтинга, не вносят непосредственный вклад в вероятность. Это делает процесс вычисления вероятности гораздо более быстрым и более эффективным на больших рейтинг- матрицах. Знак пропорциональности показывает, что проводя нормализацию, необходимо принимать во внимание ограничения \(y_m \in \left\{ {0,1} \right\} \). Заметим, что этот фактор не влияет на оптимизацию параметров.
    В более общем случае полиномиальное распределение подходит для рейтингов, представляющих целые числа \(r \in \left\{ {0,1,2,...} \right\} \). Так же, как и в предыдущем случае, мы имеем \[ P\left( {r\left| \theta \right.} \right) = Mn\left( {r\left| \beta \right.,\sum\nolimits_m {r_m } } \right). \] Вектор \(у \) отсутствует в этом выражении, так как информация об отсутствующих рейтингах уже закодирована в \(r\).
    Принцип определения рейтинга профилей остается таким же для явных рейтингов, т.е. когда рейтинги кодируются с учетом мнения пользователей. Явные рейтинги могут принимать значения в упорядоченном множестве и быть либо дискретными \(r \in \left\{ {1,2,...,r_{\max } } \right\} \),либо непрерывными \(r \in \left[ {r_{\min } ,r_{\max } } \right] \). Отсутствующие значения рейтинга будем ассоциировать с \(r = O \). Рассмотрим сначала простой случай, когда требуется только условное распределение рейтинга \(P\left( {r\left|{y;} \right.\theta } \right) \). Можно было бы определить профиль, получая рейтинги, например, с гауссовских распределений. Так, если использовать параметризацию \(\theta \equiv \left\{ {\left( {\mu _m ,\sigma _m } \right)} \right\}_{m = 1}^M \) , получаем вероятность профиля \[ P\left( {r\left| y \right.;\theta } \right) = \prod\limits_{y_m = 1} {N\left( {r_m \left| {\mu _m ,\sigma _m } \right.} \right)} , \] где произведение берется только на множестве наблюдаемых оценок. На практике, рейтинги всегда вынуждены принимать значения из ограниченного интервала, и, тогда имеет смысл использовать ограниченные распределения, подобные бета распределению (которое имеет два параметра). Кроме того, если рейтинги могут быть выбраны из дискретного набора, биномиальное распределение или полиномиальное распределения были бы более естественны, чем распределение Гаусса.
    Теперь, с учетом схемы прогнозирования, т.е. информации \(P\left( {r\left| y\right.;\theta } \right) \),можно объединить в профиль неявные и явные рейтинги. Стандартным подходом является сочетание полиномиального распределения по недостающей информации и гауссовских распределений для имеющихся значений рейтинга. Следовательно, мы имеем \(\theta \equiv \left\{ {\left( {\beta _m ,\mu _m ,\sigma _m } \right)} \right\} \) и вероятность профиля \[ P\left( {r\left| y \right.;\theta } \right) = P\left( {r\left| y \right.;\left\{ {\left( {\mu _m ,\sigma _m } \right)} \right\}} \right)P\left( {y\left| \beta \right.} \right) \propto \prod\limits_{y_m = 1} {\beta _m N\left( {r_m \left| {\mu _m ,\sigma _m } \right.} \right)}. \] Заметим, что если целью является только точное предсказание рейтингов пар пользователь-сервис, т.е. определение хорошей оценки \(P(r|(u,y))\), то, вероятно, будет мало пользы от того, что мы примем во внимание отсутствие рейтингов в модели.
    Идея скрытого профиля кластеризации состоит в том, что каждому пользователю ставится в соответствие один профиль рейтинга среди множества типичных профилей. Предположим, что существует K моделей профилей рейтингов. Каждый профиль имеет свою собственную параметризацию, следовательно, полный набор профилей параметров есть \(\theta \equiv \left\{ {\theta _k } \right\}_{k = 1}^K \). Пользователю u ставится в соответствие вектор индексов \(z = \left[ {z_1 ,...,z_K } \right] \) и \(z_k = 1 \) если пользователь соответствует \(k\)-му профилю и \(z_k = 0 \) в противном случае. Тогда вероятность того, что пользователь соответствует профилю, будет иметь вид \[ P\left( {r,y\left| u \right.;z,\theta } \right) = \prod\limits_k {P\left( {r,y\left| {\theta _k } \right.} \right)^{z_k }} . \]

    Использование кластеризации для коллаборационной фильтрации.

    Совершенно очевидно, что поскольку требуется дать рекомендацию текущему пользователю на основе истории поведения других пользователей, то для этой задачи можно использовать кластеризацию пользователей которые, по отношению к текущему, имеют подобные предпочтения или вкусы. В разделе, посвященном кластеризации были рассмотрены наиболее популярные методы группирования похожих объектов, среди которых наиболее популярным является метод k-средних. Метод прост в реализации и эффективен, но для нашего случая не годится, так как каждый объект (пользователь) помещается только в один кластер (было бы странно требовать от покупателя приобретать один и тот же товар).
    Введем необходимые в дальнейшем обозначения. Пусть \(r_{u,m}\) - рейтинг товара (услуги) \(m\) относительно пользователя \(u\). Вектор \(\vec{r}_u\) представляет собой все рейтинги пользователя \(u\). Набор всех пар пользователь-товар (услуга) в обучающей выборке обозначим через \(\mathcal{P}\). То есть, \(\mathcal{P}=\{(u,m)|r_{u,m} \hbox{ из обучающей выборки}\}\). Пусть, кроме того, \(\mathcal{P}_u=\{m|(u,m)\in \mathcal{P}\}\) и \(\mathcal{P}^m=\{u|(u,m)\in \mathcal{P}\}\) и \(p_{u,k}\) - вероятность того, что пользователь \(u\) принадлежит кластеру \(k\), далее, \(\mathbb{P}=(p_{u,k})\) - матрица размером \(U\times K\), где \(U\) и \(K\) - число пользователей и, соответственно, кластеров. Через \(c_{k,m}\) обозначим центр множества товаров(услуг) из \(k\)-го кластера и \(\mathbb{C}=(c_{k,m})\) - матрица размером \(K\times M\), где \(M\) - количество товаров (услуг).
    Нашей целью является нахождение матриц \(\mathbb{P}^*,\mathbb{C}^*\), которые минимизируют функционал \begin{equation}\label{1} \mathcal{F}(\mathbb{P},\mathbb{C})=\sum_{u=1}^U\sum_{k=1}^Kp^\alpha_{u,k}\|\vec{r}_u-\vec{x}_k\|^2= \sum_{u=1}^U\sum_{k=1}^Kp^\alpha_{u,k}\sum_{m\in \mathcal{P}_u}({r}_{u,m}-{x}_{k,m})^2, \end{equation} где \(\alpha>0\) параметр принадлежности к кластеру.
    Результатом работы должен быть прогноз рейтинга товара (услуги) по отношению к конкретному пользователю \[ r^*_{u,m}=\sum_{k=1}^Kp^*_{u,k}c^*_{k,m}. \] Решение этой задачи существенно осложнено разреженностью матрицы рейтингов, под термином "разреженность" будем понимать отсутствие данных, но, ни в коем случае, не значение 0, так как значение ноль трактуется "покупка не сделана" НО "товар (услуга) были предъявлены (просмотрены) и оценены числом ноль (не нужный, не интересный)". Отсутствие значения рейтинга (разреженность) говорит о том, что пользователь, может быть, и не имеет никакого понятия об этом товаре (услуге).
    Таким образом, требуется кким-то образом заполнить матрицу рейтингов. Эта задача называется "факторизацией матрицы". С формальной точки зрения нужно найти такие две матрицы \(\mathbb{W}^*,\mathbb{V}^*\), которые минимизируют ошибку восстановления матрицы рейтингов \[ \|\mathbb{R}-\mathbb{W}\mathbb{V}^T\|_F, \] где \(\mathbb{R}=(r_{u,m})\) - матрица рейтингов (размера \(U\times M)\)), \(\mathbb{W}=(w_{u,k})\) и \(\mathbb{V}=(v_{m,k})\) - матрицы размером \(U\times K)\) и \(M\times K)\), соответственно, матрицы пользователей и услуг (товаров), взятые из обучающей выборки, то есть для известных \(r_{u,m}\) из множества \(\mathcal{P}\). Традиционно под \(\|\cdot\|_F\) понимаем норму Фробениуса (Frobenius norm).
    Для решения такого рода задач используют методы регуляризации, к которым относится "метод усадки коэффициентов", который состоит в том, что необработанная оценка улучшается путем объединения ее с другой информацией, уже известной. Ясно, что улучшенная таким образом оценка дает меньшую погрешность.
    Тогда задачу факторизации можно свести минимизации функционала \[ G(\mathbb{W},\mathbb{V})=\frac{1}{2}\sum_{(u,m)\in \mathcal{P}}\left(\left(r_{u,m}-\vec{w}_u\vec{v}_m^T\right)^2+ \lambda\left(\|\vec{w}_u\|_2^2+\|\vec{v}_m\|_2^2\right)\right), \] где \(\vec{w}_u\) и \(\vec{v}_m\) - u-я строка \(\mathbb{W}\) и, соответственно, m-я строка \(\mathbb{V}\), а \(\lambda\) - коэффициент "усадки".
    Для решения этой задачи можно применить метод градиентного спуска.
    Метод факторизации матриц работает достаточно неплохо, ввиду того, что каждая строка \(\mathbb{W}\) представляет собой один пользовательский фактор предпочтения и каждая строка \(\mathbb{V}\) - атрибут одного товара (услуги).
    Вернемся к задаче кластеризации, то есть минимизации функционала \[ \mathcal{H}(\mathbb{P},\mathbb{C})=\|\mathbb{R}-\mathbb{P}\mathbb{C}\|^2_F= \sum_{(u,m)\in \mathcal{P}}\left(r_{u,m}-\sum_{k=1}^Kp_{u,k}c_{k,m}\right)^2= \sum_{(u,m)\in \mathcal{P}}\left(\sum_{k=1}^Kp_{u,k}(r_{u,m}-c_{k,m})\right)^2. \] Заметим, что это соотношение равно (\ref{1}) при \(\alpha=2\).
    Рассмотрим эквивалентную задачу \[ \tilde{\mathcal{H}}(\mathbb{P},\mathbb{C})= \sum_{(u,m)\in \mathcal{P}}\left(r_{u,m}-\sum_{k=1}^KP_{u,k}c_{k,m}\right)^2, \] где \[ P_{u,k}=\frac{\exp(p_{u,k})}{\sum_{i=0}^K\exp(p_{u,i})} \] вероятность принадлежности пользователя \(u\) к \(k\)-му кластеру.
    Проводя регуляризацию путем "усадки коэффициентов", получаем следующую функцию цели \[ \bar{\mathcal{H}}(\mathbb{P},\mathbb{C})=\frac{1}{2} \sum_{(u,m)\in \mathcal{P}}\left(r_{u,m}-\frac{1}{\sum_{i=0}^K\exp(p_{u,i})}\sum_{k=1}^K\exp(p_{u,k})c_{k,m}\right)^2+ \lambda\left(\|\vec{c}_m\|_2^2+\|\vec{p}_u\|_2^2\right). \] Для минимизации функции цели можно использовать, например, метод градиентного спуска.
    Пусть, \(\tilde{r}_u\) и \(\tilde{r}^m\) - средние значения рейтинга пользователя \(u\) и товара (услуги) \(m\), кроме того, \(\bar{r}\) - глобальный средний рейтинг. Ясно, что все данные берутся по множеству \(\mathcal{P}\).
    Поскольку пользователь оценивает небольшую долю имеющихся товаров или услуг, то оценка \(\tilde{r}_u\) значением \(\bar{r}\) не надежно, поэтому будем использовать значение \[ \bar{r}_u=\frac{|\mathcal{P}_u|\tilde{r}_u+\kappa_u\bar{r}}{|\mathcal{P}_u|+\kappa_u}= \bar{r}+\frac{|\mathcal{P}_u|}{|\mathcal{P}_u|+\kappa_u}(\tilde{r}_u-\bar{r}), \] где \(\kappa_u\)- фактор "усадки" пользователя.
    Аналогично \[ \bar{r}^m=\frac{|\mathcal{P}^m|\tilde{r}^m+\kappa^m\bar{r}}{|\mathcal{P}^m|+\kappa^m}= \bar{r}+\frac{|\mathcal{P}^m|}{|\mathcal{P}^m|+\kappa^m}(\tilde{r}^m-\bar{r}), \] где \(\kappa^m\)- фактор "усадки" товара (услуги).
    Значения \(\bar{r}_u\) и \(\bar{r}^m\) являются более надежными характеристиками, чем \(\tilde{r}_u\) и \(\tilde{r}^m\). Более того, часто вместо \(r_{u,m}\) используют грубое приближение, которое может лучше характеризовать пристрастия потребителя \[ \bar{r}_{u,m}=\bar{r}_{u}+\bar{r}^{m}-\bar{r}= \frac{|\mathcal{P}_u|}{|\mathcal{P}_u|+\kappa_u}(\tilde{r}_u-\bar{r})+ \frac{|\mathcal{P}^m|}{|\mathcal{P}^m|+\kappa^m}(\tilde{r}^m-\bar{r})+\bar{r}. \] Осталось привести оценку факторов "усадки": \(\kappa_u=50\) и \(\kappa^m=100\).

    Content-ориентированные рекомендации.

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


    Общая схема content-фильтрации..

    Многочисленные исследования в этой области сосредоточены на нахождении рекомендаций товаров или услуг с соответствующим текстовым контентом, например, используя веб-страницы товаров или услуг, содержащие описания и отзывы пользователей. Таким образом, можно относиться к этой проблеме, как к задаче поиска информации. Можно относиться к задаче, связанной с пользовательскими предпочтениями, как к информационному запросу, и, рейтинг документа соотносить с релевантностью запроса. Тогда документам в каждой рейтинговой категории ставится в соответствие TF-IDF вектор (см. раздел, посвященный классификаторам), после чего проводится их усреднение, что позволяет получить прототип вектора для каждой категории пользователей. Для классификации нового документа соответствующий вектор сравнивается с прототипом каждой категории. Предсказание рейтинга основано на сравнении значения косинуса угла между этими векторами.
    Альтернативой подходов, основанных на информационном поиске, является использование стохастических моделей, например, наивной байесовской классификации, построении дерева решений, нейронных сетей и пр.

    Профили пользователей.

    Профиль интересов пользователя используется в большинстве рекомендационных систем. Этот профиль может состоять из ряда различных типов информации. Мы сосредоточимся на двух типах информации:
    1. Модель пользовательских настроек, т.е. описание типов элементов, описывающих интересы пользователей. Есть много возможных альтернативных представлений этого описания, но общим является наличие функции, которая для любого элемента прогнозирует вероятность того, насколько пользователь заинтересован в этом сервисе. Для повышения эффективности рекомендаций, эта функция может быть использована для получения n элементов, которые, скорее всего, представляют интерес для пользователя.
    2. Истории взаимодействия пользователя с рекомендациями системы. Это может включать хранение элементов, которые пользователь просматривал вместе с другой информацией о действиях клиента (например, пользователь приобрел товар или рейтинг, указанный пользователем). Другой информацией может быть история запросов, введенных пользователем.
    В пользовательских настройках, система рекомендации обеспечивает интерфейс, который позволяет пользователям построить представление о своих собственных интересах. Для этого часто используются флажки, что позволяет пользователю выбрать то или иное известное значение атрибутов, например, выбрать любимые разделы новостей, или жанр фильмов. В других случаях, html-форма позволяет пользователю вводить слова, например, имя музыканта или автора, которые интересны пользователю. Как только пользователь ввел эту информацию в базу данных, процесс поиска использует их для нахождения элементов, которые отвечают критериям, определенным клиентом, и отображает их пользователю. При этом существует несколько ограничений системы пользовательских настроек. Во-первых, они требуют усилий со стороны пользователя, и нельзя рассчитывать на большое число пользователей, которые проделают эту работу. Во-вторых, настройки системы не обеспечивают способ определения порядка (рейтинга) элементов.
    Рекомендационная система, основанная на истории пользователя, должна иметь свои правила рекомендации других продуктов. Например, система может содержать правило, которое рекомендует продолжение книги или фильма для клиентов, которые приобрели ранее книгу или фильм из этой серии. Другое правило может рекомендовать новый компакт-диск для пользователей, которые приобрели ранее диски этого исполнителя. В некоторых ситуациях целесообразно рекомендовать товар пользователю, если он его приобрел ранее, а, в других ситуациях, это не так. Например, система должна по-прежнему предлагать элементы, которые изнашиваются или расходуются, например, такие как лезвия бритвы или картридж, в то же время мало рекомендуя мобильный телефон или WEB-камеру.

    Обучения модели пользователя.

    Создание модели поведения клиента на основе пользовательской истории, является одной из форм обучения рекомендационной системы. Рассмотрим классификацию алгоритмов обучения. Такие алгоритмы являются ключевым компонентом построения системы рекомендаций. Как уже отмечалось, алгоритм обучения включает функцию, которая будет обеспечивать оценку вероятности того, что пользователь оплатит товар (услугу). Эта вероятность может быть использована для сортировки списка рекомендаций. Традиционные алгоритмы машинного обучения предназначены для работы на структурированных данных. При работе с документами, текст сначала преобразуется в структурированные данные, используя небольшое подмножество терминов в качестве атрибутов.
    Приведем обзор нескольких наиболее популярных алгоритмов.

    Дерево принятия решений.

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

    Поведение ближайшего соседа.

    Алгоритм ближайшего соседа просто хранит все этапы и уровни подготовки данных. Для того, чтобы классифицировать новые, непомеченные пункты, алгоритм сравнивает их со всеми сохраненными элементами и, используя сходство, определяет "ближайшего соседа" и сводит рекомендации к действиям ближайших соседей. Использование алгоритма ближайшего соседа зависит от типа данных. Достаточно часто этот алгоритм используется для структурированных данных и евклидовой метрики, или же для векторной модели и значения косинуса угла в качестве критерия схожести. Достаточно эффективно использование этого алгоритма для сравнения текстов по одной тематике. Часто этот подход используется для персонализации новостей.

    Релевантное соответствие и алгоритм Rocchio.

    Так как при использовании модели векторного пространства, успех поиска документов зависит от способности пользователя создавать запросы, выбирая множество ключевых слов, то методы, которые помогают пользователям постепенно уточнить запросы, основанные на предыдущих результатах поиска, лежат в центре внимания многих исследований. Эти методы обычно называют отношением обратной связи (релевантное соответствие). Алгоритм Rocchio является широко используемым алгоритмом обратной связи. Алгоритм основан на модификации запроса через взвешенные прототипы соответствующих и не соответствующих документов. Подход формирует два прототипа документа - по всем соответствующим и не соответствующих документам, что формализуется следующим образом \[ Q_{i + 1} = \alpha Q_i + \beta \sum\limits_{rel} {\frac{D_i }{\left| {D_i } \right|} - \gamma } \sum\limits_{nonrel} {\frac{D_i }{\left| {D_i } \right|}} . \] Здесь \(Q_i \) пользовательский запрос на итерации i и \(\alpha ,\beta ,\gamma \) параметры, которые контролируют влияние исходного запроса и двух прототипов на изменение в результате запроса. Основная идея состоит в постепенном перемещении вектора запроса в направлении кластеров соответствующих документов и вдаль от второстепенных документов.

    Линейные классификаторы.

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

    Вероятностные методы и наивный байесовский классификатор.

    В отличие от векторной модели, не имеющей достаточного теоретического обоснования, вероятностные подходы классификации в своей основе имеют хорошую теоретическую базу. На данный момент наивный байесовский классификатор (см. раздел, посвященный классификаторам) признан как исключительно хорошо работающий алгоритм классификации текстов. Итак, нам нужно найти наиболее вероятную гипотезу \(h \in H \) при условии наличия данных \(D \),то есть нужно максимизировать \(P\left( {\left. h \right|D} \right). \) Для достижения этого будем использовать теорему Байеса \[ P(h\vert D) = \frac{P(D\vert h)P(h)}{P(D)} \] то есть, требуется найти \[ h = \arg \mathop {\max }\limits_{h \in H} P(h\vert D) = \arg \mathop {\max }\limits_{h \in H} P(D\vert h)P(h),\] а если гипотезы равновероятны, то \[ h = \arg \mathop {\max }\limits_{h \in H} P(D\vert h). \] Сравним различные варианты упрощенного алгоритма Байеса - полиномиальную модель и модель Бернулли. Обе модели основаны на предположении, что текстовые документы генерируют вероятностную модель, описываемую смесью \[ P\left( {d_i \left| \theta \right.} \right) = \sum\limits_{j = 1}^{\vert C\vert } {P\left( {c_i \left| \theta \right.} \right)P\left( {d_i \left| {c_j ;\theta } \right.} \right)} . \] Здесь, каждому классу \(с_{i} \) соответствует компонент смеси, который параметризуется непересекающимися подмножествами из \(\theta \). Как только из обучающих данных получены параметры \(\hat {\theta } \), апостериорная вероятность принадлежности тестового документа классу может быть определена в соответствии с теоремой Байеса \[ P\left( {c_j \left| {d_i ;\hat {\theta }} \right.} \right) = \frac{P\left( {c_j \left| \hat {\theta } \right.} \right)P\left( {d_i \left| {c_j ;\hat {\theta }} \right.} \right)}{P\left( {d_i \left| \hat {\theta } \right.} \right)}. \] Многомерная модель Бернулли и полиномиальные модели отличаются по способу определения величины \(P\left( {d_i \left| {c_j ;\theta } \right.} \right)\).
    Пусть \(V = \left\{ {w_t } \right\}_{t = 1}^{|V| } \)- словарь. Тогда документ \(d_{i} \) -- это вектор длины \(|V| \), состоящий из битов \(B_{i,t}. B_{i,t} = 1\) если слово \(w_{t} \) встречается в документе \(d_{i} \),иначе \(B_{i,t} =0\).
    Многомерная формулировка распределения Бернулли для задач классификации текста предполагает, что каждый документ представляется в виде бинарного вектора над пространством всех слов из словаря \(V\). Каждый элемент \(B_{i,t} \) этого вектора указывает появляется ли слово хотя бы раз в документе. Следуя наивному Байесу, вероятность каждого слова, входящего в документ не зависит от других слов и \(P\left( {d_i \left| {c_j ;\theta } \right.} \right) \) можно представить в виде произведения: \[ P\left( {d_i \left| {c_j ;\theta } \right.} \right) = \prod\limits_{i = 1}^{\vert V\vert } {\left( {B_{i,t} P\left( {w_t \left| {c_j ;\theta } \right.} \right) + (1 - B_{i,t} )\left( {1 - P\left( {w_t \left| {c_j ;\theta } \right.} \right)} \right)} \right)} . \] Для обучения такого классификатора нужно обучить вероятности \(P\left( {w_t \left| {c_j ;\theta } \right.} \right) \). Пусть дан набор документов \(D = \left\{ {d_i } \right\}_{i = 1}^{\vert D\vert } \) которые уже распределены по классам \(c_{j} \), дан словарь \(V = \left\{ {w_t } \right\}_{t = 1}^{\vert V\vert } \) и мы знаем биты \(B_{i,t} \) (знаем документы).
    Тогда можно подсчитать оптимальные оценки вероятностей \(P\left( {w_t \left| {c_j ;\theta } \right.} \right) \) того, что то или иное слово встречается в том или ином классе (при помощи лапласовой оценки): \[ P\left( {w_t \left| {c_j ;\theta } \right.} \right) = \frac{1 + \sum\limits_{i = 1}^{\vert D\vert } {B_{i,t} P\left( {c_j \left| {d_i } \right.} \right)} }{2 + \sum\limits_{i = 1}^{\vert D\vert } {P\left( {c_j \left| {d_i } \right.} \right)} }. \] Априорные вероятности классов можно вычислить следующим образом \[ P(c_j ) = \frac{1}{\vert D\vert }\sum\limits_{i = 1}^{\vert D\vert } {p(c_j \vert d_i )} \] и классификация будет происходить как \[ c = \arg \mathop {\max }\limits_j P(c_j )P(d_i \vert c_j ;\theta ) = \] \[ = \arg \mathop {\max }\limits_j \left( {\frac{1}{\vert D\vert }\sum\limits_{i = 1}^{\vert D\vert } {P(c_j \vert d_i )} } \right)\prod\limits_{t = 1}^{\vert V\vert } {\left( {B_{i,t} P(w_t \vert c_j ;\theta ) + \left( {1 - B_{i,t} } \right)\left( {1 - P(w_t \vert c_j ;\theta )} \right)} \right)} = \arg \mathop {\max }\limits_j \left( {\log \left( {\sum\limits_{i = 1}^{\vert D\vert } {P(c_j \vert d_i )} } \right) + \sum\limits_{t = 1}^{\vert V\vert } {\log \left( {B_{i,t} P(w_t \vert c_j ;\theta ) + \left( {1 - B_{i,t} } \right)\left( {1 - P(w_t \vert c_j ;\theta )} \right)} \right)} } \right) \] В отличие от бинарного представления документа многомерной моделью Бернулли, полиномиальная формулировка учитывает частоту выпадения слова. Эта модель предполагает, что документы генерируются последовательностью независимых испытаний с полиномиальным распределением вероятностей. Пусть дан набор документов \(D = \left\{ {d_i } \right\}_{i = 1}^{\vert D\vert } \), которые уже распределены по классам \(c_{j} \), дан словарь \(V = \left\{ {w_t } \right\}_{t = 1}^{\vert V\vert } \) и мы знаем \(N_{i,t} \) число вхождений слова \(w_{t} \) в документе \(d_{i}\). Опять таки, наивный Байес позволяет определить \(P\left( {d_i \left| {c_j ;\theta } \right.} \right) \) на основании вероятностей встречи отдельных слов: \[ P\left( {d_i \left| {c_j ;\theta } \right.} \right) = P\left( {\left| {d_i } \right|} \right)\prod\limits_{t = 1}^{\vert d_i \vert } {P\left( {w_t \left| {c_j ;\theta } \right.} \right)^{\mbox{N}_{\mbox{i,t}} }} . \] При этом, вероятность \(P\left( {w_t \left| {c_j ;\theta } \right.} \right)\) может быть оценена следующим образом: \[ P\left( {w_t \left| {c_j ;\theta } \right.} \right) = \frac{1 + \sum\limits_{i = 1}^{\vert D\vert } {B_{i,t} P\left( {c_j \left| {d_i } \right.} \right)} }{\vert V\vert + \sum\limits_{s = 1}^{\vert V\vert } {\sum\limits_{i = 1}^{\vert D\vert } {N_{i,s} P\left( {c_j \left| {d_i } \right.} \right)} } }. \] Априорные вероятности классов можно подсчитать как \[ P(c_j ) = \frac{1}{\vert D\vert }\sum\limits_{i = 1}^{\vert D\vert } {P(c_j \vert d_i )} \] Тогда классификация будет происходить как \[ c = \arg \mathop {\max }\limits_j P(c_j )P(d_i \vert c_j ;\theta ) = \arg \mathop {\max }\limits_j \left( {\frac{1}{\vert D\vert }\sum\limits_{i = 1}^{\vert D\vert } {P(c_j \vert d_i )} } \right)P\left( {\left| {d_i } \right|} \right)\left| {d_i } \right|!\prod\limits_{t = 1}^{\vert V\vert } {\frac{1}{N_{i,t} !}P(w_t \vert c_j ;\theta )^{N_{it} }} = \arg \mathop {\max }\limits_j \left( {\log \left( {\sum\limits_{i = 1}^{\vert D\vert } {P(c_j \vert d_i )} } \right) + \sum\limits_{t = 1}^{\vert V\vert } {N_{i,t} \log } P(w_t \vert c_j ;\theta )} \right). \] Опыт показывает, что полиномиальная формулировка Байеса эффективнее многомерной модели Бернулли.

    Гибридные подходы.

    Для того, чтобы использовать сильные стороны обоих подходов и получить более эффективную рекомендующую систему, следует использовать гибридные подходы. Один простой подход состоит в том, что на основе контентных и совместных методов фильтрации составляются отдельные списки рекомендаций, а затем объединяются, чтобы получить окончательный список весовым объединением двух прогнозов, где вес возрастает с количеством пользователей, выбирающих данный элемент.
    Интересной идеей является преобразование разреженных матриц рейтингов пользователей в заполненные матрицы, а затем, используя методы CF, получение рекомендаций. В частности, можно использовать наивный байесовский классификатор для обучения на документах, описывающих рейтинг каждого пользователя, и, использовать его для заполнения недостающих рейтингов. В результате получаем матрицу псевдо-рейтингов, используя которую, находим соседей, похожих на активного пользователя, и получаем прогнозы с помощью корреляции Пирсона. Существуют другие гибридные подходы, основанные на совместной фильтрации, но и поддерживающие профиль каждого пользователя.
    Качество рекомендующей системы можно оценить путем сравнения рекомендации для тестового набора известных рейтингов пользователей. Наиболее часто используемые метрики - это средняя абсолютная ошибка (МАЕ-Mean Absolute Error) - определяется как средняя абсолютная разница между прогнозируемым и фактическим рейтингами: \[ MAE = \frac{\sum\nolimits_{\{u,i\}} {\left| {p_{u,i} - r_{u,i} } \right|} }{N}, \] где \(р_{u,i} \) - это предсказанный рейтинг пользователя \(u \) по элементу \(i, r_{u,i}\) - фактический рейтинг, и \(N\) общее количество рейтингов, полученных в ходе тестирования.
    Другой, традиционно используемой метрикой, является среднеквадратичная (RMSE- Root Mean Squared Error), которая делает больший акцент на большие абсолютные ошибки, и определяется по формуле: \[ RMSE = \sqrt {\frac{\sum\nolimits_{\{u,i\}} {\left( {p_{u,i} - r_{u,i} } \right)^2} }{N}} \quad . \] Использование этих метрик приводит к рассмотрению всех элементов в равной степени. Однако, для большинства рекомендующих систем, главной задачей является как можно более точное предсказание поведения пользователя. В контексте информационного поиска (IR), выявление хороших на фоне плохих элементов можно рассматривать как различия между "соответствующими" и "имеющими значение" элементами. Здесь могут использоваться другие критерии, например, F-мера сбалансированной ошибки, \(\tau \(-корреляция Кендалла и пр.
    Отметим несколько проблем.
    Новинки и новые пользователи создают серьезную проблему для рекомендующей системы. В совокупности эти проблемы называют проблемой "холодного запуска". Первая из этих задач возникает в системе совместной фильтрации, когда сервис не может быть рекомендован, пока какой-нибудь пользователь не оценил его раньше. Это касается не только новинок, но и может скрыть существующие сервисы, что особенно пагубно для пользователей с особенными (экзотичными) вкусами. Проблему новых пользователей вообще трудно решать, поскольку без предварительного предпочтения пользователя не представляется возможным найти подобных пользователей или построить профиль.
    Другой проблемой является мошенничество. Как только рекомендующие системы коммерческих веб-сайтов начали играть значительную роль в воздействии на рентабельность, так сразу это привело к участию недобросовестных поставщиков в различных формах мошенничества с целью получить от рекомендующих систем результат в их пользу. Как правило, они пытаются надуть популярность собственной продукции (Push атаки) или понизить рейтинги своих конкурентов (Nuke атак). Такие атаки обычно предусматривают создание фиктивных профилей, и используют информацию о работе системы.
    Отметим еще одну область применения приведенных методов - это "анализ клиентских сред".

    Анализ клиентских сред.

    Клиентская среда - это совокупность клиентов (пользователей, cубъектов), регулярно пользующихся фиксированным набором сервисов (товаров, ресурсов, предметов, объектов). Предполагается, что действия клиентов протоколируются в электронном виде. Примерами действий являются: использование сервиса или покупка товара, оценивание (рейтингование) сервиса или товара, обращение за информацией, оплата услуг, выбор тарифного плана, участие в маркетинговой акции, получение бонуса от компании, отказ от обслуживания, и т.д.
    Анализ клиентских сред, АКС (customer environment analysis, CEA) - это технология обработки протоколов действий клиентов, позволяющая эффективно вычислять взаимно согласованные оценки сходства клиентов и сервисов и использовать их для решения таких бизнес-задач, как автоматизация маркетинговых исследований, формирование направленных предложений клиентам, персонализация сервисов, повышение удовлетворённости и лояльности клиентов, более эффективное привлечение и удержание клиентов.
    Технология АКС может быть использована для построения рекомендующих систем (recommender system), персонализации предложений (targeting, direct marketing) и управления взаимоотношениями с клиентами (customer relationship management, CRM).
    Наиболее близкими к АКС направлениями являются коллаборативная фильтрация (collaborative filtering, CF) и анализ соответствий (correspondеnce analysis). АКС имеет два основных отличия:

    Примеры клиентских сред.

    Клиентские среды возникают в самых разных сферах бизнеса, и не только бизнеса. Можно говорить о клиентских средах производителей товаров, дилерских сетей, сетей супермаркетов, операторов связи, эмитентов платежных карт, библиотек, интернет-магазинов, поисковых машин, социальных сетей, форумов, блогов и т. д.
    Возможны и такие приложения АКС, в которых сами термины "клиенты" и "сервисы" едва ли применимы, например, анализ текстов или анализ результатов парламентских выборов. Однако математические методы обработки данных остаются теми же.

    Торговые сети

    "Сервисами" являются товары, "клиентами" - постоянные покупатели, имеющие дисконтную карту. "Действия клиентов" - это покупки товаров.
    Примеры задач:
    1. Сделать клиенту направленное предложение тех товаров, которые ему с большой вероятностью понравятся. Персональное предложение может печататься с обратной стороны чека или выводиться на специальном терминале по запросу клиента.
    2. Вовремя подсказать клиенту, где находится новый товар, о котором ещё мало кто знает, но который с большой вероятностью заинтересует данного клиента.

    Операторы сотовой связи.

    "Сервисами" являются различные услуги (типы соединений), "клиентами" - абоненты сети. "Действия клиентов" - это звонки различных типов (входящие, исходящие, междугородние, международные, SMS, MMS, и т. д.), платежи, подключения и отключения услуг, смены тарифных планов, обращения в сервисный центр, и т. д.
    Примеры задач:
    1. Прогнозирование ухода клиентов (churn prediction), на основе сходства с уже ушедшими клиентами.
    2. Сегментация клиентской базы, выделение целевых групп клиентов.
    3. Выявление схожих услуг при формировании пакетных предложений.
    4. Выявление необычного или потенциально опасного поведения клиентов (fraud detection).

    Интернет-магазины книжной, аудио и видео продукции.

    "Сервисами" являются товары (книги, диски, фильмы, и т. д.), "клиентами" - постоянные покупатели. Действия клиентов - это либо покупки товаров, либо оценки (рейтинги) товаров.
    Примеры задач:
    1. Предсказать рейтинги товаров для данного пользователя и предложить ему список товаров, наиболее интересных для него.
    2. Предложить персональную скидку на совместную покупку нескольких товаров (cross-selling).
    3. Вовремя информировать клиента о появлении новых интересных для него товаров (up-selling).

    Поисковые машины.

    "Сервисы" - это страницы или документы, предлагаемые в качестве результатов поиска, "клиенты" - пользователи поисковой машины. "Действия клиентов" - это переходы со страницы результатов поиска к найденному документу. В данном приложении технология АКС примыкает к анализу веба (web mining), точнее, к анализу поведения пользователей веба (web usage mining).
    Примеры задач:
    1. Ранжировать результаты поиска в таком порядке, чтобы в начале списка оказались документы, с большой вероятностью интересные для данного пользователя.
    2. Разместить на странице адресную рекламу, предлагая данному пользователю посетить сайты, с большой вероятностью интересные именно ему, именно в данный момент.
    3. Найти для данного сайта список наиболее близких к нему сайтов (например, для автоматической генерации страницы полезных ссылок).
    4. Найти для данного сайта список сайтов, наиболее близких к нему относительно данного пользователя (для автоматической генерации персонализированного списка рекомендуемых ссылок).

    Парламентские выборы.

    Здесь в роли "сервисов" выступают политические партии, "клиентами" являются субъекты федерации, территориальные избирательные округа или избирательные участки. "Действия клиента" - это голоса избирателей, отданные партиям.
    Задачи связаны в основном с интерпретацией результатов выборов:
    1. Отранжировать партии по сходству относительно любой заданной партии.
    2. Отранжировать регионы по сходству относительно любого заданного региона.
    3. Понять и визуализировать (например, с помощью карты сходства) политический спектр партий.
    4. Выделить схожие партии, "перетягивающие" голоса друг у друга.
    5. Выделить регионы, в которых данная партия могла бы перетянуть голоса у других партий.

    Анализ текстов.

    В данном случае "сервисами" являются ключевые слова или выражения, "клиентами" - тексты. "Действие клиента" соответствует тому, что данное ключевое слово встречается в данном тексте.
    Примеры задач:
    1. Автоматическая классификация и рубрикации больших объемов текстовых документов или новостных потоков.
    2. Поиск документов по сходству с данным документом.
    3. Поиск наиболее полных и релевантных документов по данной теме.

    Социальные сети.

    В простейшем случае "сервисами" являются страницы (записи в блоге, личные страницы пользователей, разделы форума), "клиентами" - пользователи социального сервиса. Действия клиента - посещение страницы, просмотр сообщений, создание собственных сообщений, добавление/удаление друзей, и т.д. Социальные сети являются более сложным примером клиентской среды, поскольку в них приходится применять анализ текстовой информации. В общем случае имеется уже не два типа взаимосвязанных сущностей (клиенты и сервисы), а три: пользователи, страницы и ключевые слова.
    Примеры задач:
    1. Персональное предложение интересных для данного пользователя страниц, форумов, контактов.
    2. Автоматическая персонализированная классификация и рубрикация страниц, форумов, контактов.
    3. Поиск единомышленников (like-minded people), похожих людей (neighbours).

    Finis coronat opus.

    Задачи для самостоятельной работы.

    Полезная литература. Книги.

    1. Aggarwal C.C. Recommender Systems / C.C.Aggarwal; The Textbook .— Heidelberg, New York, Dordrecht, London: Springer, 2016 .— 518 p.
    2. Lampropoulos A.S. Machine Learning Paradigms. Applications in Recommender Systems / A.S.Lampropoulos, G.Tsihrintzis .— Heidelberg, New York, Dordrecht, London: Springer, 2015 .— 134 p.
    3. Large-Scale Recommender Systems and Netflix Prize Competition / A.Tuzhilin, Y.Koren, J.Bennett та ін.; Proceeding of the Second KDD Workshop .— Las Vegas, Nevada: Netflix, 2008 .— 34 p.
    4. Negre E. Information and Recommender Systems / E.Negre; dvances in Information Systems Set. Volume 4 .— Hoboken: John Wiley & Sons, Inc, 2015 .— 95 p.
    5. Recommender Systems. An Introduction / D.Jannach, M.Zanker, A.Felfernig, G.Friedrich .— Cambridge: Cambridge University Press, 2011 .— 353 p.
    6. Ricci F. Recommender Systems.Handbook / F.Ricci, L.Rokach, B.Shapira; Second Edition .— New York, Heidelberg, Dordrecht, London: Springer, 2015 .— 1008 p.
    7. Schall D. Social Network-Based Recommender Systems / D.Schall .— Heidelberg, New York, Dordrecht, London: Springer, 2015 .— 139 p.
    8. Symeonidis P. Matrix and Tensor Factorization Techniques for Recommender Systems / P.Symeonidis, A.Zioupos .— Switzerland: Springer, 2016 .— 101 p.
    9. Шумейко А.А., Сотник С.Л. Интеллектуальный анализ данных (Введение в Data Mining).-Днепропетровск:Белая Е.А., 2012.- 212 с.

    Полезная литература. Статьи.

    1. Bell R. The BellKor solution to the Netflix Prize /R.Bell, Y.Koren, C.Volinsky // AT&T Labs – Research.— 15 p.
    2. Burke R. Hybrid Recommender Systems: Survey and Experiments / R.Burke // User Modeling and User-Adapted Interaction .— 2002 .— November .— P.1-30.
    3. Evaluating Collaborative Filtering Recommender Systems / J.L.Herlocker, J.Konstan, L.G.Terveen, J.Riedl // ACM Transactions on Information Systems .— 2004 .— Vol. 22, No. 1 .— P.5–53.
    4. Gomez-Uribe C. The Netflix Recommender System: Algorithms, Business Value, and Innovation / C.Gomez-Uribe, N.Hunt // ACM Transactions on Management Information Systems .— 2015 .— Vol. 6, No. 4 .— P.1-19.
    5. The Netflix Prize and Production Machine Learning Systems: An Insider Look // MathWorks .— 2016 .— 9 P.

    Вопрос-ответ.

    Задать вопрос: