Clustering di transazioni web sulla base della similarità degli accessi

 Introduzione 
di quanto detto precedentemente, le sessioni possono essere ben 
modellate come sequenze di pagine, poiché, interessa conoscere in che 
ordine le pagine sono state richieste per la loro visita e, per rafforzare 
il concetto, si può far riferimento ai tempi di visita delle pagine stesse, 
partendo dalla supposizione che un utente si sofferma su una data 
pagina per più tempo di un’altra in quanto in essa riscontra maggior 
interesse che in altre, per cui una sessione verrà modellata come una 
sequenza di pagine con il corrispondente tempo di visita. 
 
I.3 Contributi 
Verrà prodotto un sistema che datogli come input, un insieme di 
sessioni estratti da un file logs del server, estrapoli da esse la loro 
similarità, e in base a questa, produca un insieme di profili utenti atti 
a descrivere e riassumere il comportamento di navigazione degli 
utenti, che in passato hanno contribuito alla creazione delle sessioni 
prese in esame. I profili, hanno lo scopo di essere un mezzo di 
confronto con le ultime pagine visitate da un utente on line, per 
desumere gli interessi dello stesso, a partire dai comportamenti di 
navigazione di utenti passati. 
Da quanto descritto è facile desumere che il sistema avrà due 
modalità di elaborazione, la prima (fase Batch), si occuperà della 
creazione dei profili a partire delle sessioni di input, la seconda (fase 
On Line), fornirà degli strumenti da integrare, opportunamente, con le 
applicazioni web per fornire le pagine da suggerire. 
 2
 Introduzione 
I.4 Organizzazione del lavoro di tesi 
Questo lavoro di tesi sarà organizzato nei seguenti capitoli. 
Capitolo 1: darà una succinta introduzione ai concetti di Data 
Mining, Clustering e Web Mining 
Capitolo 2: esplicherà il concetto di similarità di pagine e di 
sessione web che rappresentano il cardine di tutto il lavoro. 
Capitolo 3: introdurrà un algoritmo di clustering che sarà 
implementato e integrato nel sistema. 
Capitolo 4: mostrerà come vengono ottenuti i profili utenti e 
come vengono sfruttati nella personalizzazione 
Capitolo 5: descriverà come è stato implementato il sistema a cui 
è stato dato il nome di PROPHET. 
Capitolo 6: indicherà gli strumenti e le misure usate per valutare 
le prestazioni del sistema. 
 3
Capitolo I -Data mining  e web mining  
Capitolo 1 
 
DATA MINING E WEB MINING 
 
1.1 Data mining 
Il data mining rappresenta una vasta area di ricerca che consiste 
in tecniche ed algoritmi per l’analisi di grandi volumi di dati, al fine di 
estrazione ed enumerazione di modelli, atti a fornire una descrizione 
ad alto livello della regolarità intrinseca dei dati osservati. 
Indipendentemente dall’applicazioni specifiche, l’attività del data 
mining si contrassegna in varie fasi che vanno dagli obiettivi da 
raggiungere alla valutazione dei risultati. 
Le fasi del Data Mining si caratterizzano in: 
Definizione degli obiettivi. 
Rappresenta il cardine di tutto il processo, poiché, in questa fase verrà 
organizzata tutta la metodologia da usare nel seguito. Per meglio dire, 
verranno scelti i dati da usare, le tecniche di manipolazione e la 
produzione dei risultati. 
Pre-Trattamento dei dati 
I dati di partenza vengono manipolati in modo tale che siano 
manipolabili nelle tecniche successivamente usate e che siano privi di 
informazioni aggiuntive inutili al trattamento degli stessi.  
 4
Capitolo I -Data mining  e web mining  
Elaborazione dei dati sulla base dei metodi usati 
In questa fase, in base alle scelte fatte in analisi, vengono applicate le 
metodologie scelte, al fine di estrarre opportuni modelli a partire dai 
dati pre-trattati. Dal punto di vista metodologico, gli approcci per 
l’estrazione dei modelli si dividono in logico e statistico. Il primo 
produce una descrizione deterministica dei dati originali, mentre, il 
secondo sfrutta calcoli probabilistici per la manipolazione esplicita con 
incertezza che, essendo una caratteristica tipica dei processi di data-
generating, fa del data mining statistico il metodo più usato 
nell’applicazioni pratiche. 
Le tecniche di data mining possono essere divise in due 
categorie: 
• Predictive modelling: quando lo scopo è compiere 
l’inferenza su dati correnti per predire nuove informazioni a 
partire da dati sconosciuti. Questo si avvale di due fasi. La 
prima genera un modello dai dati osservati che, in seconda 
istanza, sfrutta per effettuare delle previsioni su una nuova 
serie di dati, sulla base delle informazioni nello stesso insieme.  
• Data description: quando lo scopo è individuare una 
caratterizzazione dei dati fondamentali, interpretabile dall’uomo, 
che può essere di qualche interesse. Per meglio dire, cercare dei 
modelli che individuano le proprietà generali da informazioni 
considerate fondamentali. Due principali tecniche descrittive 
 5
Capitolo I -Data mining  e web mining  
sono association rules mining e clustering. Di quest ultimo sarà 
data ampia descrizione nel paragrafo successivo. 
 
1.2 Clustering 
Il clustering è un metodo atto a classificare grandi insiemi di 
dati partizionandoli in gruppi di dimensioni più piccole, detti cluster 
(lett. ”grappolo”).  
Eseguire il clustering di un dataset con determinati attributi, 
significa individuare gruppi di oggetti tali che: 
• Oggetti appartenenti allo stesso gruppo siano più simili fra 
di loro (alta intra-similarità del cluster) 
• Oggetti appartenenti a gruppi diversi siano meno simili fra 
di loro (bassa extra-similarita dei cluster) 
La discriminazione degli oggetti si avvale della valutazione degli 
attributi in base ad una misura di similarità. 
Le tecniche di clustering possono essere suddivise in grandi 
categorie: 
• Algoritmi di Partizionamento: eseguono la costruzione di 
un numero variabile di cluster, per poi valutarli e selezionare 
quelli definitivi. Prevedono la costruzione di k cluster a partire 
da un insieme di n oggetti. Il parametro k è un input del 
problema e il risultato è un partizionamento che ottimizza il 
metodo di ripartizione scelto. Un criterio generale è quello di 
 
 6
Capitolo I -Data mining  e web mining  
massimizzare la intra-similarità dei clusters e minimizzare la 
extra-similarità dei clusters. 
• Algoritmi Gerarchici: creano una decomposizione 
gerarchica del dataset. I metodi di questa classe 
raggruppano i dati in un albero di cluster e lavorano 
basandosi sulla Matrice di Similarità. Non richiedono il 
numero di cluster desiderato come input, ma necessitano 
di una condizione di interruzione, per esempio una 
distanza-soglia. Ci sono due tipi di clustering gerarchico: 
ad agglomerazione (strategia bottom-up) ed a divisione 
(strategia top-down).  
• Metodi Density-based: basandosi su connettività e 
funzioni densità, fanno “crescere” i cluster finché la 
densità di punti nel vicinato non supera un prefissato 
limite; sono in grado di trovare cluster di forma arbitraria; 
• Metodi Grid-based: sono basati su una struttura a 
livelli multipli di celle, che forma una griglia sulla quale 
vengono eseguite tutte le operazioni; le prestazioni 
dipendono solo dal numero di celle della griglia; 
• Metodi Model-based: Questa tecnica si basa 
sull’assunzione che gli oggetti siano il risultato di un 
processo di data-generating, in cui sono coinvolte diverse 
distribuzioni di probabilità. Inoltre ipotizzano un modello 
 7
Capitolo I -Data mining  e web mining  
per ciascun cluster cercando il miglior adattamento di quel 
modello con ciascun altro. 
 
1.2.1 Algoritmo K-means 
L’algoritmo k-means è una tecnica di partizionamento di un 
insieme di n oggetti in k cluster disgiunti. Inizialmente, k oggetti 
sono scelti casualmente come rappresentativi del cluster. L’algoritmo 
assegna a ciascun oggetto rimanente al cluster con il più simile 
rappresentativo. A questo punto, ciascun cluster è ricalcolato 
prendendo in considerazione la media degli oggetti interni allo stesso. 
L’algoritmo itera fino a quando altri rappresentativi non cambiano o 
qualche condizione di arresto è verificata. Spesso si sfrutta il criterio 
dell’errore quadratico. Questo richiede la minimizzazione  
∑∑
=∈
−=
k
iCp
i
i
rpE
1
2
 
dove E indica l’errore quadratico di tutti i dati, p è un generico dato e 
per ciascun i compreso tra 1 e k è il rappresentativo del cluster Ci. 
La complessità computazionale dell’algoritmo è O(nkt), con t numero 
di iterazioni. L’algoritmo, però, presenta alcuni svantaggi: 
• Il numero k deve essere conosciuto a priori 
• L’algoritmo può essere utilizzato solo quando la 
media del cluster è definita  
• È incapace di manipolare dati distorti 
 8
Capitolo I -Data mining  e web mining  
• È molto sensibile agli outliers in quanto un piccolo 
numero di essi può influenzare notevolmente il valor 
medio. 
Il k-modes è una variante del k-means che permette il clustering 
di categorie di dati. Questo è ottenuto rimpiazzando la media del 
cluster con la moda e riordinando usando un approccio frequency-
based per l’aggiornamento delle mode dei cluster. Il k-prototypes è 
una ulteriore estensione che permette il clustering di dati 
caratterizzati da numeri e attributi, come per esempio dati 
memorizzati in data base. 
 
 
1.2.2 Algoritmo k-medoid 
Il k-medoid è stato ideato per sopperire ai limiti del k-means. 
L’idea chiave fonda le sue basi sull’utilizzo dei medoids come 
elemento rappresentativo anziché la media degli oggetti del cluster. Il 
medoid non è un oggetto centrale del cluster ma un oggetto dello 
stesso che meglio lo rappresenta. Questo algoritmo somiglia molto al 
k-means. Inizialmente, sono scelti k oggetti del cluster in maniera 
casuale come medoid dei clusters. Successivamente ai clusters 
vengono assegnati i rimanti oggetti che sono più simili ai medoid 
individuati. Per ogni iterazione vengono generati nuovi medoids di 
partenza per le iterazioni successive. Il principale vantaggio è che nel 
k-medoids possono essere usate metriche e non spazi metrici, ed 
inoltre, è più robusto ai rumori e agli outliers. 
 9
Capitolo I -Data mining  e web mining  
 
1.3 Web Mining 
Il Web Mining costituisce l’area del data mining che si occupa 
dell’estrazione di conoscenza dal World Wide Web.  
Si può suddividere il Web Mining in tre sottoaree: 
1. Web Content Mining: si concentra sulle informazioni 
grezze disponibili nelle pagine web ed ha come scopo la 
classificazione e l’ordinamento delle pagine in base al 
contenuto. La fonte dei dati consiste principalmente nei 
dati testuali delle pagine web  
2. Structure Mining: si focalizza sulla struttura del sito ed ha 
come scopo la classificazione delle pagine web in base ai 
collegamenti, l’ordinamento delle pagine web attraverso 
una combinazione di contenuto e struttura ed il riverse
engineering dei modelli del sito web. La fonte dei dati 
consiste principalmente nell’informazione sulla struttura 
delle pagine web (es. collegamenti alle altre pagine). 
 
3. Web Usage Mining: si occupa dell’estrazione di conoscenza 
dai log file del web server. Le principali applicazioni sono 
basate sulle tecniche per modellare gli utenti, come la 
personalizzazione del web ed i siti web adattivi. La fonte 
dei dati consiste nei log (testuali) rappresentati in formati 
standard che vengono raccolti quando gli utenti accedono 
 10