Городской АД: школьники и студенты15.07.2016 07:33

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

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

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

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

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

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

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

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

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

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

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, если не лайкнул.

Назовём вектор -того пользователя , вектор -того фильма . Для простоты обозначений,  — все пользователи,  — все фильмы.

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

где , если пользователь лайкнул , иначе 0.

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

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

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

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

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

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

Рекомендуемый интерфейс — желательно, чтобы в вашей программе была функция, которая принимает параметры (id_пользователя, id_фильма, дополнительная информация) и возвращает предсказанную вероятность лайка.
Главное, что будет влиять на оценку — работоспособность решения (значимо лучше, чем наугад), обоснованность оценки качества решения, и только потом — финальное качество. Простое работающее решение, которое честно проанализировано, всегда лучше, чем безумная смесь всего того, что вы нашли в интернете, про которое не понятно, как оно работает и завышена оценка качества. Машинное обучение использовать желательно, но не обязательно.
Кроме такой системы от вас хочется получить отчёт в произвольном формате, из которого можно понять, что именно вы делали и почему, а также как вы оценивали качество вашей рекомендательной системы. Рекомендуемый максимальный объём отчёта — 3000 символов, включая пробелы (assert len (u»«ваш отчёт»«) <=3000).