source: src/main/java/weka/classifiers/bayes/BayesNet.java @ 18

/*
 * 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.
 */

/*
 * BayesNet.java
 * Copyright (C) 2001 University of Waikato, Hamilton, New Zealand
 * 
 */
package weka.classifiers.bayes;

import weka.classifiers.Classifier;
import weka.classifiers.AbstractClassifier;
import weka.classifiers.bayes.net.ADNode;
import weka.classifiers.bayes.net.BIFReader;
import weka.classifiers.bayes.net.ParentSet;
import weka.classifiers.bayes.net.estimate.BayesNetEstimator;
import weka.classifiers.bayes.net.estimate.DiscreteEstimatorBayes;
import weka.classifiers.bayes.net.estimate.SimpleEstimator;
import weka.classifiers.bayes.net.search.SearchAlgorithm;
import weka.classifiers.bayes.net.search.local.K2;
import weka.classifiers.bayes.net.search.local.LocalScoreSearchAlgorithm;
import weka.classifiers.bayes.net.search.local.Scoreable;
import weka.core.AdditionalMeasureProducer;
import weka.core.Attribute;
import weka.core.Capabilities;
import weka.core.Drawable;
import weka.core.Instance;
import weka.core.Instances;
import weka.core.Option;
import weka.core.OptionHandler;
import weka.core.RevisionUtils;
import weka.core.Utils;
import weka.core.WeightedInstancesHandler;
import weka.core.Capabilities.Capability;
import weka.estimators.Estimator;
import weka.filters.Filter;
import weka.filters.supervised.attribute.Discretize;
import weka.filters.unsupervised.attribute.ReplaceMissingValues;

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

/**
 <!-- globalinfo-start -->
 * Bayes Network learning using various search algorithms and quality measures.<br/>
 * Base class for a Bayes Network classifier. Provides datastructures (network structure, conditional probability distributions, etc.) and facilities common to Bayes Network learning algorithms like K2 and B.<br/>
 * <br/>
 * For more information see:<br/>
 * <br/>
 * http://sourceforge.net/projects/weka/files/documentation/WekaManual-3-7-0.pdf/download
 * <p/>
 <!-- globalinfo-end -->
 * 
 <!-- options-start -->
 * Valid options are: <p/>
 * 
 * <pre> -D
 *  Do not use ADTree data structure
 * </pre>
 * 
 * <pre> -B &lt;BIF file&gt;
 *  BIF file to compare with
 * </pre>
 * 
 * <pre> -Q weka.classifiers.bayes.net.search.SearchAlgorithm
 *  Search algorithm
 * </pre>
 * 
 * <pre> -E weka.classifiers.bayes.net.estimate.SimpleEstimator
 *  Estimator algorithm
 * </pre>
 * 
 <!-- options-end -->
 *
 * @author Remco Bouckaert (rrb@xm.co.nz)
 * @version $Revision: 5928 $
 */
public class BayesNet
  extends AbstractClassifier
  implements OptionHandler, WeightedInstancesHandler, Drawable, 
             AdditionalMeasureProducer {

  /** for serialization */
  static final long serialVersionUID = 746037443258775954L;


  /**
   * The parent sets.
   */
  protected ParentSet[] m_ParentSets;

  /**
   * The attribute estimators containing CPTs.
   */
  public Estimator[][] m_Distributions;


  /** filter used to quantize continuous variables, if any **/
  protected Discretize m_DiscretizeFilter = null;

  /** attribute index of a non-nominal attribute */
  int m_nNonDiscreteAttribute = -1;

  /** filter used to fill in missing values, if any **/
  protected ReplaceMissingValues m_MissingValuesFilter = null;  

  /**
   * The number of classes
   */
  protected int m_NumClasses;

  /**
   * The dataset header for the purposes of printing out a semi-intelligible
   * model
   */
  public Instances m_Instances;

  /**
   * Datastructure containing ADTree representation of the database.
   * This may result in more efficient access to the data.
   */
  ADNode m_ADTree;

  /**
   * Bayes network to compare the structure with.
   */
  protected BIFReader m_otherBayesNet = null;

  /**
   * Use the experimental ADTree datastructure for calculating contingency tables
   */
  boolean m_bUseADTree = false;

  /**
   * Search algorithm used for learning the structure of a network.
   */
  SearchAlgorithm m_SearchAlgorithm = new K2();

  /**
   * Search algorithm used for learning the structure of a network.
   */
  BayesNetEstimator m_BayesNetEstimator = new SimpleEstimator();

  /**
   * 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.MISSING_VALUES);

    // class
    result.enable(Capability.NOMINAL_CLASS);
    result.enable(Capability.MISSING_CLASS_VALUES);

    // instances
    result.setMinimumNumberInstances(0);

    return result;
  }

  /**
   * Generates the classifier.
   * 
   * @param instances set of instances serving as training data
   * @throws Exception if the classifier has not been generated
   * successfully
   */
  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();

    // ensure we have a data set with discrete variables only and with no missing values
    instances = normalizeDataSet(instances);

    // Copy the instances
    m_Instances = new Instances(instances);

    // sanity check: need more than 1 variable in datat set
    m_NumClasses = instances.numClasses();

    // initialize ADTree
    if (m_bUseADTree) {
      m_ADTree = ADNode.makeADTree(instances);
      //      System.out.println("Oef, done!");
    }

    // build the network structure
    initStructure();

    // build the network structure
    buildStructure();

    // build the set of CPTs
    estimateCPTs();

    // Save space
    // m_Instances = new Instances(m_Instances, 0);
    m_ADTree = null;
  } // buildClassifier

  /** ensure that all variables are nominal and that there are no missing values
   * @param instances data set to check and quantize and/or fill in missing values
   * @return filtered instances
   * @throws Exception if a filter (Discretize, ReplaceMissingValues) fails
   */
  protected Instances normalizeDataSet(Instances instances) throws Exception {
    m_DiscretizeFilter = null;
    m_MissingValuesFilter = null;

    boolean bHasNonNominal = false;
    boolean bHasMissingValues = false;

    Enumeration enu = instances.enumerateAttributes();          
    while (enu.hasMoreElements()) {
      Attribute attribute = (Attribute) enu.nextElement();
      if (attribute.type() != Attribute.NOMINAL) {
        m_nNonDiscreteAttribute = attribute.index();
        bHasNonNominal = true;
        //throw new UnsupportedAttributeTypeException("BayesNet handles nominal variables only. Non-nominal variable in dataset detected.");
      }
      Enumeration enum2 = instances.enumerateInstances();
      while (enum2.hasMoreElements()) {
        if (((Instance) enum2.nextElement()).isMissing(attribute)) {
          bHasMissingValues = true;
          // throw new NoSupportForMissingValuesException("BayesNet: no missing values, please.");
        }
      }
    }

    if (bHasNonNominal) {
      System.err.println("Warning: discretizing data set");
      m_DiscretizeFilter = new Discretize();
      m_DiscretizeFilter.setInputFormat(instances);
      instances = Filter.useFilter(instances, m_DiscretizeFilter);
    }

    if (bHasMissingValues) {
      System.err.println("Warning: filling in missing values in data set");
      m_MissingValuesFilter = new ReplaceMissingValues();
      m_MissingValuesFilter.setInputFormat(instances);
      instances = Filter.useFilter(instances, m_MissingValuesFilter);
    }
    return instances;
  } // normalizeDataSet

  /** ensure that all variables are nominal and that there are no missing values
   * @param instance instance to check and quantize and/or fill in missing values
   * @return filtered instance
   * @throws Exception if a filter (Discretize, ReplaceMissingValues) fails
   */
  protected Instance normalizeInstance(Instance instance) throws Exception {
    if ((m_DiscretizeFilter != null) &&
        (instance.attribute(m_nNonDiscreteAttribute).type() != Attribute.NOMINAL)) {
      m_DiscretizeFilter.input(instance);
      instance = m_DiscretizeFilter.output();
    }
    if (m_MissingValuesFilter != null) {
      m_MissingValuesFilter.input(instance);
      instance = m_MissingValuesFilter.output();
    } else {
      // is there a missing value in this instance?
      // this can happen when there is no missing value in the training set
      for (int iAttribute = 0; iAttribute < m_Instances.numAttributes(); iAttribute++) {
        if (iAttribute != instance.classIndex() && instance.isMissing(iAttribute)) {
          System.err.println("Warning: Found missing value in test set, filling in values.");
          m_MissingValuesFilter = new ReplaceMissingValues();
          m_MissingValuesFilter.setInputFormat(m_Instances);
          Filter.useFilter(m_Instances, m_MissingValuesFilter);
          m_MissingValuesFilter.input(instance);
          instance = m_MissingValuesFilter.output();
          iAttribute = m_Instances.numAttributes();
        }
      }
    }
    return instance;
  } // normalizeInstance

  /**
   * Init structure initializes the structure to an empty graph or a Naive Bayes
   * graph (depending on the -N flag).
   * 
   * @throws Exception in case of an error
   */
  public void initStructure() throws Exception {

    // initialize topological ordering
    //    m_nOrder = new int[m_Instances.numAttributes()];
    //    m_nOrder[0] = m_Instances.classIndex();

    int nAttribute = 0;

    for (int iOrder = 1; iOrder < m_Instances.numAttributes(); iOrder++) {
      if (nAttribute == m_Instances.classIndex()) {
        nAttribute++;
      }

      //      m_nOrder[iOrder] = nAttribute++;
    }

    // reserve memory
    m_ParentSets = new ParentSet[m_Instances.numAttributes()];

    for (int iAttribute = 0; iAttribute < m_Instances.numAttributes(); iAttribute++) {
      m_ParentSets[iAttribute] = new ParentSet(m_Instances.numAttributes());
    }
  } // initStructure

  /**
   * buildStructure determines the network structure/graph of the network.
   * The default behavior is creating a network where all nodes have the first
   * node as its parent (i.e., a BayesNet that behaves like a naive Bayes classifier).
   * This method can be overridden by derived classes to restrict the class
   * of network structures that are acceptable.
   * 
   * @throws Exception in case of an error
   */
  public void buildStructure() throws Exception {
    m_SearchAlgorithm.buildStructure(this, m_Instances);
  } // buildStructure

  /**
   * estimateCPTs estimates the conditional probability tables for the Bayes
   * Net using the network structure.
   * 
   * @throws Exception in case of an error
   */
  public void estimateCPTs() throws Exception {
    m_BayesNetEstimator.estimateCPTs(this);
  } // estimateCPTs

  /**
   * initializes the conditional probabilities
   * 
   * @throws Exception in case of an error
   */
  public void initCPTs() throws Exception {
    m_BayesNetEstimator.initCPTs(this);
  } // estimateCPTs

  /**
   * Updates the classifier with the given instance.
   * 
   * @param instance the new training instance to include in the model
   * @throws Exception if the instance could not be incorporated in
   * the model.
   */
  public void updateClassifier(Instance instance) throws Exception {
    instance = normalizeInstance(instance);
    m_BayesNetEstimator.updateClassifier(this, instance);
  } // updateClassifier

  /**
   * Calculates the class membership probabilities for the given test
   * instance.
   * 
   * @param instance the instance to be classified
   * @return predicted class probability distribution
   * @throws Exception if there is a problem generating the prediction
   */
  public double[] distributionForInstance(Instance instance) throws Exception {
    instance = normalizeInstance(instance);
    return m_BayesNetEstimator.distributionForInstance(this, instance);
  } // distributionForInstance

  /**
   * Calculates the counts for Dirichlet distribution for the 
   * class membership probabilities for the given test instance.
   * 
   * @param instance the instance to be classified
   * @return counts for Dirichlet distribution for class probability 
   * @throws Exception if there is a problem generating the prediction
   */
  public double[] countsForInstance(Instance instance) throws Exception {
    double[] fCounts = new double[m_NumClasses];

    for (int iClass = 0; iClass < m_NumClasses; iClass++) {
      fCounts[iClass] = 0.0;
    }

    for (int iClass = 0; iClass < m_NumClasses; iClass++) {
      double fCount = 0;

      for (int iAttribute = 0; iAttribute < m_Instances.numAttributes(); iAttribute++) {
        double iCPT = 0;

        for (int iParent = 0; iParent < m_ParentSets[iAttribute].getNrOfParents(); iParent++) {
          int nParent = m_ParentSets[iAttribute].getParent(iParent);

          if (nParent == m_Instances.classIndex()) {
            iCPT = iCPT * m_NumClasses + iClass;
          } else {
            iCPT = iCPT * m_Instances.attribute(nParent).numValues() + instance.value(nParent);
          }
        }

        if (iAttribute == m_Instances.classIndex()) {
          fCount += ((DiscreteEstimatorBayes) m_Distributions[iAttribute][(int) iCPT]).getCount(iClass);
        } else {
          fCount
          += ((DiscreteEstimatorBayes) m_Distributions[iAttribute][(int) iCPT]).getCount(
              instance.value(iAttribute));
        }
      }

      fCounts[iClass] += fCount;
    }
    return fCounts;
  } // countsForInstance

  /**
   * Returns an enumeration describing the available options
   * 
   * @return an enumeration of all the available options
   */
  public Enumeration listOptions() {
    Vector newVector = new Vector(4);

    newVector.addElement(new Option("\tDo not use ADTree data structure\n", "D", 0, "-D"));
    newVector.addElement(new Option("\tBIF file to compare with\n", "B", 1, "-B <BIF file>"));
    newVector.addElement(new Option("\tSearch algorithm\n", "Q", 1, "-Q weka.classifiers.bayes.net.search.SearchAlgorithm"));
    newVector.addElement(new Option("\tEstimator algorithm\n", "E", 1, "-E weka.classifiers.bayes.net.estimate.SimpleEstimator"));

    return newVector.elements();
  } // listOptions

  /**
   * Parses a given list of options. <p>
   * 
     <!-- options-start -->
   * Valid options are: <p/>
   * 
   * <pre> -D
   *  Do not use ADTree data structure
   * </pre>
   * 
   * <pre> -B &lt;BIF file&gt;
   *  BIF file to compare with
   * </pre>
   * 
   * <pre> -Q weka.classifiers.bayes.net.search.SearchAlgorithm
   *  Search algorithm
   * </pre>
   * 
   * <pre> -E weka.classifiers.bayes.net.estimate.SimpleEstimator
   *  Estimator algorithm
   * </pre>
   * 
     <!-- options-end -->
   *
   * @param options the list of options as an array of strings
   * @throws Exception if an option is not supported
   */
  public void setOptions(String[] options) throws Exception {
    m_bUseADTree = !(Utils.getFlag('D', options));

    String sBIFFile = Utils.getOption('B', options);
    if (sBIFFile != null && !sBIFFile.equals("")) {
      setBIFFile(sBIFFile);
    }

    String searchAlgorithmName = Utils.getOption('Q', options);
    if (searchAlgorithmName.length() != 0) {
      setSearchAlgorithm(
          (SearchAlgorithm) Utils.forName(
              SearchAlgorithm.class,
              searchAlgorithmName,
              partitionOptions(options)));
    }
    else {
      setSearchAlgorithm(new K2());
    }


    String estimatorName = Utils.getOption('E', options);
    if (estimatorName.length() != 0) {
      setEstimator(
          (BayesNetEstimator) Utils.forName(
              BayesNetEstimator.class,
              estimatorName,
              Utils.partitionOptions(options)));
    }
    else {
      setEstimator(new SimpleEstimator());
    }

    Utils.checkForRemainingOptions(options);
  } // setOptions

  /**
   * Returns the secondary set of options (if any) contained in
   * the supplied options array. The secondary set is defined to
   * be any options after the first "--" but before the "-E". These 
   * options are removed from the original options array.
   *
   * @param options the input array of options
   * @return the array of secondary options
   */
  public static String [] partitionOptions(String [] options) {

    for (int i = 0; i < options.length; i++) {
      if (options[i].equals("--")) {
        // ensure it follows by a -E option
        int j = i;
        while ((j < options.length) && !(options[j].equals("-E"))) {
          j++;
        }
        /*      if (j >= options.length) {
          return new String[0];
          } */
        options[i++] = "";
        String [] result = new String [options.length - i];
        j = i;
        while ((j < options.length) && !(options[j].equals("-E"))) {
          result[j - i] = options[j];
          options[j] = "";
          j++;
        }
        while(j < options.length) {
          result[j - i] = "";
          j++;
        }                
        return result;
      }
    }
    return new String [0];
  }


  /**
   * Gets the current settings of the classifier.
   * 
   * @return an array of strings suitable for passing to setOptions
   */
  public String[] getOptions() {
    String[] searchOptions = m_SearchAlgorithm.getOptions();
    String[] estimatorOptions = m_BayesNetEstimator.getOptions();
    String[] options = new String[11 + searchOptions.length + estimatorOptions.length];
    int current = 0;

    if (!m_bUseADTree) {
      options[current++] = "-D";
    }

    if (m_otherBayesNet != null) {
      options[current++] = "-B";
      options[current++] = ((BIFReader) m_otherBayesNet).getFileName();
    }

    options[current++] = "-Q";
    options[current++] = "" + getSearchAlgorithm().getClass().getName();
    options[current++] = "--";
    for (int iOption = 0; iOption < searchOptions.length; iOption++) {
      options[current++] = searchOptions[iOption];
    }

    options[current++] = "-E";
    options[current++] = "" + getEstimator().getClass().getName();
    options[current++] = "--";
    for (int iOption = 0; iOption < estimatorOptions.length; iOption++) {
      options[current++] = estimatorOptions[iOption];
    }

    // Fill up rest with empty strings, not nulls!
    while (current < options.length) {
      options[current++] = "";
    }

    return options;
  } // getOptions

  /**
   * Set the SearchAlgorithm used in searching for network structures. 
   * @param newSearchAlgorithm the SearchAlgorithm to use.
   */
  public void setSearchAlgorithm(SearchAlgorithm newSearchAlgorithm) {
    m_SearchAlgorithm = newSearchAlgorithm;
  }

  /**
   * Get the SearchAlgorithm used as the search algorithm
   * @return the SearchAlgorithm used as the search algorithm
   */
  public SearchAlgorithm getSearchAlgorithm() {
    return m_SearchAlgorithm;
  }

  /**
   * Set the Estimator Algorithm used in calculating the CPTs 
   * @param newBayesNetEstimator the Estimator to use.
   */
  public void setEstimator(BayesNetEstimator newBayesNetEstimator) {
    m_BayesNetEstimator = newBayesNetEstimator;
  }

  /**
   * Get the BayesNetEstimator used for calculating the CPTs
   * @return the BayesNetEstimator used.
   */
  public BayesNetEstimator getEstimator() {
    return m_BayesNetEstimator;
  }

  /**
   * Set whether ADTree structure is used or not
   * @param bUseADTree true if an ADTree structure is used
   */
  public void setUseADTree(boolean bUseADTree) {
    m_bUseADTree = bUseADTree;
  }

  /**
   * Method declaration
   * @return whether ADTree structure is used or not
   */
  public boolean getUseADTree() {
    return m_bUseADTree;
  }

  /**
   * Set name of network in BIF file to compare with
   * @param sBIFFile the name of the BIF file
   */
  public void setBIFFile(String sBIFFile) {
    try {
      m_otherBayesNet = new BIFReader().processFile(sBIFFile);
    } catch (Throwable t) {
      m_otherBayesNet = null;
    }
  }

  /**
   * Get name of network in BIF file to compare with
   * @return BIF file name
   */
  public String getBIFFile() {
    if (m_otherBayesNet != null) {
      return m_otherBayesNet.getFileName();
    }
    return "";
  }


  /**
   * Returns a description of the classifier.
   * 
   * @return a description of the classifier as a string.
   */
  public String toString() {
    StringBuffer text = new StringBuffer();

    text.append("Bayes Network Classifier");
    text.append("\n" + (m_bUseADTree ? "Using " : "not using ") + "ADTree");

    if (m_Instances == null) {
      text.append(": No model built yet.");
    } else {

      // flatten BayesNet down to text
      text.append("\n#attributes=");
      text.append(m_Instances.numAttributes());
      text.append(" #classindex=");
      text.append(m_Instances.classIndex());
      text.append("\nNetwork structure (nodes followed by parents)\n");

      for (int iAttribute = 0; iAttribute < m_Instances.numAttributes(); iAttribute++) {
        text.append(
            m_Instances.attribute(iAttribute).name()
            + "("
                + m_Instances.attribute(iAttribute).numValues()
                + "): ");

        for (int iParent = 0; iParent < m_ParentSets[iAttribute].getNrOfParents(); iParent++) {
          text.append(m_Instances.attribute(m_ParentSets[iAttribute].getParent(iParent)).name() + " ");
        }

        text.append("\n");

        // Description of distributions tends to be too much detail, so it is commented out here
        // for (int iParent = 0; iParent < m_ParentSets[iAttribute].GetCardinalityOfParents(); iParent++) {
        // text.append('(' + m_Distributions[iAttribute][iParent].toString() + ')');
        // }
        // text.append("\n");
      }

      text.append("LogScore Bayes: " + measureBayesScore() + "\n");
      text.append("LogScore BDeu: " + measureBDeuScore() + "\n");
      text.append("LogScore MDL: " + measureMDLScore() + "\n");
      text.append("LogScore ENTROPY: " + measureEntropyScore() + "\n");
      text.append("LogScore AIC: " + measureAICScore() + "\n");

      if (m_otherBayesNet != null) {
        text.append(
            "Missing: "
            + m_otherBayesNet.missingArcs(this)
            + " Extra: "
            + m_otherBayesNet.extraArcs(this)
            + " Reversed: "
            + m_otherBayesNet.reversedArcs(this)
            + "\n");
        text.append("Divergence: " + m_otherBayesNet.divergence(this) + "\n");
      }
    }

    return text.toString();
  } // toString


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

  /**
   * Returns a BayesNet graph in XMLBIF ver 0.3 format.
   * @return String representing this BayesNet in XMLBIF ver  0.3
   * @throws Exception in case BIF generation fails
   */
  public String graph() throws Exception {
    return toXMLBIF03();
  }

  public String getBIFHeader() {
    StringBuffer text = new StringBuffer();
    text.append("<?xml version=\"1.0\"?>\n");
    text.append("<!-- DTD for the XMLBIF 0.3 format -->\n");
    text.append("<!DOCTYPE BIF [\n");
    text.append("       <!ELEMENT BIF ( NETWORK )*>\n");
    text.append("             <!ATTLIST BIF VERSION CDATA #REQUIRED>\n");
    text.append("       <!ELEMENT NETWORK ( NAME, ( PROPERTY | VARIABLE | DEFINITION )* )>\n");
    text.append("       <!ELEMENT NAME (#PCDATA)>\n");
    text.append("       <!ELEMENT VARIABLE ( NAME, ( OUTCOME |  PROPERTY )* ) >\n");
    text.append("             <!ATTLIST VARIABLE TYPE (nature|decision|utility) \"nature\">\n");
    text.append("       <!ELEMENT OUTCOME (#PCDATA)>\n");
    text.append("       <!ELEMENT DEFINITION ( FOR | GIVEN | TABLE | PROPERTY )* >\n");
    text.append("       <!ELEMENT FOR (#PCDATA)>\n");
    text.append("       <!ELEMENT GIVEN (#PCDATA)>\n");
    text.append("       <!ELEMENT TABLE (#PCDATA)>\n");
    text.append("       <!ELEMENT PROPERTY (#PCDATA)>\n");
    text.append("]>\n");
    return text.toString();
  } // getBIFHeader

  /**
   * Returns a description of the classifier in XML BIF 0.3 format.
   * See http://www-2.cs.cmu.edu/~fgcozman/Research/InterchangeFormat/
   * for details on XML BIF.
   * @return an XML BIF 0.3 description of the classifier as a string.
   */
  public String toXMLBIF03() {
    if (m_Instances == null) {
      return("<!--No model built yet-->");
    }

    StringBuffer text = new StringBuffer();
    text.append(getBIFHeader());
    text.append("\n");
    text.append("\n");
    text.append("<BIF VERSION=\"0.3\">\n");
    text.append("<NETWORK>\n");
    text.append("<NAME>" + XMLNormalize(m_Instances.relationName()) + "</NAME>\n");
    for (int iAttribute = 0; iAttribute < m_Instances.numAttributes(); iAttribute++) {
      text.append("<VARIABLE TYPE=\"nature\">\n");
      text.append("<NAME>" + XMLNormalize(m_Instances.attribute(iAttribute).name()) + "</NAME>\n");
      for (int iValue = 0; iValue < m_Instances.attribute(iAttribute).numValues(); iValue++) {
        text.append("<OUTCOME>" + XMLNormalize(m_Instances.attribute(iAttribute).value(iValue)) + "</OUTCOME>\n");
      }
      text.append("</VARIABLE>\n");
    }

    for (int iAttribute = 0; iAttribute < m_Instances.numAttributes(); iAttribute++) {
      text.append("<DEFINITION>\n");
      text.append("<FOR>" + XMLNormalize(m_Instances.attribute(iAttribute).name()) + "</FOR>\n");
      for (int iParent = 0; iParent < m_ParentSets[iAttribute].getNrOfParents(); iParent++) {
        text.append("<GIVEN>"
            + XMLNormalize(m_Instances.attribute(m_ParentSets[iAttribute].getParent(iParent)).name()) +
        "</GIVEN>\n");
      }
      text.append("<TABLE>\n");
      for (int iParent = 0; iParent < m_ParentSets[iAttribute].getCardinalityOfParents(); iParent++) {
        for (int iValue = 0; iValue < m_Instances.attribute(iAttribute).numValues(); iValue++) {
          text.append(m_Distributions[iAttribute][iParent].getProbability(iValue));
          text.append(' ');
        }
        text.append('\n');
      }
      text.append("</TABLE>\n");
      text.append("</DEFINITION>\n");
    }
    text.append("</NETWORK>\n");
    text.append("</BIF>\n");
    return text.toString();
  } // toXMLBIF03


  /** XMLNormalize converts the five standard XML entities in a string
   * g.e. the string V&D's is returned as V&amp;D&apos;s
   * @param sStr string to normalize
   * @return normalized string
   */
  protected String XMLNormalize(String sStr) {
    StringBuffer sStr2 = new StringBuffer();
    for (int iStr = 0; iStr < sStr.length(); iStr++) {
      char c = sStr.charAt(iStr);
      switch (c) {
        case '&': sStr2.append("&amp;"); break;
        case '\'': sStr2.append("&apos;"); break;
        case '\"': sStr2.append("&quot;"); break;
        case '<': sStr2.append("&lt;"); break;
        case '>': sStr2.append("&gt;"); break;
        default:
          sStr2.append(c);
      }
    }
    return sStr2.toString();
  } // XMLNormalize


  /**
   * @return a string to describe the UseADTreeoption.
   */
  public String useADTreeTipText() {
    return "When ADTree (the data structure for increasing speed on counts,"
    + " not to be confused with the classifier under the same name) is used"
    + " learning time goes down typically. However, because ADTrees are memory"
    + " intensive, memory problems may occur. Switching this option off makes"
    + " the structure learning algorithms slower, and run with less memory."
    + " By default, ADTrees are used.";
  }

  /**
   * @return a string to describe the SearchAlgorithm.
   */
  public String searchAlgorithmTipText() {
    return "Select method used for searching network structures.";
  }

  /**
   * This will return a string describing the BayesNetEstimator.
   * @return The string.
   */
  public String estimatorTipText() {
    return "Select Estimator algorithm for finding the conditional probability tables"
    + " of the Bayes Network.";
  }

  /**
   * @return a string to describe the BIFFile.
   */
  public String BIFFileTipText() {
    return "Set the name of a file in BIF XML format. A Bayes network learned"
    + " from data can be compared with the Bayes network represented by the BIF file."
    + " Statistics calculated are o.a. the number of missing and extra arcs.";
  }

  /**
   * This will return a string describing the classifier.
   * @return The string.
   */
  public String globalInfo() {
    return 
    "Bayes Network learning using various search algorithms and "
    + "quality measures.\n"
    + "Base class for a Bayes Network classifier. Provides "
    + "datastructures (network structure, conditional probability "
    + "distributions, etc.) and facilities common to Bayes Network "
    + "learning algorithms like K2 and B.\n\n"
    + "For more information see:\n\n"
    + "http://www.cs.waikato.ac.nz/~remco/weka.pdf";
  }

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

  /** get name of the Bayes network
   * @return name of the Bayes net
   */
  public String getName() {
    return m_Instances.relationName();
  }

  /** get number of nodes in the Bayes network
   * @return number of nodes
   */
  public int getNrOfNodes() {
    return m_Instances.numAttributes();
  }

  /** get name of a node in the Bayes network
   * @param iNode index of the node
   * @return name of the specified node
   */
  public String getNodeName(int iNode) {
    return m_Instances.attribute(iNode).name();
  }

  /** get number of values a node can take
   * @param iNode index of the node
   * @return cardinality of the specified node
   */
  public int getCardinality(int iNode) {
    return m_Instances.attribute(iNode).numValues();
  }

  /** get name of a particular value of a node
   * @param iNode index of the node
   * @param iValue index of the value
   * @return cardinality of the specified node
   */
  public String getNodeValue(int iNode, int iValue) {
    return m_Instances.attribute(iNode).value(iValue);
  }

  /** get number of parents of a node in the network structure
   * @param iNode index of the node
   * @return number of parents of the specified node
   */
  public int getNrOfParents(int iNode) {
    return m_ParentSets[iNode].getNrOfParents();
  }

  /** get node index of a parent of a node in the network structure
   * @param iNode index of the node
   * @param iParent index of the parents, e.g., 0 is the first parent, 1 the second parent, etc.
   * @return node index of the iParent's parent of the specified node
   */
  public int getParent(int iNode, int iParent) {
    return m_ParentSets[iNode].getParent(iParent);
  }

  /** Get full set of parent sets.
   * @return parent sets;
   */
  public ParentSet[] getParentSets() { 
    return m_ParentSets;
  }

  /** Get full set of estimators.
   * @return estimators;
   */
  public Estimator[][] getDistributions() {
    return m_Distributions;
  }

  /** get number of values the collection of parents of a node can take
   * @param iNode index of the node
   * @return cardinality of the parent set of the specified node
   */
  public int getParentCardinality(int iNode) {
    return m_ParentSets[iNode].getCardinalityOfParents();
  }

  /** get particular probability of the conditional probability distribtion
   * of a node given its parents.
   * @param iNode index of the node
   * @param iParent index of the parent set, 0 <= iParent <= getParentCardinality(iNode)
   * @param iValue index of the value, 0 <= iValue <= getCardinality(iNode)
   * @return probability
   */
  public double getProbability(int iNode, int iParent, int iValue) {
    return m_Distributions[iNode][iParent].getProbability(iValue);
  }

  /** get the parent set of a node 
   * @param iNode index of the node
   * @return Parent set of the specified node.
   */
  public ParentSet getParentSet(int iNode) {
    return m_ParentSets[iNode];
  }

  /** get ADTree strucrture containing efficient representation of counts.
   * @return ADTree strucrture
   */
  public ADNode getADTree() { return m_ADTree;}

  // implementation of AdditionalMeasureProducer interface
  /**
   * Returns an enumeration of the measure names. Additional measures
   * must follow the naming convention of starting with "measure", eg.
   * double measureBlah()
   * @return an enumeration of the measure names
   */
  public Enumeration enumerateMeasures() {
    Vector newVector = new Vector(4);
    newVector.addElement("measureExtraArcs");
    newVector.addElement("measureMissingArcs");
    newVector.addElement("measureReversedArcs");
    newVector.addElement("measureDivergence");
    newVector.addElement("measureBayesScore");
    newVector.addElement("measureBDeuScore");
    newVector.addElement("measureMDLScore");
    newVector.addElement("measureAICScore");
    newVector.addElement("measureEntropyScore");
    return newVector.elements();
  } // enumerateMeasures

  public double measureExtraArcs() {
    if (m_otherBayesNet != null) {
      return m_otherBayesNet.extraArcs(this); 
    }
    return 0;
  } // measureExtraArcs

  public double measureMissingArcs() {
    if (m_otherBayesNet != null) {
      return m_otherBayesNet.missingArcs(this); 
    }
    return 0;
  } // measureMissingArcs

  public double measureReversedArcs() {
    if (m_otherBayesNet != null) {
      return m_otherBayesNet.reversedArcs(this); 
    }
    return 0;
  } // measureReversedArcs

  public double measureDivergence() {
    if (m_otherBayesNet != null) {
      return m_otherBayesNet.divergence(this); 
    }
    return 0;
  } // measureDivergence

  public double measureBayesScore() {
    LocalScoreSearchAlgorithm s = new LocalScoreSearchAlgorithm(this, m_Instances);
    return s.logScore(Scoreable.BAYES);
  } // measureBayesScore

  public double measureBDeuScore() {
    LocalScoreSearchAlgorithm s = new LocalScoreSearchAlgorithm(this, m_Instances);
    return s.logScore(Scoreable.BDeu);
  } // measureBDeuScore

  public double measureMDLScore() {
    LocalScoreSearchAlgorithm s = new LocalScoreSearchAlgorithm(this, m_Instances);
    return s.logScore(Scoreable.MDL);
  } // measureMDLScore

  public double measureAICScore() {
    LocalScoreSearchAlgorithm s = new LocalScoreSearchAlgorithm(this, m_Instances);
    return s.logScore(Scoreable.AIC);
  } // measureAICScore

  public double measureEntropyScore() {
    LocalScoreSearchAlgorithm s = new LocalScoreSearchAlgorithm(this, m_Instances);
    return s.logScore(Scoreable.ENTROPY);
  } // measureEntropyScore

  /**
   * Returns the value of the named measure
   * @param measureName the name of the measure to query for its value
   * @return the value of the named measure
   * @throws IllegalArgumentException if the named measure is not supported
   */
  public double getMeasure(String measureName) {
    if (measureName.equals("measureExtraArcs")) {
      return measureExtraArcs();
    }
    if (measureName.equals("measureMissingArcs")) {
      return measureMissingArcs();
    }
    if (measureName.equals("measureReversedArcs")) {
      return measureReversedArcs();
    }
    if (measureName.equals("measureDivergence")) {
      return measureDivergence();
    }
    if (measureName.equals("measureBayesScore")) {
      return measureBayesScore();
    }
    if (measureName.equals("measureBDeuScore")) {
      return measureBDeuScore();
    }
    if (measureName.equals("measureMDLScore")) {
      return measureMDLScore();
    }
    if (measureName.equals("measureAICScore")) {
      return measureAICScore();
    }
    if (measureName.equals("measureEntropyScore")) {
      return measureEntropyScore();
    }
    return 0;
  } // getMeasure

  /**
   * Returns the revision string.
   * 
   * @return            the revision
   */
  public String getRevision() {
    return RevisionUtils.extract("$Revision: 5928 $");
  }
} // class BayesNet