PDF de programación - Reglas de asociación

Reglas de asociación
Reglas de asociación
© Fernando Berzal, [email protected]
© Fernando Berzal,
[email protected]

Reglas de asociación
Reglas de asociación

 Introducción
Introducción
Definiciones
 Definiciones
 Patrones frecuentes
Patrones frecuentes
 Reglas de asociación
Reglas de asociación
 Extracción de reglas de asociación
 Extracción de reglas de asociación
Extracción de reglas de asociación
Extracción de reglas de asociación
Identificación de patrones frecuentes: El algoritmo Apriori
 Identificación de patrones frecuentes: El algoritmo
Apriori
 Generación de reglas
Generación de reglas
Visualización de reglas de asociación
 Visualización de reglas de asociación
 Evaluación de reglas de asociación
Evaluación de reglas de asociación
Extensiones y variaciones
 Extensiones y variaciones
Atributos continuos
 Atributos continuos
 Reglas multinivel (
Reglas multinivel (a.k.a.
 Tipos de patrones: secuencias, estructuras…
Tipos de patrones: secuencias, estructuras…

a.k.a. generalizadas)
generalizadas)

11

Introducción
Introducción

Problema
Problema

Dado un conjunto de transacciones, encontrar reglas
Dado un conjunto de transacciones, encontrar reglas
que describen tendencias en los datos:
que describen tendencias en los datos:

Detectar cuándo la ocurrencia
Detectar cuándo la ocurrencia
de un artículo está asociada a la
de un artículo está asociada a la
ocurrencia de otros artículos en
ocurrencia de otros artículos en
la misma transacción.
la misma transacción.

Introducción
Introducción

““Market
Market--basket

basket analysis
analysis””

Transacciones
Transacciones

TID Artículos

1 Pan, leche, huevos
1 Pan, leche, huevos
2
3
4
5

Pan, pañales, cerveza
Leche, pañales, cerveza
Pan, leche, pañales, cerveza
Pan, leche, huevos, cerveza



Reglas de asociación
Reglas de asociación

pañales} } →→ {{cerveza
pañales} } →→ {{cerveza
{{pañales
{{pañales
cerveza}}
cerveza}}

{{leche
leche, pan}

, pan} →→ {{huevos
huevos}}

{{cerveza
cerveza, pan}
, pan}
→→ {{leche

leche, , huevos
huevos}}

¡OJO! →→→→→→→→ implica
¡OJO!

, no causalidad
causalidad..

implica coco--ocurrencia

ocurrencia, no

22

33

Introducción –– Aplicaciones (1)
Introducción
Aplicaciones (1)

““Product
Product placement
en las estanterías de un supermercado
en las estanterías de un supermercado

placement”: Colocación de productos
”: Colocación de productos

Objetivo
Objetivo

Identificar artículos que muchos clientes compran
Identificar artículos que muchos clientes compran
Identificar artículos que muchos clientes compran
Identificar artículos que muchos clientes compran
conjuntamente.
conjuntamente.

Solución
Solución

Procesar los datos de los terminales de punto de venta
Procesar los datos de los terminales de punto de venta
proporcionados por los escáneres de códigos de barras.
proporcionados por los escáneres de códigos de barras.

Ejemplo
Ejemplo

Si un cliente compra pañales, es muy probable que
Si un cliente compra pañales, es muy probable que
compre cerveza (¡no se sorprenda si ve las cervezas
compre cerveza (¡no se sorprenda si ve las cervezas
colocadas al lado de los pañales en el súper!)
colocadas al lado de los pañales en el súper!)

44

Introducción –– Aplicaciones (2)
Introducción
Aplicaciones (2)

Promociones y ofertas
Promociones y ofertas

Si se identifica una regla del tipo:
Si se identifica una regla del tipo: {impresora}

{impresora} →→ {tóner}
{tóner}

 Tóner en el consecuente
 Tóner en el consecuente
Tóner en el consecuente
Tóner en el consecuente
=> Puede determinarse cómo incrementar sus ventas.
=> Puede determinarse cómo incrementar sus ventas.
 Impresora en el antecedente
Impresora en el antecedente
=> Puede determinarse qué productos se verían
=> Puede determinarse qué productos se verían
afectados si dejamos de vender impresoras.
afectados si dejamos de vender impresoras.
Impresora en el antecedente y tóner en el consecuente
 Impresora en el antecedente y tóner en el consecuente
=> Puede utilizarse para ver qué productos deberían
=> Puede utilizarse para ver qué productos deberían
venderse con impresoras para promocionar las
venderse con impresoras para promocionar las
ventas de tóner.
ventas de tóner.

55

Introducción –– Aplicaciones (3)
Introducción
Aplicaciones (3)

Gestión de inventarios
Gestión de inventarios

Problema
Problema

Una empresa de reparación de electrodomésticos quiere
Una empresa de reparación de electrodomésticos quiere
anticipar la naturaleza de las reparaciones que tendrá
anticipar la naturaleza de las reparaciones que tendrá
anticipar la naturaleza de las reparaciones que tendrá
anticipar la naturaleza de las reparaciones que tendrá
que realizar y mantener a sus vehículos equipados con
que realizar y mantener a sus vehículos equipados con
las piezas que permitan reducir el números de visitas a
las piezas que permitan reducir el números de visitas a
casa de sus clientes.
casa de sus clientes.

Solución
Solución

los datos

Procesar
Procesar los
utilizadas en en reparaciones
utilizadas
patrones
patrones de co
de co--ocurrencia
ocurrencia..

datos sobre
reparaciones previas

sobre herramientas

herramientas y y piezas
piezas

previas parapara descubrir
descubrir

66

Definiciones
Definiciones

Itemset
 Itemset
Conjunto de uno o más
Conjunto de uno o más
items (artículos).
items
(artículos).

p.ej. {pan, leche}
p.ej. {pan, leche}

 KK--itemset
 KK--itemset
itemset
itemset

Itemset con k elementos.
Itemset
con k elementos.



TID Artículos

1 Pan, leche, huevos
2
3
4
5

Pan, pañales, cerveza
Leche, pañales, cerveza
Pan, leche, pañales, cerveza
Pan, leche, huevos, cerveza

 Soporte de un

Soporte de un itemset
Fracción de las transacciones que contienen el itemset
Fracción de las transacciones que contienen el
itemset..

itemset [[support
support]]

p.ej.
p.ej. supp

supp({({pan,leche

pan,leche}) = 3/5
}) = 3/5

 Itemset

Itemset frecuente
frecuente
Itemset
Itemset con soporte igual o superior a un umbral
con soporte igual o superior a un umbral
MinSupp).).
de soporte establecido por el usuario (
de soporte establecido por el usuario (MinSupp

77

Definiciones
Definiciones

Regla de asociación
Regla de asociación

Expresión de la forma
Expresión de la forma

X X →→→→→→→→ YY
X X →→→→→→→→ YY
donde
donde X e Y son

X e Y son itemsets
itemsets..

p.ejp.ej..

pañales} } →→→→→→→→ {{cerveza
cerveza}}
{{pañales
cerveza} } →→→→→→→→ {{pañales
{{cerveza
pañales}}
leche} } →→→→→→→→ {{huevos
{pan,
{pan, leche
huevos}}
{pan} →→→→→→→→ {{leche
{pan}
leche, , huevos
huevos}}

Definiciones
Definiciones

Medidas
Medidas de de evaluación

evaluación de de laslas reglas

reglas de de asociación
asociación

de la regla

Soporte de la
 Soporte
Fracción
Fracción de de laslas transacciones
como
como a Y;
como
como a Y;

a Y; estoesto eses, supp(XUY).
a Y; estoesto eses, supp(XUY).
, supp(XUY).
, supp(XUY).

regla: :
transacciones queque contiene

supp (X →→→→→→→→ Y)Y)
supp (X

contiene tanto

tanto a X a X

conf (X →→→→→→→→ Y)Y)
conf (X

 Confianza

regla: :

de la regla

Confianza de la
Fracción
Fracción de de laslas transacciones
también
también incluyen
quéqué frecuencia
incluyen
incluyen X.X.

incluyen a Y;
frecuencia aparece

aparece Y en

transacciones en en laslas queque aparece

aparece X X queque

a Y; estoesto eses, la

, la confianza

confianza midemide con
con
transacciones queque

Y en laslas transacciones

88

99

Definiciones
Definiciones

Medidas
Medidas de de evaluación

evaluación de de laslas reglas

reglas de de asociación
asociación

supp({
supp({pañales

pañales})}) = 3/5 = 0.6
= 3/5 = 0.6

TID Artículos

supp({
supp({cerveza

cerveza}) = 4/5 = 0.8
}) = 4/5 = 0.8

supp({
supp({cerveza

cerveza}}→→→→→→→→{{pañales

pañales}) })
pañales, , cerveza
cerveza})})

= supp({
= supp({pañales
= 3/5 = 0.6 = 60%
= 3/5 = 0.6 = 60%

1 Pan, leche, huevos
2
2
3
4
5

Pan, pañales, cerveza
Pan, pañales, cerveza
Leche, pañales, cerveza
Pan, leche, pañales, cerveza
Pan, leche, huevos, cerveza



conf ({
conf ({cerveza

cerveza}}→→→→→→→→{{pañales

pañales}) })
pañales, , cerveza

= supp({
= supp({pañales
cerveza}) / supp({
= (3/5) / (4/5) = 3/4 = 0.75 = 75%
= (3/5) / (4/5) = 3/4 = 0.75 = 75%

}) / supp({cerveza

cerveza})})

Extracción de reglas de asociación
Extracción de reglas de asociación
Formulación del problema
Formulación del problema

Dado un
Dado un conjunto
encontrar
encontrar todas

conjunto de de transacciones
todas laslas reglas

transacciones T, T,

reglas de de asociación

asociación……

 cuyocuyo soporte
 cuyocuyo soporte

soporte sea mayor o
soporte sea mayor o

sea mayor o igual
sea mayor o igual

igual queque un un umbral
igual queque un un umbral

umbral mínimo
umbral mínimo
mínimo
mínimo

soporte, , MinSupp

de de soporte
supp (XX →→→→→→→→ Y) Y) ≥ ≥ MinSupp
supp (
MinSupp

MinSupp: :

 cuya

sea mayor o igual

confianza sea mayor o

cuya confianza
mínimo
mínimo de de confianza
conf (XX →→→→→→→→ Y) Y) ≥ ≥ MinConf
conf (
MinConf

confianza, , MinConf
MinConf::

igual queque un un umbral
umbral

1010

1111

Extracción de reglas de asociación
Extracción de reglas de asociación
Formulación del problema
Formulación del problema

Solución por fuerza bruta
Solución por fuerza bruta
 Enumerar todas las reglas de asociación posibles.
Enumerar todas las reglas de asociación posibles.
Calcular el soporte y la confianza de cada regla.
 Calcular el soporte y la confianza de cada regla.
Eliminar las reglas que no superen los umbrales de
 Eliminar las reglas que no superen los umbrales de
 Eliminar las reglas que no superen los umbrales de
Eliminar las reglas que no superen los umbrales de
soporte y confianza (
soporte y confianza (MinSupp

MinSupp y y MinConf

MinConf).).

Computacionalmente prohibitivo…
Computacionalmente prohibitivo…

1212

Extracción de reglas de asociación
Extracción de reglas de asociación
Form