WMR 09 - Lab I (Decision Trees + Weka)

Per costruire il nostro decision tree cercheremo di analizzare i vari attributi in modo da prendere quello che meglio separa le istanze rispetto all'appartenenza alle varie classi. Questo passo è poi ripetuto ricorsivamente fino ad ottenere la separazione a grana fine delle istanze nelle varie classi.

In questo contesto torna utile il concetto di purità: un sottoinsieme di dati è detto puro se tutte le istanze del sottoinsieme appartengono alla stessa classe.

Idealmente vorremmo infatti splittare i dati in sottoinsiemi puri, in modo da rendere banale la decisione di classificazione. Per fare questo si utilizza la seguente euristica: si prende l'attributo con la massima information gain e si dividere il dataset rispetto ai valori di quell'attributo.

Ricordiamo che l'entropia nel contesto dell'information theory ci permette di misurare l'incertezza, o il contenuto informativo, di un dato evento.

Consideriamo un training set \(D\), e sia \(m = |C|\) il numero delle classi target. Possiamo definire \(X\) come la v.a. che rappresenta la classe di un elemento estratto a caso dal training set \(D\). Notiamo che \(X\) è una v.a. discreta con una sua densità descrita ottenuta dai valori \(P(c_1), \ldots, P(c_m)\), dove

\[P(c_i) = \text{probabilità che l'elemento estratto appartiene alla classe} c_i\]

A questo punto possiamo calcolare l'entropia di \(X\) come segue

\[H(X) = - \sum\limits_{j = 1}^{m} P(c_j) \log_2{P(c_j)}\]

Consideriamo i seguenti esempi in un contesto di classificazione binaria in cui \(C = \{\text{Positive}, \text{Negative}\}\).

• Se il nostro dataset \(D\) ha il \(50\%\) degli esempi nella classe \(\text{Positive}\) e il restante \(50\%\) nella classe \(\text{Negative}\), allora troviamo

  \[H(X) = - 0.5 \cdot \log_2{0.5} - 0.5 \cdot \log_2{0.5} = 1\]

• Se il nostro dataset \(D\) ha il \(20\%\) degli esempi nella classe \(\text{Positive}\) e il restante \(80\%\) nella classe \(\text{Negative}\), allora troviamo

  \[H(X) = - 0.2 \cdot \log_2{0.2} - 0.8 \cdot \log_2{0.8} = 0.722\]

• Se il nostro dataset \(D\) ha il \(100\%\) degli esempi nella classe \(\text{Positive}\) e il restante \(0\%\) nella classe \(\text{Negative}\), allora troviamo

  \[H(X) = - 1 \cdot \log_2{1} - 0 \cdot \log_2{0} = 0\]

L'idea per la costruzione del nostro decision tree consiste nel calcolare l'entropia del dataset originale per avere una baseline che verrà poi utilizzata per capire se l'attributo preso in considerazione permette di splittare il dataset andando a ridurre l'entropia delle parti oppure andandola ad aumentarla.

Observation: In generale per misurare le performance di un sistema di apprendimento automatico è di fondamentale importanza avere una baseline che ci permette di misurare la difficoltà del task affrontato.

Per fare questo calcolo iniziale posso utilizzare le probabilità a priori \(P(c_j)\) stimate tramite una semplice calcolo della frequenza. Nel nostro caso ad esempio ho due classi, di cui

\[\begin{split} P(C_\text{No}) &= \frac{6}{15} = \frac{2}{5} \\ P(C_\text{Yes}) &= \frac{9}{15} = \frac{3}{5} \\ \end{split}\]

La costruzione poi continua andando a selezionare ogni feature e partizionando il dataset rispetto al valore assunto da quella feature. Per calcolare la qualità di tale partizionamento calcolo l'entropia totale di questa scelta utilizzando l'equazione a seguire

\[H_{A_i}(D) = \sum\limits_{j = 1}^v \frac{|D_j|}{|D|} H(D_j)\]

dove \(A_i\) è l'attributo preso in considerazione, \(v\) è il numero di valori distinti assunti da tale attributo, e \(D_1, D_2, \ldots, D_v\) sono i sottoinsiemi della partizione ottenuta.

Una volta che ho fatto questo per tutte le features seleziono la feature che minimizza l'entropia totale, o, equivalentemente, che massimizza l'information gain (mutual information), dove l'information gain è definito nel seguente modo

\[IG(D, A_i) = H(D) - H_{A_i}(D)\]

ovvero è la differenza tra la prior entropy e l'entropy rispetto all'attributo selezionato.

Osserviamo che per applicare queste funzioni di suddivisione gli attributi devono necessariamente essere categoriali.

Se abbiamo a che fare con features numeriche quindi, dobbiamo quindi effettuare un processo di discretizzazione delle features. Andandoli a discretizzare è possibile qindi utilizzare la stessa features più volte a vari livelli del nostro decision tree.

L'algoritmo finale è quindi un algoritmo greedy, che applica il paradigmo divide-et-impera ed è caratterizzato da:

• Si assume di lavorare con attributi con valori discreti (categoriali).

• L'albero è costruito in modo ricorsivo.

• All'inizio tutti gli esempi del training set sono messi nella radice.

• Gli esempi sono partizionati in modo ricorsivo selezionato attributo dopo attributo.

• L'attributo utilizzato per la partizione ad ogni step è l'attributo che massimizza l'information gain rispetto alla baseline.

• Termino quando una partizione contiene tutte istanze della stessa classe; o quando non ci sono più attributi da utilizzare.

• Una volta che termino associo alle istanze della partizione la classe più frequente.

L'algoritmo descritto è chiamato J48. Segue il relativo pseudo-codice

Notiamo come nello pseudo-codice dell'algoritmo è presente un parametro chiamato threshold, che mi permette di stabilire se non c'è nessun attributo che riesce ad ottenere dei risultati significativamente migliori rispetto alla baseline calcolata. Nel caso in cui il gain è sotto la soglia infatti, è inutile aumentare la complessità del modello.

Il principale svantaggio di questo tipo di modelli è che la loro complessità dipende dal numero di features.

Weka utilizza il formato ARFF per processare i datasets. Esempio di dataset ARFF: iris.arff .

Il dataset è il tipico iris dataset , menzionato nel classico articolo di Fisher intitolato "The use of multiple measurements in taxonomic problems".

Il formato ARFF per specificare il dataset iris inizia con le seguenti linee

@RELATION iris

@ATTRIBUTE sepallength	REAL
@ATTRIBUTE sepalwidth 	REAL
@ATTRIBUTE petallength 	REAL
@ATTRIBUTE petalwidth	REAL
@ATTRIBUTE class 	{Iris-setosa,Iris-versicolor,Iris-virginica}

successivamente poi troviamo i dati effettivi, in cui ogni riga corrisponde ad una istanza, e ogni istanza ha 5 colonne, di cui quattro sono valori reali e uno è il valore della classe. Notiamo che i dati sono di training, e quindi sono etichettati.

@DATA
5.1,3.5,1.4,0.2,Iris-setosa
4.9,3.0,1.4,0.2,Iris-setosa
4.7,3.2,1.3,0.2,Iris-setosa
4.6,3.1,1.5,0.2,Iris-setosa
5.0,3.6,1.4,0.2,Iris-setosa
5.4,3.9,1.7,0.4,Iris-setosa
4.6,3.4,1.4,0.3,Iris-setosa
5.0,3.4,1.5,0.2,Iris-setosa
4.4,2.9,1.4,0.2,Iris-setosa
4.9,3.1,1.5,0.1,Iris-setosa
5.4,3.7,1.5,0.2,Iris-setosa
...
6.5,3.0,5.2,2.0,Iris-virginica
6.2,3.4,5.4,2.3,Iris-virginica
5.9,3.0,5.1,1.8,Iris-virginica

Per quanto riguarda il training, possiamo applicare quattro opzioni:

• percentage-split: applica dello shuffle. In ogni caso comunque i risultati ottenuti potrebbero non essere robusti. La cross-validation ci permette di ottenere dei risultati più robusti.

• use training set:

• Supplied test set:

• n-fold cross-validation: permette di avere \(n\) misure di \(n\) sottoinsiemi del dataset dato. Il modo in cui poi utilizzo queste n misure dipende da quello che voglio fare. Nel caso di WEKA la cross-validation viene effettuata solamente sul training.

Problema di question classification: capire che tipo di informazione voglio avere data una domanda.

Come abbiamo già detto, la proprietà più interessante dell'utilizzo degli alberi di decisioni è il fatto che una volta costurito l'albero è trasparente, nel senso che è possibile leggere le regole di inferenza apprese che veranno utilizzate per classificare i vari elementi.

Tramite weka poi siamo in grado di visualizzare tale albero.