5.Reglas de Asociación

Continuar

Las reglas de Asociación se utilizan para descubrir hechos que ocurren en común dentro de un determinado conjunto de datos. Existen diversos métodos para aprendizaje de reglas de asociación que permiten descubrir relaciones entre variables en grandes conjuntos de datos.

Definición:

Sea I el conjunto de ítems de una base de datos D.
Una Regla de Asociación (RA) es una implicación de la forma
X  => Y
donde

Soporte

Proporción de instancias que la regla predice correctamente.

El Soporte de una regla de asociación X ==> Y en una base de datos D está dado por la expresión

Confianza

 Cociente entre la cantidad de veces que la regla se cumple y la cantidad de veces que se puede aplicar.

La Confianza (confidence) de una regla de asociación X  => Y está dada por la siguiente expresión:

Análisis de la Canasta de Mercado

Este es un ejemplo clásico que explica claramente el concepto de Reglas de Asociación

La idea es obtener las Reglas de Asociación de los productos comprados por los clientes de un supermercado, los cuales se representan como transacciones Tj={I1, I2, …, Ik}

Análisis de la Canasta de Mercado

Este es un ejemplo clásico que explica claramente el concepto de Reglas de Asociación

La idea es obtener las Reglas de Asociación de los productos comprados por los clientes de un supermercado, los cuales se representan como transacciones Tj={I1, I2, …, Ik}

¿Cuál es el Soporte y la Confianza?

Este es un ejemplo clásico que explica claramente el concepto de Reglas de Asociación

Soporte = 3/4
Confianza = 3/3 = 1

Soporte = 3/4
Confianza = 3/3 = 1

¿Cuál es el Soporte y la Confianza para los siguientes ejemplos?

Soporte = ???
Confianza = ???

Deben establecerse los requisitos mínimos
Ej: soporte > 0.02

¿Qué es el Aprendizaje?

Es la extracción del conjunto de ítems que cumple con el soporte requerido y la Generación de las reglas a partir de estos ítems.

Algoritmo A priori

El algoritmo a priori es un algoritmo utilizado en BD, que permite encontrar de forma eficiente "conjuntos de ítems frecuentes", los cuales sirven para generar reglas de asociación. Comienza 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 usado mucho en el análisis de transacciones comerciales y en problemas de predicción.

Características

Las características principales de este algoritmo son:

Identifica los ítems que en forma individual que cumplen con el soporte mínimo.
Utiliza estos ítems para formar conjuntos de dos ítems que cumplen con la cobertura mínima.
Utiliza los ítems anteriores para formar grupos de a tres.
Sigue hasta que no encuentra un grupo mayor que cumpla con los requisitos.
Halla los itemsets frecuentes: conjuntos de ítems que tienen mínimo soporte
- Un subconjunto de un itemset frecuente debe ser también un itemset frecuente
  - Si {AB} es un itemset frecuente, luego {A} y {B} deberían ser itemsets frecuentes
- Iterativamente hallar los itemsets frecuentes con cardinalidad desde 1 a k (k-itemset)
Usa los itemsets frecuentes para generar reglas de asociación.

Algoritmo A priori con el problema de la Canasta de Mercado con soporte mínimo = 0.5

Si aplicamos el algoritmo Apriori para el problema de la Canasta de Mercado con soporte mínimo = 0.5 se realizan los siguientes pasos.

Luego de aplicar el algoritmo observamos que el itemset obtenido es el formado por {2 3 5} o sea formado por {leche huevos pan}

Una vez obtenido el conjunto de items frecuentes se forman las reglas y se analizan.  Por ejemplo:
 Pan  => Leche y huevos
Leche y huevos => Pan

Desventajas del algoritmo A priori

Recorre la BD varias veces ==> este es el proceso más costoso.
Genera conjuntos de ítems frecuentes de cardinalidad alta ==> dificulta la construcción de las reglas llevando a verificar sobre la BD muchas opciones.

Mejoras y Extensiones

Para mejorar la búsqueda de reglas de asociación se han propuesto variantes al algoritmo básico:

Tablas hash
Uso de una estructura tipo árbol. Por ejemplo Frequent Pattern Tree [Huan et al.2000]
Técnicas paralelización

Algoritmo FP-Growth

El algoritmo FPGrowth es el proceso de obtención de todos los patrones frecuentes de un conjunto de transacciones, mediante la generación del árbol FP que comprime las transacciones y el podado recursivo de éste.

Utiliza una estructura adicional con forma de árbol, denominada FP-Tree (frequent pattern tree), que simplifica el acceso a la información.

Recorre la estructura en forma recursiva determinando los conjuntos de ítems frecuentes con los que formará las reglas.