Algoritmo apriori

El algoritmo a priori es un algoritmo utilizado en minería de datos, sobre bases de datos transaccionales, que permite encontrar de forma eficiente "conjuntos de ítems frecuentes", los cuales sirven de base para generar reglas de asociación. 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.

Algoritmo

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. Dado un valor de un umbral $C$, el algoritmo a priori identifica todos los conjuntos de ítems que son subconjuntos de al menos $C$ transacciones en la base de datos. 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. Genera conjuntos de ítems candidatos de tamaño $k$ a partir de conjuntos de ítems de tamaño $k-1$, 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 $k$. Luego de este paso, escanea la base de datos para determinar los conjuntos de ítems frecuentes entre los candidatos.

A continuación se muestra el pseudocódigo para el algoritmo, dada una base de datos transaccional $T$ y un umbral de confianza $epsilon$. La notación usual de teoría de conjuntos es utilizada, y se define a $T$ como un multiconjunto. $C_{k}$ es el conjunto candidato en al nivel $k$. En cada paso se generan los conjuntos candidatos a partir del conjunto de ítems del nivel precedente, atendiendo al lema de clausura hacia debajo. $count[c]$ accede al campo de la estructura de datos que representa el conjunto candidato $c$, 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.

${\begin{aligned}&\mathrm {Apriori} (T,\epsilon )\\&\qquad L_{1}\gets \{\mathrm {large~1-itemsets} \}\\&\qquad k\gets 2\\&\qquad \mathrm {\textbf {while}} ~L_{k-1}\neq \ \emptyset \\&\qquad \qquad C_{k}\gets \{a\cup \{b\}\mid a\in L_{k-1}\land b\not \in a\}-\{c\mid \{s\mid s\subseteq c\land |s|=k-1\}\nsubseteq L_{k-1}\}\\&\qquad \qquad \mathrm {{\textbf {for}}~transactions} ~t\in T\\&\qquad \qquad \qquad C_{t}\gets \{c\mid c\in C_{k}\land c\subseteq t\}\\&\qquad \qquad \qquad \mathrm {{\textbf {for}}~candidates} ~c\in C_{t}\\&\qquad \qquad \qquad \qquad {\mathit {count}}[c]\gets {\mathit {count}}[c]+1\\&\qquad \qquad L_{k}\gets \{c\mid c\in C_{k}\land ~{\mathit {count}}[c]\geq \epsilon \}\\&\qquad \qquad k\gets k+1\\&\qquad \mathrm {\textbf {return}} ~\bigcup _{k}L_{k}\end{aligned}}$

Ejemplo

Asumamos una base de datos de transacciones donde cada transacción es un conjunto de productos que son comprados juntos. Por conveniencia, productos como "mantequilla" y "pan" son representados por números. Sea la base de datos representados por los siguientes conjuntos

Conjuntos

{C,U,L,O}

{C,U,O}

{C,U}

{U,L,O}

{U,L}

{L,O}

{U,O}

Usaremos Apriori para determinar los conjuntos de ítems frecuentes de la base de datos. 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

Item	Confianza
{C}	3
{U}	6
{L}	4
{O}	5

Todos los conjuntos de tamaño 1 tienen confianza de al menos 3, por lo que todos son frecuentes. El próximo paso es generar la lista de todos los pares de ítems frecuentes. Por ejemplo, considerando que el par {C,U} de la primera tabla del ejemplo, muestra que los ítems C y U aparecen juntos en tres de los conjuntos de ítems originales de la base de datos, definimos que {C,U} tiene una confianza de 3.

Item	Confianza
{C,U}	3
{C,L}	1
{C,O}	2
{U,L}	3
{U,O}	4
{L,O}	3

Los pares {C,U} , {U,L} , {U,O} y {L,O} tienen una confianza mayor que 3, por lo que son frecuentes; el resto se considera que no lo son. Como {C,L} y {C,O} 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

Item	Confianza
{U,L,O}	2

En este ejemplo, no hay triplos frecuentes, ya que {U,L,O} se encuentra por debajo del valor de confianza. Hemos determinado entonces los conjuntos frecuentes de ítems en la base de datos.

Limitaciones

El proceso de generación de candidatos en el algoritmo apriori genera un número grande de subconjuntos. Exploración de conjuntos de forma bottom-up encuentra cualquier subconjunto maximal solo después de todos los $2^{|S|}-1$ de sus subconjuntos propios. Algoritmos posteriores como Max-Miner trata de identificar el conjunto maximal de ítems frecuentes sin enumerar sus subconjuntos, ejecutan "saltos" en el espacio de búsqueda en vez de una estrategia puramente bottom-up.

Véase también

• Minería de datos
• Aprendizaje automático
• Reglas de asociación
• Weka (aprendizaje automático) (software)

Referencias

Bayardo Jr, Roberto J. (1998). «Efficiently mining long patterns from databases». ACM SIGMOD Record 27 (2). 

Rakesh Agrawal and Ramakrishnan Srikant Fast algorithms for mining association rules in large databases. Proceedings of the 20th International Conference on Very Large Data Bases, VLDB, pages 487-499, Santiago, Chile, September 1994.

Enlaces externos

• ARtool, GPL Java association rule mining application with GUI, offering implementations of multiple algorithms for discovery of frequent patterns and extraction of association rules (includes Apriori)
• ELKI includes Java implementations of Apriori, Eclat and FPGrowth.
• SPMF offers Java open-source implementations of Apriori and several variations such as AprioriClose, UApriori, AprioriInverse, AprioriRare, MSApriori, AprioriTID, and other more efficient algorithms such as FPGrowth and LCM.
• Christian Borgelt provides C implementations for Apriori and many other frequent pattern mining algorithms (Eclat, FPGrowth, etc.). The code is distributed as free software under the MIT license.
• The R package arules contains Apriori and Eclat and infrastructure for representing, manipulating and analyzing transaction data and patterns.
• Orange, an open-source data mining suite, contains widgets for enumerating itemsets and association rules based on Apriori algorithm.