Los minoristas querían saber qué productos se compran juntos, pero el número de combinaciones posibles de artículos crecía exponencialmente con el número de SKU.
Apriori, publicado en 1994, explota una propiedad: cualquier superconjunto de un conjunto de elementos infrecuente debe ser a su vez infrecuente. Cuenta elementos individuales, conserva los frecuentes, los hace crecer en pares y repite, de modo que nunca cuenta un candidato cuyo padre ya falló.
El truco convierte una búsqueda que pronto se vuelve inmanejable en una que toca solo la pequeña frontera de conjuntos frecuentes. Transformó el análisis de la cesta de la compra en una consulta de base de datos práctica.
Si un conjunto es raro, todo superconjunto de él también lo es
La clausura descendente poda la búsqueda antes de que crezca, de modo que el tiempo de ejecución sigue a los conjuntos frecuentes, no a todos los conjuntos.
Un escaneo de la base de datos por nivel mantiene la memoria acotada a los conjuntos candidatos.
Proporciona conjuntos frecuentes exactos, no una heurística ni una aproximación por muestreo.
La misma poda se generaliza a la minería de secuencias y patrones más allá de las cestas.
Antes de buscar en un espacio enorme, busca una propiedad monótona que te permita descartar ramas enteras de una vez. Una regla que descarta una región reduce la búsqueda de exponencial a lineal.
Apriori se convirtió en el algoritmo canónico de reglas de asociación y en una lección estándar de minería de datos. Sembró el campo que impulsa el análisis de recomendación, surtido y venta cruzada, y más tarde fpgrowth y otros métodos que reducen sus escaneos.
CONSULTA LAS PRUEBAS
Las fuentes
- Fast Algorithms for Mining Association Rules in Large Databases VLDB 1994 · vldb.org
- What is the Apriori algorithm? IBM Think · ibm.com