Algoritmo paralelo para extraer patrones negativos en secuencias

Abstract

[Resumen]: La minería de secuencias es un subcampo dentro de la minería de datos que consiste en encontrar patrones estadísticamente relevantes en colecciones de datos representados de forma secuencial. Debido a la frecuencia con que aparecen este tipo de datos en escenarios reales, esta técnica constituye uno de los métodos más populares de descubrimiento de patrones. La aproximación más clásica se centra solo en la repetición de eventos positivos, pero en muchas ocasiones es interesante fijarse también en la ausencia de ciertos eventos. Los algoritmos de extracción de patrones negativos, como eNSP o NegPSpan, son aquellos que analizan las secuencias buscando patrones repetitivos donde no aparezca un cierto evento. El mayor problema de estos algoritmos es su alta complejidad computacional, muchomayor que en las aproximaciones convencionales, al considerar también eventos negativos. Esto hace que requieran un tiempo demasiado elevado para ser ejecutados ante conjuntos de datos de gran tamaño. En este Trabajo de Fin de Grado se desarrolló el algoritmo Par_NegPS, una versión paralela de NegPSpan que permite ejecutarlo en entornos de computación de altas prestaciones para reducir el tiempo de ejecución de este algoritmo. Para esto, se utilizó MPI, un estándar de paso de mensajes entre procesos con el que se pueden aprovechar varias CPUs en sistemas de memoria distribuida, como los clústeres. El desarrollo de este algoritmo incluyó varias versiones diferentes, cada una de las cuales se probó en un clúster. Los resultados obtenidos tras estas pruebas mostraron que los objetivos planteados durante el trabajo se cumplieron, ya que el tiempo total de ejecución del algoritmo se redujo considerablemente al utilizar varios procesadores.

[Abstract]: Sequence mining is a subfield of data mining concerned with discovering statistically relevant patterns in sequentially represented datasets. Because such data frequently appear in real-world applications, this technique has become one of the most widely used methods for pattern discovery. The classical approach focuses exclusively on the repetition of positive events, but in many cases it is also important to consider the absence of certain events. Negative sequential pattern extraction algorithms, such as eNSP or NegPSpan, analyze sequences to identify repetitive patterns where specific events do not occur. The main challenge of these algorithms lies in their high computational complexity, which is significantly greater than that of conventional approaches due to the inclusion of negative events. As a result, their execution time becomes prohibitive when applied to large-scale datasets. In this thesis, a parallel version of NegPSpan, called Par_NegPS, was developed to run in high-performance computing environments in order to reduce execution time of this algorithm. To achieve this, MPI, a message-passing standard that enables the use of multiple CPUs in distributed memory systems such as clusters, was employed. The development process included several versions of the algorithm, each of which was tested on a cluster. The experimental results confirmed that the objectives of the work were achieved, as the total execution time of the algorithm was considerably reduced when multiple processors were used.