Reglas de Asociación
Carlos Alonso GonzálezGrupo de Sistemas InteligentesDepartamento de Informática
Universidad de Valladolid
Reglas de asociación 2
Reglas Proposicionales:Reglas de Clasificación
Descripción de instancias: pares atributo/valor Reglas Si <antecedente>
Entonces <consecuente>
<antecedente> conjunción de restricciones atributo=valor
<consecuente> restricción valor de la clases
Si ingresos=moderados,historia=desconocida,deuda=alta
Entonces riesgo=alto
Reglas de asociación 3
Reglas de Asociación
Similares a reglas de clasificación, pero Pueden predecir cualquier atributo Cualquier combinación de atributos
No suelen utilizarse todas juntas Diferentes grupos muestran distintas
regularidades del conjunto de datos
Reglas de asociación 4
Cielo Temp Humedad Viento Jugar
Soleado Alta Alta Falso No
Soleado Alta Alta Cierto No
Cubierto Alta Alta Falso Si
Lluvioso Suave Alta Falso Si
Lluvioso Fría Normal Falso Si
Lluvioso Fría Normal Cierto No
Cubierto Fría Normal Cierto Si
Soleado Suave Alta Falso No
Soleado Fría Normal Falso Si
Lluvioso Suave Normal Falso Si
Soleado Suave Normal Cierto Si
Cubierto Suave Alta Cierto Si
Cubierto Alta Normal Falso Si
Lluvioso Suave Alta Cierto No
Datos: clima
Reglas de asociación 5
Algunas reglas de asociación
Si humedad=normal, viento=falso Entonces jugar=siSi humedad=normal, jugar=si Entonces viento=falsoSi viento=falso, jugar=si Entonces humedad=normalSi humedad=normal Entonces viento=falso, jugar=siSi viento=falso Entonces humedad=normal, jugar=siSi jugar=si Entonces humedad=normal, viento=falsoSi – Entonces humedad=normal, viento=falso, jugar=si
Reglas de asociación 6
Aplicación
Interés: descubrir combinaciones de pares atributo-valor que ocurren con frecuencia en un grupo de datos
Áreas de aplicación Análisis de la cesta de la compra En general: patrón de transacciones que
permite identificar clientes con patrones de comportamiento común a los que se les puede realizar ofertas personalizadas
Reglas de asociación 7
Dificultad
Gran número de posibles reglas a considerar, incluso para conjuntos de datos pequeños, debido a que el consecuente puede contener cualquier combinación de pares atributo-valor.
Las técnicas convencionales, divide y vencerás, separa y vencerás, no son de utilidad Invocarlas para cada posible consecuente Podar en función del error
Reglas de asociación 8
Limitar la generación de reglas
Obtener solo reglas “interesantes” Se aplican a suficientes instancias Son precisas
Soporte: ejemplos que satisfacen antecedente y consecuente O bien: número de instancias que cubre correctamente
la regla Confianza: % de ejemplos que satisfacen el
consecuente de los que hacen cierto el antecedente O bien, cociente ente el soporte y el número de
instancias que satisfacen el antecedente
Reglas de asociación 9
Ejemplo
Si temperatura=alta Entonces humedad= alta
Soporte: nº de instancias con temperatura=alta & humedad= alta, 3
Confianza: soporte dividido por nº de instancias con temperatura=alta, 75% (3/4)
Cielo Temp Humedad
Viento Jugar
Soleado Alta Alta Falso No
Soleado Alta Alta Cierto No
Cubierto Alta Alta Falso Si
Lluvioso Suave Alta Falso Si
Lluvioso Fría Normal Falso Si
Lluvioso Fría Normal Cierto No
Cubierto Fría Normal Cierto Si
Soleado Suave Alta Falso No
Soleado Fría Normal Falso Si
Lluvioso Suave Normal Falso Si
Soleado Suave Normal Cierto Si
Cubierto Suave Alta Cierto Si
Cubierto Alta Normal Falso Si
Lluvioso Suave Alta Cierto No
Reglas de asociación 10
Reglas con múltiple consecuente
No es lo mismo la reglaSi viento=falso, jugar=no Entonces cielo=soleado, humedad=alta
Que las reglasSi viento=falso, jugar=no Si viento=falso, jugar=no Entonces cielo=soleado Entonces humedad=alta
Si la primera regla supera el soporte y la confianza mínimas, también lo superaran las otras dos (lo contrario no es cierto)
Además, significa queSi viento=falso, jugar=no, cielo=soleadoEntonces humedad=alta
Reglas de asociación 11
Generación eficiente de reglas de asociación
1. Buscar combinaciones de pares atributo-valor con suficiente soporte
2. Generar, a partir de ellas, reglas con suficiente confianza
Para ello, se recurre a una estructura intermedia, denominada item-set
Reglas de asociación 12
Item sets
Item: par atributo-valor Item set: conjunto de pares atributo-valor
K-item set: conjunto con k items Generación de item-sets con soporte mínimo
1-item sets, 2-item sets, 3-item sets... Motivación
Una condición necesaria para que un k-item set tenga soporte mínimo es que todos sus (k-1) item sets tengan soporte mínimo
No es suficiente: comprobarlo sobre el conjunto de datos
Cielo Temp Humedad Viento JugarSoleado Alta Alta Falso NoSoleado Alta Alta Cierto NoCubierto Alta Alta Falso SiLluvioso Suave Alta Falso SiLluvioso Fría Normal Falso SiLluvioso Fría Normal Cierto NoCubierto Fría Normal Cierto SiSoleado Suave Alta Falso NoSoleado Fría Normal Falso SiLluvioso Suave Normal Falso SiSoleado Suave Normal Cierto SiCubierto Suave Alta Cierto SiCubierto Alta Normal Falso SiLluvioso Suave Alta Cierto No
13Reglas de asociación
Reglas de asociación 14
104 Item sets para los datos climacon soporte mínimo=2
1-item sets 2-item sets 3-item sets 4-item sets
cielo=soleado (5) cielo=soleado, temp=suave (2)
cielo=soleado, temp=alta humedad=alta (2)
cielo=soleado, temp=alta humedad=alta jugar=no (2)
cielo=cubierto (4) cielo=soleado, temp=alta (2)
cielo=soleado, temp=alta jugar=no (2)
cielo=soleado, humedad=altaviento=falso,jugar=no (2)
cielo=lluvioso (4) cielo=soleado, humedad=normal (2)
cielo=soleado, humedad=normal jugar=si (2)
cielo=cubierto,temp=alta,viento=falso,jugar=si (2)
... total=12 ...total=47 ... total=39 ... total=6
Reglas de asociación 15
Generación de reglas a partir de un item set
Una vez generados los item set, se pueden convertir en reglas
Ejemplohumedad=normal, viento=falso, jugar=si (4)
7 (2n -1) posibles reglasSi humedad=normal, viento=falso Entonces jugar=si 4/4Si humedad=normal, jugar=si Entonces viento=falso 4/6Si viento=falso, jugar=si Entonces humedad=normal 4/6Si humedad=normal Entonces viento=falso, jugar=si 4/7Si viento=falso Entonces humedad=normal, jugar=si 4/8Si jugar=si Entonces humedad=normal, viento=falso 4/9Si – Entonces humedad=normal, viento=falso, jugar=si 4/12
Reglas de asociación 16
Reglas con soporte mínimo 2 y confianza 100%
Regla de asociación Sop. Con.1 Si humedad=normal, viento=falso Entonces jugar=si 4 1002 Si temp=fría Entonces humedad=normal 4 1003 Si cielo=cubierto Entonces jugar=si 4 1004 Si temp=fría, jugar=si Entonces humedad=normal 3 100
... ... ...58 Si cielo=soleado, temp=alta Entonces humedad=alta 2 100
3 con soporte 4 5 con soporte 3 50 con soporte 2
Reglas de asociación 17
Generación eficiente de item sets
Calcular k-item sets a partir de (k-1)-item sets con soporte mínimo
Generar candidatos fusionando (k-1)-item sets con soporte mínimo Sólo candidatos que compartan (k-2) item
[para no obtener k+1 item sets (ABCD) +(ABEF) =(ABCDEF)] Fusión eficiente: orden lexicográfico
No todos los candidatos son válidos: Eliminar candidatos comprobando (k-1)-item sets
Eliminación eficiente: tabla de hash Comprobar que los candidatos tienen soporte: contar
instancias sobre el conjunto de datos
Reglas de asociación 18
Ejemplo
(A B C), (A B D), (A C D), (A C E), (B C D) Si orden lexicográfico, sólo fusionar 3-item
sets con 2 primeros elementos iguales No considerar (A C D) y ( B C D)
Generaría (A B C D): (A B C) y (A B D) han de ser 3-item sets y se habría generado antes
Candidatos 4-item sets (A B C D) Si (A C D E) No, por (C D E) Almacenar (k-1)-item sets en tabla de hash
Comprobar soporte mínimo: una pasada sobre base de datos
Reglas de asociación 19
Generación de reglas a partir de item sets
Generar todas las posibles reglas a partir de un k-item set tiene un coste exponencial: (2k-1)
humedad=normal, viento=falso, jugar=si (23 -1) posibles reglasSi humedad=normal, viento=falso Entonces jugar=siSi humedad=normal, jugar=si Entonces viento=falsoSi viento=falso, jugar=si Entonces humedad=normalSi humedad=normal Entonces viento=falso, jugar=siSi viento=falso Entonces humedad=normal, jugar=siSi jugar=si Entonces humedad=normal, viento=falsoSi – Entonces humedad=normal, viento=falso, jugar=si
Reglas de asociación 20
Generación eficiente de reglas (I)
Si una regla con dos consecuentes tiene soporte y confianza mínimaSi viento=falso, jugar=no
Entonces cielo=soleado, humedad=alta
Las reglas con un consecuente obtenidas del mismo item set también han de tenerlasSi cielo=soleado, viento=falso, jugar=no Entonces humedad=altaSi humedad=alta, viento=falso, jugar=no Entonces cielo=soleado
Reglas de asociación 21
Generación eficiente de reglas
Generar reglas con c consecuentes a partir de reglas con (c-1) consecuentes del mismo item set Una regla con c consecuentes tiene soporte
si todas las reglas con (c-1) consecuentes generadas del mismo item set tiene soporte
Comprobar confianza de las reglas obtenidas
Procedimiento similar al cómputo de item sets con soporte mínimo
Reglas de asociación 22
Ejemplo
Reglas 1-consecuenteSi cielo=soleado, viento=falso, jugar=no
Entonces humedad=altaSi humedad=alta, viento=falso, jugar=no
Entonces cielo=soleado Regla 2-consecuente
Si viento=falso, jugar=noEntonces cielo=soleado, humedad=alta
Comprobar confianza: antecedente, tabla de hash
Reglas de asociación 23
Algoritmo Apriori
Algoritmo para el computo eficiente de reglas de asociación (Agrawal y colaboradores, 1993)
1. Generación eficiente de item sets2. Generación eficiente de reglas
1 pasada conjunto de datos por cada tamaño de item set considerado
Reglas de asociación 24
Reglas de asociación: discusión (I)
Generalmente se aplica a bases de datos muy grandes Interés en algoritmos eficientes Pocas pasadas base de datos
Aun así, se obtienen muchas reglas
Reglas de asociación 25
Reglas de asociación: discusión (II)
Disminuir acceso base de datos Generar k-item set y (k+1) item set
simultaneamente Se consideran algunos (k+1) item set
innecesarios Se recorren menos veces los datos Interesante si no todos caben en memoria
Reglas de asociación: discusión (III)
Generar menos reglas Limitar el número de reglas obtenidas
Especificar un soporte inicial elevado Disminuir iterativamente el soporte, hasta
obtener el nº de reglas deseado
Otras medidas sobre las reglas
Reglas de asociación 26
Referencias[AIS93a] R. Agrawal, T. Imielinski, and A. Swami. Database mining: A performance perspective.
IEEE Transactions on Knowledge and Data Engineering, 5(6):914–925, 1993.
[AIS93b] R. Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of items in large databases. In P. Buneman and S. Jajodia, editors, Proceedings of the ACM SIGMOD International Conference on Management of Data, Washington, DC, pages 207–216, New York, 1993. ACM.
[AS94] R. Agrawal and R. Srikant. Fast algorithms for mining association rules in large databases. In J. Bocca, M. Jarke, and C. Zaniolo, editors, Proceedings of the International Conference on Very Large Databases, Santiago, Chile, pages 478–499, San Francisco, 1994.Morgan Kaufmann.
[CJY96] M.S. Chen, J. Jan, and P. S. Yu. Data mining: An overview from a database perspective. IEEE Transactions on Knowledge and Data Engineering, 8(6):866–883, 1996.
[TSK06] Pang-Ning Tan, Michael Steinbach, and Vipin Kumar. Introduction to Data Mining. Addison Wesley, 2006.
[Web03] Geoffrey I. Webb. Association rules. In Nong Ye, editor, The Handbook of Data Mining, pages 25–39. Lawrence Erlbaum Associates, Mahwah, New Jersey, 2003.
27Reglas de asociación