feeeper 14 авг 2019 в 07:42

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

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

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

who are you?

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

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

Таблица 1

	Статья 1	Статья 2	Статья 3	Статья 4	Статья 5
Василий	4	0	5	5	0
Иван	0	0	4	5	0
Инна	4	2	4	0	0
Анна	5	5	0	0	5

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

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

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

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

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

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

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

$1 - cos \theta = 1 - \frac{A \cdot B}{||A|| \cdot ||B||}$

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

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

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

$1 - cos \theta = 1 - \frac{4 \cdot 0 + 0 \cdot 0 + 5 \cdot 4 + 5 \cdot 5 + 0 \cdot 0}{\sqrt{4^2 + 0^2 + 5^2 + 5^2 + 0^2} \cdot \sqrt{0^2 + 0^2 + 4^2 + 5^2 + 0^2}} = 0.1349$

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

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

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

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

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

$r_{u,i} = \frac{1}{N} \sum_{u' \in U} r_{u', i}$

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

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

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

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

$r_{u,i} = \frac{\sum_{u' \in U} (1 - simil(u, u'))r_{u',i}}{\sum_{u' \in U} |1 - simil(u, u')|}$

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

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

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

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

$RMSE = \sqrt{\frac{1}{|D|} \sum_{u,i \in D} (\hat{r}_{u,i} - r_{u,i})^2}$

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

$inline$ — множество всех оценок статей пользователями,
$\hat{r}_{u,i}$ — предсказанная оценка пользователя $inline$ статье $inline$ ,
$r_{u,i}$ — реальная оценка пользователя $inline$ статье $inline$ .

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

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

	Статья 1	Статья 2	Статья 3	Статья 4	Статья 5
Василий	4	0	5	5	0
Рекомендательная система 1	1	3	5	2	2
Рекомендательная система 2	4	1	5	3	0

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

$RMSE_{(1)} = \sqrt{\frac{(4-1)^2+(0-3)^2+(5-5)^2+(5-2)^2+(0-2)^2}{5}} = 2.489$

$RMSE_{(2)} = \sqrt{\frac{(4-4)^2+(0-1)^2+(5-5)^2+(5-3)^2+(0-0)^2}{5}} = 1$

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

Реализация

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

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

Disclaimer

Здесь и далее код написан “в лоб” для демонстрации логики работы рекомендательной системы. В реальной жизни лучше использовать все возможности numpy и pandas.

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()

Output [1]

Всего данных: 15313
Положительные оценки: 15121
Активных пользователей: 1007

	Id	DocumentId	Rate	UserId
0	1	1	True	5000
1	2	878	True	2441
2	3	1512	True	678
3	4	1515	True	678
4	5	877	True	5110
...	...	...	...	...

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()

Output [2]

	Id	DocumentId	Rate	UserId	RateInt
0	1	1	True	5000	1
1	2	878	True	2441	1
2	3	1512	True	678	1
3	4	1515	True	678	1
4	5	877	True	5110	1

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

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.

Рекомендации для случайного пользователя

Статья	Предсказанная оценка
DIRECTUM 5.6. Новый полнотекстовый поиск	0.6364
DIRECTUM 5.6 – больше возможностей для комфортной работы	0.6364
Развитие инструмента разработки в DIRECTUM 5.5	0.6364
Компания DIRECTUM представляет DirectumRX	0.5455
Ежегодный выпуск DIRECTUM – теперь 5.1!	0.5455
От А до К. DIRECTUM 5.0 снова обновляется	0.5455
DIRECTUM Jazz – новое мобильное решение от компании DIRECTUM	0.5455
А ты уже обновил DIRECTUM?	0.5455
DIRECTUM 5.6. Супер-колонки и действия в папках	0.5455
Подсветка синтаксиса ISBL в GitLab	0.5455

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

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

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. Ошибка немного больше, чем в первом случае.

Рекомендации для того же случайного пользователя

Статья	Оценка
DIRECTUM 5.6. Новый полнотекстовый поиск	0.3095
DIRECTUM 5.6 – больше возможностей для комфортной работы	0.3095
Развитие инструмента разработки в DIRECTUM 5.5	0.3095
Много служб DIRECTUM — один инструмент администрирования	0.2833
От А до К. DIRECTUM 5.0 снова обновляется	0.2809
Ежегодный выпуск DIRECTUM – теперь 5.1!	0.2784
Компания DIRECTUM представляет DirectumRX	0.2778
А ты уже обновил DIRECTUM?	0.2778
DIRECTUM 5.6. Супер-колонки и действия в папках	0.2758
DIRECTUM Ario – новое интеллектуальное решение	0.2732

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

Резюме

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

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

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

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

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

Теги:

Хабы:

Рекомендательная система для Directum Club. Часть первая, коллаборативная