Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · X 2 5 4 3 4 3 4 3 5 2 7 0 7 0 Y...

57
Esercizi Esercitazione Data Mining

Transcript of Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · X 2 5 4 3 4 3 4 3 5 2 7 0 7 0 Y...

Page 1: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizi

Esercitazione Data Mining

Page 2: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

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

Page 3: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

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)=

Page 4: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

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;

Page 5: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

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

Page 6: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

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.022

⋅+⋅

� -> 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

Page 7: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

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:

Page 8: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

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:

Page 9: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 2

Page 10: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

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].

Page 11: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

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 *

Page 12: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

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.

Page 13: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

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 *

Page 14: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

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]

Page 15: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

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 *

Page 16: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

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

Page 17: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

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.

Page 18: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 4

� 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

Page 19: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

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

Page 20: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 4

� Apriori

L1x:6y:5y:5z:7u:5

� (*) Non raggiungono il supporto� (**) Proprietà Apriori

Page 21: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 4

� Apriori

L1 C2x:6 xyy:5 xzy:5 xzz:7 xuu:5 yz

yuzu

� (*) Non raggiungono il supporto� (**) Proprietà Apriori

Page 22: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 4

� Apriori

L1 C2 L2x:6 xy xy :3y:5 xz xz :4y:5 xz xz :4z:7 xu xu:4u:5 yz yz:3

yu yu:2*zu zu:2*

� (*) Non raggiungono il supporto� (**) Proprietà Apriori

Page 23: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 4

� Apriori

L1 C2 L2 C3x:6 xy xy :3 xyzy:5 xz xz :4 xyu**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

Page 24: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 4

� Apriori

L1 C2 L2 C3 L3x:6 xy xy :3 xyz xyz:2*y:5 xz xz :4 xyu**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

Page 25: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 4

� Gli itemsets frequenti sono, quindi:

� F = {x,y,z,u,xy,xz,xu,yz}

Page 26: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 4 (secondo punto)

� Le regole associative sono :

Rule Confidence

x->y 1/2

y->x 3/5

� L’unica regola che supera la soglia di confidenza fissata è : u->x

y->x 3/5

x->z 2/3

z->x 4/7

x->u 2/3

u->x 4/5

y->z 3/5

z->y 3/7

Page 27: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 5

� Si consideri il seguente dataset:

A B C

3 1 X

4 2 X

4 1 X4 1 X

3 2 X

12 1 Y

13 2 Y

13 3 Y

18 7 X

16 8 X

18 9 X

23 7 Y

23 8 Y

24 9 Y

Page 28: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

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.

Page 29: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 5

ID A B C

1 3 1 X

2 4 2 X

3 4 1 X

4 3 2 X4 3 2 X

5 12 1 Y

6 13 2 Y

7 13 3 Y

8 18 7 X

9 16 8 X

10 18 9 X

11 23 7 Y

12 23 8 Y

13 24 9 Y

Page 30: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

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)

Page 31: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

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

Page 32: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 5

� L’albero di decisione è (banalmente) il seguente:

Page 33: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

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

Page 34: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

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.

Page 35: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 5

� A questo punto splittiamo su B.

B

< >= < >= < >= < >= < >=

X 0 3 0 3 0 3 1 2 2 1

Y 1 5 2 4 3 3 4 2 5 1

G

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

Page 36: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 5

� L’ultimo split viene fatto nuovamente su A, la scelta della soglia è banale.

Page 37: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 6

� Sia dato il seguente dataset:

ID OPL_HIGH STRUCK

OPEN_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

Page 38: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

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?

Page 39: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 6

� Matrice di Confusione per C1

real/predicted 0 1

0 6 2

1 1 51 1 5

� Matrice di Confusione per C2

real/predicted 0 1

0 8 0

1 1 5

Page 40: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 6

� C1:

� TPR = 5/6 ; FPR = ¼

� C2:

� TPR = 5/6 ; FPR = 0

1

1

5/6

Page 41: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 7

� Si consideri il seguente reticolo in cui è rappresentato il bordo

della frequenza

Page 42: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 7

� Secondo l’algoritmo apriori, quali sono gli itemsets candidati di dimensione 2, e quali di questi sono frequenti?

Soluzione:Soluzione:

2-Itemsets candidati {AB, AC, AD, BC, BD, CD } 2-Itemsets Frequenti {AB, AC, AD, BC, BD, CD }

Page 43: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 7

� Secondo l’algoritmo apriori, quali sono gli itemsets candidati di dimensione 4, e quali di questi sono frequenti?

Soluzione:Soluzione:

4-Itemsets Candidati {ABCD}4-Itemsets Frequenti {}

Page 44: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 8

� Determinare tutti gli itemset frequenti nel seguente database usando l’algoritmo FP-Growth. Si consideri un supporto pari al 30%.

Page 45: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 8

� Soluzione:

� Generiamo la F-List andando a selezionare gli itemset di lunghezza 1:gli itemset di lunghezza 1:

Item Frequenza

B 6

D 6

A 5

E 4

C 3

Page 46: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 8� Costruiamo l’FP-TREE

{ }

� Qual è il prossimo nodo?

F-List: B:6;D:6;A:5;E:4;C:3

Page 47: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 8� Costruiamo l’FP-TREE

{ }

B:6

Page 48: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 8� Costruiamo l’FP-TREE

{ }

B:6

D:4

Page 49: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 8� Costruiamo l’FP-TREE

{ }

B:6

D:4

A:3

Page 50: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 8� Costruiamo l’FP-TREE

{ }

B:6

D:4

A:3

E:2

Page 51: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 8� Costruiamo l’FP-TREE

{ }

B:6

D:4

A:3

E:2

C:1

Qual è il prossimo ramo?

Page 52: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 8� Costruiamo l’FP-TREE

{ }

B:6

D:4

A:3

E:2

C:1

A:1

Page 53: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 8� L’FP-TREE finale è il seguente:

{ }B:6

D:4

A:3

E:2

C:1

A:1

E:1

C:1

C:1 D:2

A:1

E:1

Page 54: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 8

� Conditional pattern base per C:3

� BDAE: 1; B: 1; BAE: 1

� F-list: � F-list:

� B:3

� Conditional FP-tree for C

� B: 3

� Frequent patterns

� C:3, BC:3

Page 55: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 8

� Conditional pattern base for E:4

� BDA: 2; BA:1; DA:1

� F-list: A:4, B:3, D:3

� Conditional FP-tree for E

� Passo Ricorsivo

� Conditional pattern base for DE:3

� A:1, AB:2

� Conditional FP-tree for DE

A:3 � Conditional FP-tree for E

Null

|

A:4 ---- D:1

|

B:3

|

D:2

� A:3

� Frequent patterns

� DE:3, ADE:3

Page 56: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esecizio 8

� Conditional pattern base for BE:3

� A:3

� Conditional FP-tree for BE � Conditional FP-tree for BE

� A:3

� Frequent patterns

� BE:3, ABE:3

Page 57: Esercizi - CNRstaff.icar.cnr.it/manco/Teaching/datamining/wp... · 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 4 12 13 16 18 23 24 G 0,1546 0,36 0,1307 0,0037 0,0349

Esercizio 8

� Conditional pattern base for AE:4 � NULL

� Conditional FP-tree for AE � NULL � NULL

� Frequent patterns

� AE:4 , E:4

� Si continua così fino alla generazione di tutti i frequent pattern…