6.6 Algoritmo completo modello a testo unico negoziabile
A) For i=1 To i=n
I) totprezzi=totprezzi + II) For j=1 To j=n
(a) For k =1 To tot carrello //per ogni bene k già scelto dal cliente
(i) sinergie=sinergie + (b) k=k+1
2) j=j+1 III) i=i+1 B)
CALCOLO DELLA PROBABILITA’ EPIBR_1 (HP INDIPENDENTI) A) For i=1 To i=n
I) For k=1 To k=f 1)
2)
II) =
190
CALCOLO DELLA PROBABILITA’ EPIBR_2 (HP DIPENDENTI) C) For k=1 To k=f
I)
II) For i=1 To i=n 1)
2) i=i+1 III)
D)
EPCR (si veda il Paragrafo Algoritmo completo5.5) EROGAZIONE RACCOMANDAZIONE 1 EPIBR PER W (ONLINE) L) Inizializza
M) y= 1
N) METAEURISTICAv(carrello0) /*richiama la funzione meta euristica desiderata,
che riceve in input il primo elemento del carrello scelto dal cliente*/
O) Output B1 Max /*la funzione restituisce la migliore soluzione trovata, composta
da g elementi */
SIMULAZIONE DELLA RISPOSTA DEL CLIENTE ALLA RACCOMANDAZIONE 1 P) Se
∀ ∊ 1 , +∀ , ∊ 1 >0
I) carrellol= carrello0 ∪ B1 /*i prodotti relativi al bundle raccomandato vengono
aggiunti nel carrello */ Q) Altrimenti
I) //fissa il valore di epsilon ad una costante prestabilita
II) cas1 ← casuale (0,1)
III) //inizializzo la probabilità di abbandono
IV) Se cas1<
1) Uscita = VERO //Uscita senza acquisto
V) Altrimenti Se cas1≥ && cas1≤ //compra un altro bene dal
191 1) j=1
2) cas2 ← casuale (0,1) 3) πcum= πj
4) Finché cas2>πcum
(a) j=j+1
(b) πcum= πcum +πj
5) carrellol=j //scelgo il prodotto j nel paniere 1
VI) Altrimenti
1) Uscita = VERO //Uscita con acquisto di B0
EROGAZIONE RACCOMANDAZIONE y PER W (ONLINE) R) Inizializza
S) y= y+1
T) METAEURISTICAv(carrello0, carrello1 ,… ,carrelloy-1) /*richiama la funzione meta
euristica desiderata, che riceve in input il carrello scelto dal cliente*/
U) Output By Max /*la funzione restituisce la migliore soluzione trovata, composta
da g elementi */
// SIMULAZIONE DELLA RISPOSTA DEL CLIENTE ALLA RACCOMANDAZIONE y V) Se
∀ ∊ )+ ∀ ∊ ,∀ ∊ , +∀ , ∊ >0
I) carrellol= carrello0 ∪ B1 /*i prodotti relativi al bundle raccomandato vengono
aggiunti nel carrello */ W) Altrimenti
I) //fissa il valore di epsilon ad una costante prestabilita
II) cas1 ← casuale (0,1)
III) //inizializzo la probabilità di abbandono
IV) Se cas1<
1) Uscita = VERO //Uscita senza acquisto
V) Altrimenti Se cas1≥ && cas1≤ 1) j=1
192 3) πcum= πj
4) Finché cas2>πcum
(a) j=j+1
(b) πcum= πcum +πj
5) carrellol=j //scelgo il prodotto j nel paniere 1
VI) Altrimenti
A partire da un database interamente generato artificialmente secondo le poche informazioni disponibili in letteratura sono stati effettuati dei test orientati a equilibrare i parametri e a valutare l‘efficacia dei diversi metodi e modelli proposti in questa tesi. Il capitolo evidenzia la metodologia di generazione e di analisi, nonché i principali risultati conseguiti.
7.1 I database per le simulazioni
Gran parte degli algoritmi di raccomandazione vengono testati offline su basi di dati storici al fine di effettuare analisi sull‘accuratezza della loro capacità predittiva. Tuttavia, a causa della naturale
sparsity di tali dati è sovente impossibile effettuare valutazioni su tutti i prodotti del paniere: non è
quindi possibile determinare l‘appropriatezza di una stima del rating che un utente darebbe ad un prodotto, se nel database non è presente il valore del rating realmente attribuito. Altri autori conducono esperimenti dal vivo in laboratorio, in ambienti controllati, oppure implementano gli algoritmi su portali, valutandone le performance (Herlocker J. , Konstan, Terveen, & Riedl, 2004). Un frequente dilemma per i ricercatori è la scelta tra implementare l‘algoritmo su un database che replica in modo imperfetto le caratteristiche del target dello studio, oppure su un database sintetico opportunamente generato per l‘occasione. Il secondo sistema permette un‘accurata valutazione dell‘algoritmo, essendo disponibili anche le grandezze che normalmente sono nascoste (per esempio le preferenze reali degli utenti), ciononostante tali dati non possono essere considerati repliche affidabili della realtà, e le performance degli algoritmi possono dipendere dalla struttura stessa dei dati generati, i quali possono adattarsi meglio all‘uno o all‘altro a seconda del metodo utilizzato per la loro generazione (Herlocker J. , Konstan, Terveen, & Riedl, 2004).
Per questa ragione, nonostante molti progressi siano stati fatti nella generazione di database sintetici, molti scienziati preferiscono testare i propri algoritmi su database reali, ma scarsamente correlati con i loro obiettivi iniziali, oppure hanno giocoforza concentrato i propri sforzi di ricerca su algoritmi destinati a perfezionare i sistemi di raccomandazione orientati a tali target. I database più noti ed utilizzati per i collaborative recommender systems sono:
194
EachMovie Dataseti : con 2.811.983 valutazioni di 1.628 film da parte di oltre 72.916 utenti, con marche temporali (date e orari relativi ai vari eventi registrati) e alcune caratteristiche demografiche degli utenti. Dopo essere stato utilizzato per un grandissimo numero di pubblicazioni (tra cui Canny, 2002; Domingos & Richardson, 2003; Pennock, Horvitz, Lawrence, & Giles, 2000) il database è stato ritirato nel 2004 e non è più disponibile.
MovieLensii: suddiviso in tre dataset di dimensioni diverse: A. 100.000 valutazioni di 1682 film da parte di 943 utenti B. un milione di valutazioni di 3900 film da parte di 6040 utenti
C. dieci milioni di valutazioni e 100.000 tag per 10681 film da parte di 71567 utenti Utilizzato anch‘esso da moltissimi autori (Reddy, Kitsuregawa, Sreekanth, & Rao, 2002; Sarwar, Karypis, Konstan, & Riedl, 2001; Schein, Popescul, Ungar, & Pennock, 2002).
Wikilensiii: in cui gli utenti potevano (il sito non è più online, benché la banca dati sia ancora accessibile) introdurre beni, classificarli secondo micro categorie, valutarli e ricevere raccomandazioni in merito.
Book-crossingiv: contiene 278.858 utenti con alcune informazioni demografiche, 1.149.780 valutazioni di 271.379 libri
Jester-Jokev: contiene più di quattro milioni di valutazioni su una scala continua da -10,0 a +10,0 su 100 barzellette, da parte di 73.496 utenti (Goldberg, Roeder, Gupta, & Perkins, 2001). In tutti i casi esposti, i database non sono stati costruiti in portali di commercio elettronico, né esistono grandezze che possano in qualche misura essere collegate al prezzo. La minoranza dei ricercatori che ha potuto effettuare studi su database privati non ha potuto condividerli con la comunità scientifica, limitando in qualche misura la capacità di confronto tra algoritmi che database condivisi possono permettere. D‘altronde le informazioni sui propri consumatori, oltre che essere dati sensibili, costituiscono un vantaggio competitivo per le aziende che li possiedono, le quali sono pertanto restie a diffonderle. La mancanza di adeguati database per validare le diverse tipologie di sistemi di raccomandazione è ad oggi una delle principali sfide che deve affrontare la comunità scientifica e insieme uno dei principali limiti degli studi condotti finora.
i
Database non più accessibile.
ii http://www.grouplens.org/node/73#attachments iii http://www.grouplens.org/node/425#attachments iv http://www.informatik.uni-freiburg.de/~cziegler/BX/ v http://www.ieor.berkeley.edu/~goldberg/jester-data/
195
7.1.1 Generazione del database
Di seguito si evidenzia la metodologia utilizzata per generare le matrici ed i vettori che compongono il database artificiale utilizzato per la validazione dei modelli implementati: probabilità di acquisto, storico degli acquisti e matrici da esso derivanti, vettori dei prezzi .e dei costi, matrice dei benefici e dei costi percepiti dai consumatori virtuali.
7.1.1.1 Probabilità di acquisto
I dati in input sono stati simulati in modo da replicare l‘andamento negli acquisti che caratterizza il commercio elettronico. In particolare, sono state stimate le probabilità di acquisto di ogni prodotto, affinché gli acquisti risultanti rispettassero la distribuzione power-law di Pareto e riproducessero il fenomeno della long tail già trattato nel Paragrafo 2.3.8. A tal fine è stato necessario procedere a ritroso come segue:
A partire da un comune generatore di numeri pseudo casuali r uniformemente distribuiti tra
0 e 1, si è operata la seguente trasformazione: , ottenendo la variabile
casuale reale x compresa tra e infinito (Newman, 2005). Dove assumendo che ogni prodotto presente nel portale a regime sia stato acquistato almeno una voltavi, e α=2 scelta in modo da rispettare la regola 80-20. Si noti che α è frequentemente scelta tra 2 e 3, in assenza di dati storici da utilizzare al fine di stimare tale parametro con il metodo della massima verosimiglianza, sono state condotte mille simulazioni volte ad individuare il parametro che più frequentemente permettesse alle distribuzioni di rispettare la suddetta regola.
Ogni valore di x calcolato corrisponde al numero di acquisti effettuati di uno stesso prodotto. Seguendo un approccio frequentista si è calcolata la probabilità generica di acquisto del
bene x come rapporto tra i beni acquistati e il totale dei beni acquistati.
La simulazione viene quindi condotta con le probabilità così calcolate (si veda Algoritmo 7.1).
A) Inizializza n //numero di prodotti
B) =0
C) For i=1 To i=n
vi
Tale assunzione è opinabile, ma porre il valore minimo pari a 0 avrebbe evidentemente reso impossibile il ricorso a questa tecnica di generazione di numeri casuali secondo la legge di Pareto.
196
I) //frequenza di acquisto del prodotto i
II) III)
D) For j=1 To j=n I)
II)