In questo paragrafo verr`a presentato un tipico esempio di funzionamento
dell’algoritmo correttivo. Per semplicit`a l’esempio sar`a relativo a una racco-
mandazione Top-5 ossia l’output prodotto sar`a una lista di raccomandazione
di cinque elementi.
5.3.1 Gap Posizione Assoluta
Supponiamo di aver ottenuto al tempo t1 una lista di raccomandazione L1
e al tempo t2 una lista di raccomandazione L2, con t1 < t2. Si presuppone
ovviamente che tra t1 e t2 il profilo utente dell’utente in questione sia stato
modificato, ossia che l’utente abbia inserito dei nuovi voti o che comunque il modello su cui si basa la raccomandazione sia cambiato.
Figura 5.2: Gap Posizione Assoluta - Passo 1: Lista al tempo t1 (sinistra) e lista al tempo t2(destra)
Come si pu`o vedere dalla Figura 5.2, queste due liste si differenziano
per tre film: Alien 3, Hulk e Spiderman appaiono nella lista L2 a discapito
di Shrek 2, Ace Ventura e L’era glaciale. Il Reshuffling `e quindi di 35 pari
quindi al 60%. Il secondo passo `e quello di generare la lista entranti e la
lista uscenti.
Figura 5.3: Gap Posizione Assoluta - Passo 2: Lista entranti (sinistra) e lista uscenti t2(destra)
Come si pu`o vedere dalla Figura 5.3 entrambe sono composte da tre
film, la prima dai tre film che entrano nella nuova lista di raccomandazione, la seconda dai tre film che escono dalla vecchia lista di raccomandazione. Il passo successivo consiste nell’andare a calcolare per ogni singolo film di queste due liste il Gap Posizione Assoluto e ordinare la lista entranti secondo in maniera decrescente e la lista uscenti in quella crescente.
Figura 5.4: Gap Posizione Assoluta - Passo 3: Lista entranti (sinistra) e lista uscenti t2(destra) con relativo gap
Dalla Figura 5.4 possiamo vedere ogni singolo valore assegnato ad ogni
film delle due liste. Il valore `e calcolato in base alla posizione del film nella
vecchia lista di raccomandazione (colonna P.I.) e nella nuova lista (colonna
P.F.). Possiamo anche notare il valore della soglia prefissata (15%) che sar`a
il valore in base al quale si effettueranno le cancellazioni dalle due liste. Il
passo successivo infatti `e quello di verificare, all’interno della lista entranti,
se ci sono film il cui GAP Assoluto supera la soglia. Come si pu`o notare
ce n’`e uno (Alien 3 ). Tale film verr`a cancellato da questa lista, e verr`a
cancellato anche il primo della lista uscenti. Il risultato di questa operazione `
e presentato nella Figura 5.5.
Il passo successivo consiste nell’andare a verificare che nella lista uscen- ti vi siano dei film il cui gap sia minore della soglia negativa (−15%). In
Figura 5.5: Gap Posizione Assoluta - Passo 4: Lista entranti (sinistra) e lista uscenti t2(destra) dopo il primo filtraggio
questo caso non c’`e alcun film che abbia questa caratteristica, di conseguenza
le liste rimangono cos`ı come sono. Il passo successivo consiste nel confronto a coppie. Si confronta il primo film della lista entranti con il primo film
della lista uscenti. Se la differenza tra i due gap `e maggiore della met`a della
soglia allora i due film vengono eliminati dalle rispettive liste. Si procede poi a coppie fino alla fine della lista. Ovviamente questo passo viene effet-
tuato perch`e si utilizza la metrica di valutazione Gap Posizione Assoluta.
Partendo dall’inizio effettuiamo la prima operazione:
10% − (−6%) = 16%
16% `e maggiore della met`a della soglia (ossia 7.5%), di conseguenza i
film vengono eliminati dalle rispettive liste. Per gli altri due film invece 4%
non `e maggiore di 7.5%, quindi rimarranno all’interno di tali liste.
Figura 5.6: Gap Posizione Assoluta - Passo 5: Lista entranti (sinistra) e lista uscenti t2(destra) dopo il secondo filtraggio
Dalla Figura 5.6 si possono osservare i film rimasti nella lista entranti e in quella lista uscenti. Il film Spiderman non ha avuto un incremento di posizione tale da meritare di rimanere nella lista di raccomandazione (si
noti che questo `e il primo difetto di questa metrica che penalizza i film che
sono eccessivamente vicini alle N posizioni della Top-N e che quindi non po- tranno avere un incremento tale da superare la soglia). I film verranno, di
conseguenza, scambiati, ossia Spiderman verr`a tolto dalla nuova lista di rac-
comandazione e verr`a reinserito Shrek 2. La nuova lista di raccomandazione
`
e presentata nella Figura 5.7.
Figura 5.7: Gap Posizione Assoluta - Passo 6: Lista di raccomandazione restituita dall’algoritmo correttivo
5.3.2 Gap Posizione Percentuale
Supponiamo di aver ottenuto al tempo t1 una lista di raccomandazione L1
e al tempo t2 una lista di raccomandazione L2, con t1 ¡ t2. Si presuppone
ovviamente che tra t1 e t2 il profilo utente dell’utente in questione sia stato
modificato, ossia che l’utente abbia inserito dei nuovi voti o che comunque il modello su cui si basa la raccomandazione sia cambiato.
Figura 5.8: Gap Posizione Percentuale - Passo 1: Lista al tempo t1 (sinistra) e lista al tempo t2(destra)
Come si pu`o vedere dalla Figura 5.8, queste due liste si differenziano per
4 film: Pulp Fiction, Old Boy, V per Vendetta e I fantastici quattro appaiono
nella lista L2 a discapito di Bridget Jones, What Women Want, Die Hard
e Braveheart. Il Reshuffling `e quindi di 45 pari quindi all’ 80%. Il secondo
passo `e quello di generare la lista entranti e la lista uscenti.
Come si pu`o vedere dalla Figura 5.9 entrambe sono composte da 4 film,
la prima dai 4 film che entrano nella nuova lista di raccomandazione, la seconda dai 4 film che escono dalla vecchia lista di raccomandazione. Il passo successivo consiste nell’andare a calcolare per ogni singolo film di queste due liste il Gap Posizione Percentuale e ordinare la lista entranti secondo l’ordine decrescente e la lista uscenti secondo l’ordine crescente.
Dalla Figura 5.10 possiamo vedere ogni singolo valore assegnato ad ogni
Figura 5.9: Gap Posizione Percentuale - Passo 2: Lista entranti (sinistra) e lista uscenti t2(destra)
Figura 5.10: Gap Posizione Percentuale - Passo 3: Lista entranti (sinistra) e lista uscenti t2(destra) con relativo gap
vecchia lista di raccomandazione(colonna P.I.) e nella nuova lista (colonna
P.F.). Possiamo anche notare il valore della soglia prefissata (90%) che sar`a
il valore in base al quale si effettueranno le cancellazioni dalle due liste. Il
passo successivo infatti `e quello di verificare, all’interno della lista entranti,
se ci sono film il cui Gap Posizione Percentuale supera la soglia. Come si
pu`o notare ce ne son due (Pulp Fiction e Old Boy). Tali film verranno
cancellati da questa lista, e verranno cancellati anche i primi due della lista
uscenti. Il risultato di questa operazione `e presentato nella Figura 5.11.
Figura 5.11: Gap Posizione Percentuale - Passo 4: Lista entranti (sinistra) e lista uscenti t2(destra) dopo il primo filtraggio
Il passo successivo consiste nell’andare a verificare che nella lista uscenti
vi siano dei film il cui gap sia minore della soglia negativa (-15%). Vi `e
un film che ha questa caratteristica, ossia Die Hard, che verr`a cancellato
dalla lista uscenti. Verr`a anche cancellato il rispettivo della lista entranti.
Come gi`a detto, con questa metrica il confronto a coppie `e completamente
insensato. Il procedimento di analisi delle liste entranti e uscenti `e terminato
Figura 5.12: Gap Posizione Percentuale - Passo 5: Lista entranti (sinistra) e lista uscenti t2(destra) dopo il secondo filtraggio
Come si nota dalla Figura 5.12 questi sono i film rimasti nella lista entranti e lista uscenti. Il film I fantastici Quattro non ha avuto un incre- mento di posizione relativa tale da meritare di rimanere nella lista di rac- comandazione. I film verranno, di conseguenza, scambiati, ossia I fantastici
quattro verr`a tolto dalla nuova lista di raccomandazione e verr`a reinserito
Braveheart. La nuova lista di raccomandazione `e presentata nella Figura
5.13.
Figura 5.13: Gap Posizione Percentuale - Passo 6: Lista di raccomandazione restituita dall’algoritmo correttivo
Metodologia di test e
risultati
In questa sezione vengono descritte le metodologie di test per l’algoritmo
sviluppato, le metriche di qualit`a considerate per la valutazione di quest’ul-
timo e infine vengono presentati i risultati ottenuti anche in riferimento alla valutazione del problema discussa nel capitolo 3.
6.1
K-Fold Cross Validation
La K-Fold Cross Validation `e una tecnica che permette di stimare quanto
possono essere affidabili i risultati di un’analisi statistica su un campione indipendente [17]. Partendo da un campione, o dataset, questo viene suddi-
viso casualmente in K parti, o sottocampioni, della stessa numerosit`a. La
K-esime parte viene chiamata test set, o campione di validazione, mentre i restanti K − 1 sottocampioni vengono definiti training set. Il procedimento viene ripetuto K volte in modo che ogni sottocampione possa far parte del test set esattamente una sola volta. Durante ogni campionamento il training set viene utilizzato per la costruzione del modello, mentre il test set viene utilizzato per la validazione di questo modello. I risultati ottenuti dopo i K campionamenti possono essere combinati per ottenere una singola stima. Il
vantaggio di questo metodo `e che ogni singolo elemento viene usato almeno
una volta per la validazione del modello in modo da evitare problemi di
overfitting. Solitamente K viene settato a 10 e anche in questo lavoro si `e
deciso di utilizzare il metodo di 10-fold cross validation.
Figura 6.1: Esempio metodo K-Fold Cross Validation