Minería de patrones secuenciales generalizados (GSP) en minería de datos

GSP es un algoritmo muy importante en la minería de datos. Se utiliza en la minería de secuencias de grandes bases de datos. Casi todos los algoritmos de minería de secuencias se basan básicamente en un algoritmo anterior. GSP utiliza un paradigma nivelado para encontrar todos los patrones de secuencia en los datos. Comienza con la búsqueda de los elementos frecuentes de tamaño uno y luego los pasa como entrada a la siguiente iteración del algoritmo GSP. La base de datos se pasa varias veces a este algoritmo. En cada iteración, GSP elimina todos los conjuntos de elementos no frecuentes. Esto se hace en base a una frecuencia umbral que se llama soporte. Solo se mantienen aquellos conjuntos de elementos cuya frecuencia es mayor que el recuento de soporte. Después del primer pase, GSP encuentra todas las secuencias frecuentes de longitud 1 que se denominan secuencias 1. Esto hace que la entrada al siguiente paso, sea el candidato para 2 secuencias. Al final de este pase, GSP genera todas las 2 secuencias frecuentes, lo que hace la entrada para las 3 secuencias candidatas. El algoritmo se llama recursivamente hasta que no se encuentran conjuntos de elementos más frecuentes. 

Minería básica de patrón secuencial (GSP):

• Secuencia: una secuencia se define formalmente como el conjunto ordenado de elementos {s1, s2, s3, …, sn}. Como sugiere el nombre, es la secuencia de elementos que ocurren juntos. Puede considerarse como una transacción o artículos comprados juntos en una cesta. 
• Subsecuencia: El subconjunto de la secuencia se llama subsecuencia. Supongamos que {a, b, g, q, y, e, c} es una secuencia. La subsecuencia de esto puede ser {a, b, c} o {y, e}. Observe que la subsecuencia no es necesariamente elementos consecutivos de la secuencia. A partir de las secuencias de las bases de datos se encuentran subsecuencias a partir de las cuales se encuentran al final los patrones de secuencia generalizados.
• Patrón de secuencia: una subsecuencia se denomina patrón cuando se encuentra en múltiples secuencias. El objetivo del algoritmo GSP es extraer los patrones de secuencia de la gran base de datos. La base de datos consta de las secuencias. Cuando una subsecuencia tiene una frecuencia igual a más del valor de “soporte”. Por ejemplo: el patrón <a, b> es un patrón de secuencia extraído de las secuencias {b, x, c, a}, {a, b, q} y {a, u, b}.

Métodos para la minería de patrones secuenciales:

• Enfoques basados ​​en a priori
  • SGP
  • PALA
• Enfoques basados ​​en patrones de crecimiento
  • FreeSpan
  • PrefijoSpan

Base de datos de secuencias: una base de datos que consta de elementos o eventos ordenados se denomina base de datos de secuencias. Ejemplo de una base de datos de secuencias:

S. No.	S.I.D.	secuencias
1.	100	<a(ab)(ac)d(cef)> o <a{ab}{ac}d{cef}>
2.	200	<(ad)c(bcd)(abe)>
3.	300	<(ef)(ab)(def)cb>
4.	400	<por ejemplo(adf)CBC>

Transacción: La secuencia consta de muchos elementos que se denominan transacciones.

<a(ab)(ac)d(cef)> es una secuencia mientras que (a), (ab), (ac), 

(d) y (cef) son los elementos de la secuencia. 

Estos elementos a veces se denominan transacciones.

Un elemento puede contener un conjunto de elementos. Los elementos dentro de un elemento están desordenados y los enumeramos alfabéticamente. 

Por ejemplo, (cef) es el elemento y consta de 3 elementos c, e y f. 

Dado que los tres elementos pertenecen al mismo elemento, su orden no importa. Pero preferimos ponerlos en orden alfabético por conveniencia. 

El orden de los elementos de la secuencia importa a diferencia del orden de los elementos en la misma transacción.

Secuencia de longitud k:  

El número de elementos involucrados en la secuencia se indica con K. Una secuencia de 2 elementos se denomina secuencia de 2 longitudes. Al encontrar la secuencia candidata de 2 longitudes, este término entra en uso. Un ejemplo de secuencia de 2 longitudes es: {ab}, {(ab)}, {bc} y {(bc)}.

• {bc} denota una secuencia de 2 longitudes donde b y c son dos transacciones diferentes. Esto también se puede escribir como {(b)(c)}
• {(bc)} denota una secuencia de 2 longitudes donde b y c son los elementos que pertenecen a la misma transacción, por lo tanto encerrados en el mismo paréntesis. Esto también se puede escribir como {(cb)}, porque el orden de los artículos en la misma transacción no importa.

Soporte en secuencia de longitud k:

Soporte significa la frecuencia. El número de ocurrencias de una secuencia de longitud k dada en la base de datos de secuencias se conoce como soporte. Mientras se encuentra el apoyo se cuida el orden.

Ilustración:

Supongamos que tenemos 2 secuencias en la base de datos.

s1: <a(bc)b(cd)>

s2: <b(ab)abc(de)>

Necesitamos encontrar el apoyo de {ab} y {(bc)}

Encontrar apoyo de {ab}:

Esto está presente en la primera secuencia. 

s1: <a(bc)b(cd)>

Dado que a y b pertenecen a elementos diferentes, su orden es importante.

En la segunda secuencia {ab} no se encuentra pero {ba} está presente. 

s2: <b(ab)abc(de)> Por lo tanto, no consideramos esto.

Por lo tanto, el soporte de {ab} es 1.

Encontrar apoyo de {bc}:

Dado que b y c están presentes en el mismo elemento, su orden no importa.

s1: <a(bc)b(cd)>, primera ocurrencia.

s2: <b(ab)abc(de)>, parece correcto, pero no lo es. b y c están presentes en diferentes elementos aquí. Entonces, no lo consideramos.

Por lo tanto, el soporte de {(bc)} es 1.

¿Cómo unir L1 y L1 para dar C2?

L1 es la secuencia final de 1 longitud después de la poda. Después de la poda, todas las entradas que quedan en el conjunto han soportado más que el umbral.

Caso 1: unir {ab} y {ac}

s1: {ab}, s2: {ac}

Después de eliminar a de s1 y c de s2.

s1’={b}, s2’={a}

s1′ y s2′ no son iguales, por lo que s1 y s2 no se pueden unir.

Caso 2: unir {ab} y {be}

s1: {ab}, s2: {ser}

Después de eliminar a de s1 y e de s2.

s1’={b}, s2’={b}

s1′ y s2′ son exactamente iguales, por lo que s1 y s2 se unirán.

s1 + s2 = {abe}

Caso 3: Une {(ab)} y {be}

s1: {(ab)}, s2: {ser}

Después de eliminar a de s1 y e de s2.

s1’={(b)}, s2’={(b)}

s1′ y s2′ son exactamente iguales, por lo que s1 y s2 se unirán.

s1 + s2 = {(ab)e}

s1 y s2 se unen de tal manera que los artículos pertenecen a elementos o transacciones correctos.

Fase de poda: mientras construimos Ck (conjunto de candidatos de longitud k), eliminamos una secuencia candidata que tiene una subsecuencia contigua (k-1) cuyo recuento de soporte es menor que el soporte mínimo (umbral). Además, elimine una secuencia candidata que tenga alguna subsecuencia sin soporte mínimo.

{abg} es una secuencia candidata de C3.

{abg} es una secuencia candidata de C3.

Para verificar si {abg} es el candidato adecuado o no, sin verificar su soporte, verificamos el soporte de sus subconjuntos.

Porque los subconjuntos de secuencias de 3 longitudes serán secuencias de 1 y 2 longitudes. Construimos el incremento de conjuntos candidatos como 1 longitud, 2 longitudes y así sucesivamente.

Los subconjuntos de {abg} son: {ab], {bg} y {ag}

Verifique el soporte de los tres subconjuntos. Si alguno de ellos tiene un soporte inferior al soporte mínimo, elimine la secuencia {abg} del conjunto C3; de lo contrario, consérvelo.

Desafíos en la minería de datos de patrones secuenciales generalizados

La base de datos se pasa muchas veces al algoritmo de forma recursiva. Los esfuerzos computacionales son más para extraer el patrón frecuente. Cuando la base de datos de secuencias es muy grande y los patrones que se extraerán son largos, GSP encuentra el problema para hacerlo de manera efectiva.