Definizione e costruzione del grafo del traffico

Prima di vedere l’implementazione dei metodi per la sua costruzione `e necessario definire in modo pi`u preciso che cosa `e un grafo del traffico ricavato a partire dai dati di uso web.

Osserviamo prima di tutto che il grafo del traffico che possiamo ricavare a partire dalle sessioni utente `e qualcosa di diverso dalla reale struttura to- pologica di un sito o del web, in quanto il fatto che due pagine siano state visitate una consecutivamente all’altra e si trovino contigue all’interno di una sessione, non implica che siano realmente collegate da un link. Collegare le pagine di uno o pi`u siti web con dei link permette di dare un’indicazione sull’ordine in cui le varie pagine dovrebbero essere visitate, il grafo del traffi- co indica come effettivamente un utente naviga nella rete. Questa differenza `

e fondamentale, in quanto, la struttura del sito dovrebbe essere disponibile al momento dell’interpretazione dei risultati, ma per questa particolare fase non `e n´e un input, n´e un suo output.

Per caratterizzare un grafo del traffico possiamo considerare la seguente definizione [3] :

Grafo del traffico: Sia S = h(r1, d1)i , ..., h(rN, dN)i una sequenza di N

5.5.2.1 Definizione e costruzione del grafo del traffico 113

richiesta) e da una destinazione di (la pagina richiesta). Definiamo il Grafo del Traffico di S come una tripla (V, E, T) dove:

V = {r1, ..., rN, d1, ..., dN} E = {(r1, d1), ..., (rN, dN)} T (p, q) = |(p, q) ∈ S| con p, q ∈ V T (p) = X (p,q)∈E T (p, q) con p ∈ V

I vertici V sono le pagine, mentre gli archi in E sono le transizioni. La funzione T : V → N rappresenta il Traffico di una pagina (il numero di visite alla pagina), la funzione T : E → N , indica il numero di transizioni da una pagina all’altra.

Proprio sulla base di questa definizione `e stata introdotta l’astrazione delle UCitation, che rappresenta l’astrazione di una visita da una pagina ad un’altra. Ogni oggetto di questo tipo `e relativo una pagina P e contiene un vettore che memorizza tutte le pagine che possono essere considerate un referrer per quella pagina (cio`e tutte le pagine Ri che all’interno di una o pi`u

sessioni compaiono immediatamente prima di P) e il numero di transizioni da Ri a P, oltre al numero totale di visite che sono state fatte alla pagina.

Utilizzando le UCitation cos`ı definite, `e possibile dedurre delle semplici informazioni sul traffico delle pagine. Tuttavia possiamo seguire un approc- cio pi`u sofisticato calcolando il grado “successo” di una pagina, cio`e quanto spesso `e visitata una certa pagina rispetto al numero di visite delle pagine visitate al passo precedente. Possiamo formalizzare questo concetto, intro- dotto in [3], definendo la nozione di traffico relativo:

Traffico relativo: Dato un grafo del traffico TG = (V, E, T), definiamo il traffico relativo R(p) di una pagina p ∈ V e quello di una transizione R(q, p), con (q, p) ∈ E, nel seguente modo:

114 Casi d’uso e R(q, p) =    1 se T(q,p)>T(q) T (q, p)/T (q) altrimenti

con Φ : <2 _{→ < che rappresenta una funzione di aggregazione su un}

insieme di numeri.

Φ pu`o essere un operatore di media, minimo o massimo.

L’informazione sul traffico relativo di ogni pagina viene memorizzata nel- l’attributo r traffic di ogni UCitation e calcolata sulla base di una delle prin- cipali funzioni di aggregazione scelta dall’utente. Con un semplice calcolo pu`o venir calcolato il traffico di ogni transizione dalla pagina A alla pagina B.

La ricostruzione del grafo del traffico basata sull’insieme di UCitation estratte diventa, in realt`a, una semplice rielaborazione che ha come scopo quello di presentare il grafo in una forma grafica facilmente comprensibile, in quanto tutta l’informazione necessaria `e gi`a presente nell’insieme di oggetti UCitation ricavati.

La figura 5.1 mostra un possibile grafo risultante da una prima elabo- razione di un insieme di richieste HTTP. Le etichette dei nodi indicano il numero di visite assolute alla pagina, o al gruppo di pagine, rappresentate dal nodo. Le etichette degli archi mostrano il valore del traffico relativo della transazione. Inoltre per avere un’idea immediata del traffico di una pagina o di una transizione troviamo all’interno del grafo delle linee tanto pi`u spes- se quanto pi`u frequente `e l’accesso alle pagine, rappresentate dai nodi, o le transizioni tra due pagine, individuate dagli archi.

Come possiamo vedere l’interpretazione non `e immediata in quanto ci sono moltissimi nodi e le molte etichette non indicano chiaramente a quale pagina si riferiscono.

Questo dipende principalmente da due fattori.

Il primo `e che molto probabilmente sono state fatte delle analisi a granula- rit`a troppo fine, che inseriscono nel grafo troppe pagine e rendono complicato districarsi tra le molte transizioni.

Il secondo problema dipende dal fatto che non tutte le pagine vengono visitate uno stesso numero di volte e, in questo caso, sono state inserite nel

5.5.2.1 Definizione e costruzione del grafo del traffico 115

Figura 5.1: Grafo del traffico di un sito web commerciale

grafo anche pagine che hanno ricevuto un numero di viste basso, quantomeno rispetto al totale delle pagine registrate nel log file.

Per ovviare a quest’ultimo problema sono stati introdotti due parametri al metodo in cui si esegue l’elaborazione delle UCitation in modo da inseri- re nel grafo del traffico solo le pagine in cui sia il numero di accessi, sia il numero di pagine che la riferiscono superano delle soglie definite dall’utente, soprattutto sulla base del numero totale di pagine estratte dal log file. Per quanto riguarda invece il livello di astrazione delle pagine, `e necessaria una maggiore partecipazione da parte di esperti del dominio che possono stabilire quali sono i gruppi di pagine che possono essere considerate come se fossero una pagina sola, implementando una funzione da utilizzare durante la crea- zione delle UCitation, come mostrato nel capitolo 2.

Possiamo per esempio collassare insiemi omogenei di Url in una sola UCitation. Nel grafo 5.2 possiamo osservare il traffico all’interno del sito, suddiviso in questo caso in macro aree.

In alternativa potremmo voler limitare le analisi solo ad una parte del sito, in modo da ottenere un maggiore livello di dettaglio, ma solo per al- cune pagine. Nei grafi presentati possiamo vedere un caso del genere in cui l’analisi del traffico `e ridotta alle sole pagine del supporto tecnico fornito agli utenti del sito. Possiamo anche vedere come, variando opportunamente le soglie che indicano il valore minimo delle visite che deve aver avuto una pagina per essere inserita all’interno del grafo, si ottengano dei grafi pi`u o meno dettagliati. Nei grafi 5.3, 5.4 `e mostrata una situazione di questo ti-

116 Casi d’uso

Figura 5.2: Grafo del traffico delle principali aree del sito

Figura 5.3: Grafo del traffico delle pagine pi`u visitate del supporto tecnico

po in cui `e mostrato il traffico di una parte del sito a diversi livelli di dettaglio.

Da grafi di questo tipo possiamo osservare quali sono le zone del sito pi`u visitate e il modo in cui avviene la navigazione degli utenti. Non scendiamo nei dettagli di analisi in quanto non si dispone di sufficienti informazioni per interpretare i grafi.

Il sistema, in questo momento, `e utilizzato all’interno del progetto svolto in un’altra tesi di laurea [35], in cui si sfruttano i grafi del traffico per analisi pi`u approfondite, possibili anche grazie ad una maggiore conoscenza del sito web da analizzare, confrontando il traffico con l’effettiva struttura topologica del sito in modo da individuare particolari zone critiche.

5.5.2.1 Definizione e costruzione del grafo del traffico 117

Conclusioni

In questa tesi `e stato sviluppato il Web Object Store, una framework per applicazioni di web usage mining, che fornisce delle utili astrazioni per i dati web a veri livelli, nonch´e un repertorio di algoritmi di data preparation e un algoritmo per analisi di mining. Le analisi di mining possono essere effet- tuate a partire dail log file di server web o proxy server, e procedendo per passi si ottiene, a partire dai dati grezzi, le astrazioni degli oggetti web pi`u comuni, quali le HttpRequest e le URI, rappresentanti i dati pi`u elementari, ma anche le loro aggregazioni in PageView e Session. Inoltre `e stata intro- dotta l’entit`a delle UCitation, che modella il modo in cui un utente naviga, sequenzialmente, attraverso le pagine della rete.

Il sistema finale risulta usabile e completo, facilmente personalizzabile e estendibile, e sufficientemente scalabile ed efficiente. I test di scalabilit`a e di efficienza, effettuati attraverso l’esecuzione dei principali metodi forniti e con- frontando i risultati con quelli ottenibili utilizzando un approccio puramente relazionale, hanno dimostrato le effettive prestazioni del sistema.

I casi d’uso proposti mostrano come effettivamente il sistema sia utiliz- zabile in situazioni reali e in ambienti molto eterogenei. Abbiamo mostrato infatti come pu`o essere utilizzato in un contesto commerciale senza che deb- bano essere implementate nuovi metodi o nuove classi, cos`ı come ben si presta ad essere esteso con nuove funzionalit`a per analisi pi`u particolari su dati di un motore di ricerca.

Bibliografia

[1] M. Atkinson, F. Bancilhon, D. DeWitt, K. Dittrich, D. Maier, and S. Zdonik. The object-oriented database system manifesto. In Proc. of the 1 st Int. Conf. on Deductive and Object-Oriented Databases, Kyoto, Japan. Elsevier Science Publishers B.V (NorthHolland) , 1990

[2] V. Bacarella. Progettazione e implementazione di un Web Object Store per applicazioni di Web Usage Mining. Tesi di Laurea, Dipartimento di Informatica, Pisa, 2003

[3] V. Bacarella, F. Giannotti, M. Nanni, D. Pedreschi. Discovery of unin- teresting web sites through traffic data analysis. In Proceedings of the 9th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery (DMKD 2004), September 2004

[4] R.Baraglia, and F. Silvestri. An Online Recommender System for Large Web Sites. In Proceedings of the 2004 IEEE/WIC/ACM International Conference on Web Intelligence (WI 2004). Bejing, China. September 20-24, 2004. pp 199-206

[5] F. Bonchi, F. Giannotti, C. Gozzi, G. Manco, M. Nanni, D. Pedre- schi, C. Renso, and S. Ruggieri. Web log data warehousing and mining for intelligent web caching. Data and Knowledge Engineering (DKE), 32(2):165-189, October 2001

[6] J. Borges, and M. Levene. Data mining of user navigation patterns. In Proceedings of the WEBKDD’99 Workshop on Web Usage Analysis and User Profiling. August 15, 1999

122 Bibliografia

[7] L.Catledge and J.Pitkow. Characterizing browsing behaviors on the World Wide Web. Computer Networks and ISDN Systems, 27(6), 1995

[8] R.G.G. Cattel ed., The Object Database Standard : ODMG-93, Rel. 1.2. Morgan Kaufmann, 1996

[9] X. Chen, Dissection of an application framework, Developing Application Frameworks in .NET, 2005

[10] M.-S. Chen, J.-S. Park, and P. S. Yu. Data Mining for Path Traversal Patterns in a Web Environment. Proceedings of the 16th International Conference on Distributed Computing Systems, pages 385–392, May 27- 30 1996

[11] Robert Cooley, Bamshad Mobasher, and Jaideep Srivastava. Web mi- ning: Information and pattern discovery on the world wide web. In ICTAI’97, Dec. 1997

[12] R. Cooley, B. Mobasher, and J. Srivastava. Data preparation for mining world wide web browsing patterns. Knowledge and Information Systems, 1(1), February 1999

[13] R. Cooley, B. Mobasher, and J. Srivastava. Grouping web page references into transactions for mining world wide web browsing patterns. Techni- cal Report TR 97-021, Dept. of Computer Science, Univ. of Minnesota, Minneapolis, USA, June 1997

[14] R. Cooley,P.-N. Tan, and J. Srivastava. Websift: the Web site informa- tion filter system. In Proceedings of the 1999 KDD Workshop on Web Mining, San Diego, CA. Springer-Verlag, 1999

[15] S.Demeyer,T.D. Meijer, O. Nierstrasz, and P. Steyaert. Design Guide- lines for ‘Tailorable’ Frameworks. Communications of the ACM, Oct. 1997

[16] O.Etzioni. The world wide web: Quagmire or gold mine? Comm.of the ACM,39(11):6568,1996

Bibliografia 123

[17] M. Fayad, and D. Schmid. Object-Oriented Application Framework Special Issue. Communications of the ACM, 40(10), October 1997 [18] R.Fielding, U.C.Irvine, L.Masinter, T.Berners-Lee. MIT/LCSandXerox

Corporation. RFC2396:UniformResourceIdentifiers(URI):GenericSyntax. August1998.http://www.ietf.org/rfc/rfc2396

[19] D. Gruhl, L. Chavet, D. Gibson, J. Meyer, P. Pattanayak, A. Tomkins, and J. Zien. How to build a webfountain: An architecture for very large- scale text analytics. IBM Systems Journal, 43(1), 2004

[20] J. Han, and M. Kamber. Data Mining: Concepts and Techniques. Morgan Kaufmann, 2000

[21] R. Kosala and H. Blockeel. Web mining research: A survey. SIGKDD Explorations, 2(1), June 2000

[22] J. MacQueen. Some Methods for Classification and Analysis of Multi- variate Observation. In Proc. 5th Berkley Symp. Math. Statist. Prob. 1967

[23] S.K. Madria, S.S. Bhowmick, W.K. Ng, and E.P. Lim. Research issues in Web data mining. In Proceedings of Data Warehousing and Knowledge Discovery, First International Conference, DaWaK ’99, pages 303-312, 1999

[24] F. Masseglia, P. Poncelet, and M. Teisseire. Using data mining techni- ques on Web access logs to dynamically improve hypertext structure. ACM sigweb Newsletter, 8(3):13-19, 1999

[25] R.R. Mettu, and C.G. Plaxton. Optimal time bounds for approximate clustering. Machine Learning, 56(1-3):35-60, 2004

[26] B. Mobasher, R. Cooley, and J. Srivastave. Automatic personalization based on Web usage mining. Technical Report TR99010, Department of Computer Science, DePaul University, 1999

[27] B. Mobasher, N. Jain, E.H. Han, and J. Srivastava. Web mining: Pattern discovery from world wide web transactions. Technical Report TR-96050,

124 Bibliografia

Department of Computer Science, University of Minnesota, M inneapolis, 1996

[28] M.D. Mulvenna, S.S.A nand,and A.G. Buchner. Personalization on the net using web mining: introduction. Communication of the ACM: Personalization, 43(8) ,August 2000

[29] M. Nanni. Speeding-Up Hierarchical Agglomerative Clustering in Presence of Expensive Metrics. PAKDD, 2005

[30] O. Nasraoui, H. Frigui, A. Joshi, and R. Krishnapuram. Mining Web Access Logs Using Relational Competitive Fuzzy Clustering. Eight Inter- national Fuzzy Systems Association World Congress - IFSA 99, Taipei, August 99

[31] M. Perkowiz, and O. Etzioni. Adaptive web sites: Automatically syntheti- zing web pages. In AAAI-98 - Fifteenth National Conference on Artificial Intelligence. Madison, USA, July 1998

[32] J. Pitkow. In search of reliable usage data on the WWW. Proc. of 6th Int. World Wide Web Conference, Santa Clara, CA, Apr. 1997

[33] K.A. Pitkow. The GigaBASE Object-Relational database system. http://www.ispras.ru/∼knizhnik

[34] P. Pirolli, J. Pitkow, R. Rao. Silk from a sow’s ear: Extracting usable structures from the Web. Proceedings of ACM SIGCHI Conference on Human Factors in Computing. 1996

[35] G. Rutili. Business Intelligence per ISP: caso di studio CWNet s.r.l. Tesi di Laurea, Dipartimento di Informatica, Pisa

[36] Y. Fu, K. Sandhu, and M.-Y. Shih. Clustering of Web users based on ac- cess patterns. In Proceedings of the 1999 KDD Workshop on Web Mining, San Diego, CA. Springer-Verlag, 1999

[37] H.A. Schmid. Systematic framework design by generalization. Commu- nications of the ACM, 40(10): 48-51, Oct. 1997

Bibliografia 125

[38] M. Spiliopoulu and L.C. Faulstich. Wum: A web utilization miner. In Proceedings of the EDBT Workshop WebDB98, Valencia, Spain, 1999. LNCS 1590, Springer Verlag

[39] M. Spiliopoulou, L. C. Faulstich, and K. Wilkler. A data miner analyzing the navigational behaviour of web users. In Proc. of the Workshop on Machine Learning in User Modelling of the ACAI99, Greece, July 1999 [40] J. Srivastava, R. Cooley, M. Deshpande, P-T. Tan. Web Usage Mining:

Discovery and Applications of Usage Patterns from Web Data. To appear in SIGKDD Explorations, (1) 2, 2000

[41] M. Stonebraker, and D. Moore. Object-Relational DBMS. Morgan Kaufmann Publishers, San Francisco, 1996

[42] W3C. World Wide Web committee web usage characterization activity, W3C Working Draft: Web Characterizations Terminology and Definitions Sheet, pages www.w3.org/1999/05/WCA-terms, 1999

[43] K. Wu and A. Ballman. Speed-tracer: A web usage mining and analysis tool. IBM Systems Journal, 37(1), 1998

[44] O. R. Zaiane, M. Xin, and J. Han. Discovering Web access patterns and trends by applying OLAP and data mining technology on Web logs. In Proc. Advances in Digital Libraries Conf. (ADL’98), Santa Babara, CA, April, 1998

[45] The common log file format.

http://www.w3.org/pub/WWW/, 1995 [46] The Squid web site. November, 2000.