Как найти похожих пользователей по их интересам

Question

Я пытаюсь создать систему, которая могла бы найти пользователей с похожими любимыми фильмами / книгами / интересами / и т. Д., Очень похожими на соседей по last.fm. Пользователи, имеющие общие интересы, будут иметь наибольшее совпадение и будут отображаться в профилях пользователей (5 лучших совпадений или около того).

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

Я предполагаю, что существует какое-то эффективное решение, так как last.fm работает довольно хорошо. Я бы предпочел использовать какую-нибудь общую базу данных SQL, такую ​​как mySQL или pgSQL, но что-нибудь подойдет.

Спасибо за ваши предложения.

---

UPDATE:
Как выясняется, самой большой проблемой является поиск ближайших соседей в базах данных SQL, поскольку ни одна из них с открытым исходным кодом не поддерживает такой вид поиска.
Таким образом, мое решение состояло бы в том, чтобы модифицировать ANN для запуска в качестве службы и запрашивать его из PHP (например, с помощью сокетов) - даже миллионы пользователей с 7 измерениями в памяти не так уж сложны и работают невероятно быстро.

Еще одним решением для небольших наборов данных является простой запрос:

SELECT b.user_id, COUNT(1) AS mutual_interests
FROM `users_interests` a JOIN `users_interests` b ON (a.interest_id = b.interest_id)
WHERE a.user_id = 5 AND b.user_id != 5
GROUP BY b.user_id ORDER BY mutual_interests DESC, b.user_id ASC

20-50 мс с 100K пользователями, каждый из которых имеет ~ 20 интересов (из 10 000 возможных интересов) в среднем

Answer 1

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

Какое именно пространство и какую метрику расстояния вы хотите использовать - это, вероятно, вещи для экспериментальной оценки на основе ваших данных. К счастью, есть пакет C ++, который вы можете использовать для решения этой проблемы с различными метриками и алгоритмами в соответствии с вашими потребностями: http://www.cs.umd.edu/~mount/ANN/

Редактировать: это правда, что время работы здесь зависит от количества функций. Но есть удобная теорема в многомерной геометрии, которая гласит, что если у вас есть n точек в произвольно больших измерениях, и вы заботитесь только о приблизительных расстояниях, вы можете проецировать их в O (log n) измерений без потерь. См. Здесь (http://en.wikipedia.org/wiki/Johnson-Lindenstrauss_lemma). (случайная проекция выполняется путем умножения ваших точек на случайную матрицу со значением + 1 / -1). Обратите внимание, что log (1,000,000) = 6, например.