<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 dels ítems freqüents</h1>
## Taller Nous Usos de la Informàtica
<h1><img width="150" src="https://i.imgur.com/vvZMy0I.png"></h1>
---
<h1><img width="750" src="https://hackmd.io/_uploads/rJztOrzgkg.jpg"></h1>
<center> Els prestatges d'un supermercat són un recomanador físic? </center>
---
<h1><img width="650" src="https://i.imgur.com/Dl2HOtV.png"></h1>
---
## Les dades disponibles
<h1><img width="450" src="https://hackmd.io/_uploads/SkZatSGeyg.png"></h1>
---
## El model de la bossa de la compra
Dades:
+ Donat un gran conjunt d'ítems, com per exemple els productes que es venen a un supermercat.
+ Donat un gran conjunt de clients en un periode determinat
+ En general només podem obtenir el contingut de les bosses de la compra (tiquets).
Pregunta:
+ **Quina informació útil podem obtenir a partir d'analitzar el contingut de les bosses de la compra?**
---
## Conjunts d'ítems freqüents
La pregunta "més simple" que podem intentar respondre és:
+ **Quins són els subconjunts d'ítems que apareixen de manera més freqüent a les bosses?**
Respondre-la ens pot ajudar en diverses tasques: recomanació, accions de marketing, accions de promoció, etc.
Aquest tipus de relació de "molts-a-molts" es pot aplicar a molts tipus de problemes, no només a bosses de la compra, és molt general!
---
## Conjunts d'ítems freqüents
Definicions:
+ Suposem que considerem el conjunt $U$ d'ítems a la venta que hi ha al supermercat.
+ Donat un subconjunt d'ítems $I \subset U$, definim el *suport* d'$I$ com el nombre de bosses que contenen el subconjunt $I$.
+ Donat un valor predefinit $s$, anomenem *conjunt d'ítems freqüents* a cada un dels subconjunts d'ítems que tenen un suport igual o superior a $s$.
---
## Exemple: Conjunts d'ítems freqüents
+ Ítems = $\{ m, c, p, b, j \}$;
+ Suport: $s = 3$ bosses.
+ Les bosses: $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 \}.
---
## Exemple: Conjunts d'ítems freqüents
+ El conjunts d'ítems freqüents són:
$$\{ m \}, \{ c \},\{ b
\},\{ j \},\{ m, b \},\{ b, c \},\{ c, j \}$$,
---
## Aplicacions
+ Si els ítems són els productes d'un supermercat i les bosses són el que un client compra un dia determinat, una de les *connexions interessants* que podríem trobar és, per exemple, que molta gent compra cervesa i bolquers al mateix temps.
+ Algú podria fer servir aquesta informació per col·locar-los junts al supermercat i fer una oferta sobre els bolquers i al mateix temps pujar el preu de la cervesa per compensar (els humans sóm fàcilment manipulables!).
+ Aquesta estratègia és útil en funció de la seva freqüència, que no cal que sigui molt gran: si hi ha un mínim percentatge de gent que compra cervesa i bolquers (per exemple, un 1\%).
---
## Aplicacions
+ Si els ítems són documents, les bosses són frases, i definim que un ítem/document està a una bossa/frase si la frase està al document, els conjunts d'ítems freqüents poden indicar problemes de *plagiarisme*.
+ Com podem veure en aquest exemple, ho estem aplicant a una relació de molts-a-molts que no és del tipus "*forma-part-de*": si hi ha un parell d'ítems que apareixen junts a varies bosses és que tenim documents amb les mateixes frases.
+ Si les bosses són paràgrafs i els ítems paraules, la coocurrència de certes paraules pot ajudar a caracteritzar autors i ajudar en la identificació de les seves obres.
---
## Aplicacions
+ Si les bosses són pacients que han sofert efectes no desitjats després d'un tractament i els ítems són medicaments que a priori no podien generar aquests efectes, podem detectar interaccions perilloses entre medicaments.
---
## Ús: Generació de regles d'associació
+ Aquesta anàlisi pot generar regles del tipus `If-Then` sobre els continguts de les bosses. Això pot ser útil com a recomanació!
+ $\{ i_1, i_2, i_3, \dots, i_k \} \rightarrow j$ significa que si la bossa conté els ítems $i_1, i_2, i_3, \dots, i_k$ llavors és molt probable que contingui $j$.
+ La **confiança** d'aquesta regla d'associació és la probabilitat condicional de $j$ donats $i_1, i_2, i_3, \dots, i_k$:
$$
C = p(j|i_1, \dots, i_k) = \frac{\mbox{Suport } \{ i_1, i_2, i_3, \dots, i_k \} \cup \{ j
\}}{\mbox{Suport }\{ i_1, i_2, i_3, \dots, i_k \}}
$$
---
## Regles d'associació interessants
+ No totes les regles d'associació són interessants.
+ Per exemple, la regla $X \rightarrow llet$ pot tenir una confiança alta només perquè molta gent compra llet, independentment de $X$.
+ L'*interès* es defineix com la diferència entre la seva *confiança* i la fracció de bosses (sobre el total) que contenen $j$.
$$
I = p(j|i_1, \dots, i_k) - p(j)
$$
+ Les regles $\{ i_1, i_2, i_3, \dots, i_k \} \rightarrow j$ **interessants són les que tenen un valor molt positiu (o negatiu) d'interès**.
---
## Regles d'associació interessants
+ Per tant,
+ $bolquers \rightarrow cervesa$ té un interès alt,
+ $coke \rightarrow pepsi$ i $pepsi \rightarrow coke$ tenen un interès molt baix (negatiu)
+ $X \rightarrow llet$ té un interès 0.
---
## Exemple: Confiança i 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 d'associació $\{ m, b \} \rightarrow c$ té una confiança 0.5 (hi ha dos casos sobre els quatre possibles) i un interès -0.125 (= 0.5 - 5/8).
---
## Cerca de regles d'associació
+ El problema és *trobar totes les regles d'associació amb suport $\geq s$ i confiança $\geq c$*.
+ El suport de la regla és el suport del conjunt d'ítems de l'esquerra.
+ La part més dura és trobar els conjunts d'ítems més frequents:
+ Si $\{ i_1, i_2, i_3, \dots, i_k \} \rightarrow j$ té suport (1\%) i confiança (50\%) elevats llavors tant $\{ i_1, i_2, i_3, \dots, i_k \}$ com $\{ i_1, i_2, i_3, \dots, i_k, j \}$ seran freqüents.
+ Hem de trobar tots els conjunts d'ítems amb suport alt i després totes les regles d'associació amb suport i interès suficients.
+ Si en conjunt d'ítems freqüents tenim $j$ elements, podem generar $j$ possibles regles.
---
## Model Computacional
+ Típicament les dades (que poden ser un cas de dades massives en el cas d'un supermercat) les tindrem en un fitxer en un o diversos discs, emmagatzemades *per bosses* i hem d'expandir les bosses en parells, tripletes, etc. a mesura que anem llegint les bosses.
+ La implementació ingènua és molt costosa.
---
## Model Computacional Ingenu
```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']]
# segurament hen de llegir les bosses del disc
# de forma seqüencial ...
unics = set()
for bag in bags:
for item in bag:
unics.add(item)
print(unics)
>>> {'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}
```
---
## Model Computacional Ingenu
```python=
parelles = set()
for i in combinations(items, 2):
parelles.add(i)
print(parelles)
>> {('c', 'p'), ('m', 'c'), ('m', 'p'),
('j', 'b'), ('m', 'b'), ('j', 'c'),
('j', 'p'), ('c', 'b'), ('j', 'm'),
('p', 'b')}
# llegir les bosses i comptar ...
```
---
## Model Computacional
+ El cost més important a l'hora de processar aquestes dades és el nombre de lectures/escriptures al disc.
+ A la pràctica, els algorismes que generen regles d'associació llegeixen les dades en *passades* llegint totes les bosses una darrera l'altra.
+ Per tant, mesurarem el cost de l'algorisme pel nombre de passades que fa sobre el conjunt total de les dades.
---
## Model Computacional
+ Per aquests algorismes, l'ús de la memòria principal és el recurs més crític.
+ A mesura que llegim bosses, hem de comptar alguna cosa (com per exemple els cops que apareix una determinada tupla d'ítems).
+ El nombre de coses diferents que podem comptar està limitat per la memòria principal.
---
## Trobant parelles freqüents
+ El problema més dur és normalment el de trobar les parelles més freqüents.
+ Sovint, les parelles freqüents són bastant nombroses. Les tripletes freqüents són molt més rares.
+ Si tenim $n$ elements hi ha $\binom{n}{k} = \frac{n!}{k! (n-k)!}$ possibles conjunts de $k$ elements. Per $n=20$ tenim 190 possibles parelles.
+ La probabilitat de que un conjunt d'ítems sigui freqüent baixa de forma exponencial respecte a la mida del conjunt.
+ Per tant, ens concentrarem en les parelles i després ho estendrem a conjunts més nombrosos.
---
## Un algorisme ingenu
Primera aproximació:
1. Llegim el fitxer un cop i posem a una matriu de $(\# items)^2$ elements el nombre d'ocurrències de cada parella.
2. L'algorisme donarà un error si $(\# items)^2$ excedeix la mida de la memòria.
+ El nombre d'ítems pot ser de l'ordre de 100.000 (en un gran supermercat) o de 10.000.000.000 si parlem de pàgines web.
---
## Com comptar les parelles
Segona aproximació:
+ Emmagatzemar només les tripletes $[i,j,c]$ tals que $count(i,j)=c$, amb $c>0$, en forma de llista o diccionari.
+ Si els enters i els identificadors dels ítems es poden guardar en 4 bytes, en una llista com a mínim necessitem 12 bytes per cada parella.
+ Si ho guardem en un diccionari (amb $[i,j]$ com a clau) necessitarem una mica més de memòria adicional.
---
## Com comptar les parelles
+ Què passa si la majoria de parelles surten alguna vegada?
+ Doncs que necessitarem $12n^2/2$ bytes per guardar-les (si tenim `(i,j)` no cal guardar `(j,i)`) i això només ens permet tenir un nombre d'ítems de l'ordre de milers en un ordinador convencional.
---
## Com comptar les parelles
Tercera aproximació:
+ Podem reduir espai si intentem emmagatzemar tots els $\binom{n}{2}$ comptadors de manera que sigui fàcil trobar-los a memòria donada la parella $(i,j)$, sense haver de guardar $(i,j)$.
+ Representar els ítems amb enters ho simplificarà.
---
## Com comptar les parelles: **Matriu Triagular**
1. Numerem els ítems 1,2,3,...
2. Emmagatzemarem el comptador de $\{i,j\}$ en una **matriu triangular** $A[i,j]$. Amb això estalviem l'espai per guardar els identificadors dels productes i la meitat de la matriu.
---
## Com comptar les parelles
+ De fet, si mantenim els contadors de les parelles en ordre lexicogràfic podem guardar la matriu en una **llista 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)}]$ llavors el comptador de la parella $(i,j)$ està a la posició $A[(i-1)(n-i/2)+j-i]$.
+ El nombre total de parelles és $\frac{n(n-1)}{2}$, que ocupen un total de $2n^2$ bytes (4 bytes per parella).
---
## Com comptar les parelles
+ El mètode de la matriu triangular (4 bytes per parella) és millor que un diccionari (12 bytes per parella) si al menys $\frac{1}{3}$ de les $\binom{n}{2}$ parelles apareix en alguna bossa. Sinó, són millor els diccionaris.
+ Els conjunts de $n>2$ ítems no tenen tant problemes per ser emmagatzemats, normalment n'hi ha molts menys que parelles!
---
## L'algorisme **Apriori**
+ L'algorisme **Apriori** és un mètode que busca conjunts d'ítems freqüents amb molt poques lectures de les dades i fa un ús molt limitat de la memòria.
+ La seves idees principals són:
+ *Monotonia*: Si un conjunt d'ítems apareix al menys $s$ vegades al conjunt, tots els seus possibles subconjunts també apareixen al menys $s$ vegades!
+ Per una altra banda, si un ítem $i$ no apareix a $s$ bosses, llavors cap conjunt que inclogui $i$ pot aparèixer a $s$ bosses.
---
## L'algorisme **Apriori**
<h1><img width="550" src="https://i.imgur.com/4tGHLLM.png"></h1>
---
## L'algorisme **Apriori**
<h1><img width="550" src="https://i.imgur.com/SeS0Hdq.png"></h1>
---
## L'algorisme **Apriori**
+ A la primera passada llegim les bosses, traduïm els ítems a enters i contem a la memòria principal les ocurrències de cada ítem. Aquest procés requereix una part de la memòria proporcional al nombre d'ítems.
+ Després identifiquem els ítems que apareixen al menys $s$ vegades, i per tant són els $m$ **ítems freqüents**.
---
## L'algorisme **Apriori**
+ A la segona passada, llegim les bosses una altra vegada i **comptem només les parelles per les que els dos elements van ser etiquetats com a freqüents a la passada anterior**. Per la propietat de monotonia segur que no perdem cap parella freqüent.
+ Això requereix com a màxim una quantitat de memòria proporcional al quadrat dels ítems freqüents (per guardar els comptadors) $O(m^2)$.
+ També necessita una llista dels $m$ ítems freqüents (per saber què hem de comptar).
---
## L'algorisme **Apriori**
+ Podem fer servir el mètode de la matriu triangular amb un $m$ corresponent al nombre d'ítems freqüents.
+ Per fer-ho, renumerem els ítems freqüents $1,2, \dots$ i mantenim una taula que relaciona els nous nombres amb els identificadors originals dels ítems.
---
## Tripletes, etc.
+ Per construir els conjunts de $k$ ítems a partir dels de $k-1$, construim dos $k$-conjunts (conjunts de mida $k$) a partir dels anteriors:
+ $C_k$ = $k$-conjunts candidats = aquells conjunts que poden ser freqüents, basant-se en la informació de la passada per $k-1$.
+ $L_k$ = el conjunt de $k$-conjunts realment freqüents.
<h1><img width="550" src="https://i.imgur.com/JclfgbJ.png"></h1>
---
## L'algorisme **Apriori** per tots els conjunts d'ítems freqüents
+ Un pas per cada $k$.
+ Necessita espai a la memòria principal per contar cada $k$-conjunt candidat.
+ Per un conjunt de dades típic i un suport raonable (p.e. 1\%), $k=2$ és el pas que necessita més memòria.
---
## Exemple
+ Considerem una base de dades, $D$, amb 9 transaccions.
+ Suposem que el suport mínim és 2.
+ Definim el nivell de confiança mínim com el 70\%.
+ L'objectiu és generar les regles d'associació.
---
## Exemple
|Bossa |Í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 |
---
## Exemple
Pas 1: Crear els 1-conjunts més freqüents.
+ Llegim $D$ per contar cada un dels candidats i creem $C_1$:
|Conjunt |Comptador|
|-----|--------|
I1 | 6 |
I2 | 7 |
I3 | 6 |
I4 | 2 |
I5 | 2 |
---
## Exemple
+ Comparem el suport de cada candidat amb el valor de mínim suport i creem $L_1$:
|Conjunt |Comptador|
|-----|--------|
I1 | 6 |
I2 | 7 |
I3 | 6 |
I4 | 2 |
I5 | 2 |
---
## Exemple
Pas 2: Generar els 2-conjunts més freqüents.
+ Generem els candidats $C_2$ des de $L_1$ i contem quantes vegades apareixen:
|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 |
---
## Exemple
+ Comparem el suport de cada candidat amb el valor de mínim suport i creem $L_2$:
|Conjunt |Comptador|
|-----|--------|
| {I1, I2} | 4 |
| {I1, I3} | 4 |
| {I1, I5} | 2 |
| {I2, I3} | 4 |
| {I2, I4} | 2 |
| {I2, I5} | 2 |
---
## Exemple
Pas 3: Generar els 3-conjunts més freqüents.
+ Generem els candidats $C_3$ des de $L_2$ i contem quantes vegades apareixen:
|Conjunt |Comptador|
|-----|--------|
| {I1, I2, I3} | 2 |
| {I1, I2, I5} | 2 |
+ La generació dels 3-conjunts més freqüents ha fet ús de la propietat de l'algorisme Apriori: $\{I2, I3, I5\}$ no ha estat comptat perquè $\{I3,I5\}$ no hi és a $L_2$.
---
## Exemple
+ Comparem el suport de cada candidat amb el valor de mínim suport i creem $L_3$:
|Conjunt |Comptador|
|-----|--------|
|{I1, I2, I3} | 2 |
|{I1, I2, I5} | 2 |
+ Aquesta propietat també ens diu que cap subconjunt de 4 candidats pot ser freqüent.
---
## Exemple: Regles d'associació
+ Per cada conjunt d'ítems freqüents $I$ generarem tots els subconjunts no buits de $I$.
+ Per cada subconjunt no buit $s$ de $I$ produirem una regla $s \rightarrow \{I-s\}$ si $\frac{suport(I)}{suport(s)} \geq$ confiança-mínima.
+ El resultat final és que hem trobat com a conjunts d'ítems freqüents: $\{I1\}$, $\{I2\}$, $\{I3\}$, $\{I4\}$, $\{I5\}$, $\{I1,I2\}$, $\{I1,I3\}$, $\{I1,I5\}$, $\{I2, I3\}$, $\{I2, I4\}$,$\{I2,I5\}$, $\{I1,I2,I3\}$, $\{I1,I2,I5\}$.
+ Si considerem $\{I1,I2,I5\}$, els seus subconjunt possibles són $\{I1\}$, $\{I2\}$, $\{I5\}$, $\{I1,I2\}$, $\{I1,I5\}$,$\{I2,I5\}$.
---
## Exemple: Regles d'associació
+ Suposem que el nivell mínim de confiança és del 70\%.
+ Les cerca de regles d'associació és:
+ I1 $\wedge$ I2 $\rightarrow$ I5, Confiança=2/4=50\%, regla rebutjada.
+ I1 $\wedge$ I5 $\rightarrow$ I2, Confiança=2/2=100\%, **regla acceptada**.
+ I2 $\wedge$ I5 $\rightarrow$ I1, Confiança=2/2=100\%,**regla acceptada**.
+ I1 $\rightarrow$ I2 $\wedge$ I5, Confiança=2/6=33\%, regla rebutjada.
+ I2 $\rightarrow$ I1 $\wedge$ I5, Confiança=2/7=29\%, regla rebutjada.
+ I5 $\rightarrow$ I1 $\wedge$ I2, Confiança=2/2=100\%,**regla acceptada**.
---
## Altres aplicacions: corredors GPS
<h1><img width="550" src="https://i.imgur.com/aDft0Lm.jpg"></h1>
<sup> Cavallaro, C.; Vitrià, J. Corridor Detection from Large GPS Trajectories Datasets. Appl. Sci. 2020, 10, 5003. https://doi.org/10.3390/app10145003 </sup>
{"metaMigratedAt":"2023-06-16T12:05:08.809Z","metaMigratedFrom":"YAML","title":"El problema dels ítems freqüents","breaks":true,"slideOptions":"{\"theme\":\"white\",\"transition\":\"fade\"}","description":"Dades:","contributors":"[{\"id\":\"27c1cf26-ef2c-44cb-8ae1-2edc488d3f8e\",\"add\":28142,\"del\":9960},{\"id\":\"d3f4e25d-9d42-454a-a199-9786f0e31195\",\"add\":17449,\"del\":17449}]"}