Saltar al contenido
Volver a los resultados

Minería de Reglas de Asociación (Apriori)

Propuesto por
Rakesh Agrawal & Ramakrishnan Srikant
Año
1994
Tipo
Unsupervised pattern discovery 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?

La Minería de Reglas de Asociación es una técnica de minería de datos no supervisada que descubre patrones de co-ocurrencia entre elementos en conjuntos de datos transaccionales.

Introducida formalmente por Agrawal, Imieliński y Swami en 1993, y refinada con el influyente algoritmo Apriori por Agrawal y Srikant en 1994, identifica reglas de la forma X ⇒ Y — lo que significa que las transacciones que contienen el conjunto de elementos X tienden a contener también el conjunto de elementos Y — cuantificadas por soporte, confianza y lift.

La intuición detrás del método

Imagine un registro de recibos de supermercado: si miles de clientes que compran pan y mantequilla también compran leche, ese patrón merece atención. La Minería de Reglas de Asociación funciona como un bibliotecario meticuloso que revisa cada recibo, cuenta con qué frecuencia aparecen juntas las combinaciones de artículos y resalta las combinaciones que superan una frecuencia mínima. Una vez encontradas las agrupaciones frecuentes, el algoritmo pregunta: dado que ya tiene estos artículos, ¿con qué fiabilidad predice esto el siguiente artículo? Esta lógica de dos pasadas, primero frecuencia y luego confianza, es el corazón de Apriori.

Historia

El artículo fundacional de Agrawal, Imieliński y Swami (1993) definió el problema de las reglas de asociación en el contexto de datos de transacciones de supermercado. El artículo de Agrawal y Srikant de 1994 en VLDB introdujo el algoritmo Apriori y su eficiente estrategia de poda, haciendo que la minería a gran escala fuera práctica. Trabajos posteriores produjeron FP-Growth (Han et al., 2000), que evita por completo la generación de candidatos, y ECLAT, que mina en formato de datos vertical, estableciendo una rica familia algorítmica ahora central en los planes de estudio de minería de datos.

Cuándo usarlo

La Minería de Reglas de Asociación se adapta a grandes conjuntos de datos transaccionales donde el objetivo es descubrir patrones de co-ocurrencia sin una variable objetivo predefinida. Asume que los elementos son binarios (presente/ausente) por transacción. Es apropiada para análisis de la cesta de la compra, sistemas de recomendación, análisis de flujos de clics web y descubrimiento de co-diagnósticos médicos. No es adecuada para datos continuos u ordinales a menos que se pre-discreticen, para conjuntos de datos con dimensionalidad muy alta (espacio candidato exponencial), o cuando se requiere inferencia asociativa en lugar de causal. Las alternativas incluyen FP-Growth para una enumeración más rápida de conjuntos de elementos frecuentes y minería de secuencias cuando el orden temporal importa.

Limitaciones y consideraciones

  • Espacio candidato exponencial: el número de reglas crece combinatoriamente con el número de elementos distintos.
  • El marco de soporte-confianza puede generar reglas engañosas cuando las tasas base de los elementos varían ampliamente (se requiere ajuste de lift).
  • El modelo binario de transacciones requiere la discretización de variables continuas, introduciendo pérdida de información.
  • Umbrales de soporte mínimo altos pasan por alto reglas raras pero valiosas; umbrales bajos generan miles de reglas triviales.

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

Fortalezas

  • Completamente no supervisada: no se necesitan datos etiquetados ni objetivo predefinido.
  • Salida interpretable: las reglas son declaraciones si-entonces legibles por humanos con soporte y confianza cuantificados.
  • Escalable mediante la poda de Apriori; la variante FP-Growth elimina por completo los escaneos repetidos de la base de datos.
  • Agnóstica al dominio: aplicada en comercio minorista, atención médica, análisis web y bioinformática.

Aplicaciones

  • Comercio minorista: colocación de productos y recomendación de venta cruzada a partir de registros de transacciones de punto de venta.
  • Atención médica: análisis de co-ocurrencia de diagnósticos, procedimientos o medicamentos en registros de salud electrónicos.
  • Análisis web: descubrimiento de patrones de clics para recomendación de páginas y optimización de navegación.
  • Bioinformática: identificación de conjuntos de genes co-expresados y motivos de interacción de proteínas.
  • Ciberseguridad: detección de eventos de red correlacionados que indican patrones de intrusión.

Cómo funciona

Cómo funciona

1

El algoritmo escanea la base de datos de transacciones D para contar con qué frecuencia aparece cada conjunto de elementos X. Un conjunto de elementos se declara frecuente — y se coloca en L_k — solo cuando su soporte (la fracción de transacciones que lo contienen) cumple o supera el umbral de soporte mínimo definido por el usuario σ_min. El proceso comienza con elementos individuales (k=1) y construye iterativamente conjuntos candidatos más grandes.

Fórmula
L_k = \{ X \subseteq I \mid |X| = k,\; \text{support}(X) = \frac{|\{t \in D : X \subseteq t\}|}{|D|} \geq \sigma_{\min} \}
2

La propiedad anti-monotónica del soporte establece que cualquier subconjunto de un conjunto de elementos frecuente debe ser él mismo frecuente. Apriori explota esto descartando cada conjunto candidato de k elementos cuyos subconjuntos de (k-1) elementos no estén todos en el conjunto frecuente verificado L_{k-1}. Esto reduce drásticamente el espacio de búsqueda, evitando costosos escaneos de la base de datos para conjuntos de elementos que no pueden ser frecuentes.

Fórmula
\forall X \in C_k,\; \forall Y \subset X,\; |Y| = k-1 : Y \notin L_{k-1} \Rightarrow X \notin L_k
3

A partir de cada conjunto de elementos frecuente X ∪ Y, el algoritmo genera reglas X ⇒ Y donde X e Y son subconjuntos disjuntos. Una regla se retiene solo cuando su confianza — la probabilidad condicional de Y dado X, calculada como soporte(X ∪ Y) / soporte(X) — cumple o supera el umbral de confianza mínimo γ_min. Este paso convierte la co-ocurrencia bruta en declaraciones predictivas direccionales.

Fórmula
X \Rightarrow Y \text{ where } X \cap Y = \emptyset,\quad \text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \gamma_{\min}
4

Las reglas retenidas se clasifican y filtran por lift, que mide cuánto más probable es que Y aparezca con X que por casualidad. Lift > 1 indica correlación positiva más allá de la independencia; lift = 1 indica independencia; lift < 1 indica una correlación negativa. Medidas adicionales de interés como la convicción y el leverage pueden refinar aún más el conjunto de reglas para su implementación práctica.

Fórmula
\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)} = \frac{\text{support}(X \cup Y)}{\text{support}(X) \cdot \text{support}(Y)}

Errores comunes

  • Establecer el soporte mínimo demasiado bajo inunda al analista con reglas espurias; la selección del umbral requiere conocimiento del dominio o validación cruzada.
  • Confundir asociación estadística con causalidad: un lift alto no implica que X cause Y.
  • Ignorar la distribución de frecuencia de los elementos: los elementos comunes dominan las reglas y desplazan las asociaciones significativas de elementos raros.
  • Tratar la confianza sola como métrica de calidad; una regla con alta confianza pero bajo lift puede no funcionar mejor que el azar.

Preguntas frecuentes

¿Cuál es la diferencia entre soporte, confianza y lift?

El soporte mide con qué frecuencia aparece un conjunto de elementos en el conjunto de datos en su conjunto. La confianza mide la probabilidad condicional del consecuente dado el antecedente. El lift normaliza la confianza por la frecuencia marginal del consecuente, revelando si la co-ocurrencia excede lo que se esperaría bajo independencia. Las tres métricas se necesitan juntas para una evaluación robusta de las reglas.

¿Cómo reduce el algoritmo Apriori el costo computacional?

Apriori explota la propiedad anti-monotónica: si un conjunto de elementos es infrecuente, todos sus superconjuntos también deben ser infrecuentes. Al descartar cualquier candidato cuyos subconjuntos no estén todos verificados como frecuentes, el algoritmo poda vastas porciones del espacio de búsqueda antes de contar, reduciendo drásticamente el número de pasadas por la base de datos requeridas en comparación con la enumeración por fuerza bruta.

¿Cuándo debería usar FP-Growth en lugar de Apriori?

FP-Growth se prefiere cuando el conjunto de datos es grande y el umbral de soporte mínimo es bajo, porque comprime la base de datos de transacciones en una estructura compacta de árbol FP y mina patrones directamente sin generar candidatos explícitos. Esto elimina escaneos repetidos de toda la base de datos, haciéndolo sustancialmente más rápido que Apriori en conjuntos de datos densos con muchos conjuntos de elementos frecuentes.

Métodos relacionados

Fuentes

  1. Agrawal, R., Imieliński, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. ACM SIGMOD, 207–216.

    Abrir referencia DOI
    Copiado.
  2. Agrawal, R., & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th VLDB Conference, 487–499.

    Abrir referencia de la publicación
    Copiado.