Procede identificando los ítems individuales frecuentes en la base y extendiéndolos a conjuntos de mayor tamaño siempre y cuando esos conjuntos de datos aparezcan suficientemente seguidos en dicha base de datos.
Este algoritmo se ha aplicado grandemente en el análisis de transacciones comerciales y en problemas de predicción.
El algoritmo a priori fue propuesto en 1994 for Agrawal y Srikant.
Está diseñado para operar sobre bases de datos que contienen transacciones (por ejemplo, colecciones de artículos comprados por consumidores o detalles sobre la frecuentación a un sitio web).
Cada transacción es vista como un conjunto de ítems.
, el algoritmo a priori identifica todos los conjuntos de ítems que son subconjuntos de al menos
A priori utilizada un enfoque "bottom up", donde subconjuntos frecuentes son ampliados por un ítem a la vez (este paso se conoce como generación de candidatos) y grupos de candidatos son validados contra los datos.
El algoritmo termina cuando no se pueden encontrar más ampliaciones exitosas de los conjuntos previos.
Apriori utiliza una búsqueda en anchura y un Árbol de Merkle para almacenar el conjunto de ítems candidatos eficientemente.
, luego poda los candidatos que tienen un subpatrón infrecuente.
Según el lema de clausura hacia debajo, el conjunto candidato contiene todos los conjuntos frecuentes de tamaño
A continuación se muestra el pseudocódigo para el algoritmo, dada una base de datos transaccional
e p s i l o n
En cada paso se generan los conjuntos candidatos a partir del conjunto de ítems del nivel precedente, atendiendo al lema de clausura hacia debajo.
, que inicialmente se asume cero.
Muchos detalles son omitidos, usualmente la parte más importante es la implementación de la estructura de datos utilizada para almacenar los conjuntos candidatos y contar su frecuencia.
t r a n s a c t i o n s
Por conveniencia, productos como "mantequilla" y "pan" son representados por números.
Definamos que un ítem es frecuente si aparece en al menos 3 transacciones de la base da datos, por lo que 3 será el umbral de confianza.
El primer paso es contar el número de ocurrencias, llamado la confianza, de cada ítem separadamente, escaneando la base una primera vez.
Se obtienen los siguientes resultados Todos los conjuntos de tamaño 1 tienen confianza de al menos 3, por lo que todos son frecuentes.
Como {1,3} y {1,4} no son frecuentes, cualquier conjunto que contenga estos pares es considerado infrecuente.
De esta manera se pueden podar los conjuntos.
Analizando los conjuntos de ítems frecuentes de tamaño 3 se obtiene En este ejemplo, no hay triplos frecuentes, ya que {1,2,4} y {2,3,4} se encuentran por debajo del valor de confianza.