naivebayescat.java

Naive Bayes算法java代码

package nb;

import shared.AttrInfo;
import shared.AugCategory;
import shared.BagCounters;
import shared.CatDist;
import shared.Categorizer;
import shared.DisplayPref;
import shared.Entropy;
import shared.Error;
import shared.Globals;
import shared.Instance;
import shared.InstanceList;
import shared.MLJ;
import shared.NominalAttrInfo;
import shared.Schema;
import shared.StatData;

import java.io.BufferedWriter;
import java.io.IOException;

/** This categorizer returns the category (label) that had the
  * greatest relative probability of being correct, assuming
  * independence of attributes. Relative probability of a label
  * is calculated by multiplying the relative probability for
  * each attribute.  The calculation of relative probabity for a
  * label on a single attribute depends on whether the attribute
  * is descrete or continuous.
  * By Bayes Theorem, P(L=l | X1=x1, X2=x2, ... Xn=xn)
  * = P(X1=x1, X2=x2, ... Xn=xn | L=l)*P(L=l)/P(X)
  * where P(X) is P(X1=x1, ..., Xn=xn).
  * Since P(X) is constant independent of the classes, we
  * can ignore it.
  * The Naive Bayesian approach asssumes complete independence
  * of the attributes GIVEN the label, thus
  * P(X1=x1, X2=x2, ... Xn=xn | L=l) =
  * P(X1=x1|L=l)*P(X2=x2|L)*... P(Xn=xn|L)
  * and P(X1=x1|L=l) = P(X1=x1 ^ L=l)/P(L=l) where this
  * quantity is approximated form the data.
  * When the computed probabilities for two labels have the same
  * value, we break the tie in favor of the most prevalent label.
  * 
  * If the instance being categorized has the first attribute = 1,
  * and in the training set label A occured 20 times, 10 of
  * which had value 1 for the first attribute, then the
  * relative probability is 10/20 = 0.5.
  *
  * For continuous (real) attributes, the relative probability
  * is based on the Normal Distribution of the values of the
  * attribute on training instances with the label.  The actual
  * calculation is done with the Normal Density; constants,
  * which do not affect the relative probability between labels,
  * are ignored.  For example, say 3 training instances have
  * label 1 and these instances have the following values for a
  * continous attribute: 35, 50, 65.  The program would use the
  * mean and variance of this "sample" along with the attribute
  * value of the instance that is being categorized in the
  * Normal Density equation.  The evaluation of the Normal
  * Density equation, without constant factors, provides the
  * relative probability.
  *
  * Unknown attributes are skipped over.
  * 
  * Assumptions :  This method calculates the probability of a label as the
  * product of the probabilities of each attribute.
  * This is assuming that the attributes are
  * independent, a condition not likely corresponding to
  * reality.  Thus the "Naive" of the title.
  * This method assumes that all continous attributes have a
  * Normal distribution for each label value.
  * 
  * Comments :   For nominal attributes, if a label does not have
  * any occurences for a given attribute value
  * of the test instance, a probability of
  * noMatchesFactor * ( 1 / # instances in training set )
  * is used.
  *
  * For nominal attributes, if an attribute value does not
  * occur in the training set, the attribute is skipped
  * in the categorizer, since it does not serve to
  * differentiate the labels.
  *  
  * The code can handle dealing with unknowns as a special
  * value by doing the is_unknown only in the real attribute
  * case.
  *
  * Helper class NBNorm is a simple structure to hold the
  * parameters needed to calculate the Normal Distribution
  * of each Attribute,Label pair.  The NBNorms are stored in
  * a Array2 table "continNorm" which is indexed by attribute
  * number and label value.
  *
  * For continuous attributes the variance must not equal 0 since
  * it is in the denominator.  If the variance is undefined for
  * a label value (e.g. if a label only has only one instance
  * in the training set), NaiveBayesInd will declare the
  * variance to be defaultVariance, a static variable.  In
  * cases where the variance is defined but equal to 0,
  * NaiveBayesInd will declare the variance to be epsilon,
  * a very small static variable.
  *
  * For continous attributes, if a label does not occur in
  * the training set, a zero relative probability is
  * assigned.  If a label occurs in the training set but only
  * has unknown values for the attribute, noMatchesFactor is
  * used as in the nominal attribute case above.
  *
  * Complexity : categorize() is O(ln) where l = the number of categories
  * and n = the number of attributes.
  *
  * @author James Plummer 5/15/2001 Ported to Java
  * @author Eric Bauer and Clay Kunz 5/24/1996 Added L'aplace correction
  * @author Robert Allen 12/03/94 Initial revision
  */
public class NaiveBayesCat extends Categorizer {
  public final static String endl = new String("\n");
  // Member data (also see public data)
  private BagCounters nominCounts;		// hold data on nominal attributs
  private NBNorm[][] continNorm;		        // hold data on real attributes
  private double trainWeight;
  private int numAttributes;
  private boolean useLaplace;                     // turn on to activate Laplace correction
  private double mEstimateFactor;                // noise in Laplace correction
  private double[] attrImportance;               // importance values per attribute
  private boolean[] unkIsVal;               // should unknowns be special values? // decisions per attribute

  /** Ported from C++ > 
    *   enum UnknownIsValueEnum { unknownNo, unknownYes, unknownAuto }; //C++ equivalent
    */
  public static final int unknownNo = 1;
  public static final int unknownYes = 2;
  public static final int unknownAuto = 3;
  private int unknownIsValue; // 1, 2, 3.

  private double klThreshold;
   
  /** Fraction of a single occurence to use in cases when a label
    * has no occurences of a given nominal value in the training set:
    */
  private double noMatchesFactor;

  /** If true Evidence projection is used.
    */
  private boolean useEvidenceProjection;
  /** The scale factor to use with Evidence Projection.
    */ 
  private double evidenceFactor;

  /** Categorizer option defaults.
    */
  public static final double defaultMEstimateFactor = 1.0;
  public static final boolean defaultLaplaceCorrection = false;
  public static final int defaultUnknownIsValue = unknownNo;
  public static final double defaultKLThreshold = 0.1;
  public static final double defaultNoMatchesFactor = 0.0;
  public static final boolean defaultUseEvidenceProjection = false;
  public static final double defaultEvidenceFactor = 1.0;

  /** Value to use for Variance when actual variance = 0:
    */
  public static final double epsilon = .01;
  /** Value to use for Vaiance when actual variance is undefined becase there
    * is only one occurance.
    */
  public static final double defaultVariance = 1.0;

/** Constructor 
  * @param dscr - the description of this Inducer.
  * @param instList - training data.
  */
  public NaiveBayesCat(String dscr, InstanceList instList) {
    super(instList.num_categories(), dscr, instList.get_schema());
    nominCounts = instList.counters();
    trainWeight = instList.total_weight();
    numAttributes = instList.num_attr();
    logOptions.LOG(3, "NBC . . numAttributes = "+numAttributes);
    useLaplace = defaultLaplaceCorrection;
    mEstimateFactor = defaultMEstimateFactor;
    unkIsVal = null;
    unknownIsValue = defaultUnknownIsValue;
    klThreshold = defaultKLThreshold;
    noMatchesFactor = defaultNoMatchesFactor;
    useEvidenceProjection = defaultUseEvidenceProjection;
    evidenceFactor = defaultEvidenceFactor;

    attrImportance = this.compute_importance(instList);
    continNorm = this.compute_contin_norm(instList);
  }

  /** Copy Constructor.
    * @param source - the NaiveBayesCat to copy.
    */
  public NaiveBayesCat(NaiveBayesCat source) {
    super(source.num_categories(), source.description(), source.get_schema());
    nominCounts = new BagCounters(source.nominCounts);
    continNorm = source.copyContinNorm();
    attrImportance = source.copyAttrImportance();
    trainWeight = source.trainWeight;
    numAttributes = source.numAttributes;
    useLaplace = source.useLaplace;
    mEstimateFactor = source.mEstimateFactor;
    unkIsVal = null;
    unknownIsValue = source.unknownIsValue;
    klThreshold = source.klThreshold;
    noMatchesFactor = source.noMatchesFactor;
    useEvidenceProjection = source.useEvidenceProjection;
    evidenceFactor = source.evidenceFactor;
  }

  /** Categorizes a single instances based upon the training data.
    * @param instance - the instance to categorize.
    * @return the predicted category.
    */
  public AugCategory categorize(Instance instance) {
    CatDist cDist = score(instance);
    AugCategory cat = cDist.best_category();
    return cat;
  }
  /** Simple Method to return an ID.
    * @return - an int representing this Categorizer.
    * @deprecated CLASS_NB_CATEGORIZER has been deprecated
    */
  public int class_id() {return CLASS_NB_CATEGORIZER;}

  /** Returns a pointer to a deep copy of this NaiveBayesCat.
    * @return - the copy of this Categorizer.
    */
  public Object clone() {
    if ( !(this instanceof NaiveBayesCat) ) { 
      Error.fatalErr("NaiveBayesCat.clone: invoked for improper class");
    }
    return new NaiveBayesCat(this);
  }
  /** Compute the norms of the continuous attributes
    * @param instList - the instances to calculate.
    * @return the array[][] of NBNorms.
    */
  public static NBNorm[][] compute_contin_norm(InstanceList instList) {
    int contAttrCount = 0;
    int numCategories = instList.num_categories();
    Schema schema = instList.get_schema();
    int numAttributes = schema.num_attr();
   
    // start labels at -1 for unknown
    NBNorm[][] normDens = new NBNorm[numAttributes][numCategories + 1]; // no initial value
    for (int m=0; m<normDens.length;m++) {
      for (int n=0; n<normDens[m].length;n++) {
        normDens[m][n] = new NBNorm();
        normDens[m][n].set_mean_and_var(0,0);
      }
    }
      
    // loop through each attribute, and process all instances for each
    // continuous one
    for (int attrNum = 0; attrNum < numAttributes; attrNum++) {
      AttrInfo attrinfo = schema.attr_info(attrNum);
      if (attrinfo.can_cast_to_real()) {
	  // this is a continuous attribute
	  contAttrCount++;
	 
	  // read each occurance in the list and feed the stats for attribute
	  StatData[] continStats = new StatData[numCategories + 1];
        for (int j=0; j<continStats.length;j++) {
          continStats[j]=new StatData();
        }
//	  for (ILPix pix(instList); pix; ++pix) { //What?
        for (int i = 0; i < instList.num_instances(); i++) {
	    Instance inst = new Instance((Instance)instList.instance_list().get(i));
	    int labelVal = schema.label_info().cast_to_nominal().get_nominal_val(inst.get_label()); //for some reason the label values for the instances are one number higher than the actual value
	    MLJ.ASSERT(labelVal < numCategories, " NaiveBayesCat.compute_contin_norm()");

            // Ignore unknowns.
	    if ( !attrinfo.is_unknown(inst.get_value(attrNum))) {
	       double value = attrinfo.get_real_val(inst.get_value(attrNum));
	       continStats[labelVal].insert( value );
	    }
	  }

	  double mean;
        double var;
	  // extract Normal Density parameters into normDens table
	  for (int label = 0; label < numCategories; label++) {
	    if (continStats[label].size() == 0 ) {
	       mean = 0;
	       var = defaultVariance;
	    }
	    else {
	       mean = continStats[label].mean();
	       if (continStats[label].size() == 1 )
		  var = defaultVariance;
	       
	       else if ( (var = continStats[label].variance(0))<=0 )   // var == 0
		  var = epsilon;
	    }
	    normDens[attrNum][label].set_mean_and_var(mean,var);

	    //@@ pass in a log option?
	    //LOG(3, " Continuous Attribute # " << attrNum <<
	    //", Label " << label << ": Mean = " << mean <<
	    //", Variation = " << var << endl );
	  }
      } // end of handling this continous attribute
    }    // end of loop through all attributes

    if (contAttrCount==0) {  // no continous attributes found
      normDens = null;
    }
    return normDens;
  }

  /** Computes importance values for each nominal attribute using
    * the mutual_info (entropy).
    * Static function; used as helper by train() below.
    * @param instList - the instances to use.
    * @return - the array[] of importance values.
    */
  public static double[] compute_importance(InstanceList instList) {
    double[] attrImp = new double[instList.num_attr()];
    for (int i = 0; i < attrImp.length; i++) {
      attrImp[i] = 0;
    }
   
    double ent = Entropy.entropy(instList);
    if (ent == Globals.UNDEFINED_REAL) {
      Error.fatalErr("compute_importance: undefined entropy");
    }
    if(ent < 0 && -ent < MLJ.realEpsilon) {
      ent = 0;
    }
    for (int i=0; i<instList.num_attr(); i++) {
      if(instList.get_schema().attr_info(i).can_cast_to_real()) {
	  attrImp[i] = 0;
      }
      else if(instList.get_schema().attr_info(i).can_cast_to_nominal()) {
	  if(ent <= 0) {