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

CI-2352 Intr. a la minería de datosProf. 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

La pará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 de sistemas 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 paso necesita 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 gran nú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 itemset candidato 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 itemset frecuentes 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 kLk: 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_supportendreturn ∪kLk;

11 de 67

Algoritmo Apriori: un ejemplo

12 de 67

TID Lista de elementos100 I1, I2, I5101 I2, I4102 I2, I3103 I1, I2, I4104 I1, I3105 I2, I3106 I1, I3108 I1, I2, I3, I5109 I1, I2, I3

● Considérese una base de datos D que consiste de 9 transacciones.

● Suponga que el apoyo mínimo es de 2 (i.e. min_sup = 2/9 = 22 % )

● Sea la confianza mínima requerida de 70%.

● Debemos primero encontrar los conjuntos de elementos frecuentes utilizando Apriori.

● Luego se generan las reglas de asociación utilizando el apoyo mínimo y la confianza mínima.

Apriori: paso 1

● El conjunto de 1-itemset frecuentes, L1, consiste de los 1-itemset candidatos que satisfacen el apoyo mínimo.

● En la primera iteración del algoritmo cada elemento es un miembro del conjunto candidato.

13 de 67

Apriori: paso 2

14 de 67

Apriori: paso 2● Para descubrir el conjunto de 2-itemset frecuentes, L2, el

algoritmo usa L1 Unión L1 para generar un conjunto candidato de 2-itemsets, C2.

● Luego, las transacciones en D son rastreadas y se cuenta el apoyo de cada itemset en C2 (tal como se muestra en la tabla intermedia).

● El conjunto de 2-itemset frecuentes, L2, es determinado, consistiendo de aquellos candidatos 2-itemset en C2 que tienen un apoyo mínimo.

● Nota: Aún no se ha utilizado la propiedad Apriori.15 de 67

Apriori: paso 3

● La generación del conjunto de 3-itemset candidatos, C3, implica el uso de la propiedad Apriori.

● Para encontrar C3, computamos L2 Unión L2.● C3 = L2 Unión L2 = {{I1, I2, I3}, {I1, I2, I5}, {I1, I3, I5}, {I2, I3, I4},

{I2, I3, I5}, {I2, I4, I5}}.● Una vez que la unión está completa se usa la poda para reducir

el tamaño de C3. La poda ayuda a evitar computación pesada debido a un Ck grande.

16 de 67

Apriori: paso 3● Basándose en la propiedad Apriori se puede determinar que 4

candidatos no pueden ser frecuentes. ¿Cómo?● Por ejemplo, tomése {I1, I2, I3}. Los subconjuntos suyos de tamaño 2

son {I1, I2}, {I1, I3} y {I2, I3}. Dado que todos los subconjuntos de tamaño 2 son miembros de L2 se mantiene {I1, I2, I3} en C3.

● Tómese el ejemplo de {I2, I3, I5} que muestra cómo se efectúa la poda. Los subconjuntos de elementos tamaño 2 son {I2, I3}, {I2, I5} y {I3,I5}.

● {I3, I5} no es un miembro de L2 y por lo tanto no es frecuente violando la propiedad Apriori. Así se elimina {I2, I3, I5} de C3.

● Finalmente, C3= {{I1, I2, I3}, {I1, I2, I5}} después de revisar todos los miembros resultado de la unión durante la poda.

● Ahora las transacciones en D son rastreadas para determinar L3, que consiste de aquellos 3-itemset candidatos en C3 que tienen apoyo mínimo.

17 de 67

Apriori: paso 4

● El algoritmo usa L3 Unión L3 para generar un conjunto candidato de 4-itemset, C4. El resultado es {{I1, I2, I3, I5}}, este itemset es podado dado que su subconjunto {{I2, I3, I5}} no es frecuente.

● Así C4 = ∅ y el algoritmo termina habiendo encontrado todos los elementos frecuentes.

● ¿Qué sigue?● Estos itemset frecuentes serán usado para generar

reglas de asociación fuertes (donde dichas reglas satisfacen ambos apoyo y confianza mínimos).

18 de 67

Generación de reglas: paso 5● Procedimiento:

● Para cada itemset l frecuente se generan todos los subconjuntos vacíos.

● Para cada subconjunto s no vacío de I se imprime la regla “s → (l-s)” si support_count(l) / support_count(s) >= min_conf donde min_conf es el umbral de confianza mínima.

● Volviendo al ejemplo:● Se tenía L = {{I1}, {I2}, {I3}, {I4}, {I5}, {I1,I2}, {I1,I3},

{I1,I5}, {I2,I3}, {I2,I4}, {I2,I5}, {I1,I2,I3}, {I1,I2,I5}}.● Tómese l = {I1,I2,I5}.● Sus subconjuntos no vacíos son {I1,I2}, {I1,I5}, {I2,I5},

{I1}, {I2}, {I5}.

19 de 67

Generación de reglas: paso 5● Sea el umbral de confianza mínima 70%.● Las reglas de asociación resultantes se

muestran acá con su confianza.● R1: I1 ^ I2 →I5

– confianza = sc{I1,I2,I5}/sc{I1,I2} = 2/4 = 50%– R1 es rechazada.

● R2: I1 ^ I5 →I2– confianza = sc{I1,I2,I5}/sc{I1,I5} = 2/2 = 100%– R2 es seleccionada.

● R3: I2 ^ I5 →I1– confianza = sc{I1,I2,I5}/sc{I2,I5} = 2/2 = 100%– R3 es seleccionada.

20 de 67

Generación de reglas: paso 5● R4: I1 →I2 ^ I5

– confianza = sc{I1,I2,I5}/sc{I1} = 2/6 = 33%– R4 es rechazada.

● R5: I2 →I1 ^ I5– confianza = sc{I1,I2,I5}/{I2} = 2/7 = 29%– R5 es rechazada.

● R6: I5 →I1 ^ I2– confianza = sc{I1,I2,I5}/ {I5} = 2/2 = 100%– R6 es seleccionada.

● De esta manera se han encontrado 3 reglas fuertes de asociación.

21 de 67

Sobre el algoritmo● Parece ser muy caro

● Búsqueda por nivel.● K = el tamaño del itemset más grande.● Hace al menos K pasadas sobre los datos.● En la práctica, K es acotada (10). ● El algoritmo es muy rápido. Bajo algunas

condiciones, todas las reglas pueden ser encontradas en tiempo lineal.

● Escala en grandes conjuntos de datos.

22 de 67

Posibles métodos para mejorar la eficiencia de Apriori

● Conteo de elementos basado en tablas de dispersión (Hash): Un k-itemset cuya cuenta en su cubeta está por debajo de un umbral no puede ser frecuente.

● Reducción de transacciones: Una transacción que no contiene ningún k-itemset frecuente es inútil en rastreos subsiguientes.

● Particionamiento: Cualquier itemset que es potencialmente frecuente en una base de datos debe ser frecuente en al menos una partición de la base de datos.

23 de 67

Posibles métodos para mejorar la eficiencia de Apriori

● Muestreo: minar un subconjunto de los datos, menor umbral de apoyo y un método para determinar completitud.

● Conteo de itemset dinámico: agregar nuevos itemset candidatos solamente cuando todos sus subconjuntos son estimados frecuentes.

24 de 67

Implementación eficiente de Apriori● Recursion Pruning for the Apriori Algorithm

● Christian Borgelt.● 2nd Workshop of Frequent Item Set Mining

Implementations (FIMI 2004, Brighton, UK).● Efficient Implementations of Apriori and Eclat

● Christian Borgelt.● Workshop of Frequent Item Set Mining Implementations

(FIMI 2003, Melbourne, FL, USA).● Induction of Association Rules: Apriori Implementation

● Christian Borgelt and Rudolf Kruse● 15th Conference on Computational Statistics (Compstat

2002, Berlin, Germany), 395-400● Physica Verlag, Heidelberg, Germany 2002

25 de 67

Implementación eficiente de Apriori

26 de 67

● Árbol de prefijos:● Organiza los conteos de itemset.● Utiliza poca memoria.● Permite procesar las transacciones.● Permite generar las reglas.● Cada nodo nS denota un contador para un itemset

S.

Implementación eficiente de Apriori

27 de 67

Implementación eficiente Apriori● Organización de los nodos:

● Posibilidades:– Vector de enteros:

● Eficiente en espacio (elementos implícitos en el índice).● Eficiente para encontrar el contador de un elemento.● Desventaja en que requiere tener espacio para elementos que

tal vez sea infrecuentes pues el vector no puede tener vacíos o espacios. Esto se puede mitigar parcialmente guardando el índice del elemento inicial y un desplazamiento (con lo cual se eliminan elementos infrecuentes en el margen).

– Vector de estructuras:● Identificador del elemento y contador.● Es ventajoso porque sólo se representan los elementos que se

requieren.● Es desventajoso porque requiere de memoria extra y requiere

de búsqueda binaria.

28 de 67

Implementación eficiente Apriori● Organización de los nodos:

● Posibilidades:– Tabla de dispersión por nodo:

● Reduce el tiempo de acceso.● Sin embargo, aumenta la memoria requerida (una tabla para que

sea óptima no puede estar demasiado llena).● No permite explotar el orden de los elementos.

● Obviamente, para optimizar velocidad se debe utilizar vectores simples a pesar de los “huecos”.

● Para optimizar espacio se puede escoger otra.

29 de 67

Implementación eficiente de Apriori● Organización de los nodos:

● Se necesita un conjunto de punteros a nodos hijos.– No se deben crear antes de que se necesiten.

● Para estos punteros se tienen las mismas opciones que para organizar los contadores.

● Si los contadores tienen identificadores asociados es posible utilizar el mismo orden de los elementos y dejar los punteros en nulo si no se necesitan. Puede ahorrar memoria pero pueden haber muchos nulos.

30 de 67

Implementación eficiente de Apriori● Codificación de los elementos:

● Es claro que la manera en que se codifican los elementos (enteros) puede tener un impacto en el problema de los “huecos” o espacios.

● Una heurística interesante puede ser ordenar los elementos por frecuencia. Así, si se utiliza la representación desplazamiento/tamaño, los “huecos” podrían encontrarse en los márgenes del vector.

31 de 67

Implementación eficiente de Apriori● Conteo recursivo:

● Si se ordenan los elementos en la transacción con respecto a sus identificadores, entonces procesar una transacción es un procedimiento doblemente recursivo:1.Se va al hijo correspondiente al primer elemento en la

transacción y se procesa el restante de la transacción para ese hijo.

2.Se descarta el primer elemento en la transacción y se procesa recursivamente para ese nodo.

● En un nodo del nivel que se está construyendo no se va a un nodo hijo, sino que se incrementan los contadores.

32 de 67

Implementación eficiente de Apriori● Representación de las transacciones:

● También es posible representar las transacciones por medio de un árbol de prefijos y hacer operaciones en bloques (prefijos).

● Hay una ganancia de rendimiento en el hecho de que sólo se hace una vez la operación el prefijo.

● Por supuesto, la ganancia debe ser mayor al costo de construir un árbol de prefijos para las transacciones.

33 de 67

Representación de las transacciones

34 de 67

Patrones secuenciales

Patrones secuenciales

● La minería de patrones secuenciales es la minería de patrones que ocurren frecuentemente relacionados al tiempo u a otras secuencias. Un ejemplo de patrón secuencial es “Un cliente que compra una computadora personal Pentium nueve meses antes probablemente comprará un chip de CPU nuevo en un mes”.

36 de 67

Patrones secuenciales: aplicaciones● Aplicaciones de la minería de patrones

secuenciales● Secuencias de compra del cliente:

– Primero compra computador, luego CD-ROM y por último una cámara digital, en 3 meses.

● Tratamientos médicos, desastres naturales (e.g., terremotos), procesos de la ingeniería y las ciencias, mercados y valores, etc.

● Patrones de llamadas telefónicas, flujos de navegación en el Web

● Estructuras de ADN y genes

37 de 67

Patrones secuenciales

● Es similar a la minería de itemset frecuentes, pero con una consideración de orden.

38 de 67

39

Algoritmos para minería de patrones secuenciales

● Enfoques basados en Apriori● GSP (Generalized Sequential Patterns)● SPADE

● Enfoques basados en crecimiento de patrones● FreeSpan● PrefixSpan

39 de 67

40

El algoritmo GSP● Tomar las secuencias de la forma <x> como

candidatos tamaño-1● Rastrear la base de datos una vez, encontrar F1, el

conjunto de patrones secuenciales tamaño-1● Sea k=1; mientras Fk no esté vacío haga

● Forme Ck+1, el conjunto de candidatos tamaño-(k+1) de Fk;● Si Ck+1 no está vacío, rastree la base de datos una vez,

encuentre Fk+1, el conjunto de patrones secuenciales tamaño-(k+1);

● Sea k=k+1;

40 de 67

GSP

41 de 67

GSP

42 de 67

GSP

43 de 6743 de 67

GSP

44 de 6744 de 67

GSP

45 de 67

GSP: Ejemplo

46 de 67

GSP: Ejemplo

47 de 67

GSP: Ejemplo

48 de 67

GSP: Ejemplo

49 de 67

GSP: Ejemplo

50 de 67

Patrones secuenciales en lógica temporal

Patrones secuenciales en lógica temporal

● Transacciones de compra:● Los artículos en s

i son comprados en el tiempo ti,

donde t1 < t2 < … < tn.● pj

k (k = 1, …, n) son las variables proposicionales que representan los artículos en el conjunto sj.

● Un patrón será una fórmula: s1 ˄ <F> (s2 ˄ <F> (s3 ˄ <F> (… ˄ <F> sn)...)), donde sj es la fórmula (pj

1 ˄ pj2 ˄ … pj

nj )

● Otros dominios:● Cambiar artículos por síntomas, eventos u otros.

52 de 67

Programación lógica temporal

53 de 67

Programación lógica temporal

54 de 67

Programación lógica temporal

55 de 67

Algoritmo de detección de patrones usando lógica temporal

56 de 67

Algoritmo de detección de patrones usando lógica temporal

57 de 67

Algoritmo de detección de patrones usando lógica temporal

58 de 67

Ejemplo: datos

59 de 67

Ejemplo: paso 1

Ejemplo: paso 2

Ejemplo: paso 3

Ejemplo: paso 3

Ejemplo: paso 3

Ejemplo: paso 4

Implementación

66 de 67

¡Gracias por su atención!

¿Preguntas?