Сходство между пользователями на основе голосов

Question

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

=========== =========== =======
User        Song        Vote
=========== =========== =======
user1       song1       [score]
user1       song2       [score]
user1       song3       [score]
user2       song1       [score]
user2       song2       [score]
user2       song3       [score]
user3       song1       [score]
user3       song2       [score]
user3       song3       [score]
user-n      song-n      [score]
=========== =========== =======

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

Answer 1

Существует две общие метрики, которые можно использовать для поиска сходства между пользователями:

1. Евклидово расстояние , это именно то, о чем вы думаете: представьте n-мерный график, в котором для каждой оси есть песня, которая рассматривается двумя вовлеченными пользователями ( u1 и * u2), а значение на его оси - оценка. Вы можете легко рассчитать сходство по формуле:

   для каждой песни, просмотренной u1 и u2, вычислите pow(u1.song.score - u2.song.score, 2) и сложите все вместе в sum_of_powers. Коэффициент подобия тогда определяется как 1 / 1 + (sqrt(sum_of_powers)).

2. корреляция Пирсона (или коэффициент корреляции): это лучший подход, позволяющий определить, насколько два набора данных связаны друг с другом. Этот подход использует более сложные формулы и немного статистики, проверьте это здесь: wiki . У вас будет график для каждой пары пользователей, а затем вы начертите точки в соответствии с баллами. Например, если за aSong было проголосовано 2 от u1 и 4 от u2, будет построена точка (2,4) (при условии что user1 - это ось x, а u2 - это ось y).

Просто чтобы уточнить, вы используете линейную регрессию , чтобы найти два коэффициента A и B, которые описывают линию, которая минимизирует расстояние от всех точек графика. Эта строка имеет следующую формулу: y = Ax + B. Если два набора одинаковых точек должны быть рядом с главной диагональю, поэтому A должно стремиться к 1, а B к 0. Не принимайте это объяснение как полное или в качестве справочного, потому что ему не хватает обоснованности и типичного математического формализма, просто чтобы дать вам представление.

EDIT: Как написано другими, существуют более сложные алгоритмы для кластеризации данных, например, k-means, но я предлагаю вам начать с простых (на самом деле вам нужно что-то более сложное, только когда вы понимаете, что результатов недостаточно).

Answer 2

Рекомендую книгу Программирование Коллективного Разума от Тоби Сегарана. Глава 3 описывает различные методы кластеризации, такие как Иерархическая кластеризация и К-значит кластеризация .

Исходный код для примеров доступен здесь

Answer 3

Если вы хотите получить наиболее точные результаты, то нет, вам придется перебирать все.

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

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

Answer 4

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

Answer 5

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

EDIT:

Подумав об этом еще немного:

Пирсон - это замечательно, если вы хотите сходства между вкусами двух пользователей, но не их уровнем «самоуверенности» ... один пользователь, который оценит серию песен 4, 5 и 6, будет отлично соотноситься с другим пользователем, который оценивает одни и те же песни 3, 6 и 9. Другими словами, они имеют один и тот же «вкус» (они оценивают песни в одинаковом порядке), но второй пользователь гораздо более самоуверенный. Другими словами, коэффициент корреляции рассматривает любые два вектора рейтинга с линейной зависимостью как равные.

Однако, если вы хотите подобия между фактическими оценками, которые пользователи дали каждой песне, вы должны использовать среднеквадратичную ошибку между двумя векторами рейтинга. Это показатель, основанный исключительно на расстоянии (линейные отношения не играют на оценку сходства), поэтому пользователи 4,5,6 и 3,6,9 не будут иметь идеального показателя сходства.

Решение сводится к тому, что вы подразумеваете под "подобным" ...

Это все.

Answer 6

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

Answer 7

В этой книге вы сможете найти хороший алгоритм: Руководство по разработке алгоритмов Стивена Скиены.

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

Быстрый поиск в Google нашел страницу в Википедии: http://en.wikipedia.org/wiki/Cluster_analysis Возможно, это поможет, но я думаю, что книга объясняет алгоритмы более четко.