Recommendation Systems For Personal Video Recording

Università degli Studi Torino Facoltà di Scienze Matematiche, Fisiche e Naturali Corso di Laurea in Informatica Anno Accademico 2007 - 2008

Relazione di Tirocinio Sistemi di recommendation per personal video recording

Supervisore Prof. Giancarlo Ruffo

Candidato Matteo Bovetti

Alla mia famiglia. A Anto.

Indice 1. SISTEMI DI RECOMMENDATION................................................................................4 1.1 Che cosa sono e a cosa servono?.................................................................................4 1.2 L'approccio Collaborative Filtering.............................................................................6 1.2.1 Introduzione.........................................................................................................6 1.2.2 Utilizzi del Collaborative Filtering......................................................................8 1.2.3 Confronto tra Collaborative Filtering e Content-Based Filtering......................12 1.2.4 L'approccio neighborhood-based......................................................................14 1.2.5 Valutazioni.........................................................................................................16 2. L'APPLICAZIONE RD-PVR..........................................................................................19 2.1 Il servizio V-Cast.......................................................................................................19 2.2 RD-PVR e Facebook.................................................................................................21 2.3 Algoritmo di Recommendation per RD-PVR............................................................24 2.4 Collaborative Filtering in RD-PVR...........................................................................26 2.4.1 Calcolo degli insiemi usr-affini e el-affini.........................................................26 2.5 Il calcolo del weight..................................................................................................27 2.6 Implementazione in PHP5.........................................................................................28 3. TEST E VALUTAZIONI..................................................................................................34 3.1 Test condotti sui dump di V-Cast...............................................................................34 3.2 Risultati e conclusioni...............................................................................................37 4. CODICE CORRELATO...................................................................................................41 Ringraziamenti.....................................................................................................................45 Bibliografia...........................................................................................................................46

1. SISTEMI DI RECOMMENDATION 1.1 Che cosa sono e a cosa servono? I sistemi di recommendation sono uno specifico tipo di information filtering (IF). Essi vengono utilizzati per presentare oggetti (film, musica, libri, news, immagini, web pages, ecc..) che possono interessare l'utente. Tipicamente, un sistema di recommendation compara il profilo utente con caratteristiche di riferimento, e cerca di prevedere il rating che l'utente ha con un oggetto che non ha ancora considerato. Queste caratteristiche possono provenire dalle informazioni degli oggetti (approccio Content-Based) oppure da un ambiente sociale di utenti (approccio Collaborative Filtering). Quando viene costruito il profilo utente, la distinzione viene fatta tra collezioni di dati espliciti ed impliciti.

Esempi di collezioni di dati espliciti: •

Chiedere ad un utente di votare un oggetto in base ad una scala.

•

Chiedere ad un utente di classificare una collezione di oggetti dal più gradito al meno gradito.

•

Presentare due oggetti ad un utente e chiedergli quale sceglierebbe come migliore.

•

Chiedere ad un utente di creare una lista degli oggetti che preferisce.

Esempi di collezioni di dati impliciti: •

Osservare gli oggetti che un utente vede e usa.

•

Analizzare il tempo di visualizzazione di un oggetto.

•

Tenere un registro di oggetti che un utente acquista online.

•

Ottenere una lista degli oggetti che l'utente ha ascoltato o guardato sul suo computer.

•

Analizzare la rete sociale dell'utente e scoprirne similarità di gusto con altri utenti.

Il sistema di recommendation confronta i dati collezionati dall'utente con i dati collezionati da altri, e calcola una lista di oggetti raccomandati per il primo. I sistemi di recommendation sono una importante alternativa agli algoritmi di ricerca, perché aiutano gli utenti a ricercare oggetti che non troverebbero da soli.

1.2 L'approccio Collaborative Filtering 1.2.1 Introduzione Il collaborative filtering è un processo di filtraggio o di valutazione di oggetti che utilizza informazioni e opinioni di altri utenti [1]. In questi anni, quasi inconsapevolmente, si è utilizzato una forma di collaborative filtering che veniva attuato dalle persone ad esempio quando tra conoscenti si discute su un libro letto o su un film visto al cinema. Questo tipo di confronto mette in moto un meccanismo che è una sorta di recommendation. Esso ci permette di conoscere libri, film e ristoranti che i nostri conoscenti hanno provato e che in qualche modo, durante la conversazione, ci hanno consigliato o meglio raccomandato. I sistemi di recommendation, in particolare l'approccio Collaborative Filtering, ci permettono di ottenere consigli e valutare preferenze partendo proprio dalle esperienze degli utenti vicini a noi (amici). Di seguito viene riportato [1] l'esempio MovieLents;

questo portale di recensione di film utilizza il collaborative filtering per fornire una predizione sui film che all'utente potrebbero interessare.

Come mostra la figura il sistema MovieLens offre una lista predittiva su quali film è consigliato vedere. Gli utenti, che hanno visto alcuni film e vogliono fornire un feedback diretto sul gradimento della pellicola, lo possono fare utilizzando il sistema da uno a cinque stelle che permette di esprimere un voto. Le stelle vengono valutate dal sistema MovieLens in questo modo:

Il calcolo del rating può essere rappresentato da una matrice, utente e oggetto, che associa un valore di affinità tra gli oggetti (film) e gli utenti per cui deve essere calcolata la predizione. Di seguito viene riportato un esempio di matrice dove, sulle righe abbiamo gli utenti, e sulle colonne i film. Ogni cella indica il rating di quel film con l'utente specificato.

The Matrix

Speed

Sideways

Brokeback Mountain

Amy

1

Matt

2

5

3

5

4

Paul

5

5

2

1

Cliff

5

5

5

5

La matrice è solo uno dei modi che si hanno per rappresentare e per dare una predizione. Esistono diversi modi per fornire un feedback utile per la predizione di un oggetto: •

Il metodo utilizzato da MovieLens, che utilizza le stelle da uno a cinque per indicare un gradimento che va da Awful a Must See.

•

Un rating binario, che indica se l'oggetto è piaciuto oppure no o se è buono o non buono.

•

Un rating unario, che indica se un utente ha osservato un oggetto, se l'ha acquistato o se semplicemente ha valutato esso positivamente.

Come spiegato nel paragrafo precedente esistono due modi per esprimere un feedback, esplicito o implicito. Il primo modo, indica una volontaria intenzione dell'utente di dare un giudizio su un oggetto del sistema. Questo tipo di dato deriva da un comportamento intenzionale che l'utente ha verso il sistema. Il secondo modo, viene inferito automaticamente da un comportamento o da una azione sul sistema tenuta dall'utente. Ad esempio se un utente visita una pagina contenente un prodotto, oppure acquista il prodotto stesso, è possibile banalmente dedurre che l'oggetto interessi all'utente. Questa inferenza permette di presentare oggetti (prodotti) affini e quindi mantenere l'utente sul sistema.

1.2.2 Utilizzi del Collaborative Filtering Gli utilizzi che vengono fatti dei sistemi collaborative filtering sono molti. Di seguito vengono presentati i più comuni legati a cosa un utente può ottenere dal un sistema di recommendation. 1. Innanzi tutto il collaborative filtering viene utilizzato per ricercare nuovi oggetti che potrebbero piacere all'utente. In contesti molto grandi, non è possibile che l'utente ricerchi manualmente tutti gli oggetti che gli possano interessare. Lo scopo principale di questi sistemi è proprio di ricercare oggetti e presentarli all'utente in

modo che possa ricercare cosa gli interessa in un insieme ristretto. 2. Quando un utente conosce un particolare oggetto spesso vorrebbe sapere se la rete sociale o community ha espresso un giudizio, buono o non buono, su quell'oggetto; o a sua volta esprimerlo lui stesso. 3. Un altro importante utilizzo che si può fare del collaborative filtering è quello di aiutare l'utente a ricercare altri utenti affini a lui. Questo meccanismo permette di costruire gruppi di utenti con affinità di gusti, oppure connettere utenti per permettere un tipo di raccomandazione sociale. 4. Come indicato dal punto 1, il sistema può eseguire lo stesso compito con un gruppo di utenti. Definito un gruppo di utenti affini, ad esempio un gruppo di ricerca, è possibile sfruttare le funzionalità del sistema per ricercare una pubblicazione utile a tutti i membri del gruppo. 5. Il sistema mette a disposizione anche ricerche parametrizzate come ad esempio la possibilità, da parte di un utente, di cercare tutte le pubblicazioni che lo citano. Questi cinque punti descrivono quello che un utente, che utilizza il sistema, può ottenere. Ora viene spostata l'attenzione sul sistema vero e proprio. In particolare sulle funzionalità che i sistemi collaborative filtering offrono. 1. Recommendation di oggetti. Questa è la funzionalità cardine del sistema. Essa permette di offrire all'utente una lista di elementi che, secondo le valutazioni dell'algoritmo, possono essere utili e apprezzate dall'utente. Il calcolo viene fatto creando un rating associato a ogni oggetto da raccomandare. Il sistema ordina secondo il valore del rating gli oggetti, e li presenta in questo ordine all'utente. Ad esempio l'algoritmo di recommendation di Amazon.com, aggrega oggetti simili a quelli acquistati dall'utente; invece di visualizzare una predizione personalizzata, le interfacce utenti visualizzano la media dei rating del cliente. Come risultato, la lista di recommendation potrebbe apparire in disordine rispetto alla media dei valori visualizzati. In molte applicazioni prendere i pochi oggetti al top (oggetti che sono fortemente raccomandati dall'algoritmo) è cruciale. 2. Calcolo della predizione di un dato oggetto. Questo tipo di calcolo viene fatto dal sistema per indicare un sottoinsieme di possibili elementi candidati alla recommendation. Esso è fondamentale per fornire un valore di affinità tra l'oggetto, a cui è associato il rating, e l'utente per cui si sta svolgendo la predizione. Molti di questi algoritmi hanno la caratteristica di essere altamente scalabili e di avere un

basso uso di memoria e di tempo di computazione. 3. Constrained recommendation. Questo tipo di calcolo viene eseguito su un set di oggetti. Esso utilizza sorgenti multiple per la recommendation. L'utente definisce alcune preferenze, che vengono utilizzate dall'algoritmo per restringere il set degli oggetti candidati. La recommendation basa il suo rating eseguendo un match tra le preferenze dell'utente e quelle candidate alla recommendation. Viene riportato un esempio, SQL-Like, su una recommendation di film: “RECOMMEND Movie TO User BASED ON Rating FROM MovieRecommender WHERE Movie.Length < 120 AND Movie.Rating < 3 AND User.City = Movie.Location”

Proprietà dei domini per il Collaborative Filtering (CF). Il CF è noto per essere effettivo in domini che presentano determinate proprietà. Bisogna valutare quali sono le proprietà che le applicazioni utente considerano maggiormente. Raggruppiamo queste proprietà in: •

Data distribution

•

Underlying mining

•

Data persistence

Data distribution. Le proprietà elencate di seguito riguardano il numero e la forma dei dati. 1. Avere all'interno del sistema una grande quantità di oggetti. Se la quantità di oggetti considerabili è bassa, l'utente può esplorarli e conoscerli tutti senza avere bisogno del supporto del sistema. 2. Avere un gran numero di ratings per oggetto. Se la quantità di ratings per oggetto è bassa non ci sono abbastanza informazioni per fare delle predizioni o recommendation utili. 3. Avere un grande numero di ratings utente, ma pochi oggetti utili alla recommendation. Spesso si ha necessità di avere più utenti rispetto al numero degli oggetti che il sistema sarà in grado di raccomandare. Più precisamente se ci sono pochi rating per ogni utente il sistema avrà bisogno di molti utenti. Molti sistemi hanno proprio questa proprietà. Esempio: Google, popolare motore di ricerca, indicizza al momento attuale otto miliardi di pagine. Questo numero è molto

maggiore di tutta la popolazione globale, e molto maggiore delle persone che hanno un pc. Un altro esempio, avendo un milione di utenti, un sistema CF sarà i grado di fare raccomandazioni per cento mila oggetti. Ma sarà in grado di fare predizioni precise per circa dieci mila utenti, a seconda della distribuzione dei ratings tra oggetti. Pochi oggetti ottengono molti ratings, mentre una grande quantità di oggetti ottiene pochi ratings. Calcolare una predizione su una grande quantità di oggetti non è sempre un compito semplice. 4. Gli utenti forniscono una valutazione a molti oggetti. Se un utente da un ratings a un singolo oggetto, questo provvede a fornire informazioni statistiche, ma non dà informazioni per relazionare gli oggetti tra loro. Underlying mining. 1. Per ogni utente del sistema ci sono altri utenti con necessità o gusti in comune. CF lavora perché le persone hanno necessità e gusti in comune. Se una persona ha gusti così unici da non averne in comune con nessun altro, allora il CF non può fare nessuna valutazione (fallisce). In generale CF lavora bene quando ogni utente può trovare molti altri utenti che condividono i suoi gusti in molte categorie. 2. La valutazione degli oggetti richiede gusti personali. Nei casi in cui ci sono criteri oggettivi di bontà che possono essere computati automaticamente, questi criteri possono essere meglio applicati a altri contesti piuttosto che al CF (ad esempio gli algoritmi di ricerca). Il CF permette agli utenti con gusti simili di informare se stessi sull'esistenza di oggetti che potrebbero interessare. Il CF aggiunge valori sostanziali quando le valutazioni di oggetti sono in buona parte soggettivi (musica) o quando questi oggetti hanno molti criteri oggettivi differenti che necessitano di essere pesati soggettivamente gli uni con gli altri (ad esempio le auto). Alcune volte esistono criteri oggettivi che possono aiutare il lavoro dell'algoritmo (es. raccomandare solo libri scritti in inglese). Se la recommendation può essere fatta utilizzando criteri oggettivi, il CF non è utile. 3. Gli oggetti sono omogenei. L'omogeneità è data dai criteri oggettivi che sono simili tra tutti gli oggetti presenti nel sistema. La differenziazione è fatta solo sui criteri soggettivi. Gli album musicali appartengono a questa categoria, molti sono simili da comprare e simili in lunghezza. Un altro tipo di oggetto che presenta questa proprietà sono i libri o le pubblicazioni di ricerca. Data persistence. Le proprietà elencate di seguito trattano la rilevanza dei dati nel CF.

1. Persistenza degli oggetti. Un sistema CF non solo necessita che un singolo oggetto sia classificato da molte persone, ma richiede inoltre che le persone condividano molti oggetti precedentemente classificati. Consideriamo il dominio di notizie (news). Molte notizie appaiono per giorni, altre probabilmente sono solo interessati per poco tempo. Per un sistema collaborative filtering generare una predizione riguardante una notizia apparsa recentemente, richiede che siano vere due precondizioni: A) Uno o più utenti hanno classificato la notizia. B) Questi utenti hanno inoltre classificato alcune altre notizie che io ho anche classificato. In un dominio come quello delle notizie, per essere classificate da un largo numero di persone, esse sono molto più interessanti quando sono appena uscite e di cronaca nera. Se queste notizie sono solo importanti per un breve periodo questa richiesta è difficile da incontrare. 2. Persistenza dei gusti. Il CF ha il maggior successo in domini dove i gusti degli utenti non cambiano rapidamente: film, libri ed elettronica. Se i gusti cambiano frequentemente o rapidamente, allora le vecchie classificazioni, generate dal sistema, sono poco utili. Un esempio di persistenza dei gusti potrebbe essere il vestiario, dove il gusti delle persone per cinque anni e più non cambia. Le proprietà elencate nei punti precedenti rappresentano semplificazioni del mondo dove il CF è più facilmente applicabile. Infatti, applicando il CF in domini dove queste proprietà non sono presenti permettono di aprire interessanti applicazioni e aree di ricerca. Per esempio si potrebbe applicare il collaborative filtering a oggetti non omogenei, attraverso l'uso di raccomandazioni forzate o applicando vincoli esterni (chiamate regole di bussines).

1.2.3 Confronto tra Collaborative Filtering e Content-Based Filtering Il collaborative filtering (CF) utilizza delle assunzioni su utenti (affini) per creare una lista di oggetti pronti per la recommendation. Su questi oggetti l'algoritmo crea un rating che indica l'affinità dell'oggetto con l'utente. L'approccio content-based filtering (CBF) utilizza delle assunzioni su oggetti che reputa affini all'utente o di suo gradimento. Un esempio chiarificatore è il seguente: se viene creato un collegamento a una pagina

contenente “tomato sauce”, l'approccio content-base filtering consiglierà un'altra pagina con “tomato sauce”. Questa è la prima importante distinzione tra questi due tipi di approcci. L'approccio content-based filtering può fare predizioni senza costruire un rating associato agli oggetti che raccomanda. Questo non avviene nel collaborative filtering dove è necessario costruire un rating. Un'altra importante differenza è data dal fatto che è possibile, utilizzando il collaborative filtering, ottenere oggetti per la recommendation senza che l'utente abbia mai utilizzato alcun oggetto all'interno del sistema. Questo approccio permette di raccomandare liste di elementi anche se non si è mai utilizzato il sistema. Se invece viene utilizzato l'approccio content-based non è possibile calcolare alcune lista di oggetti, se l'utente non ne ha già utilizzati sino a quel momento. Un ulteriore caratteristica del collaborative filtering, è data dal fatto che gli oggetti esaminati dall'algoritmo sono spesso manipolati dall'utente, il quale fornisce una valutazione all'oggetto stesso. Valutare l'oggetto, permette all'algoritmo di avere a disposizione ulteriori informazioni per analizzare in modo preciso gli elementi da raccomandare. Fornendo un maggior numero di informazioni è possibile aumentare la precisione sulle valutazioni fatte dall'algoritmo. Il lavoro svolto da un algoritmo content-based filtering si avvale della caratteristiche di un oggetto e le confronta con interessi, gusti e profili utente. Per molto tempo collaborative filtering e content-based filtering sono stati visti come complementari. Infatti molto spesso collaborative filtering e il content-based filtering vengono combinati formando quello che è chiamato approccio ibrido. Alcuni sistema utilizzano un approccio basato sull'analisi dei contenuti per identificare caratteristiche relative alle immediate necessità degli utenti. Gli stessi sistemi utilizzano il collaborative filtering per provare a catturare caratteristiche come la qualità degli oggetti; caratteristiche difficili da analizzare automaticamente. Per approfondire ulteriormente il rapporto che c'è tra oggetti utilizzati in un approccio content-based e collaborative filtering, viene ora presentata una tabella [9] riassuntiva che permette di vedere quali oggetti utilizzano i vari approcci. Questa tabella è importante anche per vedere l'evoluzione dei sistemi di raccomandazione partendo proprio dall'information retrieval.

Concept

Modeling Matrix

Information Retrieval

terms x documents

Information Filtering

features x documents

Content-based Filtering

features x artifacts

Collaborative Filtering

people x documents

Recommender System

people x artifacts

1.2.4 L'approccio neighborhood-based

L'approccio neighborhood-based è la trasposizione di user-based algorithms. Mentre user-based algorithms genera una predizione basata sulla similarità tra due utenti, l'approccio neighborhood-based genera una predizione basata sulla similarità tra due oggetti. La predizione per un oggetto viene basata sul ratings utente similmente agli oggetti che gli possono interessare. Considerando la seguente tabella: The Matrix

Speed

Sideways

Brokeback Mountain

User 1

5

4

3

User 2

4

5

5

User 3

3

X

4

User 4

5

3

3

3 4

Si vuole calcolare una predizione per l'oggetto “Speed” per l'utente 3 (Segnata con X). Osserviamo i ratings per l'oggetto “Speed”, si nota che il ratings sono simili a quelli di “Sideways” ma non simili a quelli si “The Matrix”. Cerchiamo di predire il rating X costruendo una media pesata su gli altri ratings dell'utente 3 (3 per “The Matrix” e 4 per

“Sideways”). Visto che “Speed” è simile a “Sideways”, consideriamo il rating dato a “Sideways” molto più rilevante rispetto a quello dato a “The Matrix”. Calcoliamo quindi la predizione eseguendo questo semplice calcolo: X = 0.25 * 3 + 0.75 * 4 = 3.75. Di seguito viene riportata l'equazione formalizzata per il calcolo della predizione per un rating utente u che ha similarità con un oggetto i.

pred(u,i) > Σj є rateditems(u)itemSim(i,j) * rui / Σj є rateditems(u)itemSim(i,j) La funzione itemSim() indica la misura di similarità dell'oggetto, e rui indica il rating dell'oggetto i associato all'utente u. Di seguito viene riportato un altro esempio, più dettagliato, di applicazione dell'algoritmo. user/ 1 items 1

2

3

1

4 3

2 2

6

1

3

4

3

11

2

1

3

5

3

2

2

2

3

12

4

4

4

3

10 5

5

4

9

5

2

4

5

8

4

1

2

7

4

4

4

6 ?

5

3

5

2

5

4

Le celle bianche non contengono un rating, mentre le celle gialle hanno specificato al loro interno il valore di rating per quell'oggetto-utente. In rosso viene indicato il rating che si vuole calcolare per l'oggetto 1 e l'utente 5. Procediamo con la selezione degli oggetti vicini (Neighbor selection). Come mostrato di seguito l'algoritmo seleziona gli oggetti 3 e 6, perché vicini ai gusti dell'utente. user/ 1 items 1

2

3

1

5 2

4 6

4 2

5

7

9

2 4 3

10 5

4

4

3

5 3

8

5

4

4 3

6 ?

1 4

1

5

3

2 3

4

4 2

11 4

2

1

3

5

3

2 2

2

12

4

5

Come indicato dalla equazione per il calcolo della predizione pred(u,i) viene calcolata una media pesata dei valori selezionati dall'algoritmo: (0.2 * 2 + 0.3 * 3 ) / (0.2 + 0.3) = 2.6 user/ 1 items 1

2

3

1

4 3

2

5

3

2

4

4 2

5 1

7

8

4 2 4

10

11

5 4

3

5 3

9

5

4

4 3

6 2,6

1 4

6

5

4 2

1

3

5

4 2

3

12

2 2

2

3

5

4

Il risultato del calcolo viene inserito nella cella relativa e quindi la predizione è stata calcolata. Infine vengono presentate le proprietà che caratterizzano questo approccio: Le proprietà dell'approccio neighborhood-based CF sono: •

Intuitivo

•

Rende semplice spiegare le ragioni che portano a una raccomandazione

•

Operare senza discontinuità nuovi ratings / users

1.2.5 Valutazioni In questa sezione viene discussa l'accuratezza, che è generalmente considerata il più importante criterio per valutare i risultati di un sistema collaborative filtering. Brevemente vengono presentati altri criteri per verificare e valutare il collaborative filtering. Accuratezza (Accuracy). Un metodo molto promettente per valutare un sistema collaborative filtering è l'accuratezza del sistema di predizione. L' accuratezza può essere misurata dall'errore che occorre tra la predizione del ranking e il “vero” ranking. La accuratezza della predizione (Predictive accurancy) è l'abilità che ha il collaborative filtering di predire il rating di un utente per un oggetto. Il metodo standard per calcolare la accuratezza della predizione è mean adsolute error (MAE). Esso è la media assoluta della differenza tra il rating predetto e il rating attuale associato all'utente. I vantaggi che si hanno nell'utilizzare il MAE sono la sua semplicità, la sua chiarezza, ed è possibile applicare ed eseguire test significativi su di esso. Inoltre, MAE sembra che intuitivamente catturi la qualità dei sistemi CF. I costruttori di sistemi di recommendation vogliono che le predizioni siano il più possibile vicine al vero rating.

Il metodo MAE è provato essere poco affidabile su una lista di recommendation classificata dall'algoritmo. Questo nasce dal seguente problema: gli utenti percepiscono maggiormente errori che sono all'inizio della lista di recommendation rispetto a errori simili posizionati al fondo della lista. MAE non differenzia tra errori all'inizio e errori alla fine delle liste. Il rank accuracy metric tenta di calcolare l'utilità di una lista di oggetti da raccomandare a un utente. Rank accuracy metrics include la precisione e half-life utility. La precisione è la percentuale degli oggetti presenti nella lista da raccomandare che l'utente considera utili. Nel collaborative filtering è spesso calcolato in vari punti della lista. Half-life utility calcola il valore per una ranked list, inteso come la percentuale dell'utilità massima raggiunta dalla lista. L'utilità massima è raggiunta quando tutti gli oggetti utili alla recommendation, per cui è stato calcolato un rating, appaiono sopra tutti gli oggetti che non sono utili. Lo scopo è comprendere se tutti gli oggetti classificati come utili appaiono sopra tutti gli oggetti classificati come non utili. In una scala di utilità errori all'inizio della lista classificata possono essere esponenzialmente maggiori rispetto agli errori nella parte terminale della lista. Se l'interfaccia utente, che utilizza il collaborative filtering, prima prevede la lista classificata dei migliori oggetti raccomandati, allora l'accuratezza del sistema viene valutata utilizzando il metodo del rank accuracy metric. Se il sistema visualizza direttamente le predizioni all'utente, allora è importante valutare l'accuratezza del sistema con il metodo Accuracy. In ogni caso, ha senso utilizzare entrambe gli approcci. Oltre l'accuratezza. Di seguito vengono presentate altre tecniche per valutare la bontà del sistema collaborative filtering. Novelty è l'abilità del sistema CF di raccomandare oggetti di cui gli utenti non erano a conoscenza. Un'idea più forte di novelty di recommendation è quella serendipity, in cui agli utenti vengono inviate raccomandazioni per oggetti che loro non avrebbero potuto notare dai loro canali. Per chiarire la distinzione tra questi due approcci, viene presentato un esempio su un sistema di recommendation di news: Un sistema di personalizzazione che utilizza l'approccio content-based potrebbe generare considerazioni che non sono novel. Se un utente esprime una preferenza verso una particolare news, il sistema gli presenterà un testo simile alla news già considerata.

Un sistema novelty, eviterà attivamente di raccomandare news di cui sono già a conoscenza. Un sistema serendipity raccomanderà news su argomenti che non sono mai stati letti prima d'ora dall'utente. I ricercatori hanno studiato come raffinare gli algoritmi per promuovere i due approcci serendipity e novelty. Ma misurando la novelty si è notato che si ha bisogno che gli utenti, in modo live, indichino se la raccomandazione è stata fatta su oggetti nuovi (novelty). Coverage è la percentuale degli oggetti conosciuti dal collaborative filtering per i quali esso genera una predizione. È inoltre possibile calcolare una variante simile alla percentuale degli oggetti potenzialmente raccomandabili agli utenti. Ottimizzare le performance permette di non ottenere oggetti che sono già stati precedentemente raccomandati. Learnig Rate è la misura di quanto velocemente il sistema collaborative filtering produce una predizione sui dati che arrivano. Generalmente questo è calcolato per utente; viene misurato il numero dei ratings che un utente fornisce dopo che il sistema abbia generato una predizione. Confidence descrive, in un sistema a collaborative filtering, la capacità di valutare la qualità della sua previsione. La maggior parte dei sistemi collaborative filtering generano classificazioni basate sul più probabile rating predetto. Un sistema che calcola una predizione deve avere la capacità di eliminare dalle sue predizioni gli oggetti che hanno ratings alto e quindi sarebbero sempre presenti all'interno della lista di recommendation. Si preferisce che vengano introdotte novità, piuttosto che elementi con un alto rating da parte degli utenti. Se è possibile calcolare la fiducia delle previsioni, sarebbe opportuno permettere all'utente una scelta tra rischio e rendimento nel calcolo delle predizioni. User satisfaction metrics. I metodi descritto sopra sono solo alcuni dei modi che si hanno per valutare la capacità di predizione di un sistema collaborative filtering. Se il sistema è ben progettato e ben presentato, può essere una misura di quale percezione ha l'utente verso il sistema. Questo può essere misurato dalle statistiche di utilizzo o dalla ritenzione che si ha verso il sistema. Site performance metric. Questa metrica utilizza per la propria analisi le informazioni ricavate dall'utilizzo di un sito web. Vengono valutate il numero di utenti che lo utilizzano, il numero di utenti che vi si iscrivono, l'utilizzo di oggetti, lo scaricamento di oggetti e la frequenza di ritorno sul sito web. Queste misurazioni sono di tipo statistico, quindi facili da ottenere. Cosa meno semplice è capire quali parti bisogna cambiare all'interno del sito web.

2. L'APPLICAZIONE RD-PVR 2.1 Il servizio V-Cast V-Cast è un servizio web che permette la registrazione di programmi (radio e tv) e le mette a disposizione di tutti gli utenti registrati. Questo servizio vuole, utilizzando la piattaforma Facebook, diffondersi e accrescere il numero dei suoi potenziali utilizzatori. L'applicazione prende il nome di RD-PVR. Essa mette in comunicazione il sistema VCast con il potenziale fornito dalla rete sociale di Facebook.

Quello che RD-PVR vuole realizzare è, non solo che gli utenti Facebook utilizzino VCast, ma che ogni singolo utente possa ampliare il numero di registrazioni che segue. Questo obbiettivo può essere raggiunto fornendo a RD-PVR un sistema di recommendation che permetta di costruire, secondo i gusti e i comportamenti dell'utente, un insieme di registrazioni che l'utilizzatore non ha notato o non conosce, ma comunque di suo gradimento. Prima di passare a descrivere il sistema di recommendation, viene presentata una breve descrizione di come un utente possa effettuare registrazioni utilizzando V-Cast. Il primo passo che un utente fa è la registrazione presso il sistema. Ottenuti utente e password è

possibile iniziare le registrazioni. L'utente che intende programmare una registrazione deve compilare i seguenti campi: 1. Tipo di registrazione (TV, Radio) 2. Emittente (Rai, MTV, AllMusic...) 3. Formato di compressione (iPod, DivX, Apple TV...) 4. Giorno in cui viene effettuata la registrazione 5. Ora di inizio della registrazione 6. Ora di fine della registrazione 7. Giorni di conservazione sul server della registrazione (1,2,3) 8. Titolo 9. Frequenza della registrazione (Non ripete, Giornalmente, Settimanalmente) Una volta compilato il form con i dati sopra elencati il server procederà alla registrazione. Il risultato dell'elaborazione sarà un file, scaricabile dal server V-Cast, con la registrazione che è stata programmata. Ecco un esempio di due registrazioni eseguite dal sistema:

Come si vede dall'immagine la prima registrazione, “Prova registrazione”, è stata eseguita per 30 minuti, (10.30 – 11.00) ed è stata memorizzata in formato iPod. Essa non verrà ripetuta come indicato dal campo Ripeti. La seconda registrazione è identica alla prima è stato modificato soltanto il tipo di compressione che ora è DivX. Questo è quanto è possibile fare tramite il sistema V-Cast. Passiamo ora a descrivere RD-PVR.

2.2 RD-PVR e Facebook

Prima di commentare e discutere l'algoritmo di recommendation implementato in RDPVR, viene presentata una carrellata introduttiva sulla piattaforma Facebook [2]. Facebook è un social network che, oltre a dare la possibilità agli utenti di registrarsi e interagire tra di loro, permette di sviluppare applicazioni distribuibili tra tutti i partecipanti alla rete sociale.

La creazione e la registrazione di una applicazione Facebook segue quattro semplici passi: •

Sviluppo dell'applicazione utilizzando le librerie php5 Facebook.

•

Registrare l'applicazione su Facebook, assegnandogli un nome univoco (Es. http://apps.facebook.com/rdpvr/). L'applicazione viene registrata su Facebook, ma risiede su un server web esterno alla piattaforma.

•

Viene compilato un descrittore che aggiunge informazioni utili alla applicazione.

•

Distribuire l'applicazione tramite la rete sociale.

Questi quattro importanti passi rendono l'applicazione pronta ed utilizzabile. La rete sociale, per sua conformazione, permetterà la diffusione sfruttando le amicizie di ogni utente. L'applicazione viene installata sul profilo utente Facebook. Esso permette sia l'utilizzo da parte dell'utente installatore, sia ai contatti (friends) di vederla e installarla a loro volta sul loro profilo. Per ottenere il corretto utilizzo dell'applicazione è stata prevista una mappatura automatica tra utente V-Cast e utente Facebook. Questo permette, all'utente Facebook, di avere pronte tutte le registrazioni che segue attraverso V-Cast. RD-PVR prevede tre voci che l'utente può utilizzare: •

My podcast: indica i podcast che l'utente segue.

•

Friends recorded podcasts: registrazioni effettuate dagli amici Facebook.

•

Friends recommended podcasts: registrazioni che ci vengono raccomandate dagli amici.

RD-PVR, grazie a queste tre voci permette a chi la utilizza di muoversi e di agire sulle proprie registrazioni, e allo stesso tempo di monitorare cosa raccomandano o registrano gli amici che l'utente ha su Facebook. L'algoritmo di recommendation che nel prossimo paragrafo andremo ad affrontare, verrà integrato nella prima sezione di RD-PVR. Esso sarà il meno invasivo possibile e permetterà all'utente di esprimere una votazione, da uno a cinque stelline, su quanto sono graditi gli elementi raccomandati.

2.3 Algoritmo di Recommendation per RD-PVR L'applicazione RD-PVR nasce con l'intento di far conoscere il servizio V-Cast [3] al maggior numero di utenti utilizzando la piattaforma Facebook. RD-PVR, nel proporre le registrazioni che l'utente segue, mette a disposizione registrazioni che potrebbero piacere a chi utilizza l'applicazione. Questo compito viene assolto dall'algoritmo di recommendation, il quale si occupa di generare una lista di elementi che potrebbero interessare l'utente e mantenerlo su V-Cast. Un banale esempio del funzionamento di tale algoritmo è il seguente: consideriamo che l'utente u1 guarda abitualmente {Seria A, Coppa Italia, Trofeo Moretti}. Il sistema analizza gusti e preferenze affini e propone un possibile insieme di elementi candidati alla recommendation. Tale insieme per l'utente u1 potrebbe essere il seguente {Champions League, Premier League}. Il sistema di recommendation, esegue una analisi e propone un insieme di elementi affini all'utente. Per avvicinarci a questo calcolo, viene presentata di seguito la base dati che viene utilizzata per il reperimento delle informazioni utili all'algoritmo. Il sistema si avvale di sette tabelle: •

discrete: tabella contenente gli elementi discreti e i campi relativi per descriverli.

•

usr-discrete: tabella associativa tra utenti ed elementi discreti.

•

recom-deleted: contiene gli elementi che sono stati esplicitamente cancellati dagli utenti dalle precedenti recommendation.

•

vcast: contiene l'elenco degli utenti V-Cast.

•

facebook: contiene l'elenco degli utenti Facebook iscritti a V-Cast.

•

relation: crea una relazione tra l'utente V-Cast e l'utente Facebook che utilizza RDPVR.

•

titles: elenco di titoli associati ad un elemento discreto.

Un concetto importante, legato alla nostra base dati, è quello di elemento discreto. Con questo nome si indica un elemento che è a rappresentanza di altri elementi rappresentati a lui. Il calcolo del rappresentante è frutto di un algoritmo di discretizzazione che viene eseguito sugli elementi registrati nel sistema V-Cast. In particolare analizziamo l'utilizzo e il significato delle prime tre tabelle, discrete, usrdiscrete e recom-deleted. La tabella discrete contiene i campi che descrivono l'elemento discreto. Di seguito vengono riportati i più importanti con una breve descrizione: •

id-el: identificativo dell'elemento discreto.

•

most-likely-title: il titolo più frequente associato all'elemento discreto.

•

channel: canale di appartenenza.

•

start: inizio della registrazione.

•

end: fine della registrazione.

•

type-channel: tipo di canale (radio, tv).

•

repeat: tipo di ripetizione della registrazione (no-repeat, weekly, daily).

•

maxrec: numero massimo di registrazioni che l'elemento discreto può avere.

•

currec: numero di registrazioni a cui si è arrivati.

•

first-found: data e ora della prima occorrenza associata a questo elemento discreto.

•

last-found: data e ora dell'ultima occorrenza associata a questo elemento discreto.

La tabella usr-discrete contiene l'associazione tra elemento discreto e utente che utilizza la registrazione. Di seguito vengono riportati i campi più significativi: •

id-usr: identificativo dell'utente.

•

id-el: identificativo dell'elemento discreto.

•

lastacc: ultimo accesso da parte dell'utente vcast all'elemento.

•

cont: numero di accessi all'elemento.

•

rating: feedback diretto, fornito dall'utente. Può assumere valore da -1 a 5.

•

share: campo che indica se l'utente ha scelto di condividere l'elemento registrato.

La tabella recom-deleted contiene gli elementi discreti, già raccomandati dal sistema ad un utente, ma che sono stati scartati dall'utente stesso. Questo elenco ci permette di restringere il numero di elementi utili alle recommendation future. Ora è possibile procedere con il calcolo degli insiemi affini all'utente.

2.4 Collaborative Filtering in RD-PVR 2.4.1 Calcolo degli insiemi usr-affini e el-affini Gli insiemi di affinità che vengono calcolati, per un ipotetico utente u, sono i seguenti: •

usr-affini a u

•

el-affini a u

L'insieme usr-affini è l'insieme che contiene tutti gli utenti che hanno visto almeno una delle registrazioni che u segue. Questo meccanismo permette di ottenere un insieme di utenti che hanno una certa affinità di gusti con u. La rete V-Cast, a differenza di quella Facebook, non permette di avere una visione delle amicizie che l'utente stringe con altri utenti; essa permette soltanto di trovare legami, tra utenti, analizzando elementi in comune. L'insieme el-affini viene costruito a partire dall'insieme di utenti affini (usr-affini). Esso conterrà tutti gli elementi che sono stati visti dagli utenti affini ad u, ma che u non ha visto. Come ultimo passo vengono eliminati, da el-affini, tutti gli elementi discreti che sono stati esplicitamente cancellati dagli utenti nelle recommendation passate (tabella recomdeleted). Esempio: Siano u1, u2, u3, u4 utenti della piattaforma V-Cast. Tutti gli utenti hanno registrato alcuni elementi discreti di loro gradimento.

u1 ha registrato {X,Y} u2 ha registrato {Y,Z} u3 ha registrato {Y,W} u4 ha registrato {M,N} Si supponga che venga calcolata la recommendation per l'utente u1; esso ha in comune con gli utenti u2 e u3 l'elemento Y. Questo permette di creare l'insieme di usr-

affini(u1)={u2,u3}. Come da definizione, una volta calcolato usr-affini(u1), è possibile ottenere gli elementi affini a u1. L'insieme el-affini(u1)={Z,W}. Nel prossimo capitolo viene descritto come gli elementi affini {Z,W}, vengano pesati tramite il calcolo del valore di weight.

2.5 Il calcolo del weight Il weight è un valore che viene calcolato per ogni elemento discreto presente nell'insieme degli elementi affini ad u. Il calcolo viene fatto sommando il valore numerico decimale di tutte le clausole. Questo meccanismo permette di “spingere” in alto gli elementi discreti con valore di weight maggiore e che, secondo l'algoritmo, devono essere presentati all'utente per primi. Per ogni elemento di el-affini viene costruito il weight valutando le seguenti clausole: Clausola

Descrizione

Repeat

Dato un insieme r di tipi di ripetibilità {norepeat, daily, weekly}, sia ru l'insieme delle ripetitività che hanno gli elementi-discreti di un utente u, dove ru è sottoinsieme di r. Se un elemento-discreto candidato alla recommendation ha un valore del campo repeat che è presente in ru allora viene assegnato il valore 0.5 al rating dell'elemento.

Cont

Numero di volte che è stato visto un determinato elemento-discreto. Il valore assegnato è cont/10.

Rating Utente

Viene sommato il campo rating (usrdicrete.rating) in modo da privilegiare gli elementi che hanno un feedback direttamente espresso da altri utenti. Se il campo contiene il valore -1, esso non viene sommato al rating perché indica che non è stato espresso alcun feedback.

Il sistema permette di aggiungere ed eliminare clausole in modo da raffinare il calcolo. I pesi sono stati decisi in base all'importanza che si vuole dare alla clausola. La pesatura della clausola è un passaggio molto importante, poiché determina quale valutazione avrà maggiore efficacia sul valore di weight. Infatti una pesatura errata porterebbe ad una cattiva valutazione degli elementi discreti, e a una conseguente poca accuratezza del sistema di recommendation. Vediamo come vengono implementate le clausole in php5 e come viene utilizzata la base dati sopra descritta.

2.6 Implementazione in PHP5 Di seguito viene commentato il codice che implementa, in PHP 5, l'algoritmo di recommendation per RD-PVR. La classe ACF è così strutturata:

Variabili globali: private $id_usr: utente per cui viene fatta la recommendation. private $db: oggetto contenente le primitive per usare il database.

Metodi pubblici: public function __construct($id_usr): public function __destruct(); public function acf();

Metodi privati: private function c_repeat($row); private function c_repeat($row); private function c_rating($row);

Le variabili globali della classe ACF permettono di memorizzare l'utente per cui dovrà essere costruita la recommendation ed un oggetto, di tipo DB, che implementa le primitive per utilizzare la base di dati. I metodi pubblici permettono il vero e proprio utilizzo dell'algoritmo. Il costruttore,

(__construct($id_usr)), ha la funzione di inizializzare le variabili globali sopra commentate. /* Costruttore */ public function __construct($id_usr) { $this->id_usr = $id_usr; $this->db = new DB('194.116.82.201','rdpvr','rdpvr','pwd'); } Il distruttore, richiamato in fase di deallocamento dell'oggetto, pone a null le variabili globali. /* Distruttore */ public function __destruct() { $id_usr = null; $db = null; } Il metodo acf() è il vero cuore del sistema di recommendation. Esso restituisce un array associativo contenente la lista di elementi raccomandati; ogni cella contiene una coppia di valori [id-elemento,weight]. L'array associativo è ordinato in modo decrescente rispetto al campo weight, in modo da avere in cima gli elementi con valore maggiore. In coda all'array vengono memorizzati due campi: num_el e avg_weight. Il primo indica il numero di elementi trovati dall'algoritmo di recommendation, il secondo indica la media dei valori di weight dell'array. La struttura dati utilizzata è un array associativo; questo tipo di struttura dati permette di utilizzare indici testuali anziché indici numerici (Es: $weight['avg_weight'], per ottenere la media). Di seguito viene spiegato, attraverso il commento del codice, come il metodo acf() calcola la lista di elementi discreti utili alla recommendation.

public function acf() { /* Insieme di elementi affini */ $elaffini = $this->db->execute_query($q);

L'algoritmo inizia il calcolo selezionando, tramite una query SQL (corrispondente a $q), l'insieme di elementi affini all'utente per cui si costruisce la recommendation. La query SQL è la seguente: Si supponga che l'utente abbia id_usr = 10664.

SELECT DISTINCT usr_discrete.id_el, usr_discrete.id_usr FROM usr_discrete, utentiaffini WHERE usr_discrete.id_usr = utentiaffini.id_usr AND usr_discrete.id_el NOT IN (SELECT id_el FROM usr_discrete WHERE id_usr = 10664) AND usr_discrete.id_el NOT IN (SELECT id_el FROM recom_deleted WHERE id_usr = 10664); La tabella utenti affini è calcolata nel seguente modo: (SELECT id_usr FROM usr_discrete WHERE id_el IN (SELECT id_el FROM usr_discrete WHERE id_usr = 10664) AND id_usr <> 10664) AS utentiaffini

La query seleziona, dalla tabella usr_discrete, i campi id_el e id_usr di tutte le tuple utili alla recommendation. Questa selezione viene fatta dalle tabelle usr_discrete e utentiaffini. Le clausole WHERE, discriminano tutti gli elementi che l'utente (10664 nell'esempio) ha già visto, e tutti quelli che sono già stati esplicitamente cancellati dalle recommendation passate. Questi ultimi sono contenuti nella tabella recom-deleted. Il calcolo prosegue costruendo il valore di weight per ogni elemento dell'insieme di elementi affini. Il valore, numerico decimale, viene costruito come somma dei risultati dei metodi privati c_repeat($row), c_repeat($row), c_rating($row). Il risultato viene poi

memorizzato all'interno dell'array associativo, e ordinato secondo il campo weight, attraverso il metodo rsort() messo a disposizione da php5. /* Viene costruito un array associativo dove ogni cella è composta da {Weight, ID Elemento}. */ $weight = array(); $i = 0; $avg_weight = 0; while ($row = mysql_fetch_assoc($elaffini)) { $ris_weight = 0; /* Richiamo tutte le FUNZIONI-CLAUSOLE */ $ris_weight += $this->c_repeat($row); $ris_weight += $this->c_cont($row); $ris_weight += $this->c_rating($row);

/* Scrivo il rating nell'array */ $weight[] = array('weight' => $ris_weight, 'id_el' => $row['id_el']); $avg_weight += $ris_weight; $i++; } /* Ordino gli elementi in base al weight */ rsort($weight); /* Memorizzo, in conda all'array, il numero di elementi per cui ho costruito il weight. */ $weight['num_el'] = $i; /* Memorizzo, in coda all'array, la media aritmetica del weight. */ $weight['avg_weight'] = $avg_weight / $i; return $weight; }

Di seguito viene proposto un esempio di output dell'algoritmo:

ID Elemento: 32033 Weight: 28.5 ID Elemento: 29556 Weight: 24.1 ID Elemento: 16765 Weight: 21.9 ID Elemento: 16101 Weight: 21.2 ID Elemento: 66204 Weight: 17.1 ID Elemento: 59490 Weight: 17.0 ID Elemento: 69554 Weight: 14.9 ID Elemento: 70490 Weight: 13.8 ID Elemento: 21809 Weight: 11.1 ID Elemento: 79982 Weight: 10.7 …

Viene ora focalizzata l'attenzione su metodi che calcolano il valore di weight. Iniziamo l'analisi dal metodo che implementa la clausola c_repeat($row): private function c_repeat($row) { $rs_repeat = $this->db->execute_query('SELECT * FROM discrete WHERE id_el='.$row['id_el'].' AND discrete.repeat IN (SELECT discrete.repeat FROM discrete,usr_discrete WHERE usr_discrete.id_usr = '.$this->id_usr.' AND discrete.id_el = usr_discrete.id_el GROUP BY discrete.repeat);'); $row_el = mysql_fetch_assoc($rs_repeat); if($row_el) return 0.5; return 0; } La query che viene eseguita controlla se l'utente per cui viene calcolata la recommendation è solito seguire registrazioni con una certa ripetibilità (daily, weekly, no_repeat). Se l'elemento discreto che si sta analizzando ha ripetibilità affine a quella dell'utente viene assegnato il valore 0.5.

Proseguo il commento con la clausola c_cont($row): private function c_cont($row) { $rrow = $this->db->execute_query('SELECT cont FROM usr_discrete WHERE id_usr = '.$row['id_usr'].' AND id_el = '.$row['id_el'].';'); $row_el = mysql_fetch_assoc($rrow); return ($row_el['cont']/10); } Il metodo estrae il valore del campo usr_discrete.cont e lo restituisce diviso per dieci. Il campo cont indica il numero di accessi all'elemento discreto. Di seguito viene riportata l'ultima clausola per il calcolo del weight c_rating($row).

private function c_rating($row) { $rrow = $this->db->execute_query('SELECT rating FROM usr_discrete WHERE id_usr = '.$row['id_usr'].' AND id_el = '.$row['id_el'].';'); $row_el = mysql_fetch_assoc($rrow); if($row_el['rating'] != -1) return $row_el['rating']; return 0; } Questa clausola permette di recuperare dalla base dati il valore del rating associato a un elemento discreto. Come indica il FROM della query SQL il valore è contenuto nella tabella usr_discrete. Esso è molto importante, perché indica il feedback diretto che gli utenti hanno esplicitato su un elemento. L'utente decide il valore di rating assegnando all'elemento un valore che varia da 1 a 5. Il campo può assumere anche il valore -1. Quest'ultimo indica che l'utente ha premuto il pulsante “x” per cancellare l'elemento dalla lista sull'interfaccia utente.

3. TEST E VALUTAZIONI 3.1 Test condotti sui dump di V-Cast L'ultima parte del lavoro sull'algoritmo di recommendation è quella di condurre i test di affinità tra la lista di recommendation calcolata dal sistema e cosa effettivamente sceglie di registrare l'utente. Questo passo del lavoro non valuta se l'utente registra effettivamente quello che l'algoritmo propone, ma si occupa di valutare se la recommendation è stata fatta in modo affine rispetto ai gusti dell'utente per cui è calcolata. Procedendo in questo senso è possibile valutare, considerando gli elementi discreti che l'utente registra dopo il calcolo della predizione, se la lista di recommendation riesce a predire elementi che poi effettivamente vengono considerati e registrati dall'utente. Scendiamo ora nel dettaglio. Consideriamo due dump successivi che chiameremo i e j. Chiamiamo l'utente u e consideriamo l'elenco delle sue registrazioni nel dump i: R(u,i) = {r_1(u,i), r_2(u,i),..., r_n(u,i)} Per l'utente u viene calcolata una predizione che chiamiamo P(u,i). Questa predizione, calcolata per u considerando il dump i, presenta tutti gli elementi che l'algoritmo ha reputato affini secondo i criteri stabiliti nel capitolo precedente (Capitolo 2). Preso un dump successivo a i, chiamato nel nostro caso j = i + 6 giorni, vengono calcolate le seguenti due misure: •

Falsi negativi: quante registrazioni nuove ci sono in R(u,j) che non ci sono in P(u,i)

•

Falsi positivi: quante registrazioni ci sono in P(u,i) che non ci sono in R(u,j)

Queste due misure permettono di valutare il livello di “rumore” che è presente all'interno della predizione rispetto agli elementi discreti, nuovi e vecchi, associati a un utente. Passiamo ora a descrivere nel dettaglio come calcoliamo il valore di queste due importanti misure. Falsi negativi. Questa misura indica il numero di registrazioni nuove associate all'utente che non sono state predette dall'algoritmo. Questo tipo di “rumore” descrive una sorta di fallimento dell'algoritmo, perché l'utente ha registrato elementi discreti che l'algoritmo non ha valutato come affini. Più il numero dei falsi negativi è basso più significa che l'algoritmo è preciso in termini di affinità rispetto all'utente per cui calcola la

recommendation. Più è alto meno l'algoritmo è affine all'utente, quindi si sviluppa una divergenza tra gli elementi presenti nella predizione, e quelli effettivamente registrati dall'utente. Viene riportato di seguito un esempio che chiarisce quanto detto precedentemente. Supponiamo di avere R(u,i) = {el1, el2, el3} e P(u,i) = {el4, el5}. Prendiamo ora in considerazione un nuovo dump, chiamato j, dove R(u,j) = {el1, el2, el3, el4, el6}. Ora vogliamo calcolare il numero dei falsi negativi (FN) per l'utente u. FN(u) = 1 (el6). Falsi positivi. Questa misura indica il numero di registrazioni che sono state predette dal sistema ma che l'utente non ha registrato, e quindi non sono presenti nel dump successivo (j) a quando è stata calcolata la predizione P(u,i). Questa misurazione è importante perché da una visione sul numero di elementi che il sistema crede affini all'utente ma che in verità non lo sono. Di seguito viene ripreso l'esempio di prima per chiarire la definizione di falsi positivi. Supponiamo di avere R(u,i) = {el1, el2, el3} e P(u,i) = {el4, el5, el7}. Prendiamo ora in considerazione un nuovo dump, chiamato j, dove R(u,j) = {el1, el2, el3, el4, el6}. Ora vogliamo calcolare il numero dei falsi positivi (FP) per l'utente u. FP(u) = 2 (el5,el7). Nell'eseguire i test sopra descritti si è presentato un problema che ora vado a descrivere. Il problema che è stato riscontrato è legato al processo di discretizzazione fatto sulle registrazione V-Cast per generare elementi discreti che li rappresentano. Il processo di discretizzazione può essere riassunto da una funzione f che riceve un elenco di registrazioni e di queste, genera un elemento discreto che le caratterizza e le rappresenta: id_elemento-discreto = f (id_reg1, id_reg2, id_reg3) dove id_reg1, id_reg2, id_reg3 indicano gli identificatori di registrazioni V-Cast. Riassunto il processo di discretizzazione, passo a descrivere il problema incontrato con un esempio. Supponiamo che il processo di discretizzazione ha generato un id_el per un insieme di registrazioni che rappresentano la trasmissione televisiva “annozero” e un altro id_el per una registrazione sempre di “annozero” ma con ripetibilità “weekly” anziché “no_repeat”. id_el

most_likely_title

repeat

5

annozeo 15Feb

no_repeat

25

annozero

weekly

Questi due elementi sono si differenti perché il primo indica una specifica puntata di “annozero”, non ripetibile che si riferisce probabilmente a un argomento preciso, mentre il secondo elemento si riferisce all'appuntamento “annozero” con ripetibilità settimanale, ma questo aspetto non è rilevante per l'utente e a chi vuole verificare e provare il livello di accuratezza del sistema di recommendation. Per questo motivo si procede a valutare questo tipo di elementi discreti come simili, nonostante siano diversi come ripetibilità. Il nocciolo del problema si vede quando l'utente registra una nuova puntata, in questo caso, di “annozero” e magari il sistema di discretizzazione assegna la nuova registrazione a un elemento discreto già esistente oppure ne crea uno nuovo, ad esempio: id_el

most_likely_title

repeat

26

annozero 22Feb

no_repeat

Nel calcolo del numero di FN e FP il nuovo elemento (26) deve essere valutato come simile ai due precedenti (5, 25). Questo deve essere fatto perché si rischia di concludere che queste registrazioni sono diverse mentre appartengono alla stessa trasmissione televisiva, appunto “annozero”. Per ovviare a questo problema è stato realizzato il confronto lavorando sul campo most_likely_title. Questo campo, che indica il titolo più vicino all'elemento discreto, viene suddiviso in token e poi confrontato con il secondo titolo da comparare. Supponiamo di avere un elemento discreto nella previsione che abbia most_likely_title uguale a “la prova del cuoco”. L'elemento con sui deve essere comparato ha titolo “la prova del cuoco 15Feb”. Come si può notare questi due elementi discreti appartengono alla medesima trasmissione tv, ma l'algoritmo di discretizzazione li ha catalogati come due elementi discreti diversi. Come primo passo viene suddiviso in token il primo titolo:

t1: la

t2: prova

t3: del

t4: cuoco

Successivamente viene ricercato ogni token all'interno del secondo titolo e se la maggior parte dei token viene trovata allora abbiamo trovato un elemento discreto che viene considerato uguale al primo cercato. Questo tipo di operazione ci aiuta nel calcolo automatizzato dei falsi positivi e risolve il problema portato dalla discretizzazione.

3.2 Risultati e conclusioni Dopo aver affrontato, nel paragrafo precedente, le problematiche legate al calcolo del numero di falsi negativi e falsi positivi, vengono presentati i risultati dei test effettuati. La prima tabella contiene i dati relativi alle percentuali con la quale le predizioni hanno effettivamente predetto elementi discreti che l'utente ha poi visionato. Questi dati forniscono un quadro generale sull'accuratezza e il comportamento dell'algoritmo. N° utenti considerati

N° elementi predetti correttamente

N° elementi % Goal nuovi rispetto al dump precedente

Dump i (Recommendati on)

165

/

/

/

Dump j

28

0

1

0

4

12

33,3

5

8

62,5

0

1

0

0

1

0

0

1

0

1

1

100

1

2

50

1

1

100

0

1

0

3

4

75

0

1

0

1

10

10

0

1

0

0

1

0

0

1

0

1

1

100

0

1

0

0

1

0

0

1

0

3

15

20

0

1

0

1

1

100

1

1

100

0

1

0

2

3

66,7

1

1

100

1

1

100 Media % Goal: 36,3

Proseguiamo l'analisi dei dati con la seconda tabella che presenta il calcolo dei dei falsi positivi e dei falsi negativi. La voce P(u,i) indica il numero di elementi predetti per l'utente u nel dump i, mentre la voce R(u,j) indica il numero di registrazioni che l'utente u ha effettuato nel dump j. P(u,i)

R(u,j)

Falsi negativi

Falsi positivi

14

5

1

14

148

59

8

144

67

57

3

61

420

15

1

413

61

27

1

53

402

10

1

400

165

12

0

162

118

34

1

111

417

18

0

394

18

5

1

18

76

17

1

67

629

21

1

625

162

50

9

153

209

12

1

207

118

24

1

113

77

12

0

77

239

19

0

218

49

11

1

42

28

4

1

26

56

24

1

53

555

121

12

453

68

8

1

68

159

18

0

143

274

16

0

254

40

13

1

36

599

68

1

546

96

28

0

88

69

7

0

64

Analizzando i dati nella seconda tabella si è notata una importante suddivisione in tre categorie di comportamenti dell'algoritmo. Questi tre comportamenti indicano quanto è stato affine il calcolo della predizione dell'algoritmo. Le tre colorazioni utilizzate (rosso, giallo e verde) indicano rispettivamente se l'algoritmo non ha predetto nulla, ha predetto una buona quantità di elementi, ha predetto una ottima quantità di elementi. Dalla suddivisione in tre categorie si è notato che gli utenti (con predizione rossa) hanno un numero basso di elementi registrati. Questo crea difficoltà all'algoritmo che produce una predizione con bassa affinità. Le predizioni categorizzate in giallo, quindi con predizione buona, presentano un numero di elementi registrati per utente medio-basso. Per questi utenti la predizione risulta buona, e l'affinità dell'algoritmo cresce rispetto a utenti che hanno poche registrazioni. Infine le predizioni categorizzate in verde sono le più affini. Esse presentano un largo numero di elementi predetti correttamente e provengono da utenti che hanno un numero medio-alto di registrazioni. Di seguito viene riportata una tabella riassuntiva che mostra il numero medio di registrazioni che hanno effettuato gli utenti per ognuna delle tre categorizzazioni. Categoria

N° medio elementi registrati 8 22 38

Dall'analisi di questi dati e di queste categorizzazioni emerge l'importanza di individuare meccanismi che stimolino gli utenti a eseguire uno svariato numero di registrazioni. Una soluzione a questo problema è proprio l'algoritmo di recommendation; esso aiuterà l'utente a trovare contenuti che gli possano interessare mantenendolo e stimolandolo a utilizzare la piattaforma. Come concluso precedentemente, più l'utente effettuerà registrazioni, più chiaro sarà per il sistema creare predizioni ad alta affinità. L'importanza di avere uno strumento che aiuti la ricerca di contenuti affini all'utente permette, a un sistema come quello di V-Cast, di ampliare la visione utente a oggetti che

esso non riuscirebbe a trovare o non registrerebbe da solo. L'algoritmo di recommendation lavora appieno in questa direzione e permette, con l'aumentare del numero di registrazioni fatte dall'utente, di alzare la affinità della predizione che produce. Concludiamo la nostra analisi fornendo il codice PHP5 aggiuntivo che è stato sviluppato e utilizzato per i test e per il corretto funzionamento dell'algoritmo.

4. CODICE CORRELATO In questa sezione viene presentato il codice di supporto al lavoro svolto. In particolare viene riportato il codice PHP5 che implementa le primitive per utilizzare la base dati. La classe DB (db.php): conn = null; $this->conn = mysql_connect($db_server, $db_user, $db_pass); mysql_select_db($db_name, $this->conn); } public function __destruct() { mysql_close($conn); }

/* Funzione che permette di eseguire le query, ritorna il recordset risultato della query. */ public function execute_query($q) { return mysql_query($q, $this->conn); } } ?> Di seguito viene riportato il codice PHP5 che è stato utilizzato per calcolare il numero di falsi positivi risolvendo il problema descritto nel capitolo precedente.
$db = new DB('localhost','rdpvr_190209','root','root'); $fp = 0; $i = 1; $fp_u = $db->execute_query('SELECT DISTINCT id_usr FROM lr;'); while ($fp_user = mysql_fetch_assoc($fp_u)) { $fp_er = $db->execute_query('SELECT id_el FROM lr where id_usr = '. $fp_user['id_usr'].';'); {

// test id_el $fp_t1 = $db->execute_query('SELECT count(*) as num FROM rdpvr_260209.usr_discrete where id_usr = '.$fp_user['id_usr'].' and id_el = '. $fp_erac['id_el'].';'); if($fp_test1['num'] == 0) { // test sul titolo, most_likely_title $fp_t_er = $db->execute_query('SELECT most_likely_title from rdpvr_260209.discrete where id_el = '.$fp_erac['id_el'].';'); $fp_t_erac = mysql_fetch_assoc($fp_t_er); $token = explode(' ',$fp_t_erac['most_likely_title']); $fp_t_elv = $db->execute_query('SELECT rdpvr_260209.discrete.most_likely_title from rdpvr_260209.usr_discrete, rdpvr_260209.discrete where rdpvr_260209.usr_discrete.id_usr = '.$fp_user['id_usr'].' and rdpvr_260209.usr_discrete.id_el = rdpvr_260209.discrete.id_el;');

$s = 0; $trovate = 0; while($fp_t_elvisti = mysql_fetch_assoc($fp_t_elv)) { $s = 0; while($s < count($token)) { if(strlen($token[$s]) > 2 && stripos($fp_t_elvisti['most_likely_title'], $token[$s])) { $trovate++; } $s++;

} } if($trovate <= (count($token)/2)) $fp++; } } echo $i++.'. User: '.$fp_user['id_usr'].' N. fp: '.$fp.'
'; $fp = 0; } ?> Di seguito vengono riportate le tecnologie e i tool di sviluppo utilizzati durante lo stage: •

Apache – HTTP Server

•

PHP 5

•

Sun MySql 5

•

NetBeans 6.5

Ringraziamenti Il primo ringraziamento va al Prof. Giancarlo Ruffo, relatore di questa tesi, per la disponibilità e il supporto datomi nella realizzazione di questo documento e nel lavoro svolto durante lo stage. In secondo luogo tengo a ringraziare il Dott. Marco Milanesio e il Dott. Alessandro Basso che mi hanno fornito un importante supporto per quanto riguarda il lavoro in PHP5 e la base dati di V-Cast. Infine ringrazio la mia famiglia per il sostegno e l'appoggio datomi in questi tre anni di duro lavoro e studio. Appoggio sia umano che economico, fondamentali per il cammino che ho intrapreso e che qui vado a concludere.

Bibliografia 1: J. Ben Schafer, Dan Frankowski, Jon Herlocker, Shilad Sen, Collaborative Filtering Recommender SystemSchool of Electrical Engineering and Computer Science Oregon State University. 2: Facebook, facebook.com. 3: V-Cast, vcast.it. 4: Giancarlo Ruffo and Rossano Schifanella, A Peer-to-Peer Recommender System Based on Spontaneous Affinities, Università degli Studi di Torino. 5: Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl. Item- based Collaborative Filtering Recommendation Algorithms. Appears in WWW10, May 1-5, 2001, Hong Kong. 6: Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl. Analysis of Recommendation Algorithms for E-Commerce. Department of Computer Science and Engineering University of Minnesota Minneapolis, MN 55455. 7: J. Ben Schafer, Dan Frankowski, Jon Herlocker, and Shilad Sen. Collaborative Filtering Recommender Systems. School of Electrical Engineering and Computer Science Oregon State University 102 Dearborn Hall Corvallis, OR 97331. 8: Robert M. Bell and Yehuda Koren, Improved Neighborhood-based Collaborative Filtering, ATT Labs Research 180 Park Ave, Florham Park, NJ 07932. 9: SAVERIO PERUGINI and MARCOS ANDRE GONCALVES and ED-WARD A. FOX. A Connection-Centric Survey of Recommender Systems Research, Department of Computer Science, Virginia Tech, Blacksburg, VA 24061. 10: Yehuda Koren. Tutorial - Recent Progress in Collaborative Filtering.