Сегодня мы поговорим о рекомендательных системах, а точнее о самой простой форме коллаборативной фильтрации. В программе передач: что такое рекомендательная система, на чем основана, каков математический аппарат и как её можно воплотить в код. В качестве бонуса предоставим результаты в виде простого сервиса.
- Что такое рекомендательная система
- Интуиция
- Теория
- Реализация: код и данные
- Сервис Хабра-рекомендаций
- Хабра-аналитика
Что такое рекомендательная система
На самом деле мы ежедневно сталкиваемся с рекомендательными системами, даже если порой этого и не замечаем. В наиболее явном виде их работа видна в онлайн магазинах e.g. Amazon.
Основная задача системы здесь предложить новые товары на базе купленных-просмотренных. Преследуется сразу несколько целей, но основная — предложить товар покупателю, который вероятнее всего приведет к продаже и удовлетворит его запросам. Значит, неформально рекомендательная система предлагает некоторый упорядоченный список товаров, основываясь на предыстории покупателя.
Интуиция
В данной статье мы говорим о коллаборативной фильтрации основанной на пользователях. Это название может показаться грозным, но за ним стоят довольно простые идеи. «Коллаборативный» означает основанный на предпочтениях некоторой группы. Например, если Вася, Петя и Саша покупатели книжного магазина и их вкусы схожи, то можно рекомендовать Саше покупки на основе покупательской истории Васи и Пети.
(картинка взята отсюда)
Картинка описывают простую ситуацию, когда несколько пользователей посмотрели видео, и только некоторым из них понравилось. Когда мы решаем стоит ли порекомендовать пользователю видео, обнаруживаем, что похожие пользователи невзлюбили это видео. Как следствие, не стоит рекомендовать. Иначе говоря мы фильтруем контент на основе схожей группы отсюда и название коллаборативная фильтрация.
Теория
В данной статье мы рассмотрим только случай бинарной оценки: «понравилось» или «нет оценки». Эта модель применима к избранному на Хабре. Если пользователь сохранил к себе статью, значит он считает её интересной или полезной, а если оценки нет, то это ничего не значит, возможно он просто не видел эту статью.
Существует несколько способов фильтровать (а точнее ранжировать) контент, мы рассмотрим так называемый user-based (основанный на пользователях) метод.
Данные
У нас есть две сущности пользователи и статьи в избранном. С каждым пользователем i мы ассоциируем множество статей ui.
Схожие пользователи
Мы определяем «схожесть» двух пользователя i и j, как
Это так называемый Коэффициент Жаккара, который определяет степень сходства двух множеств.
Идея проста — определить насколько общая часть статей двух пользователей относится к их общему количеству.
Рекомендуем статью
Пусть некоторая статья p (от post) не находится в избранном, т.е. не принадлежит множеству ui, тогда мы определяем сходство likes («насколько скорее всего понравится») между пользователем и статьёй следующим образом:
где np и Jp — это количество пользователей и сами пользователи, которые добавили пост p избранное.
Идея за формулой проста, вклад одного пользователя равен степени сходства, и нормализация на число самих пользователей.
Рекомендации
Рекомендации — это несколько постов имеющих максимальное значение likes.
Реализация: код и данные
Для реализации нам необходимо сделать несколько шагов:
- Собрать список пользователей
- Собрать рекомендации
- Посчитать np
- Написать функцию likes и получить максимальные k результатов
Собрать список пользователей
Алгоритм простой: был выбран один из первых постов за 2013ый год и для каждого поста собирались пользователи, которые оставили комментарий, и сам автор поста. Всего собран список из 25 тысяч пользователей. Код функции get_all_user_names можно найти через гит в файле: recommender.py, а сам собранный список пользователей в HabraData репозитории (это репозиторий, где я собираю всякие интересные данные с Хабра) в файле user_list.txt
Собрать рекомендации
У каждого пользователя, например тут, есть закладка избранное, которую можно распарсить и получить данные из списка. Собранные данные можно найти в файле user_favorites.csv, а сам код сбора в том же исходнике, что и выше.
Посчитать np
Для каждого собранного поста проходимся по всем пользователям и считаем количество появлений поста. Данные в файле post_counts.csv.
Функция likes
Основной код функции приведен в спойлере ниже. Кратное описание: для каждого пользователя считаем его сходство со всеми остальными пользователями, и если для другого пользователя сходство не ноль, то обновляем схожесть input-пользователя и соответствующего поста. В конце нормализуем и сортируем в убывающем порядке.
def give_recommendations(username, preferences, weights):
preference = preferences[username]
rank = {}
for user_other, preference_other in preferences.iteritems():
if username != user_other:
similarity = jaccard_index(preference, preference_other)
if not similarity:
continue
for post in preference_other:
if post not in preference:
rank.setdefault(post, 0)
rank[post] += similarity
#normalize and convert to
post_list = [(similarity/weights[post], post) for post, similarity in rank.items()]
post_list.sort(reverse=True)
К прочтению: практическая книга Programming Collective Intelligence и вот этот пост.
Сервис Хабра-рекомендаций
На основе алгоритма сделаем простой сервис рекомендаций для пользователей:
Доступен по адресу:
www.habr-analytics.com/recommender
(осторожно, автор тестировал систему рекомендаций в 4 часа утра)
Алгоритм, рассмотренный в данной статье, является один из самых простых и наивных (по предположениям модели), поэтому не стоит переоценивать результаты его работы. С другой стороны, продвинутые алгоритмы во многом основаны на тех же идеях и используют схожие приемы для моделирования рекомендаций, и поэтому полезно иметь хотя бы общее представлении о фильтрации основанной на пользователях.
Хабра Аналитика
Если аналитика на примере Хабра заинтересовала, то помимо рекомендаций текущая версия проекта www.habr-analytics.com поддерживает монитор статей, анализ пользователей и ряд других опций. Подробнее об интересном применении системы написано в статье "Синдром ступеньки и срез посещаемости Хабра".
А так же в данной статье с описанием каждой из функций в отдельности.
Автор: varagian
