UNIVERSIDAD LAICA ELOY ALFARO DE MANABÍ

FACULTAD DE CIENCIAS INFORMÁTICAS

INGENIERÍA EN SISTEMAS

NOVENO NIVEL “A”

TÉCNICAS DE SIMULACIÓN

TRABAJO AUTÓNOMO #1

Algoritmo Apriori

ESTUDIANTE:
MERO ESPINAL ALEXANDER JOEL

CATEDRÁTICO:
ING. FABRICIO RIVADENEIRA

MANTA – MANABÍ – ECUADOR

2018-2019
 Introducción

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.

El algoritmo a priori fue propuesto en 1994 por 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.
 Desarrollo

Apriori es un algoritmo de aprendizaje de reglas de asociación muy simple y

popular que permite identificar las posibles correlaciones o interdependencias entre
distintas acciones o sucesos, lo que posibilita reconocer cómo la ocurrencia de un suceso
o acción puede inducir o generar la aparición de otros. Las reglas de asociación son una
manera de expresar patrones de datos de una base de datos. Estos patrones pueden servir
para conocer el comportamiento general del problema que genera la base de datos, y de
esta manera, disponer de información que pueda asistir en la toma de decisiones. Una
regla de asociación es una proposición probabilística sobre la ocurrencia de ciertos
estados en una base de datos. A diferencia de las reglas de clasificación, en la parte
derecha de las reglas de asociación puede aparecer cualquier atributo, y además puede
aparecer más de un atributo.

Para evaluar la calidad de una regla de asociación, se suelen emplear dos medidas:
soporte (o cobertura) y confianza (o precisión). El soporte de una regla se define como el
número de instancias que la regla predice correctamente. Por otra parte, la confianza mide
el porcentaje de veces que la regla se cumple cuando se puede aplicar, es decir, cuando
se cumple su antecedente.

soporte( A → B) = P(A ∩ B) (1)

confianza( A → B) = P(B | A) = P(A ∩ B) (2)

P(A)

El funcionamiento del algoritmo Apriori se basa en la búsqueda de los conjuntos

de items que cumplen con determinado umbral de soporte. Para ello, en primer lugar se
construyen los conjuntos formados por sólo un item, que superan el soporte mínimo.
Posteriormente, estos conjuntos se utilizan para construir los conjuntos de dos items, y así
sucesivamente hasta que se llegue a un tamaño en el que no existan conjuntos de ítems
con el soporte requerido. Una vez que se han seleccionado los conjuntos de items que
cumplen con el soporte mínimo, el siguiente paso consiste en generar, a partir de estos
conjuntos, las reglas de asociación que tengan un nivel de confianza mínimo. Del
conjunto de reglas generadas, las que resultan más interesantes son aquellas que tienen su
valor de soporte más alto.
La versión del algoritmo Apriori que implementa la herramienta WEKA es ligeramente
distinta al explicado anteriormente. Así, el algoritmo no obtiene de una vez todos los
conjuntos de items frecuentes que cumplen con el valor de umbral, sino que va iterando
y cada vez se obtienen los de un tamaño determinado, y con estos va generando reglas.
Además, para mejorar la eficiencia del algoritmo en la búsqueda de los conjuntos de items
frecuentes, elimina los atributos que tengan valores desconocidos en todos los ejemplos.
Por otra parte, el algoritmo Apriori de Weka permite seleccionar las reglas atendiendo a
diferentes métricas no únicamente la confianza.

Reglas de Asociación.
En minería de datos y aprendizaje automático, las reglas de asociación se utilizan para
descubrir hechos que ocurren en común dentro de un determinado conjunto de datos. Se
han investigado ampliamente diversos métodos para aprendizaje de reglas de asociación
que han resultado ser muy interesantes para descubrir relaciones entre variables en
grandes conjuntos de datos.

Piatetsky-Shapiro describe el análisis y la presentación de reglas 'fuertes' descubiertas en

bases de datos utilizando diferentes medidas de interés. Basado en el concepto de regla
fuerte, Agrawal et al. presentaron un trabajo en el que indicaban las reglas de asociación
que descubrían las relaciones entre los datos recopilados a gran escala en los sistemas de
terminales de punto de venta de unos supermercados. Por ejemplo, la siguiente regla:

En general no es difícil extraer las reglas a partir de las bases de datos, el detalle
(y aquí esta el problema) es que es muy costoso computacionalmente, tanto que pudiese
ser imposible de generarlas para una base de datos con muchísimos productos, sin mas
detalle, imaginemos que tenemos una base de datos con solo 10 productos (tomemos en
cuenta que una departamental como walmart debe de tener miles en su inventario),
entonces para extraer las reglas debemos hacer combinaciones de estos productos, a decir,
para 10 productos tendremos 1024 posibles reglas (estas son las posibles combinaciones
entre 10 productos de diversos tamaños) ahora si tuviésemos 20 entonces seria 1,048,576
posibles combinaciones, y esto es el problema de los algoritmos con complejidad
exponencial.
La siguiente imagen muestra a mayor detalle lo que intento explicar para cinco productos
a decir :{a,b,c,d,e}

Es por ello que se usa la regla anti monotona para la poda, que nos dice en pocas
palabras: si un conjunto es infrecuente, entonces todos los conjuntos en donde este último
se encuentre tambien seran infrecuentes,es decir, si tenemos al conjunto {A,B} y este es
infrecuente, entonces {A,B,C} , {A,B,E}, {A,D,B,E} tambien seran infrecuentes por
contener a A y B en ellos. Entonces ignoraremos a todos estos, la imagen siguiente
muestra un ejemplo visual:
La forma de generar las reglas de asociación consta de dos pasos:

 Generación de combinaciones frecuentes: cuyo objetivo es encontrar aquellos

conjuntos que sean frecuentes en la base de datos. Para determinar la frecuencia
se establece cierto umbral.
 Generación de reglas: A partir de los conjuntos frecuentes no encargamos de
generar las reglas, igual se parte de un indice.

Ejemplo de a priori

El indice para la generación de combinaciones se llama soporte y el indice para la

generación de reglas se llama confidencia.

Bien ahora entendiendo esto pues manos a la obra, tomemos el siguiente ejemplo

Pan, leche, pañales

Pan, pañales, cerveza, huevos
Leche, pañales, cerveza, refresco, café
Pan,leche,pañales,cerveza
Pan,refresco,leche,pañales

Bien el primer paso es generar las combinaciones frecuentes, entonces, digamos que
queremos un soporte superior al 50%.

Entonces busquemos dichos items, primero se parte de lo individual, es decir, para cada
articulo se cuenta su frecuencia:

Cerveza 3
Pan 4
Refresco 2
Pañales 5
Leche 4
Huevos 1
Café 1

Para calcular el soporte, simplemente se utiliza la siguiente fórmula :

(Cantidad de repeticiones del producto) / (Cantidad de transacciones)

Para nuestro ejemplo tenemos 5 transacciones, entonces tenemos que para cerveza su
soporte es:
Soporte Cerveza = 3 / 5 = 0.6, es decir, 60% , bien calculando los demás productos
tendremos la siguiente información:

Cerveza 60.00%
Pan 80.00%
Refresco 40.00%
Pañales 100.00%
Leche 80.00%
Huevos 20.00%
Café 20.00%

Como queremos un soporte mayor al 50% entonces podemos eliminar a refresco,

huevos y café,

Bien ahora lo interesante, generemos combinaciones con los siguientes productos,

iremos iterando, primero combinaciones de dos y calcularemos su soporte, luego con
tres, cuatro etc.

Entonces para dos tenemos:

Conjuntos Frecuencia Soporte

Cerveza,Pan 2 40.00%
Cerveza,Pañales 3 60.00%
Cerveza,Leche 2 40.00%
Pan, Pañales 4 80.00%
Pan, Leche 3 60.00%
Pañales, Leche 4 80.00%

Entonces tenemos nuestros primeros conjuntos frecuentes que son (su soporte es
superior al 50%):

Cerveza,Pañales
Pan,Pañales
Pan, Leche
Pañales, Leche
Ahora, generaremos item de tres conjuntos, a partir de los conjuntos generados
anteriormente y tenemos

Cerveza, Pañales, Pan

Cerveza, Pañales, Leche
Pan,Pañales,leche
Pan,Leche,cerveza

Y ahora calculamos la frecuencia y el soporte

Conjuntos Frecuencia Soporte

Cerveza, Pañales, Pan 2 40.00%
Cerveza, Pañales, Leche 2 40.00%
Pan,Pañales,leche 3 60.00%
Pan,Leche,cerveza 1 20.00%

Bien ahora procederíamos a generar los items de cuatro a decir solo seria
Pan,Pañales,Leche Cerveza y como tiene un soporte del 20% entonces aquí terminamos
de generar nuestros conjuntos frecuentes y obtuvimos:

Pan,Pañales,leche
Cerveza,Pañales
Pan, Pañales
Pan, Leche
Pañales, Leche

Entonces a partir de estos conjuntos obtendremos las reglas de asociación, supongamos

que tambien queremos un indice superior al 50%

para calcular la confidencia se utiliza la siguiente formula: (Repetición de las

observaciones del conjunto) / (repeticiones de la regla)

tomemos el primer conjunto (Pan , Pañales, Leche)

las reglas posibles son:

Pan => Pañales, Leche

Pañales => Pan , Leche
Leche = > Pan,Pañales
Pan,Pañales => Leche
Pan,Leche => Pañales
Leche,Pañales => Pan

tomemos a Pan,Pañales => Leche y tenemos 3 / 4 que da una confianza del 75% en
donde 3 = (repeticiones de pan,pañales, leche) y 4 = (repeticiones de pan, pañales)

y procederemos con calcular todas las reglas y aquellas que pasen serán las que
tomaremos.

Limitaciones de apriori
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 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.

Conclusiones
 Se puede decir que a el algoritmo a priori está basado en reglas asociativas,
este algoritmo se encarga de crear subconjuntos a partir de las reglas, también
se puede decir que hay una regla en la que permite excluir ciertos subgrupos
de conjuntos, ya que si se encuentra una variable dentro de estas se eliminan.
 Podemos decir que el algoritmo a priori no tiene limes al crear subconjuntos
ya que dependiendo de los datos este mezcla y crea estos subconjuntos.

Bibliografía
http://www.rcim.sld.cu/revista_18/articulos_htm/mineriadatos.htm

http://www.rcim.sld.cu/revista_18/articulos_htm/mineriadatos.htm

http://dis.unal.edu.co/profesores/jgomez/courses/data_mining/Mineria.pdf

www.cenatav.co.cu/doc/RTecnicos/RT%20SerieGris_016web.pdf

http://ferminpitol.blogspot.com/2014/05/reglas-de-asociacion-algoritmo-apriori.html