DUGi

Implementació i millora d’un algoritme de Time-Interval-Related-Pattern (TIRP) Mining incremental per ser executat en paral·lel i en C++

http://dugi.udg.edu/item/http:@@@@hdl.handle.net@@10256@@24539

Els algortimes de mineria de "Time-interval-related pattern (TIRP) consisteixen en trobar patrons de relacions temporals tal com "A comença B". El seu ús pioner era trobar patrons de compres, però també pot tindre utilitat en altres camps, com per exemple per fer detecció i classificació en les seqüencies d’ADN, detectar atacs i/o buscar signatures dels virus, prediccions de preus dels estocs, etc. TIRP mining és una família de mètodes de "sequential patern mining"que permeten minar els patrons amb relacions totals o parcials en intervals temporals d’esdeveniments. El problema que presenten aquesta classe d’algoritmes és que tenen un cost computacional elevat i és per això que es fa de manera incremental: en aquest cas al tractar-se d’una estructura de dades en arbre, es computa per nivells. En l’article [1], s’introdueix un nou algoritme per minar TIRPS anomenat "vert- TIRP", que combina una representació eficient d’aquests patrons utilitzant les propietats de transitivitat que tenen, amb una estratègia d’aparellament que ordena les relacions temporals per així accelerar el procés de mineria. A més presenta una definició robusta de les relacions temporals que elimina les ambigüitats entre relacions fent ús d’un valor "èpsilon". En l’article esmentat es pot trobar un enllaç del repositori de l’algoritme implementat en python. Com s’explica en la secció anterior, aquesta classe d’algoritmes tenen un cost computacional molt elevat. L’objectiu del projecte és implementar l’algoritme "vert- TIRP"en C++ per disminuir el temps de càlcul i comparar els resultats amb el "vert- TIRP"original. El llenguatge C++ és conegut per ser ràpid i eficient, a més disposa de punters que millorarien significativament l’eficiència i diverses opcions de multithreading

9