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

Механизм рекомендаций (иногда называемый рекомендательной системой) — это инструмент, который позволяет разработчикам алгоритмов предсказывать, что может понравиться или не понравиться пользователю в списке заданных элементов. Системы рекомендаций — довольно интересная альтернатива полям поиска, поскольку системы рекомендаций помогают пользователям находить продукты или контент, с которыми они иначе не могли бы столкнуться. Это делает механизмы рекомендаций важной частью веб-сайтов и сервисов, таких как Facebook, YouTube, Amazon и других.

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

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

Множества и уравнения

Прежде чем внедрять механизм рекомендаций на основе совместной памяти, мы должны сначала понять основную идею такой системы. Для этого движка каждый элемент и каждый пользователь — не что иное, как идентификаторы. Поэтому при составлении рекомендаций мы не будем принимать во внимание какие-либо другие атрибуты фильма (например, актерский состав, режиссера, жанр и т. д.). Сходство между двумя пользователями представлено десятичным числом от -1,0 до 1,0. Мы будем называть это число индексом подобия. Наконец, вероятность того, что фильм понравится пользователю, будет представлена ​​другим десятичным числом от -1,0 до 1,0. Теперь, когда мы смоделировали мир вокруг этой системы, используя простые термины, мы можем использовать несколько элегантных математических уравнений, чтобы определить отношения между этими идентификаторами и числами.

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

Для расчета индекса подобия мы будем использовать вариант формулы индекса Жаккара. Первоначально известная как «общий коэффициент» (придуманная Полом Жаккаром), эта формула сравнивает два множества и выводит простую десятичную статистику в диапазоне от 0 до 1,0:

Формула включает деление количества общих элементов в любом наборе на количество всех элементов (учитываемых только один раз) в обоих наборах. Индекс Жаккара двух идентичных множеств всегда будет равен 1, тогда как индекс Жаккара двух множеств, не имеющих общих элементов, всегда будет давать 0. Теперь, когда мы знаем, как сравнивать два множества, давайте подумаем о стратегии, которую мы можем использовать для сравнения двух множеств. пользователи. Как обсуждалось ранее, пользователи, с точки зрения системы, — это три вещи: идентификатор, набор понравившихся фильмов и набор нелюбимых фильмов. Если бы нам нужно было определить индекс сходства наших пользователей, основываясь только на наборе понравившихся им фильмов, мы могли бы напрямую использовать формулу индекса Жаккара:

Здесь U1 и U2 — это два пользователя, которых мы сравниваем, а L1 и L2 — наборы фильмов, которые понравились U1 и U2 соответственно. Теперь, если подумать, два пользователя, которым нравятся одни и те же фильмы, похожи, то два пользователя, которым не нравятся одни и те же фильмы, также должны быть похожи. Здесь мы немного изменим уравнение:

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

Это одна длинная формула! Но это просто, обещаю. Это похоже на нашу предыдущую формулу с небольшим отличием в числителе. Теперь мы вычитаем количество конфликтующих симпатий и антипатий двух пользователей из числа их общих симпатий и антипатий. Это приводит к тому, что формула индекса подобия имеет диапазон значений от -1,0 до 1,0. У двух пользователей с одинаковыми вкусами индекс сходства будет равен 1,0, а у двух пользователей с совершенно противоположными вкусами в отношении фильмов индекс сходства будет равен -1,0.

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

Давайте немного разберем это уравнение. Под P(U,M) мы подразумеваем вероятность того, что пользователю U понравится фильм M . ZL и ZD представляют собой сумму индексов сходства пользователя U со всеми пользователями, которым понравился или не понравился фильм M соответственно. |ML|+|MD| представляет собой общее количество пользователей, которым понравился или не понравился фильм M . Результат P(U,M) дает число от -1,0 до 1,0.

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

Создание механизма рекомендаций

Мы создадим этот механизм рекомендаций как очень простое приложение Node.js. Также будет очень мало работы над внешним интерфейсом, в основном это будут HTML-страницы и формы (мы будем использовать Bootstrap, чтобы страницы выглядели аккуратно). На стороне сервера мы будем использовать CoffeeScript. Приложение будет иметь несколько маршрутов GET и POST. Несмотря на то, что у нас будет понятие пользователей в приложении, у нас не будет какого-либо сложного механизма регистрации/входа. Для постоянства мы будем использовать пакет Bourne, доступный через NPM, который позволяет приложению хранить данные в простых файлах JSON и выполнять к ним базовые запросы к базе данных. Мы будем использовать Express.js, чтобы упростить процесс управления маршрутами и обработчиками.

На этом этапе, если вы новичок в разработке Node.js, вы можете клонировать репозиторий GitHub, чтобы было проще следовать этому руководству. Как и в любом другом проекте Node.js, мы начнем с создания файла package.json и установки набора пакетов зависимостей, необходимых для этого проекта. Если вы используете клонированный репозиторий, файл package.json уже должен быть там, откуда для установки зависимостей потребуется выполнить «$ npm install». Это установит все пакеты, перечисленные в файле package.json.

Пакеты Node.js, которые нам нужны для этого проекта:

• асинхронный
• Борн
• кофейный сценарий
• выражать
• нефрит
• подчеркивать

Мы создадим механизм рекомендаций, разделив все соответствующие методы на четыре отдельных класса CoffeeScript, каждый из которых будет храниться в разделе «lib/engine»: Engine, Rater, Similars и Suggestions. Класс Engine будет отвечать за предоставление простого API для механизма рекомендаций и связывать три других класса вместе. Rater будет отвечать за отслеживание симпатий и антипатий (как два отдельных экземпляра класса Rater). Аналогичные и предложения будут нести ответственность за определение и отслеживание похожих пользователей и рекомендуемых элементов для пользователей, соответственно.

Отслеживание лайков и антипатий

Давайте сначала начнем с нашего класса Raters. Это простой:

 class Rater constructor: (@engine, @kind) -> add: (user, item, done) -> remove: (user, item, done) -> itemsByUser: (user, done) -> usersByItem: (item, done) ->

Как указывалось ранее в этом уроке, у нас будет один экземпляр Rater для лайков и еще один для антипатий. Чтобы записать, что пользователю нравится элемент, мы передадим их в «Rater#add()». Точно так же, чтобы удалить рейтинг, мы передадим их в «Rater#remove()».

Поскольку мы используем Bourne в качестве безсерверного решения для базы данных, мы будем хранить эти рейтинги в файле с именем «./db-#{@kind}.json», где вид — это либо «нравится», либо «не нравится». Мы откроем базу данных внутри конструктора экземпляра Rater:

 constructor: (@engine, @kind) -> @db = new Bourne "./db-#{@kind}.json"

Это сделает добавление рейтинговых записей таким же простым, как вызов метода базы данных Bourne внутри нашего метода «Rater#add()»:

 @db.insert user: user, item: item, (err) =>

И аналогично их удалить («db.delete» вместо «db.insert»). Однако, прежде чем мы что-то добавим или удалим, мы должны убедиться, что этого еще нет в базе данных. В идеале, с реальной базой данных, мы могли бы сделать это как одну операцию. В случае с Bourne мы должны сначала выполнить ручную проверку; и после того, как вставка или удаление завершены, нам нужно убедиться, что мы пересчитали индексы сходства для этого пользователя, а затем сгенерировали набор новых предложений. Методы «Rater#add()» и «Rater#remove()» будут выглядеть примерно так:

 add: (user, item, done) -> @db.find user: user, item: item, (err, res) => if res.length > 0 return done() @db.insert user: user, item: item, (err) => async.series [ (done) => @engine.similars.update user, done (done) => @engine.suggestions.update user, done ], done remove: (user, item, done) -> @db.delete user: user, item: item, (err) => async.series [ (done) => @engine.similars.update user, done (done) => @engine.suggestions.update user, done ], done

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

Два других метода, «Rater#itemsByUser()» и «Rater#usersByItem()» этого класса будут выполнять то, что подразумевают их имена — поиск элементов, оцененных пользователем и пользователями, которые оценили элемент, соответственно. Например, когда Rater создается с kind = “likes” , «Rater#itemsByUser()» найдет все элементы, которые оценил пользователь.

Поиск похожих пользователей

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

Как и в предыдущем классе Rater, мы поместим все в базу данных Bourne с именем «./db-similars.json», которую откроем в конструкторе Rater. В классе будет метод «Similars#byUser()», который позволит нам искать пользователей, похожих на данного пользователя, посредством простого поиска в базе данных:

 @db.findOne user: user, (err, {others}) =>

Однако наиболее важным методом этого класса является «Similars#update()», который работает, беря пользователя и вычисляя список других пользователей, которые похожи, и сохраняя список в базе данных вместе с их индексами сходства. Он начинается с поиска симпатий и антипатий пользователя:

 async.auto userLikes: (done) => @engine.likes.itemsByUser user, done userDislikes: (done) => @engine.dislikes.itemsByUser user, done , (err, {userLikes, userDislikes}) => items = _.flatten([userLikes, userDislikes])

Мы также находим всех пользователей, которые оценили эти элементы:

 async.map items, (item, done) => async.map [ @engine.likes @engine.dislikes ], (rater, done) => rater.usersByItem item, done , done , (err, others) =>

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

 async.map others, (other, done) => async.auto otherLikes: (done) => @engine.likes.itemsByUser other, done otherDislikes: (done) => @engine.dislikes.itemsByUser other, done , (err, {otherLikes, otherDislikes}) => done null, user: other similarity: (_.intersection(userLikes, otherLikes).length+_.intersection(userDislikes, otherDislikes).length-_.intersection(userLikes, otherDislikes).length-_.intersection(userDislikes, otherLikes).length) / _.union(userLikes, otherLikes, userDislikes, otherDislikes).length , (err, others) => @db.insert user: user others: others , done

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

Генерация рекомендаций

В нашем следующем классе, «Предложения», выполняются все прогнозы. Как и класс Similars, мы полагаемся на другую базу данных Bourne с именем «./db-suggestions.json», открытую внутри конструктора.

Класс будет иметь метод «Suggestions#forUser()» для поиска рассчитанных предложений для данного пользователя:

 forUser: (user, done) -> @db.findOne user: user, (err, {suggestions}={suggestion: []}) -> done null, suggestions

Метод, который будет вычислять эти результаты, называется «Suggestions#update()». Этот метод, как и «Similars#update()», принимает пользователя в качестве аргумента. Метод начинается с перечисления всех пользователей, похожих на данного пользователя, и всех элементов, которые данный пользователь не оценил:

 @engine.similars.byUser user, (err, others) => async.auto likes: (done) => @engine.likes.itemsByUser user, done dislikes: (done) => @engine.dislikes.itemsByUser user, done items: (done) => async.map others, (other, done) => async.map [ @engine.likes @engine.dislikes ], (rater, done) => rater.itemsByUser other.user, done , done , done , (err, {likes, dislikes, items}) => items = _.difference _.unique(_.flatten items), likes, dislikes

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

 @db.delete user: user, (err) => async.map items, (item, done) => async.auto likers: (done) => @engine.likes.usersByItem item, done dislikers: (done) => @engine.dislikes.usersByItem item, done , (err, {likers, dislikers}) => numerator = 0 for other in _.without _.flatten([likers, dislikers]), user other = _.findWhere(others, user: other) if other? numerator += other.similarity done null, item: item weight: numerator / _.union(likers, dislikers).length , (err, suggestions) =>

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

 @db.insert user: user suggestions: suggestions , done

Открытие API библиотеки

Внутри класса Engine мы связываем все в аккуратную структуру, подобную API, для легкого доступа из внешнего мира:

 class Engine constructor: -> @likes = new Rater @, 'likes' @dislikes = new Rater @, 'dislikes' @similars = new Similars @ @suggestions = new Suggestions @

Как только мы создадим экземпляр объекта Engine:

 e = new Engine

Мы можем легко добавлять или удалять лайки и антипатии:

 e.likes.add user, item, (err) -> e.dislikes.add user, item, (err) ->

Мы также можем начать обновлять индексы сходства пользователей и предложения:

 e.similars.update user, (err) -> e.suggestions.update user, (err) ->

Наконец, важно экспортировать этот класс Engine (и все остальные классы) из соответствующих файлов «.coffee»:

 module.exports = Engine

Затем экспортируйте Engine из пакета, создав файл «index.coffee» с одной строкой:

 module.exports = require './engine'

Создание пользовательского интерфейса

Чтобы иметь возможность использовать алгоритм механизма рекомендаций в этом руководстве, мы хотим предоставить простой пользовательский интерфейс через Интернет. Для этого мы создаем приложение Express внутри нашего файла «web.iced» и обрабатываем несколько маршрутов:

 movies = require './data/movies.json' Engine = require './lib/engine' e = new Eengine app = express() app.set 'views', "#{__dirname}/views" app.set 'view engine', 'jade' app.route('/refresh') .post(({query}, res, next) -> async.series [ (done) => e.similars.update query.user, done (done) => e.suggestions.update query.user, done ], (err) => res.redirect "/?user=#{query.user}" ) app.route('/like') .post(({query}, res, next) -> if query.unset is 'yes' e.likes.remove query.user, query.movie, (err) => res.redirect "/?user=#{query.user}" else e.dislikes.remove query.user, query.movie, (err) => e.likes.add query.user, query.movie, (err) => if err? return next err res.redirect "/?user=#{query.user}" ) app.route('/dislike') .post(({query}, res, next) -> if query.unset is 'yes' e.dislikes.remove query.user, query.movie, (err) => res.redirect "/?user=#{query.user}" else e.likes.remove query.user, query.movie, (err) => e.dislikes.add query.user, query.movie, (err) => res.redirect "/?user=#{query.user}" ) app.route('/') .get(({query}, res, next) -> async.auto likes: (done) => e.likes.itemsByUser query.user, done dislikes: (done) => e.dislikes.itemsByUser query.user, done suggestions: (done) => e.suggestions.forUser query.user, (err, suggestions) => done null, _.map _.sortBy(suggestions, (suggestion) -> -suggestion.weight), (suggestion) => _.findWhere movies, id: suggestion.item , (err, {likes, dislikes, suggestions}) => res.render 'index', movies: movies user: query.user likes: likes dislikes: dislikes suggestions: suggestions[...4] )

В приложении мы обрабатываем четыре маршрута. Индексный маршрут «/» — это место, где мы обслуживаем интерфейсный HTML, отображая шаблон Jade. Для создания шаблона требуется список фильмов, текущее имя пользователя, предпочтения и антипатии пользователя, а также четыре лучших предложения для пользователя. Исходный код шаблона Jade не упоминается в статье, но он доступен в репозитории GitHub.

Маршруты «/like» и «/dislike» — это то место, где мы принимаем POST-запросы для записи симпатий и антипатий пользователя. Оба маршрута добавляют оценку, предварительно удаляя любую конфликтующую оценку, если это необходимо. Например, если пользователю нравится что-то, что ему ранее не нравилось, обработчик сначала удалит рейтинг «не нравится». Эти маршруты также позволяют пользователю «не нравится» или «отменить неприязнь» к элементу, если это необходимо.

Наконец, маршрут «/refresh» позволяет пользователю повторно генерировать свой набор рекомендаций по требованию. Хотя это действие выполняется автоматически всякий раз, когда пользователь ставит какую-либо оценку элементу.

Тест-драйв

Если вы попытались реализовать это приложение с нуля, следуя этой статье, вам нужно будет выполнить последний шаг, прежде чем вы сможете протестировать его. Вам нужно будет создать файл «.json» в «data/movies.json» и заполнить его некоторыми данными фильма, например так:

 [ { "id": "1", "name": "Transformers: Age of Extinction", "thumb": { "url": "//upload.wikimedia.org/wikipedia/en/7/7f/Inception_ver3.jpg" } }, // … ]

Вы можете скопировать тот, который доступен в репозитории GitHub, который предварительно заполнен несколькими названиями фильмов и URL-адресами эскизов.

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

 $ npm start

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

 Listening on 5000

Поскольку мы не внедрили никакой настоящей системы аутентификации пользователей, приложение-прототип использует только имя пользователя, выбранное после посещения «http://localhost:5000». После ввода имени пользователя и отправки формы вы должны перейти на другую страницу с двумя разделами: «Рекомендуемые фильмы» и «Все фильмы». Поскольку нам не хватает самого важного элемента совместной системы рекомендаций на основе памяти (данных), мы не сможем порекомендовать какие-либо фильмы этому новому пользователю.

На этом этапе вы должны открыть другое окно браузера по адресу «http://localhost:5000» и войти в него как другой пользователь. Нравятся и не нравятся некоторые фильмы в качестве этого второго пользователя. Вернитесь в окно браузера первого пользователя и также оцените несколько фильмов. Убедитесь, что вы оценили хотя бы пару общих фильмов для обоих пользователей. Вы должны начать видеть рекомендации немедленно.

Улучшения

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

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

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

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

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

Заключение

Алгоритмы механизма совместных рекомендаций на основе памяти могут быть довольно мощными. Тот, с которым мы экспериментировали в этой статье, может быть примитивным, но он также прост: прост для понимания и прост в создании. Это может быть далеко не идеально, но надежные реализации механизмов рекомендаций, таких как Recommendable, построены на схожих фундаментальных идеях.

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