Saltar al contenido
Volver a los resultados

FP-Growth (crecimiento de patrones frecuentes, Frequent Pattern Growth)

Propuesto por
Jiawei Han, Jian Pei & Yiwen Yin
Año
2000
Tipo
Frequent-itemset mining algorithm
Familia
Pattern mining

Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés

Tamaño de letra

¿Qué hace?

FP-Growth, introducido por Jiawei Han, Jian Pei y Yiwen Yin en 2000, extrae conjuntos de ítems frecuentes de datos transaccionales sin generar conjuntos candidatos, el costoso paso que ralentiza el algoritmo clásico Apriori.

Comprime la base de datos en un árbol de patrones frecuentes (FP-tree) en dos lecturas, y luego genera patrones frecuentes recursivamente a partir de esa estructura, lo que lo hace drásticamente más rápido que Apriori en conjuntos de datos grandes y densos.

La intuición detrás del método

Apriori encuentra conjuntos de ítems frecuentes generando y probando repetidamente combinaciones candidatas — un proceso costoso y que requiere muchas lecturas que explota en datos densos. FP-Growth toma una ruta diferente: exprime toda la base de datos transaccional en un árbol compacto donde los prefijos compartidos se almacenan una vez, por lo que los patrones comunes se superponen y comprimen. Luego, en lugar de generar candidatos, lee patrones frecuentes directamente del árbol siguiendo los caminos que conducen a cada ítem y explorando recursivamente árboles 'condicionales' más pequeños. Dos pasadas sobre los datos y una estructura de datos inteligente reemplazan las múltiples pasadas de Apriori y la explosión combinatoria de candidatos.

Historia

Han, Pei y Yin presentaron FP-Growth en SIGMOD 2000 como una alternativa sin generación de candidatos a Apriori, con un tratamiento ampliado en su artículo de 2004 en Data Mining and Knowledge Discovery. La idea del árbol de patrones frecuentes — comprimir transacciones en una estructura de prefijo compartida y minarla recursivamente — se convirtió en una técnica fundamental en la minería de patrones, junto con Apriori (basado en candidatos) y ECLAT (formato vertical). Sigue siendo un algoritmo estándar y de alto rendimiento para extraer conjuntos de ítems en bibliotecas de minería de datos.

Cuándo usarlo

Utilice FP-Growth para extraer conjuntos de ítems frecuentes (y, posteriormente, reglas de asociación) de datos transaccionales — análisis de la cesta de la compra, minería de uso web y flujos de clics, recomendación y coocurrencia en bioinformática — especialmente en conjuntos de datos grandes o densos donde la generación de candidatos de Apriori es demasiado lenta. Solo necesita dos lecturas de base de datos y típicamente supera a Apriori. Sus costos: el FP-tree debe caber en memoria (una limitación para datos muy grandes o extremadamente dispersos, donde el árbol comprime mal), la recursión puede ser intrincada de implementar, y como toda minería basada en soporte, es sensible al umbral de soporte mínimo (un valor demasiado bajo hace explotar el número de resultados y uno demasiado alto omite patrones). ECLAT (intersección vertical de conjuntos de identificadores de transacción, tidsets) es una alternativa; para las reglas en sí, combínelo con la generación de reglas de asociación.

Limitaciones y consideraciones

  • El FP-tree debe caber en memoria; los conjuntos de datos muy grandes pueden no hacerlo.
  • En datos dispersos el árbol comprime mal, erosionando la ventaja.
  • La construcción recursiva de árboles condicionales es comparativamente compleja de implementar.
  • Sensible al umbral de soporte mínimo, como toda minería de conjuntos de ítems frecuentes.

Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.

Fortalezas

  • Sin generación de candidatos — mucho más rápido que Apriori en datos grandes/densos.
  • Solo dos lecturas de base de datos, independientemente de la longitud del patrón.
  • El FP-tree comprime la estructura compartida, ahorrando memoria y tiempo en datos densos.
  • Escala a patrones frecuentes largos que desbordan a los métodos basados en candidatos.

Aplicaciones

  • Análisis de la cesta de la compra y minería de asociaciones en el comercio minorista.
  • Minería de patrones de uso web y flujos de clics.
  • Recomendación a través de ítems que coocurren frecuentemente.
  • Coocurrencia y descubrimiento de motivos en bioinformática.
  • Cualquier tarea de conjuntos de ítems frecuentes a gran escala donde Apriori sea demasiado lento.

Cómo funciona

Cómo funciona

1

Una primera lectura de la base de datos cuenta el soporte de cada ítem y descarta aquellos por debajo del umbral de soporte mínimo. Los ítems frecuentes que permanecen se ordenan por frecuencia descendente — este orden permite que las transacciones compartan prefijos de árbol y mantiene el FP-tree compacto.

Fórmula
\text{scan DB: keep items with support} \ge \text{minsup, sort by frequency}
2

Una segunda lectura inserta cada transacción (sus ítems frecuentes, en el orden establecido) en el FP-tree, incrementando los recuentos en los caminos de prefijo compartidos y añadiendo nuevas ramas según sea necesario. Una tabla de encabezado enlaza todas las ocurrencias de cada ítem, por lo que el árbol representa de forma compacta la estructura frecuente de toda la base de datos.

Fórmula
\text{second scan: insert each transaction's frequent items into the FP-tree}
3

Para cada ítem frecuente (procesado de menor a mayor frecuencia), el algoritmo recopila su base de patrones condicionales — el conjunto de caminos de prefijo en el árbol que coocurren con ese ítem, cada uno ponderado por su recuento. Esto captura el contexto en el que el ítem aparece frecuentemente.

Fórmula
\text{for each item: collect its conditional pattern base (prefix paths)}
4

A partir de cada base de patrones condicionales se construye y mina recursivamente un FP-tree condicional más pequeño, generando conjuntos de ítems más largos al añadir el ítem a los patrones encontrados en su árbol condicional. La recursión termina en árboles de un solo camino, cuyas combinaciones de conjuntos de ítems se enumeran directamente — produciendo todos los conjuntos de ítems frecuentes sin generación de candidatos.

Fórmula
\text{build conditional FP-trees recursively to grow frequent patterns}

Errores comunes

  • Establecer el soporte mínimo demasiado bajo, produciendo una explosión de conjuntos de ítems.
  • Asumir que siempre supera a Apriori — en datos pequeños o dispersos la ganancia es modesta.
  • Olvidar que los conjuntos de ítems frecuentes no son reglas; la generación de reglas es un paso separado.
  • Pasar por alto los límites de memoria cuando el FP-tree no puede mantenerse en RAM.

Preguntas frecuentes

¿Cómo es FP-Growth más rápido que Apriori?

Apriori genera y prueba repetidamente conjuntos de ítems candidatos, leyendo la base de datos muchas veces. FP-Growth evita por completo la generación de candidatos: comprime los datos en un FP-tree en dos lecturas y extrae patrones recursivamente de él. Esto elimina la explosión combinatoria de candidatos, proporcionando grandes mejoras de velocidad en datos densos.

¿Qué es el FP-tree?

Un árbol de prefijos comprimido de los ítems frecuentes de la base de datos. Las transacciones que comparten un prefijo comparten un camino, con recuentos de nodos que registran el soporte, y una tabla de encabezado enlaza las ocurrencias de cada ítem. Almacena la estructura frecuente del conjunto de datos de forma compacta para que los patrones puedan leerse sin volver a leer los datos.

¿Cómo se relaciona FP-Growth con ECLAT y las reglas de asociación?

FP-Growth, ECLAT y Apriori encuentran conjuntos de ítems frecuentes; ECLAT utiliza un enfoque de intersección vertical de conjuntos de identificadores de transacción (tidsets) en lugar de un árbol. Encontrar conjuntos de ítems frecuentes es solo la primera etapa — las reglas de asociación (con confianza/elevación) se generan a partir de esos conjuntos de ítems en un paso separado.

Métodos relacionados

Fuentes

  1. Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1–12.

    Abrir referencia DOI
    Copiado.
  2. Han, J., Pei, J., Yin, Y., & Mao, R. (2004). Mining frequent patterns without candidate generation: a frequent-pattern tree approach. Data Mining and Knowledge Discovery, 8(1), 53–87.

    Abrir referencia DOI
    Copiado.