Не так давно я рассказывал о том, как я проектировал алгоритм под рекомендательную систему. По большому счету это даже на алгоритм, а не стандартный подход использования cosine similarity. В этой статье я хочу рассказать об ограничениях этого подхода, как с ними бороться и о своем курсовом проекте: проектирование рекомендательных систем в реальном времени с помощью графовой базы Neo4j.

Изначально я делал ставку на алгоритмы, потому что проект предназначался для стартапа. А как вы понимаете, у стартапа не так много денег, чтобы нанимать дорогих ML инженеров и брать в аренду дорогостоящую инфраструктуру.

Моя цель - рассказать о том, как можно спроектировать рекомендательную систему в буквальном смысле ”на коленке”, используя два подхода: content-based и collaborative-filtering.

---

Для чего нам нужны рекомендательные системы?

Рекомендательные системы широко используются в электронной коммерции, социальных сетях и всевозможных маркетплейсах.

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

Все это делают алгоритмы предпочтения, я хотел бы рассказать об одном из них и способе его использования.

Какими бывают системы рекомендации?

Я буду использовать терминологию рекомендательных систем из англоязычных источников. 

Content-based Filtering - рекомендации товаров или контента на подобие того, что пользователь уже просматривал, высоко оценивал или приобретал ранее.

Collaborative Filtering - система, которая использует предпочтения, рейтинги и действия других пользователей в сети, чтобы найти товары, которые можно порекомендовать.

Я расскажу об этих двух типах и о том, как это можно реализовать с помощью графовой базы Neo4j. Эти оба метода можно также комбинировать.

Структура данных

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

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

У нас есть три типа объектов:

• User;

• Movie;

• Genre.

Сценарии взаимодействия эти типов:

• Пользователь может посмотреть один или более фильмов;

• У фильма может быть один или более жанров.

Эти объекты могут быть связаны между собой следующими связями:

• HAS_WATCHED - связь между пользователем и фильмом как маркер того, что фильм был просмотрен;

• IS_ASSOCIATED_WITH - связь между пользователем и жанром, которая содержит еще и признак соответствия как свойство. Что означает признак соответствия? Он означает насколько тип жанра попадает в ожидание телезрителя. Например, если после просмотра фильма у всех телезрителей спросили: “Комедия ли это?” - и только 80% сказали да, то в качестве признака можно было бы взять 0.8 , так как оно средневзвешенное. В моих примерах будут указаны все признаки соответствия в связях как 1.0

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

Для того, чтобы повторить все мои действия в этой статье, понадобиться подготовленная инсталляция Neo4j под docker-compose с установленном плагином, о котором я буду говорить чуть ниже.

https://github.com/dmitrydivin/recommendation_system/tree/bea9e02b7b0335ccdc718f0a1015124f07091775/deployment

После запуска подготовленной заранее инсталляции нужно будет еще вставить все данные.

https://github.com/dmitrydivin/recommendation_system/tree/bea9e02b7b0335ccdc718f0a1015124f07091775/examples/movies

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

Как найти похожий контент?

Забегая вперед, я хотел бы остановиться на одном алгоритме. Мне нравиться экспериментировать и искать альтернативные способы решения задач. Сегодня я хочу рассказать об одном из них - это cosine similarity и то, как я его использовал.

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

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

По сути моя задача сводилось к нахождении ближайших соседей.

Как правило, этот алгоритм используют следующим образом: берется весь набор данных, под него создается матрица комбинации всех его признаков и делается сравнение всего со всеми.

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

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

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

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

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

CREATE (:Genre {id: 0, name: 'Adventure'})
CREATE (:Genre {id: 1, name: 'Animation'})
CREATE (:Genre {id: 2, name: 'Children'})
CREATE (:Genre {id: 3, name: 'Comedy'})
CREATE (:Genre {id: 4, name: 'Fantasy'})
CREATE (:Genre {id: 5, name: 'Drama'})
CREATE (:Genre {id: 6, name: 'Action'})

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

MATCH (g:Genre)
WITH COLLECT(g.id) AS all_genres
MATCH (g:Genre) WHERE rand() > 0.7
WITH all_genres, apoc.coll.shuffle(COLLECT(g)) AS genres
UNWIND genres AS genre
WITH all_genres, COLLECT(genre.id) AS l_classifiers,
    COLLECT(1.0) AS l_features, COLLECT(genre.name) AS l_title
UNWIND range(0, 10) AS it
MATCH (g:Genre) WHERE rand() > 0.8
WITH it, all_genres, l_classifiers, l_features, l_title,
    COLLECT(g.id) AS r_classifiers,
    COLLECT(1.0) AS r_features, COLLECT(g.name) AS r_title
WITH l_title, r_title,
 alg.classifiers.similar(l_classifiers, l_features, r_classifiers, r_features)
  AS score,
[c IN apoc.coll.frequencies(all_genres + l_classifiers) | toFloat(c.count - 1)]
  AS l_c,
[c IN apoc.coll.frequencies(all_genres + r_classifiers) | toFloat(c.count - 1)]
  AS r_c
WITH l_title, r_title, score, gds.similarity.cosine(l_c, r_c) AS score_x
return l_title, r_title, score, score_x
 ORDER BY score DESC

Для тех, кто не совсем понимает язык Cypher, приведу некоторые пояснения по поводу сравнения всех существующих жанров: берем все жанры и для первого массива и выбираем значение 1.0 - когда жанр присутствует и 0.0 - когда жанр отсутствует. Для второй части массива делаем тоже самое.

Таким образом количество параметров переданных в gds.similarity.cosine будет зависеть от количества жанров, которые у нас есть в базе.

Можно только представить каким будет "latency" одного такого сравнения, если у нас в системе может присутствовать несколько десятков тысяч классификаторов, а сравнить нам нужно только сотню для одной записи.

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

Из результата видно, что оба метода могут отличаться друг от друга, но их порядок будет одним и тем же, что приводит к одному и тому же результату сравнения.

Данное предположение я реализовал в виде функции на языке Java и упаковал в плагин для Neo4j.

Эта функция принимает две группы классификаторов и их признаков, которые можно сравнить между собой.
Признаки при этом должны быть положительными числами и иметь значения выше 0.
Как результат получаем значение подобия от 0 до 1, где:

• 0 - полный промах;

• 1 - полное попадание;

• Значение между ними - частичное попадание.

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

Перед тем как делать сравнения, я хотел бы прояснить некоторые детали: мы будем сравнивать жанры, которыми интересовался пользователь, когда смотрел фильмы.

Всю историю просмотров назовем пользовательским опытом, а если сложить все жанры просмотренных фильмов, то получим распределение интересов к жанрам.
В дальнейшем этот пользовательский опыт можно эволюционировать, например через "Модель урны Polya", чтобы развивать интересы пользователя. Но я не буду касаться данной темы в этой статье.

Это распределение и будем сравнивать со списком жанров: тот список жанров, который больше подходит под наше распределение, и будет выше в отдаче.

С помощью запроса я буду выводить список сравнения:

• Случайным образом получаем список жанров и накопленный опыт. Признаки опыта будут указаны в круглых скобках;

• Случайным образом получим 10 списков жанров, с которыми и будем делать сравнения. У этого списка не будет признаков соответствия, так как у наших фильмов все жанры считаются одинаковыми по весу, а значит возьмем для этого любое число. Например 1.0.

MATCH (g:Genre) WHERE rand() > 0.7
WITH apoc.coll.shuffle(COLLECT(g)) AS genres
UNWIND genres AS genre
WITH genre, toFloat(1+rand()*100) AS rnd
WITH COLLECT(genre.id) AS ux_classifiers, COLLECT(rnd) AS ux_features,
  COLLECT(genre.name + '(' + toInteger(rnd) + ')') AS ux_title
UNWIND range(0, 10) AS it
MATCH (g:Genre) WHERE rand() > 0.8
WITH it, ux_classifiers, ux_features, ux_title,
  COLLECT(g.id) AS classifiers, COLLECT(1.0) AS features,
  COLLECT(g.name) AS title
RETURN ux_title, title,
  alg.classifiers.similar(ux_classifiers, ux_features, classifiers, features)
  AS score
 ORDER BY score DESC

Результат сравнения выводим в таблицу, где в первой колонке будет показываться пользовательский опыт, во второй - жанры, с которыми будем сравнивать, и в третьей - результат сравнения:

Как видно из таблицы сравнения, жанр “Animation” выше в отдаче чем жанр “Fantasy”, и это потому, что к первому интерес выше: 86 против 51.

Как это работает?

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

Чтобы прояснить как работает этот подход по капотом, я приведу следующий пример:

Представьте, что у вас в одной корзине 20 апельсин, а в другой только 10. С точки зрения соотношения типов объектов оно будет равно 1:1, что эквивалентно 20/20=10/10 . Для любого количества объектов одного и того же типа алгоритм всегда будет возвращать 1.0 , потому что косинус угла векторов [20] ~ [10] = 1.0

Но что будет происходить, когда в одной корзине 20 апельсин и 10 яблок, а в другой только 10 апельсин?

Очевидно то, что равенство не соблюдается. Но как это посчитать?

Мы можем только представить, что во второй корзине 0 яблок и посчитать косинус угла по той же самой формуле. 

[20, 10] ~ [10, 0] = 0.894427

Это же утверждение нужно применить и к левой стороне: если во второй корзине есть тип фрукта, который отсутствует в первой, то в первую для этого типа выбираем 0.

Content-based Filtering

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

Для этого нужно взять все просмотренные фильмы, а жанры фильмов сгруппировать и посчитать их количество. Это количество и будет нашими признаками.

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

Затем делаем выборку всех фильмов, исключая просмотренные.

Для каждого фильма берем все его жанры и признаки соответствия из связей.

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

Затем отсортируем результат сравнения от большего к меньшему, чтобы получить рекомендацию. 

Сделаем это с помощью следующего запроса от имени пользователя, который больше интересуется жанром “Comedy”:

MATCH (u:User {name: 'Carlos M. Pratt'})-[:HAS_WATCHED]
  ->(m:Movie)-[r:IS_ASSOCIATED_WITH]->(g:Genre)
WITH u, g.id AS classifier, sum(r.accuracy) AS features
WITH u, collect(classifier) AS ux_classifiers, collect(features)
  AS ux_features
MATCH (m:Movie)-[r:IS_ASSOCIATED_WITH]->(g:Genre)
 WHERE NOT (u)-[:HAS_WATCHED]->(m)
WITH m.title AS title, ux_classifiers, ux_features, collect(g.id)
  AS classifiers, collect(r.accuracy) AS features,
    collect(g.name) AS genres
WITH title, genres, alg.classifiers.similar(
  ux_classifiers, ux_features, classifiers, features) AS score
 WHERE score > 0.4
RETURN title, genres, score
 ORDER BY score DESC
 LIMIT 7

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

Так как опыт пользователя может иметь все жанры, а количество жанров в фильмах ограничено, то попадание в рекомендацию с максимальным коэффициентом может быть редкостью.

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

Для наглядности на графике видно распределение пользовательского опыта к классификаторам. По оси Y выводится сумма пользовательского опыта, а по оси X - интересы в виде ключевых слов.

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

Для того, чтобы решить эту проблему, мы можем сделать выборку только по самым часто используемым жанром, а остальные отбросить.

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

Следующий запрос показывает то, как оставить только два высокочастотного жанра:

MATCH (u:User {name: 'Carlos M. Pratt'})-[:HAS_WATCHED]
  ->(m:Movie)-[r:IS_ASSOCIATED_WITH]->(g:Genre)
WITH u, g.id AS classifier, sum(r.accuracy) AS features
WITH u, [features, classifier] AS pair ORDER BY pair[0] DESC
WITH u, COLLECT(pair[0])[0..2] AS ux_features,
  COLLECT(pair[1])[0..2] AS ux_classifiers
MATCH (m:Movie)-[r:IS_ASSOCIATED_WITH]->(g:Genre)
 WHERE NOT (u)-[:HAS_WATCHED]->(m)
WITH m.title AS title, ux_classifiers,
  ux_features, collect(g.id) AS classifiers, collect(r.accuracy) AS features,
    collect(g.name) AS genres
WITH title, genres, alg.classifiers.similar(
  ux_classifiers, ux_features, classifiers, features) AS score
 WHERE score > 0.4
RETURN title, genres, score
 ORDER BY score DESC
 LIMIT 7

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

К теме Content-based Filtering, можно отнести также рекомендации относительно контента.

Например, когда открываем фильм на Netflix, то тут же предлагается посмотреть похожие фильмы в разделе “More Like This”

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

Это можно сделать с помощью следующего запроса:

MATCH (m:Movie {title: 'Jumanji (1995)'})-[r:IS_ASSOCIATED_WITH]->(g:Genre)
WITH m, g.id AS classifier, SUM(r.accuracy) AS total_feature
WITH m, COLLECT(classifier) AS m_classifiers,
  COLLECT(total_feature) AS m_features
MATCH (similar:Movie)-[r:IS_ASSOCIATED_WITH]->(g:Genre)
 WHERE m <> similar
WITH similar, m_classifiers, m_features, COLLECT(g.id) AS classifiers,
  COLLECT(r.accuracy) AS features
WITH similar.title AS title, alg.classifiers.similar(
  m_classifiers, m_features, classifiers, features) AS score
 WHERE score > 0.4
RETURN title, score
 ORDER BY score DESC

В результате получим наиболее похожие по жанрам фильмы относительно фильма ‘Jumanji (1995)’:

Collaborative-Filtering

Теперь попробуем раскрыть тему рекомендаций через коллективное взаимодействие.

Основная мысль - это найти похожих пользователей и предлагать фильмы, которые этот пользователь уже просмотрел. Так как на протяжении пользовательской истории его предпочтения могли меняться, то скорее всего нам нужно будет еще отфильтровать по своим предпочтениям.

Теперь давайте найдем похожих пользователей с помощью следующего запроса:

MATCH (u:User {name: 'Lonnie R. Wright'})-[:HAS_WATCHED]
  ->(m:Movie)-[r:IS_ASSOCIATED_WITH]->(g:Genre)
WITH u, g.id AS classifier, SUM(r.accuracy) AS total_accuracy
WITH u, COLLECT(classifier) AS ux_classifiers,
  COLLECT(total_accuracy) AS ux_features
MATCH (similar:User)-[:HAS_WATCHED]->(m:Movie)-[r:IS_ASSOCIATED_WITH]
  ->(g:Genre)
 WHERE similar <> u
WITH u, similar.name AS name, ux_classifiers, ux_features, g.id AS classifier,
  SUM(r.accuracy) AS total_feature
WITH u, name, ux_classifiers, ux_features, COLLECT(classifier) AS classifiers,
  COLLECT(total_feature) AS features
WITH u, name, alg.classifiers.similar(
  ux_classifiers, ux_features, classifiers, features) AS score
 WHERE score > 0.4
RETURN name, score
 ORDER BY score DESC

Получим список пользователей, которые пересекаются с интересами Lonnie R. Wright:

Тогда с помощью следующего запроса мы можем получить рекомендацию фильмов для нашего пользователя:

MATCH (u:User {name: 'Lonnie R. Wright'})-[:HAS_WATCHED]
  ->(m:Movie)-[r:IS_ASSOCIATED_WITH]->(g:Genre)
WITH u, g.id AS classifier, SUM(r.accuracy) AS total_accuracy
WITH u, COLLECT(classifier) AS ux_classifiers,
  COLLECT(total_accuracy) AS ux_features
MATCH (similar:User)-[:HAS_WATCHED]->(m:Movie)-[r:IS_ASSOCIATED_WITH]
  ->(g:Genre)
 WHERE similar <> u
WITH u, similar, ux_classifiers, ux_features, g.id AS classifier,
  SUM(r.accuracy) AS total_feature
WITH u, similar, ux_classifiers, ux_features,
  COLLECT(classifier) AS classifiers, COLLECT(total_feature) AS features
WITH u, similar, ux_classifiers, ux_features,
  alg.classifiers.similar(
  ux_classifiers, ux_features, classifiers, features) AS score
 WHERE score > 0.6
MATCH (m:Movie)-[r:IS_ASSOCIATED_WITH]->(g:Genre)
 WHERE NOT (u)-[:HAS_WATCHED]->(m) AND (similar)-[:HAS_WATCHED]-(m)
WITH ux_classifiers, ux_features, m.title AS title,
  COLLECT(g.id) AS classifiers, COLLECT(r.accuracy) AS features,
    COLLECT(g.name) AS genres
WITH title, alg.classifiers.similar(
  ux_classifiers, ux_features, classifiers, features) AS score
RETURN title, score
 ORDER BY score DESC

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

Заключение

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

Ответ на этот вопрос лежит больше в понимании доменной области.

Предположим, что у нас есть один миллион фильмов, из которых нам нужно достать рекомендацию, но при этом мы точно знаем, что у 2% фильмов можем порекомендовать среднестатическому пользователю.

А это значит, что мы смело можем отбросить 98% фильмов еще до того, как произвести поиск рекомендации.

Таким образом, выборка из один миллион данных сокращается до 20`000, что уже не так много.

Как понять, какой процент данных подойдет любому пользователю?

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

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

Предположим, что вам нужно из выборки исключить половину данных. В этом случае достаточно использовать "throttling data" в условии, с помощью следующего выражения: rand() > 0.5

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

Технические детали реализации: данные я брал из открытого источника для сервиса Unsplash. В результате у меня получилось >20 тыс. фотографий и >1.5 тыс. классификаторов в виде ключевых слов.

Время отдачи рекомендации в реальном времени составляет ~200ms.