42,85
рейтинг
14 января 2015 в 15:57

Разработка → Неперсонализированные рекомендации: метод ассоциаций

Персональные рекомендации позволяют познакомить пользователя с объектами, о которых он, возможно, никогда не знал (и не узнал бы), но которые могут ему понравиться с учетом его интересов, предпочтений и поведенческих свойств. Однако, часто пользователь ищет не новый объект, а, к примеру, объект A похожий на объект B («Форсаж 2» похож на «Форсаж»), или объект A, который приобретается/потребляется с объектом B (сыр с вином, пиво с детским питанием, гречка с тушенкой и т.д.). Построить такие рекомендации позволяют неперсонализированные рекомендательные системы (НРС).


Рекомендовать похожие/сопутствующие объекты можно, ориентируясь на знания об объектах (свойства, теги, параметры) или на знания о действиях, связанных с объектами (покупки, просмотры, клики). Преимуществом первого способа является то, что он позволяет достаточно точно определить похожие по свойствам объекты («Форсаж 2» и «Форсаж» — похожие актеры, похожий жанр, похожие теги, ...). Однако данный способ не сможет порекомендовать сопутствующие объекты: сыр и вино. Еще одним недостатком этого способа является тот факт, что для разметки всех объектов, доступных на сервисе, требуется не мало усилий.

В то же время почти каждый сервис логирует информацию о том, какой пользователь просмотрел/купил/кликнул какой объект. Данной информации достаточно для построения НРС, которая позволит рекомендовать как похожие, так и сопутствующие объекты.

Под катом описан метод ассоциаций, позволяющий построить неперсонализированные рекомендации, основываясь лишь на данных о действиях над объектами. Там же код на Python, позволяющий применить метод для большого объема данных.

Построение неперсонализированных рекомендаций


Для начала рассмотрим базовый алгоритм построения неперсонализированных рекомендаций. Предположим, что у нас есть объекты — фильмы и пользователи. Пользователи просматривают фильмы. Нашими исходными данными является разреженная матрица D (фильмы x пользователи). Если пользователь u просмотрел фильм f, то в соответствующей ячейке матрицы D стоит 1.

Для того чтобы найти фильмы, похожие на заданный фильм f необходимо знать схожесть фильма f со всеми остальными фильмами. Данные о схожести хранятся в матрице S (фильмы x фильмы).

Базовый алгоритм построения неперсонализированных рекомендаций выглядит следующим образом:

  1. для заданного фильма f найти соответствующую ему строку R в матрице S;
  2. выбрать из строки R множество наиболее похожих на f фильмов — FR;
  3. FR и есть непресонализированные рекомендации (похожие/сопутствующие).

Метод схожести


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

Как определить схожесть фильмов x и y, если их посмотрело множество пользователей X и Y соответственно? Наиболее простое решение — Коэффициент Жаккара, который вычисляет схожесть двух объектов (x и y) как:



Здесь числитель — количество пользователей, просмотревших как фильм x, так и фильм y. Знаменатель — количество пользователей, которые просмотрели или фильм x или фильм y.

Вычисленное значение является симметричным: x похож на y также, как y похож на x. Если же мы хотим сделать коэффициент асимметричным, то можно поменять формулу на следующую:



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

«Проблема Гарри Поттера» или «банановая ловушка»


Рассмотрим указанную выше формулу для случая, когда объект y очень популярен (например, фильм о Гарри Поттере). Так как фильм очень популярен и его смотрело много людей, то sim(x, y) будет стремиться к 1 почти для всех фильмов x. Это значит, что фильм y будет похож на все фильмы, а это в большинстве случаев плохо. Вряд ли «Гарри Поттер» будет похож на фильм «Зеленый слоник».

«Проблему Гарри Поттера» также называют «банановой ловушкой»(banana trap). Предположим, что некоторый магазин пытается увеличить прибыль путем рекомендации покупателю товаров, которые часто берут вместе с тем, что покупатель собирается приобрести. Одним из наиболее покупаемых товаров в продуктовом магазине являются бананы. Используя формулу выше, система будет рекомендовать всем покупателям приобрести бананы. Бананы будут покупаться — все хорошо. Но это плохие рекомендации, так как бананы покупались бы и без рекомендаций. Рекомендуя бананы, мы уменьшаем прибыль как минимум на один удачно рекомендованный товар, отличный от бананов.

Метод ассоциаций


Очевидно, что формулу надо модифицировать таким образом, чтобы объект x делал объект y более привлекательным. Т.е. нужно учитывать не только то, что объекты x и y берут вместе, но и то, что объект x не берут без y.

Модифицируем формулу схожести следующим образом:



Здесь !X — это множество пользователей, которые не просмотрели фильм x. Если y — очень популярный объект, то знаменатель в формуле будет большим. Тогда значение схожести будет меньше, а рекомендации будут более релевантными. Данный метод называется методом ассоциаций.

Сравнение методов


Для сравнения работы метода ассоциаций и коэффициента Жаккара рассмотрим поиск похожих фильмов с использованием этих двух методов по следующим исходным данным.
фильмы\пользователи А B C D E
1. Гарри Поттер и философский камень 1 1 1 1 1
2. Хоббит: Нежданное путешествие 1 1 1
3. Хоббит: Пустошь Смауга 1 1 1
4. Хроники Нарнии: Принц Каспиан 1
5. Сердце дракона 1
Матрица схожести, построенная с помощью асимметричного коэффициента Жаккара, выглядит следующим образом (диагональ зануляем, чтобы не рекомендовать исходный фильм):
фильмы\фильмы 1 2 3 4 5
1 0 0,6 0,6 0,2 0,2
2 1 0 0,667 0 0,333
3 1 0,667 0 0 0
4 1 0 0 0 0
5 1 1 0 0 0
Матрица схожести для метода ассоциаций будет выглядеть следующим образом (помимо диагонали зануляем бесконечности — случаи, когда ).
фильмы\фильмы 1 2 3 4 5
1 0 0 0 0 0
2 1,5 0 2 0 0
3 1,5 2 0 0 0
4 0,25 0 0 0 0
5 0,25 0,5 0 0 0
Как видно из матрицы схожести, метод ассоциаций позволяет учесть сверхпопулярность фильма «Гарри Поттер и философский камень». При построении рекомендаций методом ассоциаций для фильма «Хоббит: Нежданное путешествие» вес «Гарри Поттера» (1,5) будет меньше, чем вес более релевантного фильма «Хоббит: Пустошь Смауга» (2).

Реализация


Ниже приведена функция для построения матрицы схожести на базе метода ассоциаций. Функция написана на Python с использованием scipy и scikit-learn. Данная реализация позволяет быстро и без особых затрат вычислить матрицу схожести для большого объема исходных данных.

Так как в пределах одной строки матрицы значения |X| и |!X| не меняются, а схожие объекты будут находиться в пределах одной строки, то |X| и |!X| были опущены при вычислении метрики ассоциации. Конечная формула метрики выглядит так:



def get_item_item_association_matrix(sp_matrix):
    """Простой способ построения матрицы ассоциаций
    
    :param sp_matrix: матрица с исходными данными о просмотрах (фильмы x пользователи)
    :return: матрица схожести фильмов (фильмы x фильмы)
    """
    watched_x_and_y = sp_matrix.dot(sp_matrix.T).tocsr()
    watched_x = csr_matrix(sp_matrix.sum(axis=1))
    magic = binarize(watched_x_and_y).multiply(watched_x.T)
    watched_not_x_and_y = magic - watched_x_and_y
    rows, cols = watched_not_x_and_y.nonzero()
    data_in_same_pos = watched_x_and_y[rows, cols].A.reshape(-1)
    return csr_matrix((data_in_same_pos / watched_not_x_and_y.data, (rows, cols)), watched_x_and_y.shape)

Заключение


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

— определить минимальное количество данных, при котором можно применять метод;
— определить пороговое значение метрики ассоциации;
— определить, что делать, если у рекомендованных объектов значение метрики ассоциации меньше порогового;
— и т.д.

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

P.S. Удачных рекомендаций!
Автор: @madcat1991

Комментарии (16)

  • +4
    Всё хорошо и интересно, но пара мелочей, которая может быть также полезна и читателям:

    • Когда вводите какую-то новую математическую нотацию — явно прописывайте её перед использованием, все конечно догадываются, что !X — это дополнение множества Х, но лучше всего это явно прописать (у самого с этим проблемы);
    • По возможности использовать стандартные обозначения, например или для дополнения множества;
    • Сложные дроби в несколько этажей тяжело читать, возможно стоит попробовать \rfrac или другие функции для дробей.

    P.S. Данные использованные в примерах где-нибудь доступны? Чтобы самим опробовать этот метод.
    • 0
      Спасибо за замечания, постараюсь учесть в будущем.

      Данные использованные в примерах где-нибудь доступны?

      К сожалению нет
  • 0
    Показать список похожих объектов — это довольно частый кейс.

    В качестве начального baseline действительно разумно построить неперсонализированные похожести и показывать в блоке top-k. У вас сейчас так?

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

    Причем подобный блок после персонализации продолжать маскировать под неперсонализированный, а профит от персонализации измерять на честном A/B.

  • 0
    В качестве начального baseline действительно разумно построить неперсонализированные похожести и показывать в блоке top-k. У вас сейчас так?

    В блоке похожее (в карточке фильма) обычная неперсонализированная top-k похожесть.

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

    Полноценную персонализацию в похожее, своеобразную сортировку фильмов по релевантности для пользователя, сознательно пока не добавлял. Но она есть в планах. Пока что только отдельный блок персональных рекомендаций. Возможно стоит попробовать скрестить его с неперсональными на A/B и сравнить, что и как.

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

  • 0
    Интересная статья, подталкивающая к изучению тонкостей вопроса. Спасибо.
    Вопросик не по теме. А ivi.ru на Python по большей части реализована?
    • 0
      Сейчас основной язык разработки Python. Но также есть разработка на Go, php и JS
  • 0
    Приветствую. В целом неплохо, хотя это не метод ассоциаций.

    Поясню на примере: возьмём поисковый запросы «скачать фильмы» и «смотреть фильмы». Очевидно, что «смотреть» и «скачать» часто используются со словом фильм, то есть — они совместны. Но слова «смотреть» и «скачать» крайне редко участвуют в одном и том-же запросе, но очень часто — в одинаковом окружении. Они — взаимозаменяемы, или, другими словами — ассоциированы.

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

    Как бы я это сделал:

    1. Выстроить статистику в виде фраз. Пользователь посмотрел несколько фильмов? получаем строку вида «название1 название2 название3». Для другого пользователя — «название1 название 5 название8» и т.д.
    2. Обработать полученный текстовый корпус методами снижения размерности — например LSA или Word2Vec
    3. Если использовать Word2Vec — то совместные фильмы получатся при использовании алгоритма bag of words (-nbow 0), а асооциированные — skipgrams (-nbow 1).

    Преимущество подхода в частности в решении «банановой проблемы» и рекомендации пользователю редких, но очень похожих фильмов.
  • 0
    Фича технически интересна, а с точки зрения пользователя есть ли анализ, насколько успешна такая рекомендация (пользователь перешел по ссылке и посмотрел фильм)? Мне, например, в 95% хочется плеваться от рекомендаций в том же ivi.ru, поэтому уже давно не обращаю внимание на этот раздел. Это очень вероятно — субъективно, поэтому хотелось бы статистику увидеть.
    • 0
      Возможно когда-нибудь вынесем в отдельный пост. Сейчас эта информация является конфиденциальной.
  • +1
    Любимая тема и можно долго обсуждать особенности :)

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

    [evil mode]
    Другой интересный вопрос со стороны коммерции. Не всегда множество подсказанных фильмов и выгодных для проката фильмов совпадает.
    [/evil mode]
    • 0
      Интересно узнать что вы делаете с «киноманами» когда множество рекомендаций и множество просмотренных фильмов совпадает.… Вопрос в том, как посчитать наиболее похожий фильм из другого кластера, когда между элементами есть пересечение только по самым общим параметрам вроде «жанра» или года издания.

      Классный вопрос :). На деле у нас несколько рекомендателей (как персонализированных так и неперсонализированных). К каждому рекомендателю есть требования по количество возвращаемых рекомендаций и по минимальному значению веса рекомендации. Если рекомендатель A не набрал нужного количества рекомендаций, либо веса рекомендаций не прошли проверки, то система пытаемся получить рекомендации из рекомендателя B, C и т.д. Последним в каждой группе рекомендателей является рекомендатель-заглушка. Он отдает популярный контент разных жанров независимо от того смотрел пользователь его или нет. Таким образом система всегда возвращает рекомендации.

      Есть еще второй аспект. Каталог ivi довольно большой и часто обновляется. Вероятность, что пользователь посмотрел все в пределах минимальной схожести, на мой взгляд, мала. Но заглушка помогает исключить и эту вероятность.
      • 0
        А тут целых несколько любимых тем :)

        …, то система пытаемся получить рекомендации из рекомендателя B, C и т.д.

        Если на базе нескольких рекомендателей создается единый список, то как ранжируются отдельные элементы в результате? Изначально метрика соответствия в каждом из рекомендателей разная — каким образом они сводятся к единой системе весов?

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

        То есть в итоге это не список рекомендаций, а срез каталога по какому либо признаку (например по неперсонализированному рейтингу). И в случае новичков на сервисе (но не новичков в просмотре кино) мы можем получить список из фильмов, которые они уже смотрели.
        • 0
          Если на базе нескольких рекомендателей создается единый список, то как ранжируются отдельные элементы в результате? Изначально метрика соответствия в каждом из рекомендателей разная — каким образом они сводятся к единой системе весов?


          Пока все банально просто. Рекомендатели имеют свои приоритеты.Возможны два варианта:
          • рекомендатель с более высоким приоритетом ничего не нашел — тогда отрабатывает рекомендатель с менее высоким приоритетом
          • рекомендатель с более высоким приоритетом нашел что-то — тогда результат добирается объектами рекомендателя с менее высоким приоритетом


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


          Пользователю достаточно посмотреть/оценить несколько фильмов, чтобы проблема холодного старта решилась, поэтому мы предлагаем ему самое популярное.
  • 0
    Книга по теме «Программируем коллективный разум», вторая глава про рекомендации.
  • +1
    >Так как фильм очень популярен и его смотрело много людей, то sim(x, y) будет стремиться к 1 почти для всех фильмов x.
    Только для асимметричного варианта если взять столбец, а не строку.

    Второй метод какой-то менее нормированный. Пусть a=x∩y, b=¬x∩y, тогда по последней формуле: sim(x,y)=a/b, а по несимметричной схожести: sim(y,x)=a/(a+b). Соответственно, во втором варианте не требуется(но ничего не мешает) по особенному относиться к случаю b=0(фильм популярный).

    Отношение сходства симметрично, каковы преимущества отхода от симметрии?
    • +1
      Отношение сходства симметрично, каковы преимущества отхода от симметрии?

      Метод ассоциаций и асимметрия имеют преимущество, когда мы имеем дело с сопутствующими объектами. Например, если часто к новой машине мы покупаем новые колеса, это не значит, что также часто с новыми колесами мы покупаем новую машину.

      Соответственно, во втором варианте не требуется(но ничего не мешает) по особенному относиться к случаю b=0(фильм популярный).

      Да, возможно стоит над этим задуматься.

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

Самое читаемое Разработка