stringtranslate.com

Minería de patrones secuenciales

La minería de patrones secuenciales 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] [2] Por lo general, se supone 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 estructurada .

Existen 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 secuencias, la extracción de patrones que ocurren con frecuencia, la comparación de secuencias para determinar su similitud 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 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 opciones (exclusivas), bucles y construcciones de concurrencia además de la construcción de ordenación 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 típicamente muy larga. Ejemplos de un alfabeto pueden ser aquellos en el conjunto de caracteres ASCII utilizados en texto de lenguaje natural, bases de nucleótidos 'A', 'G', 'C' y 'T' en secuencias de ADN , o aminoácidos para 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 . 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 las estudiadas previamente. La comparación entre las cadenas se complica cuando ocurren inserciones , eliminaciones y mutaciones en una cadena.

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

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, 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 sube y Ericsson sube}, es probable que {Motorola suba y Samsung suba} en el plazo de 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, al analizar las transacciones de las cestas de la 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. (2007) presentan un estudio y una 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 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, las estanterías en las que se exhiben los productos son 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 una gestión adecuada de la asignación de espacio en las estanterías 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 las estanterías según el orden de los patrones de compra extraídos. [6]

Algoritmos

Los algoritmos comúnmente utilizados incluyen:

Véase también

Referencias

  1. ^ Mabroukeh, NR; Ezeife, CI (2010). "Una taxonomía de algoritmos de minería de patrones secuenciales". ACM Computing Surveys . 43 : 1–41. CiteSeerX  10.1.1.332.4745 . doi :10.1145/1824795.1824798. S2CID  207180619.
  2. ^ Bechini, A.; Bondielli, A.; Dell'Oglio, P.; Marcellonii, F. (2023). "De enfoques básicos a nuevos desafíos y aplicaciones en minería de patrones secuenciales". Computación Aplicada e Inteligencia . 3 (1): 44–78. doi : 10.3934/aci.2023004 .
  3. ^ 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.
  4. ^ 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 conocimiento . Springer. doi :10.1007/978-3-642-02788-8_9. ISBN. 978-3-642-02787-1.
  5. ^ 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 conocimiento . 15 (1): 55–86. doi : 10.1007/s10618-006-0059-1 .
  6. ^ George, A.; Binu, D. (2013). "Un enfoque para la colocación de productos en supermercados utilizando el algoritmo PrefixSpan". Revista de la Universidad Rey Saud-Ciencias de la Información y la Computación . 25 (1): 77–87. doi : 10.1016/j.jksuci.2012.07.001 .
  7. ^ 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: Minería de patrones de asociación entre residuos de aminoácidos preferidos en la vecindad de aminoácidos seleccionados para modificaciones postraduccionales". Proteómica . 8 (10): 1954–1958. doi :10.1002/pmic.200700657. PMID  18491291. S2CID  22362167.
  8. ^ 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. arXiv : 1811.06086 . doi : 10.1609/aaai.v33i01.33011495 . S2CID  53427299.
  9. ^ "Seq2Pat: biblioteca de generación de secuencias a patrones". GitHub . 9 de abril de 2022.

Enlaces externos