Web Usage Mining - Progettazione e sviluppo di un sistema di raggruppamento basato su pattern sequenziali

(Markup languages) che permettono un'estrazione di informazioni utili sull'onto-
logia delle pagine web; nel caso dello structure mining si esploreranno le strutture
dei siti e della rete, attraverso la navigazione da parte di software come crawler,
spider o robot. Il terzo ambito di ricerca e quello del web usage mining, cioe l'a-
nalisi statistica e l'utilizzo di tecniche di mining applicate a collezioni di dati relativi
all'interazione tra utente e World Wide Web. In altri termini vengono applicate
analisi statistiche e tecniche di mining ai dati provenienti dai diversi repository web
quali server, proxy e dai client connessi in rete.
Il lavoro di Agrawal [AIS93, AS94] e il caposaldo da cui si dipana tutta la ricerca
successiva sul data mining e risulta essenziale una sua conoscenza, almeno nei sui
tratti principali, per chi volesse cimentarsi in questa disciplina. La rassegna [KB00]
fornisce un'ottimo punto di partenza per l'indagine bibliograca sul web mining, in
[CHY96, PKZ01, BMAH, SCDT00, CHM06] troviamo utili basi per comprendere
meglio il linguaggio e i termini utilizzati sia in ambito web che nel data mining.
Bisogna precisare che nei primi anni '90, dal lavoro di Agrawal, il termine web mi-
ning non esisteva e solo nel '96 Etzioni [Etz96] introduce in maniera esplicita tale
denominazione per la nuova disciplina. Poi, principalmente Cooley e Mobasher,
cominciano a farne una descrizione toponomica denendo le aree del web mining,
denendone dati di interesse, problematiche e algoritmi [MJHS96, CSM97, CTS99].
Innanzitutto, bisogna precisare che il settore del web mining e molto dinamico e si
innesta, come specicato in precedenza, in diverse discipline quindi risulta arduo
fornire una bibliograa esaustiva e aggiornata. Il processo di web mining puo es-
sere facilmente classicato in due approcci. Il primo mappa i dati log in tabelle
relazionali prima che un algoritmo adatto di data mining venga applicato. Il se-
condo approccio, invece, prende direttamente i dati utilizzando tecniche speciali
per il pre-processing [CMS97]. Come e vero per il data mining, la qualita e il pre-
processing dei dati diventano argomenti chiave nel web mining. Un problema tipico
e quello di identicare gli utenti, le sessioni e gli episodi in presenza di proxy e di ca-
ching [KVP01] attraverso algoritmi di pre-processing o euristiche [CMS99, BL00].
Comunque, tecniche tipiche di data mining possono essere applicate una volta
che i dati sono stati preparati, oppure si possono utilizzare delle varianti basate
sulle regole associative [CHY96, AS95, MDLN01, LAR00, PHMaZ00, PCY95],
adattandole alle sequenze [CHY96, SA96, CPY98, JKK99, MDLN02b], o me-
todi basati sulle grammatiche e modelli probabilistici [Hof99, PHMA+, ADW02].
Inoltre, spesso, si ricorre all'integrazione dell'ontologia, della topologia del sito,
unendo allo usage le informazioni estratte attraverso web structure e web con-
tent mining [DM02, LZ, MDL+00b, Coo03, NM03]. Le applicazioni possono es-
sere catalogate in due tipi principali: la personalizzazione dinamica dei siti, at-
traverso un proling degli utenti [DM02], oppure la conoscenza dei pattern uten-
te nel sito. Queste tipologie sono le due facce della stessa medaglia, infatti la
prima e rivolta a migliorare attraverso web recommandation [YJGMD96, SM95,
PE99, PE98, MCS99, LAR00, LLC04, FBH00, FP99, Bur02] e web personaliza-
tion [MDLN02a, MDL+00a, MDLN01, MCS00, Bur02, APSS] la navigazione degli
utenti, la seconda e orientata al site design, al miglioramento del sito web in modo
che lo scopo informativo venga raggiunto e migliori l'ecienza per motivi commer-
ciali e di business [SZAS97, HKP02].
Oltre ai numerosi articoli e libri sopracitati, si possono ricavare utili informazioni sul
Web. Come gia evidenziato precedentemente, e, in questo caso, ancor maggiore
la quantita di documenti reperibili. Sul web mining Wikipedia [WIK06b] fornisce
denizioni e link utili (alcuni sono gia stati citati). Altre web page utili sono [W306,
WIK06a, BAC06] per comprendere meglio alcuni termini e caratteristiche dell'am-
biente web, mentre [SGI06, NCR06, IBM06, SPS06, BUS06, SAS06, ANG06] sono
alcuni siti di aziende che si occupano di Business Intelligence e Data mining.
La bibliograa e il punto di partenza per inquadrare il problema, poi e necessaria
una analisi delle risorse aziendali e dei dati web disponibili, per capire quale approc-
cio e preferibile. Una volta capito questo, uno studio di fattibilita delle soluzioni
pratiche e la chiara denizione degli obiettivi informativi che si vorrebbero raggiun-
gere, permettono di porre le basi per la progettazione nale. Per una lettura piu
consapevole e una comprensione dei contenuti piu specici, saranno necessarie delle
nozioni preliminari su Data warehousing e Data mining nel processo di Knowledge
Discovery cercando di fornire un background sui concetti principali che incontre-
remo nella trattazione. Tali aspetti verranno arontati nel Capitolo 1, mentre nel
Capitolo 2 cominceremo ad addentrarci nella descrizione del processo di web mining.
Innanzitutto illustreremo gli aspetti generali, poi focalizzeremo la nostra attenzione
sul web usage mining, oggetto principale d'indagine. In questi due capitoli il ta-
glio della trattazione sara perlopiu teorico e verranno forniti riferimenti bibliograci.
Nella tesi, che e stata svolta in un contesto aziendale, non mancheranno riferimen-
ti ed esempi che contestualizzino ed esplichino praticamente i concetti teorici che
vengono trattati. Nell'ultima parte, inne, si concentra il lavoro sperimentale ed
applicativo svolto sui dati relativi al repository di una intranet aziendale relativa ad
una rete di promotori nanziari. Quindi, sono stati messi in risalto gli aspetti mi-
gliorabili e che potrebbero essere oggetto di sviluppi futuri. Nel Capitolo 3 verranno
illustrate le conclusioni sull'ecacia dei risultati ottenuti e le valutazioni sull'intero
progetto.
\Simgenia e la Societa di Intermediazione Mobiliare del Gruppo bancario Banca Ge-
nerali nata per fornire ai clienti assicurativi delle compagnie del Gruppo (Alleanza,
Generali, INA) soluzioni nanziarie alle esigenze di investimento personale.
Operativa dall'inizio del 2003, a seguito del processo di riorganizzazione delle so-
cieta di distribuzione di prodotti nanziari del Gruppo Generali, Simgenia si pone
come obiettivo quello di orire una risposta complessiva alle crescenti esigenze di
risparmio nanziario.
Gli oltre 2.500 Promotori Finanziari Simgenia operano all'interno delle agenzie as-
sicurative di Alleanza, Generali ed Ina e uniscono la qualica di agenti assicurativi
con la conoscenza dei mercati nanziari, proponendosi quindi come `interlocutore
unico' alle richieste dei Clienti.
Scegliere Simgenia per i propri investimenti nanziari signica, quindi, entrare in
contatto con una grande organizzazione nata dalla solida tradizione di adabilita
delle compagnie assicurative del Gruppo Generali e dalla competenza ed innovazione
di Banca Generali." Tratto dal sito internet http://www.simgenia.it.
CAPITOLO 1
Dal Data Warehousing al Data
Mining
I progressi fatti negli ultimi anni nelle tecnologie di storage, la crescita delle potenze
di calcolo e lo sviluppo software hanno contribuito alla sempre piu vasta memo-
rizzazione di dati in formato digitale in database, data warehouse (DWH) e altri
tipi di banche dati. Si calcola approssimativamente che la quantita di informazione
digitale raddoppia ogni 20 mesi.
La grande disponibilita di dati in formato digitale pone l'interrogativo di come valu-
tare automaticamente se questa mole di dati nasconde informazione. Il data mining
si pone come obiettivo quello di scovare informazioni utili ed interessanti, ma im-
plicite e non manualmente scopribili, attraverso strumenti e tecniche automatiche.
Tale processo certamente ha implicazioni in ambito economico (Business Intelligen-
ce) in cui si cerca di superare lo stadio del DWH in cui viene applicato l'OLAP (On
Line Analytical Processing), che attraverso le strutture a \cubi" orono uno stru-
mento utile per estrarre in tempo reale statistiche e dati sulla produzione aziendale.
In questo capitolo vedremo i concetti base che caratterizzano il data warehousing e
il data mining nel piu ampio processo di Knowledge Discovery in databases (KDD).
In un certo senso, viene illustrato il processo di apprendimento svolto in fase di
consultazione bibliograca e, parallelamente, di acquisizione di informazioni e co-
noscenze di base sul data warehouse aziendale ponendo l'accento sulle denizioni e
sui possibili scenari di sviluppo di applicazioni di data mining.
1.1 Data Warehouse
Il data warehouse, letteralmente \magazzino di dati", e una collezione integrata
di informazioni relative a fatti misurabili. Tra gli attributi, l'informazione relativa
al momento temporale in cui l'evento si e vericato consente di eettuare analisi
2 1.1. DATA WAREHOUSE
Figura 1.1: Diagramma di Business Intelligence
storiche sui fatti d'interesse. Le tecniche di data ware nascono dunque per memo-
rizzare ecientemente grandi moli di dati relative a serie storiche.
Negli ultimi trent'anni si sono evolute moltissimo le tecnologie hardware che hanno
permesso la diusione di architetture di questo tipo. I data warehouse aziendali
integrano dati provenienti da piu database. Come e possibile vedere in g. 21 in
Appendice A, i dati vengono dapprima estratti dalle sorgenti poi vengono eettuati
controlli di consistenza prima di tipo sintattico e poi semantico, in modo da essere
disponibili agli applicativi. Tale architettura ha incentivato lo sviluppo dell'OLAP
(On Line Analytical Processing) [CHM06] che e utilizzato per analizzare una vasta
quantita di dati e che consente una manipolazione dei dati che sono visti come
dimensioni e fact table.
Figura 1.2: Data warehouse Simgenia Sim S.p.a.
In gura 1.2 e evidente come vengano integrati diversi data base, riguardanti
settori diversi dell'azienda e come poi questi dati possano servire a diversi tipi di
applicazioni, dai web services (DPSONLINE) alle attivita di report (tramite OLAP
o selezione con query).
WEB USAGE MINING { Daniele Munarin
1.1. DATA WAREHOUSE 3
1.1.1 Caratteristiche principali
I data warehouse (abbreviato DWH) sono stati concepiti e modellati per svolgere
analisi OLAP, query che sfruttano la struttura relazionale o processi di KDD, come
vedremo nel dettaglio. Il modello utilizzato e quello multidimensionale, che rispetto
ad un semplice database multibase deve integrare dati da piu sorgenti diverse in
tabelle di fatti (fact table) e dimensioni. Diversamente dai tradizionali data base, i
DWH, devono dare risalto alla storicita dei dati per eettuare analisi di tendenza per
prendere decisioni di business nell'azienda. Quindi, in questa situazione i dati non
sono volatili e per di piu cambiano molto raramente, di solito in periodi pressati
di aggiornamento dati, mentre le letture, le consultazioni tramite query predenite
o ad-hoc, vengono eettuate spesso nell'arco dell'orario di lavoro. Per questo
che la fase di aggiornamento, in cui vengono modicati, preparati e ricaricati i
dati, viene compiuta in momenti di bassa o nulla operativita degli applicativi, in
quanto tutte queste operazioni sono onerose in termini di tempo e occupazione di
risorse. Usualmente nelle basi di dati le transazioni sono l'unita atomica e l'agente
di aggiornamento, mentre nei DWH le informazioni sono a granularita piu grossa
e le modiche vengono eettuate attraverso una procedura di aggiornamento di
solito incrementale, in diverse fasi preposte a funzioni ben denite. Il componente
di acquisizione, diviso in stadi, si occupa di tale processo di aggiornamento.
I data warehouse, quindi presentano sinteticamente tali caratteristiche:
Orientato alle informazioni (\subject oriented") I dati presenti nei sistemi ap-
plicativi di base sono normalmente orientati ad un problema specico (ad es.
le caratteristiche tecniche di un prodotto sono presenti nella distinta base,
mentre quelli relativi ai suoi dati di vendita sono presenti nel programma di
supporto al servizio commerciale ecc.); nel DWH, invece, vengono ricostruite
nella loro completezza (e rese disponibili in contemporanea) le informazioni
presenti in modo frammentario nei vari sottosistemi; in altre parole se nei si-
stemi applicativi di base (altrimenti detti operazionali) l'accento e posto sulle
applicazioni (modalita di manipolazione dei dati), nel DWH l'accento e posto
sugli oggetti, sui fatti, sulle informazioni e non sulla loro manipolazione;
Integrato (\integrated") I vari sistemi informatici di base tipicamente utilizza-
no dierenti (e molto spesso incompatibili) piattaforme tecnologiche, DBMS
WEB USAGE MINING { Daniele Munarin
4 1.1. DATA WAREHOUSE
(Data Base Management Systems) 1, codiche, convenzioni sui nomi, attribu-
ti sici, dimensioni degli attributi ecc. I dati vengono inseriti in un DWH pro-
prio per eliminare le molte inconsistenze e incongruenze dei sistemi elementari
e per utilizzare una semantica uniforme;
Non volatile I dati sono continuamente aggiornati nei sistemi applicativi di base,
mentre tipicamente i DWH non prevedono l'aggiornamento di alcun dato, ma
memorizzano fotograe successive della realta raccolte a cadenza pressata.
In tal modo le modiche, che sul sistema operazionale andrebbero perse se
non storicizzate, vengono memorizzate in maniera permanente sul DWH;
Variante col tempo (\time variant") L'orizzonte temporale dei dati \in linea" in
un DWH e tipicamente molto superiore rispetto ai sistemi di base; questi ulti-
mi, inoltre, tipicamente mantengono solo la versione corrente dei dati, mentre
il DWH ne contiene tutta la \storia". Mentre i sistemi ERP (Enterprise Re-
source Planning)2 sono centrati sulla dimensione operativa e possono in ogni
momento dire all'utente a che punto e un certo ordine, quante componenti
di un certo tipo ci sono in magazzino e fornire altre informazioni puntuali, per
gestire la memoria delle aziende, e necessario depositare i dati elaborati in un
\magazzino strutturato".
Il modello multidimensionale ore un supporto, un mezzo, all'ingegnere della
conoscenza (dirigente, manager o analista) per prendere decisioni piu rapide e pre-
cise.
Sinteticamente possiamo dire che il processo di aggiornamento comprende lo stadio
di estrazione, integrazione, pulitura e formattazione dei dati. Successivamente ven-
gono eettuati controlli sintattici, semantici sulle dimensioni e nella fase conclusiva
controlli di coerenza referenziale tra fact e dimensioni. A questo punto possono
essere implementate OLAP, data mining e DSS (Decision Support System)3, per
la scoperta di trend, regole di decisione, classicazioni e tali informazioni possono
tornare a far parte del DWH (tramite feedback o back
ushing) con l'aggiunta di
1
I DBMS sono sistemi progettati per consentire la creazione e la manipolazione eciente di
database, solitamente da parte di piu utenti
2Gli ERP integrano, o cercano di integrare, tutti i dati e i processi di un'organizzazione in un
unico sistema
3
Il DSS e uno strumento di supporto ai decisori, che permette di aumentare l'ecacia dell'analisi
in quanto aumenta il numero si alternative vericabili e informazioni da processare
WEB USAGE MINING { Daniele Munarin
1.1. DATA WAREHOUSE 5
nuove dimensioni. In sintesi, i data warehouse possono avere tali caratteristiche
[EN01]:
 vista concettuale multidimensionale;
 dimensionalita generica;
 dimensioni e livelli di aggregazione non limitati a priori;
 operazioni tra una dimensione e l'altra non vincolate;
 gestione di matrici dinamiche sparse;
 architettura client/server;
 supporto multiutente;
 accessibilita;
 trasparenza;
 manipolazione intuitiva dei dati;
 prestazioni elevate nella generazione di report;
 struttura 
essibile dei report.
Per completezza possiamo dire che i DWH si distinguono dalle tradizionali basi di
dati anche per la quantita di dati. E comunque possibile farne una classicazione
in base all'ordine di Terabyte contenuti:
 DWH a livello d'impresa: si tratta di grandi strutture che richiedono molte
risorse e molto tempo per la gestione (si parla di Terabyte);
 DWH virtuali: forniscono viste su basi di dati operative che sono materializ-
zate per fornire un accesso ecace;
 Datamart: di solito sono rivolti a sottoinsiemi dell'organizzazione, ad esempio
un reparto, e sono maggiormente focalizzati.
WEB USAGE MINING { Daniele Munarin
6 1.1. DATA WAREHOUSE
1.1.2 Struttura del DWH
Senza addentrarci troppo nei dettagli, l'OLAP necessita, come abbiamo accenna-
to, di una struttura multidimensionale. Essa si articola in tabelle delle dimensioni
dimension e tabelle dei fatti fact table. Le prime consistono nelle tabelle degli
attributi (ad esempio la tabella prodotti, clienti, promotori, rete vendita ecc.) la
seconda invece riguarda le tuple in cui sono registrati i fatti aziendali rilevanti, con
i relativi attributi misurati o osservati (ad esempio transazioni, vendite, contratti
ecc.) identicate tramite puntatori alle dimensioni. Gli schemi multidimensionali piu
diusi sono quello a stella (con al centro la fact con riferimenti alle dimensioni) e a
\occo di neve" (con fact, dimensioni e tabelle di dettaglio a piu gerarchie). Alcuni
DWH sono normalizzati no alla terza forma normale [EN01]. Le costellazioni dei
fatti riguardano una serie di tabelle di fatti che condividono delle dimensioni. Tali
insiemi indicano quelli saranno i dati interrogabili dagli applicativi aziendali. Come
abbiamo detto, ci deve essere una referenzialita tra fact e dimensioni, che puo esse-
re ottenuta tramite indicizzazione bitmap o indicizzazione del join [Mic06, EN01].
Quest'ultima si serve di chiavi primarie che si collegano alle chiavi esterne delle
dimensioni oppure usa chiavi surrogate, che servono a mantenere i dati da diverse
fonti e tengono conto della storicita.
1.1.3 Acquisizione dei dati
La fase di acquisizione dei dati si suddivide in diversi stadi.
Estrazione: i dati devono essere estratti da diverse sorgenti, basi di dati o fonti
esterne quali possono essere dati nanziari e dati ambientali.
Formattazione: in questa fase i dati devono essere formattati in modo unifor-
me e consistente. I nomi degli attributi, i signicati e i domini devono es-
sere uniformati, in quanto poi in fase di elaborazione potrebbero vericarsi
inconsistenze.
Pulitura: il riconoscimento dei dati errati e spesso dicile da eettuare perche bi-
sogna inserire vincoli di consistenza tra attributi (constraint) e tabelle diverse
(trigger). Una volta ripuliti, i dati possono essere reintrodotti nelle sorgenti
con una operazione di back
ushing.
WEB USAGE MINING { Daniele Munarin
1.2. KNOWLEDGE DISCOVERY 7
Trasformazione: spesso i dati necessitano di trasformazioni per renderli compatibili
al modello multidimensionali del DWH.
Caricamento: questo processo e il piu oneroso e consiste nella ultima fase di
aggiornamento dei dati. In questi casi e necessario un compromesso com-
putazionale, un tradeo, tra ecenza ed ecacia. Infatti, spesso si evita di
caricare tutti i dati ma solo quelli che veramente risultano necessari per le
query ad hoc formulate dal responsabile delle decisioni. Anche se questo ac-
cade, spesso non e suciente perche la mole di dati e enorme allora si procede
ad aggiornamenti incrementali o selettivi, in cui o si cancellano dati troppo
obsoleti o si caricano in soluzioni diverse.
Al momento della progettazione del DWH bisogna tener conto dell'utilizzo che se ne
fa, per strutturarlo al meglio, scegliendo di conseguenza il modello, le caratteristiche
delle sorgenti, la modularita del sistema in modo che sia scalabile ed possa evolversi
con i cambiamenti organizzativi dell'azienda e quindi del sistema informativo.
1.2 Knowledge Discovery
Per Knowledge Discovery si intende quel processo di estrazione di fatti o regole
interessanti ed implicite che si possono estrarre da dati memorizzati in un qualche
formato in uno o piu repository (luoghi sici dove sono memorizzati i dati). In
questo capitolo considereremo come sorgenti dati i database quindi si parlera di
Knowledge discovery in Databases o KDD.
A questo punto e bene precisare quale sia il rapporto tra data mining e KDD. Alcuni
considerano KDD e data mining la stessa cosa, facendo rientrare nella denizione di
data mining anche subtask del KDD quali sono il pre{processing, la valutazione e la
visualizzazione dei dati. Piu spesso, e anche in questa tesi, si considera il data mi-
ning come un subtask del KDD, perche concettualmente intendiamo il data mining
come un insieme di tecniche e algoritmi per estrarre, scoprire nuove informazioni e
non per \preparare" i dati o valutare e visualizzare i risultati ottenuti.
Dunque il KDD si puo descrivere come un insieme di sotto processi, che descrive-
remo nelle sezioni successive e che sono evidenti in g. 1.3:
Pre{processing: subtask dedicato alla raccolta dei dati dalle sorgenti, selezione e
pulizia degli stessi (vedi sezione 1.3);
WEB USAGE MINING { Daniele Munarin