Рекомендательные системы: 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. К сожалению, русские буквы он не понимает, поэтому таблицы про Васю и Петровича пришлось делать руками.
    Surfingbird
    77.75
    Company
    Share post

    Comments 17

      0
      Увидел матан на Хабре и испугался, настолько отвык :)

      Введение про Васю гениальное. Сразу объясняет, о чем, собственно статья, и позволяет в ней разобраться.

      > Остаётся только понять, как быстро искать ближайших соседей.

      Это хорошо решается в graph базах данных, и имеет смысл, наверное, хотя бы часть данных хранить в графах и пользоваться чем-то типа Gremlin'а для поисков. Но это уже тех. детали.
        0
        Спасибо на добром слове! Вроде матана не планируется. :) Этот пост можно с большой натяжкой назвать геометрией разве что. :)

        Можете ссылку кинуть о том, что вы имели в виду про graph databases? Тут же нет статического графа как такового, расстояние между элементами базы постоянно меняется, и надо уметь считать расстояние между любой парой (а от graph database на полном графе толку немного, наверное :) ). Какие-то работы гуглятся, конечно:
        www.ncbi.nlm.nih.gov/pmc/articles/PMC2860326/
        но про «хорошо решается» я не слышал… или я недопонял, о чём идёт речь?
          +1
          Граф базы данных из популярных — это Neo4j и FlockDB.

          Есть очень симпатичная библиотека для создания запросов к таким базам под названием Gremlin. Здесь описание того, что можно делать.

          А так — да, по граф. базам данных практически работы нет. Есть некоторые презентации у автора Гремлина.
            0
            Спасибо! Про Gremlin не знал, попробую разобраться, зачем это всё может быть нужно в данном случае. :)
              0
              > попробую разобраться, зачем это всё может быть нужно в данном случае.

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

              Остаётся только понять, как быстро искать ближайших соседей.


              В простейшем случае — это все люди, до которых от нас ровно один шаг в графе, что для формулы не подойдет :)

              В более сложных — можно играться с графами на основе разных критериев (вплоть до того, чтобы проводить ребро от каждой сущности к каждому пользователю). Тога посик становится если не тривиальным, то выполнимым. Например: github.com/tinkerpop/gremlin/wiki/Flow-Rank-Pattern
                0
                Вот я и не понял, что значит «один шаг в графе». Расстояние можно подсчитать между любой парой юзеров, и эти расстояния меняются после каждой новой оценки — как определить граф так, чтобы он не оказался почти полным?..

                Если же говорить про настоящие графы, то, например, тот же социальный граф действительно можно использовать в рекомендациях — возможно, поговорим об этом ещё.
                  0
                  Ну, шагом я имел в виду ребро.

                  А так… Берем Map Reduce в руки — и вперед, высчитывать :)
                    0
                    Ну, так я и спрашиваю: как определить рёбра в графе?

                    MapReduce — дело хорошее, если всё параллелизуется идеально. kNN в этом смысле — не слишком удобная штука, хотя да, методы есть: www.lsdsir.org/wp-content/uploads/2010/05/lsdsir10-2.pdf
                      0
                      > Ну, так я и спрашиваю: как определить рёбра в графе?

                      Вот это пока не знаю :(
        +1
        Для интересующихся темой ещё можно почитать книгу на английском Programming Collective Intelligence, там одна из глав посвящена составлению рекомендаций — Collaborative Filtering.
          0
          Она уже давно переведена на русский: habrahabr.ru/blogs/books/79151/
          Мне она показалось очень поверхностной. Автор переусердствовал в избегании математики, в итоге вместо того, чтобы дать емкую и простую формулу вроде тех, что встречаются в этой статье, он словами описывает, что нужно сложить и где поделить, что очень тяжело воспринимается.

          (формулы правда есть в приложении, но все равно читать эту книгу тяжеловато).
            0
            Да, избегать математики тут сложно и совершенно ни к чему, математика только способствует пониманию. Следующая инсталляция должна сделать этот тезис совсем очевидным. :)
          0
          Спасибо, очень интересно! Продолжайте, обязательно.
            0
            Спасибо на добром слове! Будем продолжать.
            0
            Очень интересно, спасибо. Параллельно писал код для проверки и у меня получилось, что для user-based корреляция с Петровичем равна -0.1890.
              0
              И, как следствие, прогнозируемая оценка будет выше — 4.1.
              0
              да, в статье ошибка с Петровичем. Так же не очень понятно — почему в формуле GroupLens algorithm в числитель идет вес со знаком и тот же самый вес в знаменатель уходит в сумму уже по модулю…

              Only users with full accounts can post comments. Log in, please.