Как хранить наборы, чтобы быстро найти похожие шаблоны?

Question

(Это не домашняя работа и не проблема работы. Это просто мой личный интерес / профессия и вымышленная. Но меня интересует хороший алгоритм или структура данных.)

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

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

Пример

movies   A B C D E F G H I J K L M ...
user Xm  9 5   1   1   5
user Ym      4 6 1         8
user Zf  9   6 4           7

Расстояние (X, Z) = среднее (абс (9-9) + абс (1-4)) = 1,5

Расстояние (Y, Z) = среднее (абс (4-6) + абс (6-4) + абс (8-7)) = 1,666

Значит, мистер X подходит немного лучше миссис Z, чем мистер Y.

Мне нравится, что душ ...

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

Постарайтесь помнить, что это также должно работать с тысячами возможных фильмов, пользователями, которые оценивают только около 20-50 фильмов, и тысячами пользователей.

(Поскольку это ментальная головоломка, а не реальная проблема, обходные пути на самом деле не помогают.)

Каким будет ваш алгоритм поиска или структура данных?

Answer 1

Похоже, вы ищете ближайшего соседа в пространстве фильма. И ваша функция расстояния - метрика L1 . Вы можете, вероятно, использовать пространственный индекс некоторого вида. Может быть, вы можете использовать методы совместной фильтрации .

Answer 2

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

Answer 3

CREATE TABLE data (user INTEGER, movie INTEGER, rate INTEGER);

SELECT  other.user, AVG(ABS(d1.rate - d2.rate)) AS distance
FROM    data me, data other
WHERE   me.user = :user
    AND other.user <> me.user
    AND other.movie = me.movie
GROUP BY
    other.user
ORDER BY
    distance

Сложность будет O (n ^1.5 )), а не O (n ² ), так как будет n сравнение с sqrt(n) фильмами (среднее количество заполненных фильмов вместе каждой парой).