Apriori [1] es un algoritmo para la extracción frecuente de conjuntos de elementos y el aprendizaje de reglas de asociación en bases de datos relacionales . Procede identificando los elementos individuales frecuentes en la base de datos y extendiéndolos a conjuntos de elementos cada vez más grandes, siempre que esos conjuntos de elementos aparezcan con suficiente frecuencia en la base de datos. Los conjuntos de elementos frecuentes determinados por Apriori se pueden utilizar para determinar reglas de asociación que resaltan tendencias generales en la base de datos : esto tiene aplicaciones en dominios como el análisis de la cesta de la compra .
El algoritmo Apriori fue propuesto por Agrawal y Srikant en 1994. Apriori está diseñado para operar en bases de datos que contienen transacciones (por ejemplo, colecciones de artículos comprados por clientes, o detalles de la frecuentación de un sitio web o direcciones IP [2] ). Otros algoritmos están diseñados para encontrar reglas de asociación en datos que no tienen transacciones ( Winepi y Minepi) o que no tienen marcas de tiempo (secuenciación de ADN). Cada transacción se considera un conjunto de elementos (un conjunto de elementos ). Dado un umbral , el algoritmo Apriori identifica los conjuntos de elementos que son subconjuntos de al menos transacciones en la base de datos.
Apriori utiliza un enfoque "de abajo hacia arriba", donde los subconjuntos frecuentes se amplían un elemento a la vez (un paso conocido como generación de candidatos ) y los grupos de candidatos se prueban con los datos. El algoritmo finaliza cuando no se encuentran más extensiones exitosas.
Apriori utiliza una búsqueda en amplitud y una estructura de árbol Hash para contar conjuntos de elementos candidatos de manera eficiente. Genera conjuntos de elementos candidatos de longitud a partir de conjuntos de elementos de longitud . Luego poda los candidatos que tienen un subpatrón poco frecuente. Según el lema de cierre descendente, el conjunto candidato contiene todos los conjuntos de elementos de longitud frecuente. Después de eso, escanea la base de datos de transacciones para determinar conjuntos de artículos frecuentes entre los candidatos.
El pseudocódigo del algoritmo se proporciona a continuación para una base de datos de transacciones y un umbral de soporte de . Se emplea la notación teórica de conjuntos habitual, aunque tenga en cuenta que se trata de un conjunto múltiple . es el candidato establecido para el nivel . En cada paso, se supone que el algoritmo genera los conjuntos candidatos a partir de los conjuntos de elementos grandes del nivel anterior, teniendo en cuenta el lema de cierre descendente. accede a un campo de la estructura de datos que representa el conjunto candidato , que inicialmente se supone que es cero. A continuación se omiten muchos detalles; normalmente la parte más importante de la implementación es la estructura de datos utilizada para almacenar los conjuntos candidatos y contar sus frecuencias.
![{\displaystyle \mathrm {cuenta} [c]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/140f05e53551a4af31aac973f92f800c00de950b)
A priori (T, ε) L 1 ← {grande 1 - conjuntos de elementos} k ← 2 mientras que L k−1 no está vacío C k ← Apriori_gen(L k−1 , k) para transacciones t en T D t ← {c en C k : c ⊆ t} para candidatos c en D t contar[c] ← contar[c] + 1 L k ← {c en C k : contar[c] ≥ ε} k ← k + 1 Unión de retorno (L k ) Apriori_gen (L, k) resultado ← lista() para todo p ∈ L, q ∈ L donde p 1 = q 1 , p 2 = q 2 , ..., p k-2 = q k-2 y p k-1 < q k-1 c = p ∪ { q k-1 } si u ∈ L para todo u ⊆ c donde |u| = k-1 resultado.add(c) resultado de retornoConsidere la siguiente base de datos, donde cada fila es una transacción y cada celda es un elemento individual de la transacción:
Las reglas de asociación que se pueden determinar a partir de esta base de datos son las siguientes:
También podemos ilustrar esto a través de una variedad de ejemplos.
Supongamos que un gran supermercado rastrea los datos de ventas por unidad de mantenimiento de existencias (SKU) para cada artículo: cada artículo, como "mantequilla" o "pan", se identifica mediante un SKU numérico. El supermercado cuenta con una base de datos de transacciones donde cada transacción es un conjunto de SKU que se compraron en conjunto.
Deje que la base de datos de transacciones consta de los siguientes conjuntos de elementos:
Usaremos Apriori para determinar los conjuntos de elementos frecuentes de esta base de datos. Para ello diremos que un conjunto de elementos es frecuente si aparece en al menos 3 transacciones de la base de datos: el valor 3 es el umbral de soporte .
El primer paso de Apriori es contar el número de apariciones, llamado soporte, de cada elemento miembro por separado. Al escanear la base de datos por primera vez, obtenemos el siguiente resultado
Todos los conjuntos de elementos de tamaño 1 tienen un soporte de al menos 3, por lo que todos son frecuentes.
El siguiente paso es generar una lista de todos los pares de elementos frecuentes.
Por ejemplo, con respecto al par {1,2}: la primera tabla del Ejemplo 2 muestra los elementos 1 y 2 que aparecen juntos en tres de los conjuntos de elementos; por lo tanto, decimos que el elemento {1,2} admite tres.
Los pares {1,2}, {2,3}, {2,4} y {3,4} cumplen o superan el soporte mínimo de 3, por lo que son frecuentes. Los pares {1,3} y {1,4} no lo son. Ahora bien, como {1,3} y {1,4} no son frecuentes, cualquier conjunto mayor que contenga {1,3} o {1,4} no puede ser frecuente. De esta forma podemos podar conjuntos: ahora buscaremos tripletas frecuentes en la base de datos, pero ya podemos excluir todas las tripletas que contengan uno de estos dos pares:
en el ejemplo, no hay trillizos frecuentes. {2,3,4} está por debajo del umbral mínimo y los otros tripletes se excluyeron porque eran superconjuntos de pares que ya estaban por debajo del umbral.
Por lo tanto, determinamos los conjuntos frecuentes de elementos en la base de datos e ilustramos cómo algunos elementos no se contaron porque ya se sabía que uno de sus subconjuntos estaba por debajo del umbral.
Apriori, si bien es históricamente significativo, adolece de una serie de ineficiencias o compensaciones que han generado otros algoritmos. La generación de candidatos genera una gran cantidad de subconjuntos (el algoritmo intenta cargar el conjunto de candidatos, con tantos subconjuntos como sea posible antes de cada escaneo de la base de datos). La exploración de subconjuntos ascendente (esencialmente un recorrido en amplitud de la red de subconjuntos) encuentra cualquier subconjunto máximo S solo después de todos sus subconjuntos adecuados.
El algoritmo escanea la base de datos demasiadas veces, lo que reduce el rendimiento general. Debido a esto, el algoritmo asume que la base de datos está permanentemente en la memoria.
Además, la complejidad tanto temporal como espacial de este algoritmo es muy alta: , por lo tanto exponencial, donde es el ancho horizontal (el número total de elementos) presente en la base de datos.
Algoritmos posteriores como Max-Miner [3] intentan identificar los conjuntos de elementos más frecuentes sin enumerar sus subconjuntos y realizan "saltos" en el espacio de búsqueda en lugar de un enfoque puramente ascendente.
