Evoluzione genetica applicata agli alberi di classificazione
2. Machine learning e classificazione supervisionata

128x128



Machine learning e classificazione supervisionata

Un programma apprende da una certa esperienza E se: nel rispetto di una classe di compiti T, con una misura di prestazione P, la prestazione P misurata nello svolgere il compito T è migliorata dall’esperienza E. [cit. bishop2006pattern ]

L’obiettivo principale del “machine learning” è quello di fare in modo che le macchine manifestino un comportamento che, se esibito dall’uomo, implicherebbe l’uso dell’intelligenza. Si occupa in particolare della progettazione e dello studio di sistemi che possano apprendere conoscenza attraverso l’analisi dei dati in modo da poter riconoscere automaticamente modelli complessi ed essere in grado di prendere decisioni. In questa tesi ci si occupa in particolare di due approcci al machine learning e al modo in cui possano essere utilizzati insieme.

Il problema della classificazione

Uno degli scopi principali del Machine Learning è la classificazione, cioè il problema di indentificare la classe di un nuovo obiettivo sulla base di conoscenza estratta da un training set.\ Un sistema che classifica è detto classificatore. I classificatori estraggono dal dataset un modello che utilizzano poi per classificare le nuove istanze. Se una singola istanza può essere espressa come un vettore in uno spazio numerico $R^n$ il problema della classificazione può essere ricondotto alla ricerca delle superfici chiuse che delimitano le classi.

Esempi di classificazioni dello stesso dataset, a sinistra un classificatore basato su rette, a destra uno basato su parabole

Esistono molte tecniche per costruire un classificatore, in questa tesi si tratterà in particolare l’uso di Alberi di Decisione.

Alberi di decisione

Un albero di decisione è un classificatore implementato attraverso una struttura ad albero; è quindi costituito da una struttura gerarchica che applica una strategia “dividi et impera” per classificare i dati. Data la sua struttura di albero può essere facilmente convertito in un set di regole, permettendo così di estrarre conoscenza. La ricerca delle curve che delimitano le classi viene ricondotta alla ricerca ricorsiva di punti di split.

Ogni nodo interno rappresenta un vincolo che porta a una scelta determinando uno split, e ogni foglia indica la classe di appartenenza dell’elemento. Gli alberi sono tipicamente costruiti con strategie Greedy, che individuano di volta in volta il punto più conveniente in cui effettuare lo split.

Utilizzo di un albero per classificare un generico dataset, con $W_{10}$ si riesce a separare una zona completamente classificata da una ancora da classificare. la ricerca del punto di split viene poi reiterata sulla parte restante finchè l'intero spazio dei dati è stato classificato. In questo caso bastano due nodi decisionali(adattato da [cit. Alpaydin2004 ])

In base al tipo di split gli alberi di decisione si possono dividere in binari e non binari.

In base al tipo di vincolo gli alberi si possono dividere in ortogonali e obliqui:

in quelli ortogonali (o axix-parallel) il vincolo è rappresentato da una condizione espressa su una sola dimensione, portando lo spazio di ricerca ad una divisione in sottoparti delimitate da segmenti paralleli agli assi e quindi in iperrettangoli;

in quelli obliqui, invece, la condizione è espressa attraverso una combinazione lineare di un sottoinsieme delle dimensioni, portando lo spazio di ricerca ad una divisione in sottoparti delimitate da segmenti non paralleli agli assi.

Gli alberi binari, e in particolare quelli ortogonali e binari, sono i più utilizzati e i più studiati in letteratura, sia per la loro facilità di implementazione sia per la maggiore facilità di lettura (nel caso in cui siano adatti al dataset). Uno split binario, inoltre, decima più lentamente i dati rispetto a uno split multiplo, rallentando dunque il fenomeno dell’overfitting [cit. hastie2005elements ].

L’uso di alberi binari ha però degli svantaggi:

  • Nel caso di split su attributi categorici è spesso naturale uno split multiplo sulle varie categorie, questo viene riprodotto con una serie di split binari consecutivi che risultano poco leggibili.

  • In alcuni casi non esistono sequenze di split binari in grado di avere gli stessi comportamenti di uno split multiplo, possono quindi\ esistere casi in cui non esistono split binari buoni quanto quelli multipli e questo può portare ad alberi meno performanti a parità di nodi. [cit. kononenko1995counter ] e [cit. Kohavi99decisiontree ]

Illustrazione degli alberi ortogonali e obliqui, [cit. journals/tsmc/BarrosBCF12 ]

La parte cruciale degli algoritmi che creano alberi è la scelta del punto di split.

Negli alberi usati per classificazione la scelta del punto di split è guidata da misurazioni di impurità, di conseguenza gli indici tipicamente utilizzati sono l’indice di Gini o misure basate sull’entropia.

Qualunque sia l’indice, la costruzione di un albero può essere vista come una serie di scelte dei punti di taglio che portano a una maggiore diminuzione dell’impurità. Il difetto maggiore di questo approccio Greedy, oltre a quello di portare a soluzioni sub ottimali, è il fatto che il dataset utile si riduce a ogni scelta; questo porta i nodi più profondi ad agire su pochi dati, provocando quindi overfitting. Costruire alberi su dataset molto grandi, inoltre, richiede spesso memorie considerevoli, di conseguenza per aggirare l’overfitting si è pensato di mediare i risultati di alberi generati su diverse partizioni del dataset (ensemble of trees [cit. series/synthesis/2010Seni ]). In questo modo, tuttavia, si perde la facilità di lettura tipica degli alberi; come vedremo in seguito, gli algoritmi evolutivi costituiscono una migliore soluzione da questo punto di vista.

I due algoritmi più noti per la costruzione di alberi sono CART (Classification and Regression Trees) e ID3 con le sue successive evoluzioni (C4.5, C5.0 ). [cit. BreimanEtAl:84 ] [cit. Quinlan1993 ]

Il fenomeno del Overfitting

Il fenomeno dell’overfitting si verifica quando un sistema di classificazione, agendo su un dataset non sufficientemente grande, crea un modello che si adatta ai dati osservati utilizzando un numero eccessivo di parametri. Il modello ottenuto risulta efficace nel training set utilizzato per generarlo ma poco generalizzabile. L’efficacia nel training set è data dal fatto che esso era così ristretto da permettere la costruzione di un modello che vi si adatta perfettamente, basato tuttavia su scelte che sono globalmente sbagliate.

Alberi di Regressione

Un albero di regressione è molto simile a un albero di classificazione, con la differenza che il suo output non è una classe ma un numero reale. Un albero di regressione è costruito quasi allo stesso modo di un albero di classificazione, con la fondamentale differenza che la misura dell’impurità è sostituita con una stima dell’errore, che è tipicamente derivata dallo scarto quadratico medio.

Pruning

Il pruning degli alberi di classificazione ha due finalità: ridurre la dimensione dell’albero prodotto e cercare di ridurre l’overfitting. Il pruning può essere applicato durante la costruzione (prepruning) o a costruzione ultimata (postpruning). Il secondo metodo è il più utilizzato, poiché permette di valutare i risultati del pruning avendo a disposizione l’intero albero.

Prepruning

Il prepruning è una tecnica che consiste nel fermare lo split del dataset se si scende sotto una certa percentuale della dimensione del dataset iniziale, tipicamente intorno al 5%. La motivazione di tale scelta è che, altrimenti, le decisioni sarebbero prese su un set troppo piccolo e potrebbero non essere generalizzabili all’intero dataset (l’overfitting descritto prima).

Postpruning

Il postpruning è il tipo di pruning più usato. Gli alberi di classificazione sono costruiti in modo Greedy, questo implica che ogni volta che si trova un punto di split si crea un nodo decisionale e si ripete la procedura sul sottoalbero, senza possibilità di fare backtrack e modificare le scelte fatte. Il postpruning cerca in parte di correggere gli errori fatti da una costruzione Greedy, andando a identificare e potare i rami non necessari. Una volta che viene identificato un ramo potenzialmente inutile, si cerca di sostituirlo con una foglia associata al valore a cui conducono le foglie del ramo. Se la sostituzione produce una perdita in prestazioni trascurabile rispetto al guadagno in complessità, il ramo viene sostituito con la foglia, altrimenti lo si mantiene.


Precedente Successivo


Copyright © 2014 Vincenzo La Spesa

Torna su