Algoritmi di Classificazione degli Alberi

Alberi di decisione

• Alberi di decisione sono un metodo di apprendimento supervisionato per la classificazione.
• L'obiettivo è costruire un modello predittivo che preveda una classe basandosi su delle caratteristiche.
• Iniziano da un nodo radice e si diramano in nodi interni (che rappresentano decisioni) fino a raggiungere dei nodi terminali (che rappresentano le classi previste).
• Queste decisioni vengono prese basandosi su condizioni di test, che sono determinate in base agli attributi della classe di addestramento.
• Diverse partizioni degli attributi possono generare alberi diversi con la stessa accuratezza.
• L'albero di decisione viene addestrato su dati di addestramento, dopodiché applicato ai dati senza etichetta per prevedere la classe.
• Le condizioni di test possono includere attributi categorici o continui.
• Il criterio di terminazione dell'albero è quando tutti i record appartengono alla stessa classe o quando tutti i record hanno lo stesso valore per tutti gli attributi.
• Ci sono diversi algoritmi per costruire alberi di decisione, alcuni dei più famosi sono CART, ID3 e C4.5.
• I nodi terminali sono indicati come foglie.
• Si inizia sempre dal nodo radice.
• Ogni nodo intermedio rappresenta una condizione di test.
• Ogni nodo terminale si applica alle istanze della classe.
• Le decisioni vengono prese con un approccio greedy.

Approccio di base: deduzione

• L'approccio di base per la deduzione consiste nell'addestramento e nell'applicazione di un modello.
• L'algoritmo impara da un insieme di addestramento, che contiene attributi e classi.
• Il modello crea un albero di decisione.
• Questo albero di decisione viene poi applicato a nuovi dati per fare previsioni.

Applicare un modello ai dati

• Iniziare dal nodo radice per analizzare le istanze.
• Se il nodo radice rappresenta un attributo categoriale (es. Home Owner), si valuta se l'istanza soddisfa la condizione del nodo.
• Se l'istanza soddisfa la condizione, procedere verso il ramo appropriato. Altrimenti, proseguire verso il ramo opposto.
• Se il nodo rappresenta un attributo continuo (es. Income), si valuta se il valore dell'istanza è maggiore o minore di un valore di soglia.
• Se il valore dell'istanza è maggiore, procedere verso il ramo appropriato. Altrimenti, proseguire verso il ramo opposto.
• Proseguire attraverso i nodi intermedi fino a raggiungere una foglia.
• La foglia identifica la predita della classe.

Algoritmo di Hunt

• Hunt è un algoritmo greedie per la costruzione di alberi di decisione.

• È un metodo iterativo.

• Inizia da tutto l'insieme di addestramento.

• Individua una condizione che meglio separa le classi.

• Se tutte le istanze appartengono alla stessa classe, il processo termina e il nodo risultante è una foglia.

• Altrimenti, il processo di suddivisione continua ricorsivamente per i sottoinsiemi.

Algoritmo di Hunt (cont.)

• Sia D₁ l’insieme di record d’addestramento che raggiunge il nodo t.
• Se D₁ contiene tutti record con la stessa classe yt, allora t è un nodo foglia con classe yt.
• Se D₁ contiene record che appartengono a più classi, determinare una condizione di test per scindere i dati in sottoinsiemi più piccoli. Applicare la procedura ricorsivamente a ogni sottoinsieme.

Decision Tree Induction

• Decision Tree Induction è una categoria di algoritmi per l'apprendimento della classificazione di alberi di decisione.
• Gli algoritmi più famosi di questa categoria sono:
• Algoritmo di Hunt
• CART
• ID3
• C4.5
• SLIQ
• SPRINT

Dettagli da specificare

• Criterio di scissione: Individua le possibili condizioni di test, dipendente dal tipo degli attributi, e selezionare il test migliore.
• Criterio di terminazione: il processo di costruzione dell'albero si interrompe quando tutti i record appartengono alla stessa classe o quando tutti i record hanno lo stesso valore per tutti gli attributi; si sceglie come etichetta la classe maggioritaria
• Si applica un criterio di terminazione anticipata?

Condizioni di test

• Dipendono dal tipo di attributo: Nominale, Ordinale, Continuo
• Dipendono dal numero di figli che vogliamo creare: Scissione a due vie (binaria), o Scissione a molte vie (multi-way split).

Test per attributi nominali

• Scissione a molte vie: Usare tanti figli quanti sono i possibili valori distinti dell'attributo.
• Scissione binaria: Dividere i possibili valori in due sottoinsiemi.

Test per attributi ordinali

• Scissione a molte vie: Usare tanti figli quanti sono i possibili valori distinti dell'attributo.
• Scissione binaria: Dividere i valori in due sottoinsiemi in modo da mantenere l'ordine tra i valori degli attributi.

Test per attributi continui

• Scissione binaria: (A ≤ v) or (A > v).
• Costoso dal punto di vista computazionale
• Partizionamento a molte vie: discretizza l'attributo in ordinale categoriale
  • Discretizzazione statica: viene effettuata una sola volta all'inizio del procedimento
  • Discretizzazione dinamica: viene ripetuta per ogni nodo, migliorando i risultati.

Misure di impurità di un nodo

• Indice di Gini, Entropia, Errore di classificazione

Indice di Gini

• Massimo 1−1/c quando i record sono distribuiti uniformemente tra le classi.
• Minimo 0 quando tutti i record appartengono alla stessa classe.

Entropia

• Massimo log₂c quando i record sono uniformemente distribuiti fra le classi.
• Minimo 0 quando tutti i record appartengono alla stessa classe.

Errore di classificazione

• Massimo 1−1/c quando i record sono distribuiti uniformemente tra le classi.
• Minimo 0 quando tutti i record appartengono alla stessa classe.

Come valutare la bontà di un test

• Approccio greedy: si preferiscono nodi con distribuzioni di classi omogenee
• Misura di impurità dei nodi: un valore più basso indica maggiore omogeneità.

Impurità di una partizione

• La misura di impurità di una partizione viene calcolata considerando i figli di quel nodo e la misura di impurità di ogni figlio.
• Questa misura deve essere più bassa dei nodi della partizione originale.

Scegliere il test migliore

• Si calcola la misura di impurità prima della suddivisione (P).
• Si calcola la misura di impurità della suddivisione (M).
• Si calcola il guadagno di purezza della suddivisione (P-M), e viene scelto il test che ottimizza questa differenza

Alberi di decisione obliqui

• Ci sono algoritmi di alberi di decisione obliqui.
• Queste reti sono più espressive ma più complesse di quelli tradizionali, perché utilizzano test con inclinazione rispetto agli assi dei lati.

Regressione Lineare

• Una tecnica che cerca la relazione lineare tra una variabile dipendente e una o più variabili indipendenti.
• La regressione lineare viene usata per modellare una relazione lineare tra le variabili.
• Si cerca la retta con i minimi residui in modo che i valori osservati e i valori predetti della variabile dipendente siano più vicini possibile alla retta ottenuta.
• Si usa la regressione lineare quando la relazione ha un andamento lineare.

Regressione Logistica

• È usata per prevedere un'uscita dicotomica basandosi su una o più variabili indipendenti.
• Utilizza una funzione logistica per stimare la probabilità di appartenenza alla classe.
• Misura la relazione non lineare tra un output dicotomico e un insieme di diversi input.
• La forma è simile alla regressione lineare

Reti Feed-Forward

• Una rete feed-forward a più strati ha più livelli di neuroni interconnessi.
• Le informazioni fluiscono in avanti, da uno strato all'altro, fino all'output.

Reti Convoluzionali

• Utilizzate per i dati nelle immagini, hanno strati specializzati per l'analisi con connessioni di tipo convoluzioni
• Questi strati permettono di cogliere la struttura spaziale nei dati (come un'immagine).

Long Short-Term Memory (LSTM)

• Sono reti neurali ricorrenti (RNN) specializzate per imparare le dipendenze a lungo termine nei dati.
• Utilizzano più gate e una struttura a cella per migliorare l'apprendimento di sequenze lunghe
• Sono di supporto per modellare dati sequenziali

IA Generativa: I Large Language Models (LLM)

• Sono modelli di deep learning che generano testo, rispondono a domande e traducono.
• Basati su reti neurali transformer.
• I transformer utilizzano meccanismi di attenzione per modellare il contesto e la rilevanza delle parole nella sequenza.