Hybrid Event
Recommendation
using
Linked 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
Esempio: dato un utente, estrarre la lista degli utenti che ha
partecipato ad eventi comuni, ordinata per numero di eventi.
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)
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 Model
La 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
Peso di p
Evento
Proprietà in comune tra due eventi
Eventi a cui ha partecipato l’utente
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 Data
Utilizzando DBpedia, la versione RDF di Wikipedia, andremo
ad arricchire i temi degli eventi (la proprietà dcterms: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’utente
Gli 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
Rapporto fra eventi in comune
tra ui ed uj e la cardinalità di Ej
Insieme degli eventi a
cui ui ha partecipato
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