Генерация 'соседей' к пользователям на основе оценки

В книге, Программируя Коллективный разум
http://oreilly.com/catalog/9780596529321

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

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

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

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

До в вычислительном отношении недорогого решения Вы могли попробовать это:

• Создайте категории для своих объектов. Если мы говорим о музыке, они могли бы быть классическими, скала, джаз, хип-хоп... или пойти далее: Grindcore, Математическая Скала, Бунт Grrrl...
• Теперь, каждый раз пользователь оценивает объект, сверните их оценки на уровне категории. Таким образом, Вы знаете, что 'Пользователю' нравится Белый, Сильно ударяют и Эйсид-хаус, потому что они часто дают тем объектам высокие оценки. Частота и сила, вероятно, важны для Вашего счета агрегата категории.
• Когда пора найти, что соседи, вместо того, чтобы путешествовать посредством всех оценок, просто ищут подобные очки в категориях.

Этот метод не был бы так же точен, но это быстро.

Удачи.

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

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

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

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

Проблема походит, чтобы быть 'проблемами классификации'. Да существует столько решений и подходов.

Для запуска исследования проверяют это: http://en.wikipedia.org/wiki/Statistical_classification

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

Эй может найти видео о кластеризации в ряду Google о кластерных вычислениях и mapreduce.

Вы услышали о kohonen сетях?

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

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

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

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

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

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

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