Reglas de asociación, algoritmo apriori

Las reglas de asociación son una de las formas mas interesantes del data mining, esto claro a mi simple parecer, y ello debido al tipo de información que arrojan y a que su uso es directo, esto es, podemos generar reglas y sin mucho mas análisis entregarlas a los departamentos correspondientes para que realicen estrategias en base a las mismas.

Bien, pero ¿Qué es una regla de asociación?, bueno, sin tanta profundidad se trata de reglas que indican cierta relación entre sus conjuntos, sin que esto implique causalidad, por ejemplo, supongamos que tenemos una base de datos transaccional de alguna tienda departamental y obtenemos la siguiente regla

{pañales, leche, huevo } => {cerveza, cigarros}

la misma quiere decir que aquellos clientes que compraron pañales, leche y huevos también adquirieron cerveza y cigarros.

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 [1] 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[1] muestra un ejemplo visual:

Bien pero vayamos poco a poco.

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.

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.

Bien este es el proceso de generación de reglas con poda, comunmente conocido como algoritmo apriori. Espero les haya gustado.

[1]Addison Wesley,Introduction to data mining, Pang-Ning Tan