Relazione Progetto

DATA MINING I

Il Disastro del Titanic

200905060626_1226_unipi_800_800.jpg

Davide incorvaglia

Catania Vito

Giulio Bambini

1.DATA UNDERSTANDING

1.1 SEMANTICA DEI DATI

1.2 DISTRIBUZIONE DELLE STATISTICHE

1.3 QUALITA’ DEI DATI

1.4 CORRELAZIONE TRA COPPIE DI ATTRIBUTI.

2 CLUSTERING

2.1 ANALISI TRAMITE K-MEANS

2.2.ANALISI TRAMITE DBSCAN

2.3 ANALISI TRAMITE HIERARCHICAL CLUSTERING

3. REGOLE DI ASSOCIAZIONE

3.1 ITEM SET FREQUENTI

3.2 REGOLE ASSOCIATIVE ESTRATTE

3.3 DISCUSSIONE SULLE REGOLE

4. CLASSIFICAZIONE

4.1 COSTRUZIONE DELL’ ALBERO DI DECISIONE E PREDIZIONE SUI DATASET

4.2 VERIFICA DEL MODELLO VINCITORE

1.DATA UNDERSTANDING

La Data Understanding è quel processo del KDD che permette di analizzare i dati in maniera preliminare. E’ fondamentale capire il senso di ogni attributo, identificare il numero di dati mancanti o dati anomali nel dataset e comprendere se esiste una dipendenza tra i vari attributi.

1.1 SEMANTICA DEI DATI

In questa sezione del documento vengono analizzati tutti i singoli attributi e ne viene spiegato il significato:

PassengerId-> si tratta di un attributo di tipo intero che identifica

univocamente ciascun passeggero del dataset.

Survived-> si tratta di un attributo di tipo categorico che identifica se il passeggero è sopravvissuto o meno al disastro. Assume valore 0 nel caso in cui il passeggero non sia sopravvissuto, altrimenti 1.

Pclass-> si tratta di un attributo di tipo categorico che identifica la classe della cabina assegnata a ciasciun passeggero (prima, seconda e terza classe indicate rispettivamente con valori 1,2,3).

Name-> si tratta di un attributo di tipo nominale che identifica il nome del passeggero a bordo.

Per identificare nomi di donne sposate viene riportato  il nome del marito e tra parentesi il nominativo completo della donna con il cognome da nubile.

Ciascun nominativo è preceduto da un’abbreviazione che ne indica la provenienza

sociale.

Per quanto riguarda le donne, attraverso l'onorificenza inglese "Mrs." vengono indicate le donne sposate, mentre per le donne non sposate si utilizza l'abbreviazione "Miss.". Alcune donne sono indicate con l'abbreviazione "Lady" per indicarne l'appartenenza nobiliare.

Per gli uomini invece abbiamo diverse abbreviazioni che indicano la provenienza sociale e in alcuni casi un'onorificenza accademica o militare.  L'abbreviazione "Mr." serve per indicare gli uomini sposati, l'abbreviazione "Master" per i bambini e i giovani non sposati che ancora non hanno debuttato in società, l'abbreviazione "Col." per il grado militare di Colonnello,  l'abbreviazione "Major" per maggiore militare, l'abbreviazione "Dr." per indicare un titolo di laurea magistrale, l'appellativo "Don" per indicare un titolo nobiliare assegnato ai nobili spagnoli e portoghesi.

Sex-> si tratta di un attributo di tipo categorico che identifica il sesso del passeggero.

Age-> si tratta di un attributo di tipo continuo che identifica l'età del passeggero.

Sibsp-> si tratta di un attributo di tipo numerico (discreto) che identifica il numero di fratelli/coniugi a bordo. Vengono considerati i seguenti rapporti di parentela:

Parch-> si tratta di un attributo di tipo numerico (discreto) che identifica il numero di genitori/bambini a bordo. Per il grado di parentela di genitore sono stati presi in considerazione la madre e il padre del passeggero a bordo, mentre per i figli sono stati presi in considerazione il figlio, la figlia, il figliastro o la figliastra del passeggero a bordo.Sono stati esclusi dalle analisi i rapporti di parentela come nipoti, zie, zii e suoceri.

Ticket-> si tratta di un attributo di tipo nominale che identifica l’identificativo del biglietto dei passeggeri a bordo. Alcuni identificativi risultano parzialmente composte da numeri e stringhe di carattere, mentre altre sigle sono composte esclusivamente da parti numeriche.

Fare-> si tratta di un attributo di tipo continuo che identifica la tariffa del biglietto pagato dal passeggero a bordo. Nel caso di passeggero con famiglia, la cifra indica il totale speso per tutta la famiglia. Se la cifra è 0, essa indica un lavoratore della nave (è logico che non abbia pagato per essere a bordo).

Cabin-> si tratta di un attributo di tipo nominale che identifica il numero della cabina assegnata al passeggero a bordo.

Embarked-> si tratta di un attributo di tipo categorico che identifica il porto di imbarco dal quale il passeggero si è imbarcato. la lettera C indica il porto di Cherbourg, Q indica il porto di Queenstown e S indica il porto di Southampton.

Prezzobiglietto -> si tratta di un attributo creato per effettuare analisi sul prezzo di un singolo biglietto. Ottenuto dividendo l’attributo Fare per il numero di biglietti con lo stesso identificativo. E’ stata inizialmente creata la nuova colonna con tutti i valori uguali a 0, poi è stata usato il nodo Cell Replacer per contare i biglietti che presentano lo stesso identificativo; Infine è stato usato il nodo Math Formula per dividere e ottenere i valori desiderati.

1.2 DISTRIBUZIONE DELLE STATISTICHE

Si è ritenuto opportuno analizzare le seguenti statistiche:

Passeggeri morti ->549 (61,62%)

 Passeggeri sopravvissuti  ->342 (38,38%)

Passeggeri maschi ->577 (64,75%)

Passeggeri femmine ->314 (35,25%)

Passeggeri in prima classe ->216   (24,24%)

 Passeggeri in seconda classe ->184   (20,65%)  

Passeggeri in terza classe->491 (55,11%)

 Imbarchi da C ->168  (18,85%)

Imbarchi da Q ->77   (8,64%)

Imbarchi da S ->644  (72,51%)

Morti di sesso femminile-> 81 (25,79%)

Sopravvissuti di sesso femminile->233  (74,21%)

Morti di sesso maschile-> 468 (81,10%)

Sopravvissuti di sesso maschile-> 109 (18,90%)

Spesa totale per biglietti di prima classe-> 18177.412499999984 $

(216 passeggeri)

Spesa totale per biglietti di seconda classe-> 3801.8416999999995 $

(184 passeggeri)

Spesa totale per biglietti di terza classe-> 6714.695100000002 $

(491 passeggeri)

Sopravvissuti di sesso maschile

Morti di sesso maschile

Sopravvissuti di sesso femminile

Morti di sesso femminile

Prima classe

45 (41,28%)

77 (16,45%)

91 (39,05%)

3 (3,7%)

Seconda classe

17 (15,59%)

91 (19,44%)

70 (30,04)

6 (7,4%)

Terza classe

47 (43,13%)

300 (64,11%)

72 ( 30,91%)

72 (88,9%)

 

1.3 QUALITA’ DEI DATI

In questa sezione del documento viene analizzato il Dataset in rapporto ai valori mancanti e ai valori troppo lontani rispetto agli altri (Outlier).

Valori mancanti (vengono tralasciati gli attributi in cui non sono presenti):

Age -> 177 valori mancanti su 891 record.

Cabin -> 687 valori mancanti su 891 record.

Embarked -> 2 valori mancanti su 891 record.

Outlier:

Per quanto riguarda gli Outlier, sono stati trovati alcuni valori fuori dalla norma per quanto riguarda l’attributo prezzobiglietto:

boxplotage.png

Come si nota dal grafico, i valori 221.78 e 211.5 sono valori abbastanza lontani dalla media.Tuttavia, poiché potrebbero essere valori plausibili e poiché 2 valori non influiscono molto sulle nostre analisi, si è scelto di non eliminarli dal dataset.

Rapporto finale: il Dataset presenta più della metà valori mancanti sull’attributo Cabin. Riteniamo che esso non ci può essere utile ai fini delle nostre analisi, verrà quindi pensata l’eliminazione della colonna. I valori mancanti dell’’attributo Age verranno sostituiti con la mediana, indice meno sensibile agli outlier. Per l’attributo Embarked verrà sostituito il valore più frequente della colonna per i due valori mancanti.

1.4 CORRELAZIONE TRA COPPIE DI ATTRIBUTI.

Vengono adesso analizzate le possibili correlazioni tra variabili. Una forte correlazione indica che i due attributi sono strettamente legati tra di loro, ovvero che il cambiamento di un attributo influenza l’altro. Sono state considerate correlazioni con valore superiore a 0.2 in valore assoluto.

Correlazioni negative:

Buona correlazione tra gli attributi Pclass e prezzobiglietto ( con valore -0,656).

Scarsa correlazione tra gli attributi Survived e Pclass (-0,338).

Scarsa correlazione tra gli attributi Age e Pclass(-0,34).

Scarsa correlazione tra SibSp e Age (-0,233)

Correlazioni positive:

Scarsa correlazione tra gli attributi  Parch e SibSp (0.415)

Scarsa correlazione tra gli attributi prezzobiglietto e Survived (0.255)

Scarsa correlazione tra gli attributi Age e prezzobiglietto(0,097).

correlation matrix.png

2 CLUSTERING

Le analisi di clustering permettono di accomunare dati sulla base di caratteristiche che presentano in comune. Per le nostre analisi ci serviamo di 3 tipi di algoritmi: K-means, Dbscan e algoritmi di clustering gerarchici.

2.1 ANALISI TRAMITE K-MEANS

K-means è un algoritmo che ha come obiettivo la minimizzazione della varianza totale all’interno dei singoli cluster. Ogni cluster viene identificato da un centroide. L'algoritmo segue una procedura iterativa:

  1. Crea K gruppi con K scelto arbitrariamente.
  2. Calcola il centroide di ogni gruppo.
  3. Costruisce un nuovo gruppo associando ogni punto d'ingresso al cluster il cui centroide è più vicino ad esso.
  4. Vengono ricalcolati i centroidi per i nuovi cluster e così via, finché l'algoritmo non converge.

Il primo passo della nostra analisi è stato decidere il k ottimale per l’algoritmo: per effettuare le operazioni di clustering sono state aggiunte 2 colonne in modo da evitare falsi outlier:  

Replacement -> indica il numero di biglietti con lo stesso identificativo (usato per la divisione).

prezzobiglietto -> ottenuto dividendo i valori di Fare con i valori di replacement. Permette di trovare il prezzo del biglietto per persona (utile nel caso di valori di Fare per i passeggeri che hanno famiglia oppure quando ogni ci sono ticket cumulativi).

Per ottenere il k migliore è stato costruito il seguente grafico basato sull’SSE(Sum of Squared Errors, che indica la devianza intra-cluster):

Sull’asse dell’ascisse sono distribuiti i valori di K, mentre nelle ordinate sono distribuiti i valori di SSE per l’esecuzione di K-Means per i K valori. Dal grafico notiamo che la curva si stabilizza a partire da k=7 con valore SSE di 187.852; infatti superando questa soglia il valore dell’SSE tende a diminuire lentamente. L’algoritmo converge alla quindicesima iterazione: otteniamo quindi 7 cluster:

k-means7.png

Cluster 0 ---> Gruppo di passeggeri morti di sesso maschile appartenenti alla terza classe imbarcati da Southampton (231 record).

Cluster 1 --->  Per la maggior parte gruppo di passeggeri morti di sesso maschile appartenenti alla terza classe senza figli imbarcati (70 record).

Cluster 2 ---> Gruppo di passeggeri sopravvissuti appartenenti alla prima classe (136 record).

Cluster 3 ---> Gruppo di passeggeri morti di sesso maschile(167 record).

Cluster 4 ---> Gruppo di passeggeri sopravvissuti (155 record).

Cluster 5 ---> Per la maggior parte gruppo di passeggeri morti di sesso femminile appartenenti alla terza classe (81 record).

Cluster 6 ---> Per la maggior parte gruppo di passeggeri sopravvissuti appartenenti alla terza classe(51 record).

2.2.ANALISI TRAMITE DBSCAN

Il DBscan è un algoritmo basato sulla densità dei dati, il cui obiettivo è raggruppare i punti vicini tra di loro, escludendo invece quelli lontani. Etichetta i punti in core, noise e border point. Richiede 2 parametri per essere eseguito:

Eps= Raggio della distanza minima per agglomerare i punti tra di loro.

Minpts= Numero minimo di punti a cui un determinato punto deve essere collegato per essere etichettato come Core Point.

I punti agglomerati ad un Core Point che non sono Core point a loro volta sono etichettati come Border Point. I punti che non rispettano il Raggio della distanza minima e che quindi non sono collegati a nessun Core Point sono etichettati come Noise Point.

Inizialmente per eseguire l’algoritmo sono stati normalizzati i dati ed è stata calcolata la matrice delle distanze minime tra i punti con il nodo Distance Matrix Writer. I valori della matrice sono poi stati disposti su un piano cartesiano in modo tale da ottenere il seguente grafico:

Dal grafico si può capire quali sono i valori ottimali di Eps e Minpts. Abbiamo capito che Eps=0.6 (per via della stabilizzazione dell’andamento della curva) e Minpts=3 (scelto per il numero degli attributi considerati nell’esecuzione dell’algoritmo +1). L’esecuzione di Dbscan con questi parametri ha prodotto 4 cluster, con 2 punti etichettati come Noise Point.

2.3 ANALISI TRAMITE HIERARCHICAL CLUSTERING

Il clustering gerarchico è un approccio di clustering che mira a costruire una gerarchia di cluster. L'algoritmo basa il suo funzionamento sul calcolo della distanza tra i punti del dataset. I criteri di collegamento sono di tre tipi:

Single Linkage (o MIN): costruisce la matrice di prossimità per la gerarchia del dendogramma sulla base della distanza minima tra due punti di due cluster diversi.

Complete Linkage (o MAX): costruisce la matrice di prossimità per la gerarchia del dendogramma sulla base della massima similarità tra due punti di due cluster diversi.

Group Average: costruisce la matrice di prossimità sulla base della distanza media di un punto di un cluster con tutti i punti del secondo cluster.

Non si definisce un numero particolare di cluster in questo caso; con il taglio del dendogramma è possibile ottenere il numero desiderato di cluster. Si è scelto di utilizzare la distanza euclidea per calcolare le distanze.

Dendogramma ottenuto con l’algoritmo Complete Linkage:

dendro MAX.png

Dendogramma ottenuto con l’algoritmo Group Average:

dendro AVG.png

dai dendrogrammi ottenuti notiamo che la distanza aumenta a partire da 45000 per quello ottenuto con il group average e da 89000 per il dendrogramma ottenuto con il metodo complete linkage. In entrambi i casi effettuando il taglio otteniamo una divisione in 4 Cluster (Il single linkage non è stato riportato in quanto completamente sbilanciato).

3. REGOLE DI ASSOCIAZIONE

Lo scopo di questa sezione del documento è illustrare le fasi per estrarre i pattern più frequenti all’interno del dataset con il relativo supporto e successivamente trovare regole di associazione valide tra gli elementi dell’itemset per una certa soglia di confidenza. La confidenza serve per vedere quante volte nel dataset 2 valori si trovano insieme, rispetto alle volte in cui invece si trovano singolarmente.

3.1 ITEM SET FREQUENTI

Per trovare gli item set frequenti sono state affrontate le seguenti fasi del lavoro:

  1. Trasformazione dei valori dell’attributo Survived da numero a stringa. I valori 0 e 1 sono stati trasformati rispettivamente in NO e YES. Sono stati usati i nodi Number to String e String Replacer per questo compito.
  2. Binning (creazione di classi e distribuzione equa dei valori) sui seguenti attributi: Age, Prezzobiglietto e Sumparents(somma dei valori degli attributi Parch e Sibsp). Sono state create 2 nuove colonne con i  rispettivi range di binning. Il numero delle classi ottimale per ogni attributo è stato determinato automaticamente con l’uso del nodo Auto Binner nel caso di Age e Prezzobiglietto, mentre per sumparents è stato usato il nodo Numeric Binner e sono stati creati 2 bin: uno per chi aveva 0 parenti a bordo e uno per chi ne aveva almeno 1.
  3. Estrazione dei pattern frequenti con differenti valori di supporto. Sono stati provati i valori di supporto del 40% e 50%. E’ stato usato l’algoritmo Apriori. Ecco i pattern ottenuti:

Questi sono gli item set frequenti ottenuti con supporto del 40%. I range di binning da 20.315 a 30.263 rappresentano la fascia d’età che va da 20 a 30 anni circa, mentre il range da 0 a 27 .722 rappresenta la prima fascia di prezzo del biglietto (quella più economica). 0P indica nessun parente a bordo, mente +P indica almeno 1 parente a bordo.

Invece, aumentando il supporto a 50% vengono estratti i seguenti pattern:

Per un’analisi più completa, abbiamo deciso di includere anche gli itemset closed e i maximal.

Closed con supporto 40%:

Closed con supporto 50%:

Maximal con supporto 40%:

Maximal con supporto 50%:

3.2 REGOLE ASSOCIATIVE ESTRATTE

A partire dagli itemset frequenti sono state estratte le seguenti regole. Per la confidenza sono stati provati i valori del 30% e del 50%:  

Confidenza del 30%, Supporto del 30%:

Confidenza del 50%, Supporto del 50% :

Dove ogni regola è del tipo {A} -> {B}. il termine {A} è identificato dalla colonna Antecedent, mentre {B} dalla colonna Consequent. Notiamo che con una confidenza del 50% e un supporto del 50% non si ottengono regole significative. Abbiamo provato ad abbassare la percentuale di supporto per cercare di ottenere altre regole. Con stessa percentuale di confidenza e 20% di supporto otteniamo le seguenti regole:

Confidenza 50%, Supporto 20%:

3.3 DISCUSSIONE SULLE REGOLE

Dalle regole estratte si evince che le regole più interessanti sono quelle con percentuale di confidenza del 50%, ovvero:

  1. Chi aveva un età compresa tra 20 e 30 anni  ha pagato un basso prezzo per il biglietto [da 0 a 28 pounds circa].
  2. .
  3. Chi era in terza classe ha pagato un basso prezzo per il biglietto [da 0 a 28 pounds circa].
  4. Chi non aveva figli ha pagato un basso prezzo per il biglietto [da 0 a 28 pounds circa].
  5. Chi non è sopravvissuto ha pagato un basso prezzo per il biglietto.

La seconda regola è abbastanza ovvia. Più interessante invece la prima regola, in cui si evince che molte persone della terza classe non sono sopravvissute al disastro. Con una confidenza del 46% circa, inoltre, si riescono a ricavare altre regole:

  1. Chi ha pagato un basso prezzo per il biglietto [da 0 a 28 pounds circa] non è sopravvissuto
  2. Chi non è sopravvissuto ha pagato un basso prezzo per il biglietto [da 0 a 28 pounds circa].
  3. Chi era maschio non è sopravvissuto.
  4. Chi era maschio ha pagato un basso prezzo per il biglietto [da 0 a 28 pounds circa].
  5. Chi si era imbarcato da Southampton non è sopravvissuto.
  6. Chi si era imbarcato da Southampton ha pagato un basso prezzo per il biglietto [da 0 a 28 pounds circa]

4. CLASSIFICAZIONE

Lo scopo della classificazione è quello di stabilire l’appartenenza di ogni elemento del dataset ad una classe tramite la creazione di un modello, in maniera tale da saper classificare eventuali nuovi elementi. Esistono diversi modelli di classificazione. Per le nostre analisi ci siamo basati sugli alberi di decisione.

4.1 COSTRUZIONE DELL’ ALBERO DI DECISIONE E PREDIZIONE SUI DATASET

Per la costruzione dell’albero sono stati seguiti i seguenti passi:

  1. Scelta della classe da predire tra l’insieme degli attributi. Il task in questo caso richiede che la classe sia “Survived”.
  2. L’attributo “Survived” è stato trasformato da categorico a stringa, in maniera tale da restituire i valori “yes” o “no”. Sul Test set è stata invece creata la colonna.
  3. Assegnazione dei colori con il nodo “Color Manager” ai valori dell’attributo Survived, rosso(no) e blu(Yes).
  4. Generazione dell’albero di decisione con il nodo “Decison Tree Learner” per il training set scegliendo l’attributo Survived come classe. Il numero minimo di record necessario per effettuare uno split è stato impostato a 2.
  5. Predizione effettuata sul test set e sul training set sulla base del modello generato.
  6. Calcolo delle misure statistiche necessarie per verificare la validità del modello.

Sono state effettuate diverse prove di impostazioni per cercare di ottenere il modello migliore. Per completezza riportiamo i modelli delle prove effettuate, compreso il modello vincitore.

Modello 1 - Pruning: MDL, Impurity Measure: Gini Index. Accuracy Training: 83%. Accuracy Test: 65.1%

Modello 2 - Pruning: MDL, Impurity Measure: Gain Ratio. Accuracy Training: 82%. Accuracy Test: 65.1%

Modello 3 - Pruning: NO. Impurity Measure: Gain Ratio. Accuracy Training: 93%. Accuracy Test: 64%

Modello 4 - Pruning: NO. Impurity Measure: Gini Index.  Accuracy Training: 92%. Accuracy Test: 66%

Modello 5 (Vincitore) - Pruning: MDL. Impurity Measure: Gini Index.  Accuracy Training: 84%. Accuracy Test: 69%

4.2 VERIFICA DEL MODELLO VINCITORE

E’ stato utilizzato il nodo Scorer per calcolare la matrice di confusione e l’accuratezza per il Test set e per il Training set del modello vincitore a partire dai valori predetti ottenuti precedentemente.

Risultati ottenuti per il Training set:

accuracytrain.png

Risultati ottenuti per il Test set:

accuracytest.png

Tutti i modelli provati non superavano la soglia del 70% di accuratezza per il test set. Si è scelto il modello 5 perchè a dispetto di un accuratezza minore sul train set otteniamo un migliore risultato sul test set.