Algoritmo Apriori

El objetivo en todo algoritmo de búsqueda de reglas de asociación es encontrar todas las reglas que satisfacen con la condición de confidencia y soporte mínimos dada por el usuario, esto es necesario por cuanto sino es así la búsqueda se haría exhaustiva, encontrándose al final una explosión en el número de reglas generadas.

Cuando se desea realizar la búsqueda en grandes bases de datos como sucede en Minería de Datos, se debe tratar de minimizar la cantidad de tiempo que se emplea en acceder las mismas , por cuanto estas operaciones de acceso a disco son por lo general las más lentas del proceso.

Un algoritmo como APriori satisface estos requerimientos y de hecho se ha convertido en referencia obligada en esta área, el mismo consta de dos pasos:
1. Encontrar todos los conjuntos frecuentes de ítems, es decir todos aquellos subconjuntos de I que cumplen con la condición s >= smin.
2. Usar los conjuntos frecuentes de ítems obtenidos para generar reglas que cumplan con la condición c >= cmin.

La idea del algoritmo se basa en que si un conjunto de ítems cumple con la condición de soporte mínimo, entonces todo subconjunto de este también la cumplirá, en realidad se usa el contrarrecíproco, cuando se obtiene un conjunto de ítems se chequea si todos los subconjuntos de este medidos en la iteración anterior cumplían con la condición de mínimo soporte, si se encuentra alguno que no la cumple se puede concluir, "a priori", que dicho conjunto no la cumplirá y por tanto no es necesario medirlo, esto evita mucha medición innecesaria, recuérdese que se quiere minimizar el tiempo total de acceso a la base de datos.

La secuencia que sigue el algoritmo apriori es, por lo general:

xxxxxxxxxxPara el conjunto de Itemsets
xxxxx xxxxxxxxxxSi s del itemset >=smin
xxxxxxxxxxxxxxxxxxxxAgregar al conjunto de Itemset Frecuentes.
xxxxxxxxxxxxxxxxxxxxxxxxxSi c del Itemset Frecuente >=cmin
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxCrea Regla con Itemset Frecuente

Este proceso se realiza n iteraciones, mientras se puedan crear conjuntos de Itemsets.