Taller de Base de Datos
Búsqueda de Reglas de Asociación
• Agrawal, Imielinski, Swami. “Mining Association Rules
Between Sets for items in Large Databases”, 1993.
• Agrawal, Srikant. “Fast Algorithms for Mining Association
Rules”, VLDB 1994.
Taller de Base de Datos
Motivación
Progreso en tecnologías de código de barra y POS, ha hecho
habitual la captura de “basket data” (conjunto de ítemes
adquiridos en una misma transacción).
Una transacción puede involucrar un punto o periodo de
tiempo.
El análisis de esta información puede mejorar decisiones
como: diseño de cupones, ubicación de mercadería, diseño de
ofertas, etc.
Taller de Base de Datos
Definiciones Básicas
Dado un conjunto de itemes
de transacciones
y un conjunto
Una regla de asociación es una expresión de la forma:
Ejemplo:
{Leche, Perfume}
{LapizLabial}
Taller de Base de Datos
Soporte y Confianza de una Regla
• Confianza: Conf(X
Y)=c en D ssi un c% de las
transacciones en D que contieen X también contienen Y.
• Soporte: Sop(X Y)=s en D ssi un s%de las transacciones
en D contienen a X U Y.
El soporte es una medida (muy simplista ) de la significancia
de la regla, y la confianza una medida de correlación.
Taller de Base de Datos
Reglas Interesantes
(Definición) Dados un soporte y confianza mínimos, minSop
y minConf, una regla X Y es interesante en un conjunto de
Problema: Encontrar las reglas interesantes en un conjunto
de transacciones D
Taller de Base de Datos
Limitaciones de Noción de “Reglas Interesantes”
Si la confianza de X Y es alto, podemos concluir que existe
un enlace causal entre X e Y.
Resp. No necesariamente, si X e Y son independientes
Pr(X|Y) = Pr(X), por lo que basta que Pr(X) sea alto para
que la confianza sea alta.
Ejemplo :{Leche, Perfume}
{LapizLabila}
Podría ser alto sólo porque se compra mucho LapizLabial
Un medida más precisa es la corrrelación, la cual
estudiaremos más adelante.
Taller de Base de Datos
Limitaciones de Noción de “Reglas Interesantes”
Otras Limitaciones:
No captura correlación negativa (ej. Tipos de clableado
eléctrico y ocurrencia de incendios).
No aseguran significancia estadística.
Más adelante discutiremos la extensión en:
S. Brin, R Motwan, C. Silverstein. “Beyond Markets:
Generalizing Association Rules to Correlations”.
Taller de Base de Datos
Itemsets
• Un itemset es un conjunto de itemes.
• Un k-itemset es un conjunto de k ítemes
• El soporte de un itemset A en D es el % de ocurrencias de
A en D.
• Un itemset es frecuente si su soporte es al menos minSop.
Taller de Base de Datos
Algoritmo Básico
INPUT: D, minSop, minConf
OUTPUT: Reglas interesantes en D
1.- Encontrar los itemset frecuentes.
2.- Generar las reglas de asociación interesabtes a partir de los
itemset frecuentes.
Taller de Base de Datos
Descubrimiento de Itemsets Frecuentes
• Crear un buffer (variable en memoria RAM) que guarde un
contador Count(A) para cada subconjunto de A en I.
• En una única lectura de D, poe cada transacción de T en D
y por cada subconjutno A’ de T hacer Count(A’)++.
Problema:
• Tamaño del buffer
Taller de Base de Datos
Problema:Complejidad de los Datos
Si contamos la frecuencia de cada itemser en una única
lectura de la base de datos necesitamos 2n contadores.
Para n=10000, a 1 Byte por cada contador, se requiere 10GB.
Taller de Base de Datos
Otra Estrategia
• Hacer varias lecturas de D.
• En la kava lectura, computar el soporte de los k-itensets.
Esto funciona, pero significa demasiadas lecturas de D.
Taller de Base de Datos
Problema: Volumen de los Datos
Escenario común:
Dos años de transacciones en una cadena de 50 supermercados. Cada
supermercado tiene un promedio de 10000 ventas diarias, donde cada
venta consiste de 20 ítemes en promedio.
Estructura de las transacciones:
Tamaño del archivo:
• Num. De Transacciones: 50x365x10000=365 millones.
• Num. De bytes por transacción: 4x21
• Total 3066 millones, aporx. 30GB
Usando un disco duro de 10MB/seg de velocidad , necesitamos 50
minutos para una sola lectura de la base de datos.
Taller de Base de Datos
Otros Ejemplos
• Wallmart maneja aprox. 20 millones de transacciones
diarias. Su base de datos de transacciones de ventas pesa
11 terabyte
• AT&T tiene más de 100 millones de clientes y almacena
más de 300 millones de llamados diarios.
Taller de Base de Datos
Algoritmo A priori
Muchos de los itemset van a tener un soporte pequeño.
Podemos evitar contar estos itemsets?
Principio de monotonicidad: Si S es un itemser frecuente,
entonces todo subconjutno de S es un itemset frecuente.
Ejemplo:
Si {x,y,z} es frecuente entonces {x,y} es frecuente.
Taller de Base de Datos
Algoritmo A priori
• Leer D y contar el soporte de los 1-itemset candidatos C1. Obtener los
1-itemset frecuentes L1.
• En la siguiente lectura de D, contar el soporte de los 2-itemset
Obtener los 2-itemset frecuentes L2
• En la siguiente lectura de D, contar el soporte de los 3-itemset
Obtener los 3-itemset frecuentes
• Seguir con cada k-itemset hasta que
(donde n es el número de itemset)
Taller de Base de Datos
Generación de los k-itemsets Candidatos
Objetivo: dado Lk-1 generar Ck
Dos pasos: (1) Generamos C (contiene superconjuntos de los ítemes en Lk1); (2) Podamos C para obtener Ck
Paso (1):
(Asumir que las transacciones y los itemes están ordenados lexicograficamente)
Generamos C usnado el operador join
Taller de Base de Datos
Generación de los k-itemsets Candidatos
Taller de Base de Datos
Algoritmo Apriori
Taller de Base de Datos
Variante
Contar ítemsets candidatos de múltiples tamaños en cada
lectura de D.
Además de contar sólo soporte de los ítemesets en Ck,
contar el soporte de Ck y C’k+1= aprioriGen(Ck).
Esto puede ser útil en las últimas iteraciones
¿Por qué? ¡Desventajas?
Taller de Base de Datos
Manejo de Buffer
En la primera línea del loop principal necesitamos guardar Lk1 y Ck en memoria RAM. En el loop interno guardamos en
RAM la tupla t y Ck.
• Si Lk-1 cabe en RAM pero Ck no: generamos Ck por partes,
por cada parte contamos el soporte y computamos el Lk
asociado.
• Si Lk-1 no cabe en RAM: se ordena Lk-1
lexicográficamente, luego se lee el bloque de Lk-1 con los
primeros k-2 elementos igulaes. Generamos su Ck y lo
contamos.
Repetimos hasta contar todo Ck.
Taller de Base de Datos
Generación de Reglas a Partir de Itemsets Frecuentes
Taller de Base de Datos
Generación de Reglas a Partir de Itemsets Frecuentes
Descargar

Taller de Base de Datos