Tareas_de_la_minería_de_datos,_reglas_de_asociación

Tareas de la minería de datos:
reglas de asociación y secuencias
CI-2352 Intr. a la minería de datos

Prof. Braulio José Solano Rojas
ECCI, UCR

La parábola de la cerveza y las
mantillas
●

La parábola de la cerveza y las mantillas.
●

«Hace algún tiempo, Wal-Mart decidió combinar los
datos de su sistema de tarjetas de fidelización con
el de su sistema de punto de ventas. El primero
proveyódatos demográficos acerca de los clientes,
el último brindó la información de dónde, cuándo y
qué compraron. Una vez combinados, los datos
fueron minados extensivamente y muchas
relaciones aparecieron. Algunas de estas fueron
obvias: las personas que compran gin
posiblemente también compran tonic. También
compran a menudo limones. Sin embargo, una
relación fue totalmente inesperada.»
2 de 67

Laparábola de la cerveza y las
mantillas
●

«Los viernes en la tarde, los jóvenes varones
estadounidenses que compran mantillas tienen
también una predisposición a comprar cerveza.
Nadie nunca predijo dicho resultado, de tal manera
que nadie se hubiera hecho la pregunta sobre el
caso en primer lugar. Esto es un excelente ejemplo
de la diferencia entre minería de datos y consulta
de datos.»

3 de 67Reglas de asociación

Tareas de la minería de datos:
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.
Basándose en el concepto de “reglas fuertes”,
Agrawal et al. presentaron las reglas de
asociación para descubrir regularidades en
transacciones registradas en grandes
repositorios de datos desistemas de punto de
ventas en supermercados.
5 de 67

Tareas de la minería de datos:
reglas de asociación
●

Ejemplo:

{ pan, jamón } ⇒ { queso }

6 de 67

Reglas de asociación: algoritmos
●

Existen algunos algoritmos bien conocidos
como Apriori, Eclat y FP-Growth, sin embargo,
proveen únicamente la mitad del trabajo dado
que son algoritmos para minar conjuntos de
elementos frecuentes. Otro pasonecesita luego
generar reglas a partir de los conjuntos de
elementos frecuentes encontrados en la base
de datos.

7 de 67

Sobre las reglas de asociación
●

●

●

El espacio de todas las reglas de asociación es
exponencial, O(2m), donde m es el número de
elementos en I.
La minería explota la escasez de los datos y
valores de apoyo mínimo y confianza mínima
altos.
Aún así, puede producir un grannúmero de
reglas, miles, decenas de miles, millones, ...
8 de 67

Reglas de asociación: algoritmo
apriori
●

●

●

Conjuntos de elementos (itemset) frecuentes:
los itemset que tienen un apoyo mínimo de los
datos (denotado por Li para el iésimo-itemset).
Prioridad Apriori: Cualquier subconjunto de
conjuntos de elementos frecuentes debe ser
frecuente.
Operación de unión: Para encontrar Lk, un
itemsetcandidato de tamaño k, se genera
uniendo a Lk-1 consigo mismo.
9 de 67

Algoritmo Apriori: resumido
●

Encontrar los itemset frecuentes: los conjuntos
de elementos que tienen apoyo mínimo
●

Un subconjunto de un itemset frecuente también
debe ser un itemset frecuente
–

●

●

i.e., si {AB} es un itemset frecuente, ambos {A} y {B}
deben ser itemset frecuentes

Iterativamente encontrar itemsetfrecuentes con
cardinalidad 1 a k (k-itemset)

Utilizar los itemset frecuentes para generar
reglas de asociación.
10 de 67

Algoritmo Apriori: pseudo-código
●

Unión: Ck es generado uniendo Lk-1 consigo mismo
Poda: Cualquier (k-1)-itemset que no es frecuente no puede ser un
subconjunto de un k-itemset frecuente

●

Pseudo-code:

●

Ck: Itemset candidato de tamaño k
Lk: Itemset frecuente de tamaño k
L1={elementos frecuentes};
para (k= 1; Lk!=∅; k++) haga
Ck+1= candidates generated from Lk;
para cada transacción t en database haga
incremente la cuenta de candidatos en Ck+1 que están en t
Lk+1= candidatos en Ck+1 con min_support
end
return ∪kLk;
11 de 67

Algoritmo Apriori: un ejemplo
TID

Lista de elementos

100

I1, I2, I5

101

I2, I4

102

I2, I3

103

I1, I2, I4

104

I1, I3

105

I2,...