Создание «соседей» для пользователей, основанных на рейтинге

Question

Я ищу методы для создания «соседей» (людей с аналогичным вкусом) для пользователей на сайте, над которым я работаю; что-то похожее на способ last.fm.

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

Одна из идей, которые я имел, заключается в том, чтобы просто рассчитать совместимость каждой комбинации пользователей и выбрать пользователей с самым высоким рейтингом, чтобы быть соседями для пользователя. Недостатком этого является то, что по мере того, как число пользователей увеличивается, этот процесс кулаков занимает очень много времени. Для 1000 пользователей требуется 1000C2 (0,5 * 1000 * 999 = = 499 500) вызовов функции совместимости, которая также может быть очень тяжелой на сервере.

Так что я ищу любые советы, ссылки на статьи и т. Д. О том, как лучше всего достичь такой системы.

Answer 1

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

Чтобы начать проверку на разведку этого: http://en.wikipedia.org/wiki/Statistical_classification

Answer 2

В книге Программирование Collective Intelligence
http://oreilly.com/catalog/9780596529321

Глава 2 «Выполнение рекомендаций» не на основе действительно хорошую работу с изложением методов рекомендуя предметов для людей по сходству между пользователями. Вы можете использовать алгоритмы подобия, чтобы найти «соседей», которые вы ищете. Глава доступна на Поиск книг Google здесь:
http://books.google.com/books?id=fEsZ3Ey-Hq4C&printsec=frontcover

Answer 3

Вы слышали kohonen networks?

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

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

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

Кстати, чтобы найти хорошие разделительные переменные, лучшим алгоритмом является decision tree. Узлы, ближе к корню, будут самыми важными переменными, чтобы установить «близость».

Answer 4

Похоже, вы должны прочитать о clustering algorithms. Общая идея заключается в том, что вместо того, чтобы сравнивать каждую точку с каждой другой точкой каждый раз, когда вы делите их в кластерах похожих точек. Тогда окрестностью могут быть все точки в одном кластере. Количество/размер кластеров обычно является параметром алгоритма кластеризации.

В серии Google около cluster computing and mapreduce.

Answer 5

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

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

+1 для программирования Коллективный интеллект тоже - очень информативный - желаю, чтобы он не был (или я был!) Как ориентированный на Python, но все же хороший.

Answer 6

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

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

Netflix Prize - конкурс для определения, кто может наиболее эффективно решить эту проблему. Следуйте ссылкам с их LeaderBoard. Некоторые из конкурентов разделяют их решения.

Насколько вычислительно недорогое решение, вы можете попробовать это:

• создать категории для ваших вещей. Если мы говорим о музыке, они могут быть классическими, рок, джаз, хип-хоп ... или идти дальше: Grindcore, Math Rock, Riot Grrrl ...
• Теперь, каждый раз, когда пользователь оценивает предмет, сверните свои рейтинги на уровень категории. Таким образом, вы знаете, что «Пользователь А» любит Хонки Тонк и Киссид Хаус, потому что они часто дают эти высокие оценки. Частота и сила, вероятно, важны для совокупной оценки вашей категории.
• Когда пришло время найти соседей, а не путешествовать по всем рейтингам, просто найдите похожие оценки в категориях.

Этот метод будет не таким точным, но быстрым.

Cheers.

Answer 7

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

Одна хорошая возможность здесь использовать spectral clustering, которая нуждается в том, что у вас есть: матрица подобия. Недостатком является то, что вам все равно нужно вычислить свою функцию совместимости для каждой пары точек, т.е. е. алгоритм O (n^2).

Если вам нужен алгоритм быстрее, чем O (n^2), вы можете попробовать подход под названием dissimilarity spaces. Идея очень проста. Вы инвертируете свою функцию совместимости (например, принимая ее обратную), чтобы превратить ее в меру несходства или расстояния. Затем вы сравниваете каждый элемент (пользователь в вашем случае) с набором элементов прототипа и обрабатываете полученные расстояния как координаты в пространстве. Например, если у вас есть 100 прототипов, каждый пользователь будет представлен вектором из 100 элементов, т.е. е. точкой в ​​100-мерном пространстве.Затем вы можете использовать любой стандартный алгоритм кластеризации, такой как K-means.

Вопрос в том, как вы выбираете прототипы и сколько вам нужно. Однако были рассмотрены различные эвристики, однако здесь приведено dissertation, в котором утверждается, что выбор прототипов случайным образом может быть достаточным. В нем показаны эксперименты, в которых с использованием 100 или 200 случайно выбранных прототипов получены хорошие результаты. В вашем случае, если у вас 1000 пользователей, и вы выбрали 200 из них, чтобы быть прототипами, вам нужно будет оценить свою совместимость 200 000 раз, что является улучшением в 2,5 раза по сравнению с каждой парой. Однако реальным преимуществом является то, что для 1 000 000 пользователей 200 прототипов будет по-прежнему достаточным, и вам нужно будет собрать 200 000 000 сравнений, а не 500 000 000 000, что будет улучшено в 2500 раз. Что вы получаете, это алгоритм O (n), который лучше, чем O (n^2), несмотря на потенциально большой постоянный коэффициент.