Algoritmo GSP

El algoritmo GSP ( Algoritmo de Patrón Secuencial Generalizado ) es un algoritmo utilizado para la minería de secuencias . Los algoritmos para resolver problemas de minería de secuencias se basan principalmente en el algoritmo apriori (por niveles). Una forma de utilizar el paradigma por niveles es descubrir primero todos los elementos frecuentes de forma nivelada. Esto simplemente significa contar las ocurrencias de todos los elementos singleton en la base de datos. Luego, las transacciones se filtran eliminando los elementos no frecuentes. Al final de este paso, cada transacción consta solo de los elementos frecuentes que contenía originalmente. Esta base de datos modificada se convierte en la entrada del algoritmo GSP. Este proceso requiere una pasada por toda la base de datos .

El algoritmo GSP realiza múltiples pasadas sobre la base de datos. En la primera pasada, se cuentan todos los elementos individuales (secuencias de 1). A partir de los elementos frecuentes, se forma un conjunto de secuencias candidatas de 2, y se realiza otra pasada para identificar su frecuencia. Las secuencias frecuentes de 2 se utilizan para generar las secuencias candidatas de 3, y este proceso se repite hasta que no se encuentren más secuencias frecuentes. Hay dos pasos principales en el algoritmo.

• Generación de candidatos. Dado el conjunto de secuencias frecuentes (k-1) F _k-1 , los candidatos para la siguiente pasada se generan uniendo F(k-1) consigo mismo. Una fase de poda elimina cualquier secuencia, al menos una de cuyas subsecuencias no sea frecuente.
• Conteo de soporte. Normalmente, se emplea una búsqueda basada en árboles hash para un conteo de soporte eficiente. Finalmente, se eliminan las secuencias frecuentes no máximas.

 F 1 = el conjunto de secuencias frecuentes de 1 elementos k=2, hacer mientras F k-1 != Nulo; Generar conjuntos candidatos C k (conjunto de k-secuencias candidatas); Para todas las secuencias de entrada s en la base de datos D hacer Incrementar el contador de todos los a en C k si s admite un Fin de hacer Fk = {a ∈ C k tal que su frecuencia supera el umbral} k = k+1; Fin de hacer Resultado = El conjunto de todas las secuencias frecuentes es la unión de todas las F k .

El algoritmo anterior se parece al algoritmo Apriori . Sin embargo, una diferencia principal radica en la generación de conjuntos candidatos. Supongamos que:

A → B y A → C

son dos secuencias frecuentes de 2 elementos. Los elementos involucrados en estas secuencias son (A, B) y (A, C) respectivamente. La generación de candidatos al estilo Apriori habitual daría (A, B, C) como un conjunto de 3 elementos, pero en el presente contexto obtenemos las siguientes secuencias de 3 elementos como resultado de unir las secuencias de 2 elementos anteriores.

A → B → C, A → C → B y A → BC

La fase de generación de candidatos tiene esto en cuenta. El algoritmo GSP descubre secuencias frecuentes, permitiendo restricciones de tiempo como el intervalo máximo y mínimo entre los elementos de la secuencia. Además, admite el concepto de ventana deslizante, es decir, un intervalo de tiempo dentro del cual se observa que los elementos pertenecen al mismo evento, aunque provengan de eventos diferentes.

• Minería de secuencias

• R. Srikant y R. Agrawal. 1996. Minería de patrones secuenciales: generalizaciones y mejoras de rendimiento . En Actas de la 5.ª Conferencia Internacional sobre la Extensión de la Tecnología de Bases de Datos: avances en tecnología de bases de datos (EDBT '96), Peter MG Apers, Mokrane Bouzeghoub y Georges Gardarin (eds.). Springer-Verlag, Londres, Reino Unido, 3-17.
• Pujari, Arun K. (2001). Técnicas de minería de datos . Universities Press. pp. 256–260 . ISBN  81-7371-380-4.
• Zaki, MJ Aprendizaje automático (2001) 42: 31 .

• SPMF incluye una implementación de código abierto del algoritmo GSP, así como PrefixSpan , SPADE, SPAM, ClaSP, CloSpan y BIDE.