Algoritmo Apriori
- Propuesto por
- Agrawal, R. & Srikant, R.
- Año
- 1994
- Tipo
- Frequent itemset and association rule mining algorithm
- Familia
- Machine learning
Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés
¿Qué hace?
El algoritmo Apriori, introducido por Agrawal y Srikant en 1994, es el método fundamental para descubrir conjuntos de ítems frecuentes y reglas de asociación en bases de datos transaccionales.
Utiliza una búsqueda de amplitud, nivel por nivel, guiada por la propiedad anti-monótona del soporte para enumerar eficientemente todas las combinaciones de ítems que co-ocurren por encima de un umbral mínimo establecido por el usuario, y luego extrae reglas interpretables de tipo "si-entonces" de esos patrones.
La intuición detrás del método
Considere una base de datos de recibos de supermercado. La idea clave de Apriori es la propiedad anti-monótona: si un par de productos rara vez se compran juntos, ningún conjunto más grande que contenga ese par puede ser frecuente. Esto permite al algoritmo podar el espacio de búsqueda exponencialmente grande de posibles combinaciones de ítems construyendo candidatos nivel por nivel —comenzando con ítems individuales, luego pares, luego tríos— y descartando cualquier candidato cuyos subconjuntos ya se sepa que son infrecuentes, incluso antes de contarlo en los datos.
Historia
Rakesh Agrawal y Ramakrishnan Srikant introdujeron el algoritmo Apriori en VLDB 1994, basándose en la formulación de Agrawal et al. de 1993 del problema de minería de reglas de asociación. El nombre refleja su idea clave: usar el conocimiento previo de conjuntos de (k) ítems frecuentes para podar candidatos en el nivel k+1. Se convirtió en el punto de referencia canónico contra el cual se miden todos los algoritmos posteriores de conjuntos de ítems frecuentes —incluyendo FP-Growth (2000) y Eclat— y sigue siendo un capítulo estándar en los libros de texto de minería de datos y aprendizaje automático.
Cuándo usarlo
Utilice Apriori cuando el objetivo sea descubrir patrones de co-ocurrencia o relaciones de "si-entonces" en datos transaccionales o de presencia binaria de ítems —análisis de la cesta de la compra, co-respaldo de ítems en encuestas, co-ocurrencia de diagnósticos médicos, o asociación de términos en texto. Es adecuado para conjuntos de datos de tamaño moderado donde la transparencia y la interpretabilidad de las reglas de salida son una prioridad. No utilice Apriori cuando la base de datos transaccional sea muy grande (millones de filas con catálogos de ítems amplios), ya que sus escaneos repetidos completos de la base de datos lo hacen lento en comparación con FP-Growth; en esos casos se prefiere FP-Growth. Tampoco es apropiado para datos numéricos continuos sin una discretización previa, y no modela direccionalidad o causalidad.
Limitaciones y consideraciones
- Los escaneos repetidos completos de la base de datos lo hacen lento en conjuntos de datos grandes — FP-Growth a menudo se prefiere a escala.
- Reducir el umbral de soporte puede producir un número exponencial de conjuntos de ítems y reglas candidatas, dificultando la interpretación.
- No captura el orden temporal, la direccionalidad o las relaciones causales entre los ítems.
- Los resultados son sensibles a la elección de los umbrales de soporte y confianza, que requieren conocimiento del dominio o ajuste sistemático.
Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.
Fortalezas
- Genera reglas de "si-entonces" completamente interpretables con soporte, confianza y lift cuantificados.
- La propiedad de poda anti-monótona hace que una búsqueda de otro modo exponencial sea tratable.
- No requiere etiquetado previo de los datos; es completamente no supervisado.
- Los parámetros de umbral (soporte, confianza) otorgan al analista control directo sobre la granularidad de las reglas.
- Las reglas de salida son accionables y pueden comunicarse a partes interesadas no técnicas sin conocimientos algorítmicos.
- Seminal, muy citado e implementado en prácticamente todas las bibliotecas importantes de minería de datos.
Aplicaciones
- Análisis de la cesta de la compra: descubrir qué productos se compran frecuentemente juntos para guiar la disposición de los estantes y las promociones.
- Informática médica: identificar síntomas, diagnósticos o prescripciones de medicamentos que co-ocurren en registros de pacientes.
- Minería de uso web: encontrar qué páginas o características los usuarios tienden a visitar o activar juntos.
- Análisis de encuestas y cuestionarios: detectar qué ítems o respuestas de escala se respaldan sistemáticamente de forma conjunta.
- Inicio de sistemas de recomendación: generar asociaciones de ítems candidatas antes de implementar filtrado colaborativo.
- Detección de fraude: identificar patrones de co-ocurrencia inusuales en registros de transacciones que se desvían de las cestas normales.
Cómo funciona
Cómo funciona
El analista elige dos umbrales antes de ejecutar el algoritmo: soporte mínimo (la fracción de transacciones que deben contener un conjunto de ítems dado para que se considere frecuente) y confianza mínima (la probabilidad condicional requerida para que se retenga una regla de "si-entonces"). Estos dos valores controlan el volumen y la especificidad de la salida y deben calibrarse mediante conocimiento del dominio o ejecuciones exploratorias.
El algoritmo realiza un escaneo completo de la base de datos de transacciones para contar la frecuencia con la que aparece cada ítem individual. Solo se conservan los ítems cuyo soporte cumple o supera el umbral de soporte mínimo; el resto se descarta. Este conjunto de ítems individuales frecuentes forma el primer nivel de candidatos.
Fórmula
\text{support}(X) = \frac{|\{t \in T : X \subseteq t\}|}{|T|}Los conjuntos de ítems frecuentes encontrados en el nivel k se unen por pares para formar conjuntos de ítems candidatos de tamaño k+1. Solo se unen pares que comparten los mismos k-1 primeros ítems, una regla que mantiene compacto el conjunto de candidatos. Un nuevo escaneo de la base de datos cuenta el soporte de cada candidato.
Antes de contar, cada candidato de tamaño k+1 se verifica contra todos sus subconjuntos de tamaño (k). Si algún subconjunto no fue frecuente en el nivel anterior, el candidato se poda inmediatamente sin leer los datos, explotando la propiedad anti-monótona para reducir el cálculo. Los supervivientes de este paso de poda forman el siguiente nivel de conjuntos de ítems frecuentes.
A partir de cada conjunto de ítems frecuentes de tamaño dos o más, se generan todas las reglas posibles de "si-entonces" particionando los ítems en un antecedente y un consecuente. Cada regla se evalúa en cuanto a confianza —la proporción de transacciones con el antecedente que también contienen el consecuente. Se descartan las reglas por debajo de la confianza mínima.
Fórmula
\text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)}Las reglas supervivientes se clasifican por lift (elevación), que compara la confianza observada con la frecuencia base del consecuente. Un lift superior a 1 indica que el antecedente y el consecuente co-ocurren más de lo esperado por azar; un lift cercano a 1 indica independencia; un lift inferior a 1 indica una asociación negativa. Las reglas con el mayor lift son los descubrimientos más accionables.
Fórmula
\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)}Errores comunes
- Establecer el soporte mínimo demasiado bajo y ahogarse en miles de reglas de baja calidad sin filtrar por lift.
- Interpretar una alta confianza como causalidad en lugar de co-ocurrencia — una regla con alta confianza pero lift cercano a 1 es trivial.
- Aplicar Apriori a características continuas sin discretizarlas primero, lo que infla el espacio de ítems y degrada los resultados.
- Informar reglas sin verificar si el tamaño de la muestra del conjunto de ítems es lo suficientemente grande como para confiar en las estimaciones de soporte.
- Omitir la eliminación de reglas no informativas (por ejemplo, reglas que involucran ítems comprados universalmente como una tarjeta de fidelidad de la tienda).
Preguntas frecuentes
¿Cuál es la diferencia entre soporte, confianza y lift?
El soporte es la fracción de todas las transacciones que contienen el conjunto de ítems — mide la prevalencia. La confianza es la probabilidad condicional de que aparezca el consecuente dado el antecedente — mide la fiabilidad de la regla. El lift es la relación entre la confianza observada y la frecuencia base del consecuente; un lift superior a 1 muestra una asociación positiva genuina en lugar de una coincidencia debida a la popularidad del ítem.
¿Cuándo debería elegir FP-Growth sobre Apriori?
FP-Growth comprime la base de datos en una estructura de árbol y la extrae sin escaneos completos repetidos, lo que lo hace sustancialmente más rápido en bases de datos grandes o cuando el soporte mínimo es bajo. Apriori es más fácil de entender e implementar y funciona bien en conjuntos de datos pequeños a moderados donde el tiempo de ejecución no es un cuello de botella.
¿Cómo elijo el soporte y la confianza mínimos?
No hay una regla universal. La práctica común es ejecutar el algoritmo en varios niveles de soporte, graficar el número de conjuntos de ítems frecuentes frente al soporte y elegir un valor en el codo de la curva. La confianza se establece luego en función de la pregunta de negocio o investigación — mayor confianza para reglas críticas para la misión, menor para el descubrimiento exploratorio. Siempre valide las reglas principales con la experiencia del dominio.
¿Puede Apriori manejar datos numéricos o continuos?
Apriori requiere datos binarios de presencia de ítems. Las variables continuas deben discretizarse en intervalos (por ejemplo, edad en bajo/medio/alto) antes de codificarlas como ítems. Una discretización deficiente puede distorsionar gravemente las reglas descubiertas, por lo que la estrategia de agrupamiento merece una cuidadosa consideración.
¿Implica Apriori causalidad entre los ítems?
No. Las reglas de asociación capturan co-ocurrencia, no causalidad o dirección. Una regla 'pan → mantequilla' significa que a menudo aparecen en la misma cesta; no significa que comprar pan cause que alguien compre mantequilla, ni que la relación sea asimétrica en ningún sentido causal.
Métodos relacionados
Fuentes
Agrawal, R. & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), 487–499.
Abrir referencia de la publicaciónCopiado.Apriori algorithm. Wikipedia.
Abrir referencia de la publicaciónCopiado.