WEKA: l'approccio intelligente all'esplorazione dei dati

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].

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";
  }

  ...
}

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); }

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));
  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]);
    }
  }
}

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; }

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 (mAttribute == null) { return mClassValue; } else { return mSuccessors[(int) instance.value(mAttribute)] .classifyInstance(instance); } }