Item-based коллаборативная фильтрация своими руками
Одной из наиболее популярных техник для построения персонализированных рекомендательных систем (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, мы можем построить персонализированные рекомендации для пользователя А.Получение рекомендаций состоит из трех этапов:
перемножить матрицу item-item и вектор просмотров/рейтингов пользователя A; в векторе-результате занулить ячейки, соответствующие фильмам, которые пользователь A уже просмотрел или оценил; отсортировать фильмы в порядке убывания значений, оставшихся в ячеках вектора-результата, и получить 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 Результат [{'obj_id': 1156180, 'weight': 8.4493290509843408},{'obj_id': 978100, 'weight': 6.4337821664936943},{'obj_id': 1143770, 'weight': 5.5038366682680451},{'obj_id': 978120, 'weight': 5.4203284682159421},{'obj_id': 985220, 'weight': 5.2386991677359047},{'obj_id': 1033040, 'weight': 5.0466735584390117},{'obj_id': 1033290, 'weight': 4.8688497271055011},{'obj_id': 1046560, 'weight': 4.6880514059004224},{'obj_id': 984040, 'weight': 4.6199406111214927},{'obj_id': 960770, 'weight': 4.5788899365020477}]
Ура! Мы построили рекомендации для пользователя. Однако в таком виде они мало о чем говорят. Хорошо, когда 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 Результат Мы рекомендуем Вам «Кухня в Париже», так как он нравится пользователям, просмотревшим «Скорый «Москва-Россия».Вы оценили «Скорый «Москва-Россия» на 7.0.**************************Мы рекомендуем Вам «Невозможное», так как он нравится пользователям, просмотревшим «Кон-Тики».Вы оценили «Кон-Тики» на 9.0.**************************Мы рекомендуем Вам «Приключения мистера Пибоди и Шермана», так как он нравится пользователям, просмотревшим «Скорый «Москва-Россия».Вы оценили «Скорый «Москва-Россия» на 7.0.**************************Мы рекомендуем Вам «Паркер», так как он нравится пользователям, просмотревшим «Карты, деньги, два ствола».Вы оценили «Карты, деньги, два ствола» на 10.0.**************************Мы рекомендуем Вам «Бойфренд из будущего», так как он нравится пользователям, просмотревшим «Одинокий рейнджер».Вы оценили «Одинокий рейнджер» на 9.0.**************************Мы рекомендуем Вам «Волк с Уолл-стрит», так как он нравится пользователям, просмотревшим «Невероятная жизнь Уолтера Митти».Вы оценили «Невероятная жизнь Уолтера Митти» на 9.0.**************************Мы рекомендуем Вам «Горько!», так как он нравится пользователям, просмотревшим «Елки 3».Вы оценили «Елки 3» на 8.0.**************************Мы рекомендуем Вам «Стив Джобс. Потерянное интервью», так как он нравится пользователям, просмотревшим «Кон-Тики».Вы оценили «Кон-Тики» на 9.0.**************************Мы рекомендуем Вам «Техасская резня бензопилой 3D», так как он нравится пользователям, просмотревшим «Отель «Гранд Будапешт».Вы оценили «Отель «Гранд Будапешт» на 10.0.**************************Мы рекомендуем Вам «Хоббит: Пустошь Смауга», так как он нравится пользователям, просмотревшим «Невероятная жизнь Уолтера Митти».Вы оценили «Невероятная жизнь Уолтера Митти» на 9.0.**************************
В приведенном примере построения RS не используется нормализация рейтингов, так как тема нормализации данных достойна отдельной статьи.Описанный способ построения персонализированной RS позволяет показать, что item-based подход является мощным инструментом для построения RS. В то же время, стоит понимать, что современные RS используют несколько персонализированных и неперсонализированных методов для построения рекомендаций. Комбинированное использование различных методов позволяет создавать хорошие рекомендации независимо от количества данных о пользователе или объекте.
