Come conservare i set per trovare velocemente modelli simili?

Question

(Questo non è un compito a casa né un problema di lavoro. È solo il mio interesse / occupazione personale e completamente immaginario. Ma sono interessato a un buon algoritmo o struttura di dati.)

Supponiamo che avrei gestito un sito di incontri. E la mia funzione speciale sarebbe che i single erano abbinati al gusto del film . (Perché no?)

In tal caso, avrei bisogno di un modo per memorizzare le classificazioni dei film per ciascun utente. (Finora nessun problema.) E avrei bisogno di una struttura di dati per trovare l'utente più adatto. La distanza tra due modelli di gusto sarebbe la distanza media tra tutte le valutazioni effettuate da entrambi gli utenti.

Esempio

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

Distanza (X, Z) = avg (abs (9-9) + abs (1-4)) = 1.5

Distanza (Y, Z) = media (abs (4-6) + abs (6-4) + abs (8-7)) = 1.666

Quindi il signor X si adatta leggermente meglio alla signora Z, rispetto al signor Y.

Mi piace l'animazione che ...

• ... non sono necessarie molte operazioni sul database
• ... non è necessario gestire molti dati
• ... corri veloce
• ... offre la migliore corrispondenza
• Ok, forse prenderei in considerazione anche buone approssimazioni.

Cerca di tenere presente che questo dovrebbe funzionare anche con migliaia di film possibili, utenti che valutano solo circa 20-50 film e migliaia di utenti.

(Dato che si tratta di un enigma mentale e non di un problema reale, le aree di lavoro non aiutano davvero.)

Quale sarebbe il tuo algoritmo di ricerca o struttura di dati?

Answer 1

Sembra molto simile alla Premio Netflix , in particolare la prima metà dell'approccio più popolare . Le possibili implementazioni di ciò che stai cercando di fare sono numerose e varie. Nessuno di questi è eccezionalmente efficiente e la metrica L1 non è un'opzione particolarmente valida per correlazioni affidabili.

Answer 2

Sembra che tu stia cercando il vicino più vicino nello spazio del film. E la tua funzione di distanza è la L1 metric . Probabilmente puoi utilizzare un indice spaziale di qualche tipo. Forse puoi utilizzare le tecniche di filtro collaborativo .

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

La complessità sarà O (n ^1.5 )) anziché O (n ² ), poiché ci saranno n confronti con sqrt (n) film (media dei film riempiti insieme per ciascuna coppia).