<style>
.reveal section img { background:none; border:none; box-shadow:none; }
.reveal {
font-size: 30px;
}
.reveal p {
text-align: left;
}
.reveal ul {
display: block;
}
.reveal ol {
display: block;
}
</style>
<h1>El problema de los items frecuentes</h1>
## Taller Nous Usos de la Informàtica
<h1><img width="150" src="https://i.imgur.com/vvZMy0I.png"></h1>
---
<h1><img width="450" src="https://i.imgur.com/Dl2HOtV.png"></h1>
---
## El modelo de la bolsa de la compra
Datos:
+ Dado un gran conjunto de ítems, como por ejemplo los productos que se venden en un supermercado.
+ Dado un gran conjunto de clientes en un período determinado, cada uno con sus bolsas de la compra.
Pregunta:
+ **Qué información útil podemos obtener a partir de analizar el contenido de las bolsas de la compra?**
Este tipo de relación de "muchos a muchos" se puede aplicar a muchos tipos de problemas, no sólo a bolsas de la compra, es muy general!
---
## Conjuntos de ítems frecuentes
La pregunta más simple que podemos hacernos es:
+ **¿Cuáles son los subconjuntos de ítems que aparecen de forma más frecuente en las bolsas?**
Responderla puede ayudarnos en diversas tareas: recomendación, acciones de marketing, acciones de promoción, etc.
---
## Conjuntos de ítems frecuentes
Deficiones:
+ Supongamos que consideramos el conjunto $U$ de ítems a la venta que hay en el supermercado.
+ Dado un subconjunto de ítems $I \subset U$, definimos el *soporte* de $I$ como el número de bolsas que contienen el subconjunto $I$.
+ Dado un valor predefinido $s$, llamamos *conjunto de ítems frecuentes* a cada uno de los subconjuntos de ítems que tienen un soporte igual o superior a $s$.
---
## Ejemplo: Conjuntos de ítems frecuentes
+ Ítems = $\{ m, c, p, b, j \}$; Soporte: $s = 3$ bolsas.
+ Las bolsas:
$$B_1 = \{ m, c, b \} \\
B_2 = \{ m, p, j \} \\
B_3 = \{ m, b \} \\
B_4 = \{ c, j \} \\
B_5 = \{ m, p, b \} \\
B_6 = \{ m, c, b, j \} \\
B_7 = \{ c, b, j \} \\
B_8 = \{ b, c \}$$
---
## Ejemplo: Conjuntos de ítems frecuentes
+ Los conjuntos de ítems frecuentes son:
$$\{ m \}, \{ c \},\{ b
\},\{ j \},\{ m, b \},\{ b, c \},\{ c, j \}$$,
---
## Aplicaciones
+ Si los ítems son los productos de un supermercado y las bolsas son lo que un cliente compra un día determinado, una de las *conexiones interesantes* que podríamos encontrar es, por ejemplo, que mucha gente compra cerveza y pañales al mismo tiempo.
+ Alguien podría utilizar esta información para colocarlos juntos en el supermercado y hacer una oferta sobre los pañales y al mismo tiempo subir el precio de la cerveza para compensar (¡los humanos somos fácilmente manipulables!).
+ Esta estrategia es útil en función de su frecuencia, que no es necesario que sea muy grande: si hay un mínimo porcentaje de gente que compra cerveza y pañales (por ejemplo, un 1\%).
---
## Aplicaciones
+ Si los ítems son documentos, las bolsas son frases, y definimos que un ítem/documento está en una bolsa/frase si la frase está en el documento, los conjuntos de ítems frecuentes pueden indicar problemas de *plagiarismo*.
+ Como podemos ver en este ejemplo, lo estamos aplicando a una relación de muchos-a-muchos que no es del tipo "forma-part-de*": si hay un par de ítems que aparecen juntos en varias bolsas es que tenemos documentos con las mismas frases.
+ Si las bolsas son párrafos y los ítems palabras, la coocurrencia de ciertas palabras puede ayudar a caracterizar a autores y ayudar en la identificación de sus obras.
---
## Aplicaciones
+ Si las bolsas son pacientes que han sufrido efectos no deseados después de un tratamiento y los ítems son medicamentos que a priori no podían generar estos efectos, podemos detectar interacciones peligrosas entre medicamentos.
---
## Uso: Generación de reglas de asociación
+ Este análisis puede generar reglas del tipo `If-Then` sobre los contenidos de las bolsas. ¡Esto puede ser útil como recomendación!
+ $\{ i_1, i_2, i_3, \dots, i_k \} \rightarrow j$ significa que si la bolsa contiene los ítems $i_1, i_2, i_3, \dots, y_k$ entonces es muy probable que contenga $j$.
+ La **confianza** de esta regla de asociación es la probabilidad condicional de $j$ dados $i_1, i_2, i_3, \dots, i_k$:
$$
C = p(j|i_1, \dots, i_k) = \frac{\mbox{Apoyo } \{ i_1, i_2, i_3, \dots, i_k \} \cup \{ j
\}}{\mbox{Apoyo }\{ i_1, i_2, i_3, \dots, i_k \}}
$$
---
## Reglas de asociación interesantes
+ No todas las reglas de asociación son interesantes.
+ Por ejemplo, la regla $X \rightarrow leche$ puede tener una confianza alta sólo porque mucha gente compra leche, independientemente de $X$.
+ El *interés* se define como la diferencia entre su *confianza* y la fracción de bolsas (sobre el total) que contienen $j$.
$$
I = p(j|i_1, \dots, i_k) - p(j)
$$
+ Las reglas $\{ i_1, i_2, i_3, \dots, i_k \} \rightarrow j$ **interesantes son las que tienen un valor muy positivo (o negativo) de interés**.
---
## Reglas de asociación interesantes
+ Por tanto,
+ $pañales \rightarrow cerveza$ tiene un interés alto,
+ $coke \rightarrow pepsi$ y $pepsi \rightarrow coke$ tienen un interés muy bajo (negativo)
+ $X \rightarrow leche$ tiene un interés 0.
---
## Ejemplo: Confianza e interés
$$B_1 = \{ m, c, b \}\\
B_2 = \{ m, p, j \}\\
B_3 = \{ m, b \}\\
B_4 = \{ c, j \}\\
B_5 = \{ m, p, b \}\\
B_6 = \{ m, c, b, j \}\\
B_7 = \{ c, b, j \}\\
B_8 = \{ b, c \}$$
+ La regla de asociación $\{ m, b \} \rightarrow c$ tiene una confianza 0.5 (hay dos casos sobre los cuatro posibles) y un interés -0.125 (= 0.5 - 5/8).
---
## Búsqueda de reglas de asociación
+ El problema es encontrar todas las reglas de asociación con soporte $\geq s$ y confianza $\geq c$*.
+ El soporte de la regla es el soporte del conjunto de elementos de la izquierda.
+ La parte más dura es encontrar los conjuntos de ítems más frecuentes:
+ Si $\{ i_1, i_2, i_3, \dots, i_k \} \rightarrow j$ tiene soporte (1\%) y confianza (50\%) elevados entonces tanto $\{ i_1, i_2, i_3, \dots, i_k \}$ como $\{ i_1, i_2, i_3, \dots, i_k, j \}$ serán frecuentes.
+ Debemos encontrar todos los conjuntos de ítems con soporte alto y después todas las reglas de asociación con soporte e interés suficientes.
+ Si en conjunto de ítems frecuentes tenemos $j$ elementos, podemos generar $j$ posibles reglas.
---
## Modelo Computacional
+ Típicamente los datos (que pueden ser un caso de datos masivos en el caso de un supermercado) los tendremos en un archivo en uno o varios discos, almacenados *por bolsas* y debemos expandir las bolsas en pares, tripletas, etc . a medida que vayamos leyendo las bolsas.
+ La implementación ingenua es muy costosa.
---
## Modelo Computacional Ingenuo
```python=
from itertools import combinations
bags=[['m','c','b'],['m','p','j'],['m','b'],
['c','j'], ['m','p','b'],['m','c','b','j'],
['c','b','j'],['b','c']]
# seguramente deben leer las bolsas del disco
# de forma secuencial ...
únicos = set()
for bag in bags:
for item in bag:
unics.add(item)
print(únicos)
>>> {'j', 'm', 'c', 'p', 'b'}
```
---
```python=
d = dict.fromkeys(list(unics),0)
for bag in bags:
for item in d.keys():
if bag.count(item):
d[item]+=1
print(d)
>>> {'j': 4, 'm': 5, 'c': 5, 'p': 2, 'b': 6}
```
---
## Modelo Computacional Ingenuo
```python=
parejas = set()
for e in combinations(items, 2):
parejas.add(i)
print(parejas)
>> {('c', 'p'), ('m', 'c'), ('m', 'p'),
('j', 'b'), ('m', 'b'), ('j', 'c'),
('j', 'p'), ('c', 'b'), ('j', 'm'),
('p', 'b')}
# leer las bolsas y contar ...
```
---
## Modelo Computacional
+ El coste más importante a la hora de procesar estos datos es el número de lecturas/escrituras en el disco.
+ En la práctica, los algoritmos que generan reglas de asociación leen los datos en *pasadas* leyendo todas las bolsas una tras otra.
+ Por tanto, mediremos el coste del algoritmo por el número de pasadas que hace sobre el conjunto total de los datos.
---
## Modelo Computacional
+ Para estos algoritmos, el uso de la memoria principal es el recurso más crítico.
+ A medida que leemos bolsas, debemos contar algo (como por ejemplo los golpes que aparece una determinada tupla de ítems).
+ El número de cosas diferentes que podemos contar está limitado por la memoria principal.
---
## Encontrando parejas frecuentes
+ El problema más duro es normalmente el de encontrar a las parejas más frecuentes.
+ A menudo, las parejas frecuentes son bastante numerosas. Las tripletas frecuentes son mucho más raras.
+ Si tenemos $n$ elementos hay $\binom{n}{k} = \frac{n!}{k! (n-k)!}$ posibles conjuntos de $k$ elementos. Por $n=20$ tenemos 190 posibles parejas.
+ La probabilidad de que un conjunto de ítems sea frecuente baja de forma exponencial respecto al tamaño del conjunto.
+ Por tanto, nos concentraremos en las parejas y después lo extenderemos a conjuntos más numerosos.
---
## Un algoritmo ingenuo
Primera aproximación:
1. Leemos el archivo una vez y ponemos a una matriz de $(\# items)^2$ elementos el número de ocurrencias de cada pareja.
2. El algoritmo dará un error si $(\# items)^2$ excede el tamaño de la memoria.
+ El número de ítems puede ser del orden de 100.000 (en un gran supermercado) o de 10.000.000.000 si hablamos de páginas web.
---
## Cómo contar las parejas
Segunda aproximación:
+ Almacenar sólo las tripletas $[i,j,c]$ tales que $count(i,j)=c$, con $c>0$, en forma de lista o diccionario.
+ Si los enteros y los identificadores de los ítems se pueden guardar en 4 bytes, en una lista al menos necesitamos 12 bytes por cada pareja.
+ Si lo guardamos en un diccionario (con $[i,j]$ como clave) necesitaremos un poco más de memoria adicional.
---
## Cómo contar las parejas
+ ¿Qué ocurre si la mayoría de parejas salen alguna vez?
+ Pues que necesitaremos $12n^2/2$ bytes para guardarlas (si tenemos `(i,j)` no es necesario guardar `(j,i)`) y esto sólo nos permite tener un número de ítems de l orden de miles en un ordenador convencional.
---
## Cómo contar las parejas
Tercera aproximación:
+ Podemos reducir espacio si intentamos almacenar todos los $\binom{n}{2}$ contadores de forma que sea fácil encontrarlos en memoria dada la pareja $(i,j)$, sin tener que guardar $(i,j )$.
+ Representar los ítems con enteros lo simplificará.
---
## Cómo contar las parejas: **Matriz Triagular**
1. Numeramos los ítems 1,2,3,...
2. Almacenaremos el contador de $\{i,j\}$ en una **matriz triangular** $A[i,j]$. Con esto ahorramos el espacio para guardar los identificadores de los productos y la mitad de la matriz.
---
## Cómo contar las parejas
+ De hecho, si mantenemos los contadores de las parejas en orden lexicográfico podemos guardar la matriz en una **lista triangular**:
+ Si $A = [a_{(1,2)}, a_{(1,3)}, \dots, a_{(1,n)}, a_{(2,3)}, \dots, a_{ (3,4)}, \dots, a_{(n-1,n)}]$ entonces el contador de la pareja $(i,j)$ está en la posición $A[(i-1)(n-i/ 2)+j-i]$.
+ El número total de parejas es $\frac{n(n-1)}{2}$, que ocupan un total de $2n^2$ bytes (4 bytes por pareja).
---
## Cómo contar las parejas
+ El método de la matriz triangular (4 bytes por pareja) es mejor que un diccionario (12 bytes por pareja) si al menos $\frac{1}{3}$ de las $\binom{n}{2}$ parejas aparece en alguna bolsa. Sino, son mejor los diccionarios.
+ Los conjuntos de $n>2$ ítems no tienen tanto problemas para ser almacenados, ¡normalmente hay muchos menos que parejas!
---
## El algoritmo **Apriori**
+ El algoritmo **Apriori** es un método que busca conjuntos de ítems frecuentes con muy pocas lecturas de los datos y hace un uso muy limitado de la memoria.
+ Sus ideas principales son:
+ *Monotonía*: Si un conjunto de ítems aparece al menos $s$ veces en el conjunto, todos sus posibles subconjuntos también aparecen al menos $s$ veces!
+ Por otro lado, si un elemento $i$ no aparece en $s$ bolsas, entonces ningún conjunto que incluya $i$ puede aparecer en $s$ bolsas.
---
## El algoritmo **Apriori**
<h1><img width="550" src="https://i.imgur.com/4tGHLLM.png"></h1>
---
## El algoritmo **Apriori**
<h1><img width="550" src="https://i.imgur.com/SeS0Hdq.png"></h1>
---
## El algoritmo **Apriori**
+ En la primera pasada leemos las bolsas, traducimos los ítems a enteros y contamos en la memoria principal las ocurrencias de cada ítem. Este proceso requiere una parte de la memoria proporcional al número de elementos.
+ Luego identificamos los ítems que aparecen al menos $s$ veces, y por tanto son los $m$ **ítems frecuentes**.
---
## El algoritmo **Apriori**
+ En la segunda pasada, leemos las bolsas otra vez y **contamos sólo las parejas por las que ambos elementos fueron etiquetados como frecuentes en la pasada anterior**. Por la propiedad de monotonía seguro que no perdemos ninguna pareja frecuente.
+ Esto requiere como máximo una cantidad de memoria proporcional al cuadrado de los ítems frecuentes (para guardar los contadores) $O(m^2)$.
+ También necesita una lista de los $m$ ítems frecuentes (para saber qué debemos contar).
---
## El algoritmo **Apriori**
+ Podemos utilizar el método de la matriz triangular con un $m$ correspondiente al número de ítems frecuentes.
+ Para ello, renumeramos los ítems frecuentes $1,2, \dots$ y mantenemos una tabla que relaciona los nuevos números con los identificadores originales de los ítems.
---
## Tripletas, etc.
+ Para construir los conjuntos de $k$ ítems a partir de los de $k-1$, construimos dos $k$-conjuntos (conjuntos de tamaño $k$) a partir de los anteriores:
+ $C_k$ = $k$-conjuntos candidatos = aquellos conjuntos que pueden ser frecuentes, basándose en la información de la pasada por $k-1$.
+ $L_k$ = el conjunto de $k$-conjuntos realmente frecuentes.
<h1><img width="550" src="https://i.imgur.com/JclfgbJ.png"></h1>
---
## El algoritmo **Apriori** para todos los conjuntos de ítems frecuentes
+ Un paso por cada $k$.
+ Necesita espacio en la memoria principal para contar cada $k$-conjunto candidato.
+ Por un conjunto de datos típico y un soporte razonable (p.e. 1\%), $k=2$ es el paso que necesita más memoria.
---
## Ejemplo
+ Consideramos una base de datos, $D$, con 9 transacciones.
+ Supongamos que el soporte mínimo es 2.
+ Definimos el nivel de confianza mínimo como el 70\%.
+ El objetivo es generar las reglas de asociación.
---
## Ejemplo
|Bolsa |Ítems|
|-----|--------|
| 001 | I1, I2, I5 |
| 002 | I2, I4 |
| 003 | I2,I3 |
| 004 | I1,I2,I4 |
| 005 | I1, I3 |
| 006 | I2, I3 |
| 007 | I1, I3 |
| 008 | I1, I2 ,I3, I5 |
| 009 | I1, I2, I3 |
---
## Ejemplo
Paso 1: Crear los 1-conjuntos más frecuentes.
+ Leemos $D$ para contar cada uno de los candidatos y creamos $C_1$:
|Conjunto |Contador|
|-----|--------|
I1 | 6 |
I2 | 7 |
I3 | 6 |
I4 | 2 |
I5 | 2 |
---
## Ejemplo
+ Comparamos el apoyo de cada candidato con el valor de mínimo apoyo y creamos $L_1$:
|Conjunto |Contador|
|-----|--------|
I1 | 6 |
I2 | 7 |
I3 | 6 |
I4 | 2 |
I5 | 2 |
---
## Ejemplo
Paso 2: Generar los 2-conjuntos más frecuentes.
+ Generamos los candidatos $C_2$ desde $L_1$ y contamos cuántas veces aparecen:
|Conjunt |Comptador|Conjunt |Comptador|
|-----|--------|-----|--------|
| {I1, I2} | 4 | {I2, I4} | 2 |
| {I1, I3} | 4 | {I2, I5} | 2 |
| {I1, I4} | 1 | {I3, I4} | 0 |
| {I1, I5} | 2 | {I3, I5} | 1 |
| {I2, I3} | 4 | {I3, I5} | 1 |
---
## Ejemplo
+ Comparamos el apoyo de cada candidato con el valor de mínimo apoyo y creamos $L_2$:
|Conjunto |Contador|
|-----|--------|
| {I1, I2} | 4 |
| {I1, I3} | 4 |
| {I1, I5} | 2 |
| {I2, I3} | 4 |
| {I2, I4} | 2 |
| {I2, I5} | 2 |
---
## Ejemplo
Paso 3: Generar los 3-conjuntos más frecuentes.
+ Generamos los candidatos $C_3$ desde $L_2$ y contamos cuántas veces aparecen:
|Conjunto |Contador|
|-----|--------|
| {I1, I2, I3} | 2 |
| {I1, I2, I5} | 2 |
+ La generación de los 3-conjuntos más frecuentes ha hecho uso de la propiedad del algoritmo Apriori: $\{I2, I3, I5\}$ no ha sido contado porque $\{I3,I5\}$ no está en $L_2$.
---
## Ejemplo
+ Comparamos el apoyo de cada candidato con el valor de mínimo apoyo y creamos $L_3$:
|Conjunto |Contador|
|-----|--------|
|{I1, I2, I3} | 2 |
|{I1, I2, I5} | 2 |
+ Esta propiedad también nos dice que ningún subconjunto de 4 candidatos puede ser frecuente.
---
## Ejemplo: Reglas de asociación
+ Por cada conjunto de elementos frecuentes $I$ generaremos todos los subconjuntos no vacíos de $I$.
+ Por cada subconjunto no vacío $s$ de $I$ produciremos una regla
$s \rightarrow \{I-s\}$ si $\frac{soporte(I)}{soporte(s)} \geq$ confianza-mínima.
+ El resultado final es que hemos encontrado como conjuntos de ítems frecuentes: $\{I1\}$, $\{I2\}$, $\{I3\}$, $\{I4\}$, $\{I5\}$, $\{I1,I2\}$, $\{I1,I3\}$, $\{I1,I5\}$, $\{I2, I3\}$, $\{I2, I4\}$,$\{I2,I5\}$, $\{I1,I2,I3\}$, $\{I1,I2,I5\}$.
+ Si consideramos $\{I1,I2,I5\}$, sus subconjunto posibles son $\{I1\}$, $\{I2\}$, $\{I5\}$, $\{I1,I2 \}$, $\{I1,I5\}$,$\{I2,I5\}$.
---
## Ejemplo: Reglas de asociación
+ Supongamos que el nivel mínimo de confianza es del 70\%.
+ Las búsqueda de reglas de asociación es:
+ I1 $\wedge$ I2 $\rightarrow$ I5, Confianza=2/4=50\%, regla rechazada.
+ I1 $\wedge$ I5 $\rightarrow$ I2, Confianza=2/2=100\%, **regla aceptada**.
+ I2 $\wedge$ I5 $\rightarrow$ I1, Confianza=2/2=100\%,**regla aceptada**.
+ I1 $\rightarrow$ I2 $\wedge$ I5, Confianza=2/6=33\%, regla rechazada.
+ I2 $\rightarrow$ I1 $\wedge$ I5, Confianza=2/7=29\%, regla rechazada.
+ I5 $\rightarrow$ I1 $\wedge$ I2, Confianza=2/2=100\%,**regla aceptada**.
---
## Otras aplicaciones: corredores GPS
<h1><img width="550" src="https://i.imgur.com/aDft0Lm.jpg"></h1>
<sup> Cavallaro, C.; Vitrià, J. Corridor Detection from Large GPS Trayectorias Datasets. Appl. Sci. 2020, 10, 5003. https://doi.org/10.3390/app10145003 </sup>
{"description":"Dades:","title":"El problema de los items frecuentes","slideOptions":"{\"theme\":\"white\",\"transition\":\"fade\"}","contributors":"[{\"id\":\"f9d66d82-46e3-417e-9b01-6c6eb9dedb12\",\"add\":17527,\"del\":17117}]"}