Integriamo all‘interno del framework Weka un generico algoritmo di classificazione. Come caso di studio analizzeremo un semplice schema di apprendimento basato su un albero di decisione e ne implementeremo una semplice versione che estende gli algoritmi di classificazione di Weka.

Alberi di decisione

Un albero di decisione (o “decision tree”) accetta come input un oggetto od una situazione descritta da un insieme di proprietà  e restituisce in output una “decisione” costituita da un valore booleano. In realtà , è possibile anche implementare alberi di decisione in grado di rappresentare un range di output più ampio, ma in questa trattazione ci limiteremo, per semplicità , ai decision tree booleani [1][4].

 

 

Figura 1 - Esempio di albero di decisione: al ristorante… aspettare o meno?

 

Ogni nodo interno dell‘albero corrisponde al test del valore di una delle proprietà , e i nodi dell‘albero sono etichettati con i possibili esiti di tale test (nel nostro caso booleano solo “true” e “false”). Ogni nodo foglia dell‘albero è etichettato con il valore da riportare nel caso in cui sia raggiunta la foglia. Purtroppo gli alberi di decisione sono fortemente limitati: infatti, a causa della loro natura essenzialmente proposizionale, sono implicitamente condannati a riferirsi ad un unico oggetto. Se vogliamo rappresentare con un albero di decisione l‘algoritmo che ci porterà  a scegliere o meno un paio di scarpe sulla base del prezzo più basso e ci sono 200 modelli diversi di scarpe tra cui scegliere, sarà  necessario creare un albero di decisione di grandissima profondità , poiché si dovranno confrontare tutti i prezzi con tutti gli altri. Per alcune particolari funzioni questo è un grosso problema: le più famose sono la funzione di parità , che restituisce “true” solo se un numero pari di input è “true” (1), e la funzione di maggioranza, che restituisce “true” più della metà  degli input sono “true”. In entrambi i casi sarà  necessario un albero con un numero di foglie esponenziale con base 2 rispetto alla dimensione dell‘input (n).
Quante funzioni ci sono in questo insieme? Esattamente quante sono le volte di verità  che siamo in grado di scrivere, poiché una funzione binaria è completamente definita dalla sua tavola di verità . poiché l‘input di ognuna di queste funzioni è composto da n attributi, ognuna delle tavole di verità  avrà Ã‚ Â  righe (tutte le combinazioni possibili su n bit). Se sono necessari bit per definire una funzione, ciò vuol dire che ci sono differenti funzioni su n attributi.

 

Il problema: creare nuova informazione

Finora abbiamo creato il nostro albero di decisione, ma non abbiamo ancora detto nulla su come affrontare problemi che il nostro povero agente non ha mai dovuto affrontare. Fin qui, in realtà , abbiamo utilizzato i decision tree semplicemente come una struttura di dati nella quale memorizzare l‘algoritmo che il nostro programma deve eseguire per fornire in output un valore di verità .
L‘obiettivo è quello di estrapolare un pattern dalle nostre osservazioni, in modo da poter far fronte a problemi cui non ci siamo mai trovati davanti. Un pattern, in realtà , non è altro che un modo coinciso per rappresentare un gran numero di casi. Un esempio banale di un pattern utilizzato per rappresentare un concetto in modo coinciso è fornito da una banale espressione regolare.
Una funzione è un altro esempio di metodo per la rappresentazione in modo fortemente coinciso di un concetto: ad esempio la funzione x+1 è un modo molto conciso per rappresentare la corrispondenza tra infinite coppie di numeri (tutti i valori possibili per la variabile dipendente ed i rispettivi valori della variabile indipendente).
Dobbiamo quindi trovare un modo per reperire un albero decisionale piccolo e che “funzioni” con tutti i possibili input.

Dato un insieme di dati, ci sono solo poche ipotesi semplici che possono spiegare tali rilevazioni, e molte ipotesi complesse.
Ma poiché le ipotesi semplici sono molte di meno, è meno probabile che ci sia un‘ipotesi semplice in grado di spiegare tutti i dati sperimentali non essendo l‘ipotesi corretta. Da ciò possiamo concludere che è più probabile che una ipotesi semplice consistente con tutte le rilevazioni sia corretta rispetto ad un‘ipotesi complessa con le medesime caratteristiche.
Sfortunatamente, trovare il più piccolo albero di decisioni possibile è un problema intrattabile, mentre trovarne uno dei più piccoli è possibile mediante alcune semplici euristiche (ad esempio l‘information gain descritto nel seguito).

Un albero di decisione in Weka

Per capire come estendere il framework Weka [2] [3] con algoritmi personalizzati di classificazione, analizzeremo lo schema di apprendimento basato su alberi di decisone e lo integreremo all‘interno del workbench.

La classe che definisce il nuovo schema di classificazione deve estendere la classe Classifier:

public class MyDecisionTree extends Classifier
{
 private Id3[] m_Successors;
 private Attribute m_Attribute;
 private double m_ClassValue;
 private double[] m_Distribution;
 private Attribute m_ClassAttribute;
 
 public String globalInfo()
 {
  return "Classe per costruire un albero di decisione"
 }
 ...
}

 

Il primo metodo in MyDecisionTree è globalInfo(): mostra semplicemente la stringa che viene visualizzata nell‘interfaccia grafica di Weka quando lo schema di classificazione viene selezionato.

 

buildClassifier()

Il metodo buildClassifier() costruisce il classificatore da un insieme di training. In prima battuta controlliamo i valori degli attributi passati in training: gli attributi devono essere nominali e tutti valorizzati. Successivamente facciamo una copia del training set e chiamiamo un metodo da weka.core.Instances per cancellare tutte le istanze (instances) con valori di classe mancanti (infatti non possono far parte dell‘insieme di apprendimento). Infine chiamiamo il metodo makeTree(), il quale costruisce l‘albero di decisione ricorsivamente.

...
public void buildClassifier(Instances data) throws Exception
{
 if (!data.classAttribute().isNominal())
 {
  throw new UnsupportedClassTypeException
   ("Id3: le classi devono essere nominali.");
 }
 
 Enumeration enumAtt = data.enumerateAttributes();
 while (enumAtt.hasMoreElements())
 {
  if (!((Attribute) enumAtt.nextElement()).isNominal())
  {
   throw new UnsupportedAttributeTypeException
    ("Id3: gli attributi devono essere nominali.");
  }
 }
 
 Enumeration enum = data.enumerateInstances();
 while (enum.hasMoreElements())
 {
if (((Instance) enum.nextElement()).hasMissingValue())
  {
   throw new NoSupportForMissingValuesException
    ("Id3: non devono esserci valori mancati.");
  }
 }
 
 data = new Instances(data);
 data.deleteWithMissingClass();
 makeTree(data);
}
...

 

makeTree()

Il primo passo in makeTree() è controllare se il dataset è vuoto, se lo è viene creata una foglia settando mAttribute a null. Il valore della classe mClassValue assegnato alla foglia è settato come assente e la probabilità  stimata per ogni classe del dataset in mDistribution è inizializzata a 0. Se le istanze di training sono presenti, il metodo makeTree() trova gli attributi che contengono l‘information gain più alto.
Il metodo computeInfoGain() calcola l‘information gain di ogni attributo e lo memorizza in un array (vedi sottoparagrafo successivo).
In ottica ricorsiva, il metodo makeTree() costruisce un array di oggetti MyDecisionTree, uno per ogni valore dell‘attributo e chiama makeTree() su ognuno passandogli in input il relativo dataset.

...
private void makeTree(Instances data) throws Exception
{
 // Controlla se non ci sono istanze che raggiungono questo nodo
 if (data.numInstances() == 0)
 {
  mAttribute = null;
  mClassValue = Instance.missingValue();
  mDistribution = new double[data.numClasses()];
 }
 
 // Calcola il valore di Information Gain
 double[] infoGains = new double[data.numAttributes()];
 Enumeration attEnum = data.enumerateAttributes();
 while (attEnum.hasMoreElements())
 {
  Attribute att = (Attribute) attEnum.nextElement();
  infoGains[att.index()] = computeInfoGain(data, att);
 }
 mAttribute = data.attribute(Utils.maxIndex(infoGains));
 
 // Crea una foglia se l‘Information Gain è pari a 0
 // visita i successori altrimenti
 
 if (Utils.eq(infoGains[mAttribute.index()], 0))
 {
  mAttribute = null;
  mDistribution = new double[data.numClasses()];
  Enumeration instEnum = data.enumerateInstances();
  
  while (instEnum.hasMoreElements())
  {
   Instance inst = (Instance) instEnum.nextElement();
m_Distribution[(int) inst.classValue()]++;
  }
  
  Utils.normalize(m_Distribution);
  mClassValue = Utils.maxIndex(m_Distribution);
  mClassAttribute = data.classAttribute();
 } else {
  Instances[] splitData = splitData(data, mAttribute);
  mSuccessors = new Id3[mAttribute.numValues()];
  
  for (int j = 0; j < mAttribute.numValues(); j++)
  {
   mSuccessors[j] = new Id3();
   mSuccessors[j].makeTree(splitData[j]);
 } }
}
...

 

computeInfoGain()

Il metodo computeInfoGain() calcola il guadagno di informazione (IG)  associato all‘attributo in esame attraverso il calcolo dell‘entropia di informazione (E):

ÂÂ

Il metodo splitData divide il dataset in sottoinsiemi mentre computeEntropy calcola l‘entropia di informazione delle istanze passate in input.

private double computeInfoGain(Instances data, Attribute att) throws Exception
{
 double infoGain = computeEntropy(data);
 Instances[] splitData = splitData(data, att);
 for (int j = 0; j < att.numValues(); j++)
 {
  if (splitData[j].numInstances() > 0)
  {
   infoGain -= ((double) splitData[j].numInstances() /
   (double) data.numInstances()) *
   computeEntropy(splitData[j]);
  }
 }
 return infoGain;
}

 

classifyInstance()

Finora abbiamo esaminato come viene costruito un albero di decisione, ora vediamo come utilizzare tale struttura per classificare un‘istanza.
Ogni classificatore deve implementare un metodo classifyInstance() oppure un metodo distributionForInstance(). La classe Classifier contiene un‘implementazione di default per entrmbi metodi:

• se la classe è nominale, la predizione ricade sulla classe con il valore massimo di probabilità  (tale calcolo avviene mediante l‘utilizzo dell‘array restituito dal metodo distributionForInstance())
• se la classe è numerica, distributionForInstance() restituisce un array composto da un solo valore che classifiInstance() estrae e restituisce per la predizione.

public double[] distributionForInstance(Instance instance) throws   NoSupportForMissingValuesException
{
 if (instance.hasMissingValue())
 {
  throw new NoSupportForMissingValuesException
   ("Id3: non sono accettati valori assenti.");
 }
 
 if (mAttribute == null)
 {
  return mDistribution;
 } else {
  return mSuccessors[(int) instance.value(mAttribute)];
  distributionForInstance(instance);
 }
 }
 
 ...
 
 public double classifyInstance(Instance instance) 
   throws NoSupportForMissingValuesException
 {
  if (instance.hasMissingValue())
  {
   throw new NoSupportForMissingValuesException
   ("Id3: non sono accettati valori assenti.");
 }
 if (m_Attribute == null)
 {
  return m_ClassValue;
 } else {
  return m_Successors[(int) instance.value(m_Attribute)];
  classifyInstance(instance);
 }
}

Conclusioni

In questo articolo abbiamo analizzato come integrare un semplice schema di apprendimento/classificazione basato su alberi di decisione all‘interno del framework weka.
Nel prossimo e ultimo articolo della serie, vedremo come realizzare un sistema per distribuire il processo di classificazione su più calcolatori.

 

Riferimenti

[1] I. Witten & E. Frank, “Data Mining: Practical Machine Learning Tools and Techniques with Java Implementation” , Morgan Kauffman, 2005

 

[2] Weka Home Site
http://www.cs.waikato.ac.nz/ml/weka/

 

[3] Weka Sourceforge Site
http://sourceforge.net/projects/weka/

 

[4] Paolo Giudici, “Data Mining. Metodi informatici, statistici e applicazioni”, McGraw-Hill 2005