Коллаборативная фильтрация / рекомендации Система производительности и подходы

Question

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

В настоящее время у меня есть только 2 тыс. Пользователей, но моя текущая система уже не годится для будущего и уже очень обременительна для сервера. Вся система основана на предоставлении рекомендаций пользователям. Мое приложение - PHP/MySQL, но я использую MongoDB для совместной фильтрации - я работаю на большом экземпляре Amazon EC2. Моя установка действительно двухэтапная. Сначала я вычисляю сходства между предметами, а затем использую эту информацию для выработки рекомендаций. Вот как это работает:

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

• Каждый раз, когда добавляется запись, добавляется тег, комментируется или нравится, я добавляю его в очередь.
• Я обрабатываю эту очередь через cron (один раз в день), выясняя соответствующую информацию для каждого поста, например, user_id для комментаторов и likers и tag_id. Я сохраняю эту информацию в MongoDB в такой структуре: {"post_id":1,"tag_ids":[12,44,67],"commenter_user_ids":[6,18,22],"liker_user_ids":[87,6]}. Это позволяет мне в конечном итоге создать коллекцию MongoDB, которая дает мне простой и быстрый доступ ко всей необходимой информации, когда я пытаюсь вычислить сходства
• Затем я запускаю другой скрипт cron (также один раз в день, но после предыдущего), который снова проходит через очередь. На этот раз для каждого поста в очереди я извлекаю их запись из коллекции MongoDB и сравниваю ее со всеми остальными записями. Когда 2 записи имеют некоторую информацию о соответствии, я даю им +1 с точки зрения сходства. В конце у меня есть общий балл за каждую пару постов. Я сохраняю оценки в другой коллекции MongoDB со следующей структурой: {"post_id": 1, "Similar":{"23":2,"2":5,"7":2}} ("Similar" является ключ => массив значений с post_id в качестве ключа и оценкой сходства в качестве значения. Я не сохраняю оценку, если она равна 0.

У меня есть 5k сообщений. Так что все вышеперечисленное довольно сложно на сервере. Существует огромное количество операций чтения и записи. Теперь это только половина вопроса. Затем я использую эту информацию, чтобы выяснить, какие сообщения будут интересны конкретному пользователю. Итак, раз в час я запускаю скрипт cron, который запускает скрипт, который вычисляет 1 рекомендованную запись для каждого пользователя на сайте. Процесс идет так:

• Сначала скрипт решает, какой тип рекомендации получит пользователь. Это 50-50 изменений - 1. Пост, похожий на один из ваших постов, или 2. Пост, похожий на пост, с которым вы взаимодействовали.
• Если 1, то скрипт получает пользователей post_ids из MySQL, а затем использует их для получения аналогичных сообщений из MongoDB. Скрипт принимает пост, который наиболее похож и еще не рекомендован пользователю.
• Если 2, сценарий получает все сообщения, которые пользователь прокомментировал или любил в MySQL, и использует свои идентификаторы, чтобы сделать то же самое в 1 выше.

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

Мне просто интересно, если кто-то чувствует, что я мог бы подойти к этому лучше?

Answer 1

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

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

Затем создайте индексы лайков в каком-то значимом порядке и посчитайте инверсии (разделяй и властвуй - это очень похоже на сортировку слиянием, и вы все равно захотите отсортировать на своем пути для подсчета расщепленных инверсий).

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

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

Еще лучше было бы указать сами статьи, чтобы, если кому-то понравилась статья, вы могли видеть статьи, которые им могут понравиться, основанные на других пользователях (например, "пользователи Amazon, купившие это, также купили").

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

Answer 2

С 5000 сообщений, это 25 000 000 отношений, увеличивая O(n^2).

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

Другое соображение, когда вы устанавливаете отношения. Почему вы ждете, пока не запустится пакет, чтобы сравнить новый пост с существующими данными? Конечно, имеет смысл обрабатывать это асинхронно, чтобы обеспечить быструю обработку запроса - но (кроме ограничений, налагаемых вашей платформой), зачем ждать, пока пакет не вступит в силу, прежде чем устанавливать отношения? Используйте асинхронную очередь сообщений.

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

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

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