Aprende Procesamiento de Flujos de Datos Transaccionales con el Algoritmo Apriori | Fundamentos de las Reglas de Asociación y Análisis Transaccional

Desliza para mostrar el menú

El algoritmo Apriori es una herramienta fundamental para descubrir conjuntos de artículos frecuentes en datos transaccionales, lo cual es esencial para el análisis de la cesta de mercado. En el núcleo de Apriori se encuentra el Principio de Apriori, también conocido como la propiedad de cierre descendente.

Definición

Principio de Apriori - Si un conjunto de artículos es frecuente, entonces todos sus subconjuntos también deben ser frecuentes.

Este concepto reduce drásticamente la cantidad de conjuntos de artículos que deben evaluarse, ya que cualquier conjunto que contenga un subconjunto infrecuente puede descartarse de inmediato.

La generación de candidatos es la fase de emparejamiento del algoritmo. En cada ronda, el algoritmo toma los conjuntos de artículos frecuentes ganadores de la ronda anterior y los combina para formar nuevos grupos más grandes llamados candidatos. Para hacer esto de manera eficiente, el algoritmo solo une conjuntos de artículos que son casi idénticos, compartiendo todos sus elementos excepto el último.

Cómo funciona: Si el algoritmo descubre que {Bread, Milk} y {Bread, Diapers} son ambos muy populares por sí solos, los combina para crear un nuevo candidato de tres artículos para la siguiente ronda: {Bread, Milk, Diapers}.

Inmediatamente después de generar nuevos candidatos, el algoritmo inicia la fase de Poda para eliminar combinaciones innecesarias antes de realizar cálculos pesados en la base de datos. Este paso se basa completamente en el Principio de Apriori, que establece que un conjunto grande de artículos solo puede ser frecuente si todas sus partes individuales más pequeñas también son frecuentes. Durante la poda, el algoritmo examina meticulosamente cada nuevo candidato y revisa sus subconjuntos más pequeños. Si incluso un solo subconjunto no superó el corte en la ronda anterior, el candidato completo se elimina al instante.

Cómo funciona: Imagina que se genera el candidato {Bread, Milk, Eggs}. El algoritmo revisa sus subcomponentes: {Bread, Milk}, {Bread, Eggs} y {Milk, Eggs}. Si tus registros históricos de transacciones muestran que {Milk, Eggs} es una combinación poco común que no pasó una ronda anterior, el algoritmo poda completamente {Bread, Milk, Eggs}. Esto evita desperdiciar recursos computacionales en una combinación que está matemáticamente garantizada a fallar.

Una vez que la lista de candidatos se ha reducido a los contendientes más viables, el algoritmo pasa a la Identificación de Conjuntos Frecuentes de Artículos. El sistema escanea las bases de datos de transacciones para contar exactamente cuántas veces estos grupos candidatos restantes aparecen juntos en compras reales. El recuento total de cada candidato se convierte en un porcentaje. Si este valor cumple o supera el Umbral Mínimo de Soporte predefinido, el candidato es oficialmente reconocido como un Conjunto Frecuente de Artículos.

Definición

Umbral mínimo de soporte es un valor de corte definido por el usuario que determina la frecuencia más baja que un conjunto de artículos debe tener para ser considerado significativo en el algoritmo Apriori. Al establecer este umbral, se filtran los conjuntos de artículos que aparecen con poca frecuencia en el conjunto de datos. Elegir un umbral alto dará como resultado menos conjuntos de artículos, más comunes, lo que puede llevar a perder combinaciones interesantes pero poco frecuentes. Si se establece demasiado bajo, puede abrumar con demasiados conjuntos de artículos, incluidos aquellos de escaso valor práctico. El umbral seleccionado impacta directamente en la profundidad y el enfoque del análisis, por lo que debe reflejar los objetivos y la escala de la exploración de datos.

Este ciclo de tres pasos se repite consecutivamente. Avanza desde artículos individuales a pares, luego a grupos de tres, y continúa expandiéndose hasta que se ejecuta una ronda en la que no se pueden encontrar nuevos conjuntos de artículos frecuentes, mapeando con éxito toda la red de comportamiento de compra del consumidor.

Para concretar estas ideas, considera un Ejemplo usando un conjunto de datos pequeño. Supón que tienes las siguientes transacciones:

Transaction 1: {Milk, Bread};
Transaction 2: {Milk, Diaper, Beer, Bread};
Transaction 3: {Milk, Diaper, Beer, Cola};
Transaction 4: {Diaper, Beer};
Transaction 5: {Milk, Diaper, Bread, Beer}.

El algoritmo primero identificaría todos los artículos individuales que aparecen con frecuencia, luego generaría pares candidatos a partir de ellos, eliminaría aquellos que contienen artículos poco frecuentes y continuaría este proceso para descubrir grupos frecuentes más grandes, como {Milk, Diaper, Beer}.


              1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
            
import pandas as pd
from itertools import combinations

# Example transaction dataset
transactions = [
    ['Milk', 'Bread'],
    ['Milk', 'Diaper', 'Beer', 'Bread'],
    ['Milk', 'Diaper', 'Beer', 'Cola'],
    ['Diaper', 'Beer'],
    ['Milk', 'Diaper', 'Bread', 'Beer']
]

# Convert transactions to a DataFrame of one-hot encoded items
all_items = sorted(set(item for transaction in transactions for item in transaction))
df = pd.DataFrame([{item: (item in transaction) for item in all_items} for transaction in transactions])

def apriori(df, min_support=0.6):

    def get_support(itemset):
        return (df[list(itemset)].all(axis=1).sum()) / len(df)

    # Step 1: Finding frequent 1-itemsets
    frequent_itemsets = []
    current_level = []
    for item in all_items:
        support = get_support([item])
        if support >= min_support:
            current_level.append(frozenset([item]))
            frequent_itemsets.append((frozenset([item]), support))

    k = 2
    while current_level:
        # Step 2: Candidate generation
        candidates = []
        level_list = list(current_level)
        for i in range(len(level_list)):
            for j in range(i+1, len(level_list)):
                union = level_list[i] | level_list[j]
                if len(union) == k and union not in candidates:
                    # Step 3: Pruning
                    subsets = list(combinations(union, k-1))
                    if all(frozenset(subset) in current_level for subset in subsets):
                        candidates.append(union)

        # Step 4: Support counting
        next_level = []
        for candidate in candidates:
            support = get_support(candidate)
            if support >= min_support:
                next_level.append(candidate)
                frequent_itemsets.append((candidate, support))

        current_level = next_level
        k += 1

    # Format output
    return [(set(itemset), round(support, 2)) for itemset, support in frequent_itemsets]

# Running Apriori and displaying frequent itemsets
frequent_itemsets = apriori(df, min_support=0.6)
for itemset, support in frequent_itemsets:
    print(f"Frequent Itemset: {itemset}, Support: {support}")

Este código en Python demuestra una implementación sencilla del algoritmo Apriori para identificar conjuntos de artículos frecuentes en datos transaccionales. Así es como se realiza cada paso:

Preparación de los datos

Las transacciones se representan como una lista de listas, donde cada sublista contiene los artículos comprados juntos.
Se identifican y ordenan todos los artículos únicos.
Se crea un DataFrame codificado en one-hot: cada fila representa una transacción y cada columna corresponde a un artículo, con True o False indicando presencia o ausencia.

Pasos del algoritmo Apriori

1. Identificación de conjuntos frecuentes de 1 artículo

El algoritmo calcula el soporte para cada artículo individual (la proporción de transacciones que contienen el artículo).
Si el soporte de un artículo cumple o supera el umbral de min_support (aquí, 0.6), se considera frecuente y se incluye en la primera lista de conjuntos frecuentes.

2. Generación de candidatos

Para conjuntos de longitud k (comenzando desde 2), el algoritmo genera nuevos conjuntos candidatos combinando conjuntos frecuentes de la ronda anterior que comparten todos los artículos menos uno.
Solo se consideran combinaciones únicas, asegurando que no haya duplicados.

3. Poda

Se revisan los subconjuntos de longitud k-1 de cada nuevo candidato.
Si algún subconjunto no está en la lista de conjuntos frecuentes de la iteración anterior, el candidato se elimina (se excluye), según el Principio de Apriori.

4. Conteo de soporte

Para cada candidato restante, el algoritmo cuenta cuántas transacciones contienen todos los artículos del candidato.
Se calcula el soporte y se compara con el umbral. Solo los candidatos que cumplen el umbral se mantienen como conjuntos frecuentes para la siguiente ronda.

5. Iteración

Los pasos 2–4 se repiten, aumentando el tamaño de los conjuntos en cada iteración, hasta que no se encuentren nuevos conjuntos frecuentes.

Salida

La lista final incluye todos los conjuntos frecuentes y sus valores de soporte.
El código imprime cada conjunto frecuente y su soporte, mostrando qué combinaciones de artículos aparecen comúnmente juntas en las transacciones.

1. ¿Cuál de las siguientes opciones describe mejor el paso de generación de candidatos en el algoritmo Apriori?

2. ¿Cuál es la razón principal para podar conjuntos candidatos durante el algoritmo Apriori?

¿Todo estuvo claro?

¡Gracias por tus comentarios!

Sección 1. Capítulo 4

Pregunte a AI

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

Sección 1. Capítulo 4