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

Question

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

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

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

• Каждый раз, когда добавляется запись, добавляется тег, комментируется или нравится, я добавляю его в очередь.
• Я обрабатываю эту очередь через cron (один раз в день), выясняя соответствующую информацию для каждого сообщения, например, user_id's из комментаторов и 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

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

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

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

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

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

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

Answer 2

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

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

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

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

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

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

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