Sviluppi Futuri

Il lavoro svolto in questa tesi proseguirà con il miglioramento dell’algoritmo GenPrefixGrowth. Un primo obbiettivo è quello di far funzionare in maniera ottimale l’algoritmo anche nel caso in cui il DB sia formato da tante sequenze che hanno un numero elevato di items uguali, evitando l’incontrollabile crescita dei DB proiettati. Si cercherà di trovare una soluzione efficiente per superare questo limite affinché si rispetti la seguente assunzione: la dimensione dei DB proiettati non deve eccedere la dimensione del DB originale.

Per semplicità in questa tesi si è implementata una versione di GenPrefixGrowth solo con vincoli temporali ed esistenziali, ma per scoprire nuove informazioni utili all’analisi dei Logs in Brite si aggiungeranno i vincoli di contenuto, anche quelli non esprimibili con espressioni regolari, utilizzando i linguaggi liberi da contesto.

In questa nuova versione l’algoritmo dovrà prevedere la programmazione di un automa a pila con dei metodi che controllano se una sequenza soddisfa il linguaggio. Un altro naturale miglioramento è rendere GenPrefixGrowth out memory, in particolare una possibile soluzione è quella di integrare un tipo di proiezione dei DB (bi-level) per processing basati su disco [28] e la pseudo proiezione quando l’intero database può essere interamente contenuto in memoria principale.

Ringraziamenti

Un primo ringraziamento, per la loro disponibilità ed i loro suggerimenti durante la stesura di questa tesi, va ai miei due relatori: Franco Turini e Miriam Baglioni.

Un secondo grazie va ad Elena e Pasqualina che soprattutto negli ultimi mesi mi hanno supportato e sopportato anche con la loro simpatia.

Grazie papà e mamma: se oggi sono qui a festeggiare questo giorno è anche merito

vostro perché avete creduto in me e con sacrificio mi avete permesso di raggiungere anche questo traguardo.

Grazie Davide: in questi anni hai contribuito anche tu ricaricandomi il cellulare

perché ero sempre al verde…ho perso proprio il conto dei soldi che ti devo!

Grazie Fabrizio: mi hai veramente sopportato, soprattutto nell’ultimo periodo della

tesi. Mi sei sempre stato vicino con il tuo amore anche negli anni in cui eravamo lontani. Il regalo più grande che mi hai fatto è stato il giorno che mi hai detto che ti trasferivano a Pisa…grazie!

Grazie zia Antioca: per i tuoi consigli e per avermi sempre sostenuto. Con te ho

trascorso molti periodi di pausa tra un esame e l’altro…mi sono veramente divertita con una zia e con un’amica!

Grazie a tutti i miei amici “pisani”…in questi anni di Università avete lasciato un segno, in particolare:

Angela: amica da sempre e coinquila da un anno…sei stata sempre presente in tutti gli

anni a Pisa. Durante questa tesi mi hai sostenuto e sopportato, grazie!

Marco e Titty: la vostra parola d’ordine è sempre stata “stai serena”, grazie per il

vostro sostegno…sono stata molto contenta di avervi fatto da testimone…ho rotto il piatto solo a voi!!!!

Luigi e Maria: anche da Roma mi siete stati vicini…genietto grazie per i tuoi consigli!

Ricordatevi che quando vi siete messi insieme io c’ero!!!!

Luigi: con te ho condiviso la tensione di tantissimi esami e con te ho preso la laurea di

primo livello…è stato un percorso con delle difficoltà, ma ci siamo fatti anche tante risate!

Andrea: sei tra le prime persone che ho conosciuto, non dimenticherò mai quando mi

hai chiesto se venivo da Milano…mi scappa ancora da ridere! Grazie per i tuoi preziosi consigli!

Elisa: ricordo la nostra convivenza a Paradisa…quanti pranzi e quante cene

insieme…sono stata veramente bene!

Vanessa: sei arrivata da Perugia negli ultimi anni di Università ma è bastato poco per

fare subito amicizia…grazie per la tua disponibilità soprattutto in questi ultimi mesi!

Katia, Vale e Nunzia: abbiamo trascorso insieme tantissimi momenti, alcuni positivi

ed altri meno…anche se siamo lontane l’amicizia ed il ricordo del collegio ci terrà comunque unite!

Marida e Gavino: in quest’ultimo anno, insieme a Fabrizio, siete stati la mia

“famiglia” di Pisa, ci siamo divertiti tanto…quanti pranzi della domenica abbiamo organizzato…grazie di tutto!

Grazie a tutti gli amici di Magomadas…con voi ho trascorso momenti indimenticabili!

Bibliografia

[1] www.economia.unimi.it/lda/mastermida/Ferrari_slide.

[2] J. Han e M. Kamber. “Data Mining: Concepts and Techniques”. Morgan- Kaufman Publishers, 2001.

[3] F. Giannotti e D. Pedreschi Pisa KDD Lab, CNUCE-CNR e Università Pisa http://www-kdd.cnuce.cnr.it.

[4] W. H. Inmon. “Building the Data Warehouse”. New York: John Wiley& Sons, 1996.

[5] P. Cabena, P. Hadjinian, R. Stadler, J. Verhees, A. Zanasi “Discovering Data

Mining- From Concept to Implementation”. SIGKDD Explorations, volume 1 n°

1, pages 44-45, 1999.

[6] M. Wojciechowski “Discovering and Processing Sequential Patterns in

Databases”. Phd Workshop, 2000.

[7] R. Agrawal e R. Srikant. “Mining Sequential Patterns”. Proc. of the 11th Int’l Conference on Data Engineering, S. Philip e A. S. P. Chen, pages 3-14, 1995.

[8] www.dsi.it/ ̃dm.

[9] www.disi.unige.it/person/DelzannoG/AI2/dm.ppt.

[10] www.archesis.it/white/oracle/dwh.html.

[12] Z. Zheng. “Construction new attributes for tree learning”, phd Thesis, Departement of Computer Science, University of Sidney, NSW, Australia, 1996.

[13] J.R. Quinlan. “C4_5: programs for machine learning”. Morgan Kaufmann Publishers Inc., 2002.

[14] R. Agrawal, T. Imielinski e A. Swami. “Mining Associations between sets of

items in Massive Databases”. In Proceedind of ACM SIGMOD, Int’l Conference

on Management of Data, Washington D. C., pages 207-216, 1993.

[15] R. Agrawal, R.Srikant. “Fast algorithms for mining association rules”. In Proc. of the 20th Intl. Conf. on Very Larges Data Bases, J. B. Bocca, M. Jarke e C. Zaniolo, pages 487-499, 1994.

[16] C. Antunes A.L. Oliveira. “Sequential Pattern Mining Algorithms: Trade-offs

between Speed and Memory". In Workshop on Mining Graphs, Tree and Sequence

(MGTS-ECML/PKDD), 2004.

[17] J. Han, J. Pie, B. Mortazavi-Asl, Q. Chen, U. Dayal e M. C. Hsu “FreeSpan:

Frequent Pattern-Projected Sequential Pattern Mining”. In Proc. Of the 6th ACM SIGKDD Int. Conference on Knowledge and Data Mining (KDD’2000), 2000.

[18] J.S.Park, M.S. Chen, and P.S. Yu. “An effective hash-based algorithm for

mining association rules”. In Proc. 1995 ACM-SIGMOD Int. Conf. Management

of Data, M.J. Carey e D.A. Schneider, pages 175-186, 1995.

[19] J. Han and Y. Fu. “Discovery of multiple-level association rules from large

databases”. In Proc. 1995 In. Conf. Very Large Data Bases, pages 420-431,

1995.

[20] A. Bavarese, E. Omiecinski, and S. Navate. “An efficient algorithm for mining

association rules in large databases”. The Very Large Data Bases Journal, pages

[21] F. Masseglia, M. Teisseire, P. Poncelet. “Sequential Pattern Mining: A Survey

on Issues and Approaches”. In Encyclopedia of Data Warehaousing and Mining,

Information Science Publishing, 2005.

[22] J. Pei, J. Han, W. Wang. “Mining Sequential Patterns with Constraints in Large

Databases”. Proc. of the 11th International Conf. on Information and Knowledge Management, ACM Press, pages 18-25, 2002.

[23] M. Seno e G. Karypis. “SLPMiner: An Algorithm for Finding Frequent

Sequential Patterns Usinig Lenght-Decreasing Support Constraint”. 2nd IEEE Conference on Data Mining, pages 418-425, 2001.

[24] N. Ikizler. “Mining Sequential Pattern: an Overview”. Department of Computer Science, 2001.

[25] H. Mannil, H.Toivonen e A. I. Verkamo. ”Discovery of frequent episodes in

event frequent”. Data Mining and Knowledge Discovery, volume 1 n°3, pages

259-289, 1997.

[26] B. Mortasavi-Asl. “Discovering and Mining User Web-Page Traversal

Patterns”, 2001.

[27] R. Srikant e R. Agrawal. “Mining Sequential patterns: Generalizations and

Performance Improvements”. In Proc. 5th Int’l Conference Extending Database Technology, volume 1057, P.M.G. Apers, M. Bouzeghoub, G. Gardarin, pages 3- 17, 1996.

[28] J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto. “PrefixSpan: Mining Sequential

Patterns Efficiently by Prefix-Projected Pattern Growth”, In ICDE’01, pages 215-

226, 2001.

[29] M. N. Garofalakis, R. Rastogi, K. Shim. “SPIRIT: Sequential Pattern Mining

[30] M. J. Zaki. “SPADE: An efficient algorithm for mining frequent sequences”, Machine Learning, volume 42 n° 1-2, pages 31-60, 2001.

[31] M. J. Zaki. “Sequence Mining in Categorical Domains: Incorporating

Constraints”, 9th International Conference on Information and Knowledge Management, pages 422-429, 2000.

[32] A. J. M. M. Weijters, W. M. P. van der Aalst “Process Mining: Discovering

Workflow Models from Event-Based Data”, Proc. 13th Belgium-Netherlands Conf. on Artificial Intelligence, pages 283-290, 2001.

[33] R. Agrawal, D. Gunopulos, F. Leymann. “Mining Process Models from

Workflow Logs”, Lecture Notes in Computer Science, volume 1377, pages 469-

490, 1998.

[34] G. Greco, A. Guzzo, L. Pontieri, D. Saccà. “Discovering Expressive Process

Models by Clustering Log Traces”, IEEE Transactions on Knowledge and Data

Engineering, volume 18 n° 8, pages 1010-1027, 2006.

[35] G. Greco, A.Guzzo, G. Manco, L. Pontieri, D. Saccà. “Mining Constrained

Graphs: The Case of Workflow Systems”, Lecture Notes in Artificial

Intelligence, volume 3848, pages 155-171, 2004.

[36] X. Yan, J. Han. “gSpan: Graph-Based Substructure Pattern Mining”, 2nd IEEE Conf. Data Mining, pages 721-723, 2002.

[37] T. Washio, H. Motoda. “State of the Art of Graph-based Data Mining”, ACM SIGKDD Explorations Newsletter, volume 5 n° 1, pages 59-68, 2003.

[38] A. Inokuchi, T. Washio, H. Motoda. “An Apriori-based algorithm for mining

frequent substructures from graph data”, Principle of Data Mining and

[39] A. K. A. de Medeiros, W. M. P. van der Aalst, A. J. M. M. Weijters. “Workflow

Mining: Current Status and Future Directions”, On the Move of Meaningful

Internet System, serie “LNCS”, volume 2888, 2003.

[40] W. M. P. van der Aalst, A. J. M. M. Weijters, L. Maruster. “Workflow Mining:

Discovering process models from events logs”, IEEE Transactions on

Knowledge and Data Engineering, volume 16 n° 9, pages 1128-1142, 2004.

[41] G. Greco, A. Guzzo, G. Manco, D. Saccà. “Mining and Reasoning on

Workflows”, IEEE Transactions on Knowledge and Data Engineering, volume

17 n° 4, pages 519-534, 2005.

[42] L. B. Holder, D. J. Cook. “Graph-Based Data Mining”, IEEE Intelligence System, volume 15 n° 2, pages 32-41, 2000.

[43] C. M. Antunes. “Pattern Mining over Miminal Event Sequences using Constraint

Relaxations”, http://mega.ist.utl.pt/ cman/artigos/antunes.phd.thesis, 2005.

[44] D. Iozzia. “Studio, progettazione ed implementazione di un Algoritmo per il

calcolo di Sequential Pattern”, Tesi di Laurea: relatori Prof. F. Turini e Dr. S.

Ruggieri, 2003.

[45] C. Antunes, A.L. Oliverira. “Generalization of Pattern-Growth Methods for

Sequential Pattern Mining with Gap Constraints”, Int’l Conf Machine and Data

Mining, pages 239-251, 2003.

[46] S. Ruggieri. “Data Preprocessing su Dataset Vivacity”, Università di Pisa Dipartimento di Informatica, versione 3.0, 2003.

[47] W.M.P. van der Aalst, B.F. van Dongen, J. Herbst, L. Maruster, G. Schimm, and A.J.M.M. Weijters, “Workflow mining: A survey of issues and approaches,” Data and Knowledge Engineering, volume 47, n° 2, pages 237–267, 2003.

[48] X. Yan and J. Han. “CloseGraph: Mining closed frequent graph patterns”, In Proc. ACM Int. Conf. on Knowledge Discovery and Data Mining (KDD’03), pages 286–295, 2003.

[49] M. Worlein, T. Meinl, I. Ficher e M. Philippsen. “A Quantitative Comparison of

the SubGraphs Miners Mofa, gSpan, FFSM and Gaston ”, PKDD 2005, LNAI