Aprende Construcción de Árboles de Patrones Frecuentes con el Algoritmo FP-Growth | Minería de Reglas de Alto Rendimiento y Optimización de Escala

Desliza para mostrar el menú

Descripción general de FP-Growth

FP-Growth es un algoritmo de alto rendimiento diseñado para la minería de conjuntos de elementos frecuentes en grandes conjuntos de datos transaccionales. A diferencia de Apriori, que genera conjuntos candidatos y escanea repetidamente la base de datos, FP-Growth construye una estructura de datos compacta llamada FP-Tree (Árbol de Patrones Frecuentes) que permite extraer patrones frecuentes sin la generación de candidatos. Esto resulta en mejoras significativas en velocidad y uso de memoria, especialmente para conjuntos de datos con muchos patrones frecuentes.

Estructura del árbol

La estructura FP-Tree comprime el conjunto completo de transacciones en un formato de árbol de prefijos. Cada transacción se procesa ordenando sus elementos en orden descendente de frecuencia y luego insertándolos en el árbol, compartiendo prefijos comunes con rutas existentes. El nodo raíz es un nodo nulo que sirve como punto de entrada, y cada nodo en el árbol representa un elemento junto con un conteo de cuántas transacciones comparten ese prefijo hasta ese punto.

Enlace de nodos

Para facilitar la minería eficiente, todos los nodos que representan el mismo elemento están conectados mediante una lista enlazada, formando lo que se denomina una tabla de encabezado. Esto permite recorrer rápidamente todas las ocurrencias de un elemento particular en el árbol. Cada entrada en la tabla de encabezado apunta al primer nodo en el árbol para ese elemento, y cada nodo contiene un enlace al siguiente nodo con el mismo nombre de elemento.

Minería de patrones

La extracción de patrones frecuentes del FP-Tree implica dos pasos principales. Primero, se recorre el árbol de abajo hacia arriba, siguiendo los enlaces para cada elemento en la tabla de encabezado para recolectar todos los caminos de prefijo que conducen a ese elemento. Luego, se construyen FP-Trees condicionales para cada elemento y se minan recursivamente para extraer todos los conjuntos de elementos frecuentes. Este proceso recursivo continúa hasta que no se encuentren más patrones frecuentes.

Ejemplo: Construcción paso a paso de un FP-Tree

A continuación, se presenta la construcción exacta paso a paso utilizando los ejemplos de transacciones, asumiendo un Umbral Mínimo de Soporte de 2 (lo que significa que los artículos deben aparecer al menos dos veces para ser considerados).

Suponga que tiene las siguientes transacciones:

- Transaction 1: A, B, D;
- Transaction 2: B, C, E;
- Transaction 3: A, B, C, E;
- Transaction 4: B, E.

Paso 1: Escanear la base de datos y ordenar por frecuencia

Primero, el algoritmo lee todo el conjunto de datos para contar cuántas veces aparece cada artículo individual. Cualquier artículo que esté por debajo del umbral mínimo de soporte es descartado. Luego, se establece un orden global de clasificación de mayor a menor frecuencia.

Conteo global de artículos:

B aparece 4 veces

E aparece 3 veces

A aparece 2 veces

C aparece 2 veces

D aparece 1 vez (Descartado porque es menor que el Soporte Mínimo de 2)

Regla final de ordenamiento: Cada transacción ahora será filtrada y reorganizada para seguir estrictamente este orden descendente de frecuencia:

$\mathbf{B} \longrightarrow \mathbf{E} \longrightarrow \mathbf{A} \longrightarrow \mathbf{C}$

Paso 2: Reordenar cada transacción

Antes de insertar los artículos en el árbol, el algoritmo reescribe cada transacción. Elimina el artículo infrecuente (D) y reorganiza los artículos restantes para que coincidan con la nueva regla de ordenamiento global.

- Transaction 1: A, B, D se convierte en B, A
- Transaction 2: B, C, E se convierte en B, E, C
- Transaction 3: A, B, C, E se convierte en B, E, A, C
- Transaction 4: B, E se convierte en B, E

Paso 3: Insertar rutas en el FP-Tree

Todo FP-Tree comienza con un nodo raíz nulo como marcador de posición. Ahora insertamos nuestras transacciones reordenadas en el árbol una por una, incrementando los contadores cuando las rutas se superponen y ramificando cuando divergen.

Insertar Transacción 1 {B, A}: el árbol crea una nueva rama directamente desde la raíz.

Insertar Transacción 2 {B, E, C}: el algoritmo comienza en la raíz y verifica el primer artículo, B. Como B ya existe como hijo de la raíz, ¡la ruta se superpone! El algoritmo avanza a B e incrementa su contador a 2. El siguiente artículo es E. Como B aún no tiene un hijo llamado E, el árbol se divide aquí y crea una nueva sub-rama para E, seguida de C.

Insertar Transacción 3 {B, E, A, C}: comenzando desde la raíz, la ruta pasa por B (el contador se incrementa a 3), luego baja al nodo E existente (el contador se incrementa a 2). El siguiente artículo es A. Como E no tiene un hijo llamado A, el árbol crea una nueva división bajo E para (A:1) -> (C:1).

Insertar Transacción 4 {B, E}: el algoritmo sigue el camino prefijo más popular y B se incrementa a 4, E se incrementa a 3. La transacción termina aquí, por lo que no se agregan nuevos nodos.

(Null Root) | (B: 4) / \ (A: 1) (E: 3) / \ (C: 1) (A: 1) | (C: 1)


              12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
            
transactions = [
    ['A', 'B', 'D'],
    ['B', 'C', 'E'],
    ['A', 'B', 'C', 'E'],
    ['B', 'E']
]

# Step 1: Counting item frequency
from collections import defaultdict, Counter

item_counts = Counter()
for transaction in transactions:
    item_counts.update(transaction)

# Step 2: Removing infrequent items
min_support = 2
freq_items = {item for item, count in item_counts.items() if count >= min_support}

# Step 3: Sorting items in each transaction by frequency
def sort_transaction(transaction):
    return sorted([item for item in transaction if item in freq_items],
                  key=lambda item: (-item_counts[item], item))

sorted_transactions = [sort_transaction(t) for t in transactions]

# Step 4: Defining FP-Tree node class
class FPTreeNode:
    def __init__(self, item, count, parent):
        self.item = item
        self.count = count
        self.parent = parent
        self.children = {}
        self.link = None  # Node link for header table

# Step 5: Building the FP-Tree and header table
def build_fp_tree(transactions):
    root = FPTreeNode(None, 1, None)
    header_table = defaultdict(list)

    for transaction in transactions:
        current = root
        for item in transaction:
            if item not in current.children:
                current.children[item] = FPTreeNode(item, 1, current)
                header_table[item].append(current.children[item])
            else:
                current.children[item].count += 1
            current = current.children[item]
    # Linking nodes in header table
    for item, nodes in header_table.items():
        for i in range(len(nodes) - 1):
            nodes[i].link = nodes[i + 1]
    return root, header_table

fp_root, header_table = build_fp_tree(sorted_transactions)

# Step 6: Printing the FP-Tree
def print_tree(node, indent=0):
    if node.item is not None:
        print('  ' * indent + f"{node.item}:{node.count}")
    for child in node.children.values():
        print_tree(child, indent + 1)

print_tree(fp_root)

Este ejemplo de código muestra cómo construir un FP-Tree a partir de una lista de transacciones utilizando Python. A continuación se presenta una explicación detallada de cada paso:

Conteo de frecuencias de los artículos:
- El código utiliza la clase Counter del módulo collections para contar cuántas veces aparece cada artículo en todas las transacciones;
- Esto ayuda a identificar qué artículos son lo suficientemente frecuentes como para ser incluidos en el árbol.
Eliminación de artículos infrecuentes:
- Los artículos que no cumplen con el umbral mínimo de soporte son filtrados;
- El conjunto freq_items contiene solo los artículos que aparecen al menos tantas veces como lo especifica min_support.
Ordenar las transacciones por frecuencia:
- Cada transacción se filtra para conservar solo los artículos frecuentes;
- Luego, los artículos se ordenan en orden descendente de su frecuencia global (y alfabéticamente para desempatar);
- El ordenamiento maximiza el aprovechamiento de prefijos en el FP-Tree, haciendo el árbol más compacto.
Definición de la clase de nodo del FP-Tree:
- La clase FPTreeNode representa cada nodo en el árbol;
- Cada nodo almacena el nombre del artículo, el contador, un puntero a su nodo padre, un diccionario de sus hijos y un enlace al siguiente nodo con el mismo nombre de artículo (para el recorrido de la tabla de encabezados).
Construcción del FP-Tree y la tabla de encabezados:
- La función build_fp_tree crea el árbol insertando cada transacción ordenada;
- Comenzando desde la raíz, para cada artículo en una transacción, la función verifica si existe un nodo hijo; si no, crea uno y lo agrega a la tabla de encabezados;
- Si el nodo ya existe, su contador se incrementa;
- Después de construir el árbol, el código enlaza todos los nodos con el mismo nombre de artículo usando el atributo link, lo que permite un recorrido rápido a través de la tabla de encabezados.
Impresión de la estructura del FP-Tree:
- La función print_tree muestra el árbol imprimiendo recursivamente cada nodo y su contador con sangría para visualizar la estructura del árbol;
- Esta salida ayuda a visualizar cómo las transacciones se comprimen en rutas compartidas dentro del FP-Tree.

1. ¿Cuál de las siguientes es una ventaja clave de FP-Growth sobre el algoritmo Apriori?

2. ¿Cuál es la estructura de un nodo de FP-Tree?

¿Todo estuvo claro?

¡Gracias por tus comentarios!

Sección 2. Capítulo 1

Pregunte a AI

Pregunte lo que quiera o pruebe una de las preguntas sugeridas para comenzar nuestra charla

Sección 2. Capítulo 1