Уже не раз писал, что занимаюсь сейчас на двух курсах, посвященных теме BigData и машинного обучения - один для программистов, с практикой расчетов, второй для менеджеров - обзорного плана. Некоторые у меня периодически спрашивают - что там у тебя на занятиях Data-MBA происходит, насколько это интересно и полезно? Надеюсь, конспект ответит на такие вопросы.
Сразу предупрежу, конспект не полный, все же речь идет о платном курсе, а не о публичных чтениях. Поэтому приведу фрагмент конспекта занятия, примерно на 1 час 10 минут времени двухчасового занятия.
Рекомендательные системы, Школа данных Билайн, курс Data-MBA,
Сергей Марин (СМ), основатель Школы данных Билайн, открыл встречу.
СМ: Один из первых распиаренных примеров в области рекомендательных систем, это кейс - "пиво и памперсы". В США проанализировали чеки - кто и что покупает. Было замечено, что пиво нередко покупают в комбинации с памперсами. После чего в магазине стали выставлять дорогие сорта пива рядом с памперсами. Также провели исследование с тем, чтобы понять, почему так происходит, и выявили, что пиво покупают мужчины, которые приходят в магазин для того, чтобы приобрести памперсы. Так исследование позволило повысить доходы магазина от продажи пива.
Другой случай раннего использования рекомендательных систем носит немного скандальный характер. В США провели анализ на больших выборках данных и выявили, какие товары женщины начинают покупать в период беременности. Скандал случился когда одной несовершеннолетней девушке пришло рекламное сообщение из которого было ясно, что поскольку девушка беременна, магазин рекомендует ей приобрести также вот такой-то товар. Папа девушки немедленно обратился в суд, который в ходе слушаний выяснил, что девушка действительно беременна. А реклама пришла в связи с тем, что девушка покупала именно те товары, которые, как выявило ранее исследование, с высокой долей вероятности покупают только беременные.
То есть одна из основных задач, которые стоят перед рекомендательными системами - это выявление закономерностей в покупках, связей - что с чем обычно люди приобретают. А также выявление групп людей по схожести покупок, поскольку это позволяет делать выводы, что если А и Б в целом схожи по группе покупок, то можно рекламировать для Б то, что купил А, ожидая, что Б это тоже заинтересует, и наоборот.
Сегодня мы поговорим о современном статусе рекомендательных систем, о том, как они работают, какие данные необходимы для того, чтобы построить рекомендательную систему. Поговорим о том, чем отличаются РС и как измерять качество работы РС (о метриках качества). Подумаем над вопросом - стоит ли писать РС самостоятельно (это возможно, это не rocket science) или лучше приобрести готовое решение. Сколько это может потенциально стоить, во что предстоит инвестировать. Немного поговорим об алгоритмах, чтобы понимать, как примерно это работает (основной - это SVD). О специалистах, которые для этого нужны. И о направлениях развития.
Александр Крот (АК), преподаватель Школы данных Data-MBA Билайн продолжил тему.
АК: Как рекомендательные системы получили распространение? Сергей уже привел пару примеров, я расскажу еще о некоторых. С 2006 по 2009 года компания Netflix проводила конкурс на улучшение своей рекомендательной системы, который стал весьма популярен. В этот период фильмы распространялись не через интернет, а на кассетах. Компания несла значительные затраты, связанные с логистикой. Возникла идея, что человеку, который заказал какую-то кассету, можно предложить еще несколько, но, разумеется, не случайным образом, а с тем, чтобы вероятность того, что их купят, была высокой.
К 2006 году Netflix уже располагала самописной рекомендательной системой, но компания хотела повысить качество ее рекомендаций хотя бы на 10%. Был объявлен конкурс, победителю обещали $1 млн. Несмотря на немалый интерес к теме и немалое число участников, почти за три года ни одна из команд, которые приняли участие в конкурсе, не смогли достичь цели - повысить качество рекомендаций на 10%. И буквально за 20 минут до окончания конкурса сразу две разных команды послали решения, которые пробили эту отметку. Удивительно, но тот уровень качества, который обеспечивали решения этих двух команд, был равен с точностью до четвертого знака после десятичной запятой.
Эта история придала основательный импульс теме развития рекомендательных систем. Их внедрением стали интересоваться самые разные компании. Многие стали задумываться, что рекомендовать можно не только фильмы, но музыку, веб-страницы и так далее.
Известным сервисом сегодня является Pandora - этот сервис подстраивается под музыкальные предпочтения человека и со-временем радио начинает играть для него в основном то, что человеку нравится.
Другой известный сервис - это Amazon, который подбирает книги на основе схожести спроса.
В теме "рекомендательные системы" есть три основных понятия, которые следует помнить. Во-первых, это пользователи (users), второе - это товары (items), третье - события (events) . События состоят в том, что пользователю U понравился (или не понравился) товар I. Можно также говорить об оценке, которая характеризует степень, насколько товар понравился или не понравился. То есть событием r[u,i] может быть то, что U поставил товару I оценку R. Это "базовая механика" рекомендательной системы.
Основная задача рекомендательной системы заключается в том, чтобы по каким-то имеющися у нас данным для каждого пользователя предсказать, какую оценку R он поставит каждому из товаров. Зная оценки, мы сможем давать какие-то рекомендации. Например, если мы прогнозируем, что для товара I пользователь U поставит высокую оценку, то стоит этому пользователю об этом товаре рассказать. Скажем, если у нас есть некий набор товаров, то мы можем их отранжировать по прогнозируемым R, затем выбрать Топ-5, исходя из максимума R, и предложить эти Топ-5 товаров вниманию пользователя.
Как это может работать?
Данные о пользователях, товарах, событиях/оценках удобно держать в виде матрицы. Например, по строкам - пользователи, по столбцам - товары, в пересечениях - оценки. Проблемой является запуск рекомендательной системы - ведь в момент начала ее работы у нас, скорее всего, нет ни одной оценки.
Давайте пока что представим, что ситуация несколько иная, что у нас уже заполнено примерно 40-50% ячеек таблицы. В этом случае задачей рекомендательной системы будет восстановление всех пропушенных в таблице значений. Делать это можно различными способами.
Начнем с простых алгоритмов, которые на уровне идеи понятны многим из вас. Первая очевидная идея заключается в том, что похожие люди смотрят похожие фильмы (покупают похожие товары). И наоборот, люди, покупающие похожие товары, вероятно, похожи. Соответствующие методы получили название Content-based или Item-based.
Как они работают?
- Пользователю рекомендуют объекты, похожие на те, которые этот пользователь уже употредил
- Похожесть оценивается по признакам содержимого объектов (о ней мы уже говорили на прошлом занятии).
- Сильная зависимость от предметной области, полезность рекомендаций ограничена. Т.е. рекомендательные системы для фильмов и для музыки будут разными.
Есть более универсальный способ - это так называемая коллоборативная фильтрация или алгоритм SVD.
Для рекомендаций используется история оценок, как самого пользователя, так и других пользователей. Это более универсальный подход, который часто дает лучший результат. На сегодня он наиболее распространен, в том числе и в силу понятности, а также потому, что он хорошо сводится к задачам машинного обучения (ML). У метода есть свои проблемы, в частности, "холодный старт". Что делать в этой ситуации?
Пользователей можно разбить на множество небольших групп. И считать, что внутри группы у пользователей вкусы схожие, что они интересуются одними и теми же товарами. И если кто-то в группе что-то купил или оценил, то можно эти данные использовать для всех членов группы.
Важно понять, что даже если вы не пишете решение с нуля, а покупаете готовое, то придется потрудиться с его настройкой - например, правильными описаниями объектов, "холодным стартом" и другими проблемами.
СМ: Netflix - это хороший пример, но давайте вспомним что-то, с чем мы знакомы лучше, из местной практики. Ozon, Яндекс.Радио. Как вы думаете, что является оценкой пользователя в Яндекс.Радио?
- Дослушивают ли до конца ту или иную композицию
СМ: Верно. Т.е. важно понимать, что является метрикой в каждом конкретном случае.
Несмотря на то, что рекомендательные системы - это уже проработанная тема, такие системы внедрены не везде. И сегодня зачастую наличие рекомендательной системы является дифференциатором компании, ее услуг. Знаком ли вам сайт okko.tv ? У него очень качественный рекомендательный движок.
АК: Вернемся к примеру с Netflix, стоит отметить, что для построения рекомендательных систем сравнимого масштаба компании, вероятно, придется создавать какую-то инфраструктуру для хранения данных. Данных много, работать с ними с использованием стандартного КИХ (корпоративного хранилища информации) может быть сложно.
У Netflix на момент внедрения системы были такие показатели: 0.5 млн пользователей, 18 тысяч фильмов, 100 млн оценок (от 1 до 5). Если умножить 0.5 млн на 18 тыс, то получим 9 млрд ячеек в матрице. Т.е. матрица была очень слабо заполненной. Что не помешало им сделать очень высококачественную рекомедательную систему, которая помогла заработать дополнительные деньги.
АК: Рассмотрим кейс крупного интернет-магазина. Примерно по такой схеме работает, например, рекомендательная система Озона.
Какие объекты есть в процессе - есть пользователи, есть товары, есть события. Ясно, что нужно собрать как можно больше данных о товарах, о пользователя и о действиях пользователя. Данные пользователя на первом этапе - это данные его регистрационной анкеты, в частности. Данные о товаре магазин, как правило, получает от поставщика вместе с товаром, либо из других источников. С ними, как правило, проблем нет. В частности, в нашем примере речь идет примерно о 8 млн постоянно обновляемых товарах, их описаниях, цене, доступности. Для их хранения хватит и обычной информационной базы предприятия. То же и данные о пользователях, анкетные данные могут храниться в обычной таблице, в реляционных базах данных, в SQL сервере, который есть у любого магазина.
Иное дело - данные о транзакциях, о действиях пользователей. Пользователь отобрал товар в корзину. Пользователь поставил лайк. Пользователь просмотрел каталог. Таких действий очень много - это примерно в среднем 100 событий в секунду, такой поток данных по примерной оценке "весит" 15 ГБ/день. Для хранения таких объемов данных желательна уже какая-то продвинутая система.
Откуда берутся данные о действиях пользователей? Вы знаете, что практически на всех сайтах стоят счетчики, фиксирующие практически любые действия пользователей. Эти данные поступают в очередь и складываются в Hadoop-кластер, в нашу файловую систему HDFS через такие инструменты очереди, как RabbitMQ и Flume. Hive в этой системе позволяет простыми запросами получать необходимые выборки из распределенной файловой системы.
Такая рекомендательная система, это уже пример работы с Big Data. Алгоритм работает с данными в Hadoop-кластере, куда также добавляются через Sqoop данные о пользователях и товарах.
Сформированные рекомендации складывают в базу данных, которую называют Cassandra в данном магазине. Это известное решение, особенность которого - быстрая выдача результатов. Скорость выдачи важна потому, что пользователь должен еще быть на сайте в момент, когда его данные обработаются и ему будут выданы рекомендации.
СМ: Hadoop кластер не обязательно строить внутри компании. Впрочем, сейчас часто компания считает, что это ее конкурентное преимущество и предпочитает его создать у себя.
Для интернет-компании проблемой является идентификация пользователя, ходящего по страницам сайта. Для этого удобны, например, карты лояльности или что-то подобное. Идентификация даже более сложная задача, нежели построение ИТ-системы.
АК: Вернемся к инструментам - как это было сделано. Изначально систему писали на языке Java. Выбор был обусловлен тем, что Java - это язык, на котором написан Hadoop, логично было бы, чтобы и алгоритм реализовывался на этом же языке. Кроме того, тогда еще не было Spark и других современных средств.
Ожидаемый плюс был бы - быстрота работы. Минусы просматривались такие: программировать на Java достаточно непросто, язык "многословный", математикам трудно принимать участие в работе - расширять или улучшать алгоритм по мере надобности. Кроме того, в Java бедный MapReduce API. Например, а каждый tuple (кортеж) приходится заводить свой класс.
В итоге решили взять Apache Spark.
Почему сейчас столь популярен Spark? Представьте, что у вас есть кластер Hadoop, в частности, есть HDFS-система, в которой лежит множество логов. И вы хотите делать какие-то итеративные вычисления. Что-то взять, посчитать что-то по этим данным, а затем положить результат обратно. Все алгоритмы машинного обучения итеративны - для них это оптимальная схема работы. Многие из вас знают, что читать данные с диска в ОЗУ, и затем выгружать данные на диск - это достаточно дорогие операции.
Что позволяет делать Spark? В вашем кластере помимо большого числа недорогих жестких дисков есть оперативная память. Фреймворк Spark грузит данные в оперативную память и в ней работает. На диск будет затем записан только конечный результат множества различных операций. Это серьезно сокращает число операций I/O. Это обеспечило Spark немалую популярность. Из других плюсов - Spark очень неплохо подключается к Hive-таблицам, можно прямо из Spark доставать данные из кластера. Код на Spark лаконичный. В Spark есть немало библиотек, в частности в нем есть модуль "рекомендательная система", которой можно "скормить" ту таблицу о которой мы ранее говорили (пользователи/фильмы/оценки), и этот модуль выдаст некие рекомендации.
Есть, конечно, и минусы - проект пока сырой, не все работает из коробки, на задачах большого размера может работать неустойчиво.
Рекомендательную систему решили написать на языке Hive. SQL-запросы поверх больших таблиц писать проще, они выразительнее и понятнее, чем даже Python-код на Spark.
Все, что можно сформулировать в виде SQL-запроса считается алгоритмом быстро. Минус в том, что если в SQL-виде запрос написать не получается, то придется писать UDF (User-Defined Function) на Java.
В результате опытным путем сложилось представление, какие инструменты можно использовать при построении рекомендательной системы. В частности хорошо работает следующая комбинация:
40% Apache Spark (Python) + 50% Hive on TEZ + 10% Hive UDF (Java)
Плюсы такого подхода. Удобно парсить данные в Spark на Python. Далее эти данные можно сложить в Hive-таблицу и работать с ними SQL-запросами. И поскольку данные хранятся в кластере, с ними можно вести любые ETL-работы, готовить их так, как нам необходимо. Это занимает чуть не половину всего времени и делается инструментом Hive, который близок аналитикам, знакомым с SQL-запросами к корпоративному хранилищу.
Если возникают сложности, то пользуются Hive UDF, для сложных преобразований.
Достигается 70% переиспользование кода на пути от прототипа к продакшену, как правило, на UDF переписываются только критичные по производительности и не очень сложные функции, которые универсальны. В отличие от ML, где зачастую прототип приходится затем переписывать на продуктовой стадии на других языках программирования, в случае с Apache Spark мы изначально работаем с производительной структурой и потому формируемый алгоритм, как только он начинает работать, можно будет довести до продуктивного решения сравнительно быстро.
Математики могут улучшать алгоритм, если конечно они знают Python и SQL!
У каждого инструмента есть минусы, это нужно иметь в виду и уметь пользоваться плюсами.
СМ: Какая мораль из всех этих технических знаний? Когда к вам придет консультант по рекомендательным системам, расскажет, что у него есть мега-суперская рекомендательная система, покажет даже пару клиентов, которые ее используют... вы будете готовы ее купить. Следует задаться двумя вопросами.
Во-первых, как этот человек будет интегрировать свой алгоритм с вашими данными? Если он не сможет об этом уверенно говорить, не сможет это на пилоте показать, то у вас могут возникнуть проблемы. Основное время, которое у вас уйдет на внедрение готовой рекомендательной системы, уйдет как раз на интеграцию с вашими данными.
Второе. Все начиналось с Hadoop/Java. Но Java - это время. В смысле - большие затраты времени. На Java программировать долго. Да, она стабильна, она надежна. Но когда система динамически меняется, а это с рекомендательными системами случается сплошь и рядом, то Java - не лучший инструмент. Но другие инструменты практически все "в процессе развития".
Поэтому ваш второй вопрос к консультанту - как будет осуществляться поддержка системы? Потому что система почти наверняка будет "глючить", и нужно будет эти глюки устранять. Кроме того в систему, в алгоритм, нужно будет вносить изменения.
Следует помнить об этих вопросах, если соберетесь внедрять такую систему.
АК: Перейдем к теме "Как оценить качество работы рекомендательной системы"?
Рассмотрим матрицу Item-User, где в ячейку на пересечении пишется оценка пользователя.
Нам нужно прогнозировать, какую оценку поставил пользователь u фильму i ? Т.е. нам нужно уметь спрогнозировать число. Т.е. это задача регрессии. Как оценить прогноз, который сделает наш алгоритм.
Здесь r с крышкой - это прогнозное значение и r ui - это которое изначально было. Метрика позволяет понять, насколько далеко наши прогнозы отклонились от того, что известно, насколько мы ошибаемся в прогнозах. Значение отклонения должно быть минимальным.
Минусы такой метрики - в предсказании высокой оценки и низкой оценки ошибка имеет одинаковый вес - это не всегда удобно. Эта метрика не учитывает также то, например, что есть люди, которые принципиально не ставят высокие оценки.
Поэтому всякий раз, когда речь идет о задачах машинного обучения, желательно смотреть не на одну, а на несколько различных метрик. В частности на известные метрики Precision и Recall. Для множества рекомендованных объектов R и множества объектов, которые на самом деле нравятся пользователю:
Precision - доля объектов, которые мы верно рекомендовали. Обе эти метрики должны быть как можно больше. Если Precision большой, но при небольшом значении Recall, это не очень хорошо. Пока что нет готовых алгоритмов оптимизации рекомендательных систем, которые бы оптимизировали напрямую обе эти метрики. Поэтому на практике обычно оптимизируют RMSE, а затем смотрят, какими при этом получаются Precision и Recall.
СМ: При покупке рекомендательной системы всегда просите, чтобы вам сделали dashboard, где вы сможете наблюдать за показателями Precision и Recall. Не смотрите на то, что вначале показатели будут выглядеть не идеально, вашей системе еще предстоит обучиться. Важно, чтобы метрики не падали. Если вы заметите падение, это значит, что что-то пошло не так и нужно вмешиваться.
АК: Поговорим о проблемах, с которыми приходится сталкиваться при запуске рекомендательных систем. Первая проблема - это так называемая проблема "холодного старта". Если ваши пользователи еще не давали никаких оценок фильмам или товарам, то откуда вам взять соответствующие данные? Возникают вопросы - что показывать первым пользователям, которые появляются на сайте? Второй вопрос - кому рекомендовать вновь добавленные фильмы?
Рассмотрим решение проблемы "холодный старт для пользователей". Пользователь только пришел на сайт, зарегистрировался, что ему предложить? Прежде всего проводим анализ - что мы знаем о пользователе - это основа. Во-первых, пользователь уже заполнил какую-то анкету, возможно он указал имя, возраст, пол. Какие-то демо-данные, которые обычно используются при регистрации. Во-вторых, можно использовать данные пользователя из соц.сетей.
(
АБ: АК рассказывает о кликджекинге. Пропущу в конспекте)
АК: Далее возможны варианты. Например, можно экспертным путем определить стереотипы, пример - предлагать мультфильмы только людям моложе X лет. Некоторые до сих пор так работают.
Второй путь - применение машинного обучения, а именно кластеризации. Взять всех пользователей и провести для них кластеризацию. Всю пользовательскую базу условно бьем на кластеры. В качестве признаков для кластеризации берем демографические признаки. Например, у нас в первом кластере - женщины, второй мужчины, третий - пожилые люди, четвертый - дети. Далее при появлении нового пользователя мы имеем все характеристики для того, чтобы отнести его к одному из кластеров, соответственно рекомендуем ему то, что рекомендуется для кластера.
Третий путь. Как вы помните у нас есть матрица товары/пользователи. И мы умеем прогнозировать некоторую оценку R. Эти алгоритмы способны доубучаться. Для демографических данных экспертно мы проставили исходно некоторое количество оценок. Далее обучаем алгоритм на основании этих неточных данных и проведем прогноз для всей совокупности людей. Теперь у нас больше данных, и мы можем провести дообучение.
АБ: на этом завершу конспект, выше я представил первые 70 минут занятия, осталось еще 50 минут, которые оставляю "за кадром". Курс коммерческий и выкладывать его весь в открытый доступ было бы некорректно.
О чем было дальше - в основном о том, как найти в соц.сети ВКонтакте Топ-100 пользователей за 1 минуту.
Надеюсь, вы получили представление, если не о курсе data-MBA в целом, то хотя бы о 4-м занятии этого курса.
+ +
Что еще я писал о занятиях.
Data-MBA для менеджеров.
-
Анонс: Data MBA для менеджеров и бизнесменов
-
Что было на втором занятии (Машинное обучение, методы, метрики, инструменты анализа "малых данных", инструменты анализа Big Data, бизнес-процесс работы с Big Data, подготовка специалистов в области Big Data, кейс Титаник, обработка текстов).
-
Третье занятие "Анализ текста", Петр Ермаков, краткий конспект
- Четвертое занятие "Рекомендательные системы", Александр Крот, фрагмент полного конспекта (см. выше).
Школа данных Билайн. Машинное обучение и Big Data
-
Завтра у меня первое занятие в Школе данных Билайн (анонс)
-
Анонс Школы данных Билайн на хабре
-
Как прошло мое первое занятие
-
Как прошло мое третье занятие
-
Краткий конспект по теме Patter Mining. Частые множества и ассоциативные правила
