Evoluzione genetica applicata agli alberi di classificazione 3. ID3, C4.5 e J48 (e Cart)

ID3, C4.5 e J48

ID3 e C4.5 [cit. Quinlan1993 ] sono algoritmi per costruire alberi di decisione a partire da dataset.

Nella formulazione originale il dataset è costituito da record consistenti in una lista di coppie attributo-valore e dalle classi associate ai record. Il training set è quindi costituito da un insieme S={s₁ , s₂ ... sₙ} di sample già classificati, dove ogni sample è un vettore del tipo ( x₁, x₂ , ... , xₚ ), ogni x_j rappresenta una feature del sample e s_j la classe di appartenenza.

In ID3 i valori sono discreti e la classe binaria. In C4.5 si è aggiunto il supporto per dati continui e classi multiple; si sono aggiunte, inoltre, tecniche di pruning che permettono di semplificare l’albero e di ridurre l’overfitting.

C4.5 permette di creare sia alberi con split binario sia alberi che eseguono split multipli sulle features discrete.

J48 è un porting di C4.5 in Java contenuto dentro il framework Weka [cit. hall2009weka ].

C4.5 con split binario applicato sul famoso dataset Fisher-Iris e relative curve di partizionamento, si notano i tipic split successivi sullo stesso attributo in livelli contigui tipici degli split binari. Albero generato con C4.5 che presenta uno split binario su dati continui e uno split multiplo su dati categorici.

Entropia e Gain-Ratio

C4.5 misura l’impurità attraverso l’entropia.

L’entropia di Shannon H di una variabile discreta X che assume valori discreti {x₁ , x₂ ... xₙ} le cui probabilità sono P={p₁ , p₂ ... pₙ} è definita come:

$$H(P)=-\sum _{ i=1 }^{ n }{ p_{ i }\cdot log(p_{ i }) }$$

La formula può essere spiegata in questo modo: se ci sono n messaggi possibili ognuno dei quali ha probabilità p=1 / n, allora il valore H(x)=log(n) rappresenta l’informazione contenuta nel messaggio. Questo concetto è applicato ai dataset, Sia T un training set costituito da elementi preclassificati in C_k classi, possiamo definire le probabilità P={p₁ , p₂ , ... , pₙ} come

$$P = (\frac{|C_1|}{|T|}, \frac{|C_2|}{|T|}, ..., \frac{|C_k|}{|T|})$$

A questo punto l’informazione associata al training set T può essere definita come

$$Informazione(T)=H(T)$$

Se si effettua uno split di T in base al valore di un attributo X, supponendolo per semplicità discreto e categorico, si ottiene un nuovo partizionamento di T in (T₁ , T₂ , ... , Tₙ); a questo punto l’informazione necessaria per identificare la classe di un elemento di T è

$$Informazione(X,T)= \sum_{i=1}^n \frac{ |T_i|\cdot Informazione(T_i) }{|T|}$$

Si può quindi definire il guadagno di informazione (Gain) relativo a uno split come $$Gain(X,T)=Informazione(T)-Informazione(X,T)$$

Questo stimatore però tende a favorire gli attributi che sono particolarmente numerosi, [cit. Quinlan1993 ] suggerisce quindi di utilizzare un GainRatio definito in questo modo: $$GainRatio(X,T)= \frac{Gain(X,T)}{SplitInfo(X,T)},$$ dove lo SplitInfo(X,T) rappresenta l’informazione persa durante lo split sul valore discreto X. Supponendo uno split in T=(T₁ , T₂ , ... , Tₙ) dovuto al valore di X, lo SplitInfo viene calcolato come l’entropia di questa distribuzione utilizzando l'equazione definita sopra.

L’estensione di questo meccanismo ai valori continui viene effettuata costruendo un test binario x > α dove α è una costante che viene scelta in modo da massimizzare il GainRatio, che viene quindi calcolato sull’intera distribuzione dei valori univoci della variabile.

CART

Anche se non verranno utilizzati in questa tesi, è il caso di introdurre brevemente i CART. CART è un acronimo di “Classication And Regression Trees”[cit. BreimanEtAl:84 ]. Un albero CART viene costruito in modo Greedy come per gli alberi C4.5 ma il tipo di albero prodotto è sostanzialmente differente.

• CART produce alberi a split binario su attributi continui (o discreti trattati come continui).

• Il criterio di split si basa sull’indice di Gini [cit. BreimanEtAl:84 ], che ha il vantaggio di poter essere utilizzato bene anche per problemi di regressione.

Precedente Successivo