Tecniche di classificazione

Esistono varie tecniche per classificare un insieme di oggetti. Tra queste, le più importanti sono:

• Classificazione basata su alberi di decisione. Prevede la costruzione di un albero i cui nodi interni sono condizioni sugli attributi, i nodi foglia rappresentano le classi da predire; un percorso dalla radice ad un nodo foglia descrive le caratteristiche che un oggetto deve avere per appartenere alla classe che etichetta la foglia in quel particolare percorso.

• Bayesian Classifiers. E’ un classificatore statistico. Si calcola la probabilità che un dato oggetto appartenga ad una classe come probabilità condizionale. Esistono due classificatori bayesiani: naive bayesian classifier e bayesian

belief networks. Il primo assume che l’effetto di un attributo su una data

classe sia indipendente dal valore degli altri attributi. Il secondo consente la rappresentazione di dipendenze tra sottoinsiemi di attributi.

• Classificazione basata su regole associative. Si cercano pattern frequenti all’interno del training set che possano essere utilizzati per la classificazione.

3.11.1 Alberi di decisione

La tecnica di classificazione scelta in questo lavoro di tesi è quella basata su alberi di decisione. E’ il metodo più semplice per classificare degli oggetti in un numero finito di classi. Un algoritmo di classificazione di questo tipo prevede due fasi:

1. Costruzione dell’albero di decisione.

2. Utilizzo dell’albero di decisione costruito per predire la classe di appartenenza di un particolare oggetto.

L’albero di decisione è un diagramma con struttura ad albero, dove i nodi interni rappresentano test sugli attributi e i nodi foglia rappresentano le classi. Lo pseudocodice di un tipico algoritmo per la generazione di un albero di

decisione è riportato in figura 3.7. Si tratta di una versione dell’algoritmo ID3 [Han00].

Figura 3.7 Pseudocodice di un algoritmo per la generazione di un albero di decisione

L’albero iniziale è costituito da un unico nodo che rappresenta il training

sample. Se le tuple appartengono tutte alla stessa classe, il nodo diventa una

foglia ed è etichettato con questa classe; altrimenti l’algoritmo usa una misura basata su entropia detta information gain che seleziona l’attributo che meglio separa le tuple in classi individuali. Questo attributo diventa l’attributo “test” o “decision” del nodo. E’ l’attributo con information gain massimo, cioè quello che minimizza le informazioni necessarie per classificare le tuple nelle partizioni (sottoalberi) risultanti. Viene creato un ramo per ogni valore conosciuto dell’attributo “test” e le tuple sono suddivise in accordo a questi valori. Si assume che gli attributi siano a valori discreti. Gli attributi a valori continui vanno discretizzati.

Il processo ricorsivo di partizionamento si ferma quando è verificata una delle seguenti condizioni:

1. Tutte le tuple per un dato nodo appartengono alla stessa classe.

2. Non ci sono attributi (tra quelli rimanenti) per i quali si possano fare ulteriori partizioni.

3. Non ci sono tuple per il ramo test-attribute= ai . In questo caso viene creata

una foglia etichettata con la classe che occorre più spesso.

Una volta costruito l’albero di decisione, lo si può utilizzare per predire la classe di appartenenza di oggetti privi di etichetta di classe. Si segue un percorso dal nodo radice ad un nodo foglia e ad ogni passo si va in un particolare sottoalbero, se l’arco che porta ad esso è etichettato con una condizione su un attributo soddisfatta dalla tupla da classificare.

Una descrizione dettagliata dell’algoritmo di classificazione utilizzato in questa tesi è fornita in [Rug04].

Esempio 3.3

Una compagnia assicurativa vorrebbe una procedura che sia in grado di segnalare se un nuovo cliente è a rischio. Dispone di un training set, contenente i dati relativi ai propri clienti. Tra gli attributi l’età dell’utente e il tipo di autoveicolo. L’etichetta di classe è il livello di rischio per un particolare soggetto. Per la classe sono previsti due valori: “Alto” e “Basso”. L’etichetta di classe è stata assegnata sulla base degli incidenti in cui è stato coinvolto il cliente.

In figura 3.8 è riportato il training set ed il relativo albero di decisione.

Figura 3.8 Esempio di classificazione mediante un albero di decisione

Supponiamo che ci sia un nuovo potenziale cliente per la compagnia assicurativa, di 45 anni che possiede una macchina di tipo familiare: in base all’albero di decisione il rischio associato a questo soggetto è basso, quindi può essere accettato come nuovo cliente.

3.11.2 Alberi di decisione: Tree Pruning

L’albero di decisione generato a partire da un insieme di dati, può non essere completamente corretto. Nel valutare l’accuratezza di quest’albero, bisogna tener conto dell’errore associato ai dati ed in particolare bisogna prendere in

Età Tipo Autoveicolo Rischio Cliente 1 18 Sportiva Alto

Cliente 2 43 Familiare Basso Cliente 3 68 Familiare Basso Cliente 4 32 Autocarro Basso Cliente 5 23 Familiare Alto Cliente 6 18 Familiare Alto Cliente 7 20 Familiare Alto Cliente 8 45 Sportiva Alto Cliente 9 50 Autocarro Basso Cliente 10 64 Autocarro Alto Cliente 11 46 Familiare Basso Cliente 12 40 Familiare Basso

considerazione la possibilità che tra i dati ci sia “rumore”. Il suo mancato rilevamento si riflette sull’albero e sulla sua accuratezza. I metodi di pruning hanno come scopo quello di modificare l’accuratezza dell’albero, per tener conto di rumore che può essere presente nei dati; a tale scopo si eliminano rami dell’albero meno affidabili. Esistono due diversi approcci per realizzare il clustering: approccio prepruning e approccio postpruning. Nel primo caso, il pruning viene realizzato in fase di costruzione dell’albero, decidendo per esempio dato un nodo di non partizionare ulteriormente un dato insieme di tuple. In questo caso il nodo diventa una foglia.

Con il secondo approccio, il pruning viene realizzato dopo che l’albero è stato generato. In questo caso il pruning consiste nel rimuovere un ramo di un certo nodo.