Apriori [1] es un algoritmo para la minería de conjuntos de elementos frecuentes y el aprendizaje de reglas de asociación en bases de datos relacionales . Procede mediante la identificación de los elementos individuales frecuentes en la base de datos y los extiende a conjuntos de elementos cada vez más grandes, siempre que esos conjuntos de elementos aparezcan con la 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 ve como 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", en el que los subconjuntos frecuentes se amplían elemento por elemento (un paso conocido como generación de candidatos ) y se prueban grupos de candidatos 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, elimina los candidatos que tienen un subpatrón poco frecuente. De acuerdo con el lema de cierre descendente, el conjunto de candidatos contiene todos los conjuntos de elementos de longitud frecuente. Después de eso, escanea la base de datos de transacciones para determinar los conjuntos de elementos frecuentes entre los candidatos.
El pseudocódigo para el algoritmo se proporciona a continuación para una base de datos de transacciones y un umbral de soporte de . Se emplea la notación habitual de teoría de conjuntos, aunque tenga en cuenta que es un multiconjunto . es el conjunto candidato para el nivel . En cada paso, se supone que el algoritmo genera los conjuntos candidatos a partir de los grandes conjuntos de elementos del nivel anterior, atendiendo al 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 {contar} [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 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 cuenta[c] ← cuenta[c] + 1 L k ← {c en C k : count[c] ≥ ε} k ← k + 1 retorno Unión(L k ) A priori_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) devolver resultadoConsidere 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 mediante una variedad de ejemplos.
Supongamos que un gran supermercado lleva un registro de los datos de ventas por unidad de stock (SKU) para cada artículo: cada artículo, como "mantequilla" o "pan", se identifica mediante un SKU numérico. El supermercado tiene una base de datos de transacciones donde cada transacción es un conjunto de SKU que se compraron juntos.
Deje que la base de datos de transacciones se componga de los siguientes conjuntos de elementos:
Utilizaremos Apriori para determinar los conjuntos de ítems frecuentes de esta base de datos. Para ello, diremos que un conjunto de ítems 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 ocurrencias, llamadas 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 que los elementos 1 y 2 aparecen juntos en tres de los conjuntos de elementos; por lo tanto, decimos que el elemento {1,2} tiene soporte de 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 manera, podemos podar conjuntos: ahora buscaremos triples frecuentes en la base de datos, pero ya podemos excluir todos los triples que contengan uno de estos dos pares:
En el ejemplo, no hay tripletes 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.
De esta forma, hemos determinado los conjuntos frecuentes de elementos en la base de datos e ilustrado 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, sufre 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 de abajo hacia arriba (esencialmente un recorrido en amplitud de la red de subconjuntos) encuentra cualquier subconjunto máximo S solo después de todos sus subconjuntos apropiados.
El algoritmo escanea la base de datos demasiadas veces, lo que reduce el rendimiento general. Debido a esto, el algoritmo supone que la base de datos está permanentemente en la memoria.
Además, tanto la complejidad temporal como la espacial de este algoritmo son muy altas: , 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 de abajo hacia arriba.
