My favorites | Sign in
Project Home Wiki Issues Source
READ-ONLY: This project has been archived. For more information see this post.
Search
for
Introduzione  
Updated Sep 18, 2013 by andrea.p...@gmail.com

Introduzione

Il progetto in esame mira a raccomandare brani musicali ad un utente. Tutte le informazioni su brani e utenti sono ricavate grazie alle API di Last.fm. Nel processo di raccomandazione, i due fattori principali tenuti in considerazione sono:

  • le amicizie dell'utente
  • i tag associati ai brani

Algoritmo

Da un punto di vista ad alto livello, il processo di raccomandazione può essere diviso nelle seguenti fasi:

  1. Recupera tutti gli utenti collegati all'utente tramite qualche amicizia (amico diretto, amico di amico, ecc.)
  2. Per ogni utente, recupera i suoi brani preferiti e quelli che ha ascoltato
  3. Per ogni brano (di ogni utente) recupera i tag associati a quel brano
  4. Per ogni utente, calcola la similarità con l'utente iniziale e utilizzala per pesare i tag associati a quell'utente
  5. Per ognuno dei migliori tag, recupera i migliori brani per quel tag, in modo da raccomandarli all'utente
  6. Per ogni brano da raccomandare verifica che (rispetto all'utente iniziale):
    • non lo ha ascoltato
    • non è tra i suoi preferiti
    • non lo ha bannato
  7. Inoltre, per l'autore di ogni brano da raccomandare, verifica che (sempre rispetto all'utente iniziale):
    • o è un autore che ascolta
    • o è un autore simile a quelli che ascolta
    • o è un autore ascoltato dagli utenti più simili a lui

Amicizie

A partire dall'utente iniziale vengono recuperati i suoi amici, poi gli amici degli amici e così via, fino ad una data profondità. Tuttavia è possibile che un utente, compreso l'utente iniziale, non abbia alcun amico o ne abbia pochi. Questo potrebbe impedire di raccomandare brani all'utente.

Per questo per ogni utente, oltre che agli amici, vengono recuperati anche un certo numero di utenti simili (secondo Last.fm). In questo modo si hanno comunque un certo numero di utenti da poter analizzare, anche se si hanno pochi amici. Inoltre, siccome gli utenti simili vengono scelti sulla base degli autori che ascoltano, c'è una buona probabilità che tali utenti permettano buone raccomandazioni.

Se per ogni utente si devono avere K utenti a lui vicini da analizzare, allora il numero di utenti simili da richiedere a Last.fm è:

In questo modo, anche se l'utente ha abbastanza amici (friends=K), viene comunque richiesto un utente simile a Last.fm. Così facendo si ha comunque la possibilità di raccomandare brani di interesse per l'utente, anche se i gusti degli amici non coincidono con i suoi.

Similarità fra utenti

Una parte molto importante dell'algoritmo appena citato è il calcolo della similarità fra due utenti. Ogni utente viene rappresentato come un vettore pesato di tag, che rappresentano i tag dei suoi brani preferiti o che ha ascoltato. Per esempio, due utenti possono essere rappresentati dai seguenti vettori:

User1: (rock 20, pop 10, rap 3)
User2: (rock 12, classic 6, pop 4)

La similarità fra due utenti è calcolata tramite l'utilizzo della metrica cosine similarity:

Per i due utenti citati, la similarità risulta quindi essere:

La similarità con l'utente iniziale viene poi utilizzata per pesare il contributo per i tag di un utente. Basandoci su solo questi due utenti e assumento User1 come utente iniziale, il vettore pesato dei tag risulterebbe:

Ranking dei risultati

Un'altra parte degna di nota è il processo di ranking dei risultati. Una volta creato il vettore pesato di tag, si estraggono i brani migliori per i migliori tag. Ad gni brano viene poi dato un peso pari al peso (normalizzato) del tag che lo ha generato. In riferimento al vettore dei tag precedente, normalizzando si ottiene:

Quindi, per ogni brano recuperato per il tag 'rock' viene assegnato peso 1, per ogni brano per il tag 'pop' viene assegnato peso 0.44, ecc. Poi si ordina la lista dei brani in modo che se un brano è stato recuperato da più tag, sarà preferito rispetto ad altri.

Tuning dell'algoritmo

E' possibile cambiare il comportamento dell'algoritmo tramite alcuni parametri contenuti nella classe TuningParameters. In questo modo si rende più flessibile il processo e si può valutare il cambiamento della raccamandazione al variare dei vari parametri. Per esempio, si possono cambiare:

  • Numero massimo di tag da recuperare per un brano
  • Numero massimo di brani da recuperare per un tag
  • Profondità del grafo delle amicizie
  • Ecc...

Struttura del progetto

Il progetto è articolato in package, che contengono ognuno classi con responsabilità simili:

  • creator - Contiene classi responsabili della creazione (tramite delega a classi del livello più basso) delle strutture principali necessarie al funzionamento dell'algoritmo, come la lista degli utenti, la lista dei brani per ogni utente, ecc.
  • domain - Contiene le classi del dominio applicativo come Track e Tag.
  • parser - Contiene classi responsabili del parsing delle risposte ricevute da Last.fm in seguito alle varie richieste.
  • thread - Contiene le classi responsabili della suddivisione dei processi in vari thread.
  • util - Contiene classi eterogenee che svolgono funzionalità utili in vari punti dell'algoritmo.

Richieste e risposte da Last.fm

Per ogni informazione necessaria all'algoritmo, per esempio i brani preferiti di un utente, si deve:

  1. Inviare una richiesta HTTP alle API di Last.fm
  2. Parsare la risposta

Delle richieste HTTP si occupa la classe Requester, mentre del parsing delle risposte (che hanno formato JSON) se ne occupano le varie classi contenute nel package 'parser'.

Parallelismo

Durante tutto il processo, due azioni condizionano in particolar modo il tempo impiegato dall'algoritmo per terminare: l'invio delle richieste HTTP e il parsing delle relative risposte. Per questo è stato implementato un meccanismo di thread che possa essere utilizzato nelle varie situazioni in maniera facile e flessibile.

Il tutto è organizzato in modo da creare un numero di thread pari ai processori disponibili ed impiegarli per risolvere un determinato task in maniera parametrica. Ogni task (come recuperare i tag relativi ad un brano) è rappresentato da una classe nel package 'thread/processor' e viene attuato su una lista fornita in input, da cui vengono estratti gli oggetti da processare.

Database dei tag

Tra le varie richieste da fare a Last.fm, la richiesta relativa ai tag è la più onerosa. Infatti occorre fare una richiesta per ogni brano di ogni utente. Tuttavia, siccome i tag di un brano possono essere considerati un'informazione abbastanza stabile, si utilizza un database per ottimizzare le prestazioni del processo.

La struttura del database è molto semplice: una sola tabella che colleziona tuple relative ai tag di un brano. Vi sono quindi tre colonne:

  • Nome del brano
  • Nome dell'artista del brano
  • Lista dei tag del brano (codificata come un'unica stringa di tag separati da uno spazio)

Prima di fare una richiesta a Last.fm, si controlla quindi che esista una tupla relativa al brano in questione nel database. Se esiste si evita di fare la richiesta, altrimenti la si fa e si inseriscono poi i tag del brano nel database.

Powered by Google Project Hosting