Presentation Master Degree

Tesi di Laurea Magistralein

Accesso all’Informazione ed Elaborazione del Linguaggio Naturale

Selezione automatica di attributi estrattidalla Linked Open Data cloud in

un recommender system basato su grafi

Simone Rutigliano

Corso di Laurea Magistrale in Informatica

29 Aprile 2015

Relatore:Chiar.mo Prof. Giovanni Semeraro

Correlatore:Dr. Cataldo Musto

Recommender System

Simone Rutigliano 29 Aprile 2015 1

Recommender System - graph-based representation

NodiUtentiItem

ArchiPreferenza dell’utenteverso quell’item


Come raccomandare gli item?

Algoritmo utilizzato per determinare l’importanza di un nodo in ungrafo e PageRank

Sviluppato da Larry Page e Sergey Brin nel 1998 presso laStanford University

Algoritmo di ricerca di Google“The heart of our software is PageRank TM. . . it provides thebasis for all of our web search tools.”

Lo score restituito dal PageRank per ogni item puo essereutilizzato per ordinare gli item dal piu rilevante al menorilevante


PageRank

Valuta l’importanza di un documento sulla base del numero edella qualita di connessioni che quel documento avra all’interno delgrafo di appartenza


PageRank con Priorita

Il pageRank classico assegna una equa probabilita ad ogniarco del grafoVariante con Priorita definita in [Hav03] introduce un bias afavore di alcuni nodi

enfatizza maggiormente le preferenze dell’utente


Applicazione del PageRank in un RS

E possibile utilizzare il PageRank come algoritmo diraccomandazione in un Recommender System graph-based


Estensione del RS

E possibile arricchire il grafo aggiungendo nuove informazionirelative agli item?


Linked Open Data cloud

Metodologia per pubblicare, condividere e collegaredati strutturati sul web


Linked Open Data cloud

Collezione (Cloud) di dataset:

Interconnessi fra loro (Linked)

Fruibili liberamente e gratuitamente (Open)

Descritti attraverso RDF


DBpedia

Centro della LinkedOpen Data cloud

Conversione diWikipedia in RDF


Partendo da Wikipedia. . .


. . . otteniamo DBpedia


Integrare LOD nel Recommender System. . .

Partendo dal grafo User-Item


. . . Integrare LOD nel Recommender System. . .

Espandendo il film Inglorious Basterds attraverso la Linked OpenData



Espandendo il film Django attraverso la Linked Open Data



Espandendo anche gli altri film presenti nel grafo avremo


. . . PageRank nel nuovo grafo

Riapplicando il PageRank si potrebbe avere un nuovo ranking


PageRank + LOD: pro e contro

PROnuove connessioni nel grafo

CONTROmaggiore costo computazionaleper l’esecuzione del PageRank

alcune proprieta non sonorilevanti


Tecniche di feature selection

SOLUZIONE: Applicare tecniche di feature selection!


Research question

1 L’uso delle proprieta della LODmigliorano le performance delrecommender?

2 Si possono trarre vantaggidall’utilizzo di tecniche di FS sullaLOD?

3 Esiste una connessione tra la sceltadella tecnica di FS e ilcomportamento dell’algoritmo?

4 Come si comporta la nostrametodologia rispetto allo statodell’arte?


Protocollo Sperimentale - Datasets

Movielens dataset

Rating di film estratto dal sito di MovieLens dal GroupLensResearch (http://movielens.org)

Users: 943

Films: 1.682

Binary ratings: 100.000

Sparsity: 93,69%Positive Rating: 55,17%Avg. Rating per user: 84,83Avg. Rating per item: 48,48


Protocollo Sperimentale - Datasets

Books dataset

Rating di libri usato per la Challenge di ESWC 2014

Users: 6.181

Books: 6.733

Binary ratings: 72.372

Sparsity: 99,83%Positive Rating: 45,85%Avg. Rating per user: 11,70Avg. Rating per item: 10,74

Molto sparso

Sbilanciato verso rating negativi


Protocollo Sperimentale - Setup

Ogni esperimento sara dato dalla combinazione dei seguenti fattori

TecnicaPageRank conpriorita

SplitMovielens: 5 foldBooks: training etest fisso

RappresentazioniGraphGraph + LODGraph + LOD + FS

Proprieta totali60 per Movielens70 per Books

Tecniche di FSPageRankχ2

Info GainGain RatiomRMRPCASVM

Featuresselezionate

103050

MetricheF1Diversity (ILD)


Experiment 1

L’uso delle proprieta della LOD migliorano le performance delrecommender?

Movielens Books

Graph Graph + LOD Graph Graph + LOD

F1@5 0,5389 0,5424 0,5502 0,5504F1@10 0,6023 0,6083 0,6431 0,6421F1@15 0,5941 0,5963F1@20 0,5662 0,5686

Time(min) 72 880 +1122% 104 2.433 +2239%

Nodes 2.466 53.734 +2078% 12.649 211.661 +1573%Edges 44.300 178.646 +303% 33.189 534.841 +1511%

Tutte differenze statisticamente significative(Wilcoxon p-value < 0.01)


Experiment 2 - Movielens

Si possono trarre vantaggi dall’utilizzo di tecniche di FS sulla LOD?

N Feature PageRank mRMR χ2 SVM GainRatio InfoGain PCA

F1@510 0,5418 0,5397 0,5414 0,5382 0,5372 0,5397 0,540630 0,5429 0,5429 0,5419 0,5413 0,5398 0,5396 0,541350 0,5412 0,5421 0,5420 0,5421 0,5406 0,5412 0,5431

F1@1010 0,6069 0,6039 0,6056 0,6043 0,6033 0,6039 0,604530 0,6084 0,6072 0,6070 0,6074 0,6059 0,6055 0,608150 0,6070 0,6077 0,6079 0,6081 0,6078 0,6072 0,6088

F1@1510 0,5964 0,5950 0,5955 0,5943 0,5938 0,5950 0,594830 0,5967 0,5962 0,5967 0,5964 0,5960 0,5955 0,596750 0,5955 0,5962 0,5972 0,5966 0,5968 0,5962 0,5970

F1@2010 0,5684 0,5668 0,5672 0,5669 0,5666 0,5668 0,566730 0,5684 0,5679 0,5679 0,5679 0,5675 0,5675 0,568950 0,5682 0,5685 0,5686 0,5683 0,5687 0,5685 0,5689

Ad esclusione del PageRank, tutte le altre tecniche hanno illoro picco su 50 features

Tutte differenze statisticamente significative(Friedman p-value < 0.01)


Experiment 2 - Movielens Riepilogo

Paragonando i risultati migliori con le baseline

Graph Graph + LOD Graph + LOD + PCA

F1@5 0,5389 0,5424 0,5431F1@10 0,6023 0,6083 0,6088F1@15 0,5941 0,5963 0,5970F1@20 0,5662 0,5686 0,5689

Time(min) 72 880 585 -33%

Nodes 2.466 53.734 48.327 -10%Edges 44.300 178.646 167.319 -6%


Experiment 2 - Books


N Feature PageRank mRMR χ2 SVM GainRatio InfoGain PCA

F1@510 0,5515 0,5493 0,5512 0,5507 0,5524 0,5540 0,551330 0,5518 0,5519 0,5517 0,5519 0,5524 0,5519 0,551050 0,5517 0,5511 0,5505 0,5512 0,5503 0,5511 0,5513

F1@1010 0,6431 0,6435 0,6423 0,6434 0,6435 0,6445 0,643330 0,6422 0,6427 0,6420 0,6430 0,6431 0,6427 0,643250 0,6418 0,6419 0,6419 0,6426 0,6425 0,6419 0,6428

I risultati migliori con 10 e 30 feature

Tutte differenze statisticamente significative(Friedman p-value < 0.01)




InfoGain risulta essere la tecnica piu performante


Experiment 2 - Books Riepilogo

Paragonando i risultati migliori con le baseline

Graph Graph + LOD Graph + LOD + InfoGain

F1@5 0,5502 0,5504 0,5540F1@10 0,6431 0,6421 0,6445

Time(min) 104 2.433 1.341 -45%

Nodes 12.649 211.661 88.669 -58%Edges 33.189 534.841 142.334 -73%



Esiste una connessione tra la scelta della tecnica di FS e ilcomportamento dell’algoritmo?



Come si comporta la nostra metodologia rispetto allo statodell’arte?


Conclusioni

L’uso delle proprieta della LOD migliora leperformance del recommender

Si possono trarre vantaggi dall’utilizzo ditecniche di FS sulla LOD sia in termini di F1 chein tempo di esecuzione

Alcune tecniche di FS sono in grado di migliorareun particolare aspetto anziche altri

Rispetto allo stato dell’arte il sistema realizzatoriesce a produrre risultati migliori


Sviluppi futuri

Testare altre tecniche di Feature Selection

Combinare le tecniche di FS in base ai risultati ottenuti

Unire o intersecare le tecniche migliori

Trovare il numero esatto di feature da utilizzare in ognitecnica di FS


References I

Taher H. Haveliwala.

Topic-sensitive pagerank: A context-sensitive ranking algorithm for websearch.

IEEE Trans. on Knowl. and Data Eng., 15(4):784–796, July 2003.


Funzionamento del PageRank

Consideriamo un grafo composto da sei documenti cosi connessi

1 2

3

56

4



Creazione della matrice di Google per righe P del grafo

1 2

3

56

4

P =

0 12

12 0 0 0

0 0 0 0 0 013

13 0 0 1

3 0

0 0 0 0 12

12

0 0 0 12 0 1

2

0 0 0 1 0 0




1 2

3

56

4

P =

0 12

12 0 0 0

0 0 0 0 0 013

13 0 0 1

3 0

0 0 0 0 12

12

0 0 0 12 0 1

2

0 0 0 1 0 0


. . . Funzionamento PageRank - Stocasticita . . .

Considerato che il nodo 2 e un nodo dangling1 sara necessariotrasformare il grafo e rendere stocastica la matrice corrispondente

1 2

3

56

4

P =

0 12

12 0 0 0

16

16

16

16

16

16

13

13 0 0 1

3 0

0 0 0 0 12

12

0 0 0 12 0 1

2

0 0 0 1 0 0

s1Privo di link uscenti


. . . Funzionamento PageRank - irriducibilita. . .

Il grafo dovra subire un’ulteriore trasformazione rendendo lamatrice di Google per righe irriducibile

1 2

3

56

4

P =

0 12

12 0 0 0

16

16

16

16

16

16

13

13 0 0 1

3 0

0 0 0 0 12

12

0 0 0 12 0 1

2

0 0 0 1 0 0

s


. . . Funzionamento PageRank - irriducibilita. . .

Per rendere irriducibile la matrice i valori verranno ricalcolatisecondo la formula:

¯P = 0.85 ∗ P +0.15 ∗ 11ᵀ

6

1 2

3

56

4

¯P =

0.025 0.45 0.45 0.03 0.03 0.03

0.17 0.17 0.17 0.17 0.17 0.17

0.31 0.31 0.03 0.03 0.31 0.03

0.03 0.03 0.03 0.03 0.45 0.45

0.03 0.03 0.03 0.45 0.03 0.45

0 0.03 0.03 1 0.03 0.03

sSimone Rutigliano 29 Aprile 2015 54

. . . Funzionamento PageRank

Attraverso il metodo delle potenze si andranno a calcolare gliautovalori della matrice ottenendo i valori del PageRank

1 2

3

56

4

π =

0.372

0.054

0.042

0.375

0.206

0.286

sIl ranking dei documenti sara quindi: 4 - 1 - 6 - 5 - 2 - 1


PageRank

Utilizza la stessa tecnica utilizzata nella raccomandazione pereffettuare anche la feature selection

Cerca le feature piu importanti in base a quante volte sonopresenti nella Linked Open Data


Chi Squared

Verifica se esiste una correlazione tra le feature e l’attributo diclasse usando la statistica χ2

Il test statistico sara:

χ2 =C∑i=1

(Oi − Ei )2

Eicon gradi di liberta pari a C − 1

dove

C = numero di categorie

Oi = frequenze osservate per la categoria i

Ei = frequenze attese per la categoria i


Information Gain

Valuta gli attributi sulla base del guadagno di informazione cheapporta al dataset

Guadagno ottenuto riducendo l’incertezza iniziale

IG (S ,Attr) = Entropy(S)−∑

v∈Values(Attr)

|Sv ||S |· Entropy(Sv )

dove:

S : dataset di training

Attr : rappresenta l’attributo da analizzare

v : valori degli attributi Attr

Sv : subset di istanze con attributo Attr valorizzato con v


Gain Ratio

Estensione dell’information gain classico

Mira a penalizzare gli attributi con un numero elevato di valori

Normalizza l’InfoGain usando l’entropia di S in relazioneall’attributo Attr (Split information)

SplitInformation(S ,Attr) = −∑

v∈Values(Attr)

|Sv ||S |

log

(|Sv ||S |

)

Definizione di GainRatio:

GainRatio(S ,Attr) =IG (S ,Attr)

SplitInformation(S ,Attr)


mRMR

Consiste nel trovare il subset di feature che riesconocontemporaneamente a garantire:

minima ridondanza tra le features

features tra loro piu dissimilari possibili

massima rilevanza delle features con la classe target

features piu discriminanti per la classe target


Principal Component Analysis (PCA)

Riduce la dimensionalita del dataset combinando le variabili ingioco

Mantiene lo stesso apporto informativo del dataset originale

Le nuove variabili, chiamate Principal Components (PC), sononon correlate, e sono ordinate in base all’informazione cheessa contiene


Principal Component Analysis (PCA)

Trova l’asse che meglio rappresenta la piu grande variazione(First principal component) e proietta tutti i punti suquest’asse

Definisce la nuova dimensionalita sulla base degli autovettoridella matrice di covarianza associata


Support Vector Machine (SVM)

SVM massimizza il margine di separazione tra gli iperpiani

La funzione di decisione viene creata sulla base del subset diesempi (support vectors)


Presentation Master Degree

Technology

Transcript of Presentation Master Degree