html текст
All interests
  • All interests
  • Design
  • Food
  • Gadgets
  • Humor
  • News
  • Photo
  • Travel
  • Video
Click to see the next recommended page
Like it
Don't like
Add to Favorites

Рекомендательные системы: user-based и item-based

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



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

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

Мы упомянули два подхода: либо искать похожих пользователей – это называется «рекомендации, основанные на пользователях» (user-based collaborative filtering), либо искать похожие продукты – это, что логично, называется «рекомендации, основанные на продуктах» (item-based collaborative filtering). Собственно, основной алгоритм в обоих случаях понятен.
  1. Найти, насколько другие пользователи (продукты) в базе данных похожи на данного пользователя (продукт).
  2. По оценкам других пользователей (продуктов) предсказать, какую оценку даст данный пользователь данному продукту, учитывая с большим весом тех пользователей (продукты), которые больше похожи на данный.

Осталось только понять, как же всё это делать.

Во-первых, нужно определить, что значит «похожий». Напоминаю, что всё, что у нас есть – это вектор предпочтений для каждого пользователя (строки матрицы R) и вектор оценок пользователей для каждого продукта (столбцы матрицы R). Прежде всего оставим в этих векторах только те элементы, для которых нам известны значения в обоих векторах, т.е. оставим только те продукты, которые оценили оба пользователя, или только тех пользователей, которые оба оценили данный продукт. В результате нам просто нужно определить, насколько похожи два вектора вещественных чисел. Это, конечно, известная задача, и классическое её решение – подсчитать коэффициент корреляции: для двух векторов предпочтений пользователей i и j коэффициент корреляции Пирсона равен

где — средний рейтинг, выставленный пользователем i. Иногда пользуются так называемой «косинусной похожестью», используя косинус угла между векторами:

Но для того, чтобы косинус хорошо работал, желательно всё равно сначала вычесть среднее по каждому вектору, так что в реальности это та же самая метрика.

Для примера рассмотрим какую-нибудь матрицу оценок.


Ручной анализ предпочтений мы оставим читателю, а сами подсчитаем для user-based рекомендаций корреляцию между вектором предпочтений Васи и остальных участников системы.


Мы сейчас привели формулы для user-based рекомендаций. В item-based подходе ситуация похожая, но есть один нюанс: разные пользователи по-разному относятся к оценкам, кто-то ставит всем подряд по пять звёздочек («лайкает» все подряд сайты), а кто-то, наоборот, ставит всем по две-три звёздочки (часто жмёт «дизлайк»). Для первого пользователя низкий рейтинг («дизлайк») будет гораздо более информативен, чем высокий, а для второго – наоборот. В user-based подходе об этом автоматически заботится коэффициент корреляции. А в item-based рекомендациях, чтобы это учесть, можно, например, вычесть из каждой оценки средний рейтинг того или иного пользователя, а потом уже подсчитать корреляцию или косинус угла между векторами. Тогда в формуле для косинуса получится
,
где обозначает средний рейтинг, выставленный пользователем i. В нашем примере, если вычесть из каждого вектора оценок среднее, получится вот что:


И тогда корреляция между вектором оценок фильма «Трактористы» и оценками других фильмов составит (заметим, что с «Once Upon a Tractor» сложилась вырожденная ситуация, потому что пересекающихся оценок было слишком мало)


У этих мер похожести есть свои недостатки и разнообразные вариации на тему, но давайте для иллюстрации методов ими ограничимся. Таким образом, мы разобрались с первым пунктом плана; на очереди второй – как воспользоваться этими оценками похожести (весами )?

Простой и логичный подход – приблизить новый рейтинг как средний рейтинг данного пользователя плюс отклонения от среднего рейтингов других пользователей, взвешенных этими самыми весами:
.
Этот подход иногда ещё называют GroupLens algorithm – так работал дедушка рекомендательных систем GroupLens (кстати, pardon the pun, рекомендую сайт MovieLens] – с него когда-то фактически начиналась серьёзная коллаборативная фильтрация, но и сегодня он может порадовать малоизвестными фильмами, которые вам понравятся). В случае с Васей и «Трактористами» по этому методу ожидается оценка около 3.9 (Петрович чуть подкачал), так что можно смело смотреть.

Для item-based рекомендаций всё совершенно эквивалентно – нужно просто найти взвешенное среднее уже оцененных пользователем продуктов:

Item-based метод в нашем примере предполагает, что Вася поставит «Трактористам» аж 4.4.

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


Остаётся только понять, как быстро искать ближайших соседей. Это уже выходит за рамки нашего обсуждения, поэтому я просто назову два основных метода: в небольших размерностях можно пользоваться k-d-деревьями (k-d-trees, см., например, это введение), а в больших размерностях выручит локально-чувствительное хеширование (locally sensitive hashing, см., например, здесь).

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

P.S. За картинки с формулами спасибо сервису mathURL. К сожалению, русские буквы он не понимает, поэтому таблицы про Васю и Петровича пришлось делать руками.
Читать дальше
Twitter
Одноклассники
Мой Мир

материал с habrahabr.ru

2

      Add

      You can create thematic collections and keep, for instance, all recipes in one place so you will never lose them.

      No images found
      Previous Next 0 / 0
      500
      • Advertisement
      • Animals
      • Architecture
      • Art
      • Auto
      • Aviation
      • Books
      • Cartoons
      • Celebrities
      • Children
      • Culture
      • Design
      • Economics
      • Education
      • Entertainment
      • Fashion
      • Fitness
      • Food
      • Gadgets
      • Games
      • Health
      • History
      • Hobby
      • Humor
      • Interior
      • Moto
      • Movies
      • Music
      • Nature
      • News
      • Photo
      • Pictures
      • Politics
      • Psychology
      • Science
      • Society
      • Sport
      • Technology
      • Travel
      • Video
      • Weapons
      • Web
      • Work
        Submit
        Valid formats are JPG, PNG, GIF.
        Not more than 5 Мb, please.
        30
        surfingbird.ru/site/
        RSS format guidelines
        500
        • Advertisement
        • Animals
        • Architecture
        • Art
        • Auto
        • Aviation
        • Books
        • Cartoons
        • Celebrities
        • Children
        • Culture
        • Design
        • Economics
        • Education
        • Entertainment
        • Fashion
        • Fitness
        • Food
        • Gadgets
        • Games
        • Health
        • History
        • Hobby
        • Humor
        • Interior
        • Moto
        • Movies
        • Music
        • Nature
        • News
        • Photo
        • Pictures
        • Politics
        • Psychology
        • Science
        • Society
        • Sport
        • Technology
        • Travel
        • Video
        • Weapons
        • Web
        • Work

          Submit

          Thank you! Wait for moderation.

          Тебе это не нравится?

          You can block the domain, tag, user or channel, and we'll stop recommend it to you. You can always unblock them in your settings.

          • tachikoma
          • домен habrahabr.ru

          Get a link

          Спасибо, твоя жалоба принята.

          Log on to Surfingbird

          Recover
          Sign up

          or

          Welcome to Surfingbird.com!

          You'll find thousands of interesting pages, photos, and videos inside.
          Join!

          • Personal
            recommendations

          • Stash
            interesting and useful stuff

          • Anywhere,
            anytime

          Do we already know you? Login or restore the password.

          Close

          Add to collection

             

            Facebook

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

            Facebook

            К сожалению, вы не попадаете под условия акции