/*
* Id3.java
*/
import weka.core.*;
import java.io.*;
import java.util.*;
/**
* Clase que implementa un árbol ID3
*/
public class Id3 extends DistributionClassifier {
/** The node's successors. */
private Id3[] m_Successors;
/** Attribute used for splitting. */
private Attribute m_Attribute;
/** Class value if node is leaf. */
private double m_ClassValue;
/** Class distribution if node is leaf. */
private double[] m_Distribution;
/** Class attribute of dataset. */
private Attribute m_ClassAttribute;
/**
* Genera arbol ID3
*
* @param data Datos de entrenamiento
* @exception Exception Si el clasificador no puede ser creado
*/
public void buildClassifier(Instances data) throws Exception {
if (!data.classAttribute().isNominal()) {
throw new Exception("Id3: Solo clases nominales");
}
Enumeration enumAtt = data.enumerateAttributes();
while (enumAtt.hasMoreElements()) {
Attribute attr = (Attribute) enumAtt.nextElement();
if (!attr.isNominal()) {
throw new Exception("Id3: Solo atributos nominales");
}
Enumeration enum = data.enumerateInstances();
while (enum.hasMoreElements()) {
if (((Instance) enum.nextElement()).isMissing(attr)) {
throw new Exception("Id3: No pueden haber valores nulos");
}
}
}
data = new Instances(data);
data.deleteWithMissingClass();
makeTree(data);
}
/**
* Clasifica un instancia, utilizando el arbol ID3
*
* @param instance Instancia a ser clasificada
* @return La Clasificacion
*/
public double classifyInstance(Instance instance) {
if (m_Attribute == null) {
return m_ClassValue;
} else {
return m_Successors[(int) instance.value(m_Attribute)].
classifyInstance(instance);
}
}
/**
* Calcula la entropia del conjunto de datos
*
* @param data Los datos
* @return La entropia calculada
*/
private double computeEntropy(Instances data) throws Exception {
double [] classCounts = new double[data.numClasses()];
Enumeration instEnum = data.enumerateInstances();
while (instEnum.hasMoreElements()) {
Instance inst = (Instance) instEnum.nextElement();
classCounts[(int) inst.classValue()]++;
}
double entropy = 0;
for (int j = 0; j < data.numClasses(); j++) {
if (classCounts[j] > 0) {
entropy -= classCounts[j] * Utils.log2(classCounts[j]);
}
}
entropy /= (double) data.numInstances();
return entropy + Utils.log2(data.numInstances());
}
/**
* Calcula ganancia de informacion
*
* @param data Los datos
* @param att El atributos
* @return La ganancia de informacion para el atributo dado
*/
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;
}
/**
* Calcula distribucion utilizando arbol de decision
*
* @param instance La instancia dada
* @return La distribucion para la instancia
*/
public double[] distributionForInstance(Instance instance) {
if (m_Attribute == null) {
return m_Distribution;
} else {
return m_Successors[(int) instance.value(m_Attribute)].
distributionForInstance(instance);
}
}
/**
* Main method.
*
* @param args the options for the classifier
*/
public static void main(String[] args) {
try {
System.out.println(Evaluation.evaluateModel(new Id3(), args));
throw new Exception(Evaluation.evaluateModel(new Id3(), args));
} catch (Exception e) {
System.err.println(e.getMessage());
}
}
/**
* Metodo para crear arbol ID3
*
* @param data Los datos de entrenamiento
* @exception Exception Si no se puede crear arbol
*/
private void makeTree(Instances data) throws Exception {
// Ver que no hay instancias que han llegado a tal nodo
if (data.numInstances() == 0) {
m_Attribute = null;
m_ClassValue = Instance.missingValue();
m_Distribution = new double[data.numClasses()];
return;
}
// Calcular atributo con maxima ganancia de informacion
double[] infoGains = new double[data.numAttributes()];
Enumeration attEnum = data.enumerateAttributes();
while (attEnum.hasMoreElements()) {
Attribute att = (Attribute) attEnum.nextElement();
infoGains[att.index()] = computeInfoGain(data, att);
}
m_Attribute = data.attribute(Utils.maxIndex(infoGains));
// Crear hoja si ganancia es cero
// Sino, crear hijos
if (Utils.eq(infoGains[m_Attribute.index()], 0)) {
m_Attribute = null;
m_Distribution = 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);
m_ClassValue = Utils.maxIndex(m_Distribution);
m_ClassAttribute = data.classAttribute();
} else {
Instances[] splitData = splitData(data, m_Attribute);
m_Successors = new Id3[m_Attribute.numValues()];
for (int j = 0; j < m_Attribute.numValues(); j++) {
m_Successors[j] = new Id3();
m_Successors[j].buildClassifier(splitData[j]);
}
}
}
/**
* Particiona un conjunto de datos, dado un valor nominal
*
* @param data Los datos a partir
* @param att El atributo a usar para particionar
* @return Conjunto de instancias producidas al particionar
*/
private Instances[] splitData(Instances data, Attribute att) {
Instances[] splitData = new Instances[att.numValues()];
for (int j = 0; j < att.numValues(); j++) {
splitData[j] = new Instances(data, data.numInstances());
}
Enumeration instEnum = data.enumerateInstances();
while (instEnum.hasMoreElements()) {
Instance inst = (Instance) instEnum.nextElement();
splitData[(int) inst.value(att)].add(inst);
}
return splitData;
}
/**
* Imprime ARbol de Decision
*
* @return Descripcion textual de Clasificador
*/
public String toString() {
if ((m_Distribution == null) && (m_Successors == null)) {
return "Id3: No hay modelo aún.";
}
return "Arbol de Decisión Id3\n\n" + toString(0);
}
/**
* Muestra un arbol de cierto nivel
*
* @param level El nivel del arbol que debe ser mostrado
*/
private String toString(int level) {
StringBuffer text = new StringBuffer();
if (m_Attribute == null) {
if (Instance.isMissingValue(m_ClassValue)) {
text.append(" : null");
} else {
text.append(" : "+m_ClassAttribute.value((int) m_ClassValue));
}
} else {
for (int j = 0; j < m_Attribute.numValues(); j++) {
text.append("\n");
for (int i = 0; i < level; i++) {
text.append("| ");
}
text.append(m_Attribute.name() + " = " + m_Attribute.value(j));
text.append(m_Successors[j].toString(level + 1));
}
}
//verarbol.Gui.main(text,0);
String[] p=new String[1];
p[0]=new String(text);
verarbol.visor.main(p);
return text.toString();
}
}
Copyright Nelson Flores 2001™.
Departamento de Ciencias de la Computacion, Universidad de Chile.