source: src/main/java/weka/classifiers/bayes/net/BayesNetGenerator.java @ 16

/*
 * 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) 2003 University of Waikato, Hamilton, New Zealand
 * 
 */

package weka.classifiers.bayes.net;

import weka.classifiers.bayes.net.estimate.DiscreteEstimatorBayes;
import weka.core.Attribute;
import weka.core.FastVector;
import weka.core.Instance;
import weka.core.Instances;
import weka.core.DenseInstance;
import weka.core.Option;
import weka.core.OptionHandler;
import weka.core.RevisionUtils;
import weka.core.Utils;
import weka.estimators.Estimator;

import java.util.Enumeration;
import java.util.Random;
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://www.cs.waikato.ac.nz/~remco/weka.pdf
 * <p/>
 <!-- globalinfo-end -->
 * 
 <!-- options-start -->
 * Valid options are: <p/>
 * 
 * <pre> -B
 *  Generate network (instead of instances)
 * </pre>
 * 
 * <pre> -N &lt;integer&gt;
 *  Nr of nodes
 * </pre>
 * 
 * <pre> -A &lt;integer&gt;
 *  Nr of arcs
 * </pre>
 * 
 * <pre> -M &lt;integer&gt;
 *  Nr of instances
 * </pre>
 * 
 * <pre> -C &lt;integer&gt;
 *  Cardinality of the variables
 * </pre>
 * 
 * <pre> -S &lt;integer&gt;
 *  Seed for random number generator
 * </pre>
 * 
 * <pre> -F &lt;file&gt;
 *  The BIF file to obtain the structure from.
 * </pre>
 * 
 <!-- options-end -->
 *
 * @author Remco Bouckaert (rrb@xm.co.nz)
 * @version $Revision: 5987 $
 */
public class BayesNetGenerator extends EditableBayesNet {
    /** the seed value */
    int m_nSeed = 1;
    
    /** the random number generator */
    Random random;
    
    /** for serialization */
    static final long serialVersionUID = -7462571170596157720L;

        /**
         * Constructor for BayesNetGenerator.
         */
        public BayesNetGenerator() {
                super();
        } // c'tor

        /** 
         * Generate random connected Bayesian network with discrete nodes
         * having all the same cardinality.
         * 
         * @throws Exception if something goes wrong
         */
        public void generateRandomNetwork () throws Exception {
                if (m_otherBayesNet == null) {
                        // generate from scratch
                        Init(m_nNrOfNodes, m_nCardinality);
                        generateRandomNetworkStructure(m_nNrOfNodes, m_nNrOfArcs);
                        generateRandomDistributions(m_nNrOfNodes, m_nCardinality);
                } else {
                        // read from file, just copy parent sets and distributions
                        m_nNrOfNodes = m_otherBayesNet.getNrOfNodes();
                        m_ParentSets = m_otherBayesNet.getParentSets();
                        m_Distributions = m_otherBayesNet.getDistributions();


                        random = new Random(m_nSeed);
                        // initialize m_Instances
                        FastVector attInfo = new FastVector(m_nNrOfNodes);
                        // generate value strings

                        for (int iNode = 0; iNode < m_nNrOfNodes; iNode++) {
                                int nValues = m_otherBayesNet.getCardinality(iNode);
                                FastVector nomStrings = new FastVector(nValues + 1);
                                for (int iValue = 0; iValue < nValues; iValue++) {
                                        nomStrings.addElement(m_otherBayesNet.getNodeValue(iNode, iValue));
                                }
                                Attribute att = new Attribute(m_otherBayesNet.getNodeName(iNode), nomStrings);
                                attInfo.addElement(att);
                        }

                        m_Instances = new Instances(m_otherBayesNet.getName(), attInfo, 100);
                        m_Instances.setClassIndex(m_nNrOfNodes - 1);
                }
        } // GenerateRandomNetwork

        /** 
         * Init defines a minimal Bayes net with no arcs
         * @param nNodes number of nodes in the Bayes net 
         * @param nValues number of values each of the nodes can take
         * @throws Exception if something goes wrong
         */
        public void Init(int nNodes, int nValues) throws Exception {
                random = new Random(m_nSeed);
                // initialize structure
                FastVector attInfo = new FastVector(nNodes);
                // generate value strings
        FastVector nomStrings = new FastVector(nValues + 1);
        for (int iValue = 0; iValue < nValues; iValue++) {
                        nomStrings.addElement("Value" + (iValue + 1));
        }

                for (int iNode = 0; iNode < nNodes; iNode++) {
                        Attribute att = new Attribute("Node" + (iNode + 1), nomStrings);
                        attInfo.addElement(att);
                }
                m_Instances = new Instances("RandomNet", attInfo, 100);
                m_Instances.setClassIndex(nNodes - 1);
                setUseADTree(false);
//              m_bInitAsNaiveBayes = false;
//              m_bMarkovBlanketClassifier = false;
                initStructure();
                
                // initialize conditional distribution tables
                m_Distributions = new Estimator[nNodes][1];
                for (int iNode = 0; iNode < nNodes; iNode++) {
                        m_Distributions[iNode][0] = 
                          new DiscreteEstimatorBayes(nValues, getEstimator().getAlpha());
                }
                m_nEvidence = new FastVector(nNodes);
                for (int i = 0; i < nNodes; i++) {
                        m_nEvidence.addElement(-1);
                }
                m_fMarginP = new FastVector(nNodes);
                for (int i = 0; i < nNodes; i++) {
                        double[] P = new double[getCardinality(i)];
                        m_fMarginP.addElement(P);
                }

                m_nPositionX = new FastVector(nNodes);
                m_nPositionY = new FastVector(nNodes);
                for (int iNode = 0; iNode < nNodes; iNode++) {
                        m_nPositionX.addElement(iNode%10 * 50);
                        m_nPositionY.addElement(((int)(iNode/10)) * 50);
                }
        } // DefineNodes

        /** 
         * GenerateRandomNetworkStructure generate random connected Bayesian network 
         * @param nNodes number of nodes in the Bayes net to generate
         * @param nArcs number of arcs to generate. Must be between nNodes - 1 and nNodes * (nNodes-1) / 2
         * @throws Exception if number of arcs is incorrect
         */
        public void generateRandomNetworkStructure(int nNodes, int nArcs) 
                throws Exception
        {
                if (nArcs < nNodes - 1) {
                        throw new Exception("Number of arcs should be at least (nNodes - 1) = " + (nNodes - 1) + " instead of " + nArcs);
                }
                if (nArcs > nNodes * (nNodes - 1) / 2) {
                        throw new Exception("Number of arcs should be at most nNodes * (nNodes - 1) / 2 = "+ (nNodes * (nNodes - 1) / 2) + " instead of " + nArcs);
                }
                if (nArcs == 0) {return;} // deal with  patalogical case for nNodes = 1

            // first generate tree connecting all nodes
            generateTree(nNodes);
            // The tree contains nNodes - 1 arcs, so there are 
            // nArcs - (nNodes-1) to add at random.
            // All arcs point from lower to higher ordered nodes
            // so that acyclicity is ensured.
            for (int iArc = nNodes - 1; iArc < nArcs; iArc++) {
                boolean bDone = false;
                while (!bDone) {
                                int nNode1 = random.nextInt(nNodes);
                                int nNode2 = random.nextInt(nNodes);
                                if (nNode1 == nNode2) {nNode2 = (nNode1 + 1) % nNodes;}
                                if (nNode2 < nNode1) {int h = nNode1; nNode1 = nNode2; nNode2 = h;}
                                if (!m_ParentSets[nNode2].contains(nNode1)) {
                                        m_ParentSets[nNode2].addParent(nNode1, m_Instances);
                                        bDone = true;
                                }
                }
            }

        } // GenerateRandomNetworkStructure
        
        /** 
         * GenerateTree creates a tree-like network structure (actually a
         * forest) by starting with a randomly selected pair of nodes, add 
         * an arc between. Then keep on selecting one of the connected nodes 
         * and one of the unconnected ones and add an arrow between them, 
         * till all nodes are connected.
         * @param nNodes number of nodes in the Bayes net to generate
         */
        void generateTree(int nNodes) {
        boolean [] bConnected = new boolean [nNodes];
        // start adding an arc at random
                int nNode1 = random.nextInt(nNodes);
                int nNode2 = random.nextInt(nNodes);
                if (nNode1 == nNode2) {nNode2 = (nNode1 + 1) % nNodes;}
                if (nNode2 < nNode1) {int h = nNode1; nNode1 = nNode2; nNode2 = h;}
                m_ParentSets[nNode2].addParent(nNode1, m_Instances);
                bConnected[nNode1] = true;
                bConnected[nNode2] = true;
                // Repeatedly, select one of the connected nodes, and one of 
                // the unconnected nodes and add an arc.
            // All arcs point from lower to higher ordered nodes
            // so that acyclicity is ensured.
                for (int iArc = 2; iArc < nNodes; iArc++ ) {
                        int nNode = random.nextInt(nNodes);
                        nNode1 = 0; //  one of the connected nodes
                        while (nNode >= 0) {
                                nNode1 = (nNode1 + 1) % nNodes;
                                while (!bConnected[nNode1]) {
                                        nNode1 = (nNode1 + 1) % nNodes;
                                }
                                nNode--;
                        }
                        nNode = random.nextInt(nNodes);
                        nNode2 = 0; //  one of the unconnected nodes
                        while (nNode >= 0) {
                                nNode2 = (nNode2 + 1) % nNodes;
                                while (bConnected[nNode2]) {
                                        nNode2 = (nNode2 + 1) % nNodes;
                                }
                                nNode--;
                        }
                        if (nNode2 < nNode1) {int h = nNode1; nNode1 = nNode2; nNode2 = h;}
                        m_ParentSets[nNode2].addParent(nNode1, m_Instances);
                        bConnected[nNode1] = true;
                        bConnected[nNode2] = true;
                }
        } // GenerateTree
        
        /** 
         * GenerateRandomDistributions generates discrete conditional distribution tables
         * for all nodes of a Bayes network once a network structure has been determined.
         * @param nNodes number of nodes in the Bayes net 
         * @param nValues number of values each of the nodes can take
         */
    void generateRandomDistributions(int nNodes, int nValues) {
            // Reserve space for CPTs
        int nMaxParentCardinality = 1;
            for (int iAttribute = 0; iAttribute < nNodes; iAttribute++) {
            if (m_ParentSets[iAttribute].getCardinalityOfParents() > nMaxParentCardinality) {
                     nMaxParentCardinality = m_ParentSets[iAttribute].getCardinalityOfParents();
            } 
        } 

        // Reserve plenty of memory
        m_Distributions = new Estimator[m_Instances.numAttributes()][nMaxParentCardinality];

        // estimate CPTs
        for (int iAttribute = 0; iAttribute < nNodes; iAttribute++) {
                int [] nPs = new int [nValues + 1];
                nPs[0] = 0;
                nPs[nValues] = 1000;
            for (int iParent = 0; iParent < m_ParentSets[iAttribute].getCardinalityOfParents(); iParent++) {
                // fill array with random nr's
                for (int iValue = 1; iValue < nValues; iValue++)  {
                        nPs[iValue] = random.nextInt(1000);
                }
                // sort
                for (int iValue = 1; iValue < nValues; iValue++)  {
                        for (int iValue2 = iValue + 1; iValue2 < nValues; iValue2++)  {
                                if (nPs[iValue2] < nPs[iValue]) {
                                        int h = nPs[iValue2]; nPs[iValue2] = nPs[iValue]; nPs[iValue] = h;
                                }
                        }
                }
                // assign to probability tables
                DiscreteEstimatorBayes d = new DiscreteEstimatorBayes(nValues, getEstimator().getAlpha());
                for (int iValue = 0; iValue < nValues; iValue++)  {
                        d.addValue(iValue, nPs[iValue + 1] - nPs[iValue]);
                }
                    m_Distributions[iAttribute][iParent] = d;
            } 
        } 
    } // GenerateRandomDistributions
    
        /**
         * GenerateInstances generates random instances sampling from the
         * distribution represented by the Bayes network structure. It assumes
         * a Bayes network structure has been initialized
         * 
         * @throws Exception if something goes wrong
         */
        public void generateInstances () throws Exception {
            int [] order = getOrder();
                for (int iInstance = 0; iInstance < m_nNrOfInstances; iInstance++) {
                    int nNrOfAtts = m_Instances.numAttributes();
                        Instance instance = new DenseInstance(nNrOfAtts);
                        instance.setDataset(m_Instances);
                        for (int iAtt2 = 0; iAtt2 < nNrOfAtts; iAtt2++) {
                            int iAtt = order[iAtt2];

                                double iCPT = 0;

                                for (int iParent = 0; iParent < m_ParentSets[iAtt].getNrOfParents(); iParent++) {
                                  int nParent = m_ParentSets[iAtt].getParent(iParent);
                                  iCPT = iCPT * m_Instances.attribute(nParent).numValues() + instance.value(nParent);
                                } 
        
                                double fRandom = random.nextInt(1000) / 1000.0f;
                                int iValue = 0;
                                while (fRandom > m_Distributions[iAtt][(int) iCPT].getProbability(iValue)) {
                                        fRandom = fRandom - m_Distributions[iAtt][(int) iCPT].getProbability(iValue);
                                        iValue++ ;
                                }
                                instance.setValue(iAtt, iValue);
                        }
                        m_Instances.add(instance);
                }
        } // GenerateInstances

    /**
     * @throws Exception if there's a cycle in the graph
     */ 
    int [] getOrder() throws Exception {
        int nNrOfAtts = m_Instances.numAttributes();
        int [] order = new int[nNrOfAtts];
        boolean [] bDone = new boolean[nNrOfAtts];
        for (int iAtt = 0; iAtt < nNrOfAtts; iAtt++) {
            int iAtt2 = 0; 
            boolean allParentsDone = false;
            while (!allParentsDone && iAtt2 < nNrOfAtts) {
                if (!bDone[iAtt2]) {
                    allParentsDone = true;
                    int iParent = 0;
                    while (allParentsDone && iParent < m_ParentSets[iAtt2].getNrOfParents()) {
                        allParentsDone = bDone[m_ParentSets[iAtt2].getParent(iParent++)];
                    }
                    if (allParentsDone && iParent == m_ParentSets[iAtt2].getNrOfParents()) {
                        order[iAtt] = iAtt2;
                        bDone[iAtt2] = true;
                    } else {
                        iAtt2++;
                    }
                } else {
                    iAtt2++;
                }
            }
            if (!allParentsDone && iAtt2 == nNrOfAtts) {
                throw new Exception("There appears to be a cycle in the graph");
            }
        }
        return order;
    } // getOrder

        /**
         * Returns either the net (if BIF format) or the generated instances
         * 
         * @return either the net or the generated instances
         */
        public String toString() {
          if (m_bGenerateNet) {
            return toXMLBIF03();
          }
          return m_Instances.toString();
        } // toString
        

        boolean m_bGenerateNet = false;
        int m_nNrOfNodes = 10;
        int m_nNrOfArcs = 10;
        int m_nNrOfInstances = 10;
        int m_nCardinality = 2;
        String m_sBIFFile = "";

        void setNrOfNodes(int nNrOfNodes) {m_nNrOfNodes = nNrOfNodes;}
        void setNrOfArcs(int nNrOfArcs) {m_nNrOfArcs = nNrOfArcs;}
        void setNrOfInstances(int nNrOfInstances) {m_nNrOfInstances = nNrOfInstances;}
        void setCardinality(int nCardinality) {m_nCardinality = nCardinality;}
        void setSeed(int nSeed) {m_nSeed = nSeed;}

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

                newVector.addElement(new Option("\tGenerate network (instead of instances)\n", "B", 0, "-B"));
                newVector.addElement(new Option("\tNr of nodes\n", "N", 1, "-N <integer>"));
                newVector.addElement(new Option("\tNr of arcs\n", "A", 1, "-A <integer>"));
                newVector.addElement(new Option("\tNr of instances\n", "M", 1, "-M <integer>"));
                newVector.addElement(new Option("\tCardinality of the variables\n", "C", 1, "-C <integer>"));
                newVector.addElement(new Option("\tSeed for random number generator\n", "S", 1, "-S <integer>"));
                newVector.addElement(new Option("\tThe BIF file to obtain the structure from.\n", "F", 1, "-F <file>"));

                return newVector.elements();
        } // listOptions

        /**
         * Parses a given list of options. <p/>
         * 
         <!-- options-start -->
         * Valid options are: <p/>
         * 
         * <pre> -B
         *  Generate network (instead of instances)
         * </pre>
         * 
         * <pre> -N &lt;integer&gt;
         *  Nr of nodes
         * </pre>
         * 
         * <pre> -A &lt;integer&gt;
         *  Nr of arcs
         * </pre>
         * 
         * <pre> -M &lt;integer&gt;
         *  Nr of instances
         * </pre>
         * 
         * <pre> -C &lt;integer&gt;
         *  Cardinality of the variables
         * </pre>
         * 
         * <pre> -S &lt;integer&gt;
         *  Seed for random number generator
         * </pre>
         * 
         * <pre> -F &lt;file&gt;
         *  The BIF file to obtain the structure from.
         * </pre>
         * 
         <!-- options-end -->
         *
         * @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 {
                m_bGenerateNet = Utils.getFlag('B', options);

                String sNrOfNodes = Utils.getOption('N', options);
                if (sNrOfNodes.length() != 0) {
                  setNrOfNodes(Integer.parseInt(sNrOfNodes));
                } else {
                        setNrOfNodes(10);
                } 

                String sNrOfArcs = Utils.getOption('A', options);
                if (sNrOfArcs.length() != 0) {
                  setNrOfArcs(Integer.parseInt(sNrOfArcs));
                } else {
                        setNrOfArcs(10);
                } 

                String sNrOfInstances = Utils.getOption('M', options);
                if (sNrOfInstances.length() != 0) {
                  setNrOfInstances(Integer.parseInt(sNrOfInstances));
                } else {
                        setNrOfInstances(10);
                } 

                String sCardinality = Utils.getOption('C', options);
                if (sCardinality.length() != 0) {
                  setCardinality(Integer.parseInt(sCardinality));
                } else {
                        setCardinality(2);
                } 

                String sSeed = Utils.getOption('S', options);
                if (sSeed.length() != 0) {
                  setSeed(Integer.parseInt(sSeed));
                } else {
                        setSeed(1);
                } 

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

        /**
         * Gets the current settings of the classifier.
         * 
         * @return an array of strings suitable for passing to setOptions
         */
        public String[] getOptions() {
                String[] options = new String[13];
                int current = 0;
                if (m_bGenerateNet) {
                  options[current++] = "-B";
                } 

                options[current++] = "-N";
                options[current++] = "" + m_nNrOfNodes;

                options[current++] = "-A";
                options[current++] = "" + m_nNrOfArcs;

                options[current++] = "-M";
                options[current++] = "" + m_nNrOfInstances;

                options[current++] = "-C";
                options[current++] = "" + m_nCardinality;

                options[current++] = "-S";
                options[current++] = "" + m_nSeed;

                if (m_sBIFFile.length() != 0) {
                  options[current++] = "-F";
                  options[current++] = "" + m_sBIFFile;
                }

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

                return options;
        } // getOptions

    /**
     * prints all the options to stdout
     */
    protected static void printOptions(OptionHandler o) {
      Enumeration enm = o.listOptions();
      
      System.out.println("Options for " + o.getClass().getName() + ":\n");
      
      while (enm.hasMoreElements()) {
        Option option = (Option) enm.nextElement();
        System.out.println(option.synopsis());
        System.out.println(option.description());
      }
    }
    
    /**
     * Returns the revision string.
     * 
     * @return          the revision
     */
    public String getRevision() {
      return RevisionUtils.extract("$Revision: 5987 $");
    }

    /**
     * Main method
     * 
     * @param args the commandline parameters
     */
    static public void main(String [] args) {
                BayesNetGenerator b = new BayesNetGenerator();
        try {
                if ( (args.length == 0) || (Utils.getFlag('h', args)) ) {
                        printOptions(b);
                        return;
                }
                b.setOptions(args);
                
                b.generateRandomNetwork();
                if (!b.m_bGenerateNet) { // skip if not required
                                b.generateInstances();
                }
                System.out.println(b.toString());
        } catch (Exception e) {
                e.printStackTrace();
                printOptions(b);
        }
    } // main
    
} // class BayesNetGenerator