Post on 15-Jul-2020
Esercizi
Esercitazione Data Mining
Esercizio 1
� Sia dato il seguente dataset
x y z U
0 0 1 0
1 1 1 01 1 1 0
1 0 0 1
0 1 1 0
0 0 1 0
0 1 0 1
1 0 1 1
1 1 0 1
1 1 1 0
1 0 1 1
Esercizio 1 (punto a)
� Utilizzando l’algoritmo Naive Bayes,
� Nell’ipotesi in cui le variabili x,y,z siano discrete binarie, calcolare P(U=0|x = 1,y=0,z=1).
Soluzione:� Soluzione:
)1,0,1(
)0(*)0|1,0,1(
========
zyxP
UPUzyxP
)1(*)1|1,0,1()0(*)0|1,0,1(
)0(*)0|1,0,1(
=====+==========
UPUzyxPUPUzyxP
UPUzyxP
P(U=0|x=1,y=0,z=1)=
Esercizio 1
1*5/2*5/2)0|1(*)0|0(*)0|1()0|1,0,1( ============ UzPUyPUxPUzyxP
5/2*5/3*5/4)1|1(*)1|0(*)1|1()1|1,0,1( ============ UzPUyPUxPUzyxP
[ ] 10/5*1*5/2*5/2 08.0[ ][ ] 10/5*]5/2*5/3*5/4[10/5*1*5/2*5/2
10/5*1*5/2*5/2
+ 096.008.0
08.0
+= = 0.454;
Esercizio 1 (punto b)
� Utilizzando l’algoritmo Naive Bayes,
� Nell’ipotesi in cui x e y siano discrete binarie e z continua, calcolare la classificazione ottimale per x=1,y=0,z=1.
� Soluzione:
Z è continua: usiamo una distribuzione gaussiana di media µ e � Z è continua: usiamo una distribuzione gaussiana di media µ e
varianza σ2 .
y
Esercizio 1
� Calcoliamo P(z=1|U=0) e P(z=1|U=1):
� se U=0 -> µ = 1 e σ2 = 0
� -> P(z=1|U=0) = 1;
� se U=1 -> µ = 0.4 e σ2 = = 0.24 applicando la formula della densità con z=1 5
34.026.0 22 ⋅+⋅
� -> P(z=1|U=1) = 0.3854;
� v0 = P(0)*[P(x=1|U=0)*P(y=0|U=0)*P(z=1|U=0)] = 0,08
� v1 = P(1)*[ P(x=1|U=1)*P(y=0|U=1)*P(z=1|U=1)] = 0,0926
Esercizio 2
� In riferimento al dataset presentato nell’esercizio 1:
� nell’ipotesi in cui tutte le variabili siano discrete binarie, apprendere l’albero di decisione basato sul guadagno informativo.
Soluzione: � Soluzione:
� Calcoliamo, innanzi tutto il primo attributo sul quale fare split. Usando come criterio, l’Information Gain, otteniamo:
Esercizio 2
� H(D): [5+,5-], H(X0): [1+,3-] e H(X1): [4+,2-].
� H(D) = 1
� H(X0) = -1/4*log2(1/4)-3/4*log2(3/4) = 0.8113
� H(X1) = -4/6*log2(4/6)-2/6*log2(2/6) = 0.9183
� Gain (D, x) = H(D) – (4/10)*H(X0)-(6/10)*H(X1) = 1-(4/10)*0.8113-� Gain (D, x) = H(D) – (4/10)*H(X0)-(6/10)*H(X1) = 1-(4/10)*0.8113-(6/10)*0.9183 = 0.124;
� Analogamente:� Gain (D, y) = 0.029 e Gain (D, z) = 0.514.
� Quindi il primo attributo su cui fare split è z.
� Ripetendo gli stessi calcoli sulle rimanenti tuple (ripulite dell’attributo z), otteniamo il seguente albero di classificazione:
Esercizio 2
Esercizio 3
� Si applichi, al dataset dell’esercizio 1, l’algoritmo 2-Means all’intero dataset, ignorando l’attributo di classe U, utilizzando la distanza euclidea e la distanza di Jaccard.
Soluzione:� Soluzione:
� Distanza Euclidea
� Supponiamo di avere il seguente assegnamento iniziale:
� C1 = {x1,x2,x3,x4,x5} C2 = {x6,x7,x8,x9,x10}.
� I centroidi dei clusters saranno:
� Ce1= [2/5, 2/5, 4/5] e Ce2 = [4/5, 3/5, 3/5].
Esercizio 3
� Iterazione1
C1 C2
X1 0.6 * 1.07
X2 1.03 0.6 *X2 1.03 0.6 *
X3 0.842 * 0.871
X4 0.938 * 0.979
X5 0.824 * 1.07
X6 0.824 * 1.07
X7 0.938 0.748 *
X8 0.938 0.748 *
X9 1.03 0.6 *
X10 0.938 0.748 *
Esercizio 3
� Pertanto i nuovi clusters saranno:
� C1={x1,x3,x4,x5,x6} e C2={x2,x7,x8,x9,x10}
� E i nuovi centroidi:
� Ce1 = [1/5, 2/5, 3/5] e Ce2 = [1, 3/5, 4/5].
� A questo punto si reitera l’algoritmo.
Esercizio 3
� Iterazione 2
C1 C2
X1 0.748 * 1.41
X2 1.07 0.44 *
X3 1.07 1 *
X4 0.748 0.44 *
X5 0.6 * 1.18
X6 0.871 * 1.34
X7 0.979 0.632 *
X8 1.16 0.894 *
X9 1.07 0.447 *
X10 0.979 0.632 *
Esercizio 3
� I clusters saranno:
� C1 = {x1,x5,x6} e C2 = {x2,x3,x4,x7,x8,x9,x10}
� I centroidi saranno quindi:
� Ce1 = [0,0.33,0.66] e Ce2 = [0.857,0.571,0.714]
Esercizio 3
� Iterazione 3
C1 C2
X1 0.473 * 1.06
X2 1.25 0.535 *X2 1.25 0.535 *
X3 1.242 0.925 *
X4 0.751 * 1
X5 0.473 * 1.06
X6 0.940 * 1.195
X7 1.106 0.654 *
X8 1.372 0.845 *
X9 1.25 0.535 *
X10 1.106 0.654 *
Esercizio 3
� I cluster sono:� C1 = {x1,x4,x5,x6} e C2 = {x2,x3,x7,x8,x9,x10}
� I centroidi sono:� Ce1 = [0,0.5,0.75] e Ce2 = [1,0.5,0.66]
� L’algoritmo continua ad iterare finchè non si raggiunge la condizione di stop (i centroidi non cambiano più).
� Distanza di Jaccard
� Dist J =
� Il procedimento dell’algoritmo è identico al passo precedente
yxyx
yx
•−+
•22
Esercizio 4
� Prendendo in considerazione il dataset dell’ esercizio 1 e assumendo un supporto del 30% e una confidenza dell’80%,
� Calcolare gli itemset frequenti unidimensionali trasformando il dataset in formato transazionale;dataset in formato transazionale;
� Calcolare le regole associative a partire dagli itemset frequenti calcolati nel primo punto.
Esercizio 4 (primo punto)
� Soluzione:
� Trasformiamo il dataset in formato transazionale e applichiamo Apriori per il calcolo degli itemsets
TID Items
T1 z
T2 xyzcalcolo degli itemsets frequenti. T3 xu
T4 yz
T5 z
T6 yu
T7 xzu
T8 xyu
T9 xyz
T10 xzu
Esercizio 4
� Apriori
L1 C2 L2 C3 L3x:6 xy xy :3 xyz xyz:2*x:6 xy xy :3 xyz xyz:2*y:5 xz xz :4 xyu**z:7 xu xu:4 xzu**u:5 yz yz:3
yu yu:2*zu zu:2*
� (*) Non raggiungono il supporto� (**) Proprietà Apriori
Esercizio 4
� Gli itemsets frequenti sono, quindi:
� F = {x,y,z,u,xy,xz,xu,yz}
Esercizio 4 (secondo punto)
� Le regole associative sono :
Rule Confidence
x->y 1/2y->x 3/5
� L’unica regola che supera la soglia di confidenza fissata è : u->x
y->x 3/5x->z 2/3z->x 4/7x->u 2/3u->x 4/5y->z 3/5z->y 3/7
Esercizio 5
� Si consideri il seguente dataset:
A B C3 1 X4 2 X4 1 X4 1 X3 2 X
12 1 Y13 2 Y13 3 Y18 7 X16 8 X18 9 X23 7 Y23 8 Y24 9 Y
Esercizio 5
� Considerando C come attributo di classe ed A e B come variabili numeriche continue, calcolare l’entropia del dataset e costruire due alberi di decisione:� Discretizzando A e B.
� Assumendo A e B come attributi numerici.� Assumendo A e B come attributi numerici.
� Motivare il metodo di discretizzazione scelto e discutere le differenze fra i due alberi generati.
Esercizio 5
ID A B C1 3 1 X2 4 2 X3 4 1 X4 3 2 X4 3 2 X5 12 1 Y6 13 2 Y7 13 3 Y8 18 7 X9 16 8 X10 18 9 X11 23 7 Y12 23 8 Y13 24 9 Y
Esercizio 5
� L’entropia dell’intero Dataset è 0.9957.
� Si discretizzano A e B secondo i seguenti criteri:
AMB=Molto Basso (X<10)B=Basso (10<=X<15)M=Medio (15<=X<20)A=Alto (20<=X<25)
BB=Basso (X<5) A=Alto (X>=5)
Esercizio 5ID A B C
1 MB B X
2 MB B X
3 MB B X
4 MB B X4 MB B X
5 B B Y
6 B B Y
7 B B Y
8 M A X
9 M A X
10 M A X
11 A A Y
12 A A Y
13 A A Y
Esercizio 5
� L’albero di decisione è (banalmente) il seguente:
Esercizio 5
� Nell’altro caso invece, occorre scegliere l’attributo su cui splittare.
� Lo split sull’attributo A garantisce un maggior guadagno informativo rimane però da stabilire la guadagno informativo rimane però da stabilire la soglia per lo split.
� Visto che A assume 8 valori diversi possiamo scegliere fra 7 soglie diverse.
� Tramite la seguente tabella calcoliamo il guadagno informativo correlato allo split sulle varie soglie
Esercizio 5
A
< >= < >= < >= < >= < >= < >= < >=
X 2 5 4 3 4 3 4 3 5 2 7 0 7 0
Y 0 6 0 6 1 5 3 3 3 3 3 3 5 1
18 23 244 12 13 16
Y 0 6 0 6 1 5 3 3 3 3 3 3 5 1
G 0,1546 0,36 0,1307 0,0037 0,0349 0,3178 0,0912
� Risulta conveniente splittare il dataset distinguendo fra valori di A<12 e valori di A>=12.
Esercizio 5
� A questo punto splittiamo su B.
B< >= < >= < >= < >= < >=
X 0 3 0 3 0 3 1 2 2 1Y 1 5 2 4 3 3 4 2 5 1G
9
0,0699 0,152 0,2516 0,0728 0,0248
2 3 7 8
� Risulta conveniente splittare il dataset distinguendo fra valori di B<7 e valori di B>=7.
G 0,0699 0,152 0,2516 0,0728 0,0248
Esercizio 5
� L’ultimo split viene fatto nuovamente su A, la scelta della soglia è banale.
Esercizio 6
� Sia dato il seguente dataset:
ID OPL_HIGH STRUCKOPEN_DOO
R PUSHED HIT PARKED COLLITION CLASS
1 0 0 0 0 0 1 1 0
2 0 0 0 0 0 0 1 0
3 0 1 0 1 0 0 1 03 0 1 0 1 0 0 1 0
4 0 0 1 0 1 0 1 0
5 1 1 1 0 0 1 1 0
6 0 0 0 0 0 1 1 0
7 1 0 0 0 0 0 0 0
8 0 0 0 1 0 0 0 0
9 1 1 0 1 0 0 1 1
10 0 0 0 0 1 1 0 1
11 0 0 0 0 1 1 1 1
12 1 0 0 0 0 0 1 1
13 1 1 0 0 0 0 1 1
14 1 1 1 0 0 0 1 1
Esercizio 6
� Vengono appresi due classificatori, che producono le seguenti probabilità per CLASS=1:
� Considerando la soglia di classificazione 0.5, produrre la matrice di confusione e disegnare i punti sul piano ROC. Qual è il classificatore migliore?
Esercizio 6
� Matrice di Confusione per C1
real/predicted 0 10 6 21 1 51 1 5
� Matrice di Confusione per C2
real/predicted 0 10 8 01 1 5
Esercizio 6
� C1:
� TPR = 5/6 ; FPR = ¼
� C2:
� TPR = 5/6 ; FPR = 0
1
1
5/6
Esercizio 7
� Si consideri il seguente reticolo in cui è rappresentato il bordo
della frequenza
Esercizio 7
� Secondo l’algoritmo apriori, quali sono gli itemsets candidati di dimensione 2, e quali di questi sono frequenti?
� Soluzione:
� 2-Itemsets candidati {AB, AC, AD, BC, BD, CD }
� 2-Itemsets Frequenti {AB, AC, AD, BC, BD, CD }
Esercizio 7
� Secondo l’algoritmo apriori, quali sono gli itemsets candidati di dimensione 4, e quali di questi sono frequenti?
� Soluzione:
� 4-Itemsets Candidati {ABCD}
� 4-Itemsets Frequenti {}