source: branches/MetisMQI/src/main/java/weka/classifiers/trees/ADTree.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.
 */

/*
 *    ADTree.java
 *    Copyright (C) 2001 University of Waikato, Hamilton, New Zealand
 *
 */

package weka.classifiers.trees;

import weka.classifiers.Classifier;
import weka.classifiers.AbstractClassifier;
import weka.classifiers.IterativeClassifier;
import weka.classifiers.trees.adtree.PredictionNode;
import weka.classifiers.trees.adtree.ReferenceInstances;
import weka.classifiers.trees.adtree.Splitter;
import weka.classifiers.trees.adtree.TwoWayNominalSplit;
import weka.classifiers.trees.adtree.TwoWayNumericSplit;
import weka.core.AdditionalMeasureProducer;
import weka.core.Attribute;
import weka.core.Capabilities;
import weka.core.Drawable;
import weka.core.FastVector;
import weka.core.Instance;
import weka.core.Instances;
import weka.core.Option;
import weka.core.OptionHandler;
import weka.core.RevisionUtils;
import weka.core.SelectedTag;
import weka.core.SerializedObject;
import weka.core.Tag;
import weka.core.TechnicalInformation;
import weka.core.TechnicalInformationHandler;
import weka.core.Utils;
import weka.core.WeightedInstancesHandler;
import weka.core.Capabilities.Capability;
import weka.core.TechnicalInformation.Field;
import weka.core.TechnicalInformation.Type;

import java.util.Enumeration;
import java.util.Random;
import java.util.Vector;

/**
 <!-- globalinfo-start -->
 * Class for generating an alternating decision tree. The basic algorithm is based on:<br/>
 * <br/>
 * Freund, Y., Mason, L.: The alternating decision tree learning algorithm. In: Proceeding of the Sixteenth International Conference on Machine Learning, Bled, Slovenia, 124-133, 1999.<br/>
 * <br/>
 * This version currently only supports two-class problems. The number of boosting iterations needs to be manually tuned to suit the dataset and the desired complexity/accuracy tradeoff. Induction of the trees has been optimized, and heuristic search methods have been introduced to speed learning.
 * <p/>
 <!-- globalinfo-end -->
 *
 <!-- technical-bibtex-start -->
 * BibTeX:
 * <pre>
 * &#64;inproceedings{Freund1999,
 *    address = {Bled, Slovenia},
 *    author = {Freund, Y. and Mason, L.},
 *    booktitle = {Proceeding of the Sixteenth International Conference on Machine Learning},
 *    pages = {124-133},
 *    title = {The alternating decision tree learning algorithm},
 *    year = {1999}
 * }
 * </pre>
 * <p/>
 <!-- technical-bibtex-end -->
 *
 <!-- options-start -->
 * Valid options are: <p/>
 * 
 * <pre> -B &lt;number of boosting iterations&gt;
 *  Number of boosting iterations.
 *  (Default = 10)</pre>
 * 
 * <pre> -E &lt;-3|-2|-1|&gt;=0&gt;
 *  Expand nodes: -3(all), -2(weight), -1(z_pure), &gt;=0 seed for random walk
 *  (Default = -3)</pre>
 * 
 * <pre> -D
 *  Save the instance data with the model</pre>
 * 
 <!-- options-end -->
 *
 * @author Richard Kirkby (rkirkby@cs.waikato.ac.nz)
 * @author Bernhard Pfahringer (bernhard@cs.waikato.ac.nz)
 * @version $Revision: 5928 $
 */
public class ADTree
  extends AbstractClassifier 
  implements OptionHandler, Drawable, AdditionalMeasureProducer,
             WeightedInstancesHandler, IterativeClassifier, 
             TechnicalInformationHandler {

  /** for serialization */
  static final long serialVersionUID = -1532264837167690683L;
  
  /**
   * Returns a string describing classifier
   * @return a description suitable for
   * displaying in the explorer/experimenter gui
   */
  public String globalInfo() {

    return  "Class for generating an alternating decision tree. The basic "
      + "algorithm is based on:\n\n"
      + getTechnicalInformation().toString() + "\n\n"
      + "This version currently only supports two-class problems. The number of boosting "
      + "iterations needs to be manually tuned to suit the dataset and the desired "
      + "complexity/accuracy tradeoff. Induction of the trees has been optimized, and heuristic "
      + "search methods have been introduced to speed learning.";
  }

  /** search mode: Expand all paths */
  public static final int SEARCHPATH_ALL = 0;
  /** search mode: Expand the heaviest path */
  public static final int SEARCHPATH_HEAVIEST = 1;
  /** search mode: Expand the best z-pure path */
  public static final int SEARCHPATH_ZPURE = 2;
  /** search mode: Expand a random path */
  public static final int SEARCHPATH_RANDOM = 3;
  /** The search modes */
  public static final Tag [] TAGS_SEARCHPATH = {
    new Tag(SEARCHPATH_ALL, "Expand all paths"),
    new Tag(SEARCHPATH_HEAVIEST, "Expand the heaviest path"),
    new Tag(SEARCHPATH_ZPURE, "Expand the best z-pure path"),
    new Tag(SEARCHPATH_RANDOM, "Expand a random path")
  };

  /** The instances used to train the tree */
  protected Instances m_trainInstances;

  /** The root of the tree */
  protected PredictionNode m_root = null;

  /** The random number generator - used for the random search heuristic */
  protected Random m_random = null; 

  /** The number of the last splitter added to the tree */
  protected int m_lastAddedSplitNum = 0;

  /** An array containing the inidices to the numeric attributes in the data */
  protected int[] m_numericAttIndices;

  /** An array containing the inidices to the nominal attributes in the data */
  protected int[] m_nominalAttIndices;

  /** The total weight of the instances - used to speed Z calculations */
  protected double m_trainTotalWeight;

  /** The training instances with positive class - referencing the training dataset */
  protected ReferenceInstances m_posTrainInstances;

  /** The training instances with negative class - referencing the training dataset */
  protected ReferenceInstances m_negTrainInstances;

  /** The best node to insert under, as found so far by the latest search */
  protected PredictionNode m_search_bestInsertionNode;

  /** The best splitter to insert, as found so far by the latest search */
  protected Splitter m_search_bestSplitter;

  /** The smallest Z value found so far by the latest search */
  protected double m_search_smallestZ;

  /** The positive instances that apply to the best path found so far */
  protected Instances m_search_bestPathPosInstances;

  /** The negative instances that apply to the best path found so far */
  protected Instances m_search_bestPathNegInstances;

  /** Statistics - the number of prediction nodes investigated during search */
  protected int m_nodesExpanded = 0;

  /** Statistics - the number of instances processed during search */
  protected int m_examplesCounted = 0;

  /** Option - the number of boosting iterations o perform */
  protected int m_boostingIterations = 10;

  /** Option - the search mode */
  protected int m_searchPath = 0;

  /** Option - the seed to use for a random search */
  protected int m_randomSeed = 0; 

  /** Option - whether the tree should remember the instance data */
  protected boolean m_saveInstanceData = false; 

  /**
   * Returns an instance of a TechnicalInformation object, containing 
   * detailed information about the technical background of this class,
   * e.g., paper reference or book this class is based on.
   * 
   * @return the technical information about this class
   */
  public TechnicalInformation getTechnicalInformation() {
    TechnicalInformation        result;
    
    result = new TechnicalInformation(Type.INPROCEEDINGS);
    result.setValue(Field.AUTHOR, "Freund, Y. and Mason, L.");
    result.setValue(Field.YEAR, "1999");
    result.setValue(Field.TITLE, "The alternating decision tree learning algorithm");
    result.setValue(Field.BOOKTITLE, "Proceeding of the Sixteenth International Conference on Machine Learning");
    result.setValue(Field.ADDRESS, "Bled, Slovenia");
    result.setValue(Field.PAGES, "124-133");
    
    return result;
  }

  /**
   * Sets up the tree ready to be trained, using two-class optimized method.
   *
   * @param instances the instances to train the tree with
   * @exception Exception if training data is unsuitable
   */
  public void initClassifier(Instances instances) throws Exception {

    // clear stats
    m_nodesExpanded = 0;
    m_examplesCounted = 0;
    m_lastAddedSplitNum = 0;

    // prepare the random generator
    m_random = new Random(m_randomSeed);

    // create training set
    m_trainInstances = new Instances(instances);

    // create positive/negative subsets
    m_posTrainInstances = new ReferenceInstances(m_trainInstances,
                                                 m_trainInstances.numInstances());
    m_negTrainInstances = new ReferenceInstances(m_trainInstances,
                                                 m_trainInstances.numInstances());
    for (Enumeration e = m_trainInstances.enumerateInstances(); e.hasMoreElements(); ) {
      Instance inst = (Instance) e.nextElement();
      if ((int) inst.classValue() == 0)
        m_negTrainInstances.addReference(inst); // belongs in negative class
      else
        m_posTrainInstances.addReference(inst); // belongs in positive class
    }
    m_posTrainInstances.compactify();
    m_negTrainInstances.compactify();

    // create the root prediction node
    double rootPredictionValue = calcPredictionValue(m_posTrainInstances,
                                                     m_negTrainInstances);
    m_root = new PredictionNode(rootPredictionValue);

    // pre-adjust weights
    updateWeights(m_posTrainInstances, m_negTrainInstances, rootPredictionValue);
    
    // pre-calculate what we can
    generateAttributeIndicesSingle();
  }

  /**
   * Performs one iteration.
   * 
   * @param iteration the index of the current iteration (0-based)
   * @exception Exception if this iteration fails 
   */  
  public void next(int iteration) throws Exception {

    boost();
  }

  /**
   * Performs a single boosting iteration, using two-class optimized method.
   * Will add a new splitter node and two prediction nodes to the tree
   * (unless merging takes place).
   *
   * @exception Exception if try to boost without setting up tree first or there are no 
   * instances to train with
   */
  public void boost() throws Exception {

    if (m_trainInstances == null || m_trainInstances.numInstances() == 0)
      throw new Exception("Trying to boost with no training data");

    // perform the search
    searchForBestTestSingle();

    if (m_search_bestSplitter == null) return; // handle empty instances

    // create the new nodes for the tree, updating the weights
    for (int i=0; i<2; i++) {
      Instances posInstances =
        m_search_bestSplitter.instancesDownBranch(i, m_search_bestPathPosInstances);
      Instances negInstances =
        m_search_bestSplitter.instancesDownBranch(i, m_search_bestPathNegInstances);
      double predictionValue = calcPredictionValue(posInstances, negInstances);
      PredictionNode newPredictor = new PredictionNode(predictionValue);
      updateWeights(posInstances, negInstances, predictionValue);
      m_search_bestSplitter.setChildForBranch(i, newPredictor);
    }

    // insert the new nodes
    m_search_bestInsertionNode.addChild((Splitter) m_search_bestSplitter, this);

    // free memory
    m_search_bestPathPosInstances = null;
    m_search_bestPathNegInstances = null;
    m_search_bestSplitter = null;
  }

  /**
   * Generates the m_nominalAttIndices and m_numericAttIndices arrays to index
   * the respective attribute types in the training data.
   *
   */
  private void generateAttributeIndicesSingle() {

    // insert indices into vectors
    FastVector nominalIndices = new FastVector();
    FastVector numericIndices = new FastVector();

    for (int i=0; i<m_trainInstances.numAttributes(); i++) {
      if (i != m_trainInstances.classIndex()) {
        if (m_trainInstances.attribute(i).isNumeric())
          numericIndices.addElement(new Integer(i));
        else
          nominalIndices.addElement(new Integer(i));
      }
    }

    // create nominal array
    m_nominalAttIndices = new int[nominalIndices.size()];
    for (int i=0; i<nominalIndices.size(); i++)
      m_nominalAttIndices[i] = ((Integer)nominalIndices.elementAt(i)).intValue();
    
    // create numeric array
    m_numericAttIndices = new int[numericIndices.size()];
    for (int i=0; i<numericIndices.size(); i++)
      m_numericAttIndices[i] = ((Integer)numericIndices.elementAt(i)).intValue();
  }

  /**
   * Performs a search for the best test (splitter) to add to the tree, by aiming to
   * minimize the Z value.
   *
   * @exception Exception if search fails
   */
  private void searchForBestTestSingle() throws Exception {

    // keep track of total weight for efficient wRemainder calculations
    m_trainTotalWeight = m_trainInstances.sumOfWeights();
    
    m_search_smallestZ = Double.POSITIVE_INFINITY;
    searchForBestTestSingle(m_root, m_posTrainInstances, m_negTrainInstances);
  }

  /**
   * Recursive function that carries out search for the best test (splitter) to add to
   * this part of the tree, by aiming to minimize the Z value. Performs Z-pure cutoff to
   * reduce search space.
   *
   * @param currentNode the root of the subtree to be searched, and the current node 
   * being considered as parent of a new split
   * @param posInstances the positive-class instances that apply at this node
   * @param negInstances the negative-class instances that apply at this node
   * @exception Exception if search fails
   */
  private void searchForBestTestSingle(PredictionNode currentNode,
                                       Instances posInstances, Instances negInstances)
    throws Exception {

    // don't investigate pure or empty nodes any further
    if (posInstances.numInstances() == 0 || negInstances.numInstances() == 0) return;

    // do z-pure cutoff
    if (calcZpure(posInstances, negInstances) >= m_search_smallestZ) return;

    // keep stats
    m_nodesExpanded++;
    m_examplesCounted += posInstances.numInstances() + negInstances.numInstances();

    // evaluate static splitters (nominal)
    for (int i=0; i<m_nominalAttIndices.length; i++)
      evaluateNominalSplitSingle(m_nominalAttIndices[i], currentNode,
                                 posInstances, negInstances);

    // evaluate dynamic splitters (numeric)
    if (m_numericAttIndices.length > 0) {

      // merge the two sets of instances into one
      Instances allInstances = new Instances(posInstances);
      for (Enumeration e = negInstances.enumerateInstances(); e.hasMoreElements(); )
        allInstances.add((Instance) e.nextElement());
    
      // use method of finding the optimal Z split-point
      for (int i=0; i<m_numericAttIndices.length; i++)
        evaluateNumericSplitSingle(m_numericAttIndices[i], currentNode,
                                   posInstances, negInstances, allInstances);
    }

    if (currentNode.getChildren().size() == 0) return;

    // keep searching
    switch (m_searchPath) {
    case SEARCHPATH_ALL:
      goDownAllPathsSingle(currentNode, posInstances, negInstances);
      break;
    case SEARCHPATH_HEAVIEST: 
      goDownHeaviestPathSingle(currentNode, posInstances, negInstances);
      break;
    case SEARCHPATH_ZPURE: 
      goDownZpurePathSingle(currentNode, posInstances, negInstances);
      break;
    case SEARCHPATH_RANDOM: 
      goDownRandomPathSingle(currentNode, posInstances, negInstances);
      break;
    }
  }

  /**
   * Continues single (two-class optimized) search by investigating every node in the
   * subtree under currentNode.
   *
   * @param currentNode the root of the subtree to be searched
   * @param posInstances the positive-class instances that apply at this node
   * @param negInstances the negative-class instances that apply at this node
   * @exception Exception if search fails
   */
  private void goDownAllPathsSingle(PredictionNode currentNode,
                                    Instances posInstances, Instances negInstances)
    throws Exception {

    for (Enumeration e = currentNode.children(); e.hasMoreElements(); ) {
      Splitter split = (Splitter) e.nextElement();
      for (int i=0; i<split.getNumOfBranches(); i++)
        searchForBestTestSingle(split.getChildForBranch(i),
                                split.instancesDownBranch(i, posInstances),
                                split.instancesDownBranch(i, negInstances));
    }
  }

  /**
   * Continues single (two-class optimized) search by investigating only the path
   * with the most heavily weighted instances.
   *
   * @param currentNode the root of the subtree to be searched
   * @param posInstances the positive-class instances that apply at this node
   * @param negInstances the negative-class instances that apply at this node
   * @exception Exception if search fails
   */
  private void goDownHeaviestPathSingle(PredictionNode currentNode,
                                        Instances posInstances, Instances negInstances)
    throws Exception {

    Splitter heaviestSplit = null;
    int heaviestBranch = 0;
    double largestWeight = 0.0;
    for (Enumeration e = currentNode.children(); e.hasMoreElements(); ) {
      Splitter split = (Splitter) e.nextElement();
      for (int i=0; i<split.getNumOfBranches(); i++) {
        double weight =
          split.instancesDownBranch(i, posInstances).sumOfWeights() +
          split.instancesDownBranch(i, negInstances).sumOfWeights();
        if (weight > largestWeight) {
          heaviestSplit = split;
          heaviestBranch = i;
          largestWeight = weight;
        }
      }
    }
    if (heaviestSplit != null)
      searchForBestTestSingle(heaviestSplit.getChildForBranch(heaviestBranch),
                              heaviestSplit.instancesDownBranch(heaviestBranch,
                                                                posInstances),
                              heaviestSplit.instancesDownBranch(heaviestBranch,
                                                                negInstances));
  }

  /**
   * Continues single (two-class optimized) search by investigating only the path
   * with the best Z-pure value at each branch.
   *
   * @param currentNode the root of the subtree to be searched
   * @param posInstances the positive-class instances that apply at this node
   * @param negInstances the negative-class instances that apply at this node
   * @exception Exception if search fails
   */
  private void goDownZpurePathSingle(PredictionNode currentNode,
                                     Instances posInstances, Instances negInstances)
    throws Exception {

    double lowestZpure = m_search_smallestZ; // do z-pure cutoff
    PredictionNode bestPath = null;
    Instances bestPosSplit = null, bestNegSplit = null;

    // search for branch with lowest Z-pure
    for (Enumeration e = currentNode.children(); e.hasMoreElements(); ) {
      Splitter split = (Splitter) e.nextElement();
      for (int i=0; i<split.getNumOfBranches(); i++) {
        Instances posSplit = split.instancesDownBranch(i, posInstances);
        Instances negSplit = split.instancesDownBranch(i, negInstances);
        double newZpure = calcZpure(posSplit, negSplit);
        if (newZpure < lowestZpure) {
          lowestZpure = newZpure;
          bestPath = split.getChildForBranch(i);
          bestPosSplit = posSplit;
          bestNegSplit = negSplit;
        }
      }
    }

    if (bestPath != null)
      searchForBestTestSingle(bestPath, bestPosSplit, bestNegSplit);
  }

  /**
   * Continues single (two-class optimized) search by investigating a random path.
   *
   * @param currentNode the root of the subtree to be searched
   * @param posInstances the positive-class instances that apply at this node
   * @param negInstances the negative-class instances that apply at this node
   * @exception Exception if search fails
   */
  private void goDownRandomPathSingle(PredictionNode currentNode,
                                      Instances posInstances, Instances negInstances)
    throws Exception {

    FastVector children = currentNode.getChildren();
    Splitter split = (Splitter) children.elementAt(getRandom(children.size()));
    int branch = getRandom(split.getNumOfBranches());
    searchForBestTestSingle(split.getChildForBranch(branch),
                            split.instancesDownBranch(branch, posInstances),
                            split.instancesDownBranch(branch, negInstances));
  }

  /**
   * Investigates the option of introducing a nominal split under currentNode. If it
   * finds a split that has a Z-value lower than has already been found it will
   * update the search information to record this as the best option so far. 
   *
   * @param attIndex index of a nominal attribute to create a split from
   * @param currentNode the parent under which a split is to be considered
   * @param posInstances the positive-class instances that apply at this node
   * @param negInstances the negative-class instances that apply at this node
   */
  private void evaluateNominalSplitSingle(int attIndex, PredictionNode currentNode,
                                          Instances posInstances, Instances negInstances)
  {
    
    double[] indexAndZ = findLowestZNominalSplit(posInstances, negInstances, attIndex);

    if (indexAndZ[1] < m_search_smallestZ) {
      m_search_smallestZ = indexAndZ[1];
      m_search_bestInsertionNode = currentNode;
      m_search_bestSplitter = new TwoWayNominalSplit(attIndex, (int) indexAndZ[0]);
      m_search_bestPathPosInstances = posInstances;
      m_search_bestPathNegInstances = negInstances;
    }
  }

  /**
   * Investigates the option of introducing a two-way numeric split under currentNode.
   * If it finds a split that has a Z-value lower than has already been found it will
   * update the search information to record this as the best option so far. 
   *
   * @param attIndex index of a numeric attribute to create a split from
   * @param currentNode the parent under which a split is to be considered
   * @param posInstances the positive-class instances that apply at this node
   * @param negInstances the negative-class instances that apply at this node
   * @param allInstances all of the instances the apply at this node (pos+neg combined)
   * @throws Exception in case of an error
   */
  private void evaluateNumericSplitSingle(int attIndex, PredictionNode currentNode,
                                          Instances posInstances, Instances negInstances,
                                          Instances allInstances)
    throws Exception {
    
    double[] splitAndZ = findLowestZNumericSplit(allInstances, attIndex);

    if (splitAndZ[1] < m_search_smallestZ) {
      m_search_smallestZ = splitAndZ[1];
      m_search_bestInsertionNode = currentNode;
      m_search_bestSplitter = new TwoWayNumericSplit(attIndex, splitAndZ[0]);
      m_search_bestPathPosInstances = posInstances;
      m_search_bestPathNegInstances = negInstances;
    }
  }

  /**
   * Calculates the prediction value used for a particular set of instances.
   *
   * @param posInstances the positive-class instances
   * @param negInstances the negative-class instances
   * @return the prediction value
   */
  private double calcPredictionValue(Instances posInstances, Instances negInstances) {
    
    return 0.5 * Math.log( (posInstances.sumOfWeights() + 1.0)
                          / (negInstances.sumOfWeights() + 1.0) );
  }

  /**
   * Calculates the Z-pure value for a particular set of instances.
   *
   * @param posInstances the positive-class instances
   * @param negInstances the negative-class instances
   * @return the Z-pure value
   */
  private double calcZpure(Instances posInstances, Instances negInstances) {
    
    double posWeight = posInstances.sumOfWeights();
    double negWeight = negInstances.sumOfWeights();
    return (2.0 * (Math.sqrt(posWeight+1.0) + Math.sqrt(negWeight+1.0))) + 
      (m_trainTotalWeight - (posWeight + negWeight));
  }

  /**
   * Updates the weights of instances that are influenced by a new prediction value.
   *
   * @param posInstances positive-class instances to which the prediction value applies
   * @param negInstances negative-class instances to which the prediction value applies
   * @param predictionValue the new prediction value
   */
  private void updateWeights(Instances posInstances, Instances negInstances,
                             double predictionValue) {
    
    // do positives
    double weightMultiplier = Math.pow(Math.E, -predictionValue);
    for (Enumeration e = posInstances.enumerateInstances(); e.hasMoreElements(); ) {
      Instance inst = (Instance) e.nextElement();
      inst.setWeight(inst.weight() * weightMultiplier);
    }
    // do negatives
    weightMultiplier = Math.pow(Math.E, predictionValue);
    for (Enumeration e = negInstances.enumerateInstances(); e.hasMoreElements(); ) {
      Instance inst = (Instance) e.nextElement();
      inst.setWeight(inst.weight() * weightMultiplier);
    }
  }

  /**
   * Finds the nominal attribute value to split on that results in the lowest Z-value.
   *
   * @param posInstances the positive-class instances to split
   * @param negInstances the negative-class instances to split
   * @param attIndex the index of the nominal attribute to find a split for
   * @return a double array, index[0] contains the value to split on, index[1] contains
   * the Z-value of the split
   */
  private double[] findLowestZNominalSplit(Instances posInstances, Instances negInstances,
                                           int attIndex)
  {
    
    double lowestZ = Double.MAX_VALUE;
    int bestIndex = 0;

    // set up arrays
    double[] posWeights = attributeValueWeights(posInstances, attIndex);
    double[] negWeights = attributeValueWeights(negInstances, attIndex);
    double posWeight = Utils.sum(posWeights);
    double negWeight = Utils.sum(negWeights);

    int maxIndex = posWeights.length;
    if (maxIndex == 2) maxIndex = 1; // avoid repeating due to 2-way symmetry

    for (int i = 0; i < maxIndex; i++) {
      // calculate Z
      double w1 = posWeights[i] + 1.0;
      double w2 = negWeights[i] + 1.0;
      double w3 = posWeight - w1 + 2.0;
      double w4 = negWeight - w2 + 2.0;
      double wRemainder = m_trainTotalWeight + 4.0 - (w1 + w2 + w3 + w4);
      double newZ = (2.0 * (Math.sqrt(w1 * w2) + Math.sqrt(w3 * w4))) + wRemainder;

      // record best option
      if (newZ < lowestZ) { 
        lowestZ = newZ;
        bestIndex = i;
      }
    }

    // return result
    double[] indexAndZ = new double[2];
    indexAndZ[0] = (double) bestIndex;
    indexAndZ[1] = lowestZ;
    return indexAndZ; 
  }

  /**
   * Simultanously sum the weights of all attribute values for all instances.
   *
   * @param instances the instances to get the weights from 
   * @param attIndex index of the attribute to be evaluated
   * @return a double array containing the weight of each attribute value
   */    
  private double[] attributeValueWeights(Instances instances, int attIndex)
  {
    
    double[] weights = new double[instances.attribute(attIndex).numValues()];
    for(int i = 0; i < weights.length; i++) weights[i] = 0.0;

    for (Enumeration e = instances.enumerateInstances(); e.hasMoreElements(); ) {
      Instance inst = (Instance) e.nextElement();
      if (!inst.isMissing(attIndex)) weights[(int)inst.value(attIndex)] += inst.weight();
    }
    return weights;
  }

  /**
   * Finds the numeric split-point that results in the lowest Z-value.
   *
   * @param instances the instances to find a split for
   * @param attIndex the index of the numeric attribute to find a split for
   * @return a double array, index[0] contains the split-point, index[1] contains the
   * Z-value of the split
   * @throws Exception in case of an error
   */
  private double[] findLowestZNumericSplit(Instances instances, int attIndex)
    throws Exception {
    
    double splitPoint = 0.0;
    double bestVal = Double.MAX_VALUE, currVal, currCutPoint;
    int numMissing = 0;
    double[][] distribution = new double[3][instances.numClasses()];   

    // compute counts for all the values
    for (int i = 0; i < instances.numInstances(); i++) {
      Instance inst = instances.instance(i);
      if (!inst.isMissing(attIndex)) {
        distribution[1][(int)inst.classValue()] += inst.weight();
      } else {
        distribution[2][(int)inst.classValue()] += inst.weight();
        numMissing++;
      }
    }

    // sort instances
    instances.sort(attIndex);
    
    // make split counts for each possible split and evaluate
    for (int i = 0; i < instances.numInstances() - (numMissing + 1); i++) {
      Instance inst = instances.instance(i);
      Instance instPlusOne = instances.instance(i + 1);
      distribution[0][(int)inst.classValue()] += inst.weight();
      distribution[1][(int)inst.classValue()] -= inst.weight();
      if (Utils.sm(inst.value(attIndex), instPlusOne.value(attIndex))) {
        currCutPoint = (inst.value(attIndex) + instPlusOne.value(attIndex)) / 2.0;
        currVal = conditionedZOnRows(distribution);
        if (currVal < bestVal) {
          splitPoint = currCutPoint;
          bestVal = currVal;
        }
      }
    }
        
    double[] splitAndZ = new double[2];
    splitAndZ[0] = splitPoint;
    splitAndZ[1] = bestVal;
    return splitAndZ;
  }

  /**
   * Calculates the Z-value from the rows of a weight distribution array.
   *
   * @param distribution the weight distribution
   * @return the Z-value
   */
  private double conditionedZOnRows(double [][] distribution) {
    
    double w1 = distribution[0][0] + 1.0;
    double w2 = distribution[0][1] + 1.0;
    double w3 = distribution[1][0] + 1.0; 
    double w4 = distribution[1][1] + 1.0;
    double wRemainder = m_trainTotalWeight + 4.0 - (w1 + w2 + w3 + w4);
    return (2.0 * (Math.sqrt(w1 * w2) + Math.sqrt(w3 * w4))) + wRemainder;
  }

  /**
   * Returns the class probability distribution for an instance.
   *
   * @param instance the instance to be classified
   * @return the distribution the tree generates for the instance
   */
  public double[] distributionForInstance(Instance instance) {
    
    double predVal = predictionValueForInstance(instance, m_root, 0.0);
    
    double[] distribution = new double[2];
    distribution[0] = 1.0 / (1.0 + Math.pow(Math.E, predVal));
    distribution[1] = 1.0 / (1.0 + Math.pow(Math.E, -predVal));

    return distribution;
  }

  /**
   * Returns the class prediction value (vote) for an instance.
   *
   * @param inst the instance
   * @param currentNode the root of the tree to get the values from
   * @param currentValue the current value before adding the value contained in the
   * subtree
   * @return the class prediction value (vote)
   */
  protected double predictionValueForInstance(Instance inst, PredictionNode currentNode,
                                            double currentValue) {
    
    currentValue += currentNode.getValue();
    for (Enumeration e = currentNode.children(); e.hasMoreElements(); ) {
      Splitter split = (Splitter) e.nextElement();
      int branch = split.branchInstanceGoesDown(inst);
      if (branch >= 0)
        currentValue = predictionValueForInstance(inst, split.getChildForBranch(branch),
                                                  currentValue);
    }
    return currentValue;
  }

  /**
   * Returns a description of the classifier.
   *
   * @return a string containing a description of the classifier
   */
  public String toString() {
    
    if (m_root == null)
      return ("ADTree not built yet");
    else {
      return ("Alternating decision tree:\n\n" + toString(m_root, 1) +
              "\nLegend: " + legend() +
              "\nTree size (total number of nodes): " + numOfAllNodes(m_root) + 
              "\nLeaves (number of predictor nodes): " + numOfPredictionNodes(m_root)
              );
    }
  }

  /**
   * Traverses the tree, forming a string that describes it.
   *
   * @param currentNode the current node under investigation
   * @param level the current level in the tree
   * @return the string describing the subtree
   */      
  protected String toString(PredictionNode currentNode, int level) {
    
    StringBuffer text = new StringBuffer();
    
    text.append(": " + Utils.doubleToString(currentNode.getValue(),3));
    
    for (Enumeration e = currentNode.children(); e.hasMoreElements(); ) {
      Splitter split = (Splitter) e.nextElement();
            
      for (int j=0; j<split.getNumOfBranches(); j++) {
        PredictionNode child = split.getChildForBranch(j);
        if (child != null) {
          text.append("\n");
          for (int k = 0; k < level; k++) {
            text.append("|  ");
          }
          text.append("(" + split.orderAdded + ")");
          text.append(split.attributeString(m_trainInstances) + " "
                      + split.comparisonString(j, m_trainInstances));
          text.append(toString(child, level + 1));
        }
      }
    }
    return text.toString();
  }

  /**
   *  Returns the type of graph this classifier
   *  represents.
   *  @return Drawable.TREE
   */   
  public int graphType() {
      return Drawable.TREE;
  }

  /**
   * Returns graph describing the tree.
   *
   * @return the graph of the tree in dotty format
   * @exception Exception if something goes wrong
   */
  public String graph() throws Exception {
    
    StringBuffer text = new StringBuffer();
    text.append("digraph ADTree {\n");
    graphTraverse(m_root, text, 0, 0, m_trainInstances);
    return text.toString() +"}\n";
  }

  /**
   * Traverses the tree, graphing each node.
   *
   * @param currentNode the currentNode under investigation
   * @param text the string built so far
   * @param splitOrder the order the parent splitter was added to the tree
   * @param predOrder the order this predictor was added to the split
   * @param instances the data to work on
   * @exception Exception if something goes wrong
   */       
  protected void graphTraverse(PredictionNode currentNode, StringBuffer text,
                               int splitOrder, int predOrder, Instances instances)
    throws Exception {
    
    text.append("S" + splitOrder + "P" + predOrder + " [label=\"");
    text.append(Utils.doubleToString(currentNode.getValue(),3));
    if (splitOrder == 0) // show legend in root
      text.append(" (" + legend() + ")");
    text.append("\" shape=box style=filled");
    if (instances.numInstances() > 0) text.append(" data=\n" + instances + "\n,\n");
    text.append("]\n");
    for (Enumeration e = currentNode.children(); e.hasMoreElements(); ) {
      Splitter split = (Splitter) e.nextElement();
      text.append("S" + splitOrder + "P" + predOrder + "->" + "S" + split.orderAdded +
                  " [style=dotted]\n");
      text.append("S" + split.orderAdded + " [label=\"" + split.orderAdded + ": " +
                  split.attributeString(m_trainInstances) + "\"]\n");

      for (int i=0; i<split.getNumOfBranches(); i++) {
        PredictionNode child = split.getChildForBranch(i);
        if (child != null) {
          text.append("S" + split.orderAdded + "->" + "S" + split.orderAdded + "P" + i +
                      " [label=\"" + split.comparisonString(i, m_trainInstances) + "\"]\n");
          graphTraverse(child, text, split.orderAdded, i,
                        split.instancesDownBranch(i, instances));
        }
      }
    }  
  }

  /**
   * Returns the legend of the tree, describing how results are to be interpreted.
   *
   * @return a string containing the legend of the classifier
   */
  public String legend() {
    
    Attribute classAttribute = null;
    if (m_trainInstances == null) return "";
    try {classAttribute = m_trainInstances.classAttribute();} catch (Exception x){};
    return ("-ve = " + classAttribute.value(0) +
            ", +ve = " + classAttribute.value(1));
  }

  /**
   * @return tip text for this property suitable for
   * displaying in the explorer/experimenter gui
   */
  public String numOfBoostingIterationsTipText() {

    return "Sets the number of boosting iterations to perform. You will need to manually "
      + "tune this parameter to suit the dataset and the desired complexity/accuracy "
      + "tradeoff. More boosting iterations will result in larger (potentially more "
      + " accurate) trees, but will make learning slower. Each iteration will add 3 nodes "
      + "(1 split + 2 prediction) to the tree unless merging occurs.";
  }

  /**
   * Gets the number of boosting iterations.
   *
   * @return the number of boosting iterations
   */
  public int getNumOfBoostingIterations() {
    
    return m_boostingIterations;
  }

  /**
   * Sets the number of boosting iterations.
   *
   * @param b the number of boosting iterations to use
   */
  public void setNumOfBoostingIterations(int b) {
    
    m_boostingIterations = b; 
  }

  /**
   * @return tip text for this property suitable for
   * displaying in the explorer/experimenter gui
   */
  public String searchPathTipText() {

    return "Sets the type of search to perform when building the tree. The default option"
      + " (Expand all paths) will do an exhaustive search. The other search methods are"
      + " heuristic, so they are not guaranteed to find an optimal solution but they are"
      + " much faster. Expand the heaviest path: searches the path with the most heavily"
      + " weighted instances. Expand the best z-pure path: searches the path determined"
      + " by the best z-pure estimate. Expand a random path: the fastest method, simply"
      + " searches down a single random path on each iteration.";
  }

  /**
   * Gets the method of searching the tree for a new insertion. Will be one of
   * SEARCHPATH_ALL, SEARCHPATH_HEAVIEST, SEARCHPATH_ZPURE, SEARCHPATH_RANDOM.
   *
   * @return the tree searching mode
   */
  public SelectedTag getSearchPath() {

    return new SelectedTag(m_searchPath, TAGS_SEARCHPATH);
  }
  
  /**
   * Sets the method of searching the tree for a new insertion. Will be one of
   * SEARCHPATH_ALL, SEARCHPATH_HEAVIEST, SEARCHPATH_ZPURE, SEARCHPATH_RANDOM.
   *
   * @param newMethod the new tree searching mode
   */
  public void setSearchPath(SelectedTag newMethod) {
    
    if (newMethod.getTags() == TAGS_SEARCHPATH) {
      m_searchPath = newMethod.getSelectedTag().getID();
    }
  }

  /**
   * @return tip text for this property suitable for
   * displaying in the explorer/experimenter gui
   */
  public String randomSeedTipText() {

    return "Sets the random seed to use for a random search.";
  }

  /**
   * Gets random seed for a random walk.
   *
   * @return the random seed
   */
  public int getRandomSeed() {
    
    return m_randomSeed;
  }

  /**
   * Sets random seed for a random walk.
   *
   * @param seed the random seed
   */
  public void setRandomSeed(int seed) {
    
    // the actual random object is created when the tree is initialized
    m_randomSeed = seed; 
  }  

  /**
   * @return tip text for this property suitable for
   * displaying in the explorer/experimenter gui
   */
  public String saveInstanceDataTipText() {

    return "Sets whether the tree is to save instance data - the model will take up more"
      + " memory if it does. If enabled you will be able to visualize the instances at"
      + " the prediction nodes when visualizing the tree.";
  }

  /**
   * Gets whether the tree is to save instance data.
   *
   * @return the random seed
   */
  public boolean getSaveInstanceData() {
    
    return m_saveInstanceData;
  }

  /**
   * Sets whether the tree is to save instance data.
   * 
   * @param v true then the tree saves instance data
   */
  public void setSaveInstanceData(boolean v) {
    
    m_saveInstanceData = v;
  }

  /**
   * Returns an enumeration describing the available options..
   *
   * @return an enumeration of all the available options.
   */
  public Enumeration listOptions() {
    
    Vector newVector = new Vector(3);
    newVector.addElement(new Option(
                                    "\tNumber of boosting iterations.\n"
                                    +"\t(Default = 10)",
                                    "B", 1,"-B <number of boosting iterations>"));
    newVector.addElement(new Option(
                                    "\tExpand nodes: -3(all), -2(weight), -1(z_pure), "
                                    +">=0 seed for random walk\n"
                                    +"\t(Default = -3)",
                                    "E", 1,"-E <-3|-2|-1|>=0>"));
    newVector.addElement(new Option(
                                    "\tSave the instance data with the model",
                                    "D", 0,"-D"));
    return newVector.elements();
  }

  /**
   * Parses a given list of options. Valid options are:<p>
   *
   * -B num <br>
   * Set the number of boosting iterations
   * (default 10) <p>
   *
   * -E num <br>
   * Set the nodes to expand: -3(all), -2(weight), -1(z_pure), >=0 seed for random walk
   * (default -3) <p>
   *
   * -D <br>
   * Save the instance data with the model <p>
   *
   * @param options the list of options as an array of strings
   * @exception Exception if an option is not supported
   */
  public void setOptions(String[] options) throws Exception {
    
    String bString = Utils.getOption('B', options);
    if (bString.length() != 0) setNumOfBoostingIterations(Integer.parseInt(bString));

    String eString = Utils.getOption('E', options);
    if (eString.length() != 0) {
      int value = Integer.parseInt(eString);
      if (value >= 0) {
        setSearchPath(new SelectedTag(SEARCHPATH_RANDOM, TAGS_SEARCHPATH));
        setRandomSeed(value);
      } else setSearchPath(new SelectedTag(value + 3, TAGS_SEARCHPATH));
    }

    setSaveInstanceData(Utils.getFlag('D', options));

    Utils.checkForRemainingOptions(options);
  }

  /**
   * Gets the current settings of ADTree.
   *
   * @return an array of strings suitable for passing to setOptions()
   */
  public String[] getOptions() {
    
    String[] options = new String[6];
    int current = 0;
    options[current++] = "-B"; options[current++] = "" + getNumOfBoostingIterations();
    options[current++] = "-E"; options[current++] = "" +
                                 (m_searchPath == SEARCHPATH_RANDOM ?
                                  m_randomSeed : m_searchPath - 3);
    if (getSaveInstanceData()) options[current++] = "-D";
    while (current < options.length) options[current++] = "";
    return options;
  }

  /**
   * Calls measure function for tree size - the total number of nodes.
   *
   * @return the tree size
   */
  public double measureTreeSize() {
    
    return numOfAllNodes(m_root);
  }

  /**
   * Calls measure function for leaf size - the number of prediction nodes.
   *
   * @return the leaf size
   */
  public double measureNumLeaves() {
    
    return numOfPredictionNodes(m_root);
  }

  /**
   * Calls measure function for prediction leaf size - the number of 
   * prediction nodes without children.
   *
   * @return the leaf size
   */
  public double measureNumPredictionLeaves() {
    
    return numOfPredictionLeafNodes(m_root);
  }

  /**
   * Returns the number of nodes expanded.
   *
   * @return the number of nodes expanded during search
   */
  public double measureNodesExpanded() {
    
    return m_nodesExpanded;
  }

  /**
   * Returns the number of examples "counted".
   *
   * @return the number of nodes processed during search
   */

  public double measureExamplesProcessed() {
    
    return m_examplesCounted;
  }

  /**
   * Returns an enumeration of the additional measure names.
   *
   * @return an enumeration of the measure names
   */
  public Enumeration enumerateMeasures() {
    
    Vector newVector = new Vector(4);
    newVector.addElement("measureTreeSize");
    newVector.addElement("measureNumLeaves");
    newVector.addElement("measureNumPredictionLeaves");
    newVector.addElement("measureNodesExpanded");
    newVector.addElement("measureExamplesProcessed");
    return newVector.elements();
  }
 
  /**
   * Returns the value of the named measure.
   *
   * @param additionalMeasureName the name of the measure to query for its value
   * @return the value of the named measure
   * @exception IllegalArgumentException if the named measure is not supported
   */
  public double getMeasure(String additionalMeasureName) {
    
    if (additionalMeasureName.equalsIgnoreCase("measureTreeSize")) {
      return measureTreeSize();
    }
    else if (additionalMeasureName.equalsIgnoreCase("measureNumLeaves")) {
      return measureNumLeaves();
    }
    else if (additionalMeasureName.equalsIgnoreCase("measureNumPredictionLeaves")) {
      return measureNumPredictionLeaves();
    }
    else if (additionalMeasureName.equalsIgnoreCase("measureNodesExpanded")) {
      return measureNodesExpanded();
    }
    else if (additionalMeasureName.equalsIgnoreCase("measureExamplesProcessed")) {
      return measureExamplesProcessed();
    }
    else {throw new IllegalArgumentException(additionalMeasureName 
                              + " not supported (ADTree)");
    }
  }

  /**
   * Returns the total number of nodes in a tree.
   *
   * @param root the root of the tree being measured
   * @return tree size in number of splitter + prediction nodes
   */       
  protected int numOfAllNodes(PredictionNode root) {
    
    int numSoFar = 0;
    if (root != null) {
      numSoFar++;
      for (Enumeration e = root.children(); e.hasMoreElements(); ) {
        numSoFar++;
        Splitter split = (Splitter) e.nextElement();
        for (int i=0; i<split.getNumOfBranches(); i++)
            numSoFar += numOfAllNodes(split.getChildForBranch(i));
      }
    }
    return numSoFar;
  }

  /**
   * Returns the number of prediction nodes in a tree.
   *
   * @param root the root of the tree being measured
   * @return tree size in number of prediction nodes
   */       
  protected int numOfPredictionNodes(PredictionNode root) {
    
    int numSoFar = 0;
    if (root != null) {
      numSoFar++;
      for (Enumeration e = root.children(); e.hasMoreElements(); ) {
        Splitter split = (Splitter) e.nextElement();
        for (int i=0; i<split.getNumOfBranches(); i++)
            numSoFar += numOfPredictionNodes(split.getChildForBranch(i));
      }
    }
    return numSoFar;
  }

  /**
   * Returns the number of leaf nodes in a tree - prediction nodes without
   * children.
   *
   * @param root the root of the tree being measured
   * @return tree leaf size in number of prediction nodes
   */       
  protected int numOfPredictionLeafNodes(PredictionNode root) {
    
    int numSoFar = 0;
    if (root.getChildren().size() > 0) {
      for (Enumeration e = root.children(); e.hasMoreElements(); ) {
        Splitter split = (Splitter) e.nextElement();
        for (int i=0; i<split.getNumOfBranches(); i++)
            numSoFar += numOfPredictionLeafNodes(split.getChildForBranch(i));
      }
    } else numSoFar = 1;
    return numSoFar;
  }

  /**
   * Gets the next random value.
   *
   * @param max the maximum value (+1) to be returned
   * @return the next random value (between 0 and max-1)
   */
  protected int getRandom(int max) {
    
    return m_random.nextInt(max);
  }

  /**
   * Returns the next number in the order that splitter nodes have been added to
   * the tree, and records that a new splitter has been added.
   *
   * @return the next number in the order
   */
  public int nextSplitAddedOrder() {

    return ++m_lastAddedSplitNum;
  }

  /**
   * Returns default capabilities of the classifier.
   *
   * @return      the capabilities of this classifier
   */
  public Capabilities getCapabilities() {
    Capabilities result = super.getCapabilities();
    result.disableAll();

    // attributes
    result.enable(Capability.NOMINAL_ATTRIBUTES);
    result.enable(Capability.NUMERIC_ATTRIBUTES);
    result.enable(Capability.DATE_ATTRIBUTES);
    result.enable(Capability.MISSING_VALUES);

    // class
    result.enable(Capability.BINARY_CLASS);
    result.enable(Capability.MISSING_CLASS_VALUES);
    
    return result;
  }

  /**
   * Builds a classifier for a set of instances.
   *
   * @param instances the instances to train the classifier with
   * @exception Exception if something goes wrong
   */
  public void buildClassifier(Instances instances) throws Exception {

    // can classifier handle the data?
    getCapabilities().testWithFail(instances);

    // remove instances with missing class
    instances = new Instances(instances);
    instances.deleteWithMissingClass();

    // set up the tree
    initClassifier(instances);

    // build the tree
    for (int T = 0; T < m_boostingIterations; T++) boost();

    // clean up if desired
    if (!m_saveInstanceData) done();
  }

  /**
   * Frees memory that is no longer needed for a final model - will no longer be able
   * to increment the classifier after calling this.
   *
   */
  public void done() {

    m_trainInstances = new Instances(m_trainInstances, 0);
    m_random = null; 
    m_numericAttIndices = null;
    m_nominalAttIndices = null;
    m_posTrainInstances = null;
    m_negTrainInstances = null;
  }

  /**
   * Creates a clone that is identical to the current tree, but is independent.
   * Deep copies the essential elements such as the tree nodes, and the instances
   * (because the weights change.) Reference copies several elements such as the
   * potential splitter sets, assuming that such elements should never differ between
   * clones.
   *
   * @return the clone
   */
  public Object clone() {
    
    ADTree clone = new ADTree();

    if (m_root != null) { // check for initialization first
      clone.m_root = (PredictionNode) m_root.clone(); // deep copy the tree

      clone.m_trainInstances = new Instances(m_trainInstances); // copy training instances
      
      // deep copy the random object
      if (m_random != null) { 
        SerializedObject randomSerial = null;
        try {
          randomSerial = new SerializedObject(m_random);
        } catch (Exception ignored) {} // we know that Random is serializable
        clone.m_random = (Random) randomSerial.getObject();
      }

      clone.m_lastAddedSplitNum = m_lastAddedSplitNum;
      clone.m_numericAttIndices = m_numericAttIndices;
      clone.m_nominalAttIndices = m_nominalAttIndices;
      clone.m_trainTotalWeight = m_trainTotalWeight;

      // reconstruct pos/negTrainInstances references
      if (m_posTrainInstances != null) { 
        clone.m_posTrainInstances =
          new ReferenceInstances(m_trainInstances, m_posTrainInstances.numInstances());
        clone.m_negTrainInstances =
          new ReferenceInstances(m_trainInstances, m_negTrainInstances.numInstances());
        for (Enumeration e = clone.m_trainInstances.enumerateInstances();
             e.hasMoreElements(); ) {
          Instance inst = (Instance) e.nextElement();
          try { // ignore classValue() exception
            if ((int) inst.classValue() == 0)
              clone.m_negTrainInstances.addReference(inst); // belongs in negative class
            else
              clone.m_posTrainInstances.addReference(inst); // belongs in positive class
          } catch (Exception ignored) {} 
        }
      }
    }
    clone.m_nodesExpanded = m_nodesExpanded;
    clone.m_examplesCounted = m_examplesCounted;
    clone.m_boostingIterations = m_boostingIterations;
    clone.m_searchPath = m_searchPath;
    clone.m_randomSeed = m_randomSeed;

    return clone;
  }

  /**
   * Merges two trees together. Modifies the tree being acted on, leaving tree passed
   * as a parameter untouched (cloned). Does not check to see whether training instances
   * are compatible - strange things could occur if they are not.
   *
   * @param mergeWith the tree to merge with
   * @exception Exception if merge could not be performed
   */
  public void merge(ADTree mergeWith) throws Exception {
    
    if (m_root == null || mergeWith.m_root == null)
      throw new Exception("Trying to merge an uninitialized tree");
    m_root.merge(mergeWith.m_root, this);
  }
  
  /**
   * Returns the revision string.
   * 
   * @return            the revision
   */
  public String getRevision() {
    return RevisionUtils.extract("$Revision: 5928 $");
  }

  /**
   * Main method for testing this class.
   *
   * @param argv the options
   */
  public static void main(String [] argv) {
    runClassifier(new ADTree(), argv);
  }
}