Un nuevo algoritmo eficiente para la búsqueda de patrones parciales frecuentes

Abstract

Un patrón periódico es una serie específica de símbolos que aparece repetidas veces a lo largo de una serie de tiempo. Los patrones periódicos emergen de manera natural dentro de los datos secuenciales: rutinas, errores sistemáticos, repeticiones. La repetición embebida en nuestro propio genoma no aparece para introducir redundancia, sino para cumplir una función auxiliar. La búsqueda de patrones periódicos frecuentes (BPPF) es una forma de minería de datos cuyo propósito es descubrir los patrones periódicos más prevalentes en una base de datos de series de tiempo. De interés para la BPPF son dos formas de patrones periódicos: completos y parciales. Para clasificar un patrón periódico como completo, cada elemento del patrón debe exhibir periodicidad. Un patrón periódico parcial (PPP) es una definición menos estricta donde solo ciertos elementos del patrón exhiben periodicidad, y al resto se les puede denominar “comodines” (Gadiraju, 2013). Este estudio tratará exclusivamente de la BPPF de patrones parciales, o BPPPF. El problema de descubrir PPPs en una base de datos de series de tiempo es altamente complejo, puesto que el número de patrones por probar aumenta combinatorialmente con respecto al número de ítems (distintos valores que la serie de tiempo puede tomar en cada posición) y al largo, o periodo, del patrón. Soluciones convencionales involucran de una forma u otra al algoritmo Apriori para reducir dramáticamente el espacio de búsqueda. En su implementación más ingenua, el algoritmo Apriori requiere en el peor caso hacer tantas lecturas a la base de datos como el largo del patrón de interés. Debido a esto, esta implementación no es escalable a la búsqueda de patrones largos. Soluciones más modernas como FP-growth o Max-subpattern, sin embargo, emplean estructuras que optimizan la búsqueda y requieren a lo más dos lecturas de la base de datos. Un aspecto común a estas soluciones es que todas determinan el soporte y/o la confianza de un PPP para determinar si este efectivamente es frecuente. Determinar ambos indicadores requiere una o múltiples búsquedas exhaustivas de la base de datos. Sin embargo, se puede argumentar que en la tarea de descubrir patrones interesantes existen instancias en que determinar con exactitud el soporte y la confianza no es más útil que reportar, por ejemplo, un ranking o lista ordenada de los patrones más frecuentes. Los valores exactos de soporte y confianza son útiles para determinar esta jerarquía, pero al fin y al cabo, asumiendo garantías mínimas, para unexperto la información más relevante son los patrones mismos. La razón por la que este argumento es siquiera una consideración es que el uso de técnicas aproximadas de minería de datos abre las puertas a nuevas implementaciones más eficientes con estructuras de datos escalables. Con esta posibilidad en mente, en este estudio se propuso explorar métodos aproximados para la BPPPF. Con pocos antecedentes, se tuvo que conducir una revisión de la literatura acerca de métodos aproximados de búsqueda e indexación en bases de datos de series de tiempo. Un método prometedor para estos propósitos es una variante de locality-sensitive hashing (LSH) denominada min-hashing (Cohen et al., 2001). A grandes rasgos, LSH es una familia de algoritmos para la búsqueda aproximada que emplean funciones de hash con la conveniente propiedad de que la colisión entre datos en una tabla hash es más probable entre datos similares que entre datos diferentes. La métrica más común de similitud es la distancia euclideana o el largo de la línea entre dos puntos en un espacio. Existe una definición clara de la distancia euclideana entre series de tiempo, y aún otras definiciones más elaboradas que dan cuenta de la maleabilidad temporal de las series de tiempo (dynamic time warping), y aunque estas métricas sirven para determinar la similitud entre series de tiempo con datos en un espacio lineal, no así en el tipo de series de tiempo usualmente involucradas en la BPPPF. Estas últimas consisten usualmente de una secuencia ordenada de ítems denotados por un identificador, sin garantías de ordinalidad. Una métrica mucho más conveniente para este caso viene dada por el coeficiente de Jaccard. Con min-hashing es posible comparar segmentos de series de tiempo y descubrir segmentos similares, y esto ha sido empleado exitosamente en la tarea de determinar infracciones al derecho de autor en bases de datos multimedia (tarea popularmente conocida como Content ID) (Chiu et al., 2010). La ventaja más importante que se le atribuye a los métodos de búsqueda aproximada es que estos no requieren de estructuras de datos "volatiles", es decir, estructuras cuya dimensionalidad es muy sensible al tamaño del espacio de búsqueda. Otros algoritmos como FP-growth y Maxsubpattern presentan este problema donde el volumen de la estructura de árbol empleada para indexar una base de datos crece a una velocidad insostenible cuando el número de símbolos supera los cientos o miles. Teniendo en cuenta las posibles aplicaciones de min-hashing y LSH, este estudio propone adaptar esta técnica para resolver la BPPPF.