# Progetto Machine Learning analisi Breast Cancer Wisconsin

Autori:

- Fabio Marchesi mtr: 844941.
- Simone Mallei mtr: 844659.

## Introduzione

Questa relazione ha lo scopo di studiare e confrontare due modelli di Machine Learning su un dataset specifico.

Nei seguenti capitoli verrà fatta una prima analisi sul dataset scelto, con una descrizione del dominio di riferimento e del significato di ognuno degli attributi.

Successivamente, si effettuerà un'operazione di feature extraction per poter avere una rappresentazione migliore e più concisa delle informazioni del dataset preso in considerazione.

Verranno inoltre selezionati dei modelli da addestrare su questo dataset, in modo tale da poterli confrontare e verificare quale dei due dia risultati migliori, indicando quale modello è meglio utilizzare per questo insieme di dati.

Per poterli confrontare si considereranno metriche come l'accuratezza, la precisione e, per avere risultati più robusti, si utilizzerà la cross-validation per poter calcolare gli intervalli di confidenza per ogni metrica analizzata.

## Selezione Dataset
Il [dataset](https://archive-beta.ics.uci.edu/ml/datasets/breast+cancer+wisconsin+diagnostic) selezionato contiene informazioni riguardo la diagnosi di tumori al seno rispetto a diverse caratteristiche del nucleo della cellula tumorale misurate da 3 dimensioni differenti. Ogni istanza del dataset è caratterizzata da 32 colonne:
- $1$: L'id dell'istanza.
- $2$: L'esito dell'analisi.
- $3 + 10 * i, 1 \le i \le 3$: Raggio del nucleo (espresso come media delle distanze dei punti sul perimetro dal centro del nucleo).
- $4 + 10 * i, 1 \le i \le 3$: Texture (deviazione standard dei valori sulla scala di grigi).
- $5 + 10 * i, 1 \le i \le 3$: Perimetro.
- $6 + 10 * i, 1 \le i \le 3$: Area.
- $7 + 10 * i, 1 \le i \le 3$: Levigatezza (variazione locale delle lunghezze dei raggi).
- $8 + 10 * i, 1 \le i \le 3$: Compattezza (perimetro alla seconda fratto (area - 1)).
- $9 + 10 * i, 1 \le i \le 3$: Concavità (Severità delle porzioni concave sul contorno)
- $10 + 10 * i, 1 \le i \le 3$: Numero di porzioni concave.
- $11 + 10 * i, 1 \le i \le 3$: Simmetria.
- $12 + 10 * i, 1 \le i \le 3$: Dimensione frattale.

Un passo preliminare è stato quello di assegnare manualmente ad ogni colonna del dataset in formato `.csv` il corretto identificativo in modo da poter lavorare in maniera più comoda con le varie covariate.

Inoltre, in quanto potevano essere presenti all'interno del dataset delle istanze per le quali i valori di alcuni attributi non fossero disponibili (tali valori sono rappresentati tramite il valore `0.0000`), è stato necessario identificare tali istanze ed, in base alla loro quantità, decidere come trattarle. In questo caso solo 13 istanze su un totale di 569 contenevano uno o più valori mancanti, è stato quindi deciso di rimuoverle completamente dal dataset in quanto rappresentavano una frazione molto piccola del dataset.

Inoltre sono state effettuate delle analisi relative alle istanze presenti e sono state raggiunte diverse conclusioni:
- Il numero di esiti benigni e quello di esiti maligni è sufficientemente bilanciato (344 benigni contro 212 maligni).
- I valori di una stessa proprietà analizzati sulle 3 dimensioni sono correlati tra loro ma non a sufficienza per poter utilizzare solo una delle 3 dimensioni.
- L'attributo `diagnosi` è l'unico di tipo non numerico, deve essere dunque fattorizzato.
## PCA

Avere 30 covariate per un insieme di 556 istanze risulta rischioso in quanto alcune potrebbero essere fortemente correlate, mentre altre potrebbero essere addirittura ininfluenti e/o rumorose.

Gli algoritmi che vengono presi in considerazione hanno bisogno di definire lo spazio di input manualmente e dato che la complessità dei modelli dipende dal numero di attributi, è stato deciso di affrontare questo problema con l'utilizzo della PCA.

La PCA (*Principal Component Analysis*) ci permette di rappresentare il dataset in un nuovo spazio sfruttando il concetto di **feature extraction**: ovvero la trasformazione di attributi iniziali in uno spazio di dimensione minore (con la PCA le trasformazioni risultano lineari), passando da uno spazio da $N$ dimensioni ad uno con $M$ dimensioni con $N > M$.

Questo metodo determina le coordinate in un nuovo spazio dove la prima componente rappresenta maggiormente la varianza originale del dataset, la seconda componente principale è una componente ortogonale alla prima che cerca di rappresentare maggiormente la varianza rimanente non rappresentata dalla prima componente, dalla terza quella rimanente dalle prime due e così via.

Quindi trasformiamo gli attributi potenzialmente correlati $x$ in un insieme di componenti principali $p$ non correlati (ortogonali fra loro).

È possibile applicare la PCA al dataset WDBC in quanto i valori sono tutti reali e non nominali/categorici (altrimenti il risultato ottenuto dalla PCA non sarebbe significativo).

Viene mostrato uno "Scree plot", che contiene per ognuna delle prime nuove 10 dimensioni quanta varianza originale del dataset viene catturata da ognuna di queste componenti:


Si sceglie di voler "spiegare" almeno l' 80% della varianza originale, quindi si selezionano le prime 5 componenti ottenute attraverso la PCA, con una varianza cumulativa pari all'84.83%.

Vengono mostrate nei plot seguenti le coordinate delle covariate originali rispetto alle due prime componenti principali:

- Il primo plot contiene gli attributi della cellula raccolti nella prima dimensione:
Si può notare la vicinanza tra le covariate "perimeter1", "area1" e "radius1", indicando una correlazione molto elevata fra questi attributi. Inoltre, le coordinate "simmetry1" e "smoothness1" sono pressoché identiche, indicando anch'esse una forte correlazione fra queste due covariate.

- Il secondo contiene gli attributi relativi alla seconda dimensione della cellula:
Nuovamente, è evidente la correlazione tra le covariate "perimeter2", "area2" e "radius2", mentre in questo caso la correlazione tra "simmetry2" e "smoothness2" viene meno (rispetto a quelle relative alla prima dimensione), mentre è possibile osservare una direzione molto simile tra "compactness2" e "concavity2", indicando una miglior rappresentazione da parte di "compactness2" vista la norma di valore maggiore.

- Il terzo ed ultimo grafico contiene gli attributi relativi alla terza dimensione della cellula:
Anche per la terza dimensione, gli attributi "perimeter3", "area3", "radius3" sono fortemente correlati. Si può notare come, anche nella terza dimensione, "smoothness3" e "symmetry3" risultino nuovamente correlati (anche se non fortemente quanto nella prima dimensione).

Vengono mostrati i seguenti scatter plot: il primo utilizza le due covariate "Concave Points 1" e "Fractal Dimension 1", ovvero gli attributi che hanno maggior contributo sulla prima e sulla seconda componente, rispettivamente.
Il secondo grafico mostra invece le due prime componenti ottenute da PCA:



Si può osservare come il plot con le prime due componenti ottenute con PCA faccia visualizzare una "maggiore" separazione lineare tra le due classi rispetto al grafico ottenuto utilizzando due delle covariate originali.
Tutto ciò si può spiegare dal fatto che le componenti della PCA considerano pure le altre covariate, quindi riescono a catturare delle caratteristiche delle distribuzioni delle due classi che non vengono rappresentate nei due attributi del dataset originale.

## Support Vector Machine
Essendo il problema considerato di classificazione binaria, posso utilizzare le support vector machine per predirre la variabile target. Essendo le istanze non linearmente separabili nelle 5 dimensioni ottenute tramite PCA, è necessario l'utilizzo di una funzione kernel. Nel nostro caso è stato utilizzato il kernel di tipo "radial" $K(x,y) = exp(- \gamma \Sigma_{j = 1}^{p}(x_{ij}-y_{ij})^2)$ dove il parametro $\gamma$ rappresenta il parametro di tuning responsabile per la "fluidità" del margine (e di conseguenza la varianza).

La dimensione del dataset a nostra disposizione non è particolarmente elevata, di conseguenza per effettuare una robusta stima dell'effettiva efficacia dei vari modelli, comprese le support vector machine, viene effettuata una 10-fold cross validation. Tramite tale procedura le 556 istanze vengono divise in 10 fold in modo che ogni istanza appartenga ad esattamente un fold. Successivamente si itera su ognuna di queste fold e la si seleziona come test set, mentre le altre 9 si utilizzano come training set. Bisogna quindi poi analizzare i risultati ottenuti da ognuna delle 10 iterazioni secondo varie metriche. Le metriche utilizzate vengono calcolate rispetto ad ogni possibile classe e vengono poi combinate tramite macro-average: $perf^* = \frac{1}{|L|}\Sigma_{l = 1}^{|L|}perf(l)$, ossia dando la stessa importanza alle varie classi senza considerare la loro cardinalità. Le metriche utilizzate sono calcolate per ogni classe $l$ come:

**Accuracy:** Porzione di predizioni effettuate correttamente $\frac{TP + TN}{P + N}$

**Precision**: Porzione di persone alle quali è stata correttamente predetta la classe $l$ rispetto al numero di persone alle quali è stata predetta la classe $l$ $\frac{TP}{TP+FP}$

**Recall**: Porzione di persone alle quali è stata diagnosticata la classe $l$ rispetto al numero di persone che appartengono alla classe $l$ $\frac{TP}{P}$

**F-Measure**: Combina i concetti di precision e recall in un unico valore $\frac{2 \times precision \times recall }{precision + recall}$

Analizzando le metriche presentate durante le 10 iterazioni otteniamo:

| | **Accuracy** | **Precision** | **Recall** | **F-Measure** |
| ------- | ------------ | ------------- | ---------- | ------------- |
|**Massimo**|1.0000|1.0000|1.0000|1.0000|
|**Minimo**|0.8928|0.8857|0.8857|0.8857|
|**Mediana**|0.9639|0.9674|0.9575|0.9616|
|**Media**|0.9568|0.9550|0.9543|0.9543|

Inoltre possiamo sommare le matrici di confusione ottenute durante le 10 iterazioni ottenendo:

|| **Effettivamente Benigni** | **Effettivamente Maligni** |
| -- | -- | -- |
|**Predetti Benigni**|332|12|
| **Predetti Maligni** |12|200|

Da questa matrice di confusione complessiva otteniamo un'accuratezza pari a `0.9568`

## Decision Tree
Il secondo approccio utilizzato per risolvere il problema di classificazione binaria affrontato sono gli alberi di decisione. Sono stati utilizzati alberi chiamati `rpart`, ossia recursive partitioning, all'interno dei quali, a differenza dei classici alberi di decisione, un determinato attributo può apparire in più rami. Un'altra differenza sostanziale è che i classici alberi di decisione utilizzano il concetto di information gain per selezionare l'attributo sul quale fare lo split mentre i cart utilizzati usano il concetto di Gini index per effettuare lo split (verrà scelto l'attributo che minimizza tale indice). Il Gini index viene calcolato come: $I_G(p) = 1 - \Sigma_{i=1}^{J}p_i^2$ dove $p_i$ rappresenta la porzione di istanze con etichetta $i$.

Anche in questo caso le 5 coordinate trovate per ogni istanza tramite PCA sono utilizzate per predire la diagnosi di ogni istanza. Anche per valutare questo modello è stata applicata una 10-fold cross validation per ottenere una misura di precisione robusta e sono state valutate le stesse metriche, ottenendo i seguenti risultati:

| | **Accuracy** | **Precision** | **Recall** | **F-Measure** |
| ------- | ------------ | ------------- | ---------- | ------------- |
|**Massimo**|0.9642|0.9619|0.9714|0.9625|
|**Minimo**|0.8571|0.8477|0.8424|0.8519|
|**Mediana**|0.8738|0.8858|0.8697|0.8663|
|**Media**|0.9047|0.9020|0.8999|0.8988|

Inoltre possiamo sommare le matrici di confusione ottenute durante le 10 iterazioni ottenendo:

|| **Effettivamente Benigni** | **Effettivamente Maligni** |
| -- | -- | -- |
|**Predetti Benigni**|317|26|
| **Predetti Maligni** |27|186|

Da questa matrice di confusione complessiva otteniamo un'accuratezza pari a `0.9047`
## Esperimenti e risultati
Confrontando le metriche proposte precedentemente è facile notare come le support vector machine risultino essere il modello più efficace per il problema di classificazione affrontato.
Andiamo ora a vedere altre modi per confrontare le loro performance.

### Curve ROC

Introduciamo la curva ROC, un grafico che mostra l'efficacia di un classificatore binario al variare della sua soglia di classificazione. In particolare per ogni soglia di classificazione viene valutato il suo true positive rate (anche chiamata sensitivity) ed il suo false positive rate. Facendo variare il valore della soglia possiamo tracciare una curva come illustrato successivamente (viene mostrata la curva ROC relativa al Fold 3). Per valutare da un punto di vista numerico la curva possiamo calcolare l'area sottesa alla curva (AUC), maggiore è tale valore e migliore risulterà il classificatore finale. Anche in questo caso quando procediamo al calcolo di tale curva dobbiamo dividere il ragionamento in classi, quindi riferendoci prima alle cellule tumorali che risultano essere benigne:


E poi a quelle che risultano maligne:


Si nota facilmente che la ROC relative alle svm risultano avere un'area sottesa alla curva molto maggiore rispetto alle ROC relative agli alberi di decisione. Nei grafici possiamo anche notare il classificatore random nel quale, a prescindere dalla soglia di decisione, il true positive rate e false positive rate risultano equivalenti.

Analizzando le aree sotto le curve ROC durante le 10 iterazioni otteniamo:

| | **SVM** | **RPART** |
| ------- | ------------ | ------------- |
|**Massimo**|1.0000|0.9714|
|**Minimo**|0.9776|0.8424|
|**Mediana**|0.9938|0.8697|
|**Media**|0.9908|0.8999|

Anche questa è una prova che ci porta a confermare la miglior performance da parte del modello SVM (inoltre, il valore minimo di AUC ottenuto dai 10 fold per SVM è addirittura maggiore del valore massimo raggiunto dal modello di Decision Tree).

### Intervalli di Confidenza
Per poter confrontare in modo robusto i dati ottenuti relativi alle metriche, possiamo avvalerci degli intervalli di confidenza, nel nostro caso considereremo gli intervalli di confidenza al 95%.
In statistica, un intervallo di confidenza al 95% di un insieme di campioni, è l'intervallo stimato sulla media dei valori di questo insieme di campioni. Il 95% viene indicato come livello di confidenza e quindi l'attendibilità del metodo in sé (se il metodo venisse ripetuto su un numero indefinito di campioni, l'intervallo di confidenza al 95% tenderebbe a contenere il vero parametro il 95% delle volte).
Vengono mostrati nei grafici seguenti la media e gli intervalli di confidenza al 95% dei valori delle metriche considerate (gli intervalli di confidenza sono stati calcolati attraverso una distribuzione t Student con 10 - 1 = 9 gradi di libertà):


Si può osservare come, per le metriche di accuracy, precision, recall e f_measure i due intervalli di confidenza si intersecano, ma quello relativo al modello di SVM è sempre quello che ottiene un risultato migliore.
Per quanto riguarda l'Area Under Curve, i due intervalli sono addirittura disgiunti, mostrando un considerevole distacco di performance da parte del modello di SVM rispetto a quello ottenuto usando il Decision Tree.

### Box Plot
Un altro tipo di plot che può essere interessante per l'analisi dei risultati è il boxplot.
Questo tipo di rappresentazione ci permette di osservare i valori dei quartili delle metriche, mostrando di conseguenza un'idea di ciò che è la distribuzione della metrica per quel dataset con il modello considerato.

I grafici seguenti mostrano i boxplot per ogni metrica considerata:


Oltre all'ennesima prova della migliore performance da parte del modello di SVM, in questo caso ci è possibile notare anche la differenza della "larghezza" delle distribuzioni delle metriche: infatti, le distribuzioni delle metriche ottenute dal modello di RPART suggeriscono una maggiore varianza dei valori: infatti il primo ed il terzo quartile hanno un distacco ben visibile rispetto alla distanza tra il primo ed il terzo quartile dei corrispondenti valori del modello di SVM.
Questo ci indica anche una maggiore stabilità nelle performance da parte del modello ottenuto tramite SVM.
Inoltre, data la posizione della mediana rispetto al terzo quartile nelle distribuzioni delle metriche del Decision Tree, si può notare una coda verso destra allungata rispetto a quella verso sinistra, ciò suggerisce un'asimmetria positiva delle distribuzioni considerate (confermata anche dai valori delle medie e delle mediane mostrate nelle tabelle precedenti).

## Conclusione

Durante questo studio, abbiamo affrontato un problema di classificazione binaria e, data la presenza di un numero elevato di covariate iniziali, abbiamo ridotto il numero di attributi attraverso la tecnica di PCA.

I modelli che abbiamo utilizzato sono Decision Tree e SVM, addestrati utilizzando una cross-validation con 10 fold.

Per poterli confrontare abbiamo analizzato i valori delle varie metriche e dei loro intervalli di confidenza, ottenendo una performance migliore da parte del modello di SVM sotto tutte le misure prese in considerazione.