Sol. Shapes Problem

Only AI members
Il Problema

In un impianto industriale per la lavorazione del legno un particolare macchinario deve eseguire una qualche operazione solo sui tagli quadrati. Le tavole non arrivano al macchinario in modo ordinato: prima del macchinario sono stati introdotti dei sensori ottici ed una unità di pre-processing the forniscono una descrizione del pezzo in arrivo sotto forma di una poligonale:

 

I pezzi possono avere diversa dimension e forma irregolare. Poiché non vengono caricati in modo ordinato possono trovarsi in posizioni diverse del nastro trasportatore.

Si richiede di mettere a punto una soluzione basata su alberi decisionali per il riconoscimento dei pezzi su cui occorre intervenire (i quadrati). L'obiettivo è apprendere un albero decisionale J48 con il 100% di accuratezza sia sul training set che sul validation set.

Materiale e procedimento
  • Dataset in formato "grezzo" [zip]
  • Script Python per ottenre un arff dal formato grezzo [zip]
  • Presentazione dell'esercitazione su alberi decisionali (contiene alcuni cenni su Python) [pdf]

Modificando lo script python è possibile estrarre features a partire dal dataset grezzo. La scelta delle features da utilizzare come input per l'algoritmo di apprndimento dell'albero decisionale influenza moltissimo l'efficacia del classificatore. In secondo luogo, è possibile modificare i parametri dell'algoritmo di apprendimento dell'albero (J48) per migliorare i risultati.

Una Possible Soluzione

L'elemento di maggior difficoltà per il riconoscimento delle forme è la presenza di "sbeccature" sugli angoli, che ne alterano le proprità geometriche. Un metodo efficace per affrontare il problema consistente perciò nell'eliminare tali sbeccature. Questo può essere fatto rimuovendo alcuni vertici dalla poligonale, nel caso la distanza dal vertice precedente sia troppo piccola. Dal momento che le forme hanno diversa dimensione, un distanza è "troppo piccola" se lo è rispetto ad una misura di riferimento (per esempio il lato più lungo della figura). 

Le altre features utilizzate sono:

  • numero di lati
  • media e deviazione standard della lunghezza relativa di un lato (lunghezza/lato più lungo)
  • numero di angoli
  • media e deviazione standard dell'ampiezza degli angoli

Tutte le features sono calcolate sulla poligonale con le sbeccature rimosse. L'albero decisionale che si ottiene con i parametri di deafult di J48 è:

Che  ottiene il 100% di accuratezza sia sul training che sul test set. Questo NON significa che l'albero sia "perfetto", ma è un ottimo indice di performance. Intuitivamente, l'abero verifica che:

  • I lati siano più o meno tutti uguali
  • Ci siano 4 lati
  • Gli angoli siano più o meno tutti uguali

Segue il materiale della soluzione:

  • Lo script Python della soluzione [zip]

 

Un gruppo di studenti ha presentato una soluzione molto interessante, che porta ad un solo errore di classificazione sul validation set (con un albero J48 unpruned). L'idea principale è quella di confrontare l'area della poligonale (con le sbeccature) con l'area che avrebbe un quadrato con lato di lunghezza pari a quella della più lunga distanza tra due vertici. 

  • Lo script per l'estrazione delle features (Montanari, Ghinassi, Tagliapietra) [zip]