Recommender systems : Content-based RS

Da Wiki Corso Web.

Indice

STATO=Libero

back

Definizione RS [Mazzotta Simone]

Un Recommender System (RS), secondo la definizione, è un software di filtraggio di contenuti che guida un utente nelle sue scelte, fornendo risultati personalizzati.
Più in generale, un Recommender System può essere applicato in un qualsiasi contesto in cui le preferenze dell’utente siano una discriminante fondamentale per la ricerca: film, video, musica, libri, notizie, immagini, prodotti ma anche servizi. Le società di eCommerce, in particolare, sono in permanente competizione tra loro, cercando di prevalere l’una sull’altra in una sfida senza fine.
A tale scopo investono importanti cifre di denaro per capire ciò che desiderano i clienti. L’importanza dei Recommender System in questo ambito, quindi, è sempre più evidente.

I Recommender system rappresentano un'ampia famiglia di strumenti che forniscono suggerimenti automatici personalizzati ad un utente, basandosi sulle sue preferenze. Una possibile definizione formale del compito affidato ad un Recommender System può essere la seguente:

"Sia C l’insieme di tutti gli utenti di una applicazione che adotta un RS. Sia S l’insieme di tutti i possibili item che il RS può proporre agli utenti. Sia R un insieme finito, discreto e totalmente ordinato (es. i numeri naturali da 1 a 10). Sia u una funzione che misura l’utilità di un oggetto s ϵ S per un utente c ϵ C tale che u: C X S -> R. Per ogni utente c di C il Recommender System deve scegliere un oggetto Sbest di S, che massimizzi la funzione u. "
La principale difficoltà insita in questo task è che la funzione u non è definita per tutte le coppie (utente, oggetto), quindi non è possibile stabilire quale sia l’oggetto migliore per un utente.

Lo scopo di un Recommender System è fornire all’utente suggerimenti che corrispondano alle sue preferenze. Per raggiungere tale obiettivo, ci sono una serie di proprietà che un Recommender System dovrebbe garantire: la trasparenza, la possibilità di correzione,l’affidabilità,l’efficacia,la capacità di persuasione,l’efficienza,la soddisfazione del cliente,l’ampiezza dei risultati,l’aggiornamento costante,la serendipità,la varietà dei suggerimenti,la robustezza, il rispetto della privacy,la scalabilità. (Per avere più informazioni sulle proprietà, utilizzare la fonte del contributo, da pagina 28 in poi.)

Classificazione RS [Mazzotta Simone]

Adottando come criterio di classificazione di un Recommender System l’origine dei suggerimenti si possono distinguere quattro tipi di RS:

  1. Collaborative Based (o Social based). Il RS suggerisce all’utente gli item preferiti dalle persone simili a lui;
  2. Content Based. Gli item suggeriti dal sistema sono simili a quelli che l’utente ha giudicato positivamente in passato;
  3. Economic Factor Based. Il sistema suggerisce gli item che possiedono il miglior rapporto qualità prezzo, in base ai costi oggettivi e alle valutazioni soggettive degli utenti;
  4. Hybrid. Nei suggerimenti di questo tipo vi è la compresenza di due o più fattori tra quelli sopracitati (preferenze degli utenti simili, item preferiti dall’utente, rapporto qualità prezzo).

I suggerimenti possono essere forniti in base a specifiche richieste dell’utente oppure proposti in automatico, quindi con diverse modalità di erogazione dei suggerimenti. In base al modello di information retrieval utilizzato si distinguono tre tipi di Recommender System:

  1. Pull information model. L’utente deve eseguire una query per ricevere il suggerimento, specificando i parametri necessari alla ricerca;
  2. Push information model. L’utente riceve i suggerimenti in base alle informazioni contenute nel suo profilo;
  3. Hybrid. È una combinazione dei due modelli.

Esempi di utilizzo di RS [Mazzotta Simone]

Vengono qui elencati tre esempi di siti web che integrano nelle loro applicazioni un Recommender System.

Amazon

Amazon è una compagnia di commercio elettronico statunitense con sede a Seattle, nello stato di Washington.
Il Recommender System di Amazon è basato sullo storico degli acquisti di un utente, sullevalutazioni dei prodotti più venduti, e sui giudizi personali relativi a oggetti proposti in passato dal sistema.

Inoltre vengono indicate anche le preferenze dei clienti con profili simili, favorendo la conoscenza di nuovi prodotti che potrebbero risultare interessanti.

Flixster

Flixster è un social network, creato da Joe Greenstein e Saran Chari nel 2005, che permette agli utenti di condividere valutazioni sui film, scoprirne di nuovi, e incontrare persone con i gusti simili ai propri.

Il sistema di raccomandazioni di cui si avvale Flixster si basa sulla somiglianza tra i film. Se un film A, secondo il parere degli utenti, ha una trama simile ad un film B, è l’utente X ha valutato positivamente il film A, allora il RS suggerirà B a X.

Se X trova interessante B può decidere di vederlo e poi valutarlo, oppure inserirlo nella lista dei film da vedere e valutarlo in un secondo momento. Qualunque sia l’azione intrapresa da X, essa sarà registrata dal sistema e influenzerà i suggerimenti successivi.

Last.fm

Last.fm è un sito di musica, che propone ai propri utenti consigli personalizzati riguardo canzoni che rispecchiano i loro gusti.

Si avvale di un music recommender system chiamato Audioscrobbler, grazie al quale è possibile ricostruire un dettagliato profilo dei gusti di ciascun utente.
A supporto di tale funzione è possibile scaricare un software, lo Scrobbler, che memorizza le canzoni ascoltate tramite i propri lettori musicali, come Windows Media Player, iTunes, Winamp, e molti altri ancora.

Lo Scrobbler invia a Last.fm dei messaggi, i cosiddetti scrobbling, per segnalare il brano che l’utente sta ascoltando.
In tal modo vengono memorizzati i brani che l’utente ascolta più spesso, il numero di volte che ha ascoltato canzoni di un certo artista, gli amici che hanno gusti simili al suo e così via.
Analizzando la musica ascoltata, il RS di Last.fm aiuta l’utente a scoprire nuove canzoni e artisti, coerenti ai suoi gusti, attraverso consigli personalizzati.


Content-based RS [Mazzotta Simone]

I sistemi Content Base, basati sul contesto, suggeriscono articoli e prodotti basandusi sul contenuto degli stessi piuttosto che sulle quotazioni (rating) degli altri utenti. Questi sistemi si compongono di quattro passi esssenziali:

  1. Raccolgono i dati del contenuto dei varti articoli. La maggior parte dei sistemi usano tecniche di estrazione dell'informazione per estrarre questi dati e tecniche di Retrieval per recuperare in informazioni interessanti;
  1. Chiedono all'utente di fornire alcune quotazioni (rating). In questa fase, all'utente, potrebbe venire chiesto di quotare degli articoli o prodotti casuali, oppure di cercare per esempio libri di suo gradimento;
  1. Successivamente si compila il profilo dell'utente utilizzando le informazioni sul contesto estratte al primo passo e le informazioni di rating fornite nel passo precedente. Per apprendere un profilo, possono essere utilizzate tecniche di information retrieval o di machine learning;
  1. L'ultimo passo è quello di fare un match del contenuto, ad esempio, dei libri non quotati con i profili utente compilati nel terzo passo ed assegnando degli score agli articoli in base alla qualità del match. Gli articoli o prodotti vengono poi ordinati in base al loro score e presentati all'utente in ordine.


Fonti:
spagoworld.org Tesi che tratta della progettazione di un Service Recommender System basato su Intelligenza Collettiva, capitolo 3, pagina 27;
unisi.it Tesi sullo studio e rappresentazione di algoritmi, capitolo 2, pagina 3.

Per maggiori informazioni: wikipedia.org/Recommender system

Algoritmi e metodi per i Recommender System tradizionali [Stefano Manicone]

In questa sezione vengono presentati alcuni approcci presenti in letteratura per determinare la similarità tra item e la similarità tra user, selezionare i vicini e generare i suggerimenti.

Calcolo della similarità tra item [Stefano Manicone]

Nell’approccio Content Based, è fondamentale trovare una misura di similarità affidabile che permetta di confrontare gli item. In generale, si assume di avere una matrice R dove ad ogni colonna corrisponde un oggetto e ad ogni riga un utente. Consideriamo due item, ti e tk, l’obiettivo è valutare la loro somiglianza. A tale scopo si possono utilizzare due metriche: la correlazione di Pearson, oppure il Coseno. Correlazione di Pearson: supponiamo che {u1,...,uL} siano il sottoinsieme di utenti che hanno valutato sia l’item ti che tk. Indichiamo con rij l’elemento di riga i e colonna j della matrice R, cioè la valutazione che l’utente ui ha dato per l’item tj, e con ri la valutazione media che gli utenti {u1,...,uL} hanno dato dell’item ti. Allora definiamo la similarità di ti e tk come:

Coseno: sia R la matrice mxn utenti-item. Allora la similarità tra due item i e j, è definita come il coseno dell’angolo formato dai vettori a n dimensioni corrispondenti alla i-esima e alla j-esima colonna della matrice R.

Per capire meglio con un esempio semplificato, sia i = A = (x1, y1) e j = B = (x2, y2), allora:


Calcolo della similarità tra user [Stefano Manicone]

Nell’approccio Collaborative Filtering, un elemento essenziale è dato dalla generazione dei vicini (neighbor) di un utente. In generale, si assume di avere una matrice R dove ad ogni colonna corrisponde un oggetto e ad ogni riga un utente. Consideriamo due utenti, ui e uk, l’obiettivo è determinare quanto si assomigliano. A tale scopo si possono utilizzare due metriche: la correlazione di Pearson, oppure il Coseno [40]. Correlazione di Pearson: supponiamo che {i1,...,iL} siano il sottoinsieme di item valutati sia da ui che da uk. Indichiamo con rij l’elemento di riga i e colonna j della matrice R, cioè la valutazione che l’utente ui ha dato per l’item j, e con ri la valutazione media che i ha fatto sugli item {i1,...,iL}. Allora definiamo la similarità di ui e uk come:

Coseno: se consideriamo un utente come un vettore nello spazio N-dimensionale (N è il numero di item totali), dove ogni elemento xt del vettore corrisponde alla valutazione che l’utente ha fornito per l’item t, allora si può calcolare la similarità tra utenti come l’angolo compreso tra i due vettori che li rappresentano. Si noti che per gli item non valutati, il corrispondente elemento nel vettore vale 0. Indichiamo con rij l’elemento j-esimo del vettore associato all’utente ui e con ri il valore medio degli elementi del vettore. Definiamo la similarità di ui e uk come:


Selezione dei vicini [Stefano Manicone]

Calcolando la similarità tra tutti gli utenti, indipendentemente dal metodo specifico, si ottiene una matrice simmetrica S di dimensione M xM (dove M è il numero di utenti nel sistema). Il generico elemento sik di tale matrice corrisponde alla similarità tra l’utente ui e l’utente uk. Ovviamente sik = ski. Inoltre, sulla diagonale c’è la misura di similarità di ogni utente con se stesso e non è utile tenerla in considerazione. Consideriamo, ora, l’utente per cui vogliamo generare un insieme di suggerimenti, e lo chiamiamo utente attivo (ua). Dobbiamo quindi selezionare un insieme di user che costituiscano il suo “vicinato” (neighborhood), cioè il gruppo di utenti a lui simili. Per tale scopo ci sono varie possibilità, e qui ne presentiamo due: centerd-based e per aggregazione. Center-Based: è la soluzione più semplice. Sulla matrice S si considera la riga corrispondente all’utente ua e si scelgono gli L valori più alti. Gli utenti corrispondenti a tali valori formano la neighborhood dell’utente attivo. Per aggregazione: richiede un procedimento più complesso. Al primo passo si prende l’utente che ha valore di similarità più alto in relazione all’utente attivo ua. Questo utente, insieme a ua, costituiscono la neighborhood corrente NC. In totale i vicini di ua da individuare sono L. Gli L -1 utenti successivi vengono selezionati applicando un algoritmo iterativo.

L’algoritmo iterativo [Stefano Manicone]

Supponiamo che al h-esimo passo di questo algoritmo abbiamo una neighborhood corrente formata da h utenti, più l’utente attivo. Viene calcolato un centroide di questi h+1 utenti secondo la formula:

Si noti che il centroide è un vettore di N componenti come i vettori utente, e quindi confrontabile con essi. La somma di due vettori utente uj e uk viene fatta componente a componente. Sia Z = U – NC l’insieme degli utenti che non fanno parte della neighborhood corrente. Tra gli elementi di Z, viene selezionato quello più simile al centroide, e viene aggiunto a NC (ed eliminato da Z). A questo punto la neighborhood corrente è formato da h+1 elementi, oltre all’utente attivo. Se h+2 =L l’algoritmo è terminato, altrimenti si passa all’iterazione successiva.

Generazione dei suggerimenti [Stefano Manicone]

Il recommendation problem richiede di associare ad un item i un valore r che l’utente non ha ancora espresso esplicitamente. A tale scopo si possono adottare più tecniche [40][41][42]: neighborhood based, fattorizzazione della matrice user-item, somma pesata, media pesata, association rules based. Neighborhood based: per stimare R*(u,i), cioè il rating che l’utente u dovrebbe assegnare all’item i bisogna innanzitutto calcolare la similarità tra l’utente u e gli altri utenti u’, ad esempio utilizzando il coseno:

dove I(u,u’) indica l’insieme di tutti gli item valutati sia dall’utente u che da u’, e R(u,i) indica il rating effettivo dell’utente u riguardo all’item i. Basandosi sulle similarità tra utenti calcolate, si determina l’insieme N(u) dei neighbor di u più vicini. La taglia dell’insieme N(u) può essere compresa tra 1 e |U| – 1. Il valore di R*(u,i) è calcolato come la somma pesata di tutti i rating conosciuti R(u’, i) degli utenti u’ ε N(u) secondo la seguente formula:

Fattorizzazione della matrice user-item [Stefano Manicone]

Si parte dall’assunzione che il rating di un utente per un certo item è composto dalla somma dei voti riguardo le varie feature di quell’item. Usando K feature, l’utente u è associato a un vettore pu (dove gli elementi sono le preferenze dell’utente u per le K feature) e l’item i è associato a un vettore qi, (dove gli elementi sono i pesi dell’importanza di ciascuna feature dell’item i). La previsione di quanto un item i possa piacere all’utente u, indicata con R*(u,i) è data dal prodotto interno dei due vettori.

dove il pallino scuro indica il prodotto interno. Tutti i valori degli elementi dei vettori utente e dei vettori item sono inizialmente posti a un numero arbitrario. Successivamente vengono aggiornati, variando il valore dei parametri θ e λ. L’aggiornamento viene fatto tramite un algoritmo di apprendimento, con l’obiettivo di minimizzare una certa funzione di merito. Una possibilità è la seguente :

Infine, utilizzando i valori ottenuti di pu e qi , si calcola il prodotto interno dei due vettori ottenendo R*(u,i).

Somma pesata [Stefano Manicone]

Per fare una predizione del gradimento di un utente attivo a riguardo un item i, possiamo prendere la media pesata di tutti i rating riguardanti quel determinato item (ru,i ), in accordo con la seguente formula.

dove ra e ru sono i rating medi, rispettivamente, per l’utente a e l’utente u di tutti gli altri item e wa,u è il peso (similarità) tra l’utente a e l’utente u. La sommatoria è su tutti gli utenti u di U che hanno valutato l’item i.

Media pesata [Stefano Manicone]

Per le predizioni item-based, si può utilizzare una media pesata per calcolare il rating dell’item i non ancora valutato da u:

dove le sommatorie sono su tutti gli oggetti n ε N valutati dall’utente u, wi,n è il peso (la similarità) tra gli oggetti i e n, e ru,n è il rating dell’utente u per l’oggetto n.

Association rules based [Stefano Manicone]

Supponiamo di avere n item, I = {i1, i2,...,in}, nella matrice R iniziale user-item. Una transazione T ⊆ I è definita come un insieme di item che sono stati valutati o acquistati insieme. Una regola associativa (association rule) tra due insiemi di item, IX e IY, tali che IX,IY⊆I e IX∩IY = Ø, stabilisce che se gli item dell’insieme IX sono presenti nella transazione T, allora c’è un’alta probabilità che gli item dell’insieme IY siano presenti in T. Una simile regola associativa viene indicata con IX => IY.


Metriche di valutazione dei Recommender System [Marco Carisio]

Si distinguono due tipi di metriche per valutare un Recommender System: le misure per valutare la qualità e le misure per valutare le performance. Le prime analizzano i suggerimenti, le seconde il RS come sistema.
Tra le misure per valutare la qualità dei suggerimenti di un RS possiamo distinguere l’accuratezza, e la copertura:

− Mean Absolute Error (MAE): uno dei metori per determinare l’accuratezza (o viceversa, l’errore di classificazione), è il Mean Absolute Error, che calcola la media della differenza
assoluta tra i rating previsti dal RS e la valutazione che successivamente l’utente esprime.
Schermata 02-2455965 alle 14.08.37.png
dove n è il numero totale di rating di tutti gli utenti, pi,j è il rating previsto per l’utente i sull’item j, e ri,j è il rating effettivo. Più basso è il valore del MAE e migliore è la predizione del rating. A volte è utile normalizzare tale valore rispetto alla scala utilizzata nel RS specifico, in modo da poter poi comparare sistemi che utilizzano rating minimo (rmin) e massimo (rmax)diversi. In tal caso si calcola la Normalized MAE (NMAE):
Schermata 02-2455965 alle 14.08.43.png
− Root Mean Squared Error (RMSE): è la metrica prescelta per stimare la qualità dei RS nell’ambito del Netflix Prize.
Schermata 02-2455965 alle 14.08.49.png
dove n è il numero totale di rating su tutti gli user, pi,j è il rating previsto per l’utente i sull’item j e ri,j è il rating effettivo.


− ROC sensivity: è una misura della potenza di previsione di un RS. Operazionalmente è data dalla Area Under the ROC Curve (AUC), letteralmente l’area sotto la curva ROC.
In realtà il valore di AUC è quello dell’area sotto la curva ROC soltanto se la previsione è un problema con due possibili esiti (problema binario). In generale la ROC sensivity si
calcola con la seguente formula:
Schermata 02-2455965 alle 14.08.56.png
dove n0 e n1 sono rispettivamente il numero di previsioni sbagliate e di previsioni corrette, e S0 = ∑ ri, dove ri è il rank dell’i-esima previsione positiva nella lista delle previsioni, ordinata per precisione.







Whos here now:   Members 0   Guests 0   Bots & Crawlers 1
 
Strumenti personali
Namespace
Varianti
Azioni
Forum Menu
Wikibook
Autori
Istruzioni
Widget e Social Media
Strumenti
Modifiche