Hybrid Event Recommendation usingLinked Data and User Diversity

Approfondimento per il corso di Commercio Elettronico

Università Ca’ Foscari – A.A. 2013/2014

Filippo Ragazzo - 838696

Obiettivi dello studio

Sistema di raccomandazione di eventi tramite approccio ibrido basato sul web semantico.

Da un lato, verrà utilizzato un content-based system arricchito con dati collegati (Linked Data).

Dall’altro lato, verrà aggiunto un collaborative filtering per incorporare l’aspetto sociale, elemento che influenza significativamente le decisioni dell’utente.

Questo modello sarà arricchito da un user diversity model atto a rilevare la propensione dell’utente verso oggetti specifici.

Linked Data e cb recommendation

Principio generale: suggerire nuovi eventi simili a quelli che sono piaciuti all’utente nel passato.

La somiglianza fra eventi verrà calcolata tramite coseno di similitudine sugli attributi degli stessi.

Gli eventi saranno strutturati e collegati tramite la modalità Linked Data.

Linked Data

Modalità di pubblicazione di dati strutturati e collegati fra loro. Si basa su tecnologie e standard web aperti come HTTP e URI. Questo rende possibile collegare e utilizzare dati provenienti da diverse sorgenti per creare dataset RDF.

Il Resource Description Framework (RDF) è lo strumento base proposto da W3C per la codifica, lo scambio e il riutilizzo di metadati strutturati e consente l'interoperabilità tra applicazioni che condividono le informazioni sul Web.

Dataset RDF degli eventi

Assumiamo come evento un qualsiasi accadimento che comprende un gruppo di persone, luoghi, tempi e attività.

Lo modelliamo caratterizzandolo rispetto le 4 Ws:

• What happened?

• Where did it happened?

• When did it happened?

• Who was involved?

LODE ontology

Nome del termine

Tipo Definizione

Event Class “Qualcosa che è accaduto”, come riportato in articolo

atPlace Property Il nome del luogo

atTime Property Istante

circa Property Intervallo temporale

illustrate Property Oggetto multimediale che illustra l’evento

inSpace Property Regione astratta dello spazio (coord)

involved Property Persona o oggetto (fisico, sociale, …) coinvolto

involvedAgent Property … con agenzia

Esempio

Concerto degli Snow Patrol descritto tramite LODE ontology

Operativamente

Il dataset è stato collezionato da tre grandi directory di eventi (Eventful, Last.FM, Upcoming) e pubblicato su Linked Data Cloud (linkeddata.org).

Utilizzando SPARQL (linguaggio di interrogazione RDF) è possibile ricavare informazioni di interesse a partire da utenti in relazione.

Esempio

PREFIX UserURI:http://data.linkedevents.org/user

/6e150c44-d5f3-4dfc-97f1-1c593d9cc4a2

SELECT ?coattendee COUNT(DISTINCT ?event) as ?NB

WHERE {

?event lode:involved UserURI: .

?event lode:involved ?coattendee .

?event lode:atPlace ?place .

?place vcard:adr ?address .

?address vcard:locality "London" .

FILTER(?coattendee!=UserURI:)

} ORDER BY DESC (?NB)

Esempio: dato un utente, estrarre la lista degli utenti che ha partecipato ad eventi comuni, ordinata per numero di eventi.

Linked Data – Tensor Space Model

Oggetti: triple <subject, property, object>

Idea: oggetti semanticamente simili sono il subject di due triple RDF aventi la stessa property e lo stesso object.

Generalizzazione del classico Vector Space Model.

Linked Data visto come tensore tridimensionale, ove ogni sezione rappresenta la matrice di adiacenza per una proprietà particolare

Esempio

Linked Data – Tensor Space ModelLa rappresentazione di un evento ei relativamente

alla proprietà p è un vettore t-dimensionale che indicizza i termini/risorse in relazione con ei tramite p.

Assegnamo un peso TF-IDF per ogni risorsa r come segue.

1 se ei ha un collegamento a r tramite p, 0 altrimenti

Eventi totali nel dataset

Numero di eventi collegati a r tramite p

Linked Data – Similarità

La similarità fra due eventi ei ed ej rispetto alla proprietà p è pari alla misura del coseno di similarità fra i vettori che li rappresentano:

Problemi

L’approccio visto è stato utilizzato con successo per sistemi di raccomandazione, ma la sua efficacia è limitata nel caso di matrici di adiacenza molto sparse, come ad esempio lode:involvedAgent o lode:atPlace.

Un evento, infatti, accade in un solo luogo, quindi la proprietà lode:atPlace risulta discriminante nel calcolo della similarità.

Similarity-based Interpolation - Discriminabilità

Per risolvere il problema, andremo ad interpolare valori fittizi basati sulla similarità fra oggetti.

Metrica di discriminabilità:

Un valore di discriminabilità alto per la proprietà p indica che gli eventi hanno molti valori differenti rispetto a p.

Similarity-based Interpolation – Similarità di oggetti

Interpoliamo, inoltre, un punteggio di similarità fra oggetti della matrice di adiacenza, consci del fatto che, per esempio, eventi simili non coinvolgono necessariamente gli stessi performer.

Dunque, se le risorse rh e rk sono simili (diremo collegate) e se per un certo evento ei si ha che frh,

i, p = 1 e frk, i, p = 0, allora sostituiremo il valore di frk, i, p = sim(rh, rk) .

(Se rk è simile a più risorse, sceglieremo il valore massimo di similarità).

Similarity-based Interpolation – Similarità di oggetti

Ora, la formula del peso diventa, più in generale:

Insieme degli oggetti collegati a ei

Event recommendation

Nei dataset utilizzati, la relazione tra utenti ed eventi a cui hanno partecipato sono rappresentati come una matrice binaria con grado di densità del 2%.

Come soluzione, possiamo fornire una raccomandazione di eventi utilizzando algoritmi che mettano in relazione i metadati dell’evento con le preferenze dell’utente.

Metadati importanti sono distanza, argomenti, performer, …

Tuttavia, le raccomandazioni basate sui contenuti non tengono conto dell’aspetto sociale:

“Quali amici parteciperanno?”

Content-based Recommendation

Utente

Evento

Eventi a cui ha partecipato l’utente

Proprietà in comune tra due eventi

Peso di p

Vicinanza geografica

Gli utenti tendono a partecipare ad eventi geograficamente vicini, dunque questa è un aspetto da tenere in considerazione nella raccomandazione di eventi.

La similarità degli oggetti di tipo lode:atPlace sarà dunque calcolata come la vicinanza geografica normalizzata su un valore soglia misurato empiricamente pari a 80 km.

Arricchimento con Linked DataUtilizzando DBpedia, la versione RDF di Wikipedia,

andremo ad arricchire i temi degli eventi (la proprietà dc-terms:subject) semplicemente interrogando il database di DBpedia tramite query SPARQL sull’artista presente all’evento.

La ragione che sta dietro all’interesse per le categorie di DBpedia è data dalla loro struttura gerarchica ben definita.

Varietà degli interessi dell’utenteGli eventi della vita reale possono essere classificati

in un vasto insieme di categorie. L’utente può essere interessato ad eventi riguardanti uno specifico topic o artista, oppure può avere un orizzonte più ampio di interesse. Dunque confidare sulla similarità di eventi per le raccomandazioni può portare a risultati imprecisi.

Per far fronte al problema, daremo un peso differente agli eventi maggiormente di interesse.

Per determinare tali picchi di interesse, verrà usato il Latent Dirichlet Allocation (LDA), una tecnica per modellizzare i topic basata sull’occorrenza dei termini.

Varietà degli interessi dell’utente

Ove βp = 1 se p è diverso da dc:subject, altrimenti è un valore stimato che dipende dal grado di interesse dell’evento ei.

Varietà degli interessi dell’utente

Punteggi ottenuti da un campione di 1000 utenti di Last.fm.

(a)Range di varietà di interessi maggiormente fra 0.3 e 0.5 => utenti con alto interesse verso topic specifici.

(b)Interessi di un singolo utente, focalizzati prevalentemente sul topic 9.

Collaborative filtering

L’idea di base è che due utenti che assistono allo stesso evento possano avere un legame più forte tra loro rispetto ad altri utenti.

A differenza dei tradizionali collaborative filtering basati sui singoli utenti, non considereremo soltanto il legame fra singoli utenti, ma anche il contributo di un gruppo di amici.

Definiamo, dunque, una formula per predire la partecipazione di un utente u ad un evento sulla base delle intenzioni dei suoi co-partecipanti (utenti che hanno partecipato ad eventi passati assieme a u).

Collaborative filtering

Insieme dei co-partecipanti di ui che assisteranno ad e

Insieme degli eventi a cui ui ha partecipato

Rapporto fra eventi in comune tra ui ed uj e la cardinalità di Ej

Collaborative filtering

Contributo del singolo co-partecipante

Contributo del gruppo di amici

Hybrid Recommendation

Peso dato al collaborative filtering

Conoscere i pesi - GA

Gli algoritmi genetici (GA) sono metodi stocastici ispirati al meccanismo di evoluzione naturale ed ereditarietà genetica.

Nei GAs, una popolazione è data da un insieme di cromosomi, i quali denotano ciascuno un insieme di geni.

Una fitness function è una funzione che stima la bontà di ciascuna soluzione.

L’algoritmo applica la fitness function alla popolazione selezionando le soluzioni migliori e ricombinando la popolazione per la nuova generazione, fino a raggiungere la soluzione ottimale (o iterazioni massime).

Conoscere i pesi - GA

Nel nostro caso

Cromosoma – vettore dei coefficienti α

Fitness function – precisione sui dati campione

Popolazione – 30

Iterazioni – 80

Crossover rate – 0.9 (quantità di padri scelti ad ogni iterazione)

Mutation rate – 0.1 (grado di cambiamento della popolazione ad ogni iterazione)

Conoscere i pesi - PSO

La Particle Swarm Optimization (PSO) è una tecnica di ottimizzazione stocastica basata su popolazione ispirata ai comportamenti sociali degli stormi di uccelli o dei banchi di pesci.

PSO è più semplice da implementare, poiché non ha operatori di evoluzione come crossover e mutation.

Ogni generazione, ogni particella accelera verso la soluzione migliore, finchè tutte le particelle si raggruppano sulla soluzione ottima, sempre valutata da una fitness function.

Valutazione

Nota: fino ad ora non sono stati inclusi user diversity, né il peso βsubject .

Valutazione

Nota: coefficienti α ottenuti tramite PSO.

βsubject = 0.4 se l’evento non è incluso nei picchi di interesse, 1.6 altrimenti.

Valutazione