Algoritmo de minería de datos, búsqueda de patrones periódicos en función del tiempo en base de datos espacio-temporales

Abstract

En los últimos años las Bases de Datos Espacio-Temporales han alcanzado un gran interés por parte de la comunidad científica, esto debido a la creciente demanda de servicios de móviles basadas en la localización, al progreso de los sistemas de posicionamiento global (GPS) así como también a los sistemas de Información Geográficos (SIG). Más aún, la creciente generación de información (del orden de los terabytes, como por ejemplo en los centros astronómicos) en diversos ámbitos de la ciencia y aplicaciones convencionales, han dado lugar a un nuevo concepto llamado Big Data Analytics. Big Data Analytics (note que los fundamentos de Minería de Datos son comunes para esta nueva área, por lo que la diferencia radica en la cantidad de información) agrupa un conjunto de metodologías y desarrollos matemáticos para almacenar, analizar y cruzar información con el objeto de encontrar patrones de comportamiento ocultos en los datos. Un patrón es una característica o rasgo constante y recurrente que ayuda a identificar un fenómeno o problema y sirve como indicador o modelo para predecir su comportamiento futuro. Así uno de los principales objetivos de este proyecto de título, es analizar y diseñar e implementar un algoritmo eficiente para detectar patrones secuenciales. Un patrón secuencial es una secuencia ordenada de eventos en el tiempo. Con el objeto de corroborar la eficiencia de nuestro algoritmo hemos implementado dos algoritmos ampliamente utilizados en la literatura, el algoritmo Apriori y el algoritmo Max-Subpattern. Para verificar la correctitud y eficiencia de nuestro algoritmo denominado Minus-F1 hemos utilizado datos sintéticos. Adicionalmente, hemos verificado la eficiencia (el tiempo que toma el algoritmo en encontrar patrones) de los tres algoritmos utilizando una porción de una base de datos real llamada GeoLife. Para lograr esto los datos de GeoLife han sido preprocesados y los eventos espacio-temporales han sido codificados como secuencias de texto (eventos en el espacio-tiempo), lo cual permite un mejor procesamiento. Los algoritmos fueron implementados en Java y los resultados empíricos finales muestran que nuestro algoritmo supera ampliamente a Apriori y Max-Subpttern en cuanto al ahorro de procesamiento, por lo que esta propuesta resulta ser la más eficiente. Finalmente, una importante contribución de este proyecto de título, es que presentamos el orden en función del tiempo de los tres algoritmos, ya que en la literatura actual no es posible encontrar dicho orden para los algoritmos Apriori y 𝑛 Max-Subpattern.