Неперсоналізовані рекомендації: метод асоціацій

Персональні рекомендації дозволяють познайомити користувача з об'єктами, про які він, можливо, ніколи не знав (і не дізнався б), але які можуть йому сподобатися, з урахуванням його інтересів, уподобань і поведінкових властивостей. Однак, часто користувач шукає новий об'єкт, а, наприклад, об'єкт A схожий на об'єкт B («Форсаж 2» схожий на «Форсаж»), або об'єкт A, який набувається споживається з об'єктом B (сир з вином, пиво з дитячим харчуванням, гречка з тушонкою і т. д.). Побудувати такі рекомендації дозволяють неперсоналізовані рекомендаційні системи (НРС).


Рекомендувати схожі/супутні об'єкти можна, орієнтуючись на знання про об'єкти (властивості, теги, параметри) або на знання про діях, пов'язаних з об'єктами (купівлі, перегляди, кліки). Перевагою першого способу є те, що він дозволяє досить точно визначити схожі за властивостями об'єкти («Форсаж 2» та «Форсаж» — схожі актори, схожий жанр, схожі теги, ...). Однак даний спосіб не зможе порекомендувати супутні об'єкти: сир і вино. Ще одним недоліком цього способу є той факт, що для розмітки всіх об'єктів, доступних на сервісі, потрібно не мало зусиль.

У той же час майже кожен сервіс логирует інформацію про те, який користувач переглянув/купив/клікнув який об'єкт. Цієї інформації достатньо для побудови НРС, яка дозволить рекомендувати як схожі, так і супутні об'єкти.

Під катом описаний метод асоціацій, що дозволяє побудувати неперсоналізовані рекомендації, ґрунтуючись лише на даних про дії над об'єктами. Там же код на Python, що дозволяє застосувати метод для великого обсягу даних.

Побудова неперсоналізованих рекомендацій

Для початку розглянемо базовий алгоритм побудови неперсоналізованих рекомендацій. Припустимо, що у нас є об'єкти — фільми і користувачі. Користувачі переглядають фільми. Нашими вихідними даними є розріджена матриця D (фільми x користувачі). Якщо користувач u переглянув фільм f, то у відповідній клітинці матриці D коштує 1.

Для того, щоб знайти фільми, схожі на заданий фільм f необхідно знати схожість фільму f з усіма іншими фільмами. Дані про схожість зберігаються в матриці S (фільми x фільми).

Базовий алгоритм побудови неперсоналізованих рекомендацій виглядає наступним чином:

  1. для заданого фільму f знайти відповідну йому рядок в матриці R S;
  2. вибрати з рядка R безліч схожих на f фільмів — FR;
  3. FR і є непресонализированные рекомендації (схожі/супутні).

Метод схожості

З наведеного видно, що рекомендації і їхня якість залежать тільки від способу побудови матриці S, а якщо бути точніше — від способу визначення схожості двох фільмів.

Як визначити схожість фільмів x і y, якщо їх подивилося безліч користувачів X і Y відповідно? Найбільш просте рішення — Коефіцієнт Жаккара, який обчислює схожість двох об'єктів (x і y):



Тут чисельник — кількість користувачів, які переглянули фільм x, так і фільм y. Знаменник — кількість користувачів, які переглянули фільм x або фільм y.

Обчислене значення є симетричним: x схожий на y також, як y схожий на x. Якщо ж ми хочемо зробити коефіцієнт асиметричним, то можна поміняти на наступну формулу:



На перший погляд даний метод є ідеальним: він збільшує значення схожості фільмів, які дивляться разом, і нормалізує метрику щодо кількості користувачів, які переглянули фільм.

«Проблема Гаррі Поттера» чи «бананова пастка»

Розглянемо зазначену вище формулу для випадку, коли об'єкт y дуже популярний (наприклад, фільм про Гаррі Поттера). Так як фільм дуже популярний і його дивилося багато людей, то sim(x, y) буде прагнути до 1 майже для всіх фільмів x. Це означає, що фільм y буде схожий на всі фільми, а це в більшості випадків погано. Навряд чи «Гаррі Поттер» буде схожий на фільм «Зелений слоник».

«Проблему Гаррі Поттера» також називають «бананової пасткою»(banana trap). Припустимо, що деякий магазин намагається збільшити прибуток шляхом рекомендації покупцеві товарів, які часто беруть разом з тим, що покупець збирається придбати. Одним з найбільш купованих товарів в продуктовому магазині є банани. Використовуючи формулу вище, система буде рекомендувати всім покупцям придбати банани. Банани будуть купуватися — все добре. Але це погані рекомендації, так як банани купувалися б і без рекомендацій. Рекомендуючи банани, ми зменшуємо прибуток як мінімум на один вдало рекомендований товар, відмінний від бананів.

Метод асоціацій

Вочевидь, що формулу треба модифікувати таким чином, щоб об'єкт x робив об'єкт y більш привабливим. Тобто потрібно враховувати не тільки те, що об'єкти x і y беруть разом, але і те, що об'єкт x не беруть без y.

Модифікуємо формулу схожості наступним чином:



Якщо y — дуже популярний об'єкт, то знаменник у формулі буде великим. Тоді значення схожості буде менше, а рекомендації будуть більш релевантними. Даний метод називається методом асоціацій.

Порівняння методів

Для порівняння методу асоціацій і коефіцієнта Жаккара розглянемо пошук схожих фільмів з використанням цих двох методів по наступним вихідним даним.
фільми\користувачі B C D E
1. Гаррі Поттер і філософський камінь 1 1 1 1 1
2. Хоббіт: Несподівана подорож 1 1 1
3. Хоббіт: Пустка Смауга 1 1 1
4. Хроніки Нарнії: Принц Каспіан 1
5. Серце дракона 1
Матриця подібності, побудована з допомогою асиметричного коефіцієнта Жаккара, виглядає наступним чином (діагональ зануляем, щоб не рекомендувати вихідний фільм):
фільми\фільми 1 2 3 4 5
1 0 0,6 0,6 0,2 0,2
2 1 0 0,667 0 0,333
3 1 0,667 0 0 0
4 1 0 0 0 0
5 1 1 0 0 0
Матриця подібності для методу асоціацій буде виглядати наступним чином (крім діагоналі зануляем нескінченності — випадки, коли ).
фільми\фільми 1 2 3 4 5
1 0 0 0 0 0
2 1,5 0 2 0 0
3 1,5 2 0 0 0
4 0,25 0 0 0 0
5 0,25 0,5 0 0 0
Як видно з матриці схожості, метод асоціацій дозволяє врахувати надпопулярність фільму «Гаррі Поттер і філософський камінь». При побудові рекомендацій методом асоціацій для фільму «Хоббіт: Несподівана подорож» вага «Гаррі Поттера» (1,5) буде менше, ніж вага більш релевантного фільму «Хоббіт: Пустка Смауга» (2).

Реалізація

Нижче приведена функція для побудови матриці схожості на базі методу асоціацій. Функція написана на Python з використанням scipy і scikit-learn. Дана реалізація дозволяє швидко і без особливих витрат обчислити матрицю схожості для великого обсягу вихідних даних.

Так як у межах одного рядка матриці значення |X||!X| не змінюються, а схожі об'єкти будуть знаходитися в межах одного рядка, то |X||!X| були опущені при обчисленні метрики асоціації. Кінцева метрики формула виглядає так:



def get_item_item_association_matrix(sp_matrix):
"""Простий спосіб побудови матриці асоціацій

:param sp_matrix: матриця з вихідними даними про переглядах (фільми x користувачі)
:return: матриця схожості фільмів (фільми x фільми)
"""
watched_x_and_y = sp_matrix.dot(sp_matrix.T).tocsr()
watched_x = csr_matrix(sp_matrix.sum(axis=1))
magic = binarize(watched_x_and_y).multiply(watched_x.T)
watched_not_x_and_y = magic - watched_x_and_y
rows, cols = watched_not_x_and_y.nonzero()
data_in_same_pos = watched_x_and_y[rows, cols].A.reshape(-1)
return csr_matrix((data_in_same_pos / watched_not_x_and_y.data, (rows, cols)), watched_x_and_y.shape)

Висновок

Метод асоціацій є всього лише одним із способів побудови неперсоналізованих рекомендацій. Як і для будь-якого іншого методу, перед його застосуванням слід вирішити ряд питань:

— визначити мінімальну кількість даних, за якого можна застосовувати метод;
— визначити порогове значення метрики асоціації;
— визначити, що робити, якщо у рекомендованих об'єктів значення метрики асоціації менше порогового;
— і т. д.

З перерахованого випливає, що метод асоціацій може бути застосований не для усіх об'єктів. Тому його варто комбінувати з одним або більше методів побудови неперсоналізованих рекомендацій. Такий підхід дозволить створювати гарні рекомендації незалежно від кількості даних про користувача або об'єкті.

P. S. Вдалих рекомендацій!

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.