Collaborative Filtering — подход, основанный на отношениях между пользователями (users) и товаром (items), при этом нет никакой информации о пользователях или товарах.

Взаимодействие между пользователем и товаром разделят на две категории:

• Явное взаимодействие. Например, рейтинг, который пользователь ставит товару.

• Неявное взаимодействие. Например, клик, просмотр или покупка товара не очевидны с точки зрения рейтинга.

User-item matrix — это таблица, в которой каждая строка представляет собой пользователя, каждый столбец — товар, а каждая ячейка содержит информацию о взаимодействии между пользователем и товаром. Например, в ячейке может быть указано количество раз, которое пользователь купил товар, или оценка, которую пользователь поставил товару. User-item matrix используется в рекомендательных системах для определения предпочтений пользователей и предложения им наиболее подходящих товаров. Очевидно, что user-item matrix — очень большая и разряженная матрица.

Для таких задач применяют матричную факторизацию (представление user-item matrix в виде произведения двух или более матриц более простого вида).

Часто матричная факторизация применяется для уменьшения размерности, где мы пытаемся уменьшить количество элементов, сохраняя при этом соответствующую информацию.

Так дело обстоит с основным компонентным анализом (PCA) и разложение по сингулярному значению (SVD).

где — user-item matrix, — диагональная матрица с неотрицательными сингулярными числами, и — ортогональные матрицы и .

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

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

Оставив -первых (главных) компонент () в SVD разложении, получим наиболее точное приближение к по норме Фробениуса.

За «Скрытым текстом» пример использования SVD и PCA.

Hidden text

Наглядно как работает SVD и PCA.

import numpy as np from matplotlib import image from matplotlib import pyplot as plt import cv2

img = image.imread("photo.jpg") plt.imshow(img) plt.show()

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

gray_img = cv2.cvtColor(img, cv2.COLOR_RGB2GRAY) plt.imshow(gray_img, cmap='gray') plt.show()

gray_img.shape  (558, 563)

Применим SVD разложение

U, lmbd, V = np.linalg.svd(gray_img) U.shape, lmbd.shape, V.shape  ((558, 558), (558,), (563, 563))

S = np.zeros((U.shape[1], V.shape[0]))  S[ : U.shape[1], : U.shape[1]] = np.diag(lmbd) S.shape  (558, 563)

Вернем как было, убедимся что ничего не изменилось

plt.imshow(U @ S @ V, cmap='gray') plt.show()

Попробуем оставить первые 100 компонент и посмотрим насколько изменится качество изображения.

d = 100 U_crop = U[:, :d] S_crop = S[:d, :d] V_crop = V[:d, :]  plt.imshow(U_crop @ S_crop @ V_crop, cmap='gray') plt.show()

Качество картинки почти не изменилось, зато сколько сэкономлено памяти!

Попробуем оставить первые 50 компонент.

d = 50 U_crop = U[:, :d] S_crop = S[:d, :d] V_crop = V[:d, :]  plt.imshow(U_crop @ S_crop @ V_crop, cmap='gray') plt.show()

Оставим первые 10 компонент.

d = 10 U_crop = U[:, :d] S_crop = S[:d, :d] V_crop = V[:d, :]  plt.imshow(U_crop @ S_crop @ V_crop, cmap='gray') plt.show()

Сингулярные числа в матрице S расположены по убыванию: чем ближе к началу, тем компоненты важнее и сильнее влияют на качество изображения.

Уберем первые 5 компонент.

k = 5U_crop = U[:, k:] S_crop = S[k:, k:] V_crop = V[k:, :]  plt.imshow(U_crop @ S_crop @ V_crop, cmap='gray') plt.show()

Качество картинки значительно хуже.

Представим нашу user-item matrix как произведение следующих матриц:

Тогда ‑aя строка  — это представление ‑го пользователя, а ‑ый столбец  — представленте ‑го товара. Их отношение (рейтинг) выражается с помощью скалярного произведения:

Матрицы и найдем с помощью градиентного спуска.

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

Посчитав градиенты по и по , получим формулы обновления весов:

k пробегает от 1 до d, где d — число главных компонент.

Продемонстрируем работу алгоритма. Пусть нам заданы пользователи и их оценки к просмотренным фильмам. Задача — спрогнозировать незаполненные ячейки user-item matrix.

import numpy as np import pandas as pd

Зададим пользователей и фильмы:

k = 10 # максимальная оценка  movies = ['Фантазия', 'ВАЛЛ-И', 'Пиноккио', 'Бемби' , 'Шрэк', 'Дамбо', 'Спасатели', 'Геркулес', 'Кунг-фу Панда'] m_movies = len(movies)  users = ['Андрей', 'Аня', 'Алиса', 'Ваня', 'Леша', 'Оксана', 'Саша', 'Паша', 'Сеня', 'Гриша']         n_users = len(users)

Оценки раскидаем случайным образом. С учетом чтобы пара user-movie не повторялась

RANDOMSEED = 42 np.random.seed(42)  N = np.random.randint(50, 60) # сколько оценок будет поставлено  ind_users, ind_movies, rating = [], [], [] user_movie = [] # чтобы пара user-movie не повторялись for _ in range(N):     user = np.random.randint(0, n_users)     movie = np.random.randint(0, m_movies)     if not [user, movie] in user_movie:         ind_users.append(user)         ind_movies.append(movie)         rating.append(np.random.randint(1, k)) # случайная оценка пользователя фильму         user_movie.append([user, movie])          N = len(user_movie)  def get_user_item_matrix(n_users, m_movies, ind_users, ind_movies, rating):     R = [[0] * m_movies for _ in range(n_users)]     N = len(ind_users)     for i in range(N):         R[ind_users[i]][ind_movies[i]] = rating[i]     R = np.array(R)     return R  R = get_user_item_matrix(n_users, m_movies, ind_users, ind_movies, rating)  pd.DataFrame(R, users, movies) 

Ошибку будем считать как:

def MSE(R, U, V):     mse = 0     for ind in range(N):         i = ind_users[ind]         j = ind_movies[ind]         mse += ( R[i][j] - np.dot(U[i,:], V[:,j]) )**2 / N     return mse

Использовать будем стохастический градиентный спуск c фиксированным шагом step. Сделаем n_iters итераций.

def SVD(ind_users, ind_movies, R, d, step, n_iters):          # инициализация матриц разложения     P = np.random.rand(R.shape[0], d)     Q = np.random.rand(d, R.shape[1])      start_mse = MSE(R, P, Q)          # Стохастический градиентный спуск     for n in range(n_iters):         ind = np.random.randint(0, N)         i = ind_users[ind]         j = ind_movies[ind]                  for k in range(0, d):             P[i, k] = P[i, k] + step * (R[i][j] - P[i, :] @ Q[:, j]) * Q[k, j]              Q[k, j] = Q[k, j] + step * (R[i][j] - P[i, :] @ Q[:, j]) * P[i, k]           mse = MSE(R, P, Q)     return P, Q, start_mse, mse  P, Q, start_mse, mse = SVD(ind_users, ind_movies, R, 3, 0.1, 3000) 

start_mse, mse  (22.327189007469947, 0.9592817343783187)

Спрогнозируем user-item matrix

R_pred = np.zeros((R.shape[0], R.shape[1]))  for i in range(n_users):     for j in range(m_movies):         R_pred[i][j] = round(P[i,:] @ Q[:,j], 2)  pd.DataFrame(R_pred, users, movies)

# Вывод еще раз для сравнения pd.DataFrame(R, users, movies)