http://habrahabr.ru/company/ivi/blog/232843/


Одной из наиболее популярных техник для построения персонализированных рекомендательных систем (RS, чтобы не путать с ПиСи) является коллаборативная фильтрация. Коллаборативная фильтрация бывает двух типов: user-based и item-based. User-based часто используется в качестве примера построения персонализированных RS [на хабре, в книге Т.Сегаран,...]. Тем не менее, у user-based подхода есть существенный недостаток: с увеличением количества пользователей RS линейно увеличивается сложность вычисления персонализированной рекомендации.

Когда количество объектов для рекомендаций большое, затраты на user-based подход могут быть оправданы. Однако во многих сервисах, в том числе и в ivi.ru, количество объектов в разы меньше количества пользователей. Для таких случаев и придуман item-based подход.

В этой статье я расскажу, как за несколько минут можно создать полноценную персонализированную RS на основе item-based подхода.

Немного теории

Рассмотрим получение k персонализированных рекомендаций (top-k) для некоторого пользователя A. В случае с user-based подходом, для построения рекомендаций находятся так называемые пользователи-соседи (neighbors) пользователя A. Соседи пользователя А — это пользователи, наиболее похожие на него с точки зрения истории просмотров/рейтингов. Количество соседей варьируется в зависимости от реализации и требований к RS, но обычно не превышает 50. Зная предпочтения соседей и историю просмотров пользователя А, RS строит top-k рекомендаций. Такой подход предполагает, что пользователю A понравятся те же объекты, что и пользователям-соседям.

В случае с item-based подходом пользователь A характеризуется объектами objsA, которые он просмотрел или оценил. Для каждого объекта из objsA определяется m объектов-соседей, т.е. находятся m наиболее похожих объектов с точки зрения просмотров/оценок пользователей. При построении RS для фильмов, m принимает значения от 10 до 30. Все объекты-соседи объединяются во множество из которого исключаются объекты, просмотренные или оцененные пользователем A. Из оставшегося множества строится top-k рекомендаций. Таким образом, при item-based подходе в создании рекомендаций участвуют все пользователи, которым понравился тот или иной объект из objsA.

В нашем случае для получения top-k рекомендаций используется простейший вариант алгоритма Deshpande M. и Karypsis G.. Рекомендации строятся на основе рейтингов зарегистрированных пользователей ivi.ru.

Реализация

Описанный ниже код позволяет получать рекомендации по фильмам для некоторого пользователя A по его истории рейтингов. Данные о рейтингах пользователей ivi.ru (за последние 30 дней) и названиях фильмов для удобства были предварительно выкачены в sqlite БД — ivi_rates.db.

RS построена на Python с использованием пакетов: numpy, scipy, scikit-learn. Некоторые участки кода могут показаться «дикими» вследствие оптимизации, для них есть комментарии.

Подготовка матрицы item-user

Item-user матрица является исходной матрицей как для user-based, так и для item-based коллаборативной фильтрации. Строке данной матрицы соответствует объект, в нашем случае фильм. Столбцу соответствует пользователь. В ячейках матрицы расположены рейтинги.

Для уменьшения шума в рекомендациях и увеличения их точности используются только данные о фильмах с количеством просмотров/рейтингов не менее определенного значения (confidence value). В нашем случае в построении item-user матрицы будут участвовать фильмы минимум c 10 рейтингами. Также, для уменьшения размерности пространства пользователей, мы исключим из построения всех пользователей, которые оценили только один фильм.

Матрица item-user будет сильно разрежена, поэтому и хранить её мы будем соответствующим образом.

import sqlite3
conn = sqlite3.connect('ivi_rates.db')
cursor = conn.cursor()

# строим индекс user_id -> col_id, где col_id - идентификатор столбца в матрице
# берем пользователей, оценивших не менее 2 фильмов
users_sql = """
    SELECT user_id
    FROM rates
    WHERE rate IS NOT NULL
    GROUP BY user_id HAVING count(obj_id) >= 2
"""
cursor.execute(users_sql)
user_to_col = {}
for col_id, (user_id,) in enumerate(cursor):
    user_to_col[user_id] = col_id

# строим индекс obj_id -> row_id, где row_id - идентификатор строки в матрице
# берем только фильмы, которые оценили не менее 10 пользователей
objs_sql = """
    SELECT obj_id
    FROM rates
    WHERE rate IS NOT NULL AND user_id IN (
        SELECT user_id
        FROM rates
        WHERE rate IS NOT NULL
        GROUP BY user_id HAVING count(obj_id) >= 2
    )
    GROUP BY obj_id HAVING count(user_id) >= 10 
"""
cursor.execute(objs_sql)
obj_to_row = {}
for row_id, (obj_id,) in enumerate(cursor):
    obj_to_row[obj_id] = row_id
    
print u"Количество пользователей:", len(user_to_col)
print u"Количество объектов:", len(obj_to_row)

Количество пользователей: 353898
Количество объектов: 7808

Индексы нужны для быстрого преобразования идентификаторов пользователей/фильмов в идентификаторы столбцов/строк. Зная количество фильмов и пользователей, можно упростить процесс создания и заполнения матрицы item-user.

from scipy.sparse import lil_matrix

sql = """
    SELECT obj_id, user_id, rate
    FROM rates
    WHERE rate IS NOT NULL
"""
cursor.execute(sql)

matrix = lil_matrix((len(obj_to_row), len(user_to_col)))  # создаем матрицу нужных размеров
# заполняем матрицу
for obj_id, user_id, rate in cursor:
    row_id = obj_to_row.get(obj_id)
    col_id = user_to_col.get(user_id)
    if row_id is not None and col_id is not None:
        matrix[row_id, col_id] = min(rate, 10)
        
percent = float(matrix.nnz) / len(obj_to_row) / len(user_to_col) * 100
print u"Процент заполненности матрицы: %.2f%%" % percent

Процент заполненности матрицы: 0.17%

Подготовка матрицы item-item

Основной матрицей для item-based подхода является матрица item-item. Строкам и столбцам этой матрицы соответствуют объекты. В ячейках хранится значение схожести объектов. Для определения схожести двух объектов используется метрика косинусной меры угла. Список рекомендаций вычисляется путем перемножения матрицы item-item на вектор просмотров/рейтингов пользователя A.

В item-item матрице все значения по диагонали равны 1 (объект на 100% похож на себя). Чтобы исключить диагональ из рекомендаций, ее обычно зануляют.

При стабильном интересе пользователей к объектам, матрица item-item также является стабильной. Под стабильностью интересов подразумевается следующее: если пользователю B нравятся фильмы, понравившиеся пользователю A, то велика вероятность, что пользователю B понравится еще один фильм из списка фильмов, понравившихся пользователю A. Стабильность матрицы означает, что с появлением новых просмотров/рейтингов значения внутри ячеек матрицы будут почти неизменны. Стабильность позволяет не перестраивать матрицу каждый раз при появлении новых рейтингов.

Scipy, numpy, scikit позволяют выполнять матричные операции очень быстро (скорее всего, быстрее, чем любая самописная итерация). При использовании матриц лучше использовать функции из этих пакетов.

from sklearn.preprocessing import normalize
from scipy.sparse import spdiags

# косинусная мера вычисляется как отношение скалярного произведения векторов(числитель) 
# к произведению длины векторов(знаменатель)

# нормализуем исходную матрицу 
# (данное действие соответствует приведению знаменателя в формуле косинусной меры к 1)
normalized_matrix = normalize(matrix.tocsr()).tocsr()
# вычисляем скалярное произведение
cosine_sim_matrix = normalized_matrix.dot(normalized_matrix.T)

# обнуляем диагональ, чтобы исключить ее из рекомендаций
# быстрое обнуление диагонали
diag = spdiags(-cosine_sim_matrix.diagonal(), [0], *cosine_sim_matrix.shape, format='csr')
cosine_sim_matrix = cosine_sim_matrix + diag

percent = float(cosine_sim_matrix.nnz) / cosine_sim_matrix.shape[0] / cosine_sim_matrix.shape[1] * 100
print u"Процент заполненности матрицы: %.2f%%" % percent
print u"Размер в МБ:", cosine_sim_matrix.data.nbytes / 1024 / 1024

Процент заполненности матрицы: 45.54%
Размер в МБ: 211

На самом деле, в каждой строке полученной матрицы item-item хранится список соседей объекта, соответствующего данной строке. Как уже было сказано ранее, для item-based подхода достаточно хранить m наиболее похожих объектов-соседей (top-m). Так как мы работаем с фильмами, то возьмем m равным 30.

from scipy.sparse import vstack
import numpy as np

cosine_sim_matrix = cosine_sim_matrix.tocsr()
m = 30

# построим top-m матрицу в один поток
rows = []
for row_id in np.unique(cosine_sim_matrix.nonzero()[0]):
    row = cosine_sim_matrix[row_id]  # исходная строка матрицы
    if row.nnz > m:
        work_row = row.tolil()
        # заменяем все top-m элементов на 0, результат отнимаем от row
        # при большом количестве столбцов данная операция работает быстрее, 
        # чем простое зануление всех элементов кроме top-m
        work_row[0, row.nonzero()[1][np.argsort(row.data)[-m:]]] = 0
        row = row - work_row.tocsr()
    rows.append(row)
topk_matrix = vstack(rows) 
# нормализуем матрицу-результат
topk_matrix = normalize(topk_matrix)

percent = float(topk_matrix.nnz) / topk_matrix.shape[0] / topk_matrix.shape[1] * 100
print u"Процент заполненности матрицы: %.2f%%" % percent
print u"Размер в МБ:", topk_matrix.data.nbytes / 1024 / 1024

Процент заполненности матрицы: 0.38%
Размер в МБ: 1

Согласно работе Deshpande M. и Karypsis G. рекомендации получаются лучше при нормализации конечной матрицы.

Полученная top-m матрица является сильно разреженой и ее размер составляет всего 1 МБ. Т.е. в нашем случае для построения рекомендаций на основании данных о 353898 пользователях и 7808 объектах достаточно хранить матрицу размером всего 1 МБ.

Получение рекомендаций

Теперь, когда у нас есть матрица item-item, мы можем построить персонализированные рекомендации для пользователя А.

Получение рекомендаций состоит из трех этапов:

1. перемножить матрицу item-item и вектор просмотров/рейтингов пользователя A;
2. в векторе-результате занулить ячейки, соответствующие фильмам, которые пользователь A уже просмотрел или оценил;
3. отсортировать фильмы в порядке убывания значений, оставшихся в ячеках вектора-результата, и получить top-k рекомендованных фильмов.

# индекс для преобразования row_id -> obj_id, где row_id - идентификатор строки в матрице
row_to_obj = {row_id: obj_id for obj_id, row_id in obj_to_row.iteritems()}

# заранее собираем индекс obj_id -> title
title_sql = """
    SELECT obj_id, obj_title
    FROM rates
    GROUP BY obj_id, obj_title
"""
cursor.execute(title_sql)
obj_to_title = {}
for obj_id, title in cursor:
    obj_to_title[obj_id] = title

#подготавливаем вектор рейтингов пользователя:
user_vector = lil_matrix((len(obj_to_row), 1))
user_vector[7780, 0] = 7  # Скорый «Москва-Россия»
user_vector[7755, 0] = 10 # Отель «Гранд Будапешт»
user_vector[7746, 0] = 8  # Мстители
user_vector[7657, 0] = 8  # Охотники за сокровищами
user_vector[6683, 0] = 7  # 300 спартанцев: Расцвет империи
user_vector[7656, 0] = 9  # Невероятная жизнь Уолтера Митти
user_vector[7356, 0] = 9  # Одинокий рейнджер
user_vector[7296, 0] = 8  # Елки 3
user_vector[6839, 0] = 7  # Легенда №17
user_vector[4190, 0] = 7  # 21 и больше
user_vector[7507, 0] = 9  # Покорители волн
user_vector[6938, 0] = 9  # Кон-Тики
user_vector[4230, 0] = 10 # Карты, деньги, два ствола
user_vector[3127, 0] = 8  # 13
user_vector = user_vector.tocsr()

# 1. перемножить матрицу item-item и вектор рейтингов пользователя A
x = topk_matrix.dot(user_vector).tolil()
# 2. занулить ячейки, соответствующие фильмам, которые пользователь A уже оценил
for i, j in zip(*user_vector.nonzero()):
    x[i, j] = 0
    
# превращаем столбец результата в вектор
x = x.T.tocsr()    
    
# 3. отсортировать фильмы в порядке убывания значений и получить top-k рекомендаций (quorum = 10)
quorum = 10
data_ids = np.argsort(x.data)[-quorum:][::-1]

result = []
for arg_id in data_ids:
    row_id, p = x.indices[arg_id], x.data[arg_id] 
    result.append({"obj_id": row_to_obj[row_id], "weight": p})

result

Ура! Мы построили рекомендации для пользователя. Однако в таком виде они мало о чем говорят. Хорошо, когда RS объясняет пользователю, почему ему рекомендуют тот или иной объект. Существует множество способов объяснения рекомендаций, полученных с использованием коллаборативной фильтрации (подробнее можно почитать у J.Herlocker, J.Konstan, J.Riedl). Здесь приведен один из способов объяснения рекомендаций, который легко реализуется с учетом имеющихся матриц и данных.

Каждый рекомендованный фильм будет объясняться так: Мы рекомендуем Вам "%(title)s", так как он нравится пользователям, просмотревшим "%(impact)s". Вы оценили "%(impact)s" на %(impact_value)s.

# фильмы, которые мы рекомендуем, и их связь с фильмами, которые оценил пользователь
result = []
for arg_id in data_ids:
    row_id, p = x.indices[arg_id], x.data[arg_id]
    obj_id = row_to_obj[row_id]
    
    # определяем, как повлиял на рекомендуемый фильм каждый из оцененных пользователем фильмов.
    # topk_matrix[row_id] - вектор соседей рекомендованного фильма obj_id
    # .multiply(user_vector.T) - зануляет все фильмы, которые пользователь не оценивал
    # impact_vector - вес просмотренных пользователем фильмов при подсчете метрики рекомендации obj_id
    impact_vector = topk_matrix[row_id].multiply(user_vector.T)
    
    # наиболее значимый фильм - ячейка с наибольшим значением в impact_vector
    impacted_arg_id = np.argsort(impact_vector.data)[-1]
    impacted_row_id = impact_vector.indices[impacted_arg_id]
    impact_value = user_vector[impacted_row_id, 0]
    impacted_obj_id = row_to_obj[impacted_row_id]  # наиболее значимый фильм
    
    rec_item = {
        "title": obj_to_title[obj_id],
        "weight": p,
        "impact": obj_to_title[impacted_obj_id],
        "impact_value": impact_value
    }
    result.append(rec_item)
    print u'''Мы рекомендуем Вам "%(title)s", так как он нравится пользователям, просмотревшим "%(impact)s". Вы оценили "%(impact)s" на %(impact_value)s.''' % rec_item

В приведенном примере построения RS не используется нормализация рейтингов, так как тема нормализации данных достойна отдельной статьи.

Описанный способ построения персонализированной RS позволяет показать, что item-based подход является мощным инструментом для построения RS. В то же время, стоит понимать, что современные RS используют несколько персонализированных и неперсонализированных методов для построения рекомендаций. Комбинированное использование различных методов позволяет создавать хорошие рекомендации независимо от количества данных о пользователе или объекте.