Minería de patrones secuenciales

La minería de patrones secuenciales es un tema de minería de datos que se ocupa de encontrar patrones estadísticamente relevantes entre ejemplos de datos donde los valores se entregan en una secuencia. ^{[ 1 ] [ 2 ]} Generalmente se presume que los valores son discretos, por lo que la minería de series temporales está estrechamente relacionada, pero suele considerarse una actividad diferente. La minería de patrones secuenciales es un caso especial de minería de datos estructurados .

En este campo se abordan varios problemas computacionales tradicionales clave. Estos incluyen la creación de bases de datos e índices eficientes para información de secuencias, la extracción de patrones frecuentes, la comparación de secuencias para detectar similitudes y la recuperación de elementos faltantes en las secuencias. En general, los problemas de minería de secuencias se pueden clasificar como minería de cadenas, que generalmente se basa en algoritmos de procesamiento de cadenas, y minería de conjuntos de elementos , que generalmente se basa en el aprendizaje de reglas de asociación . Los modelos de procesos locales ^{[ 3 ]} extienden la minería de patrones secuenciales a patrones más complejos que pueden incluir elecciones (exclusivas), bucles y estructuras de concurrencia, además de la estructura de ordenación secuencial.

La minería de cadenas generalmente trabaja con un alfabeto limitado para los elementos que aparecen en una secuencia , pero la secuencia en sí puede ser muy larga. Ejemplos de un alfabeto pueden ser los del conjunto de caracteres ASCII utilizado en el lenguaje natural, las bases nucleotídicas 'A', 'G', 'C' y 'T' en secuencias de ADN , o los aminoácidos en secuencias de proteínas . En aplicaciones biológicas , el análisis de la disposición del alfabeto en cadenas puede utilizarse para examinar secuencias de genes y proteínas y determinar sus propiedades. Conocer la secuencia de letras de un ADN o una proteína no es un objetivo final en sí mismo. Más bien, la tarea principal es comprender la secuencia en términos de su estructura y función biológica . Esto generalmente se logra primero identificando regiones individuales o unidades estructurales dentro de cada secuencia y luego asignando una función a cada unidad estructural. En muchos casos, esto requiere comparar una secuencia dada con secuencias estudiadas previamente. La comparación entre las cadenas se complica cuando ocurren inserciones , deleciones y mutaciones en una cadena.

Abouelhoda y Ghanem (2010) presentan una revisión y taxonomía de los algoritmos clave para la comparación de secuencias para bioinformática, que incluyen: ^{[ 4 ]}

• Problemas relacionados con repeticiones: que tratan sobre operaciones en secuencias individuales y pueden basarse en métodos de coincidencia de cadenas exactas o aproximadas para encontrar repeticiones dispersas de longitud fija y de longitud máxima, encontrar repeticiones en tándem y encontrar subsecuencias únicas y subsecuencias faltantes (sin escribir).
• Problemas de alineación: se refieren a la comparación entre cadenas mediante la alineación de una o más secuencias. Algunos ejemplos de métodos populares son BLAST , para comparar una sola secuencia con múltiples secuencias en una base de datos, y ClustalW, para alineamientos múltiples. Los algoritmos de alineación pueden basarse en métodos exactos o aproximados, y también se clasifican en alineamientos globales, semiglobales y locales. Véase alineación de secuencias .

Algunos problemas en la minería de secuencias se prestan al descubrimiento de conjuntos de elementos frecuentes y el orden en que aparecen. Por ejemplo, se buscan reglas del tipo "si un cliente compra un coche, es probable que compre un seguro en el plazo de una semana", o, en el contexto de los precios de las acciones, "si Nokia y Ericsson suben, es probable que Motorola y Samsung suban en los próximos dos días". Tradicionalmente, la minería de conjuntos de elementos se utiliza en aplicaciones de marketing para descubrir regularidades entre elementos que aparecen con frecuencia en grandes transacciones. Por ejemplo, analizando las transacciones de las cestas de la compra de los clientes en un supermercado, se puede generar una regla que diga: "si un cliente compra cebollas y patatas juntas, es probable que también compre carne picada para hamburguesas en la misma transacción".

Han et al. (2007) presentan una revisión y taxonomía de los algoritmos clave para la minería de conjuntos de elementos. ^{[ 5 ]}

Las dos técnicas comunes que se aplican a las bases de datos de secuencias para la minería de conjuntos de elementos frecuentes son el influyente algoritmo Apriori y la técnica más reciente de crecimiento de FP .

Con una gran variedad de productos y comportamientos de compra de los usuarios, el espacio en los estantes donde se exhiben los productos es uno de los recursos más importantes en el entorno minorista. Los minoristas no solo pueden aumentar sus ganancias, sino también reducir costos mediante una gestión adecuada de la asignación del espacio en los estantes y la exhibición de los productos. Para resolver este problema, George y Binu (2013) propusieron un enfoque para extraer patrones de compra de los usuarios utilizando el algoritmo PrefixSpan y colocar los productos en los estantes según el orden de los patrones de compra extraídos. ^{[ 6 ]}

Los algoritmos más utilizados incluyen:

• Algoritmo GSP
• Descubrimiento de patrones secuenciales mediante clases de equivalencia (SPADE)
• FreeSpan
• PrefixSpan
• MAPres ^{[ 7 ]}
• Seq2Pat (para minería de patrones secuenciales basada en restricciones) ^{[ 8 ] [ 9 ]}

• Extracción de colocaciones : técnica computacional para encontrar secuencias de palabras. 
• Minería de procesos : técnica de minería de datos que utiliza registros de eventos. 
• Análisis de secuencias : identificación y estudio de secuencias genómicas. 
• Análisis de secuencias en ciencias sociales – Análisis de conjuntos de secuencias categóricas 
• Agrupación de secuencias
• Etiquetado de secuencias

• SPMF incluye implementaciones de código abierto de GSP, PrefixSpan, SPADE, SPAM y muchas otras.