forestaugmenter.java

bayes network classifier toolbox 贝叶斯网络分类工具箱

/**
 *  JBNC - Bayesian Network Classifiers Toolbox <p>
 *
 *  Latest release available at http://sourceforge.net/projects/jbnc/ <p>
 *
 *  Copyright (C) 1999-2003 Jarek Sacha <p>
 *
 *  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. <p>
 *
 *  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. <p>
 *
 *  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., 59 Temple
 *  Place - Suite 330, Boston, MA 02111-1307, USA. <br>
 *  http://www.fsf.org/licenses/gpl.txt
 */
package jbnc.operators;

import BayesianNetworks.BayesNet;
import jbnc.graphs.Edge;
import jbnc.graphs.Graph;
import jbnc.graphs.MinSpanTree;
import jbnc.graphs.Vertex;
import jbnc.measures.QualityMeasure;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 *  Constructs Forest Augmented Naive Bayes classifier (FAN).<br>
 *  <br>
 *
 *
 * @author     Jarek Sacha
 * @since      June 1, 1999
 */
public class ForestAugmenter extends Augmenter {
  /**
   *  Description of the Method
   *
   * @param  gamma          Description of Parameter
   * @param  lambda         Description of Parameter
   * @param  fc             Description of Parameter
   * @param  qm             Description of Parameter
   * @param  usePriors      Description of Parameter
   * @param  alpha_ijk      Description of Parameter
   * @return                Description of the Returned Value
   * @exception  Exception  Description of Exception
   */
  public final Result train(List gamma,
                            List lambda, jbnc.util.FrequencyCalc fc,
                            QualityMeasure qm,
                            boolean usePriors,
                            double alpha_ijk) throws Exception {
    // Check if it is possible to augment
    if (gamma.size() <= 1 && (lambda == null || lambda.size() == 0)) {
      Result r = new Result();
      r.bayesNet = ClassDepend.create(null, gamma, fc.names);

      return r;
    }

    // Allocate cmi if needed
    if (cmi == null) {
      cmi = new jbnc.util.CondMutualInfo(fc);
    }

    // Compute conditianal mutual information for each pair of input nodes
    // conditioned on the class node.
    boolean[] cond = new boolean[fc.names.length];
    Iterator gammaIterator = gamma.iterator();
    while (gammaIterator.hasNext()) {
      int v = ((Integer) gammaIterator.next()).intValue();
      cond[v] = true;
    }
    double[][] cm = cmi.get(cond, usePriors, alpha_ijk);

    // Create fully connected graph for input nodes
    LinkedList allConnectedNodes = new LinkedList();
    allConnectedNodes.addAll(gamma);
    if (lambda != null) {
      allConnectedNodes.addAll(lambda);
    }
    Graph fullGraph = createFullGraph(cm, allConnectedNodes, fc.names);

    // Get sorted edges of the maximum spanning tree
    MinSpanTree minTree = new MinSpanTree();
    Integer firstGamma = (Integer) gamma.get(0);
    Vertex rootVertex = fullGraph.getVertex(firstGamma.intValue());
    Edge[] treeEdges = minTree.getDirectedEdges(fullGraph, rootVertex);

    // Prepare quality measures
    qm.setUsePriors(usePriors);
    qm.setAlphaK(alpha_ijk);

    // Create initial network structure (selective naive Bayes)
    BayesNet bestNet = ClassDepend.create(null, gamma, fc.names);
    double bestScore = qm.evaluate(bestNet);
    int bestNbAugmentingEdges = 0;

    if (debugMode) {
      System.out.println("Net #" + bestNbAugmentingEdges + " score: " + bestScore);
    }

    // Add one edge at a time and test quality of new network
    Graph augmentingGraph = new Graph();
    for (int i = 0; i < treeEdges.length; ++i) {
      augmentingGraph.addEdge(treeEdges[i]);
      BayesNet thisNet = ClassDepend.create(augmentingGraph, gamma,
          fc.names);
      double score = qm.evaluate(thisNet);

      if (score > bestScore) {
        bestScore = score;
        bestNet = thisNet;
        bestNbAugmentingEdges = i + 1;
      }

      if (debugMode) {
        System.out.println("Net #" + (i + 1) + " score: " + score);
      }
    }

    if (debugMode) {
      System.out.println("Best net #" + bestNbAugmentingEdges
          + ", score: " + bestScore);
    }

    // Prepare results
    Result r = new Result();
    r.bayesNet = bestNet;
    r.quality = new Double(bestScore);

    return r;
  }
}