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. [1] 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 construcció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 [2] extienden la minería de patrones secuenciales a patrones más complejos que pueden incluir opciones (exclusivas), bucles y construcciones de concurrencia 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 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: [3]
- 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 alineamientos. 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). [4]
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. [5]
Algoritmos
Los algoritmos de uso común incluyen:
- Algoritmo GSP
- Descubrimiento de patrones secuenciales usando clases de equivalencia (SPADE)
- FreeSpan
- PrefijoSpan
- MAPres [6]
- Seq2Pat (para minería de patrones secuenciales basada en restricciones) [7]
Ver también
Referencias
- ^ Mabroukeh, NR; Ezeife, CI (2010). "Una taxonomía de algoritmos de minería de patrones secuenciales". Encuestas de computación ACM . 43 : 1-41. CiteSeerX 10.1.1.332.4745 . doi : 10.1145 / 1824795.1824798 . S2CID 207180619 .
- ^ Impuesto, N .; Sidorova, N .; Haakma, R .; van der Aalst, Wil MP (2016). "Modelos de procesos locales mineros". Revista de Innovación en Ecosistemas Digitales . 3 (2): 183–196. arXiv : 1606.06066 . doi : 10.1016 / j.jides.2016.11.001 . S2CID 10872379 .
- ^ Abouelhoda, M .; Ghanem, M. (2010). "Minería de cadenas en bioinformática". En Gaber, MM (ed.). Minería de datos científicos y descubrimiento de conocimientos . Saltador. doi : 10.1007 / 978-3-642-02788-8_9 . ISBN 978-3-642-02787-1.
- ^ Han, J .; Cheng, H .; Xin, D .; Yan, X. (2007). "Minería de patrones frecuentes: estado actual y direcciones futuras" . Minería de datos y descubrimiento de conocimientos . 15 (1): 55–86. doi : 10.1007 / s10618-006-0059-1 .
- ^ George, A .; Binu, D. (2013). "Una aproximación a la colocación de productos en supermercados mediante el algoritmo PrefixSpan" . Revista de Ciencias de la Información y Computación de la Universidad Rey Saud . 25 (1): 77–87. doi : 10.1016 / j.jksuci.2012.07.001 .
- ^ Ahmad, Ishtiaq; Qazi, Wajahat M .; Khurshid, Ahmed; Ahmad, Munir; Hoessli, Daniel C .; Khawaja, Iffat; Choudhary, M. Iqbal; Shakoori, Abdul R .; Nasir-ud-Din (1 de mayo de 2008). "MAPRes: patrones de asociación de minería entre los residuos de aminoácidos preferidos en la vecindad de los aminoácidos dirigidos a modificaciones postraduccionales". Proteómica . 8 (10): 1954-1958. doi : 10.1002 / pmic.200700657 . PMID 18491291 . S2CID 22362167 .
- ^ Hosseininasab A, van Hoeve WJ, Cire AA (2019). "Minería de patrones secuenciales basada en restricciones con diagramas de decisión" . Actas de la Conferencia AAAI sobre Inteligencia Artificial . 33 : 1495-1502. doi : 10.1609 / aaai.v33i01.33011495 . S2CID 53427299 .
enlaces externos
- SPMF incluye implementaciones de código abierto de GSP, PrefixSpan, SPADE, SPAM y muchas otras.