1

Università degli Studi di Bari “Aldo Moro”

Comparazione tra due Sistemi di Apprendimento

Esame di:

Intelligenza Artificiale

Studente: Luigi Accetta

2

Indice 1 Introduzione……………………………………………………………………………………….3 1.1 Breve descrizione di C4.5 ………….………………………………………………………….3 1.2 Breve descrizione di ITI………………………………………………………………………..4 1.3 Scelta dei Dataset………………………………………………………………………………4 1.3.1 Caratteristiche di Contraceptive Method Choise dataset………………………………...4 1.3.2 Caratteristiche di Credit Approval dataset……………………………………………….5 2 Elaborazione dei dataset………………………………………………………………………….7 2.1 Metodo di campionamento usato……………………………………………………………..7 2.2 Configurazione dei dataset per C4.5 e Iti……………………………………………………..7 3 Analisi e Test Statistico utilizzato………………………………………………………………..8 3.1 Contraceptive Method Choise dataset ………………………………………………………..8 3.1.1 Stima dei dati per c4.5…………………………………………………………………...8 3.1.2 Stima dei dati per Iti…………………………………………………………………….12 3.1.3 Test delle ipotesi………………………………………………………………………...15 3.2 Credit Approval dataset …………………….………………………………………………..17 3.2.1 Stima dei dati per C4.5…………………………………………………………………..18 3.2.2 Stima dei dati per Iti……………………………………………………………………..21 3.2.3 Test delle Ipotesi………………………………………………………………………...24 4 Conclusioni……………………………………………………………………………………….27

3

1 Introduzione La seguente relazione presenta una descrizione dettagliata del processo usato per il confronto tra due sistemi di apprendimento automatico applicati a due dataset differenti. I sistemi considerati sono stati:

1) C4.5. 2) ITI.

Di seguito verranno mostrati sia i risultati in output generati per ogni dataset, sia le metologie e test statistici usati per formulare una data ipotesi. L’obiettivo è stato ricercare differenze significative tra i due sistemi scelti. 1.1 Breve descrizione di C4.5

Come accennato in precedenza, gli algoritmi di machine learning scelti per il confronto sono stati C4.5 e Iti. C4.5 è un algoritmo usato per generare alberi di decisione sviluppato da Ross Quinlan ed è un estensione di un sistema precedente ID3. Questo sistema è spesso usato come un classificatore statistico dato che può essere usato per la classificazione. C4.5 costruisce alberi di decisione partendo da un set di traning data usando il concetto di information entropy ( misura di incertezza associata ad una variabile random).

I dati di training sono definiti come un set S = s1,s2,... di esempi già classificati. Ogni esempio si = x1, x2 è un vettore dove x1,x2,... rappresentano gli attributi o le caratteristiche di un dato esempio. I dati di training sono definiti come un vettore C = c1, c2, c3 dove questi valori rappresentano la classe a cui ogni esempio appartiene. Ad ogni nodo dell’albero, C4.5 sceglie un attributo dei dati che divide più efficacemente il suo set di campioni in un sottoinsieme completo per una determinata classe. Questo sistema si basa sul criterio di guadagno di informazioni normalizzato ( differenza di entropia) derivato proprio dalla scelta di un attributo per dividere i dati. L’attributo con il più alto guadagno di informazioni normalizzato è scelto per generare una regola di decisione. Questo criterio è applicato ricorsivamente per ogni sottoinsieme definito.

Algoritmo in pseudo-codice:

1) Verifica la presenza di casi base (nodi di partenza) 2) Per ogni attributo a: trova il guadagno di informazione normalizzata da assegnare ad a. 3) Sia a l’attributo con il maggior guadagno di informazione normalizzata. 4) Creare un nodo di decisione che si divide su a. 5) Utilizza le sottoliste ottenute dividendo il nodo a, per aggiungere figli al nodo.

4

1.2 Breve descrizione di ITI

Questo sistema genera alberi di decisione incrementalmente. Alberi di decisione incrementali sono costruiti utilizzando metodi che consentono ad un albero esistente di essere aggiornato o corretto per mezzo di nuove istanze di dati individuali. Questo è utile in varie situazioni:

a) L'intero set di dati non è disponibile nel momento in cui viene costruito l'albero originale.

b) Il set di dati originale è troppo grande per il processo.

c) le caratteristiche dei dati cambiano nel tempo.

Iti, nello specifico, costruisce alberi di decisione automaticamente da esempi già definiti. Come descritto in precedenza, generando alberi incrementalmente, Iti permette di rivedere un albero costruito precedentemente senza doverlo costruire necessariamente da zero. Gestisce variabili simboliche, numeriche e valori mancanti e presenta anche un sistema di pruning (potatura dell’albero).

1.3 Scelta dei Dataset

I dataset utilizzati per testare i due algoritmi sono:

Contracpetive Method Choise Credit approval

La scelta di questi due dataset è stata dettata da vari motivi:

La presenza di attributi di diverso formato per garantire un test più completo possibile. La diversa dimensione dei dataset per testare le prestazioni dei sistemi in termini di

consumo di cpu e tempo impiegato per l’esecuzione. Un formato dei dati facilmente modificabile e già compatibile con i sistemi da testare. Similarità tra i dataset scelti in termini di tipologia di attributi.

1.3.1 Caratteristiche di Contraceptive Method Choise dataset

Informazioni Pertinenti:

Questo dataset è un sottoinsieme di dati prelevati dal National Indonesia Contraceptive Prevalence Survey, nell’anno 1987. I campioni scelti sono: donne sposate incinta donne sposate non incinta. donne con gravidanza incerta al momento del colloquio.

5

Il problema è quello di prevedere la scelta del metodo contraccettivo tenendo conto di alcune caratteristiche demgratiche e socio-economiche di una donna (senza impiego, lavoro full-time, lavoro part-time).

Numero di istanze: 1473

Numero di attributi: 10 (tra cui l'attributo di classe)

Informazioni sugli attributi: 1. Età moglie (numerica). 2. Titolo di studio moglie (categorica) 1 = basso, 2, 3, 4 = alto 3. Titolo di studio marito (categorica) 1 = basso, 2, 3, 4 = alto 4. Numero di bambini già nati (numerica) 5. Orientamento religioso moglie (binario) 0 = Non-Islam, 1 = Islam 6. Orario di lavoro moglie (Binario) 0 = Si, 1 = No 7. occupazione marito (categorico) 1, 2, 3, 4 8. Tenore di vita standard (categorico) 1 = basso, 2, 3, 4 = alto 9. Media esposizione (binario) 0 = Buono, 1 = Non va bene 10. metodo contraccettivo utilizzato (attributo class) 1 = No-uso 2 = a lungo termine 3 = a breve termine

I valori degli attributi mancanti: Nessuno

1.3.2 Credit Approval Dataset

Informazioni pertinenti: Questo dataset raccoglie varie transizioni di carte di credito. Tutti i nomi degli attributi ed i valori sono stati modificati con simboli privi di significato per proteggere la privacy dei dati. Questo dataset è interessante perché c'è un buon mix di attributi: continui, nominali e numerici. Ci sono anche alcuni valori mancanti.

Numero di istanze: 690

Numero di attributi: l'attributo class 15 +

Informazioni sugli attributi: A1: b, a. A2: continuo. A3: continuo. A4: u, y, l, t.

6

A5: g, p, gg. A6: c, d, cc, i, j, k, m, r, q, w, x, e, AA, ff. A7: v, h, bb, j, n, z, dd, ff, o. A8: continuo. A9: t, f. A10: t, f. A11: continuo. A12: t, f. A13: g, p, s. A14: continuo. A15: continuo. A16: +, - (attributo class)

Missing valori di attributo: 37 casi (5%) hanno uno o più valori mancanti. I valori mancanti sono in particolare degli attributi: A1: 12 A2: 12 A4: 6 A5: 6 A6: 9 A7: 9 A14: 13

Classe di distribuzione: +: 307 (44,5%) -: 383 (55,5%)

7

2 Elaborazione dei Dataset Entrambi i dati set scelti sono stati stati scaricati in un formato compatibile solo per c4.5 e sono state necessarie alcune modifiche per essere caricati anche all’interno di Iti. Inoltre, in base al metodo di campionamento scelto è stato necessario organizzare i training set in più cartelle differenti in modo da evitare errori di esecuzione sia per C4.5 che per Iti. 2.1 Metodo di Campionamento scelto Data la numerosità abbastanza elevata dei training set scelti è stato scelto il metodo di campionamento della k-cross validation che consiste nella suddivisione del dataset totale in k parti e, ad ogni passo, la parte (1/k)-esima del dataset viene ad essere il validation dataset, mentre la restante parte costituisce il training dataset. Così, per ognuna delle k parti (di solito k = 10) si allena il modello, evitando quindi problemi di overfitting ( nel caso in cui un modello statistico si adatti troppo ai dati osservati), ma anche di campionamento asimmetrico del training dataset, tipico della suddivisione del dataset in due sole parti (ovvero training e validation dataset). 2.2 Configurazione dei dataset per C4.5 e Iti Entrambi i sistemi sono stati eseguiti in ambiente Unix e ognuno di questi dataset sono stati organizzati in 10 sottocartelle ( create appositamente per il tipo di campionamento scelto) comprendenti rispettivamente per C4.5 :

fold_num.data // indica il dataset di training scelto per la cross-validation fold_num.test // indica il dataset di test associato al training set fold_num.names // descrive gli attributi di uno specifico Shot

Per Iti:

fold_num.data // indica il dataset di training scelto per per la cross-validation Test. data // indica il dataset di test associato al training set Names // // descrive gli attributi di uno specifico Shot

Sia per C4.5 che per Iti sia è pensato di creare 10 cartelle distinte per ogni Shot per evitare di confondere i file scelti per l’esecuzione. Questa operazione è risultata molto utile per Iti che non permette di leggere file rinominati diversamente da Names.

8

3 Analisi e Test Statistico utilizzato Per ognuno dei dataset scelti è stato effettuato un test statistico con l’obiettivo di evidenziare differenze statisticamente significative tra i due sistemi di apprendimento scelti. Il test che verrà utilizzato sarà il Test di Mann-Withney, un test non parametrico, dato che non si conosce la distribuzione dei dati ( nel caso di distribuzione normale dei dati sarebbe stato utilizzato un test parametrico equivalente). Per quanto riguarda il carattere, ovvero il tipo di dati su cui si è stato effettuato lo studio statistico, ci si è trovati di fronte a dati di tipo:

Quantitativo esprime una quantità ovvero dei valori numeri e comprende 1. Quantitativo discreto che assume una quantità finita o numerabile di valori (es.

Numero figli) 2. Quantitativo continuo che esprime una quantità non numerabile ma continua di

valori, che cioè possono assumere tutti i valori intermedi di un intervallo (es. A2, A3, ecc).

Qualitativo esprime una qualità ovvero dei valori non numerici

1. Qualitativo ordinale assume valori che posseggono naturalmente un ordine, ovvero che possono essere disposti lungo una scala ( es. Tenore di vita standard)

2. qualitativo nominale assume valori che non posseggono alcune ordine (es. metodo contraccettivo utilizzato)

Come tool è stato utilizzato R, un software statistico gratuito che mette a disposizione anche delle funzioni grafiche molto interessanti associate ad ogni specifico test statistico.

3.1 Contraceptive Method Choise dataset in C4.5 Questo dataset presenta 1473 istanze suddivise in dieci fold ognuno dei quali aventi le seguenti dimensioni:

Fold1: 146 istanze Fold2: 147 istanze Fold3: 147 istanze Fold4: 147 istanze Fold5: 147 istanze Fold6: 147 istanze Fold7: 147 istanze Fold8: 148 istanze Fold9: 148 istanze Fold10: 149 istanze

9

Ogni fold è stato utilizzato come test-set e le rimanenti istanze come trainig-set. 3.2 Stima dei Dati per c4.5 Le informazioni utili per valutare la qualità del sistema che vengono state prese in considerazione sono:

Numero di foglie generate nell’albero di decisione. Percentuale di errore commesso nella classificazione delle istanze di test. Accuracy media di classificazione. Tempo di esecuzione e consumo di cpu impiegato per la generazione dell’albero.

Per stimare l’ultimo parametro è stato utilizzato per entrambi i sistemi il comando TIME in linux che fornisce in output il tempo di esecuzione di un comando diviso in real ( tempo effettivo di esecuzione dal momento dell’avvio del comando), user ( tempo utente) sys( e tempo di sistema). Anche se Iti già fornisce un output che mostra il tempo impiegato in termini di cpu, si è preferito applicare questo comando ad entrambi i sistemi e valutare il parametro real per avere una stima più precisa del tempo impiegato da entrambi. Tornando a C4.5, per quanto riguarda l’accuracy questa è stata calcolata nel modo seguente:

Il calcolo effettuato è riferito al fold 1 ottenuto nella classificazione, la accuracy media è stata ottenuta dividendo il numero delle istanze corrette della classe per il numero di istanze totali e facendo la media aritmetica. Di seguito viene mostrato un tipico risultato ottenuto in output: Evaluation on training data (1324 items): Before Pruning After Pruning ---------------- --------------------------- Size Errors Size Errors Estimate 629 255(19.3%) 251 377(28.5%) (42.1%) << Evaluation on test data (149 items): Before Pruning After Pruning ---------------- --------------------------- Size Errors Size Errors Estimate 629 75(50.3%) 251 76(51.0%) (42.1%) Mediante la K-cross validation viene caricato il validation set costituito da 149 istanze mentre le restanti 1324 costituiscono il training set. Altri valori visualizzati sono le foglie generate dell’albero

10

e la stima d’errore durante la classificazione (prima e dopo il pruning). Di seguito verranno elencati gli output legati a tutti e dieci i fold. c4.5 fold 1 (a) (b) (c) <-classified as accuracy ---- ---- ---- 36 8 18 (a): class 1 58,06 6 12 15 (b): class 2 36,36 17 9 25 (c): class 3 49,01 fold2 (a) (b) (c) <-classified as accuracy ---- ---- ---- 41 5 17 (a): class 1 65,07 9 16 8 (b): class 2 48,48 15 13 23 (c): class 3 45,09 fold3 (a) (b) (c) <-classified as accuracy ---- ---- ---- 39 7 17 (a): class 1 61,90 10 12 11 (b): class 2 36,36 19 10 22 (c): class 3 43,13 fold4 (a) (b) (c) <-classified as accuracy ---- ---- ---- 31 10 22 (a): class 1 49,20 6 14 13 (b): class 2 42,42 16 8 27 (c): class 3 52,94 fold5

11

(a) (b) (c) <-classified as accuracy ---- ---- ---- 39 10 14 (a): class 1 61,90 11 13 9 (b): class 2 39,39 13 13 25 (c): class 3 49,01 fold 6 (a) (b) (c) <-classified as accuracy ---- ---- ---- 38 4 21 (a): class 1 60,31 9 9 15 (b): class 2 27,27 17 11 23 (c): class 3 45,09 fold 7 (a) (b) (c) <-classified as accuracy ---- ---- ---- 40 7 16 (a): class 1 63,49 8 13 12 (b): class 2 39,39 19 8 24 (c): class 3 47,05 fold 8 (a) (b) (c) <-classified as accuracy ---- ---- ---- 34 7 22 (a): class 1 53,96 8 14 12 (b): class 2 41,17 17 3 31 (c): class 3 60,78 fold 9 (a) (b) (c) <-classified as accuracy ---- ---- ---- 33 6 24 (a): class 1 52,38 9 11 14 (b): class 2 32,35 13 7 31 (c): class 3 60,78 fold 10 (a) (b) (c) <-classified as accuracy ---- ---- ---- 30 14 19 (a): class 1 47,61 10 15 9 (b): class 2 44,11 10 14 28 (c): class 3 53,84

12

Viene mostrata una tabella riepilogativa con i dati ottenuti per ogni fold e una media per ogni parametro considerato. fold foglie Accuratezzac4.5 tempo

1 211 50 0,09

2 271 54,41 0,09

3 313 49,65 0,1

4 231 48,97 0,08

5 273 52,38 0,11

6 217 47,61 0,07

7 203 52,38 0,1

8 265 53,37 0,09

9 253 50,67 0,11

10 251 49 0,1

Media 248,8 50,844 0,09

3.1.2 Stima dei dati per Iti

E’ stato eseguito lo stesso processo per Iti, per questo sistema sono stati valutati i seguenti parametri:

Numero di foglie dell’albero generato. Accuracy complessiva. Tempo di esecuzione.

Un esempio di output è il seguente:

ITI 3.10 - (C) Copyright, U. of Massachusetts, 23 March 2001, All Rights Reserved Loading variable names ... 9 loaded

13

Loading training set from ./Scrivania/ai/apprendimento/ITI/umass/data/cmc1/shot.data ... 1327 loaded Building tree: Tree built Loading testing set from ./Scrivania/ai/apprendimento/ITI/umass/data/cmc1/test.data ... 146 loaded Leaves: 645, xtests: 9.71, instances: 1327, accuracy: 47.260, cpu: 1.8400, transps: 98003 (iti-incremental)

Vengono caricati i 9 attributi del dataset corrispondenti a 1327 istanze. L’albero generato ha 645 foglie, un’accuracy di 47,260, un tempo di esecuzione di 1.84 sec. Di seguito vengono mostrati tutti gli altri risultati in output:

fold 1 Loading testing set from ./Scrivania/ai/apprendimento/ITI/umass/data/cmc1/test.data ... 146 loaded Leaves: 645, xtests: 9.71, instances: 1327, accuracy: 47.260, cpu: 1.7000, transps: 98003 (iti-incremental) fold2 Loading testing set from ./Scrivania/ai/apprendimento/ITI/umass/data/cmc2/test.data ... 147 loaded Leaves: 657, xtests: 9.97, instances: 1326, accuracy: 51.020, cpu: 1.7600, transps: 103350 (iti-incremental) fold3 Loading testing set from ./Scrivania/ai/apprendimento/ITI/umass/data/cmc3/test.data ... 147 loaded Leaves: 668, xtests: 9.91, instances: 1326, accuracy: 50.340, cpu: 1.8400, transps: 107030 (iti-incremental) fold4 Loading testing set from ./Scrivania/ai/apprendimento/ITI/umass/data/cmc4/test.data ... 147 loaded Leaves: 648, xtests: 9.69, instances: 1326, accuracy: 50.340, cpu: 1.6800, transps: 95216 (iti-incremental) fold5 Loading testing set from ./Scrivania/ai/apprendimento/ITI/umass/data/cmc5/test.data ... 147 loaded

14

Leaves: 648, xtests: 9.70, instances: 1326, accuracy: 50.340, cpu: 1.8800, transps: 110175 (iti-incremental) fold6 Loading testing set from ./Scrivania/ai/apprendimento/ITI/umass/data/cmc6/test.data ... 147 loaded Leaves: 666, xtests: 9.91, instances: 1326, accuracy: 49.660, cpu: 1.4600, transps: 80436 (iti-incremental) fold7 Loading testing set from ./Scrivania/ai/apprendimento/ITI/umass/data/cmc7/test.data ... 147 loaded Leaves: 658, xtests: 9.89, instances: 1326, accuracy: 46.259, cpu: 1.7000, transps: 97673 (iti-incremental) fold8 Loading testing set from ./Scrivania/ai/apprendimento/ITI/umass/data/cmc8/test.data ... 148 loaded Leaves: 649, xtests: 9.90, instances: 1325, accuracy: 45.946, cpu: 1.3500, transps: 73255 (iti-incremental) fold9 Loading testing set from ./Scrivania/ai/apprendimento/ITI/umass/data/cmc9/test.data ... 148 loaded Leaves: 656, xtests: 9.81, instances: 1325, accuracy: 44.595, cpu: 1.8200, transps: 105996 (iti-incremental) fold10 Loading testing set from ./Scrivania/ai/apprendimento/ITI/umass/data/cmc10/test.data ... 149 loaded Leaves: 652, xtests: 9.84, instances: 1324, accuracy: 42.282, cpu: 2.0700, transps: 124021 (iti-incremental).

15

Viene mostrata una tabella riepilogativa con i dati ottenuti per ogni fold e una media per ogni parametro considerato.

fold foglie Accuratezza Iti tempo

1 645 47,26 1,7

2 657 51,02 1,76

3 668 50,34 1,84

4 648 50,34 1,68

5 648 50,34 1,88

6 666 49,66 1,46

7 658 46,25 1,7

8 649 45,95 1,35

9 656 44,6 1,82

10 652 42,28 2,07

Media 654,7 47,84 1,72

3.1.3 Test delle ipotesi

Il test statistico verterà sulle accuracy di classificazione ottenute per ogni fold da entrambi i sistemi, viene mostrata una tabella riepilogativa:

Fold Accuratezza c4.5 Accuratezza Iti 1 50 47,26

2 54,41 51,02

3 49,65 50,34

16

4 48,97 50,34

5 52,38 50,34

6 47,61 49,66

7 52,38 46,25

8 53,37 45,95

9 50,67 44,6

10 49 42,28

media 50,844 47,84

Verrà effettuato il test di Mann-Withney, sui 10 fold generati dopo l’esecuzione di C4.5 e Iti.

Viene definita l’ipotesi nulla H0 che specifica che non c’è alcuna differenza statisticamente significativa tra i due sistemi:

H0 µc4.5 = µiti

L’ipotesi H1 asserisce che esiste una differenza statisticamente significativa tra i due sistemi:

H1 µc4.5 ≠ µiti

Il test statistico ci dà i seguenti risultati:

Wilcoxon rank sum test // contra

> wilcox.test(Dataset$V1, Dataset$V2, correct=FALSE)

Wilcoxon rank sum test

data: Dataset$V1 and Dataset$V2

W = 75, p-value = 0.05831

alternative hypothesis: true location shift is not equal to 0

17

Il p-level è superiore al livello 0,05 livello di confidenza del test. Quindi non si può asserire che vi sia differenza statisticamente significativa tra i due sistemi, si accetta dunque l’ipotesi H0. In questo caso le prestazioni dei due sistemi relativamente alle accuracy non presentano differenze statisticamente significative.

Una rappresentazione grafica è rappresentata dal seguente box-plot:

Il seguente grafico mostra le media di entrambi i sistemi che sono quasi allo stesso livello ( non è presente nessun outliers), è un’ulteriore controprova per l’accettazione dell’ipotesi iniziale.

18

3.2 Credit Approval dataset

Questo dataset presenta 690 istanze suddivise in dieci fold ognuno dei quali aventi le seguenti dimensioni:

Fold1: 68 istanze Fold2: 68 istanze Fold3: 68 istanze Fold4: 69 istanze Fold5: 69 istanze Fold6: 69 istanze Fold7: 69 istanze Fold8: 70 istanze Fold9: 70 istanze Fold10: 70 istanze

Ogni fold è stato utilizzato come test-set e le rimanenti istanze come trainig-set. 3.2.1 Stima dei Dati per c4.5 Le informazioni utili per valutare la qualità del sistema che vengono state prese in considerazione sono:

Numero di foglie generate nell’albero di decisione. Percentuale di errore commesso nella classificazione delle istanze di test. Accuracy media di classificazione. Tempo di esecuzione e consumo di cpu impiegato per la generazione dell’albero.

Per stimare l’ultimo parametro è stato utilizzato per entrambi i sistemi il comando TIME in linux che fornisce in output il tempo di esecuzione di un comando diviso in real ( tempo effettivo di esecuzione dal momento dell’avvio del comando), user ( tempo utente) sys( e tempo di sistema). Anche se Iti già fornisce un output che mostra il tempo impiegato in termini di cpu, si è preferito applicare questo comando ad entrambi i sistemi e valutare il parametro real per avere una stima più precisa del tempo impiegato da entrambi. Tornando a C4.5, per quanto riguarda l’accuracy questa è stata calcolata nel modo seguente:

Il calcolo effettuato è riferito al fold 1 ottenuto nella classificazione, la accuracy media è stata ottenuta dividendo il numero delle istanze corrette della classe per il numero di istanze totali e facendo la media aritmetica. Di seguito viene mostrato un tipico risultato ottenuto in output: Evaluation on training data (622 items):

19

Before Pruning After Pruning ---------------- --------------------------- Size Errors Size Errors Estimate 144 31( 5.0%) 29 57( 9.2%) (12.9%) << Evaluation on test data (68 items): Before Pruning After Pruning ---------------- --------------------------- Size Errors Size Errors Estimate 144 12(17.6%) 29 12(17.6%) (12.9%) << Mediante la K-cross validation viene caricato il validation set costituito da 68 istanze mentre le restanti 622 costituiscono il training set. Altri valori visualizzati sono le foglie generate dell’albero e la stima d’errore durante la classificazione (prima e dopo il pruning). Di seguito verranno elencati gli output legati a tutti e dieci i fold: fold1 (a) (b) <-cl as accuracysified as accuracy ---- ---- 25 5 (a): cl as accuracys + 83,33 7 31 (b): cl as accuracys - 81,57 fold 2 (a) (b) <-cl as accuracysified as accuracy ---- ---- 28 2 (a): cl as accuracys + 93,33 9 29 (b): cl as accuracys - 76,31 fold 3 (a) (b) <-cl as accuracysified as accuracy ---- ---- 25 5 (a): cl as accuracys + 83,33 7 31 (b): cl as accuracys - 81,57 fold 4 (a) (b) <-cl as accuracysified as accuracy ---- ---- 25 6 (a): cl as accuracys + 80,64 2 36 (b): cl as accuracys - 94,73

20

fold 5 (a) (b) <-cl as accuracysified as accuracy ---- ---- 25 6 (a): cl as accuracys + 80,64 8 30 (b): cl as accuracys - 78,94 fold 6 (a) (b) <-cl as accuracysified as accuracy ---- ---- 28 3 (a): cl as accuracys + 90,32 2 36 (b): cl as accuracys - 94,73 fold 7 (a) (b) <-cl as accuracysified as accuracy ---- ---- 21 10 (a): cl as accuracys + 67,74 5 33 (b): cl as accuracys - 86,84 fold 8 (a) (b) <-cl as accuracysified as accuracy ---- ---- 28 3 (a): cl as accuracys + 90,32 4 35 (b): cl as accuracys - 89,74 fold 9 (a) (b) <-cl as accuracysified as accuracy ---- ---- 23 8 (a): cl as accuracys + 74,19 5 34 (b): cl as accuracys - 87,17 fold 10 (a) (b) <-cl as accuracysified as accuracy ---- ---- 24 7 (a): cl as accuracys + 77,41 3 36 (b): cl as accuracys - 92,30

21

Viene mostrata una tabella riepilogativa con i dati ottenuti per ogni fold e una media per ogni parametro considerato. fold foglie Accuratezzac4.5 tempo

1 29 82,35 0,02

2 27 83,82 0,02

3 42 82,35 0,02

4 17 88,40 0,02

5 26 79,71 0,02

6 47 92,75 0,04

7 15 78,26 0,04

8 25 90,00 0,02

9 41 81,42 0,03

10 13 85,71 0,02

media 28,2 84,47 0,025

3.2.2 Stima dei dati per Iti

E’ stato eseguito lo stesso processo per Iti, per questo sistema sono stativalutati i seguenti parametri:

Numero di foglie dell’albero generato

22

Accuracy complessiva Tempo di esecuzione

Un esempio di output è il seguente:

ITI 3.10 - (C) Copyright, U. of Massachusetts, 23 March 2001, All Rights Reserved Loading variable names ... 15 loaded Loading training set from ./Scrivania/ai/apprendimento/ITI/umass/data/crx1/shot.data ... 622 loaded Building tree: Tree built Loading testing set from ./Scrivania/ai/apprendimento/ITI/umass/data/crx1/test.data ... 68 loaded Leaves: 102, xtests: 6.31, instances: 622, accuracy: 73.529, cpu: 0.5400, transps: 5232 (iti-incremental)

Vengono caricati i 15 attributi del dataset corrispondenti a 622 istanze. L’albero generato ha 105 foglie, un’accuracy di 73,529, un tempo di esecuzione di 1.84 sec. Di seguito vengono mostrati tutti gli altri risultati in output:

fold 1 Loading testing set from ./Scrivania/ai/apprendimento/ITI/umass/data/crx1/test.data ... 68 loaded Leaves: 102, xtests: 6.31, instances: 622, accuracy: 73.529, cpu: 0.5300, transps: 5232 (iti-incremental) fold 2 Loading testing set from ./Scrivania/ai/apprendimento/ITI/umass/data/crx2/test.data ... 68 loaded Leaves: 93, xtests: 6.18, instances: 622, accuracy: 82.353, cpu: 0.5200, transps: 5453 (iti-incremental) fold 3 Loading testing set from ./Scrivania/ai/apprendimento/ITI/umass/data/crx3/test.data ... 68 loaded Leaves: 93, xtests: 5.89, instances: 622, accuracy: 73.529, cpu: 0.5000, transps: 4625 (iti-incremental)

23

fold 4 Loading testing set from ./Scrivania/ai/apprendimento/ITI/umass/data/crx4/test.data ... 69 loaded Leaves: 95, xtests: 6.11, instances: 621, accuracy: 82.609, cpu: 0.5300, transps: 5792 (iti-incremental) fold 5 Loading testing set from ./Scrivania/ai/apprendimento/ITI/umass/data/crx5/test.data ... 69 loaded Leaves: 94, xtests: 6.14, instances: 621, accuracy: 75.362, cpu: 0.5400, transps: 5514 (iti-incremental) fold 6 Loading testing set from ./Scrivania/ai/apprendimento/ITI/umass/data/crx6/test.data ... 69 loaded Leaves: 96, xtests: 6.22, instances: 621, accuracy: 81.159, cpu: 0.6500, transps: 8167 (iti-incremental) fold7 Loading testing set from ./Scrivania/ai/apprendimento/ITI/umass/data/crx7/test.data ... 69 loaded Leaves: 97, xtests: 6.26, instances: 621, accuracy: 76.812, cpu: 0.5100, transps: 4853 (iti-incremental) fold8 Loading testing set from ./Scrivania/ai/apprendimento/ITI/umass/data/crx8/test.data ... 70 loaded Leaves: 99, xtests: 6.23, instances: 620, accuracy: 82.857, cpu: 0.5300, transps: 4761 (iti-incremental) fold9 Loading testing set from ./Scrivania/ai/apprendimento/ITI/umass/data/crx9/test.data ... 70 loaded Leaves: 96, xtests: 6.20, instances: 620, accuracy: 81.429, cpu: 0.5300, transps: 5635 (iti-incrementals) fold10 Loading testing set from ./Scrivania/ai/apprendimento/ITI/umass/data/crx10/test.data ... 70 loaded Leaves: 101, xtests: 6.51, instances: 620, accuracy: 82.857, cpu: 0.6000, transps: 6185 (iti-incremental)

24

Viene mostrata una tabella riepilogativa con i dati ottenuti per ogni fold e una media per ogni parametro considerato.

fold foglie accuratezzaIti tempo

1 102 73,53 0,53

2 93 82,35 0,52

3 93 73,52 0,5

4 95 82,61 0,53

5 94 75,36 0,54

6 96 81,16 0,65

7 97 76,81 0,51

8 99 82,85 0,53

9 96 81,43 0,53

10 101 82,85 0,54

media 96,6 79,24 0,53

3.2.3 Test delle ipotesi

Il test statistico verterà sulle accuracy di classificazione ottenute per ogni fold da entrambi i sistemi, viene mostrata una tabella riepilogativa:

25

Fold Accuratezzac4.5 accuratezzaIti

1 82,35 73,53

2 83,82 82,35

3 82,35 73,52

4 88,4 82,61

5 79,71 75,36

6 92,75 81,16

7 78,26 76,81

8 90 82,85

9 81,42 81,43

10 85,71 82,85

media 84,47 79,24

Verrà effettuato il test di Mann-Withney, sui 10 fold generati dopo l’esecuzione di C4.5 e Iti.

Viene definita l’ipotesi nulla H0 che specifica che non c’è alcuna differenza statisticamente significativa tra i due sistemi:

H0 µc4.5 = µiti

L’ipotesi H1 asserisce che esiste una differenza statisticamente significativa tra i due sistemi:

H1 µc4.5 ≠ µiti

Il test statistico ci dà i seguenti risultati:

> wilcox.test(c45,iti, correct=FALSE)

wilcox.test(Dataset$V1, Dataset$V2,correct=FALSE) // credit

Wilcoxon rank sum test

data: Dataset$V1 and Dataset$V2

26

W = 76, p-value = 0.04894

alternative hypothesis: true location shift is not equal to 0

Il p-level è di poco inferiore al livello 0,05 livello di confidenza del test. Quindi si può asserire che vi sia differenza statisticamente significativa tra i due sistemi, si accetta dunque l’ipotesi H1.

Una rappresentazione grafica è rappresentata dal seguente box-plot:

Il seguente grafico mostra le media di entrambi i sistemi che sono quasi allo stesso livello ( non è presente nessun outliers), la differenza tra le due mediane è minima ( si evince anche dal valore del p-level) quanto basta per rigettare l’ipotesi H0.

27

4 Conclusioni

Alla luce dei dati raccolti per entrambi i sistemi di apprendimento, si può concludere che C4.5 è risultato leggermente migliore in termini di accuratezza della classificazione, non tenendo conto del tempo impiegato che è risultato molto inferiore a quello impiegato da ITI. La motivazione è da ricercare nella modalità di esecuzione di ogni sistema: per quanto riguarda C4.5, esso viene eseguito di default in modalità di batch mode non permettendo di modificare l’albero di decisione appena generato, al contrario ITI permette di revisionare e ristrutturare l’albero appena generato. Il parametro tempo non è stato considerato ai fine della valutazione perché si è ritenuto che, in relazione alla grandezza dei dataset, non fosse necessaro valutarlo. Con dataset di dimensioni maggiori sarebbe stato opportuno valutare anche il fattore tempo. Concludendo possiamo ribadire il concetto che C4.5 sia risultato migliore ma la possibilità che offre Iti di modificare il modello dell’albero mediante passi successivi incrementali e dunque non costruire il modello da zero, in termini di efficienza, sicuramente risulta superiore a C4.5.