Minería de patrones secuenciales - Sequential pattern mining

La minería de patrones secuencial es un tema de la 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. Por lo general, se presume que los valores son discretos y, por lo tanto , la minería de series de tiempo está estrechamente relacionada, pero generalmente se considera una actividad diferente. La minería de patrones secuenciales es un caso especial de minería de datos estructurados .

Hay varios problemas computacionales tradicionales clave que se abordan en este campo. Estos incluyen la creación de bases de datos e índices eficientes para la información de secuencia, la extracción de los patrones que ocurren con frecuencia, la comparación de secuencias en busca de similitudes y la recuperación de miembros de secuencia faltantes. En general, los problemas de minería de secuencias se pueden clasificar como minería de cadenas, que normalmente se basa en algoritmos de procesamiento de cadenas y minería de conjuntos de elementos, que normalmente se basa en el aprendizaje de reglas de asociación . Los modelos de procesos locales extienden la extracción de patrones secuenciales a patrones más complejos que pueden incluir opciones (exclusivas), bucles y construcciones de simultaneidad además de la construcción de ordenamiento secuencial.

Minería de cadenas

La minería de cadenas generalmente se ocupa de un alfabeto limitado para los elementos que aparecen en una secuencia , pero la secuencia en sí puede ser generalmente muy larga. Los ejemplos de un alfabeto pueden ser los del conjunto de caracteres ASCII utilizados en el texto en lenguaje natural, las bases de nucleótidos 'A', 'G', 'C' y 'T' en las secuencias de ADN o los aminoácidos para las secuencias de proteínas . En aplicaciones de biología , el análisis de la disposición del alfabeto en cadenas se puede utilizar para examinar secuencias de genes y proteínas para 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 . Por lo general, esto 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 determinada con otras previamente estudiadas. La comparación entre las cadenas se complica cuando se producen inserciones , eliminaciones y mutaciones en una cadena.

Abouelhoda & Ghanem (2010) presentan un estudio y una taxonomía de los algoritmos clave para la comparación de secuencias para la bioinformática, que incluyen:

  • Problemas relacionados con la repetición: que tratan con operaciones en secuencias únicas y se pueden basar en métodos de coincidencia de cadenas exactas o aproximadas para encontrar repeticiones de longitud fija y longitud máxima dispersas, encontrar repeticiones en tándem y encontrar subsecuencias únicas y faltantes (sin ortografía) subsecuencias.
  • Problemas de alineación: que tratan con la comparación entre cadenas alineando primero una o más secuencias; ejemplos de métodos populares incluyen BLAST para comparar una sola secuencia con múltiples secuencias en una base de datos y ClustalW para múltiples alineaciones. Los algoritmos de alineación se pueden basar en métodos exactos o aproximados, y también se pueden clasificar como alineaciones globales, alineaciones semiglobales y alineaciones locales. Ver alineación de secuencia .

Minería de conjuntos de elementos

Algunos problemas en la minería de secuencias se prestan a descubrir conjuntos de elementos frecuentes y el orden en que aparecen, por ejemplo, uno está buscando reglas de la forma "si un {cliente compra un automóvil}, es probable que {compre un seguro} dentro de una semana ", o en el contexto de los precios de las acciones," si {Nokia sube y Ericsson sube}, es probable que {Motorola suba y Samsung suba} en 2 días ". Tradicionalmente, la minería de conjuntos de elementos se utiliza en aplicaciones de marketing para descubrir regularidades entre elementos que concurren con frecuencia en transacciones grandes. Por ejemplo, al analizar las transacciones de las cestas de compra de los clientes en un supermercado, se puede producir una regla que diga "si un cliente compra cebollas y patatas juntas, es probable que también compre carne de hamburguesa en la misma transacción".

Han et al. Presentan una encuesta y una taxonomía de los algoritmos clave para la minería de conjuntos de elementos. (2007).

Las dos técnicas comunes que se aplican a las bases de datos de secuencia para la extracción frecuente de conjuntos de elementos son el influyente algoritmo a priori y la técnica de crecimiento FP más reciente .

Aplicaciones

Con una gran variedad de productos y comportamientos de compra de los usuarios, el estante en el que 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 los costos mediante la gestión adecuada de la asignación de espacio en los estantes y la exhibición de productos. Para resolver este problema, George y Binu (2013) han propuesto un enfoque para minar los 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.

Algoritmos

Los algoritmos de uso común incluyen:

  • Algoritmo GSP
  • Descubrimiento de patrones secuenciales usando clases de equivalencia (SPADE)
  • FreeSpan
  • PrefijoSpan
  • MAPres
  • Seq2Pat (para minería de patrones secuenciales basada en restricciones)

Ver también

Referencias

enlaces externos

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