Каждый день пользователи по всему миру получают большое количество различных рассылок — только через сервис MailChimp ежедневно рассылают миллиард писем. Из них открывают 20.81%.

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

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

В этой статье расскажу о том, как реализовать рекомендательную систему с нуля на основе коллаборативной фильтрации.

Первая часть статьи содержит теоретическую основу для реализации рекомендательной системы. Для понимания материала достаточно школьной математики.

Во второй части описана реализация на Python для данных нашего сайта.

Немного теории о коллаборативной фильтрации

Коллаборативная фильтрация, наверное, самый простой подход в рекомендательных системах. Основывается на идее, что похожим пользователям нравятся похожие объекты, например, статьи.

Что значит «похожие пользователи»?

Каким образом определить, насколько Василий похож на Ивана или статья про SQL Server на статью про PostgreSQL?

Посмотрим на примере. Допустим, у нас есть четыре пользователя: Василий, Иван, Инна и Анна. На сайте размещены пять статей: Статья 1, Статья 2, Статья 3, Статья 4 и Статья 5. В таблице ниже число на пересечении пользователя и статьи – оценка статьи пользователем по пятибалльной шкале. Нулём в таблице отмечены статьи которые не были оценены пользователем. Например, Василию понравились статьи 1, 3 и 4.

Таблица 1

Интуитивно можно предположить, что если пользователям нравятся одни и те же статьи, то их вкусы совпадают. Как вам кажется, чьи интересы похожи на интересы Василия?

Интересы Василия больше похожи на интересы Ивана и Инны и менее похожи на интересы Анны. Почему — будет рассказано дальше.

Для дальнейшей работы необходимо формализовать и измерить «похожесть» Василия и Ивана или Инны и Анны.

Проще всего это сделать, если рассматривать оценки пользователя, как описание его профиля. В примере каждая строка в таблице – это описание одного пользователя. Первая строка – описание Василия – это вектор из пяти чисел: [4, 0, 5, 5, 0]; вторая – Ивана – [0, 0, 4, 5, 0]; третья – Инны – [4, 2, 4, 0, 0]; четвертая – Анны – [5, 5, 0, 0, 5].

Теперь можно ввести понятие «меры похожести» описаний пользователей.

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

Косинусное расстояние вычисляется по формуле:

где $$ и $$ — векторы-описания пользователей; $$ — скалярное произведение векторов-описаний; $$, $$ — длины векторов-описаний.

Смысл косинусного расстояния в следующем: если два вектора где $$ и $$ (векторы-описания пользователей) “похожи”, то угол между ними будет стремиться к нулю, а косинус этого угла – к единице. В идеальном случае, когда «интересы» двух пользователей совпадают, косинусное расстояние для них будет равно нулю.

Косинусное расстояние между Василием и Иваном:

Аналогично, косинусное расстояние между Василием и Анной равно 0.715. То есть интересы Василия похожи на интересы Ивана больше, чем на интересы Анны.

Как предсказывать оценки пользователей?

Эта часть — самая интересная. Есть множество различных вариантов. Ниже рассмотрим два простых варианта.

Предсказанная оценка — средняя оценка среди “похожих” пользователей

Самый простой вариант для расчёта предсказываемой оценки — посмотреть, какие оценки статье ставили “похожие” пользователи и взять среднюю оценку:

В этой формуле:

• $$ — оценка, которую предсказываем для $$-ой статьи и пользователя $$,
• $$ — оценка пользователя $$ для $$-ой статьи,
• $$ —множество “похожих” пользователей,
• $$ — количество “похожих” пользователей.

Предсказанная оценка — взвешенная средняя оценка среди “похожих” пользователей

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

В этой формуле:

• $$ — оценка, которую предсказываем для $$-ой статьи и пользователя $$,
• $$ — оценка пользователя $$ для $$-ой статьи,
• $$ —множество “похожих” пользователей,
• $$ — “похожесть” (косинусное расстояние) пользователей $$ и $$.

Как измерить качество рекомендаций?

При создании любой рекомендательной системы следует определить метрику, по которой можно оценивать качество нашей модели — насколько хорошо система предлагает пользователю новые материалы. Например, в качестве такой меры можно использовать среднеквадратическую ошибку ($$) — квадратный корень средней ошибки по всем оценкам пользователя. Формально эта мера описывается формулой:

В этой формуле

• $$ — множество всех оценок статей пользователями,
• $$ — предсказанная оценка пользователя $$ статье $$,
• $$ — реальная оценка пользователя $$ статье $$.

В идеальном случае, когда предсказанные оценки совпали с поставленными пользователем, $$ равна нулю.

Рассмотрим пример. Две рекомендательных системы сделали предсказания оценок для Василия. Результат в таблице ниже.

Интуитивно понятно, что вторая рекомендательная система предсказала оценки лучше, чем первая. Посчитаем $$:

Ожидаемо, что ошибка для оценок второй рекомендательной системы, значительно ниже.

Реализация

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

Для реализации коллаборативной фильтрации достаточно оценок пользователей.

import pandas as pd
import numpy as np
import os

ratings_df = pd.read_csv('./input/Ratings.csv')
print('Всего данных:', ratings_df.shape[0])
print('Положительные оценки:', ratings_df[ratings_df['Rate']].shape[0])
unique_user_ids = ratings_df[ratings_df['Rate']]['UserId'].unique()
print('Активных пользователей:', len(unique_user_ids))
ratings_df.head()

1007 активных пользователей поставили 15313 “оценки”. Из них 15121 “лайк”.

Данные содержат четыре колонки: идентификатор строки из базы данных (колонка Id), идентификатор объекта (колонка DocumentId), признак, что статья понравилась пользователю (колонка Rate) и идентификатор пользователя (колонка UserId).

Для удобства добавим колонку RateInt. 1 в этой колонке значит, что статья понравилась пользователю; -1 — что не понравилась.

ratings_df['RateInt'] = ratings_df['Rate'].apply(lambda x: 1 if x else -1)
ratings_df.head()

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

from sklearn.model_selection import train_test_split
train, test = train_test_split(ratings_df, test_size=0.2)

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

def create_matrix(df):
    ratings_per_user = []
    post_ids = df['DocumentId'].unique()
    for user_id in tqdm_notebook(all_users_ids, 'Пользователи'):
        row = {'user_id': user_id}
        ratings = df[df['UserId'] == user_id]['DocumentId'].values
        for post_id in post_ids:
            row[str(post_id)] = 1 if post_id in ratings else 0
        ratings_per_user.append(row)
    return pd.DataFrame(ratings_per_user)

train_df = create_matrix(train)
test_df = create_matrix(test)

Матрица соответствия пользователей и любимых статей позволит посчитать косинусное расстояние между пользователями:

from scipy import spatial

def cos_distance(x1, x2):
    return spatial.distance.cosine(x1, x2)

at_least_one_fav_post_users = list(train_valuable_df['user_id'].values)

def calculate_distances(df):
    columns = df.columns[:-1]
    cp = at_least_one_fav_post_users.copy()
    data = []
    for user_id_1 in tqdm_notebook(at_least_one_fav_post_users, 'Пользователи'):
        row = {'user_id': user_id_1}
        for user_id_2 in cp:
            x1 = df[df['user_id'] == user_id_1][columns].values[0]
            x2 = df[df['user_id'] == user_id_2][columns].values[0]
            row[str(user_id_2)] = cos_distance(x1, x2)
        data.append(row)
    return pd.DataFrame(data)

train_distances = calculate_distances(train_valuable_df)

Теперь всё готово для того, чтобы подсказать пользователям статьи, которые им, как мы считаем, понравятся.

Реализуем две описанные выше стратегии расчёта рекомендаций: средняя и средневзвешенная оценки среди похожих пользователей.

Первый способ

Берём 10 пользователей наиболее близких к текущему и предсказываем оценку как среднюю по похожим пользователям для статьи:

from tqdm import tqdm_notebook
import heapq 

def rmse(predicted, actual):
    return ((predicted - actual) ** 2).mean() ** 0.5

def get_similar(id, n):
    df = train_distances[train_distances['user_id'] == id]
    d = df.to_dict('records')[0]
    top_similar_ids = heapq.nsmallest(n+1, d, key=d.get)
    top_similar = df[top_similar_ids]
    return top_similar.to_dict('records')[0]

def get_predictions(id, n):
    top_similar_users = get_similar(id, n)
    top_similar_users_ids = list([int(x) for x in top_similar_users.keys()])
    ratings_for_top_similar = train_df[train_df['user_id'].isin(top_similar_users_ids)]
    predicted_ratings = {}
    for article_id in train_df.columns[:-1]:
        predicted_ratings[article_id] = ratings_for_top_similar[article_id].mean()
            return predicted_ratings

rand_n_users = train_distances.sample(50)['user_id'].values
err = 0

for u in tqdm_notebook(rand_n_users):
    pred = get_predictions(u, 10)
    err += rmse(test_df[test_df['user_id'] == u][list(pred.keys())].values, pd.DataFrame(pred, index=[0]).values)

print(err / len(rand_n_users))

Для первого подхода получили ошибку равной 0.855.

Второй способ

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

def get_predictions(id, n):
    similar_users = get_similar(u, 10)
    prediction = {}    
    user_ids = list(similar_users.keys())
    user_similarities = []
    for user_id in user_ids:
        user_similarities.append(similar_users[user_id])
        predicted_ratings = {}

    for article_id in train_df.columns[:-1]:
        prediction_for_article = 0
        numerator = 0
        denominator = 0

        for user_id in user_ids:
            rating = train_df[train_df['user_id'] == int(user_id)][article_id].values[0]
            numerator += rating * (1 - similar_users[user_id])
            denominator += np.abs(similar_users[user_id])    
            predicted_ratings[article_id] = numerator / denominator
    return predicted_ratings

err = 0

for u in tqdm_notebook(rand_n_users):
    pred = get_predictions(u, 10)
    err += rmse(test_df[test_df['user_id'] == u][list(pred.keys())].values, pd.DataFrame(pred, index=[0]).values)

print(err / len(rand_n_users))

В этом случае получили ошибку 0.866. Ошибка немного больше, чем в первом случае.

Полученные результаты можно использовать в разных сценариях. Например, в рассылках новых статей за месяц или добавить на сайте раздел “вам может быть интересно”.

Резюме

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

Преимуществом данного подхода является его универсальность – в рекомендациях никак не учитывается, какие объекты рекомендуются. Одну систему можно использовать как для статей в блоге, так и для товаров в интернет-магазине.

К недостаткам можно отнести следующее:

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

В следующей статье будет рассмотрен другой подход — основанный на анализе самих объектов.