Algoritmo de crecimiento de patrón frecuente (FP) en minería de datos

frequent pattern growth algorithm data mining

Tutorial detallado sobre el algoritmo de crecimiento de patrones frecuentes que representa la base de datos en forma de árbol FP. Incluye comparación FP Growth Vs Apriori:

Algoritmo a priori se explicó en detalle en nuestro tutorial anterior. En este tutorial, aprenderemos sobre el crecimiento de patrones frecuentes: FP Growth es un método para extraer conjuntos de elementos frecuentes.

mejor limpieza de disco para Windows 10

Como todos sabemos, Apriori es un algoritmo para la minería de patrones frecuente que se centra en generar conjuntos de elementos y descubrir el conjunto de elementos más frecuente. Reduce en gran medida el tamaño del conjunto de elementos en la base de datos, sin embargo, Apriori también tiene sus propias deficiencias.

Lea nuestro Serie completa de capacitación sobre minería de datos para un conocimiento completo del concepto.

Lo que vas a aprender:

• Deficiencias del algoritmo a priori
• Algoritmo de crecimiento de patrón frecuente
• Árbol FP
• Pasos frecuentes del algoritmo de patrones
• Ejemplo de algoritmo de crecimiento FP
• Ventajas del algoritmo de crecimiento FP
• Desventajas del algoritmo de crecimiento FP
• FP Growth vs Apriori
• BRILLAR
• Conclusión
• Lectura recomendada

Deficiencias del algoritmo a priori

1. El uso de Apriori necesita una generación de conjuntos de elementos candidatos. Estos conjuntos de elementos pueden ser grandes en número si el conjunto de elementos en la base de datos es enorme.
2. Apriori necesita múltiples escaneos de la base de datos para verificar el soporte de cada conjunto de elementos generado y esto conduce a altos costos.

Estas deficiencias se pueden superar utilizando el algoritmo de crecimiento FP.

Algoritmo de crecimiento de patrón frecuente

Este algoritmo es una mejora del método Apriori. Se genera un patrón frecuente sin necesidad de generación de candidatos. El algoritmo de crecimiento FP representa la base de datos en forma de un árbol llamado árbol de patrones frecuentes o árbol FP.

Esta estructura de árbol mantendrá la asociación entre los conjuntos de elementos. La base de datos está fragmentada utilizando un elemento frecuente. Esta parte fragmentada se denomina 'fragmento de patrón'. Se analizan los conjuntos de elementos de estos patrones fragmentados. Por tanto, con este método, la búsqueda de conjuntos de elementos frecuentes se reduce comparativamente.

Árbol FP

El árbol de patrones frecuentes es una estructura en forma de árbol que se crea con los conjuntos de elementos iniciales de la base de datos. El propósito del árbol FP es extraer el patrón más frecuente. Cada nodo del árbol FP representa un elemento del conjunto de elementos.

El nodo raíz representa nulo mientras que los nodos inferiores representan los conjuntos de elementos. La asociación de los nodos con los nodos inferiores que son los conjuntos de elementos con los otros conjuntos de elementos se mantienen mientras se forma el árbol.

Pasos frecuentes del algoritmo de patrones

El método de crecimiento de patrón frecuente nos permite encontrar el patrón frecuente sin generación de candidatos.

Veamos los pasos seguidos para extraer el patrón frecuente utilizando el algoritmo de crecimiento de patrón frecuente:

#1) El primer paso es escanear la base de datos para encontrar las ocurrencias de los conjuntos de elementos en la base de datos. Este paso es el mismo que el primer paso de Apriori. El recuento de conjuntos de 1 elemento en la base de datos se denomina recuento de soporte o frecuencia de conjunto de 1 elemento.

#2) El segundo paso es construir el árbol FP. Para ello, cree la raíz del árbol. La raíz está representada por nulo.

mejor convertidor de video a dvd gratis

#3) El siguiente paso es escanear la base de datos nuevamente y examinar las transacciones. Examine la primera transacción y descubra el conjunto de elementos que contiene. El conjunto de elementos con el recuento máximo se toma en la parte superior, el siguiente conjunto de elementos con el recuento más bajo y así sucesivamente. Significa que la rama del árbol se construye con conjuntos de elementos de transacción en orden descendente de recuento.

#4) Se examina la siguiente transacción de la base de datos. Los conjuntos de elementos se ordenan en orden descendente de recuento. Si algún conjunto de elementos de esta transacción ya está presente en otra rama (por ejemplo, en la primera transacción), esta rama de transacción compartiría un prefijo común con la raíz.

Esto significa que el conjunto de elementos común está vinculado al nuevo nodo de otro conjunto de elementos en esta transacción.

#5) Además, el recuento del conjunto de elementos se incrementa a medida que ocurre en las transacciones. Tanto el nodo común como el recuento de nodos nuevos aumentan en 1 a medida que se crean y vinculan de acuerdo con las transacciones.

#6) El siguiente paso es extraer el árbol FP creado. Para ello, se examina primero el nodo más bajo junto con los enlaces de los nodos más bajos. El nodo más bajo representa la longitud del patrón de frecuencia 1. A partir de aquí, recorra la ruta en el árbol FP. Esta ruta o rutas se denominan base de patrón condicional.

La base de patrón condicional es una subbase de datos que consta de rutas de prefijo en el árbol FP que ocurren con el nodo más bajo (sufijo).

#7) Construya un árbol FP condicional, que está formado por un recuento de conjuntos de elementos en la ruta. Los conjuntos de elementos que cumplen con el umbral de compatibilidad se consideran en el árbol FP condicional.

#8) Los patrones frecuentes se generan a partir del árbol FP condicional.

Ejemplo de algoritmo de crecimiento FP

Umbral de soporte = 50%, confianza = 60%

tabla 1

Solución:

Umbral de soporte = 50% => 0.5 * 6 = 3 => min_sup = 3

1. Recuento de cada artículo

Tabla 2

2. Ordene el conjunto de elementos en orden descendente.

Tabla 3

3. Construir árbol FP

mejor sitio de descarga de mp3 para android

1. Considerando nulo el nodo raíz.
2. El primer escaneo de la transacción T1: I1, I2, I3 contiene tres elementos {I1: 1}, {I2: 1}, {I3: 1}, donde I2 está vinculado como hijo a raíz, I1 está vinculado a I2 e I3 está vinculado a I1.
3. T2: I2, I3, I4 contiene I2, I3 e I4, donde I2 está vinculado a la raíz, I3 está vinculado a I2 e I4 está vinculado a I3. Pero esta rama compartiría el nodo I2 tan común como ya se usa en T1.
4. Incrementa el recuento de I2 en 1 e I3 está vinculado como niño a I2, I4 está vinculado como niño a I3. El recuento es {I2: 2}, {I3: 1}, {I4: 1}.
5. T3: I4, I5. Del mismo modo, una nueva rama con I5 está vinculada a I4 cuando se crea un hijo.
6. T4: I1, I2, I4. La secuencia será I2, I1 e I4. I2 ya está vinculado al nodo raíz, por lo tanto, se incrementará en 1. De manera similar, I1 se incrementará en 1 ya que ya está vinculado con I2 en T1, por lo tanto, {I2: 3}, {I1: 2}, {I4: 1}.
7. T5: I1, I2, I3, I5. La secuencia será I2, I1, I3 e I5. Así {I2: 4}, {I1: 3}, {I3: 2}, {I5: 1}.
8. T6: I1, I2, I3, I4. La secuencia será I2, I1, I3 e I4. Por tanto, {I2: 5}, {I1: 4}, {I3: 3}, {I4 1}.

4. La minería del árbol FP se resume a continuación:

1. El elemento de nodo más bajo I5 no se considera ya que no tiene un recuento mínimo de soporte, por lo que se elimina.
2. El siguiente nodo inferior es I4. I4 ocurre en 2 ramas, {I2, I1, I3:, I41}, {I2, I3, I4: 1}. Por lo tanto, considerando I4 como sufijo, las rutas de prefijo serán {I2, I1, I3: 1}, {I2, I3: 1}. Esto forma la base del patrón condicional.
3. La base del patrón condicional se considera una base de datos de transacciones, se construye un árbol FP. Este contendrá {I2: 2, I3: 2}, I1 no se considera ya que no cumple con el recuento mínimo de soporte.
4. Esta ruta generará todas las combinaciones de patrones frecuentes: {I2, I4: 2}, {I3, I4: 2}, {I2, I3, I4: 2}
5. Para I3, la ruta del prefijo sería: {I2, I1: 3}, {I2: 1}, esto generará un árbol FP de 2 nodos: {I2: 4, I1: 3} y se generarán patrones frecuentes: {I2 , I3: 4}, {I1: I3: 3}, {I2, I1, I3: 3}.
6. Para I1, la ruta del prefijo sería: {I2: 4} esto generará un árbol FP de un solo nodo: {I2: 4} y se generarán patrones frecuentes: {I2, I1: 4}.

El diagrama que se muestra a continuación muestra el árbol FP condicional asociado con el nodo condicional I3.

Ventajas del algoritmo de crecimiento FP

1. Este algoritmo necesita escanear la base de datos solo dos veces en comparación con Apriori, que escanea las transacciones para cada iteración.
2. El emparejamiento de elementos no se realiza en este algoritmo y esto lo hace más rápido.
3. La base de datos se almacena en una versión compacta en la memoria.
4. Es eficiente y escalable para minar patrones frecuentes tanto largos como cortos.

Desventajas del algoritmo de crecimiento FP

1. FP Tree es más engorroso y difícil de construir que Apriori.
2. Puede resultar caro.
3. Cuando la base de datos es grande, es posible que el algoritmo no quepa en la memoria compartida.

FP Growth vs Apriori

BRILLAR

El método anterior, Apriori y FP growth, extrae conjuntos de elementos frecuentes utilizando formato de datos horizontal. ECLAT es un método para extraer conjuntos de elementos frecuentes utilizando el formato de datos vertical. Transformará los datos en formato de datos horizontal en formato vertical.

Por ejemplo,Uso de crecimiento a priori y FP:

El ECLAT tendrá el formato de la tabla como:

Este método formará conjuntos de 2 elementos, 3 conjuntos de elementos, k conjuntos de elementos en el formato de datos vertical. Este proceso con k aumenta en 1 hasta que no se encuentran conjuntos de elementos candidatos. Algunas técnicas de optimización como diffset se utilizan junto con Apriori.

Este método tiene una ventaja sobre Apriori, ya que no requiere escanear la base de datos para encontrar el soporte de k + 1 conjuntos de elementos. Esto se debe a que el conjunto de transacciones llevará el recuento de ocurrencia de cada elemento en la transacción (soporte). El cuello de botella se produce cuando hay muchas transacciones que requieren una gran cantidad de memoria y tiempo computacional para cruzar los conjuntos.

Conclusión

El algoritmo Apriori se utiliza para las reglas de asociación minera. Funciona según el principio, 'los subconjuntos no vacíos de conjuntos de elementos frecuentes también deben ser frecuentes'. Forma candidatos de k-itemset a partir de (k-1) conjuntos de elementos y escanea la base de datos para encontrar los conjuntos de elementos frecuentes.

El algoritmo de crecimiento de patrones frecuentes es el método para encontrar patrones frecuentes sin generación de candidatos. Construye un árbol FP en lugar de utilizar la estrategia de generación y prueba de Apriori. El enfoque del algoritmo FP Growth es fragmentar las rutas de los elementos y extraer patrones frecuentes.

¡Esperamos que estos tutoriales de la serie Data Mining enriquezcan sus conocimientos sobre Data Mining!

PREV Tutorial | PRIMER Tutorial

Lectura recomendada

• Técnicas de minería de datos: algoritmos, métodos y principales herramientas de minería de datos
• Algoritmo a priori en minería de datos: implementación con ejemplos
• Ejemplos de algoritmos de árboles de decisión en minería de datos
• Ejemplos de minería de datos: aplicaciones más comunes de minería de datos 2021
• Minería de datos: procesos, técnicas y problemas principales en el análisis de datos
• Proceso de minería de datos: modelos, pasos del proceso y desafíos involucrados
• Patrón de preguntas de examen de certificación de pruebas de software CSTE
• Minería de datos Vs Aprendizaje automático Vs Inteligencia artificial Vs Aprendizaje profundo