UNIVERSITÀ DI PISA
Dipartimento di Informatica
Corso di Laurea Magistrale in Informatica per l'economia e per l'azienda
(Business Informatics)
TESI DI LAUREA
ANALISI E CORRELAZIONE DI DATI ETEROGENEI PER LA VALUTAZIONE DELL'EFFICACIA DEL SITO B2B DI UN'AZIENDA INFORMATICA
RELATORE Prof. Mirco NANNI
CANDIDATO Valentina MURGIA
L'obiettivo di questa tesi è quello di analizzare i dati del sito web di un'azienda informatica leader nel settore ICT.
Per poter raggiungere il nostro scopo, verrà svolta l'analisi del comportamento degli utenti che si collegano al sito e utilizzano lo stesso come principale canale dal quale effettuare gli acquisti.
Si vogliono profilare gli utenti sulla base delle loro azioni, e identificare eventuali miglio-ramenti da apportare al sito web al fine di renderlo uno strumento di vendita più moderno e efficace. L'analisi verrà realizzata utilizzando gli strumenti di data mining presentati nel se-condo capitolo.
Inizialmente verrà utilizzato Informatica Cloud per il recupero dei file contenenti i dati. Inoltre, prima di procedere con l'analisi vera e propria, i dati verranno sottoposti a una prima fase di preprocessing, con lo scopo di ripulirli e identificare gli utenti e le sessioni utente.
In seguito, i dati riferiti agli accessi e agli ordini verranno utilizzati per il calcolo di alcune metriche. Queste ultime verranno analizzate con il software Knime e alcuni nodi del software Weka. Il nostro fine sarà quello di classificare gli utenti in base alle abitudini di accesso e di acquisto.
Per una migliore descrizione dei contenuti delle pagine, verrà eseguito l'arricchimento semantico, che permetterà lo svolgimento dell'analisi di clustering degli utenti sulla base delle diverse aree del sito visitate e la ricerca di regole di associazione e pattern sequenziali. I risultati verranno presentati alla fine dell'elaborato attraverso alcuni grafici realizzati grazie al software Tableau.
Indice
Capitolo 1 INTRODUZIONE 1
1.1 Web e E-commerce 1
1.2 Presentazione del progetto 2
1.3 Rassegna della letteratura 3
1.4 Contenuto della tesi 4
Capitolo 2 BACKGROUND 6
2.1 Il Data mining 6
2.2 Sistemi per la gestione dei dati 10
2.3 Modelli estratti dal Data mining 12
2.4 Web mining 14
2.4.1 Tipi di dati nel Web mining 14
2.4.2 Categorie di Web mining 15
2.5 Web Usage Mining 17
2.5.1 Preprocessing 19
2.5.2 Pattern Discovery 21
2.5.3 Pattern Analysis 21
2.6 Clustering 22
2.6.1 Diversi tipi di Clustering 25
2.6.2 Diversi tipi di Cluster 27
2.6.3 K-means 29
2.7 Regole di associazione 31
2.8 Sequential pattern 33
2.9 Web Log 34
2.9.1 Struttura Web Log 35
Capitolo 3 IL CASO DI STUDIO 38
3.1 L'azienda 38 3.2 Il sito web 39 3.2.1 Il contenuto 39 3.2.2 I dati 41 Capitolo 4 PREPROCESSING 44 4.1 Software e tools 45 4.2 Preparazione dati 47
4.2.1 Tabella Access_Log 47
4.2.2 Tabella Order 48
Capitolo 5 CLUSTERING IN BASE AD ACCESSI E ORDINI 50
5.1 Prima fase: Clustering in base agli accessi 51
5.1.1 Scelta delle metriche 51
5.1.2 Scelta del valore di K 54
5.2 Seconda fase: Clustering in base agli ordini 57
5.2.1 Scelta delle metriche 57
5.2.2 Scelta del valore di K 60
5.3 Terza fase: Analisi di Clustering finale 61
5.3.1 Scelta del valore di K 61
Capitolo 6 CLUSTERING IN BASE ALLE PAGINE 64
6.1 Arricchimento semantico 64
6.2 Clustering in base alle aree del sito 67
6.2.1 Creazione matrice 67
6.2.2 Scelta del valore di K 71
Capitolo 7 PRESENTAZIONE RISULTATI 73
7.1 Risultati Clustering in base agli accessi 73
7.2 Risultati Clustering in base agli ordini 76
7.3 Risultanti analisi di Clustering finale 79
7.4 Risultati Clustering Pagine 82
Capitolo 8 REGOLE DI ASSOCIAZIONE E SEQUENZE 87
8.1 Scelta delle aree del sito 88
8.2 Ricerca delle regole di associazione 89
8.3 Ricerca sequenze 91
Capitolo 9 CONCLUSIONI E SVILUPPI FUTURI 93
9.1 Conclusioni 93
9.2 Sviluppi futuri 94
Indice delle figure
Figura 2-1 Il Data mining come un passo nel processo di Knowledge Discovery. ... 9
Figura 2-2 Web Mining Taxonomy. ... 16
Figura 2-3 The Web Usage Mining process. ... 19
Figura 2-4 Euclidean Distance Based Clustering in 3-D space. ... 23
Figura 2-5 Clustering partizionale. ... 25
Figura 2-6 Clustering gerarchico. ... 26
Figura 2-7 Density-based clusters. ... 27
Figura 2-8 Well-separated clusters. ... 28
Figura 2-9 Center-based clusters. ... 28
Figura 2-10 Contiguity-based clusters. ... 28
Figura 2-11 Conceptual clusters. ... 29
Figura 2-12 Clustering di un insieme di oggetti basato sul metodo k-means. ... 30
Figura 2-13 Association Rule Discovery. ... 31
Figura 2-14 Esempio di File Log. ... 37
Figura 2-15 Status Codes of HTTP. ... 37
Figura 3-1 Home page sito aziendale. ... 40
Figura 3-2 Modulo iscrizione sito web. ... 41
Figura 4-1 Panoramica di Informatica Cloud. ... 46
Figura 5-1 Grafico del calcolo di K. Punto di GOMITO per l'analisi della frequenza degli accessi. .. 56
Figura 5-2 Indice di Silhouette per l'analisi della frequenza degli accessi. ... 57
Figura 5-3 Grafico del calcolo di K. Punto di GOMITO per l'analisi degli ordini. ... 60
Figura 5-4 Indice di Silhouette per l'analisi della frequenza degli ordini. ... 61
Figura 5-5 Grafico del calcolo di K. Punto di GOMITO per l'analisi di FrequenzaAccessi&Ordini. ... 62
Figura 5-6 Indice di Silhouette per l'analisi di FrequenzaAccessi&Ordini. ... 62
Figura 6-1 Asegnazione categorie. ... 65
Figura 6-2 Categorie pagine. ... 66
Figura 6-3 Esempio richieste file log prima dell'arricchimento semantico. ... 66
Figura 6-4 Esempio richieste file log dopo l'arricchimento semantico. ... 67
Figura 6-5 Esempio tabella con numero richieste per utente, sessione e categoria. ... 68
Figura 6-6 Esempio tabella con numero complessivo delle richieste per utente e categoria. ... 69
Figura 6-7 Esempio matrice... 70
Figura 6-8 Elenco categorie considerate durante l'analisi. ... 71
Figura 6-9 Grafico del calcolo di K per l'analisi delle pagine. ... 72
Figura 6-10 Indice di Silhouette per l'analisi delle pagine. ... 72
Figura 7-1 Diagramma a torta analisi accessi. ... 74
Figura 7-2 Valori medi metriche analisi accessi. ... 74
Figura 7-3 Valori minimi e massimi analisi accessi. ... 75
Figura 7-4 Diagramma a torta analisi ordini. ... 77
Figura 7-5 Valori medi metriche analisi ordini. ... 77
Figura 7-6 Valori minimi e massimi metriche analisi ordini. ... 78
Figura 7-7 Diagramma a torta Cluster analisi completa. ... 79
Figura 7-8 Valori medi analisi completa. ... 80
Figura 7-9 Valori min e max analisi completa metriche accessi... 81
Figura 7-11 Diagramma a torta Cluster aree sito. ... 83
Figura 7-12 Primo cluster aree sito. ... 83
Figura 7-13 Secondo cluster aree sito. ... 84
Figura 7-14 Terzo cluster aree sito. ... 84
Figura 7-15 Quarto cluster aree sito. ... 85
Figura 7-16 Quinto cluster aree sito... 85
Figura 7-17 Sesto cluster aree sito. ... 86
Figura 8-1 Pagine considerate per la ricerca di regole di associazione. ... 88
Figura 8-2 Sequenze frequenti. ... 91
Indice delle tabelle
Tabella 1 Association rules. ... 901
Capitolo 1
INTRODUZIONE
1.1 Web e E-commerce
Negli ultimi anni, grazie alla sua rapida crescita, il Web è diventato la più grande fonte di informazione disponibile. L'elevato numero di pagine dalle quali è composto, oltre ad aver rivoluzionato la ricerca delle informazioni, passate dalla consultazione di testi scritti all'uti-lizzo dei motori di ricerca, ha permesso la loro condivisione e, soprattutto, lo ha reso uno dei principali canali commerciali grazie alla possibilità di vendere e acquistare prodotti e servizi direttamente in rete.
La crescente disponibilità, facilità e popolarità degli affari condotti sul Web permette la raccolta di enormi quantità di dati riguardanti vendite, cronologia degli acquisti, consumi e servizi.
Alcune aziende, esempio Amazon.com, svolgono la loro attività esclusivamente online, senza alcun negozio fisico. Questo permette loro di concentrarsi principalmente sul miglio-ramento dell'esperienza del cliente nel sito, personalizzando le pagine sulla base degli inte-ressi e dei desideri dell'utente.
Col passare del tempo ci si è resi conto che l'e-commerce non è solo l'acquisto e la vendita su Internet, ma offre la possibilità ad aziende e clienti di interagire eliminando le barriere del tempo e dello spazio, migliorando in questo modo anche l'efficienza e la competitività sul mercato.
2
Oltre a Amazon.com, ci sono altri siti e-commerce che hanno avuto successo negli anni, si pensi ad esempio a eBay.com e ePRICE.it. Tuttavia, i modelli di siti e-commerce possono essere diversi.
Contrariamente a quanto si possa pensare, sito e-commerce non è sinonimo di vendita di prodotti online. Sono considerati siti e-commerce anche quelli che si occupano di vendita di spazi pubblicitari, sottoscrizioni (esempio i siti di quotidiani), sponsorizzazioni, concessione di licenze, affiliazione.1
I dati raccolti attraverso le attività di e-commerce forniscono una ricca fonte di dati. Il Data mining, e in particolare il Web mining, può fornire un grosso aiuto per scoprire i mo-delli di acquisto e le tendenze dei clienti, migliorare la qualità del servizio clienti, ottenere una migliore fidelizzazione e soddisfazione dei clienti.
1.2 Presentazione del progetto
Il sito web analizzato durante il progetto che verrà presentato in questo elaborato è un sito e-commerce di una grossa azienda leader nel settore ICT. Le sue numerose visite giornaliere consentono la raccolta di milioni di dati annuali e la necessità di una costante analisi.
Per una questione di tempistica, verranno analizzati soltanto i dati riferiti agli ultimi tre mesi del 2017. Lo scopo è quello di individuare eventuali punti di forza e/o di debolezza da presentare ai responsabili che si occuperanno di indirizzare la strategia aziendale.
Dopo l'estrazione dei dati, il processo di analisi si suddividerà in diverse fasi.
La prima fase riguarderà la pulizia del file log e l'individuazione delle sessioni utente che verranno poi utilizzate per l'analisi di clustering. In questa fase verranno calcolate alcune metriche riferite alle abitudini di visita del sito web da parte degli utenti, con lo scopo di attribuire loro un'etichetta sulla base del risultato ottenuto.
3
Nella seconda fase verranno analizzati i dati degli ordini dell'ultimo trimestre 2017. An-che in questo caso verranno calcolate alcune metriAn-che An-che riguarderanno le abitudini di ac-quisto dei clienti che utilizzano il sito web aziendale per effettuare gli ordini.
I risultati ottenuti durante queste due fasi, verranno utilizzati come input della terza fase che riguarderà un'ulteriore analisi di clustering con il fine di poter individuare alcuni profili utente interessanti.
Al termine dei punti precedenti, ci si concentrerà sulle diverse aree del sito maggiormente visitate dagli utenti. In particolare, inizialmente verrà eseguito l'arricchimento semantico, successivamente ci si concentrerà sull'analisi di clustering e la ricerca di regole di associa-zione e sequenze frequenti.
Per ragioni di privacy l'azienda ha richiesto di rimanere anonima. Pertanto, durante l'in-tera stesura dell'elaborato, non ne verrà citato il nome e verranno volutamente modificati alcuni contenuti.
1.3 Rassegna della letteratura
Durante lo svolgimento del progetto sono stati consultati alcuni testi di Data mining e di Web mining, alcuni articoli reperiti nel web e alcuni esempi e guide riguardanti i software utilizzati.
In particolare, per quanto riguarda il capitolo dedicato al background (Capitolo 2), i testi che hanno fornito un maggiore contributo sono quelli di [Tan 06], [Han 11], [Liu 11] e [Sri-vastava 05].
Per la descrizione e l'analisi del file log sono stati utilizzati il testo di [Vasta 10] e alcuni articoli scaricati dal web (i principali sono quelli di [Suneetha 09] e [Joshila Grace 11]).
4
Per quanto riguarda gli strumenti utilizzati per lo svolgimento delle analisi (Informatica cloud e Knime), si è preso spunto da alcuni esempi e dalle relative guide presenti nei siti web ufficiali.
Tutte le fonti sono state citate nella bibliografia.
1.4 Contenuto della tesi
Oltre a questo primo capitolo contenente un'introduzione sull'e-commerce e una breve sintesi riguardante il contenuto del progetto e le analisi svolte, l'elaborato si compone di altri otto capitoli.
Nel Capitolo 2 verranno presentati alcuni concetti e strumenti che verranno utilizzati du-rante le fasi salienti del progetto. Lo scopo di questo capitolo è quello di facilitare la com-prensione degli argomenti esposti nei capitoli successivi e permettere ai meno esperti di ac-quisire una conoscenza base delle materie trattate durante la stesura dell'elaborato.
In particolare, si introdurrà la definizione di Data mining (2.1) e Web mining (2.4), soffer-mandosi sul Web usage mining (2.5) e sulle tecniche di Data mining (Clustering 2.6, Regole di associazione 2.7 e Sequential pattern 2.8) utilizzate durante l'analisi delle tabelle conte-nenti i dati del file log (2.9) e degli ordini.
Il Capitolo 3 fornirà alcune informazioni riguardanti l'azienda e il sito web aziendale. In particolare, verrà presentata la missione dell'azienda (3.1) e il contenuto del sito web e della struttura delle tabelle utilizzate durante la fase di elaborazione dei dati (3.2).
Il Capitolo 4 presenterà gli strumenti utilizzati durante le fasi di recupero delle tabelle necessarie per l'analisi (4.1) e quelli necessari per la preparazione e l'elaborazione (4.2). Nell'ultimo paragrafo (4.3) verrà affrontata la fase di preprocessing, in cui i dati della tabella del file log verranno ripuliti per eliminare le righe non necessarie al fine dell'analisi, e dell'i-dentificazione delle sessioni utente.
5
Il Capitolo 5 tratterà l'analisi di clustering effettuata sulle tabelle oggetto di preprocessing durante il capitolo precedente. L'analisi sarà divisa in tre fasi, la prima riguarderà la tabella contenente i dati del file log (5.1), la seconda fase si occuperà dell'analisi della tabella degli ordini (5.2), la terza utilizzerà i risultati delle due fasi precedenti come input per un'ulteriore analisi di clustering (5.3).
Nel Capitolo 6 ci si concentrerà sulle diverse aree del sito. In particolare, ci si occuperà dell'arricchimento semantico (6.1) e dell'analisi di clustering (6.2).
Nel Capitolo 7 verranno presentati i risultati delle analisi di clustering. Inizialmente ci si concentrerà sull'analisi riguardante la frequenza di accesso e utilizzo del sito (7.1), segui-ranno i paragrafi sull'analisi delle abitudini di acquisto (7.2), l'analisi di clustering finale (7.3) e l'analisi riguardante le abitudini di navigazione degli utenti (7.4).
Nel Capitolo 8 verranno selezionate le aree del sito di maggiore interesse (8.1) e ricercate alcune regole di associazione (8.2) e pattern sequenziali (8.3) riguardanti queste aree. Lo scopo sarà quello di trovare informazioni interessanti sulle combinazioni più frequenti delle pagine navigate degli utenti.
6
Capitolo 2
BACKGROUND
La nostra è stata definita l'era dell'informazione. Viviamo in un mondo in cui giornal-mente vengono prodotte e raccolte enormi quantità di dati. La costante crescita del volume di dati prodotti non è altro che il risultato dell'informatizzazione e dello sviluppo di strumenti e mezzi per la raccolta e l'archiviazione dei dati.
Si pensi alla grossa quantità di dati prodotta giornalmente dalle aziende (transazioni di vendita, descrizioni di prodotti, promozioni di prodotti e servizi, feedback dei clienti), dai social media e dalle community (ormai diventati quasi fonti di dati primarie), dalle ricerche effettuate attraverso i motori di ricerca. L'elenco delle fonti è infinito.
Questa grande produzione e raccolta di dati ha reso necessario lo sviluppo di strumenti che permettessero una facile e veloce elaborazione dei dati al fine di trasformarli in infor-mazioni utilizzabili e, quindi, in conoscenza.
2.1 Il Data mining
Il Data mining può essere visto come risultato della naturale evoluzione della tecnologia dell'informazione. Grazie alla sua natura multidisciplinare, può essere definito in modi di-versi.
7 “l'insieme di tecniche e metodologie che hanno per oggetto l'estrazione di una informa-zione o di una conoscenza a partire da grandi quantità di dati (attraverso metodi automa-tici o semi-automaautoma-tici) e l'utilizzo scientifico, industriale o operativo di questa
informa-zione”2.
Spesso il Data mining viene considerato sinonimo di un altro termine, Knowledge Disco-very in Databases, o KDD.
“Il KDD è il processo di identificazione di una struttura valida, potenzialmente utile e alla fine comprensibile nei dati. Questo processo comporta la selezione o il campiona-mento di dati da un data warehouse, la pulizia o preelaborazione, la trasformazione o la
riduzione (se necessario), l'applicazione di un componente di Data mining per produrre una struttura, e quindi la valutazione della struttura derivata”3.
Altri considerano il Data mining come un passaggio essenziale nel processo di Know-ledge Discovery, suddividendo l'esecuzione del Data mining in tre fasi principali:
Pre-processing: I dati grezzi di solito non sono adatti per l'estrazione; affinché questo possa esser reso possibile, potrebbe essere necessario rimuovere rumori o anomalie. La dimensione dei dati può anche essere troppo elevata e/o coinvolgere molti attributi irrilevanti, per questo motivo potrebbe essere richiesta una ridu-zione dei dati tramite il campionamento e la seleridu-zione di attributi o caratteristiche. Data mining: Una volta terminata la fase di pre-processing, i dati elaborati
ven-gono inviati a un algoritmo di Data mining che produce pattern o conoscenza. Post-processing: Questa fase ha lo scopo di identificare i pattern utili per le
ap-plicazioni. Per ausilio alle decisioni vengono utilizzate varie tecniche di valuta-zione e visualizzavaluta-zione. L'intero processo di Data mining è quasi sempre iterativo. Sono necessari diversi step per raggiungere il risultato finale soddisfacente.
2 Definizione Wikipedia: https://it.wikipedia.org/wiki/Data_mining 3 A. K Pujari, Data mining Techniques, Universities Press, 2001.
8
Possiamo rappresentare i diversi passi del processo KDD attraverso la Figura 2-1. Ogni passo rappresentato nella figura ha un determinato compito.
1. Data cleaning: il suo scopo è quello di rimuovere il rumore e i dati inconsistenti; 2. Data integration: il suo scopo è quello di combinare più fonti di dati;
3. Data selection: in questa fase i dati rilevanti per l'attività di analisi vengono re-cuperati dal database;
4. Data transformation: durante la fase di trasformazione i dati vengono trasfor-mati e consolidati in moduli appropriati per l'esecuzione del mining, eseguendo operazioni di riepilogo o aggregazione;
5. Data mining: durante questo processo vengono applicati i metodi necessari per estrarre i modelli di dati;
6. Pattern evaluation: processo che ha lo scopo di identificare i modelli interessanti che rappresentano la conoscenza sulla base di misure di interesse;
7. Knowledge presentation: in questa fase vengono presentate agli utenti le cono-scenze estratte grazie all'utilizzo di tecniche di visualizzazione e di rappresenta-zione della conoscenza.
9 Figura 2-1 Il Data mining come un passo nel processo di Knowledge Discovery.
Il passo 1 e il passo 4 appartengono alla fase di pre-processing dei dati in cui i dati ven-gono preparati per l'estrazione. La fase di Data mining può interagire con l'utente o una base di conoscenza (knowledge base). Gli schemi considerati interessanti vengono presentati all'utente e possono essere memorizzati come nuove conoscenze nella base di conoscenza.
I dati ai quali può essere applicato il Data mining sono diversi; tra questi vi sono: database, data warehouse e i dati transazionali.
Oltre a quelli appena citati, il Data mining può anche essere applicato ad altre forme di dati (ad esempio, flussi di dati, dati ordinati/sequenza di dati, grafici o dati di rete, dati spa-ziali, dati di testo, dati multimediali e WWW).
10
2.2 Sistemi per la gestione dei dati
Nelle prossime righe verranno descritti sinteticamente i sistemi per la gestione di dati più comunementeadottati in ambito business.
DATABASE
Un sistema di Database, chiamato anche Database Management System (DBMS), consi-ste in una raccolta di database e un insieme di programmi software per la gestione dei dati e per consentire l'accesso agli stessi.
Il DBMS offre opportuni linguaggi per:
definire lo schema di una base di dati (lo schema va definito prima di creare dati); scegliere le strutture dati per la memorizzazione dei dati;
memorizzare i dati rispettando i vincoli definiti nello schema;
recuperare e modificare i dati interattivamente (linguaggio di interrogazione o query language) o da programmi.4
Un Database relazionale è una raccolta di tabelle con nome univoco. Ogni tabella è com-posta da un insieme di attributi (colonne o campi) che spesso memorizza una grande quantità di record.
Ogni record non è altro che un oggetto che viene identificato da una chiave univoca e descritto da un insieme di valori di attributo. Per i database relazionali è spesso costruito un modello di entità-relazione (ER). Questo modello di dati ER rappresenta il database come un insieme di entità e le loro relazioni.
DATA WAREHOUSE
Secondo la definizione di William H. Inmon (informatico statunitense considerato il pa-dre del Data warehouse) un Data Warehouse è:
11 "una raccolta di dati orientata al soggetto, integrata, variabile nel tempo e non volatile
a supporto del processo decisionale".
Orientata al soggetto. Un Data Warehouse è organizzato intorno a soggetti impor-tanti come clienti, prodotti, vendite ecc, e si concentra sulla modellazione e l'ana-lisi dei dati per i responsabili delle decisioni. La differenza tra data warehouse e database operativo riguarda il fatto che i primi memorizzano i dati per argomento, i secondi memorizzano i dati per applicazioni.
Integrata. I dati vengono raccolti nel Data Warehouse integrando più fonti etero-genee. I dati vengo ripuliti e integrati in modo da garantire che vengano riuniti in un insieme coerente. Lo scopo di queste tecniche è quello di rendere i dati omo-genei e accessibili da parte dei decisori aziendali.
Variabile nel tempo. I dati contenuti nel Data Warehouse vengono utilizzati per effettuare analisi e supportare le decisioni. A tal proposito, i dati vengono archi-viati per fornire informazioni da una prospettiva storica (esempio, gli ultimi 5-10 anni).
Non volatile. I dati in un Data Warehouse vengono utilizzati principalmente per eseguire query e analisi, non vengono mai modificati. Un Data Warehouse è sem-pre un archivio di dati fisicamente separato dai dati trovati nell'ambiente opera-tivo. Di solito richiede solo due operazioni, caricamento iniziale dei dati e accesso.
TRANSACTIONAL DATA
In un database transazionale ogni record si riferisce a una transazione (esempio, l'acquisto da parte di un cliente) che generalmente include un numero identificativo univoco e un elenco di item (esempio, prodotti acquistati). È anche possibile che un database transazionale abbia ulteriori tabelle contenenti informazioni aggiuntive (esempio, descrizione prodotti).
12
DATI COMPLESSI
Ci possono essere altri dati che si prestano ad essere analizzati dal Data mining.
Questi dati, denominati complessi, di solito non vengono gestiti dai sistemi sopracitati e possono comprendere: dati relativi al tempo o alla sequenza (ad esempio, record storici, dati di borsa e serie temporali, dati di sequenza biologica), flussi di dati (ad esempio, dati di videosorveglianza e sensori trasmessi in modo continuo), dati spaziali (esempio mappe), dati di progettazione tecnica (ad esempio, progettazione di edifici, componenti di sistema o cir-cuiti integrati), ipertesto e dati multimediali (inclusi testo, immagini, video e dati audio), dati grafici e di rete (esempio, reti sociali e informative) e il Web (un enorme archivio di infor-mazioni ampiamente distribuito reso disponibile da Internet).5
2.3 Modelli estratti dal Data mining
Ci sono diversi modelli che possono essere estratti grazie al Data mining. Le numerose funzionalità di Data mining includono:
la caratterizzazione e la discriminazione. Strumenti che permettono di descrivere i dati del database in modo sintetico e preciso. La caratterizzazione descrive le caratteristiche di una classe; la discriminazione mette in evidenza quelle che sono le differenze tra una classe e le altre classi attraverso il confronto diretto dei dati. analisi associativa. Analisi grazie alla quale è possibile identificare la presenza di
condizioni che si verificano contemporaneamente con elevata frequenza.
Rileva pattern che si ripetono su determinati attributi e ne deriva regole di impli-cazione del tipo A ⇒ B.
13
La significatività delle associazioni viene valutata in base alla Confidence, che misura la certezza del pattern, e al Support, che misura la frequenza con cui il pattern è presente sulla base di dati.
classificazione e predizione. Processo di ricerca di un modello (basato sull'analisi di dati di training) che descrive e distingue classi di dati. Il modello viene utiliz-zato per prevedere l'etichetta di classe degli oggetti la cui classe è sconosciuta. analisi di clustering. Il clustering analizza gli oggetti senza considerare le etichette
di classe che, in molti casi, potrebbero anche non essere presenti all'inizio dell'a-nalisi. Gli oggetti vengono raggruppati in modo che venga massimizzata la simi-larità intraclasse e minimizzata la simisimi-larità interclasse.
analisi outlier. Un insieme di dati potrebbe contenere al suo interno valori ano-mali, cioè non conformi al comportamento generale o al modello dei dati. Alcuni metodi di Data mining scartano questi valori anomali. Tuttavia, per alcune appli-cazioni, gli eventi rari possono rivelarsi più interessanti di quelli più frequenti. L'analisi dei dati anomali viene definita analisi degli outlier. I valori anomali pos-sono essere rilevati utilizzando test statistici che assumono un modello di distri-buzione o probabilità per i dati o misure di distanza in cui gli oggetti lontani da qualsiasi altro cluster vengono considerati valori anomali.
Le funzionalità di Data mining vengono utilizzate per specificare i tipi di pattern da tro-vare nelle attività di Data mining.
In base all'obiettivo dell'analisi, possiamo distinguere tra Data mining predittivo o de-scrittivo.
Nel primo caso lo scopo è quello di approfondire la conoscenza di ciò che avviene all'in-terno dei dati e quindi di ciò che gli stessi rispecchiano.
14
Nel caso del Data mining predittivo l'obiettivo è quello di automatizzare il processo de-cisionale creando un modello che sia in grado di prevedere, assegnare un'etichetta o stimare un valore.
2.4 Web mining
Nell'ultimo decennio sempre più aziende si sono rese conto che quando si parla di l'e-commerce non ci si riferisce solo alla vendita online. L'e-l'e-commerce, infatti, è anche un im-portante strumento col quale poter aumentare l'efficienza e, di conseguenza, la posizione sul mercato rispetto ai competitors.
L'incremento nell'utilizzo del web ha portato all'aumento della quantità di dati semi-strut-turati e eterogenei raccolti e memorizzati. Questi dati possono riguardare documenti web, hyperlink tra documenti, il web log del sito ecc.
2.4.1 Tipi di dati nel Web mining
I dati raccolti dalle diverse fonti possono essere suddivisi in quattro gruppi.
Usage Data. I dati del log raccolti automaticamente dal Web server e dall'applica-tion server sono la fonte primaria di dati e rappresentano il comportamento di navigazione dei visitatori. Ogni hit6 genera una singola registrazione nei log di
accesso del server. In base agli obiettivi dell'analisi, i dati devono essere trasfor-mati e aggregati a diversi livelli di astrazione. Nel Web usage mining, il livello di base dell'astrazione dei dati è quello di una pageview7.
6 Quando una pagina web viene visitata si verifica un "hit", cioè la pagina viene trovata dal browser. Nel
mo-mento in cui questo accade, il server invia al computer dell'utente la pagina HTML e tutti i file contenuti al suo interno (immagini, suoni ecc).
15
Content Data. Questi dati, all'interno di un sito web, sono la raccolta di oggetti e relazioni trasmessa all'utente. Sono composti principalmente da combinazioni di materiali testuali e immagini e vengono forniti o generati da pagine HTML/XML statiche, file multimediali, segmenti di pagina generati dinamicamente da script e raccolte di record dai database operazionali.
Structure Data. Rappresentano l'organizzazione dei contenuti all'interno del sito. Questa organizzazione viene catturata attraverso la struttura di collegamento in-ter-page tra le pagine, collegamenti ipertestuali (hyperlinks). I dati della struttura includono anche la struttura intra-page del contenuto all'interno di una pagina. User Data. I database operativi per il sito possono includere informazioni
aggiun-tive riguardanti gli utenti. Questi dati possono comprendere informazioni demo-grafiche, valutazioni degli utenti su vari oggetti, informazioni sugli acquisti pre-cedenti o la cronologia delle visite, informazioni su diversi interessi degli utenti. Alcuni di questi dati possono essere raccolti in modo anonimo.
2.4.2 Categorie di Web mining
Possiamo definire il Web mining come l'applicazione di tecniche di Data mining per estrarre conoscenza dai dati web. Sulla base dei dati che si vogliono estrarre, il Web mining può essere suddiviso in tre categorie (Figura 2-2): Web Content Mining, Web Structure Mi-ning, Web Usage Mining.
16 Figura 2-2 Web Mining Taxonomy.
WEB CONTENT MINING
Il continuo incremento del numero di documenti html, immagini e altri file multimediali dovuti allo sviluppo del World Wide Web, ha reso sempre più complicato il recupero di contenuti interessanti. I contenuti presenti sul web sono vari e possono riguardare testi, im-magini, audio, video o record strutturati come elenchi e tabelle.
Il Web Content mining è il processo che permette di estrarre informazioni utili dai conte-nuti dei documenti Web. I dati possono essere strutturati (Database, tabelle), semi strutturati (HTML) o non strutturati (testi). Nel Web Content mining vengono usate tecniche di Text mining per la scoperta di argomenti, estrazione di pattern di associazione, clustering di do-cumenti web e classificazione di pagine web. Il Text mining è considerato l'estensione del Data mining tradizionale in fonti non strutturate, il suo scopo è l'estrazione di informazioni implicitamente contenute in un insieme di documenti.
17
WEB STRUCTURE MINING
Il Web Structure Mining è il processo per scoprire le informazioni sulla struttura del Web. Questo può essere ulteriormente suddiviso in due tipi in base al tipo di informazioni sulla struttura utilizzata.
Hyperlink: un hyperlink è un rinvio da una posizione in una pagina web a una posizione diversa, all'interno della stessa pagina o su una pagina diversa. Un hy-perlink che si connette a una parte diversa della stessa pagina viene chiamato in-tra-document hyperlink, un hyperlink che connette due pagine diverse è chiamato inter-document hyperlink.
Document Structure: il contenuto di una pagina web può anche essere organizzato in un formato tridimensionale, basato sui vari tag HTML e XML all'interno della pagina.
WEB USAGE MINING
Il Web Usage Mining è quel processo di Data mining che si occupa di scoprire, modellare e analizzare i comportamenti e i profili degli utenti che interagiscono con un sito web. Queste informazioni vengono reperite principalmente dai file log del web server.
Nel prossimo paragrafo tratteremo nel dettaglio alcuni aspetti del Web Usage Mining.
2.5 Web Usage Mining
Con la continua crescita dell'e-commerce, anche il volume dei dati riguardanti l'utilizzo dei siti web ha raggiunto proporzioni importanti. Il Web Usage Mining (WUM) ha lo scopo di estrarre informazioni sull'utilizzo dei siti web da parte degli utenti attraverso l'analisi dei file log.
18
I modelli scoperti riguardano spesso insiemi di pagine, oggetti o risorse alle quali fanno spesso accesso gruppi di utenti con interessi comuni.
Il World Wide Web Committe (W3C) ha definito diverse astrazioni dei dati che possono essere utili per il Web Usage Mining. Questi dati sono: pageview, server session, click-stream, user session e user episode.
Pageview: è l'insieme di tutti i file che contribuiscono al risultato visualizzato da un utente durante la navigazione.
Clickstream: è la sequenza delle pageviews a cui ha avuto accesso un utente. User session: è il clickstream delle pageviews per un singolo utente.
Server session: è l'insieme delle pageviews in una user session per un determinato sito.
User episode: è riferito a un sottoinsieme di pageviews in una user session. Le fasi del Web Usage Mining sono tre (Figura 2-3): preprocessing, pattern discovery, pattern analysis.
La prima fase si occupa della preparazione dei dati del web log. Questi vengono ripuliti con lo scopo di identificare le sessioni utente e le azioni svolte da questi durante le visite al sito.
La fase di pattern discovery riguarda l'applicazione di alcune tecniche di Data mining ai dati ottenuti nella fase di preprocessing con il fine di ottenere dei modelli che rispecchino le abitudini comportamentali degli utenti che visitano il sito.
L'ultima fase si occupa dell'analisi dei pattern scoperti. Questi modelli possono anche essere utilizzati come input di altre applicazioni (Web analytics, Report, strumenti di visua-lizzazione).
19 Figura 2-3 The Web Usage Mining process.
2.5.1 Preprocessing
Il Preprocessing è sicuramente il compito più importante e più dispendioso. Questa fase comprende le attività di Cleaning, User Identification e Session Identification.
CLEANING
All'interno del file di log è presente un'hit per ogni file che viene richiesto. Una pagina web può essere composta da diversi file (testo, immagini, suoni, diversi fotogrammi), ma, affinché l'analisi possa essere svolta correttamente, è necessario tenere traccia solo del file espressamente richiesto dall'utente.
20
La fase di cleaning (pulizia) è una funzione che permette di eliminare dal web log tutte le richieste non necessarie ai fini dell'analisi. Durante questa fase devono essere eliminate an-che le sessioni di navigazione eseguite da web crawler, robot e spider8 e le voci del registro che hanno un codice di stato di serie 400 e 5009.
Il processo di cleaning può richiedere anche la rimozione di alcuni campi presenti nel file di log (esempio il numero di byte trasferiti e la versione del protocollo http utilizzato ecc) in quanto non contenenti informazioni utili.
USER IDENTIFICATION
Un altro problema da affrontare durante la fase di Preprocessing è l'identificazione degli utenti.
L'analisi di Web Usage Mining non richiede che sia nota l'identità dell'utente, ma è im-portante poter distinguere i diversi visitatori che navigano il sito web. I log server registrano più sessioni per ciascun utente. Qualora il sito web sia sprovvisto di meccanismi di identifi-cazione, l'approccio più diffuso per distinguere i visitatori è l'uso di cookie lato client. Tut-tavia, i cookie non sono utilizzati da tutti i siti web e spesso vengono cancellati o disabilitati dagli utenti.
Gli indirizzi IP non sono sufficienti per identificare i visitatori unici. I server proxy ISP (internet service provider) assegnano indirizzi IP ai client che navigano in rete. Pertanto, due occorrenze dello stesso IP potrebbero corrispondere a utenti differenti. Un modo per poter sfruttare l'indirizzo IP per identificare un utente è quello di combinare l'IP con l'informazione del browser agent in modo da suddividere il file log in record di attività per utenti separati.
Infine, un'altra soluzione utile potrebbe essere quella di identificare gli utenti attraverso l'inserimento di login e password. Tuttavia, non tutti i siti possono fare ciò in quanto spesso
8 I Web crawler (detti anche robot o spider) sono dei software che analizzano i contenuti di una rete per conto
dei motori di ricerca al fine di poterne indicizzare il contenuto.
9 Queste richieste vengono eliminate perché corrispondono, rispettivamente, a richieste sintatticamente
21
gli utenti sono restii a fornire informazioni personali per effettuare la registrazione in un sito web.
SESSION IDENTIFICATION
Una volta identificati gli utenti, il passo successivo riguarda l'identificazione delle ses-sioni.
L'obiettivo dell'identificazione della sessione è quello di dividere gli accessi alle pagine di ciascun utente in singole sessioni. Una sessione comprende un gruppo di attività che ven-gono svolte da un certo utente durante la navigazione in un sito web.
Una regola utilizzata durante l'identificazione delle sessioni, è quella di suddividere il flusso di click in due sessioni quando si presenta un intervallo di 30 minuti tra la visualizza-zione di due pagine oppure quando scatta la mezzanotte durante la navigavisualizza-zione. Sono con-siderate due sessioni differenti anche le richieste fatte a cavallo della mezzanotte.
2.5.2 Pattern Discovery
Il Web Usage Mining può essere utilizzato per scoprire pattern nei server log. È necessa-rio che i dati del campione su cui eseguire il processo di Data mining siano rappresentativi dell'insieme dei dati affinché questo risulti efficace.
I metodi di scoperta dei pattern sono: Analisi statistica, Regole di associazione, Cluste-ring, Classificazione, Pattern sequenziali e Modelli di dipendenza.
2.5.3 Pattern Analysis
In questa fase vengono valutati i modelli ottenuti nella fase precedente. L'analisi ha lo scopo di filtrare e eliminare regole e pattern non interessanti.
22
L'analisi statistica dei dati costituisce la forma più comune di analisi. Durante questa fase i dati vengono aggregati in unità predeterminate (giorni, sessioni, visitatori o domini).
L'analisi può acquisire informazioni sul comportamento degli utenti che visitano il sito. Alcune informazioni che possono essere incluse nei report riguardano le pagine a cui si ac-cede più frequentemente, il tempo medio di visualizzazione di una pagina, la lunghezza me-dia di un percorso attraverso un sito, i punti di entrata e uscita comuni e altre misure aggre-gate. La conoscenza appresa può essere utilizzata come supporto alle decisioni di marketing.
Un'altra forma di analisi sui dati è l'Online Analytical Processing (OLAP), che fornisce una struttura più integrata per l'analisi con un maggiore grado di flessibilità.
L'origine dei dati per l'analisi OLAP è solitamente un Data Warehouse multidimensionale che integra dati a diversi livelli di aggregazione per ciascuna dimensione. Le dimensioni di analisi in questa struttura possono essere basate su vari campi disponibili nei file log e questo permette l'esecuzione di analisi su parti del log relative a un intervallo di tempo specifico o a un livello più alto di astrazione rispetto alla struttura del percorso dell'URL.
2.6 Clustering
La Cluster Analysis è il processo di partizionamento di un insieme di oggetti dati in sot-toinsiemi. Ogni sottoinsieme è un cluster, gli oggetti in un cluster sono simili tra loro, ma diversi dagli oggetti presenti in altri cluster (Figura 2-4). L'insieme dei cluster risultante da un'analisi di clustering può essere definito clustering.
23 Figura 2-4 Euclidean Distance Based Clustering in 3-D space.
Diversi metodi di clustering possono generare cluster differenti sullo stesso set di dati. Il partizionamento viene eseguito dall'algoritmo di clustering. Il clustering è utile in quanto può portare alla scoperta di gruppi precedentemente sconosciuti all'interno dei dati.
Il problema del clustering è detto non supervisionato in quanto all'interno del set non è presente un target e attribuire una classe affidabile è spesso difficile e costoso.
Alcuni requisiti del clustering nel Data mining sono:
Scalabilità. Molti algoritmi di clustering funzionano bene su piccoli set di dati; tuttavia, un database di grandi dimensioni può contenere milioni o addirittura mi-liardi di oggetti. Sono necessari algoritmi di clustering altamente scalabili per po-ter ottenere dati non distorti da dataset di dimensioni importanti.
Capacità di gestire diversi tipi di attributi. Molti algoritmi sono progettati per rag-gruppare dati numerici. Tuttavia, le applicazioni possono richiedere il clustering di dati binari, nominali e ordinali, o mix di questi tipi di dati. Sempre più applica-zioni richiedono tecniche di clustering per tipi di dati complessi come grafici, se-quenze, immagini e documenti.
24
Individuazione di cluster con forme arbitrarie. Molti algoritmi di clustering deter-minano cluster basati su misure di distanza Euclidea10 o Manhattan11. Gli algo-ritmi basati su tali misure di distanza tendono a trovare cluster sferici con dimen-sioni e densità simili. Tuttavia, un cluster potrebbe essere di qualsiasi forma. Richieste minime sulla conoscenza del dominio per determinare i parametri di
input. Molti algoritmi di clustering richiedono di fornire parametri di input come il numero desiderato di cluster. Di conseguenza, i risultati del clustering potreb-bero essere influenzati da questi parametri. La determinazione di questi ultimi non è sempre semplice, soprattutto per i set di dati di grandi dimensioni e in cui non si conoscono ancora bene i dati.
Capacità di gestire dati rumorosi. Gli algoritmi di clustering possono essere sen-sibili al rumore e produrre risultati di scarsa qualità. È importante avere a dispo-sizione dei metodi di cluster robusti e in grado di non essere influenzati dalla pre-senza di rumore nei dati.
Cluster incrementale e insensibilità all'ordine di input. Alcuni algoritmi di cluste-ring non possono incorporare dati più recenti all'interno di strutture di clustecluste-ring esistenti e devono ricalcolare da zero un nuovo clustering. Gli algoritmi di cluste-ring possono anche essere sensibili all'ordine dei dati di input. Sono necessari al-goritmi di cluster incrementale e insensibili all'ordine di input.
Elevata dimensionalità. Un set di dati può contenere numerose dimensioni o attri-buti. La maggior parte degli algoritmi di clustering sono in grado di gestire dati di
10Euclidean distance. Sianoi = (x
i1, xi2, … , xip) e j = (xj1, xj2, … , xjp)due oggetti descritti da p attributi
nu-merici.
La distanza Euclidea tra l'oggetto i e l'oggetto j è definite come 𝑑(𝑖, 𝑗) = √(𝑥𝑖1− 𝑥𝑗1)2+ (𝑥𝑖1− 𝑥𝑗1)2+ ⋯ + (𝑥𝑖𝑝− 𝑥𝑗𝑝)2.
11Manhattan distance. È definita come
𝑑(𝑖, 𝑗) = |𝑥𝑖1− 𝑥𝑗1| + |𝑥𝑖2− 𝑥𝑗2| + ⋯ + |𝑥𝑖𝑝− 𝑥𝑗𝑝|.
25
piccole dimensioni. Trovare cluster di oggetti in uno spazio ad elevata dimensio-nalità è difficile, soprattutto se si considera che tali dati possono essere molto scarsi e altamente distorti.
Cluster basato su vincoli. Alcuni clustering potrebbero dover essere eseguiti nel rispetto di alcuni vincoli. È importante trovare gruppi di dati con un buon com-portamento di clustering che soddisfino i vincoli specificati.
Interpretabilità e usabilità. I risultati del clustering devono essere interpretabili, comprensibili e utilizzabili. È importante studiare in che modo un obiettivo può influenzare la selezione delle funzionalità di clustering e dei metodi di clustering.
2.6.1 Diversi tipi di Clustering
In letteratura sono presenti diversi metodi di clustering, alcuni di questi possono sovrap-porsi e rendere difficile una categorizzazione ben distinta. Nelle prossime righe verranno presentati i metodi di clustering principali.
Clustering partizionale. Dato un database di n oggetti, un metodo di partiziona-mento costruisce k partizioni dei dati, dove ciascuna partizione rappresenta un cluster, e k ≤ n. I k gruppi in cui sono classificati i dati devono contenere almeno un oggetto e ciascun oggetto deve appartenere esattamente ad un gruppo.
Figura 2-5 Clustering partizionale.
Clustering gerarchico. Se ai cluster è consentito di avere sottocluster, otteniamo un insieme di cluster annidati che sono organizzati come un albero. In base a come vengono formati i sottocluster, possiamo distinguere tra agglomerativi o divisivi.
26
Nel primo approccio, detto anche “bottom-up”, ogni oggetto inizialmente forma un gruppo separato. In seguito i singoli oggetti, o i gruppi tra loro vicini, vengono fusi fino all'ottenimento di un unico gruppo, o fino al raggiungimento di una con-dizione di terminazione. L'approccio divisivo, detto anche “approccio top-down”, inizia con un unico cluster nel quale sono presenti tutti gli oggetti. Durante cia-scuna iterazione successiva, ogni cluster viene suddiviso in cluster più piccoli, fino al momento in cui ciascun oggetto si trova in un cluster differente, o fino al raggiungimento di una condizione di terminazione.
Figura 2-6 Clustering gerarchico.
Clustering esclusivo e non esclusivo. Nel primo caso ciascun oggetto viene asse-gnato a un singolo cluster. Nel caso di clustering non esclusivo (o overlapping) un oggetto può appartenere contemporaneamente a più di un gruppo (classe). Clustering fuzzy e non fuzzy. In questo clustering l'appartenenza di ogni oggetto
ad ogni cluster è indicata con un peso di appartenenza compreso tra 0 (assoluta-mente non appartiene) e 1 (assoluta(assoluta-mente appartiene). La somma dei pesi per cia-scun punto deve essere 1.
Clustering parziale e completo. Nel primo caso alcuni oggetti potrebbero non ap-partenere a nessun cluster. Nel secondo caso, ogni oggetto viene assegnato a un cluster.
27
2.6.2 Diversi tipi di Cluster
Nelle prossime righe verranno presentati i diversi tipi di cluster.
Density-Based (Basati sulla densità). Molti metodi di partizionamento clusteriz-zano gli oggetti basandosi sulla loro distanza. Tali metodi sono adatti a cluster con forma sferica e possono incontrare difficoltà nell'individuare cluster di forma ar-bitraria. Sono stati sviluppati metodi di clustering che si basano sulla nozione di densità.
Un cluster è una regione densa di oggetti circondata da una regione a bassa den-sità. La loro idea generale è quella di far crescere un dato cluster fino a quando la densità (numero di oggetti o punti) in un vicinato non eccede una determinata soglia. In altre parole, è necessario garantire che, per ciascun punto all’interno di un dato cluster, il vicinato di un determinato raggio contenga almeno un numero minimo di punti. Una definizione basata sulla densità viene utilizzata quando i cluster sono irregolari o intrecciati e quando sono presenti rumore e valori ano-mali.
Figura 2-7 Density-based clusters.
Well-separated (Ben separati). Un cluster è un insieme di punti tali che qualsiasi punto nel cluster è più vicino (più simile) a ogni altro punto del cluster rispetto a ogni altro punto che non appartiene al cluster.
28 Figura 2-8 Well-separated clusters.
Prototype-Based (Basato sui prototipi). Un cluster è un insieme di punti in cui ogni punto è più vicino (più simile) al prototipo che definisce il cluster rispetto al prototipo di qualsiasi altro cluster. Per i dati con attributi continui, il prototipo di un cluster è spesso un centroide, cioè la media di tutti i punti che appartengono al cluster, oppure medioide, il punto più rappresentativo del cluster.
Figura 2-9 Center-based clusters.
Graph-Based (Basato sui grafici). Se i dati sono rappresentati come un grafico, in cui i nodi sono punti e i collegamenti rappresentano le connessioni tra i punti, un cluster può essere definito come un gruppo di punti che sono collegati tra loro, ma che non hanno alcuna connessione con punti esterni al gruppo. Questa definizione è utile quando i cluster sono irregolari o intrecciati. Un importante esempio è un cluster basato sulla contiguità (Figura 2-10). In questo cluster due oggetti sono connessi solo se si trovano a una distanza specifica l'uno dall'altro.
29
Shared-Property (Conceptual Clusters). Possiamo definire un cluster come un in-sieme di punti che condividono alcune proprietà. Questa definizione comprende tutte le precedenti, tuttavia, l'approccio della proprietà condivisa include anche nuovi tipi di cluster. Un algoritmo di clustering avrebbe bisogno di un concetto molto specifico per rilevare con successo questi cluster. Il processo di ricerca di tali cluster è chiamato clustering concettuale.
Figura 2-11 Conceptual clusters.
2.6.3 K-means
L'algoritmo di clustering K-means è un metodo di partizionamento. Dato un database di n oggetti, e un numero di cluster k, un algoritmo di partizionamento organizza gli oggetti in k partizioni (k ≤ n), dove ciascuna partizione rappresenta un cluster.
In questo paragrafo verrà approfondito l'algoritmo K-means in quanto verrà utilizzato durante l'analisi del caso di studio.
L'algoritmo k-means riceve in input un parametro k e partiziona un insieme di n oggetti in k cluster in modo da ottenere un'alta similarità intra-cluster e una bassa similarità inter-cluster. La similarità è misurata rispetto al valore medio dei punti in un inter-cluster.
L'algoritmo K-means procede nel seguente modo:
seleziona casualmente k dei punti, ciascuno dei quali rappresenta inizialmente la media o il centro di un cluster;
successivamente, i punti rimanenti vengono associati al cluster più simile sulla base del valore della distanza tra il punto e la media del cluster. Ogni raccolta di punti assegnati a un centroide è un cluster.
30
A questo punto, viene calcolata la nuova media per ogni cluster sulla base dei punti asse-gnati al cluster. Questo procedimento va avanti fino a quando nessun punto cambia i cluster o finché i centroidi rimangono gli stessi.
Tipicamente viene utilizzato come criterio l'errore quadratico, definito come:
𝐒𝐒𝐄 = ∑ ∑ |𝒑 − 𝒎𝒊|𝟐
𝒑 ∈ 𝑪𝒊
𝑲 𝒊 = 𝟏
dove SSE è la somma dell'errore quadratico per tutti gli oggetti del database, p è il punto nello spazio che rappresenta il dato oggetto e mi è la media del cluster Ci (sia p che mi sono
multidimensionali). L'algoritmo tenta di determinare k partizioni che minimizzano la fun-zione errore quadratico.
Figura 2-12 Clustering di un insieme di oggetti basato sul metodo k-means.
L'algoritmo k-means non raggiunge buoni risultati quando i cluster hanno:
Diverse dimensioni. Il valore di SSE porta a identificare i centroidi in modo da avere cluster delle stesse dimensioni se i cluster non sono ben separati.
Diversa densità. Cluster più densi comportano distanze intra-cluster minori, quindi le zone meno dense richiedono più mediani per minimizzare il valore totale di SSE.
Forma non globulare. Il valore di SSE si basa su una distanza euclidea che non tiene conto della forma degli oggetti.
I dati contengono outlier. Gli outlier possono influenzare il valore medio del clu-ster preso in considerazione.
31
L' algoritmo presenta anche alcuni vantaggi:
l'efficienza nel processare grandi insiemi di dati.
la complessità computazionale dell'algoritmo è O(nkt), dove n è il numero di to-tale di oggetti, k è il numero dei cluster e t è il numero di iterazioni sull'intero data set. Normalmente, k ≪ n e t ≪ n.
spesso l'algoritmo termina con un ottimo locale.
2.7 Regole di associazione
L'estrazione di regole di associazione è una delle tecniche di Data mining fondamentale e più utilizzata nel Web Usage Mining. Il suo obiettivo è trovare tutte le relazioni di co-occorrenza (associazioni) tra gli elementi dei dati.
La classica applicazione delle regole di associazione nel Data mining è la Market basket analysis. Questa analisi ha lo scopo di evidenziare come sono legati tra loro gruppi di pro-dotti acquistati dai clienti (Figura 2-13).
Figura 2-13 Association Rule Discovery.
Un esempio di Association rule può essere rappresentata nel modo seguente: Cheese → Beer [support = 10%, confidence = 80%].
Questa regola spiega che il 10% dei clienti compra formaggio e birra insieme, e chi ac-quista formaggio acac-quista anche birra l'80% delle volte (del support e della confidence par-leremo più avanti).
32
Questo modello di Data mining è molto generale e può essere utilizzato in diverse appli-cazioni, esempio il Web mining. In questo ambito infatti può essere utilizzato per trovare relazioni di co-occorrenza di parole e modelli di utilizzo del Web.
Quando la Market basket analysis viene applicata ai clickstream, i prodotti vengono so-stituiti con le pagine del sito web. Lo scopo di questa analisi è quello di individuare le com-binazioni più frequenti delle pagine che vengono visitate dagli utenti del sito. Analizzando la combinazione di pagine visitate, e il numero di volte che queste sono ripetute, si può ottenere una regola del tipo “if condition then result”.
Una regola di associazione si presenta nella forma A → B, dove A è detta “corpo della regola” o “condizione” e B è detta “testa della regola” o “risultato”. La regola A → B non indica solo che entrambe le pagine son state visitate ma anche che la pagina A precede la pagina B.
Le regole di associazione, tuttavia, non considerano l'ordine in cui vengono acquistati gli articoli. L'estrazione di Sequential patterns si occupa di questo. Tali modelli sono utili nel Web Usage Mining per l'analisi dei clickstream12 presenti nei log del server.
Il Web Usage Mining trova le relazioni tra i diversi accessi degli utenti. Ad esempio, si può scoprire che: il 90% dei clienti che hanno effettuato l'accesso alla pagina con URL /pro-dotti /prodotto.html, hanno effettuato l'accesso anche alla pagina /contact/contact.html. Que-ste informazioni rivelano che queQue-ste due pagine sono strettamente correlate e possono essere organizzate insieme per fornire agli utenti un percorso di navigazione più semplice.
Se consideriamo la sequenza indiretta A → B, e indichiamo con NA → B il numero delle
sessioni utente in cui tale sequenza appare almeno una volta, il support della regola A → B può essere ottenuto nel modo seguente
𝑠𝑢𝑝𝑝𝑜𝑟𝑡 {𝐴 → 𝐵} = 𝑁𝐴 → 𝐵 𝑁
33
dove N è il numero delle sessioni complessive. Il support e può essere considerato come la percentuale degli utenti che hanno visitato in successione le due pagine.
La confidence è ottenuta con il rapporto 𝑐𝑜𝑛𝑓𝑖𝑑𝑒𝑛𝑐𝑒 {𝐴 → 𝐵} = 𝑁𝐴 → 𝐵
𝑁𝐴
dove NA è il numero di sessioni che contengono la pagina A. Questa misura può essere
de-finita come la probabilità condizionata che in una sessione in cui viene visitata la pagina A, viene richiesta anche la pagina B13.
La scoperta della regola di associazione utilizzando l'algoritmo Apriori, può collegare le pagine che sono più spesso consultate insieme in un'unica sessione utente. Pertanto, la pre-senza o l'aspre-senza di tali regole può aiutare i web designer a ristrutturare il sito web.
2.8 Sequential pattern
Mentre le regole di associazione trovano le relazioni intra-transazione, i sequential pattern trovano schemi inter-transazione per rilevare la presenza di un insieme di elementi in una sequenza di transazioni ordinata in base al tempo. Nel mining delle regole di associazione gli elementi che si verificano in una transazione non sono ordinati, nel mining dei sequential pattern, invece, esiste un ordine tra gli elementi (eventi) e un elemento può ripresentarsi nella stessa sequenza.
Grazie ai sequential pattern, i web marketer14 possono prevedere modelli di visite future
che potranno essere utili per l'inserimento di annunci pubblicitari mirati a determinati gruppi di utenti.
Ad esempio, a partire dalla home page di un motore di ricerca, gli utenti possono indivi-duare informazioni riguardanti le università in Canada seguendo uno dei seguenti percorsi:
13 P. Giudici, C. Tarantola, Web Mining pattern discovery, No.156, settembre 2003. 14 Persona che si occupa della promozione del sito attraverso i canali legati al Web.
34
Home → Education → Higher Education → Colleges and Universities → By Region → Countries → Canada;
Home → Regional → Countries → Canada → Education → Higher Education.
Pertanto, le università che desiderano attrarre potenziali studenti possono posizionare i propri annunci su una delle pagine lungo il percorso.
La tecnica del modello sequenziale è utile per trovare modelli frequenti di accesso al web. È possibile distinguere tra Sequential rule diretta e indiretta. Nel caso di Sequential rule indiretta, tra la visita della pagina A e della pagina B vengono visualizzate altre pagine web. Nel caso di Sequential rule diretta, la visita della pagina A e della pagina B è sequenziale. Nell'analisi di clickstream web le regole sequenziali sono tipicamente indirette.
2.9 Web Log
Le statistiche di un sito web dipendono da un insieme di fattori. Il primo elemento da considerare, che può essere definito il “livello 0”, è il file di log del web server.
Un file web log registra tutte le informazioni riguardanti le azioni di un utente che visita un sito web. Le informazioni raccolte all'interno del web log non riguardano solo le visite dell'utente, vengono registrate anche le informazioni riguardanti gli spider dei motori di ri-cerca che visitano un sito web per includerlo nel proprio indice.
Un file di log può trovarsi in tre diversi punti: i) Web Servers, ii) Web Proxy Servers, iii) Client Browsers. Ognuno di questi presenta due importanti inconvenienti.
Server-side logs. Questi generalmente forniscono dati più completi e accurati, ma sono caratterizzati dai seguenti svantaggi:
Contengono informazioni personali sensibili, pertanto i proprietari dei server di solito li tengono chiusi.
35
Non registrano le pagine visitate nella cache. Le pagine memorizzate nella cache non vengono richiamate dal Web server ma dallo storage locale del browser o dal proxy server.
Proxy-side logs. Un proxy server accetta le richieste HTTP dagli utenti e le passa a un Web server, quindi restituisce agli utenti i risultati trasmessi loro dal Web server. Anche in questo caso si presentano degli svantaggi:
La costruzione del proxy server è un compito difficile che richiede una program-mazione di rete avanzata, come TCP / IP.
L'intercettazione della richiesta è limitata.
Client-side logs. I partecipanti testano da remoto un sito Web scaricando un software speciale che ne registra l'utilizzo, o modificando il codice sorgente di un browser esistente. Anche i cookie HTTP potrebbero essere utilizzati per questo scopo. Si tratta di informazioni che vengono generate da un Web server e memorizzate nei computer degli utenti, pronte per accessi futuri. Gli svantaggi di questo approccio sono:
Il team di progettazione deve distribuire il software speciale e farlo installare dagli utenti finali.
La tecnica rende difficile ottenere compatibilità con una vasta gamma di sistemi operativi e Web browser.
2.9.1 Struttura Web Log
Il contenuto del file log può variare in base al Web server e può contenere diversi tipi di informazioni. Tuttavia, possono essere definiti alcuni elementi del file log comuni a tutti i Web server:
36
Indirizzo IP. L'indirizzo IP15 viene assegnato dall’Interne Service Provider (ISP)16
e identifica univocamente la macchina dalla quale è partita la richiesta della pa-gina sul web server.
Authuser. Identifica l'utente qualora questo abbia effettuato l'autenticazione. In caso di utente non autentificato è presente il segno “-“.
Time stamp. Si tratta della data e dell'ora della richiesta e definisce il momento esatto in cui è stata richiesta una pagina.
Action. Indica l'oggetto della richiesta. Le azioni richieste possono essere di tipo GET, HEAD e POST. GET: Richiede una risorsa ad un server. HEAD: Il server risponde soltanto con i metadati associati alla risorsa. POST: Permette di trasmet-tere delle informazioni dal client al server.
Request. Indica la risorsa a cui l'utente ha avuto accesso (pagina HTML, file mul-timediali, script ecc).
Status. Indica il codice di risposta HTTP restituito all'utente, indica se la richiesta è andata a buon fine o meno e l'eventuale messaggio di errore restituito.
Bytes. La dimensione totale dei byte trasferiti per il contenuto richiesto.
Nella Figura 2-14 viene presentato un esempio di file log, mentre nella Figura 2-15 sono elencati i possibili status della richiesta.
15 IP (Internet Protocol). Etichetta numerica che identifica univocamente un dispositivo detto host collegato a
una rete informatica che utilizza l'Internet Protocol come protocollo di rete. È costituito da 4 byte e suddiviso in 4 gruppi separati da un punto.
16 Organizzazione che offre agli utenti servizi inerenti a internet, i principali sono l'accesso al World Wide
37 Figura 2-14 Esempio di File Log.
38
Capitolo 3
IL CASO DI STUDIO
I vantaggi che portano un'azienda a scegliere di aprire un sito web e-commerce possono essere diversi. Alcune delle ragioni più importanti che spingono un'azienda verso il mercato online possono essere riassunte nei seguenti punti:
Il sito e-commerce non è vincolato agli orari di apertura, è sempre possibile effet-tuare degli ordini.
I costi dell'e-commerce si son ridotti rispetto al passato.
L'e-commerce permette di ottenere maggiore visibilità e aumentare il bacino di utenza.
L'e-commerce permette all'azienda di farsi conoscere anche fuori dai confini lo-cali.
In questo capitolo presenteremo l'azienda oggetto di studio e il suo sito web, descrivendo le tabelle che verranno utilizzate durante le diverse fasi dell'analisi.
3.1 L'azienda
L'azienda che è stata analizzata durante questo progetto è un primario player nella distri-buzione dei prodotti di alcuni dei principali vendor ICT.
39
Da oltre vent'anni si occupa di distribuzione di prodotti ICT, distinguendosi in qualità di operatore evoluto che gestisce in misura sempre maggiore una quota del valore aggiunto destinato al canale dei rivenditori.
Oltre alle attività di box-moving, fornisce al canale un supporto a 360 gradi su tutti i prodotti distribuiti, attraverso uno staff di oltre 500 persone qualificate e certificate sui pro-dotti e soluzioni.
La specializzazione, la competenza e i servizi di ciascuna delle Business Unit sono il punto di forza riconosciuti dal mercato con la leadership sui principali Vendor Informatici, e che permette all'azienda di distinguersi dai competitors.
Uno dei canali principali di comunicazione con rivenditori è il sito web, che vanta più di 16.000 iscritti, oltre alla presenza sul territorio italiano con 15 Cash and Carry, attraverso i quali è possibile reperire informazioni e prodotti leader del settore informatico.
3.2 Il sito web
In questo paragrafo verranno presentate alcune caratteristiche del sito web aziendale, non solo da un punto di vista grafico, ma, soprattutto, da un punto di vista tecnico, analizzando le tabelle che verranno utilizzate durante le diverse fasi dell'analisi.
3.2.1 Il contenuto
Il nome di dominio del sito web aziendale corrisponde al nome dell'azienda (www.no-meazienda.it). Questa scelta rende immediato il reperimento del sito da parte dei visitatori e migliora l'indicizzazione da parte dei motori di ricerca.
40
Le pagine del sito sono sviluppate nel formato .DO17. La prima pagina è la Home page (Figura 3-1) e si presenta carica di contenuti.
La versione del sito presentata in questo elaborato presenta il form per il login nella parte superiore. Questo strumento è fondamentale in quanto la maggior parte delle pagine presenti sono navigabili solo dopo l'autenticazione dell'utente.
Le uniche zone del sito navigabili liberamente sono quelle collegate al menù. Quest'ul-timo permette la navigazione all'interno delle pagine in cui è presente la descrizione dell'a-zienda, i brand commercializzati, le news, le sedi, i Cash&Carry.
Nella parte superiore sono presenti anche i collegamenti ai principali social media, canali sui quali l'azienda è particolarmente attiva.
Il corpo della pagina è caratterizzato prevalentemente da banner che collegavano alle of-ferte in corso e ai prodotti in prima linea.
Sulla parte inferiore sono presenti tre tabelle che permettono ai visitatori del sito di rima-nere sempre aggiornati sulle ultime Promozioni, le ultime inserzioni riguardanti Eventi e Formazioni e le ultime News riguardanti l'azienda.
Figura 3-1 Home page sito aziendale.
41
Trattandosi di un sito B2B, i prodotti commercializzati possono essere acquistati, previo registrazione, soltanto da parte di altre aziende.
All'interno del sito è presente un modulo dettagliato che è necessario compilare per effet-tuare la registrazione (Figura 3-2) e poter iniziare ad acquistare online.
Nella parte finale del modulo è permesso all'utente di indicare quali brand sono commer-cializzati dalla propria azienda. Scegliendo uno o più marchi, viene offerta all'utente la pos-sibilità di ricevere servizi personalizzati sui brand indicati.
Figura 3-2 Modulo iscrizione sito web.
3.2.2 I dati
I dati riguardanti gli accessi vengono registrati sul file log del web server Apache e, in seguito, registrati sulla tabella ACCESS_LOG ad intervalli schedulati di due ore.
Per quanto riguarda gli ordini, i dati vengono registrati in tempo reale all'interno di un Database.
Durante le varie fasi dell'analisi è stata sfruttata un'altra tabella, denominata RE-QUEST_DECODER. Questa tabella, realizzata attraverso l'utilizzo di un'applicazione java, permette ai responsabili del sito web di comprendere il contenuto delle pagine più rilevanti e assegnare loro una categoria di appartenenza.
42
TABELLA ACCESS_LOG
La tabella ACCESS_LOG contiene al suo interno ogni hit (documento HTML, immagine ecc) registrata durante le visite degli utenti.
Come già spiegato in precedenza, il contenuto delle informazioni registrate in un Web log possono variare. Nella tabella utilizzata per il progetto, con riferimento all'ultimo trime-stre 2017, prima della fase di cleaning, erano presenti poco più di 10 milioni di righe e 14 colonne.
Ai fini della nostra analisi, le colonne utilizzate sono state solo 5. Se ne presenta in seguito una breve descrizione.
DATE: contenente la data della richiesta effettuata dall'utente; REMOTE_USER: contenente il nome dell'utente (se autenticato); REQUEST_URI: contenente l'URI della richiesta effettuata;
REQUEST_METHOD: contenente il tipo di richiesta (Post, Get, Head ecc); HTTP_STATUS: contenente il codice di stato (da 200 a 501).
TABELLA ORDER
La tabella ORDER contiene al suo interno gli ordini effettuati dai clienti utilizzando il sito web aziendale. Anche in questo caso il periodo di riferimento riguarda l'ultimo trimestre 2017 e, prima della fase di pulizia, nella tabella erano presenti più di 47.000 righe e 42 co-lonne.
Le colonne della tabella ORDER utilizzate per l'analisi degli ordini sono riportate in se-guito.
USER_IDENTIFIER: contenente il nominativo dell'utente; TIMECREATED: contenente la data dell'evasione dell'ordine; STATUS: contenente il codice corrispondente allo stato dell'ordine;
