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?

Research question

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)

Featuresselezionate

103050

Featuresselezionate

103050

Featuresselezionate

103050

Featuresselezionate

103050

Featuresselezionate

103050

Featuresselezionate

103050

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

Conclusioni

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

Sviluppi futuri

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

Creazione della matrice di Google per righe P del grafo

12 0 0 0

0 0 0 0 0 013

13 0 0 1

0 0 0 0 12

0 0 0 12 0 1

0 0 0 1 0 0

12 0 0 0

0 0 0 0 0 013

13 0 0 1

0 0 0 0 12

0 0 0 12 0 1

0 0 0 1 0 0

12 0 0 0

0 0 0 0 0 013

13 0 0 1

0 0 0 0 12

0 0 0 12 0 1

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

12 0 0 0

13 0 0 1

0 0 0 0 12

0 0 0 12 0 1

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

12 0 0 0

13 0 0 1

0 0 0 0 12

0 0 0 12 0 1

0 0 0 1 0 0

. . . Funzionamento PageRank - irriducibilita. . .

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

¯P = 0.85 ∗ P +0.15 ∗ 11ᵀ

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

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

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 )

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 |

(|Sv ||S |

Definizione di GainRatio:

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

SplitInformation(S ,Attr)

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

Lg presentation

Máster Universitario en Arquitectura-Barcelona …...Máster Universitario en Arquitectura-Barcelona (Master BarcelonaArch) Master Degree in Architecture - Barcelona (Master BarcelonaArch)

Untitled presentation

Corso di Laurea in Ingegneria Anno accademico …...study course dedicated to E-mobility 2 PRESENTAZIONE DEL CORSO DI LAUREA PRESENTATION OF THE BACHELOR DEGREE Nell'anno accademico

FPGrowth Presentation

I Master IPE - Business School - ipeistituto.it · Business case & business game Visite aziendali Project work ... Lavoro di consulenza specifico ... scrivere il cv, presentation,

Bachelor Degree Certificate with grades - Università degli Studi di Palermo

Degree Thesis

Rivestimenti Rami cati e Prime-Degree ... - AMS Tesi di Laurea

Slideshow of my bachelor's degree thesis (italian)

Filiera presentation

Easy Degree

Presentazione standard di PowerPoint - ccsmecc.polimi.it · Outline Mechanical Engineering Study Programme Campuses and courses Master of Science - Introduction Internal Double Degree

WELCOME GUIDE DEGREE SEEKER - Unive

My degree thesis Google Food & Google Food+

PRIJSLIJST 2020 · 2020-02-10 · Nemas Middle Management HBO-ad (Associate Degree) € 1.995,- p.p. Nemas Advance Management HBO-ad (Associate Degree) € 2.795,- p.p. Al onze HBO

DOUBLE DEGREE - unipr.it · Double Degree il piano di studi sarà così articolato: Primo Anno (a Parma, Italia) IL PIANO DI STUDI DEL DOUBLE DEGREE PARMA-LIONE 5 Insegnamenti (Trade

Roadshow Presentation Initial Public Offering - Giugno ... · Roadshow Presentation Initial Public Offering - Giugno 2001Roadshow Presentation Initial Public Offering - Giugno2001.

PRESENTATION TITLE PRESENTATION SUBTITLE - CORE

L’ATTIVAZIONE DI COMPETENZE INTERCULTURALI all’interno dei programmi Double Degree