somiglianza tra gli utenti basano sui voti

Question

Diciamo che ho un gruppo di utenti, un insieme di canzoni, e una serie di voti per ogni brano:

=========== =========== ======= 
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] 
=========== =========== ======= 

che cosa è il modo più efficiente per calcolare similarità utente basata su canzone-voti? c'è un modo migliore di iterare su ogni utente e ogni voto per ogni canzone?

Answer 1

Ci sono due metriche comuni che possono essere utilizzati per trovare le somiglianze tra gli utenti:

1. distanza euclidea, che è esattamente ciò che sei pensando: immagina un grafico n-dimensionale che ha per ogni asse una canzone che viene rivista da due utenti coinvolti (u1 e * u2) e il valore sul suo asse è il punteggio. Puoi facilmente calcolare la somiglianza usando la formula:

   per ogni brano recensito da u1 e u2, calcolare pow(u1.song.score - u2.song.score, 2) e aggiungere tutti insieme in sum_of_powers. Il coefficiente di similarità viene quindi fornito da 1/1 + (sqrt(sum_of_powers)).

2. Correlazione di Pearson (o coefficiente di correlazione): è un approccio migliore che rileva quanto due insiemi di dati siano correlati l'uno con l'altro. Questo approccio utilizza formule più complesse e un po 'di background statistiche, controlla qui: wiki. Avrai un grafico per ogni coppia di utenti, quindi traccia i punti in base ai punteggi .. ad esempio se aSong è stato votato 2 da u1 e 4 da u2 verrà tracciato il punto (2,4) (presupponendo che l'utente1 sia l'asse xe l'u2 è l'asse y).

Giusto per chiarire, si utilizza regressione lineare per trovare due coefficienti A e B, che descrivono la linea che riduce al minimo la distanza da tutti i punti del grafico. Questa riga ha questa formula: y = Ax + B. Se due set sono punti simili dovrebbero essere vicini alla diagonale principale quindi A dovrebbe tendere a 1 mentre B a 0. Non dare per scontato che questa spiegazione sia completa o di riferimento perché manca di solidità e tipico formalismo matematico, ma solo per darti un'idea.

EDIT: come scritto da altri, più complessi algoritmi per dati del cluster esistono, come k-means, ma vi consiglio di iniziare da quelli semplici (in realtà dovrebbe essere necessario qualcosa di più difficile proprio quando ci si rende conto che i risultati sono non abbastanza).

Answer 2

Dovresti riuscire a trovare un buon algoritmo in questo libro: The Algorithm Design Manual di Steven Skiena.

Il libro ha un sacco di algoritmi per vari scopi. Tu vuoi un algoritmo di clustering grafico, credo. Non ho a portata di mano la mia copia del libro, quindi non posso cercarlo per te.

Una rapida ricerca su Google ha trovato una pagina di Wikipedia: http://en.wikipedia.org/wiki/Cluster_analysis Forse ciò aiuterà, ma penso che il libro spieghi gli algoritmi in modo più chiaro.

Answer 3

Raccomando il libro Programming Collective Intelligence di Toby Segaran. Il capitolo 3 descrive diversi metodi di clustering come Hierarchical Clustering e K-means Clustering.

Il codice sorgente per gli esempi è disponibile here

Answer 4

Se si desidera ottenere i risultati più precisi, quindi no, è necessario eseguire iterazioni su tutto.

Se il tuo database è abbastanza grande, potresti semplicemente effettuare un campionamento statistico, ad esempio prendendo tra 1.000 e 10.000 utenti e confrontandolo con quello.

Sarebbe anche meglio aggiungere altre tabelle al database, archiviare i risultati e aggiornarli ogni tanto, invece di calcolarli al volo.

Answer 5

Ilya Grigorik ha realizzato una serie di algoritmi di raccomandazione, sebbene si stesse concentrando su Ruby. Sembra che sia sotto la sezione di apprendimento automatico nel suo archives, ma non esiste un collegamento di sezione diretto.

Answer 6

Penso che a molte persone qui manca la semplicità della domanda. Non ha detto nulla sulla creazione di un sistema di previsione del rating. Vuole solo calcolare la somiglianza tra il comportamento di classificazione dei brani di ciascun utente e il comportamento di valutazione dei brani di ciascun altro utente. Il coefficiente di correlazione di Pearson dà esattamente questo. Sì, è necessario scorrere su ogni coppia utente/utente.

EDIT:

Dopo pensando a questo un po 'di più:

Pearson è grande se si desidera che la somiglianza tra i gusti dei due utenti, ma non il loro livello di 'opinionatedness' ... un utente che valuta una serie di brani 4, 5 e 6 che si correlano perfettamente con un altro utente che valuta le stesse canzoni 3, 6 e 9. In altre parole, hanno lo stesso "gusto" (classificano le canzoni nello stesso ordine), ma il secondo utente è molto più supponente. In altre parole, il coefficiente di correlazione considera ogni due vettori di valutazione con una relazione lineare uguale.

Tuttavia, se si desidera la somiglianza tra le valutazioni effettive fornite dagli utenti a ciascuna canzone, è necessario utilizzare l'errore quadratico medio quadratico tra i due vettori di valutazione. Questa è una metrica basata esclusivamente sulla distanza (le relazioni lineari non giocano nel punteggio di similarità), quindi gli utenti di 4,5,6 e 3,6,9 non avrebbero un punteggio di similarità perfetto.

La decisione si riduce a ciò che si intende per "simile" ...

Questo è tutto.

Answer 7

Se si desidera eseguire l'operazione in modo approssimativo senza visualizzare tutti i record, è possibile utilizzare il coefficiente Jaccard. Probabilmente ha bisogno di un adattamento se vuoi prendere in considerazione i punteggi. Ma credo che siano le migliori soluzioni se il tuo sistema è troppo grande e non hai il tempo di controllare tutti i record.