Reglas de Asociación

En minería de datos hay diferentes tipos de algoritmos que nos ayudan a la toma de decisiones.

Introducción

·      Algoritmos de clasificación, estos nos ayudan a predecir una o más variables discretas, basándose en otros atributos del conjunto de datos.

·      Algoritmos de regresión, que predicen una o más variables continuas, como las pérdidas o los beneficios, basándose en otros atributos del conjunto de datos.

·      Algoritmos de segmentación, que dividen los datos en grupos, o clústeres, de elementos que tienen propiedades similares.

·       Algoritmos de asociación, que buscan correlaciones entre diferentes atributos de un conjunto de datos. La aplicación más común de esta clase de algoritmo es la creación de reglas de asociación, que pueden utilizarse en un análisis de la cesta de compra. Un ejemplo serían el algoritmo que utiliza Amazon para establecer la relación de las preferencias de los libros de los usuarios del sitio, en base a búsquedas o compras realizadas.

·       Algoritmos de análisis de secuencias, que resumen secuencias o episodios frecuentes en los datos, como un flujo de rutas Web.

En este pequeño artículo tratara solamente de las reglas de asociación.

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.

Algoritmo 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 en su libro “Mining Association Rules Between Sets of Items in Large Databases”, presentó 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:

{Cebollas,Vegetables}=>{Carne}

Encontrada en los datos de ventas de un supermercado, indicaría que un consumidor que compra cebollas y vegetales a la vez, es probable que compre también carne. Esta información se puede utilizar como base para tomar decisiones sobre marketing como precios promocionales para ciertos productos o donde ubicar éstos dentro del supermercado. Además del ejemplo anterior aplicado al análisis de la cesta de la compra, hoy en día, las reglas de asociación también son de aplicación en otras muchas áreas como el Web Mining, la detección de intrusos o la bio-informática.

Un Ejemplo muy popular

Un caso muy famoso sobre reglas de asociación es el de la "cerveza y los pañales", basado en el comportamiento de los compradores en el supermercado. Se descubrió que muchos hombres acaban comprando pañales por encargo de sus esposas. En la cadena de supermercados Wal-Mart, donde se descubrió este hecho, se adoptó la medida de colocar la cerveza junto a los pañales. De esta manera consiguió aumentar la venta de cerveza.

Definiendo el problema

Según la definición original de Agrawal et al el problema de minería de reglas de asociación se define como:

I={i1, i2, i3,…,in} un conjunto de n atributos binarios llamados ítems.

D={t1, t2,t3,…tn} un conjunto de transacciones almacenadas en una base de datos.

Cada transacción en D tienen un Id (identificador) único y contiene un subconjunto de ítems de I. Una regla se define como una implicación de la forma:

X=>Y

Donde:

Los conjuntos de items X y Y se denominan respectivamente “antecedente” (o parte izquierda) y “Consecuente” (o parte derecha) de la regla.

Caso Práctico

Para ilustrar estos conceptos véase el siguiente ejemplo sobre ventas en un supermercado. El conjunto de ítems es:

 En la siguiente grafica se muestra una base de datos contiene los ítems, donde el código '1' se interpreta como que el producto (ítem) correspondiente está presenta en la transacción y el código '0' significa que dicho producto no está presente. Un ejemplo de regla para el supermercado podría ser:

Ejemplo: Base de datos con 4 items y 5 transacciones
ID	Leche	Pan	Mantequilla	Cerveza
1	1	1	0	0
2	0	1	1	0
3	0	0	0	1
4	1	1	1	0
5	0	1	0	0

Significaría que si el cliente compró 'leche' y 'pan' también compró 'mantequilla', es decir, según la especificación formal anterior se tendría que:

X={Leche, Pan}

Y={Mantequilla}

Reglas significativas, 'soporte' y 'confianza'

Nótese que el ejemplo anterior es muy pequeño, en la práctica, una regla necesita un soporte de varios cientos de registros (transacciones) antes de que ésta pueda considerarse significativa desde un punto de vista estadístico. A menudo las bases de datos contienen miles o incluso millones de registros.

Para seleccionar reglas interesantes del conjunto de todas las reglas posibles que se pueden derivar de un conjunto de datos se pueden utilizar restricciones sobre diversas medidas de "significancia" e "interés". Las restricciones más conocidas son los umbrales mínimos de "soporte" y "confianza".

El 'soporte' de un conjunto de ítems X en una base de datos  se define como la proporción de transacciones en la base de datos D que contiene dicho conjunto de ítems:

En el ejemplo anterior el conjunto {Leche, Pan} tiene un soporte de:

Es decir, el soporte es del 40% (2 de cada 5 transacciones).

La 'confianza' de una regla se define como:

Por ejemplo, para la regla:

{Leche, Pan}=>{Mantequilla}

La confianza sería:

Este cálculo significa que el 50% de las reglas de la base de datos que contienen 'leche' y 'pan' en el antecedente la también tienen 'mantequilla' en el consecuente; en otras palabras, que la regla:

{Leche, Pan}=>{Mantequilla} 

Es cierta en el 50% de los casos

La confianza puede interpretarse como un estimador de P(Y | X), la probabilidad de encontrar la parte derecha de una regla condicionada a que se encuentre también la parte izquierda.

Las reglas de asociación deben satisfacer las especificaciones del usuario en cuanto a umbrales mínimos de soporte y confianza. Para conseguir esto el proceso de generación de reglas de asociación se realiza en dos pasos. Primero se aplica el soporte mínimo para encontrar a los conjuntos de ítems más frecuentes en la base de datos. En segundo lugar se forman las reglas partiendo de estos conjuntos frecuentes de ítems y de la restricción de confianza mínima.

Encontrar todos los subconjuntos frecuentes de la base de datos es difícil ya que esto implica considerar todos los posibles subconjuntos de ítems (combinaciones de ítems). El conjunto de posibles conjuntos de ítems es el conjunto potencia de I y su tamaño es de 2ⁿ − 1 (excluyendo el conjunto vacío que no es válido como conjunto de ítems). Aunque el tamaño del conjunto potencia crece exponencialmente con el número de ítems n de I, es posible hacer una búsqueda eficiente utilizando la propiedad "downward-closure" del soporte (también llamada anti-monótona) que garantiza que para un conjunto de ítems frecuente, todos sus subconjuntos también son frecuentes, y del mismo modo, para un conjunto de ítems infrecuente, todos sus super-conjuntos deben ser infrecuentes.