source: tags/MetisMQIDemo/src/main/java/weka/classifiers/pmml/consumer/TreeModel.java

/*
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with this program; if not, write to the Free Software
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/*
 *    TreeModel.java
 *    Copyright (C) 2009 University of Waikato, Hamilton, New Zealand
 *
 */

package weka.classifiers.pmml.consumer;

import java.io.Serializable;
import java.util.ArrayList;

import org.w3c.dom.Element;
import org.w3c.dom.Node;
import org.w3c.dom.NodeList;

import weka.core.Attribute;
import weka.core.Drawable;
import weka.core.Instance;
import weka.core.Instances;
import weka.core.RevisionUtils;
import weka.core.Utils;
import weka.core.pmml.*;

/**
 * Class implementing import of PMML TreeModel. Can be used as a Weka
 * classifier for prediction (buildClassifier() raises and Exception).
 * 
 * @author Mark Hall (mhall{[at]}pentaho{[dot]}com)
 * @version $Revision: 5987 $;
 */
public class TreeModel extends PMMLClassifier implements Drawable {
  
  /**
   * For serialization
   */
  private static final long serialVersionUID = -2065158088298753129L;

  /**
   * Inner class representing the ScoreDistribution element
   */
  static class ScoreDistribution implements Serializable {
    
    /**
     * For serialization
     */
    private static final long serialVersionUID = -123506262094299933L;

    /** The class label for this distribution element */
    private String m_classLabel;
    
    /** The index of the class label */
    private int m_classLabelIndex = -1;
    
    /** The count for this label */
    private double m_recordCount;
    
    /** The optional confidence value */
    private double m_confidence = Utils.missingValue();
    
    /**
     * Construct a ScoreDistribution entry
     * 
     * @param scoreE the node containing the distribution
     * @param miningSchema the mining schema
     * @param baseCount the number of records at the node that owns this 
     * distribution entry
     * @throws Exception if something goes wrong
     */
    protected ScoreDistribution(Element scoreE, MiningSchema miningSchema, double baseCount) 
      throws Exception {
      // get the label
      m_classLabel = scoreE.getAttribute("value");
      Attribute classAtt = miningSchema.getFieldsAsInstances().classAttribute();
      if (classAtt == null || classAtt.indexOfValue(m_classLabel) < 0) {
        throw new Exception("[ScoreDistribution] class attribute not set or class value " +
            m_classLabel + " not found!");
      }
      
      m_classLabelIndex = classAtt.indexOfValue(m_classLabel);
      
      // get the frequency
      String recordC = scoreE.getAttribute("recordCount");
      m_recordCount = Double.parseDouble(recordC);
      
      // get the optional confidence
      String confidence = scoreE.getAttribute("confidence");
      if (confidence != null && confidence.length() > 0) {
        m_confidence = Double.parseDouble(confidence);        
      } else if (!Utils.isMissingValue(baseCount) && baseCount > 0) {
        m_confidence = m_recordCount / baseCount;
      }
    }
    
    /**
     * Backfit confidence value (does nothing if the confidence
     * value is already set).
     * 
     * @param baseCount the total number of records (supplied either
     * explicitly from the node that owns this distribution entry
     * or most likely computed from summing the recordCounts of all
     * the distribution entries in the distribution that owns this
     * entry).
     */
    void deriveConfidenceValue(double baseCount) {
      if (Utils.isMissingValue(m_confidence) && 
          !Utils.isMissingValue(baseCount) && 
          baseCount > 0) {
        m_confidence = m_recordCount / baseCount;
      }
    }
    
    String getClassLabel() {
      return m_classLabel;
    }
    
    int getClassLabelIndex() {
      return m_classLabelIndex;
    }
    
    double getRecordCount() {
      return m_recordCount;
    }
    
    double getConfidence() {
      return m_confidence;
    }
    
    public String toString() {
      return m_classLabel + ": " + m_recordCount 
        + " (" + Utils.doubleToString(m_confidence, 2) + ") ";
    }
  }
  
  /**
   * Base class for Predicates
   */
  static abstract class Predicate implements Serializable {
    
    /**
     * For serialization
     */
    private static final long serialVersionUID = 1035344165452733887L;

    enum Eval {
      TRUE,
      FALSE,
      UNKNOWN;
    }
    
    /**
     * Evaluate this predicate.
     * 
     * @param input the input vector of attribute and derived field values.
     * 
     * @return the evaluation status of this predicate.
     */
    abstract Eval evaluate(double[] input);
    
    protected String toString(int level, boolean cr) {
      return toString(level);
    }
    
    protected String toString(int level) {
      StringBuffer text = new StringBuffer();
      for (int j = 0; j < level; j++) {
        text.append("|   ");
      }
      
      return text.append(toString()).toString();
    }
    
    static Eval booleanToEval(boolean missing, boolean result) {
      if (missing) {
        return Eval.UNKNOWN;
      } else if (result) {
        return Eval.TRUE;
      } else {
        return Eval.FALSE;
      }
    }
    
    /**
     * Factory method to return the appropriate predicate for
     * a given node in the tree.
     * 
     * @param nodeE the XML node encapsulating the tree node.
     * @param miningSchema the mining schema in use
     * @return a Predicate
     * @throws Exception of something goes wrong.
     */
    static Predicate getPredicate(Element nodeE, 
        MiningSchema miningSchema) throws Exception {
      
      Predicate result = null;
      NodeList children = nodeE.getChildNodes();
      for (int i = 0; i < children.getLength(); i++) {
        Node child = children.item(i);
        if (child.getNodeType() == Node.ELEMENT_NODE) {
          String tagName = ((Element)child).getTagName();
          if (tagName.equals("True")) {
            result = new True();
            break;
          } else if (tagName.equals("False")) {
            result = new False();
            break;
          } else if (tagName.equals("SimplePredicate")) {
            result = new SimplePredicate((Element)child, miningSchema);
            break;
          } else if (tagName.equals("CompoundPredicate")) {
            result = new CompoundPredicate((Element)child, miningSchema);
            break;
          } else if (tagName.equals("SimpleSetPredicate")) {
           result = new SimpleSetPredicate((Element)child, miningSchema);
           break;
          }
        }
      }
      
      if (result == null) {
        throw new Exception("[Predicate] unknown or missing predicate type in node");
      }
      
      return result;
    }
  }
  
  /**
   * Simple True Predicate
   */
  static class True extends Predicate {
    
    /**
     * For serialization
     */
    private static final long serialVersionUID = 1817942234610531627L;

    public Predicate.Eval evaluate(double[] input) {
      return Predicate.Eval.TRUE;
    }
    
    public String toString() {
      return "True: ";
    }
  }
  
  /**
   * Simple False Predicate
   */
  static class False extends Predicate {
    
    /**
     * For serialization 
     */
    private static final long serialVersionUID = -3647261386442860365L;

    public Predicate.Eval evaluate(double[] input) {
      return Predicate.Eval.FALSE;
    }
    
    public String toString() {
      return "False: ";
    }
  }
  
  /**
   * Class representing the SimplePredicate
   */
  static class SimplePredicate extends Predicate {
    
    /**
     * For serialization
     */
    private static final long serialVersionUID = -6156684285069327400L;

    enum Operator {
      EQUAL("equal") {
        Predicate.Eval evaluate(double[] input, double value, int fieldIndex) {
          return Predicate.booleanToEval(Utils.isMissingValue(input[fieldIndex]), 
              weka.core.Utils.eq(input[fieldIndex], value));
        }
        
        String shortName() {
          return "==";
        }
      },
      NOTEQUAL("notEqual")
       {
        Predicate.Eval evaluate(double[] input, double value, int fieldIndex) {
          return Predicate.booleanToEval(Utils.isMissingValue(input[fieldIndex]), 
              (input[fieldIndex] != value));
        }
        
        String shortName() {
          return "!=";
        }
      },
      LESSTHAN("lessThan")  {
        Predicate.Eval evaluate(double[] input, double value, int fieldIndex) {
          return Predicate.booleanToEval(Utils.isMissingValue(input[fieldIndex]),
              (input[fieldIndex] < value));
        }
        
        String shortName() {
          return "<";
        }
      },
      LESSOREQUAL("lessOrEqual") {
        Predicate.Eval evaluate(double[] input, double value, int fieldIndex) {
          return Predicate.booleanToEval(Utils.isMissingValue(input[fieldIndex]),
              (input[fieldIndex] <= value));
        }
        
        String shortName() {
          return "<=";
        }
      },
      GREATERTHAN("greaterThan") {
        Predicate.Eval evaluate(double[] input, double value, int fieldIndex) {
          return Predicate.booleanToEval(Utils.isMissingValue(input[fieldIndex]),
              (input[fieldIndex] > value));
        }
        
        String shortName() {
          return ">";
        }
      },
      GREATEROREQUAL("greaterOrEqual") {
        Predicate.Eval evaluate(double[] input, double value, int fieldIndex) {
          return Predicate.booleanToEval(Utils.isMissingValue(input[fieldIndex]),
              (input[fieldIndex] >= value));
        }
        
        String shortName() {
          return ">=";
        }
      },
      ISMISSING("isMissing") {
        Predicate.Eval evaluate(double[] input, double value, int fieldIndex) {
          return Predicate.booleanToEval(false,
              Utils.isMissingValue(input[fieldIndex]));
        }
        
        String shortName() {
          return toString();
        }
      },
      ISNOTMISSING("isNotMissing") {
        Predicate.Eval evaluate(double[] input, double value, int fieldIndex) {
          return Predicate.booleanToEval(false, !Utils.isMissingValue(input[fieldIndex]));
        }
        
        String shortName() {
          return toString();
        }
      };
      
      abstract Predicate.Eval evaluate(double[] input, double value, int fieldIndex);
      abstract String shortName();
      
      private final String m_stringVal;
      
      Operator(String name) {
        m_stringVal = name;
      }
            
      public String toString() {
        return m_stringVal;
      }
    }
    
    /** the field that we are comparing against */
    int m_fieldIndex = -1;
    
    /** the name of the field */
    String m_fieldName;
    
    /** true if the field is nominal */
    boolean m_isNominal;
    
    /** the value as a string (if nominal) */
    String m_nominalValue;
    
    /** the value to compare against (if nominal it holds the index of the value) */
    double m_value;
    
    /** the operator to use */
    Operator m_operator;
        
    public SimplePredicate(Element simpleP, 
        MiningSchema miningSchema) throws Exception {
      Instances totalStructure = miningSchema.getFieldsAsInstances();
      
      // get the field name and set up the index
      String fieldS = simpleP.getAttribute("field");
      Attribute att = totalStructure.attribute(fieldS);
      if (att == null) {
        throw new Exception("[SimplePredicate] unable to find field " + fieldS
            + " in the incoming instance structure!");
      }
      
      // find the index
      int index = -1;
      for (int i = 0; i < totalStructure.numAttributes(); i++) {
        if (totalStructure.attribute(i).name().equals(fieldS)) {
          index = i;
          m_fieldName = totalStructure.attribute(i).name();
          break;
        }
      }
      m_fieldIndex = index;
      if (att.isNominal()) {
        m_isNominal = true;
      }
      
      // get the operator
      String oppS = simpleP.getAttribute("operator");
      for (Operator o : Operator.values()) {
        if (o.toString().equals(oppS)) {
          m_operator = o;
          break;
        }
      }
      
      if (m_operator != Operator.ISMISSING && m_operator != Operator.ISNOTMISSING) {
        String valueS = simpleP.getAttribute("value");
        if (att.isNumeric()) {
          m_value = Double.parseDouble(valueS);
        } else {
          m_nominalValue = valueS;
          m_value = att.indexOfValue(valueS);
          if (m_value < 0) {
            throw new Exception("[SimplePredicate] can't find value " + valueS + " in nominal " +
                "attribute " + att.name());
          }
        }
      }
    }
    
    public Predicate.Eval evaluate(double[] input) {
      return m_operator.evaluate(input, m_value, m_fieldIndex);
    }
        
    public String toString() {
      StringBuffer temp = new StringBuffer();
      
      temp.append(m_fieldName + " " + m_operator.shortName());
      if (m_operator != Operator.ISMISSING && m_operator != Operator.ISNOTMISSING) {
        temp.append(" " + ((m_isNominal) ? m_nominalValue : "" + m_value));
      }
      
      return temp.toString();
    }
  }
  
  /**
   * Class representing the CompoundPredicate
   */
  static class CompoundPredicate extends Predicate {
    
    /**
     * For serialization
     */
    private static final long serialVersionUID = -3332091529764559077L;

    enum BooleanOperator {
      OR("or") {
        Predicate.Eval evaluate(ArrayList<Predicate> constituents, double[] input) {
          Predicate.Eval currentStatus = Predicate.Eval.FALSE;
          for (Predicate p : constituents) {
            Predicate.Eval temp = p.evaluate(input);
            if (temp == Predicate.Eval.TRUE) {
              currentStatus = temp;
              break;
            } else if (temp == Predicate.Eval.UNKNOWN) {
              currentStatus = temp;
            }            
          }
          return currentStatus;
        }
      },
      AND("and") {
        Predicate.Eval evaluate(ArrayList<Predicate> constituents, double[] input) {
          Predicate.Eval currentStatus = Predicate.Eval.TRUE;
          for (Predicate p : constituents) {
            Predicate.Eval temp = p.evaluate(input);
            if (temp == Predicate.Eval.FALSE) {
              currentStatus = temp;
              break;
            } else if (temp == Predicate.Eval.UNKNOWN) {
              currentStatus = temp;
            }
          }          
          return currentStatus;
        }
      },
      XOR("xor") {
        Predicate.Eval evaluate(ArrayList<Predicate> constituents, double[] input) {
          Predicate.Eval currentStatus = constituents.get(0).evaluate(input);
          if (currentStatus != Predicate.Eval.UNKNOWN) {
            for (int i = 1; i < constituents.size(); i++) {
              Predicate.Eval temp = constituents.get(i).evaluate(input);
              if (temp == Predicate.Eval.UNKNOWN) {
                currentStatus = temp;
                break;
              } else {
                if (currentStatus != temp) {
                  currentStatus = Predicate.Eval.TRUE;
                } else {
                  currentStatus = Predicate.Eval.FALSE;
                }
              }
            }
          }
          return currentStatus;
        }
      },
      SURROGATE("surrogate") {
        Predicate.Eval evaluate(ArrayList<Predicate> constituents, double[] input) {
          Predicate.Eval currentStatus = constituents.get(0).evaluate(input);
          
          int i = 1;
          while (currentStatus == Predicate.Eval.UNKNOWN) {
            currentStatus = constituents.get(i).evaluate(input);            
          }
          
          // return false if all our surrogates evaluate to unknown.
          if (currentStatus == Predicate.Eval.UNKNOWN) {
            currentStatus = Predicate.Eval.FALSE;
          }
          
          return currentStatus;
        }
      };
      
      abstract Predicate.Eval evaluate(ArrayList<Predicate> constituents, double[] input);
      
      private final String m_stringVal;
      
      BooleanOperator(String name) {
        m_stringVal = name;
      }
      
      public String toString() {
        return m_stringVal;
      }
    }
    
    /** the constituent Predicates */
    ArrayList<Predicate> m_components = new ArrayList<Predicate>();
    
    /** the boolean operator */
    BooleanOperator m_booleanOperator;
        
    public CompoundPredicate(Element compoundP, 
        MiningSchema miningSchema) throws Exception {
//      Instances totalStructure = miningSchema.getFieldsAsInstances();
      
      String booleanOpp = compoundP.getAttribute("booleanOperator");
      for (BooleanOperator b : BooleanOperator.values()) {
        if (b.toString().equals(booleanOpp)) {
          m_booleanOperator = b;
        }
      }
      
      // now get all the encapsulated operators
      NodeList children = compoundP.getChildNodes();
      for (int i = 0; i < children.getLength(); i++) {
        Node child = children.item(i);
        if (child.getNodeType() == Node.ELEMENT_NODE) {
          String tagName = ((Element)child).getTagName();
          if (tagName.equals("True")) {
            m_components.add(new True());
          } else if (tagName.equals("False")) {
            m_components.add(new False());
          } else if (tagName.equals("SimplePredicate")) {
            m_components.add(new SimplePredicate((Element)child, miningSchema));
          } else if (tagName.equals("CompoundPredicate")) {
            m_components.add(new CompoundPredicate((Element)child, miningSchema));
          } else {
            m_components.add(new SimpleSetPredicate((Element)child, miningSchema));
          }
        }
      }
    }
    
    public Predicate.Eval evaluate(double[] input) {
      return m_booleanOperator.evaluate(m_components, input);
    }
    
    public String toString() {
      return toString(0, false);
    }
    
    public String toString(int level, boolean cr) {
      StringBuffer text = new StringBuffer();
      for (int j = 0; j < level; j++) {
        text.append("|   ");
      }
      
      text.append("Compound [" + m_booleanOperator.toString() + "]");
      if (cr) {
        text.append("\\n");
      } else {
        text.append("\n");
      }
      for (int i = 0; i < m_components.size(); i++) {
        text.append(m_components.get(i).toString(level, cr).replace(":", ""));
        if (i != m_components.size()-1) {
          if (cr) {
            text.append("\\n");
          } else {
            text.append("\n");
          }
        }
      }
      
      return text.toString();
    }
  }
  
  /**
   * Class representing the SimpleSetPredicate
   */
  static class SimpleSetPredicate extends Predicate {
    
    /**
     * For serialization
     */
    private static final long serialVersionUID = -2711995401345708486L;

    enum BooleanOperator {
        IS_IN("isIn") {
          Predicate.Eval evaluate(double[] input, int fieldIndex, 
              Array set, Attribute nominalLookup) {            
            if (set.getType() == Array.ArrayType.STRING) {
              String value = "";
              if (!Utils.isMissingValue(input[fieldIndex])) {
                value = nominalLookup.value((int)input[fieldIndex]);
              }
              return Predicate.booleanToEval(Utils.isMissingValue(input[fieldIndex]), 
                  set.contains(value));
            } else if (set.getType() == Array.ArrayType.NUM ||
                set.getType() == Array.ArrayType.REAL) {
              return Predicate.booleanToEval(Utils.isMissingValue(input[fieldIndex]), 
                set.contains(input[fieldIndex]));
            }
            return Predicate.booleanToEval(Utils.isMissingValue(input[fieldIndex]), 
                set.contains((int)input[fieldIndex]));
          }
        },
        IS_NOT_IN("isNotIn") {
          Predicate.Eval evaluate(double[] input, int fieldIndex,
              Array set, Attribute nominalLookup) {
            Predicate.Eval result = IS_IN.evaluate(input, fieldIndex, set, nominalLookup);
            if (result == Predicate.Eval.FALSE) {
              result = Predicate.Eval.TRUE;
            } else if (result == Predicate.Eval.TRUE) {
              result = Predicate.Eval.FALSE;
            }
            
            return result;
          }
        };
        
        abstract Predicate.Eval evaluate(double[] input, int fieldIndex, 
            Array set, Attribute nominalLookup);
        
        private final String m_stringVal;
        
        BooleanOperator(String name) {
          m_stringVal = name;
        }
        
        public String toString() {
          return m_stringVal;
        }
    }
    
    /** the field to reference */
    int m_fieldIndex = -1;
    
    /** the name of the field */
    String m_fieldName;
    
    /** is the referenced field nominal? */
    boolean m_isNominal = false;
    
    /** the attribute to lookup nominal values from */
    Attribute m_nominalLookup;
    
    /** the boolean operator */
    BooleanOperator m_operator = BooleanOperator.IS_IN;
    
    /** the array holding the set of values */
    Array m_set;
        
    public SimpleSetPredicate(Element setP, 
        MiningSchema miningSchema) throws Exception {
      Instances totalStructure = miningSchema.getFieldsAsInstances();
      
      // get the field name and set up the index
      String fieldS = setP.getAttribute("field");
      Attribute att = totalStructure.attribute(fieldS);
      if (att == null) {
        throw new Exception("[SimplePredicate] unable to find field " + fieldS
            + " in the incoming instance structure!");
      }
      
      // find the index
      int index = -1;
      for (int i = 0; i < totalStructure.numAttributes(); i++) {
        if (totalStructure.attribute(i).name().equals(fieldS)) {
          index = i;
          m_fieldName = totalStructure.attribute(i).name();
          break;
        }
      }
      m_fieldIndex = index;
      if (att.isNominal()) {
        m_isNominal = true;
        m_nominalLookup = att;
      }
  
      // need to scan the children looking for an array type
      NodeList children = setP.getChildNodes();
      for (int i = 0; i < children.getLength(); i++) {
        Node child = children.item(i);
        if (child.getNodeType() == Node.ELEMENT_NODE) {
          if (Array.isArray((Element)child)) {
            // found the array
            m_set = Array.create((Element)child);
            break;
          }
        }
      }

      if (m_set == null) {
        throw new Exception("[SimpleSetPredictate] couldn't find an " +
        "array containing the set values!");
      }
      
      // check array type against field type
      if (m_set.getType() == Array.ArrayType.STRING &&
          !m_isNominal) {
        throw new Exception("[SimpleSetPredicate] referenced field " +
            totalStructure.attribute(m_fieldIndex).name() + 
            " is numeric but array type is string!");
      } else if (m_set.getType() != Array.ArrayType.STRING && 
          m_isNominal) {
        throw new Exception("[SimpleSetPredicate] referenced field " +
            totalStructure.attribute(m_fieldIndex).name() +
            " is nominal but array type is numeric!");
      }      
    }
    
    public Predicate.Eval evaluate(double[] input) {
      return m_operator.evaluate(input, m_fieldIndex, m_set, m_nominalLookup);
    }
    
    public String toString() {
      StringBuffer temp = new StringBuffer();
      
      temp.append(m_fieldName + " " + m_operator.toString() + " ");
      temp.append(m_set.toString());
      
      return temp.toString();
    }
  }
  
  /**
   * Class for handling a Node in the tree
   */
  class TreeNode implements Serializable {
    // TODO: perhaps implement a class called Statistics that contains Partitions?
        
    /**
     * For serialization
     */
    private static final long serialVersionUID = 3011062274167063699L;

    /** ID for this node */
    private String m_ID = "" + this.hashCode();
    
    /** The score as a string */
    private String m_scoreString;
    
    /** The index of this predicted value (if class is nominal) */
    private int m_scoreIndex = -1;
    
    /** The score as a number (if target is numeric) */
    private double m_scoreNumeric = Utils.missingValue();
    
    /** The record count at this node (if defined) */
    private double m_recordCount = Utils.missingValue();
    
    /** The ID of the default child (if applicable) */
    private String m_defaultChildID;
    
    /** Holds the node of the default child (if defined) */
    private TreeNode m_defaultChild;
    
    /** The distribution for labels (classification) */
    private ArrayList<ScoreDistribution> m_scoreDistributions = 
      new ArrayList<ScoreDistribution>();
    
    /** The predicate for this node */
    private Predicate m_predicate;
    
    /** The children of this node */
    private ArrayList<TreeNode> m_childNodes = new ArrayList<TreeNode>();
    
    
    protected TreeNode(Element nodeE, MiningSchema miningSchema) throws Exception {
      Attribute classAtt = miningSchema.getFieldsAsInstances().classAttribute();
      
      // get the ID
      String id = nodeE.getAttribute("id");
      if (id != null && id.length() > 0) {
        m_ID = id;
      }
      
      // get the score for this node
      String scoreS = nodeE.getAttribute("score");
      if (scoreS != null && scoreS.length() > 0) {
        m_scoreString = scoreS;
        
        // try to parse as a number in case we 
        // are part of a regression tree
        if (classAtt.isNumeric()) {
          try {
            m_scoreNumeric = Double.parseDouble(scoreS);
          } catch (NumberFormatException ex) {
            throw new Exception("[TreeNode] class is numeric but unable to parse score " 
                + m_scoreString + " as a number!");
          }
        } else {
          // store the index of this class value
          m_scoreIndex = classAtt.indexOfValue(m_scoreString);
          
          if (m_scoreIndex < 0) {
            throw new Exception("[TreeNode] can't find match for predicted value " 
                + m_scoreString + " in class attribute!");
          }
        }
      }
      
      // get the record count if defined
      String recordC = nodeE.getAttribute("recordCount");
      if (recordC != null && recordC.length() > 0) {
        m_recordCount = Double.parseDouble(recordC);
      }
      
      // get the default child (if applicable)
      String defaultC = nodeE.getAttribute("defaultChild");
      if (defaultC != null && defaultC.length() > 0) {
        m_defaultChildID = defaultC;
      }
      
      //TODO: Embedded model (once we support model composition)
      
      // Now get the ScoreDistributions (if any and mining function 
      // is classification) at this level
      if (m_functionType == MiningFunction.CLASSIFICATION) {
        getScoreDistributions(nodeE, miningSchema);
      }
      
      // Now get the Predicate
      m_predicate = Predicate.getPredicate(nodeE, miningSchema);
      
      // Now get the child Node(s)
      getChildNodes(nodeE, miningSchema);
      
      // If we have a default child specified, find it now
      if (m_defaultChildID != null) {
        for (TreeNode t : m_childNodes) {
          if (t.getID().equals(m_defaultChildID)) {
            m_defaultChild = t;
            break;
          }
        }
      }
    }
    
    private void getChildNodes(Element nodeE, MiningSchema miningSchema) throws Exception {
      NodeList children = nodeE.getChildNodes();
      
      for (int i = 0; i < children.getLength(); i++) {
        Node child = children.item(i);
        if (child.getNodeType() == Node.ELEMENT_NODE) {
          String tagName = ((Element)child).getTagName();
          if (tagName.equals("Node")) {
            TreeNode tempN = new TreeNode((Element)child, miningSchema);
            m_childNodes.add(tempN);
          }
        }
      }
    }
    
    private void getScoreDistributions(Element nodeE, 
        MiningSchema miningSchema) throws Exception {
      
      NodeList scoreChildren = nodeE.getChildNodes();
      for (int i = 0; i < scoreChildren.getLength(); i++) {
        Node child = scoreChildren.item(i);
        if (child.getNodeType() == Node.ELEMENT_NODE) {
          String tagName = ((Element)child).getTagName();
          if (tagName.equals("ScoreDistribution")) {
            ScoreDistribution newDist = new ScoreDistribution((Element)child, 
                miningSchema, m_recordCount);
            m_scoreDistributions.add(newDist);
          }
        }
      }
      
      // backfit the confidence values
      if (Utils.isMissingValue(m_recordCount)) {
        double baseCount = 0;
        for (ScoreDistribution s : m_scoreDistributions) {
          baseCount += s.getRecordCount();
        }
        
        for (ScoreDistribution s : m_scoreDistributions) {
          s.deriveConfidenceValue(baseCount);
        }
      }
    }
        
    /**
     * Get the score value as a string.
     * 
     * @return the score value as a String.
     */
    protected String getScore() {
      return m_scoreString;
    }
    
    /**
     * Get the score value as a number (regression trees only).
     * 
     * @return the score as a number
     */
    protected double getScoreNumeric() {
      return m_scoreNumeric;
    }
    
    /**
     * Get the ID of this node.
     * 
     * @return the ID of this node.
     */
    protected String getID() {
      return m_ID;
    }
    
    /**
     * Get the Predicate at this node.
     * 
     * @return the predicate at this node.
     */
    protected Predicate getPredicate() {
      return m_predicate;
    }
    
    /**
     * Get the record count at this node.
     * 
     * @return the record count at this node.
     */
    protected double getRecordCount() {
      return m_recordCount;
    }
    
    protected void dumpGraph(StringBuffer text) throws Exception {
      text.append("N" + m_ID + " ");
      if (m_scoreString != null) {
        text.append("[label=\"score=" + m_scoreString);
      }
      
      if (m_scoreDistributions.size() > 0 && m_childNodes.size() == 0) {
        text.append("\\n");
        for (ScoreDistribution s : m_scoreDistributions) {
          text.append(s + "\\n");
        }
      }
      
      text.append("\"");
      
      if (m_childNodes.size() == 0) {
        text.append(" shape=box style=filled");
        
      }
      
      text.append("]\n");
      
      for (TreeNode c : m_childNodes) {
        text.append("N" + m_ID +"->" + "N" + c.getID());
        text.append(" [label=\"" + c.getPredicate().toString(0, true));
        text.append("\"]\n");
        c.dumpGraph(text);
      }
    }
    
    public String toString() {
      StringBuffer text = new StringBuffer();
      
      // print out the root
      dumpTree(0, text);

      return text.toString();
    }
    
    protected void dumpTree(int level, StringBuffer text) {
      if (m_childNodes.size() > 0) {

        for (int i = 0; i < m_childNodes.size(); i++) {
          text.append("\n");
          
/*          for (int j = 0; j < level; j++) {
            text.append("|   ");
          } */
          
          // output the predicate for this child node
          TreeNode child = m_childNodes.get(i);
          text.append(child.getPredicate().toString(level, false));
          
          // process recursively
          child.dumpTree(level + 1 , text);          
        }
      } else {
        // leaf
        text.append(": ");
        if (!Utils.isMissingValue(m_scoreNumeric)) {
          text.append(m_scoreNumeric);
        } else {
          text.append(m_scoreString + " ");
          if (m_scoreDistributions.size() > 0) {
            text.append("[");
            for (ScoreDistribution s : m_scoreDistributions) {
              text.append(s);
            }
            text.append("]");
          } else {
            text.append(m_scoreString);
          }
        }
      }
    }
    
    /**
     * Score an incoming instance. Invokes a missing value handling strategy.
     * 
     * @param instance a vector of incoming attribute and derived field values.
     * @param classAtt the class attribute
     * @return a predicted probability distribution.
     * @throws Exception if something goes wrong.
     */
    protected double[] score(double[] instance, Attribute classAtt) throws Exception {
      double[] preds = null;
      
      if (classAtt.isNumeric()) {
        preds = new double[1];
      } else {
        preds = new double[classAtt.numValues()];
      }
      
      // leaf?
      if (m_childNodes.size() == 0) {
        doLeaf(classAtt, preds);
      } else {
        // process the children
        switch (TreeModel.this.m_missingValueStrategy) {
        case NONE:
          preds = missingValueStrategyNone(instance, classAtt);
          break;
        case LASTPREDICTION:
          preds = missingValueStrategyLastPrediction(instance, classAtt);
          break;
        case DEFAULTCHILD:
          preds = missingValueStrategyDefaultChild(instance, classAtt);
          break;
        default:
          throw new Exception("[TreeModel] not implemented!");
        }
      }
      
      return preds;
    }
    
    /**
     * Compute the predictions for a leaf.
     * 
     * @param classAtt the class attribute
     * @param preds an array to hold the predicted probabilities.
     * @throws Exception if something goes wrong.
     */
    protected void doLeaf(Attribute classAtt, double[] preds) throws Exception {
      if (classAtt.isNumeric()) {
        preds[0] = m_scoreNumeric;
      } else {
        if (m_scoreDistributions.size() == 0) {
          preds[m_scoreIndex] = 1.0;
        } else {
          // collect confidences from the score distributions
          for (ScoreDistribution s : m_scoreDistributions) {
            preds[s.getClassLabelIndex()] = s.getConfidence();
          }
        }
      }
    }
    
    /**
     * Evaluate on the basis of the no true child strategy.
     * 
     * @param classAtt the class attribute.
     * @param preds an array to hold the predicted probabilities.
     * @throws Exception if something goes wrong.
     */
    protected void doNoTrueChild(Attribute classAtt, double[] preds) 
      throws Exception {
      if (TreeModel.this.m_noTrueChildStrategy == 
        NoTrueChildStrategy.RETURNNULLPREDICTION) {
        for (int i = 0; i < classAtt.numValues(); i++) {
          preds[i] = Utils.missingValue();
        }
      } else {
        // return the predictions at this node
        doLeaf(classAtt, preds);
      }
    }
    
    /**
     * Compute predictions and optionally invoke the weighted confidence
     * missing value handling strategy.
     * 
     * @param instance the incoming vector of attribute and derived field values.
     * @param classAtt the class attribute.
     * @return the predicted probability distribution.
     * @throws Exception if something goes wrong.
     */
    protected double[] missingValueStrategyWeightedConfidence(double[] instance,
        Attribute classAtt) throws Exception {
      
      if (classAtt.isNumeric()) {
        throw new Exception("[TreeNode] missing value strategy weighted confidence, "
            + "but class is numeric!");
      }
      
      double[] preds = null;
      TreeNode trueNode = null;
      boolean strategyInvoked = false;
      int nodeCount = 0;
      
      // look at the evaluation of the child predicates
      for (TreeNode c : m_childNodes) {
        if (c.getPredicate().evaluate(instance) == Predicate.Eval.TRUE) {
          // note the first child to evaluate to true
          if (trueNode == null) {
            trueNode = c;
          }
          nodeCount++;
        } else if (c.getPredicate().evaluate(instance) == Predicate.Eval.UNKNOWN) {
          strategyInvoked = true;
          nodeCount++;
        }
      }
      
      if (strategyInvoked) {
        // we expect to combine nodeCount distributions
        double[][] dists = new double[nodeCount][];
        double[] weights = new double[nodeCount];
        
        // collect the distributions and weights
        int count = 0;
        for (TreeNode c : m_childNodes) {
          if (c.getPredicate().evaluate(instance) == Predicate.Eval.TRUE ||
              c.getPredicate().evaluate(instance) == Predicate.Eval.UNKNOWN) {
            
            weights[count] = c.getRecordCount();
            if (Utils.isMissingValue(weights[count])) {
              throw new Exception("[TreeNode] weighted confidence missing value " +
                        "strategy invoked, but no record count defined for node " +
                        c.getID());
            }            
            dists[count++] = c.score(instance, classAtt);
          }
        }
        
        // do the combination
        preds = new double[classAtt.numValues()];
        for (int i = 0; i < classAtt.numValues(); i++) {
          for (int j = 0; j < nodeCount; j++) {
            preds[i] += ((weights[j] / m_recordCount) * dists[j][i]); 
          }
        }
      } else {
        if (trueNode != null) {
          preds = trueNode.score(instance, classAtt);
        } else {
          doNoTrueChild(classAtt, preds);
        }
      }
      
      return preds;
    }
    
    protected double[] freqCountsForAggNodesStrategy(double[] instance,
        Attribute classAtt) throws Exception {
    
      double[] counts = new double[classAtt.numValues()];
      
      if (m_childNodes.size() > 0) {
        // collect the counts
        for (TreeNode c : m_childNodes) {
          if (c.getPredicate().evaluate(instance) == Predicate.Eval.TRUE ||
              c.getPredicate().evaluate(instance) == Predicate.Eval.UNKNOWN) {

            double[] temp = c.freqCountsForAggNodesStrategy(instance, classAtt);
            for (int i = 0; i < classAtt.numValues(); i++) {
              counts[i] += temp[i];
            }
          }
        }
      } else {
        // process the score distributions
        if (m_scoreDistributions.size() == 0) {
          throw new Exception("[TreeModel] missing value strategy aggregate nodes:" +
                        " no score distributions at leaf " + m_ID);
        }
        for (ScoreDistribution s : m_scoreDistributions) {
          counts[s.getClassLabelIndex()] = s.getRecordCount();
        }
      }
            
      return counts;
    }
    
    /**
     * Compute predictions and optionally invoke the aggregate nodes
     * missing value handling strategy.
     * 
     * @param instance the incoming vector of attribute and derived field values.
     * @param classAtt the class attribute.
     * @return the predicted probability distribution.
     * @throws Exception if something goes wrong.
     */
    protected double[] missingValueStrategyAggregateNodes(double[] instance,
        Attribute classAtt) throws Exception {
      
      if (classAtt.isNumeric()) {
        throw new Exception("[TreeNode] missing value strategy aggregate nodes, "
            + "but class is numeric!");
      }

      double[] preds = null;
      TreeNode trueNode = null;
      boolean strategyInvoked = false;
      int nodeCount = 0;
      
      // look at the evaluation of the child predicates
      for (TreeNode c : m_childNodes) {
        if (c.getPredicate().evaluate(instance) == Predicate.Eval.TRUE) {
          // note the first child to evaluate to true
          if (trueNode == null) {
            trueNode = c;
          }
          nodeCount++;
        } else if (c.getPredicate().evaluate(instance) == Predicate.Eval.UNKNOWN) {
          strategyInvoked = true;
          nodeCount++;
        }
      }
      
      if (strategyInvoked) {
        double[] aggregatedCounts = 
          freqCountsForAggNodesStrategy(instance, classAtt);
        
        // normalize
        Utils.normalize(aggregatedCounts);
        preds = aggregatedCounts;
      } else {
        if (trueNode != null) {
          preds = trueNode.score(instance, classAtt);
        } else {
          doNoTrueChild(classAtt, preds);
        }
      }
      
      return preds;             
    }
    
    /**
     * Compute predictions and optionally invoke the default child
     * missing value handling strategy.
     * 
     * @param instance the incoming vector of attribute and derived field values.
     * @param classAtt the class attribute.
     * @return the predicted probability distribution.
     * @throws Exception if something goes wrong.
     */
    protected double[] missingValueStrategyDefaultChild(double[] instance, 
        Attribute classAtt) throws Exception {
      
      double[] preds = null;
      boolean strategyInvoked = false;
      
      // look for a child whose predicate evaluates to TRUE
      for (TreeNode c : m_childNodes) {
        if (c.getPredicate().evaluate(instance) == Predicate.Eval.TRUE) {
          preds = c.score(instance, classAtt);
          break;
        } else if (c.getPredicate().evaluate(instance) == Predicate.Eval.UNKNOWN) {
          strategyInvoked = true;
        }
      }
      
      // no true child found
      if (preds == null) {
        if (!strategyInvoked) {
          doNoTrueChild(classAtt, preds);
        } else {
          // do the strategy
          
          // NOTE: we don't actually implement the missing value penalty since
          // we always return a full probability distribution.
          if (m_defaultChild != null) {
            preds = m_defaultChild.score(instance, classAtt);
          } else {
            throw new Exception("[TreeNode] missing value strategy is defaultChild, but " +
                        "no default child has been specified in node " + m_ID);
          }
        }
      }
                  
      return preds;
    }
    
    /**
     * Compute predictions and optionally invoke the last prediction
     * missing value handling strategy.
     * 
     * @param instance the incoming vector of attribute and derived field values.
     * @param classAtt the class attribute.
     * @return the predicted probability distribution.
     * @throws Exception if something goes wrong.
     */
    protected double[] missingValueStrategyLastPrediction(double[] instance, 
        Attribute classAtt) throws Exception {
      
      double[] preds = null;
      boolean strategyInvoked = false;
      
      // look for a child whose predicate evaluates to TRUE
      for (TreeNode c : m_childNodes) {
        if (c.getPredicate().evaluate(instance) == Predicate.Eval.TRUE) {
          preds = c.score(instance, classAtt);
          break;
        } else if (c.getPredicate().evaluate(instance) == Predicate.Eval.UNKNOWN) {
          strategyInvoked = true;
        }
      }
      
      // no true child found
      if (preds == null) {
        preds = new double[classAtt.numValues()];
        if (!strategyInvoked) {
          // no true child
          doNoTrueChild(classAtt, preds);
        } else {
          // do the strategy
          doLeaf(classAtt, preds);
        }
      }
      
      return preds;
    }
    
    /**
     * Compute predictions and optionally invoke the null prediction
     * missing value handling strategy.
     * 
     * @param instance the incoming vector of attribute and derived field values.
     * @param classAtt the class attribute.
     * @return the predicted probability distribution.
     * @throws Exception if something goes wrong.
     */
    protected double[] missingValueStrategyNullPrediction(double[] instance,
        Attribute classAtt) throws Exception {
      
      double[] preds = null;
      boolean strategyInvoked = false;
      
      // look for a child whose predicate evaluates to TRUE
      for (TreeNode c : m_childNodes) {
        if (c.getPredicate().evaluate(instance) == Predicate.Eval.TRUE) {
          preds = c.score(instance, classAtt);
          break;
        } else if (c.getPredicate().evaluate(instance) == Predicate.Eval.UNKNOWN) {
          strategyInvoked = true;
        }
      }
      
      // no true child found
      if (preds == null) {
        preds = new double[classAtt.numValues()];
        if (!strategyInvoked) {
          doNoTrueChild(classAtt, preds);
        } else {
          // do the strategy
          for (int i = 0; i < classAtt.numValues(); i++) {
            preds[i] = Utils.missingValue();
          }
        }
      }
      
      return preds;
    }
    
    /**
     * Compute predictions and optionally invoke the "none"
     * missing value handling strategy (invokes no true child).
     * 
     * @param instance the incoming vector of attribute and derived field values.
     * @param classAtt the class attribute.
     * @return the predicted probability distribution.
     * @throws Exception if something goes wrong.
     */
    protected double[] missingValueStrategyNone(double[] instance, Attribute classAtt)
      throws Exception {
      
      double[] preds = null;
      
      // look for a child whose predicate evaluates to TRUE
      for (TreeNode c : m_childNodes) {
        if (c.getPredicate().evaluate(instance) == Predicate.Eval.TRUE) {
          preds = c.score(instance, classAtt);
          break;
        }
      }
      
      if (preds == null) {
        preds = new double[classAtt.numValues()];
        
        // no true child strategy
        doNoTrueChild(classAtt, preds);
      }
      
      return preds;
    }
  }
  
  /**
   * Enumerated type for the mining function
   */
  enum MiningFunction {
    CLASSIFICATION,
    REGRESSION;
  }
  
  enum MissingValueStrategy {
    LASTPREDICTION("lastPrediction"),
    NULLPREDICTION("nullPrediction"),
    DEFAULTCHILD("defaultChild"),
    WEIGHTEDCONFIDENCE("weightedConfidence"),
    AGGREGATENODES("aggregateNodes"),
    NONE("none");
    
    private final String m_stringVal;
    
    MissingValueStrategy(String name) {
      m_stringVal = name;
    }
    
    public String toString() {
      return m_stringVal;
    }
  }
  
  enum NoTrueChildStrategy {
    RETURNNULLPREDICTION("returnNullPrediction"),
    RETURNLASTPREDICTION("returnLastPrediction");
    
    private final String m_stringVal;
    
    NoTrueChildStrategy(String name) {
      m_stringVal = name;
    }
    
    public String toString() {
      return m_stringVal;
    }
  }
  
  enum SplitCharacteristic {
    BINARYSPLIT("binarySplit"),
    MULTISPLIT("multiSplit");
  
    private final String m_stringVal;
    
    SplitCharacteristic(String name) {
      m_stringVal = name;
    }
    
    public String toString() {
      return m_stringVal;
    }  
  }
  
  /** The mining function */
  protected MiningFunction m_functionType = MiningFunction.CLASSIFICATION;
  
  /** The missing value strategy */
  protected MissingValueStrategy m_missingValueStrategy = MissingValueStrategy.NONE;
  
  /** 
   * The missing value penalty (if defined). 
   * We don't actually make use of this since we always return 
   * full probability distributions.
   */
  protected double m_missingValuePenalty = Utils.missingValue();
  
  /** The no true child strategy to use */
  protected NoTrueChildStrategy m_noTrueChildStrategy = NoTrueChildStrategy.RETURNNULLPREDICTION;
  
  /** The splitting type */
  protected SplitCharacteristic m_splitCharacteristic = SplitCharacteristic.MULTISPLIT;
  
  /** The root of the tree */
  protected TreeNode m_root;
  
  public TreeModel(Element model, Instances dataDictionary, 
      MiningSchema miningSchema) throws Exception {
    
    super(dataDictionary, miningSchema);
    
    if (!getPMMLVersion().equals("3.2")) {
      // TODO: might have to throw an exception and only support 3.2
    }
    
    String fn = model.getAttribute("functionName");
    if (fn.equals("regression")) {
      m_functionType = MiningFunction.REGRESSION;
    }
    
    // get the missing value strategy (if any)
    String missingVS = model.getAttribute("missingValueStrategy");
    if (missingVS != null && missingVS.length() > 0) {
      for (MissingValueStrategy m : MissingValueStrategy.values()) {
        if (m.toString().equals(missingVS)) {
          m_missingValueStrategy = m;
          break;
        }
      }
    }

    // get the missing value penalty (if any)
    String missingP = model.getAttribute("missingValuePenalty");
    if (missingP != null && missingP.length() > 0) {
      // try to parse as a number
      try {
        m_missingValuePenalty = Double.parseDouble(missingP);
      } catch (NumberFormatException ex) {
        System.err.println("[TreeModel] WARNING: " +
          "couldn't parse supplied missingValuePenalty as a number");
      }
    }

    String splitC = model.getAttribute("splitCharacteristic");

    if (splitC != null && splitC.length() > 0) {
      for (SplitCharacteristic s : SplitCharacteristic.values()) {
        if (s.toString().equals(splitC)) {
          m_splitCharacteristic = s;
          break;
        }
      }
    }
    
    // find the root node of the tree
    NodeList children = model.getChildNodes();
    for (int i = 0; i < children.getLength(); i++) {
      Node child = children.item(i);
      if (child.getNodeType() == Node.ELEMENT_NODE) {
        String tagName = ((Element)child).getTagName();
        if (tagName.equals("Node")) {
          m_root = new TreeNode((Element)child, miningSchema);          
          break;
        }
      }
    }    
  }
  
  /**                                                                                                             
   * Classifies the given test instance. The instance has to belong to a                                          
   * dataset when it's being classified.                                                          
   *                                                                                                              
   * @param inst the instance to be classified                                                                
   * @return the predicted most likely class for the instance or                                                  
   * Utils.missingValue() if no prediction is made                                                             
   * @exception Exception if an error occurred during the prediction                                              
   */
  public double[] distributionForInstance(Instance inst) throws Exception {
    if (!m_initialized) {
      mapToMiningSchema(inst.dataset());
    }
    double[] preds = null;
    
    if (m_miningSchema.getFieldsAsInstances().classAttribute().isNumeric()) {
      preds = new double[1];
    } else {
      preds = new double[m_miningSchema.getFieldsAsInstances().classAttribute().numValues()];
    }
    
    double[] incoming = m_fieldsMap.instanceToSchema(inst, m_miningSchema);
    
    preds = m_root.score(incoming, m_miningSchema.getFieldsAsInstances().classAttribute());
    
   return preds; 
  }
  
  public String toString() {
    StringBuffer temp = new StringBuffer();

    temp.append("PMML version " + getPMMLVersion());
    if (!getCreatorApplication().equals("?")) {
      temp.append("\nApplication: " + getCreatorApplication());
    }
    temp.append("\nPMML Model: TreeModel");
    temp.append("\n\n");
    temp.append(m_miningSchema);
    
    temp.append("Split-type: " + m_splitCharacteristic + "\n");
    temp.append("No true child strategy: " + m_noTrueChildStrategy + "\n");
    temp.append("Missing value strategy: " + m_missingValueStrategy + "\n");
    
    temp.append(m_root.toString());
    
    return temp.toString();
  }
  
  public String graph() throws Exception {
    StringBuffer text = new StringBuffer();
    text.append("digraph PMMTree {\n");
    
    m_root.dumpGraph(text);
    
    text.append("}\n");
    
    return text.toString();
  }

  public String getRevision() {
    return RevisionUtils.extract("$Revision: 5987 $");
  }

  public int graphType() {
    return Drawable.TREE;
  }
}