Компания
90,48
рейтинг
16 октября 2014 в 17:25

Разработка → Как мы кластеризуем подарки в ОК

Всем привет! Меня зовут Артур, я аналитик в отделе анализа данных департамента рекламных технологий Mail.Ru Group. И я попробую рассказать о том, как мы используем кластеризацию в своей работе.

Чего в этой статье не будет: я не буду рассказывать об алгоритмах кластеризации, об анализе качества или сравнении библиотек. Что будет в этой статье: я покажу на примере конкретной задачи, что такое кластеризация (с картинками), как ее делать если данных действительно много (ДЕЙСТВИТЕЛЬНО много) и что получается в результате.



Итак, задача. У пользователей соц.сети OK.RU, как и во многих других сетях, есть возможность дарить друг другу милые и не очень подарочки. Поскольку такие дарения приносят определенную прибыль — ее хотелось бы максимизировать. Один из очевидных путей максимизации – построить хорошую рекомендательную систему.

Что это значит в смысле подарков в OK.RU? N различных подарков дарятся M различными пользователями ежедневно, а в праздничные дни количество дарений вырастает в десятки раз. Поскольку N и M, как вы, наверное, догадываетесь, крайне велики — для хранения и обработки этих данных мы используем Hadoop.

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

Зачем вообще кластеризовать подарки и как понять насколько подарки похожи? Ответ на первый вопрос примерно таков: когда место отдельного подарка занимает кластер подарков — у нас увеличивается количество дарений каждого объекта и уменьшается количество таких объектов. А значит больше статистики и меньше размерность. Ответов на второй вопрос миллион, но я люблю один конкретный: если пользователь подарил два подарка — они чем-то похожи.



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

Как на этом построить хорошую меру? А все как обычно – за нас давно все придумали, в данном случае это сделал некто Поль Жаккар (англ. Paul Jaccard). Допустим у нас есть A — множество пользователей, подаривших первый подарок и B — второй. Тогда коэффициентом сходства будет формула:



Вообще, распространенных коэффициентов сходства не так мало, но нас вполне устраивает этот. Как только у нас есть «схожесть» — остается выбрать алгоритм кластеризации. Для многих алгоритмов кластеризации необходима пространственная интерпретация объектов. Так, например, простой k-means должен иметь возможность вычислять центроиды. Однако есть алгоритмы, и их достаточно много, которым хватает попарных расстояний или, наоборот, «схожестей» между объектами. К таким алгоритмам относится, например, обобщение k-means – k-medoids. В интернете, безусловно, масса статей на тему кластеризации и найти подходящий алгоритм не составляет большого труда.

В нашем случае, одним из требований было наличие готовой библиотеки, позволяющей работать не только с «игрушечными» датасетами. Кроме того, нам не хотелось явно указывать количество кластеров, так как мы не знаем заранее количество «интересов» пользователей OK.RU. В итоге выбор пал на MCL о котором подробнее можно почитать тут. Кратко: MCL получает на вход файл, каждая строка которого содержит два идентификатора подарков и симилярити и пишет в выходной файл кластеры построчно в виде списка идентификаторов.

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

Итого, решение выглядит примерно так:
  1. Берем много событий вида пользователь U подарил подарок P
  2. Считаем для каждой пары подарков количество пользователей, которые подарили их оба (ничего себе задачка, как вам кажется?). А так же, количество дарений каждого подарка.
  3. Для каждой пары подарков вычисляем коэффициент Жаккара.
  4. Полученные данные скармливаем MCL
  5. Profit!!! (не мог удержаться, сори)

А теперь, собственно, картинки! А именно, примеры полученных кластеров на реальных данных. Одна картинка — один кластер:

цветы бывают разными




туфли и яйца




с новым годом - пошел нафиг




женщины и дети




и даже подарки с загнутой подписью!


На мой взгляд, эта простая история одной кластеризации дает поверхностное представление о той мощи, которая скрывается за словами «машинное обучение». Ведь по сути, что у нас есть на входе? Один простой факт о том, что два подарка дарились одним и тем же пользователем. Что у нас есть на выходе? Кластеры подарков с такой семантикой, которую не всякий модератор способен выделить. Область применения этих данных очевидна — это и банальные рекомендации пользователям, и автоматическое тегирование, и материал для статьи на Хабр. И, позволю себе побыть немного в роли Капитана Очевидность, подарки можно заменить: доменами, поисковыми фразами, покупками в магазине или странами туристических путешествий. Если есть данные, главное — не бояться экспериментировать.

Автор: @Spoilt333
Одноклассники
рейтинг 90,48

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

  • –2
    Не совсем понятно какая от этого польза?
    • +2
      А улучшение рекомендательное системы по вашему недостаточно высокая цель?)
  • +2
    Спасибо, интересно. Пишите еще обязательно!

    Как вы используете результаты кластеризации? Пробовали ли находить пересечения кластеров, предпочитаемых конкретным пользователем?
    • 0
      обязательно:)
    • 0
      Вопросы видимо появились после моего коммента.
      Как используем сейчас ответил ниже.
      Пересечения кластеров — пустое множество. Так как каждый подарок попадает ровно в 1 кластер.
      Но в целом, даже бинарный вектор длиной в кол-во кластеров и 1 там где из кластера дарился хотя бы один подарок — является неплохой фичей для наших рекламных задач.
      • 0
        Просто не заметили :-)
        • 0
          Странно. Я думал, логично, что подарок может входить в разные кластеры, например цветы и кривая надпись. Что именно препятствует этому: алгоритм, отсутствие значимых пересечений в действительности, политика партии?..
          • 0
            Алгоритм дает однозначное сопоставление. По сути, алгоритм находит своеобразные центроиды и бьет пространство объектов на непересекающиеся области.
            • 0
              Кстати вариант похожий по смыслу на «пересекающиеся кластера» мы делали с помощью LDA, но топики подарков получились так себе, из-за того, что Ципфа никто не отменял. Были подарки попавшие почти везде с большим весом. Ну и визуальное представление кластеров получалось не настолько крутым. В этом варианте семантика вылазит на поверхность.
  • 0
    Такой вопрос, почему для коллаборативной фильтрации был выбран кластерный анализ а не ассоциативные правила? они же заточены именно под эту цель.
    Быть может датасет настолько велик что только эта библиотека потянула?
    Кстати, какой порядок числа записей?
    • 0
      Под коллаборативной фильтрацией вы здесь имеете в виду рекомендательные системы в целом или все-таки SVD над спарс матрицами? В общем случае рекомендательные системы это больше чем коллаборативная фильтрация.
      В этом конкретном случае, первое что получается запилить — это улучшение тегирования. Модераторы могут тегировать подарки не по-одному, а кластерами. Это в свою очередь улучшает ранжирование выдачи.
      К сожалению я не могу говорить про порядок числа реальных записей. Но для этого примера я брал примерно 200к разных подарков с медианой количества дарений в районе нескольких сотен.
      • 0
        Т.е. таргетирование происходит вручную без учета интересов пользователей? Если ты девушка — на тебе цветочки, несмотря на то, что твои же выборы входили в совсем другие кластеры?
        • 0
          таргетирование… откуда оно тут взялось?)
          Люди редко хотят подарок просто так. Обычно они ищут его в поиске. Ранжирование поисковой выдачи с учетом персональных интересов и без учета очевидно будет отличаться. Насколько я знаю, пока что история дарений не учитывается. Но есть множество других факторов, например: поисковый запрос, пол, текущий праздник если он есть и т.д. Этот эксперимент можно считать одним из шагов в сторону персональной выдачи подарков.
          • 0
            Я слово «тегирование» прочитал неправильно, сорри :)
          • 0
            Да, тут, видимо, есть еще много интересных возможностей. Удачных экспериментов!
  • –1
    Так и не увидел ответа про ассоциативные правила, почему «побрезговали» этим инструментом? Транзакцией в данном случае выступил бы ID юзера, на выходе устойчивые релевантное правила.
    • +1
      Матрица дарений настолько разрежена, что нормально ассоциативные правила можно применять на очень маленькой подвыборке. Но вопрос тут скорее в другом. Какую задачу вы предлагаете так решать?
      • 0
        Один из очевидных путей максимизации – построить хорошую рекомендательную систему.

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

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

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