san.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.dataset.AttributeSpecs;
import jbnc.measures.QualityMeasure;

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

/**
 * Constructs Selective Augmented Naive Bayes operator (SAN).<br> <br>
 *
 * @author Jarek Sacha
 * @since June 1, 1999
 */
public class SAN extends Operator {

    /**  LOCAL */

    /**
     * Whether nodes that are not dependent on the class node should be
     * dsiscarded from augmenting tree creation.
     */
    protected boolean discardNonDependent = false;


    /**
     * @param discard
     */
    public void setDiscardNonDependent(boolean discard) {
        discardNonDependent = discard;
    }


    /**
     * @return whether nondependent nodes are discared.
     */
    public boolean getDiscardNonDependent() {
        return discardNonDependent;
    }


    /**
     * Description of the Method
     *
     * @param fc             Description of Parameter
     * @param qualityMeasure Description of Parameter
     * @param augmenter      Description of Parameter
     * @param usePriors      Description of Parameter
     * @param alpha_ijk      Description of Parameter
     * @return Description of the Returned Value
     * @throws Exception Description of Exception
     */
    public BayesNet train(jbnc.util.FrequencyCalc fc,
                          QualityMeasure qualityMeasure,
                          Augmenter augmenter,
                          boolean usePriors,
                          double alpha_ijk) throws Exception {
        AttributeSpecs[] names = fc.names;

        if (names.length < 3) {
            // nothing to augment
            LinkedList gamma = new LinkedList();
            for (int i = 0; i < names.length; ++i) {
                gamma.add(new Integer(i));
            }

            return ClassDepend.create(null, gamma, names);
        }

        // Check quality measure
        if (qualityMeasure == null) {
            throw new Exception("Network quality measure has not been assigned.");
        }

        qualityMeasure.setUsePriors(usePriors);
        qualityMeasure.setAlphaK(alpha_ijk);

        //
        int nbAttrib = names.length - 1;
        int nbVars = nbAttrib + 1;
        LinkedList gamma = new LinkedList();
        //indexes of vertices dependent on C
        LinkedList lambda = new LinkedList();
        //indexes of vertices independent from C
        for (int i = 0; i < nbAttrib; i++) {
            lambda.add(new Integer(i));
        }

        BayesNet bestNet = null;
        //best bayes net constructed so far
        double bestScore = Double.NEGATIVE_INFINITY;
        //score of the best bayes net for curreent gamma set

        LinkedList bestGamma = null;

        while (!lambda.isEmpty()) {
            Integer bestVertex = null;
            BayesNet bestLocalNet = null;
            double bestLocalScore = Double.NEGATIVE_INFINITY;

            LinkedList lambdaPrim = new LinkedList(lambda);

            // Iterate through lambda looking for best candidate vertex
            Iterator lambdaIterator = lambda.iterator();
            while (lambdaIterator.hasNext()) {
                // Consider vertex for testing
                Integer thisVertex = (Integer) lambdaIterator.next();

                // Add it temporalilly to class dependent vertices
                gamma.add(thisVertex);
                lambdaPrim.remove(thisVertex);

                Augmenter.Result ar;
                if (discardNonDependent) {
                    ar = augmenter.train(gamma, null, fc,
                            qualityMeasure, usePriors, alpha_ijk);
                } else {
                    ar = augmenter.train(gamma, lambdaPrim, fc,
                            qualityMeasure, usePriors, alpha_ijk);
                }

                BayesNet thisNet = ar.bayesNet;

                // Test quality of the network
                double score = 0;
                if (ar.quality != null) {
                    score = ar.quality.doubleValue();
                } else {
                    score = qualityMeasure.evaluate(thisNet);
                }

                if (score > bestLocalScore) {
                    bestLocalScore = score;
                    bestLocalNet = thisNet;
                    bestVertex = thisVertex;
                }

                // Remove current vertex from class dependent vertices
                gamma.remove(thisVertex);
                lambdaPrim.add(thisVertex);
            }
            // while(lambdaIterator.hasNext())

            lambda.remove(bestVertex);
            gamma.add(bestVertex);

            if (bestLocalScore > bestScore) {
                bestScore = bestLocalScore;
                bestNet = bestLocalNet;
                bestGamma = new LinkedList(gamma);
            }

            if (debugMode) {
                System.out.println("Best vertex #" + bestVertex + ": '"
                        + fc.names[bestVertex.intValue()].getName() + "'");
                System.out.println("Best local score #" + gamma.size() + " = "
                        + bestLocalScore);
            }
        }
        //while(!lambda.isEmpty());

        if (debugMode) {
            System.out.print("\nBest score = " + bestScore + " ");
            if (bestGamma != null) {
                System.out.println(" [" + bestGamma.size() + "/" + nbAttrib + "]");
            } else {
                System.out.println(" [0/" + nbAttrib + "]");
            }
//      System.out.println("Best gamma = "+bestGamma.toString());
        }

        return bestNet;
    }

}