Algoritmo Apriori

Apriori ^{[ 1 ]} es un algoritmo para la minería de conjuntos de elementos frecuentes y el aprendizaje de reglas de asociación sobre bases de datos relacionales . Procede identificando los elementos individuales frecuentes en la base de datos y extendiéndolos a conjuntos de elementos cada vez mayores, siempre que dichos conjuntos aparezcan con suficiente frecuencia en la base de datos. Los conjuntos de elementos frecuentes determinados por Apriori pueden utilizarse 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 cestas de 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 frecuencia de un sitio web o direcciones IP ^{[ 2 ]} ). Otros algoritmos están diseñados para encontrar reglas de asociación en datos sin transacciones ( Winepi y Minepi), o sin marcas de tiempo ( secuenciación de ADN ). Cada transacción se considera un conjunto de elementos (un itemset ). Dado un umbral${\displaystyle C}$, el algoritmo Apriori identifica los conjuntos de elementos que son subconjuntos de al menos${\displaystyle C}$transacciones en la base de datos.

Apriori utiliza un enfoque "de abajo hacia arriba", donde los subconjuntos frecuentes se extienden elemento por elemento (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 anchura y una estructura de árbol hash para contar eficientemente conjuntos de elementos candidatos. Genera conjuntos de elementos candidatos de longitud${\displaystyle k}$de conjuntos de elementos de longitud${\displaystyle k-1}$Luego, poda los candidatos que tienen un subpatrón poco frecuente. Según el lema de cierre descendente, el conjunto de candidatos contiene todos los subpatrones frecuentes.${\displaystyle k}$-conjuntos de elementos de longitud. Después de eso, escanea la base de datos de transacciones para determinar los conjuntos de elementos frecuentes entre los candidatos.

A continuación se muestra el pseudocódigo del algoritmo para una base de datos transaccional.${\displaystyle T}$y un umbral de soporte de${\displaystyle \varepsilon }$Se emplea la notación habitual de la teoría de conjuntos, aunque tenga en cuenta que${\displaystyle T}$es un multiconjunto .${\displaystyle C_{k}}$es el candidato establecido para el nivel${\displaystyle k}$En cada paso, se supone que el algoritmo genera los conjuntos candidatos a partir de los grandes conjuntos de elementos del nivel anterior, teniendo en cuenta el lema de cierre descendente.${\displaystyle \mathrm {count} [c]}$accede a un campo de la estructura de datos que representa el conjunto de candidatos${\displaystyle c}$, que inicialmente se asume que es cero. A continuación se omiten muchos detalles; por lo general, la parte más importante de la implementación es la estructura de datos utilizada para almacenar los conjuntos candidatos y contar sus frecuencias.

Apriori (T, ε) L 1 ← {conjuntos de elementos singleton grandes} k ← 2 mientras L k−1 no está vacío C k ← Generar_candidatos(L k−1 , k) para transacciones t en T D t ← {c en C k : c ⊆ t} para candidatos c en D t count[c] ← count[c] + 1 L k ← {c en C k : count[c] ≥ ε} k ← k + 1 devolver Unión(L k ) sobre todos los k Generar_candidatos (L, k) resultado ← empty_set() para todo p ∈ L, q ∈ L donde p y q difieren en exactamente un elemento c ← p ∪ q si u ∈ L para todo u ⊆ c donde |u| = k-1 resultado.add(c) devolver resultado

Apriori, si bien es históricamente significativo, adolece de varias ineficiencias o compromisos que han dado lugar a otros algoritmos. La generación de candidatos genera un gran número 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 anchura de la red de subconjuntos) encuentra cualquier subconjunto maximal S solo después de que todos${\displaystyle 2^{|S|}-1}$de sus subconjuntos propios.

El algoritmo escanea la base de datos demasiadas veces, lo que reduce el rendimiento general. Por ello, el algoritmo asume que la base de datos permanece permanentemente en la memoria.

Además, la complejidad temporal y espacial de este algoritmo es muy alta:${\displaystyle O\left(2^{|D|}\right)}$, por lo tanto exponencial, donde${\displaystyle |D|}$es el ancho horizontal (el número total de elementos) presentes en la base de datos.

Algoritmos posteriores como Max-Miner ^{[ 3 ]} intentan identificar los conjuntos máximos de elementos frecuentes sin enumerar sus subconjuntos y realizan "saltos" en el espacio de búsqueda en lugar de un enfoque puramente ascendente.

• ARtool , aplicación Java GPL para la minería de reglas de asociación con interfaz gráfica de usuario (GUI), que ofrece implementaciones de múltiples algoritmos para el descubrimiento de patrones frecuentes y la extracción de reglas de asociación (incluye Apriori).
• SPMF ofrece implementaciones de código abierto en Java del algoritmo Apriori y varias variantes como AprioriClose, UApriori, AprioriInverse, AprioriRare, MSApriori, AprioriTID y otros algoritmos más eficientes como FPGrowth y LCM.
• Christian Borgelt proporciona implementaciones en C para Apriori y muchos otros algoritmos de minería de patrones frecuentes (Eclat, FPGrowth, etc.). El código se distribuye como software libre bajo la licencia MIT .
• El paquete R arules contiene Apriori y Eclat, así como la infraestructura necesaria para representar, manipular y analizar datos y patrones de transacciones.
• Efficient-Apriori es un paquete de Python que incluye una implementación del algoritmo tal como se presenta en el artículo original.