Городской АД: школьники и студенты +6



Привет, Хабр. В этом году у нас довольно успешно прошли эксперименты по вовлечению юных программистов в АД:


  • затеяли хакатон, где школьники и студенты соревновались на равных (выиграли школьники), помогли организовать олимпиаду НТИ по большим данным.


  • открыли направление АДских чудес в летних школах. О том, как школьники написали рекомендательную систему ленты новостей Дождя, освоили параметрическое моделирование, осваивали азы социнженерии по Митнику, расскажем в следующей статье.


  • организовали митапы для "укушенных" в Яндексе с Ежом. Ёж (Александр Панин) не устоял перед обаянием юных "датасайнтистов" на хакатоне, с тех пор каждую субботу одна из переговорок превращается в Малый АД под звуки арфы, на которой Ёж играет в перерывах.

Школа


Воодушевленные упорством ребят, решили начать вовлекать студентов постарше. Задумали школу прямо в Москве, пройдет она с 1 по 8 августа на факультете компьютерных наук ВШЭ, к участию приглашаются все желающие возрастом до 22 лет.


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


Отбор


Для участия необходимо пройти отбор – решить реальную задачу, с которой столкнулся наш партнер E­-Contenta при разработке рекомендательного движка для Tviz.tv. До 25 июля принимаем решения любым способом – интересно посмотреть на нестандартные идеи, возможно, кто переплюнет решение партнера. Опытные участники имеют возможность заявить о себе и выиграть грант на бесплатное обучение.


Наша цель — дать возможность молодёжи погрузиться в Data Science не за 180 тысяч на "взрослых" курсах. Отбор нацелен прежде всего на проверку мотивации.


Отборочное задание


Главная задача — на основании имеющихся данных проанализировать интересы пользователей и построить алгоритм рекомендации новых фильмов.
В начале предлагается решить несколько простых аналитических задач (задачи 1 и 2) при помощи предложенных данных, после чего попытаться получить решение творческой задачи.
Идеальное решение задания должно содержать: ответ, код, воспроизводящий этот ответ, и описание того, что вы сделали. Решение рекомендуется присылать на языке Python (2.7 или 3.4/3.5). Можно использовать любые библиотеки, если вы готовы в разговоре объяснить, как они работают. Если вы “списываете” (заимствуете материалы из интернета) — будьте добры сослаться на источник. Заимствование при указанном источнике не наказывается, если вы способны объяснить, что именно происходит в коде и почему он решает ту задачу, для которой вы его используете. Списывание без указания источника карается всегда.
Приветствуется (особенно — на продвинутое направление) код, работающий не только у вас (например, полезно pin'ить зависимости в requirements.txt). Желательно также наличие очевидной / документированной точки входа. Git-репозитории с подписанными коммитами, выложенные в IPFS, будут рассматриваться отдельно :)


Данные


Архив с данными можно скачать здесь. Часть данных была анонимизирована, часть отсутствует – в реальном мире сервера ломаются, данные пропадают. Пример чтения данных.


В нём вы найдёте:


Выборку о том, какому зрителю какие фильмы понравились


train_likes.csv

Таблица со строками вида user_id, item_id, channel, time.


  • user_id — идентификатор зрителя
  • item_id — идентификатор фильма
  • channel — идентификатор канала
  • time — время (timestamp)

Каждая такая четвёрка означает, что в момент time пользователю user_id понравился фильм item_id,
который шёл по каналу channel.


Описания фильмов


items.json

Метаданные о фильмах в формате json (открывается любым стандартным json модулем). Каждая строчка обязательно содержит:


  • id — идентификатор фильма
  • duration — коэффициент продолжительности фильма
  • year — коэффициент года производства
  • genre — номер жанра (категориальная переменная, всего 10 жанров)
  • f_{номер} — дополнительные признаки (см. ниже).

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


Признаки f_* — различные анонимизированные признаки фильма. Примеры таких признаков — «Страна производства — США» или «Бюджет больше $100к» (да — 1, нет — 0 или не присутствует).


Важно. Строчки с описанием есть не у всех фильмов: описано примерно 2/3 фильмов, которые были лайкнуты.


Расписание фильмов


schedule.csv

Таблица со строками вида time_end, time_start, item_id, channel.


  • time_end — время конца передачи
  • time_start — время начала передачи
  • item_id — id фильма
  • channel — id канала

Задача 1

Не все каналы и не все фильмы одинаково популярны. Для начала вычислите, сколько в среднем пользовательских лайков (train_likes) есть у одного канала. Также посчитайте количество фильмов, у которых есть хотя бы 5 «лайков». Рекомендуемый формат вывода – одно вещественное число (среднее число лайков на канал) и одно целое (число фильмов с 5+ лайков).


Задача 2

У зрителей обычно есть свои жанровые предпочтения, причём эти предпочтения могут различаться от канала к каналу. Учтите, что не для всех фильмов известны их жанры — такие фильмы придётся посчитать отдельно. Для начала вычислите сумму лайков для каждого жанра и отдельно — для фильмов, где жанр неизвестен. Далее вычислите такую же сумму лайков по жанрам для каждого из топ­10 самых залайканных каналов.
Рекомендуемый формат вывода — строчка из чисел: число лайков каждого жанра по возрастанию номера жанра, в конце – число лайков для фильмов с неизвестным жанром. Далее 10 таких же строчек для каждого из топ­10 каналов по популярности. Нужно пояснить, какой именно канал показан на каждой строчке.


Задача 3

Ваша основная цель – научиться рекомендовать пользователям фильмы так, чтобы они им нравились. Существует много способов это сделать, используя довольно простые предположения. Например:


  • Вам нравятся фильмы похожие на те, которые вы уже полайкали. Если в выборке есть фильм, который по признакам (items.json) похож на другие фильмы, которые вам понравились, то скорее всего этот фильм вам тоже понравится.
  • Похожим пользователям нравятся похожие фильмы. Если пользователи, которые лайкали те же фильмы, что и вы, как правило лайкают ещё 1 фильм, о котором вы не знаете, скорее всего этот фильм вам понравится.
  • Каналы формируют свои программы так, что в одно время там идут программы, рассчитанные на примерно одну и ту же аудиторию.
  • И так далее

Напутствия и помощь


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


Далеко не все такие идеи окажутся работоспособными, поэтому вам потребуется проверять, работает ли та или иная гипотеза. Например, чтобы проверить, насколько работает идея "смотреть на похожих пользователей", можно воспользоваться метрикой mAP@k или NDCG.


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


Много добра про коллаборативную фильтрацию под спойлером v


Baseline в помощь

tl;dr: https://github.com/goto-ru/2016.09-school-baseline.


Подготовленный нами baseline основывается именно на второй идее – коллаборативной фильтрации.
В нашем алгоритме мы используем только данные про лайки, забывая о признаках фильма. Это очень грубое допущение, наверняка, внесение информации о содержании фильма существенно улучшит результат, попробуйте.


Идея, лежащая в корне нашего метода, заключается в следующем:


  • пользователю нравятся те же фильмы, что и похожим на него пользователям
  • фильм смотрят те же пользователи, что смотрят похожие на него фильмы

Иными словами, у каждого пользователя есть некоторый неизвестный нам набор интересов, который определяет, какие фильмы ему нравятся. У фильма, в свою очередь, тоже есть профиль, отвечающий за то, какой аудитории он нравится. Мы не знаем психологический профиль каждого пользователя и аудиторию каждого фильма, но можем восстановить его при помощи вышеописанных идей.


Косинусная мера


Сначала мы рассмотрим интуитивный способ решения задачи, основанный на том, насколько пользователь подходит под аудиторию фильма.
Представим данные в формате фильм -> посмотревшие пользователи. Рекоммендованность фильма item пользователю user посчитаем так:


  • Для каждого фильма, полайканного пользователем user, найдём других людей, которым понравился фильм.
  • Сложим всех таких «друзей по лайкам» вместе и назовём соседями (neighborhood) пользователя.
  • Для фильма item узнаем его аудиторию — множество пользователей, которые его лайкнули
  • Пригодность фильма пользователю — то, насколько «друзьям по лайкам» пользователя нравится этот фильм.

Подробное описание алгоритма.


Этот способ, пожалуй, лучше случайного гадания, однако он рассматривает всех "соседей" пользователя одинаково, руководствуясь лишь количеством раз, когда они смотрели одинаковые фильмы.
Поскольку пользователи обычно смотрят совсем немного фильмов, зачастую будет оказываться, что два пользователя с почти идеально совпадающими интересами не имеют "общих" фильмов, хотя фильмы одного пользователя понравились бы другому, если бы он о них знал.


SVD


Для того, чтобы исправить этот недостаток, попытаемся перейти от "пользователей, которые смотрели фильмы, просмотренные другим пользователем" к явному получению "интересов пользователя" и "аудитории фильма". Этот ход изрядно улучшит качество результата.


Итак, математика.



Богатый внутренний мир пользователя и художественную глубину фильма нужно как-то закодировать, да ещё так, чтобы было легко понять, насколько близки два пользователя, два фильма или насколько фильм подходит пользователю.


Делать это руками мы, пожалуй, не захотим, поэтому как все нормальные математики скажем, что душа пользователя ограничевается вектором из нескольких чисел. Зная всю сложность и многогранность человеческой натуры, отведём под это аж 100 чиселок (любых действительных чисел). Что конкретно за числа – пока не знаем.


Фильму для верности поставим в соответствие тоже 100 чисел. Выражаясь языком математиков, мы только что ввели 2 вектора — вектор "интересов пользователя" и вектор "аудитории фильма". Выражаясь языком программистов, мы объявили 2 массива, никак их не задали и без повода выпендриваемся.


Теперь давайте поймём, что же мы хотим от этих векторов.
Давайте будем говорить, что вектора "похожи", если их скалярное произведение большое. Насколько большое это скалярное произведение тоже не скажем – мы же математики! Скажем только, что у похожих пользователей пусть будет больше, чем у непохожих. То же самое с фильмами – пусть похожие фильмы имеют скалярное произведение побольше, а непохожие — поменьше.


Наконец, самое важное – у нас есть вектор пользователя, есть вектор фильма. Давайте захотим, чтобы скалярное произведение вектора пользователя на вектор фильма было как можно ближе к 1, если пользователю нравится этот фильм, и к 0, если не нравится или не смотрел.
Почему так – да вот захотели. Можно было захотеть, чтобы если фильм не нравится, было -1, а если не смотрели — 0, но к сожалению, у нас есть только "лайки" пользователей — дизлайков в выборке нет.


А теперь перейдём на больший масштаб. У нас есть несколько десятков тысяч пользователей и того больше – фильмов.
Ещё мы знаем, что такие-то пользователи лайкнули такой-то фильм.


Будем щедры, дадим по 100 чисел каждому пользователю, и даже каждому фильму. Сделать так мы вполне можем — чиселка во float32 "весит" 4 байта, а нам таких чиселок потребуется по грубым прикидкам (число пользователей + число фильмов) ~ 10^5.
Нам нужно, чтобы выполнялось главное условие: скалярное произведение души пользователя на аудиторию фильма должна быть поближе к 1, если пользователь лайкнул фильм, и 0, если не лайкнул.


Назовём вектор i-того пользователя U_{i}, вектор j-того фильма V_{j}. Для простоты обозначений, U — все пользователи, V — все фильмы.


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


\sum_{i,j}((U_{i} ,V_{j})-like_{i,j})\to min,

где like_{i,j}=1, если пользователь U_{i} лайкнул V_{i}, иначе 0.


Наконец, для подгонки под известные математики методы, введём для каждой из 100 компонент векторов "важность" — единую для всех пользователей/фильмов. Формально это — вектор S, в котором опять-таки 100 чиселок.


\sum_{i,j}((U_{i} ,S,V_{j}--like_{i,j})\to min.

Градиентный спуск

Один из способов решения задачи можно описать вот так:
Сначала мы запишем в U и V всех пользователей и фильмов случайные числа.
Далее в цикле:


  • Выбираем пользователя U_{i} и фильм V_{i} .
  • Считаем скалярное произведение векторов U, S, V.
  • Считаем "ошибку", если мы недобрали (ошибка отрицательная) — двигаем чиселки в U_{i}, S и V_{i} так, чтобы скалярное произведение немного увеличилось. Если мы переборщили (ошибка положительная), двигаем те же чиселки в обратную сторону.
  • Наконец, если ошибка равна нулю, ничего не меняем.


    Теперь выбираем следующего пользователя и повторяем процесс до тех пор, пока U, S и V не устаканятся примерно в одних и тех же значениях. За счёт того, что мы каждый раз выбираем нового пользователя и фильм, такие уменьшения-увеличения в среднем за много итераций будут уменьшать нашу "ошибку", и в лучшей степени выполнять наши "хотелки". Таким образом, через много итераций мы получим-таки пригодные для нашей задачи вектора.



От того, что бы намеренно ограничили количество чиселок в векторах на 100, не давая идеально подогнать под все лайки и не-лайки, нам только лучше:


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

Переходя от идеи к реализации и от концепции к конкретным методам и структурам данных: в простом виде достаточно взять только пары user_id <-> film_id из train_likes.csv; каждая такая пара значит, что пользователь user_id смотрел film_id (а ещё в том же файле есть время и канал, которые мы сейчас игнорируем). Мы строим из этих связей sparse-матрицу смежности, к которой применяем Truncated Singular Value Decomposition. Этот метод сжимает исходную матрицу, стараясь найти такое скрытое пространство фичей, где вектора фичей пользователей и нравящихся им фильмов близки; мы получаем приближение k-го порядка. После такого сжатия мы реконструируем исходную матрицу — с некоторой ошибкой. Именно благодаря этой ошибке всё и работает: так, фильмы, которые пользователь не смотрел, но которые нравятся похожим на него пользователям будут теперь иметь значение не 0, а 0.4, т.к. мы не могли сохранить все данные при сжатии, и пользователь "смешался" с похожими на себя.


Код по мотивам всего вышесказанного: матричные разложения и reproducible-тетрадки смотреть бесплатно без СМС.


Ещё раз подчеркнём, что выше используются только минимально возможные данные: смотрел ли пользователь фильм или нет. Рассматривая дополнительные метаданные (например, жанр или время показа), можно значительно улучшить качество предсказания; комбинация методов коллаборативной и контент-фильтрации (посредством инициализиции, например, матрицы признаками фильмов, полученными из метаданных) – следующий логический шаг на скользкой дорожке анализа данных в решении этой задачи.


Интерфейс решения

Рекомендуемый интерфейс: желательно, чтобы в вашей программе была функция (пример), которая принимает параметры (id_пользователя, id_фильма, дополнительная информация) и возвращает предсказанную уверенность модели в лайке. Для подсчёта ранжирующих метрик также потребуется ранжирующий интерфейс: (user_id, k) -> Sequence[confidence].
Главное, что будет влиять на оценку – работоспособность решения (значимо лучше, чем наугад), обоснованность оценки качества решения, и только потом – финальное качество. Простое работающее решение, которое честно проанализировано, всегда лучше, чем безумная смесь всего того, что вы нашли в интернете, про которое не понятно, как оно работает и завышена оценка качества. Машинное обучение использовать желательно, но не обязательно.
Кроме такой системы от вас хочется получить отчёт в произвольном формате, из которого можно понять, что именно вы делали и почему, а также как вы оценивали качество вашей рекомендательной системы. Рекомендуемый максимальный объём отчёта — 3000 символов, включая пробелы: (assert len(u"""ваш отчёт""") <=3000).


Ждем все возможные решения, и даже с большим нетерпением – решения без применения ML. Главное же мотивация, а незнание ML – это верный признак того, что школа будет полезна.

-->


К сожалению, не доступен сервер mySQL